Relational Operators (Comparison Operators) in c++

Relational Operators (also known as Comparison Operators)in C++

There is often need to compare two values in program. Such as whether the value in one a variable is greater than the value in the other variable. Depending upon the situation we can perform different operation for different cases.
Relational Operators (also known as Comparison Operators) are used to compare two values. The result of comparison is a boolean value.
The boolean value can either be true or false. In c and c++, 1 represents true and 0 represent false. However in c++ the data type bool has been introduced, which holds only two values either true or false. The value true in bool corresponds to 1 and 0 corresponds to false.

List of Relational Operators (aka Comparison Operators)


OperatorOperator's NameExampleResult
<less than5<101(true)
<=less than or equal to5<=101(true)
>greater than5>100(false)
>=greater than or equal to5>=100(false)
==equal to5==100(false)
!=not equal to5!=21(true)

/* A c++ program example to demonstrate that the result of comparison is always a boolean value, either 1 or 0. The value 1 represents true and 0 represents false. */



#include <iostream>
#include <iomanip>

using namespace std;

int main ()
{
    cout << "5 <10" << setw (4) << ": " << (5 < 10) << endl;
    cout << "5 <=10" << setw(3) << ": " << (5 <= 10) << endl;
    cout << "5 >10" << setw (4) << ": " << (5 > 10) << endl;
    cout << "5 >= 10" << setw (2) << ": " << (5 >= 10) << endl;
    cout << "5 == 10" << setw (2) << ": " << (5 == 10) << endl;
    cout << "5 != 10" << setw (2) << ": " << (5 != 10) << endl;

    return 0;
}


This chapter is important to understand selection and looping statement. In coming chapters we will learn about selection and looping statement.

C++ example for Abstract Factory Design Pattern

The Abstract Factory Design Pattern provides an interface for creating families of related or dependent objects without specifying their concrete classes. The following UML class diagram explains how the Abstract Factory fits with the rest.


The following is example of Abstract factory design pattern:



//Program tested on Microsoft Visual Studio 2008 - Zahid Ghadialy
//Abstract Factory is part of Creational Patterns
//Creational Patterns deal with initializing and configuring classes and objects
//Abstract Factory creates an instance of several families of classes

//We will take an example of Animal Classes and Abstract them.
//There are 2 types of animals; Herbivores and Carnivores.
//The rule of nature is that Carnivores eats Herbivores which will be shown
//Different animas live in different continents but the same rule applies

#include<iostream>
#include<string>

using namespace
std;

//The Herbivore class - The 'AbstractProductA' abstract class
class Herbivore
{

public
:
virtual const
string& getName(void)=0;
};


//Lets define couple of Herbivores called Cow and Deer
class Cow : public Herbivore //The 'ProductA1' class
{
public
:
Cow():name("Cow"){};
//default destructor
const string& getName(void) {return name;}
private
:
string name;
};


class
Deer : public Herbivore //The 'ProductA2' class
{
public
:
Deer():name("Deer"){};
//default destructor
const string& getName(void) {return name;}
private
:
string name;
};


//The Carnivore class - The 'AbstractProductB' abstract class
class Carnivore
{

public
:
virtual const
string& getName(void)=0;
virtual
void eat(Herbivore& h) = 0;
};


//Lets define couple of Carnivores called Lion and Wolf
class Lion : public Carnivore //The 'ProductB1' class
{
public
:
Lion():name("Lion"){};
const
string& getName(void) {return name;}
void
eat(Herbivore& h) //override
{
cout << name << " eats " << h.getName() << endl;
}

private
:
string name;
};


class
Wolf : public Carnivore //The 'ProductB2' class
{
public
:
Wolf():name("Wolf"){};
const
string& getName(void) {return name;}
void
eat(Herbivore& h) //override
{
cout << name << " eats " << h.getName() << endl;
}

private
:
string name;
};


//The 'AbstractFactory' abstract class
class ContinentFactory
{

public
:
virtual
Herbivore& CreateHerbivore() = 0;
virtual
Carnivore& CreateCarnivore() = 0;
};


class
AfricaFactory : public ContinentFactory //The 'ConcreteFactory1' class
{
Herbivore& CreateHerbivore()
{

return
*(dynamic_cast<Herbivore *>(new Cow()));
}

Carnivore& CreateCarnivore()
{

return
*(dynamic_cast<Carnivore *>(new Lion()));
}
};


class
AmericaFactory : public ContinentFactory //The 'ConcreteFactory2' class
{
Herbivore& CreateHerbivore()
{

return
*(dynamic_cast<Herbivore *>(new Deer()));
}

Carnivore& CreateCarnivore()
{

return
*(dynamic_cast<Carnivore *>(new Wolf()));
}
};


//The 'Client' class
class AnimalWorld
{

public
:
AnimalWorld(ContinentFactory& factory):_herbivore(factory.CreateHerbivore()),_carnivore(factory.CreateCarnivore())
{
}

void
RunFoodChain()
{

_carnivore.eat(_herbivore);
}

private
:
Herbivore& _herbivore;
Carnivore& _carnivore;
};


int
main()
{

//Create and run African Animal World
ContinentFactory& africa = *(dynamic_cast<ContinentFactory *>(new AfricaFactory()));
AnimalWorld& world1 = *(new AnimalWorld(africa));
world1.RunFoodChain();

// Create and run the American animal world
ContinentFactory& america = *(dynamic_cast<ContinentFactory *>(new AmericaFactory()));
AnimalWorld& world2 = *(new AnimalWorld(america));
world2.RunFoodChain();

return
0;
}





The output is as follows:



For more details please see: http://www.dofactory.com/Patterns/PatternAbstract.aspx

Java Servlet : HTML with Servlet [ part 2]

http://www.youtube.com/watch?v=EUtDqq1kTDcendofvid [starttext]
Servlet + html
get request from tag input
[endtext]

Java Servlet : HTML with Servlet [ part 1]

http://www.youtube.com/watch?v=d1etDYzuxDkendofvid [starttext]
Servlet + html get request from tag input
[endtext]

Application J2EE : Servlet Tomcat+Eclipse JEE [PART 2] By [ TariQ ESTM ]

http://www.youtube.com/watch?v=b3DpgVokbcAendofvid [starttext]
eclipse tomcat servlet
[endtext]

Application J2EE : Servlet Tomcat+Eclipse JEE By [ TariQ ESTM ]

http://www.youtube.com/watch?v=qYTH5Uehc4Yendofvid [starttext]
Configuration du tomcat dans Eclipse JEE et Exécution d'une Simple Servlet
[endtext]

J2EE - Eclipse Tomcat Configuration

http://www.youtube.com/watch?v=R4zkTU_gvb4endofvid [starttext]
[endtext]

[Part1] | How to Create a Java Server Faces (JSF) Development Environment + Apache Tomcat + Suns JDK

http://www.youtube.com/watch?v=KmvRUnNRytoendofvid [starttext]

This is part one of a three part Java Server Faces CBT Tutorial that demonstrates how to configure your Windows XP environment in order to do some JSF development.

The idea is that first you need to install the JDK, configure the JAVA_HOME environment variable, and then install the Tomcat Servlet & JSP engine. With the JAVA_HOME set, and the bin directory of the Tomcat6 server located, it's just a matter of running the startup.bat file and your tomcat server can be found at http://localhost:8080

After installing and configuration Tomcat, further tutorials demonstrate how to obtain the JSF JAR files from the mojarra project (jsf-api.jar & jsf-api.jar). We even recommend finding the jstl.jar and standard.jar files from the examples in the Tomcat installation.

Subsequent tutorials demonstrate how to create a simple J2EE/JEE5 war file with the appropriate war file structure, how to create a web.xml deployment descriptor, a faces-config.xml file, and finall, how to jar the whole darn thing up and deploy it to the Servlet Engine.

This tutorial uses Apache Tomcat, but the instructions will work with any J2EE/JEE5 compliant application server, including WebSphere, WebLogic, Tomcat, Oracle, etc.
[endtext]

JEE Introduction

http://www.youtube.com/watch?v=0q-HC3PDX5sendofvid [starttext]
Introduction to Java Enterprise Edition Software.

Allowing others to get a grip on this vast technology from start to finish.
[endtext]

C++ Design Patterns


Over the next few months we will be looking at Design Pattern examples using C++. Here is a good starting point from which the information in this post has been extracted.

Q: What is a Design Pattern?
A: Design Patterns represent solutions to problems what arise when developing software within a particular context.
Quote:
Each pattern describes a problem which occurs over and over again in our environment, and then describes the core of the solution to that problem, in such a way that you can use this solution a million times over, without ever doing it the same way twice.C. Alexander, The Timeless Way of Building, 1979
Quote:
Patterns help you learn from other's successes, instead of your own
failures.Mark Johnson (cited by Bruce Eckel)

Q: How many types of design patterns exist?
A: Basically, there are three categories:

Creational Patterns: deal with initializing and configuring classes and objects
Structural Patterns: deal with decoupling the interface and implementation of classes and objects
Behavioral Patterns: deal with dynamic interactions among societies of classes and objects


Q: What are good books about design patterns.
A: Here are some must-have books:
Design Patterns by Erich Gamma, Richard Helm, Ralph Johnson, John Vlissides (also known as Gang of Four)
Thinking in Patterns with Java, by Bruce Eckel
Thinking in Patterns with C++, by Bruce Eckel


Q: How can I quickly find information about a design pattern?
A: Here are some links on the web:


Creational Patterns

Abstract Factory: Creates an instance of several families of classes
resource 1
resource 2

Builder: Separates object construction from its representation
resource 1
resource 2

Factory Method: Creates an instance of several derived classes
resource 1
resource 2
resource 3

Prototype: A fully initialized instance to be copied or cloned
resource 1
resource 2

Singleton: A class of which only a single instance can exist
resource 1
resource 2

Structural Patterns

Adapter: Match interfaces of different classes
resource 1
resource 2
resource 1

Bridge: Separates an object’s interface from its implementation
resource 1
resource 2

Composite: A tree structure of simple and composite objects
resource 1
resource 2
resource 3

Decorator: Add responsibilities to objects dynamically
resource 1
resource 2
resource 3

Façade: A single class that represents an entire subsystem
resource 1
resource 2

Flyweight: A fine-grained instance used for efficient sharing
resource 1
resource 2
resource 3

Proxy: An object representing another object
resource 1
resource 2

Behavioral Patterns

Chain of Responsibility: A way of passing a request between a chain of objects
resource 1
resource 2

Command: Encapsulate a command request as an object
resource 1
resource 2
resource 3

Interpreter: A way to include language elements in a program
resource 1
resource 2

Iterator: Sequentially access the elements of a collection
resource 1
resource 2

Mediator: Defines simplified communication between classes
resource 1
resource 2

Memento: Capture and restore an object's internal state
resource 1

Observer: A way of notifying change to a number of classes
resource 1
resource 2
resource 3

State: Alter an object's behavior when its state changes
resource 1
resource 2
resource 3

Strategy: Encapsulates an algorithm inside a class
resource 1
resource 2
resource 3

Template Method: Defer the exact steps of an algorithm to a subclass
resource 1
resource 2
resource 3

Visitor: Defines a new operation to a class without change
resource 1
resource 2
resource 3


Source: Code Guru

Graph Processing in Map Reduce

In my previous post about Google's Pregel model, a general pattern of parallel graph processing can be expressed as multiple iterations of processing until a termination condition is reached. Within each iteration, same processing happens at a set of nodes (ie: context nodes).

Each context node perform a sequence of steps independently (hence achieving parallelism)
  1. Aggregate all incoming messages received from its direct inward arcs during the last iteration
  2. With this aggregated message, perform some local computation (ie: the node and its direct outward arcs' local state)
  3. Pass the result of local computation along all outward arcs to its direct neighbors
This processing pattern can be implemented using Map/Reduce model, using a MR job for each iteration. The sequence is a little different from above. Typically a mapper will perform (2) and (3) where it emits the message using its neighbor's node id as key. Reducer will be responsible to perform (1).

Issue of using Map/Reduce

However, due to the functional programming nature of Map() and Reduce(), M/R does not automatically retain "state" between jobs. To retain the graph across iterations, the mapper need to explicitly pass along the corresponding portion of the graph to the reducer, in additional to the messages itself. Similarly, the reducer need to handle a different type of data passed along.

map(id, node) {
emit(id, node)
partial_result = local_compute()
for each neighbor in node.outE.inV {
emit(neighbor.id, partial_result)
}
}

reduce(id, list_of_msg) {
node = null
result = 0

for each msg in list_of_msg {
if type_of(msg) == Node
node = msg
else
result = aggregate(result, msg)
end
}

node.value = result
emit(id, node)
}

This downside of this approach is a substantial amount of I/O processing and bandwidth is consumed to just passing the graph itself around.

Google's Pregel model provides an alternative message distribution model so that state can be retained at the processing node across iterations.

The Schimmy Trick

In a recent research paper, Jimmy Lin and Michael Schatz use a clever partition() algorithm in Map /Reduce which can achieve "stickiness" of graph distribution as well as maintaining a sorted-order of node id on disk.

The whole graph is broken down into multiple files and stored in HDFS. Each file contains multiple records and each record describe a node and its corresponding adjacency list.

id -> [nodeProps, [[arcProps, toNodeId], [arcProps, toNodeId] ...]

In addition, the records are physically sorted within the file by their node id.

There will be as many reducers as the number of above files and so each Reducer task is assigned with one of this file. On the other hand, the partition() function assign all nodes within the file to land on its associated reducer.

Mapper does the same thing before, except the first line in the method is removed as it no longer need to emit the graph.

Reducer will receive all the message emitted from the mapper, which is sorted by the Map/Reduce framework by the key (which happens to be the node id). On the other hand, the reducer can open the corresponding file in HDFS, which also maintain a sorted list of nodes based on their ids. The reducer can just read the HDFS file sequentially on each reduce() call and confident that all preceding nodes in the file has already received their corresponding messages.

reduce(id, list_of_msg) {
nodeInFile = readFromFile()

# Emit preceding nodes that receives no message
while(nodeInFile.id < id)
emit(nodeInFile.id, nodeInFile)
end

result = 0

for each msg in list_of_msg {
result = aggregate(result, msg)
}

nodeInFile.value = result
emit(id, nodeInFile)
}

Although the Schimmy trick provides an improvement over the classical way of map/reduce, it only eliminates the communication between the mapper and the reducer. At each iteration, the mapper still needs to read the whole graph from HDFS to the mapper node and the reducer still need to write the whole graph back to HDFS, which maintains a 3-way replication for each file.

Hadoop provides some co-location mechanism for the mapper and try to assign files that is sitting at the same machine to the mapper. However, this co-location mechanism is not available for the reducer and so reducer still need to write the graph back over the network.

Pregel Advantage

Since Pregel model retain worker state (the same worker is responsible for the same set of nodes) across iteration, the graph can be loaded in memory once and reuse across iterations. This will reduce I/O overhead as there is no need to read and write to disk at each iteration. For fault resilience, there will be a periodic check point where every worker write their in-memory state to disk.

Also, Pregel (with its stateful characteristic), only send local computed result (but not the graph structure) over the network, which implies the minimal bandwidth consumption.

Of course, Pregel is very new and relative immature as compared to Map/Reduce.

Client/Server communication via sockets

The following is a simple Client Server example that actually covers quite a few different topics. The code is modified from the MadWizard.org Winsock Tutorial. It may be a good idea to go through the StringStreams example here and C/C++ String differences example here.

Please note that the code below is not the best example of coding practice.

Server code:



//Original Client-Server code from www.MadWizard.org
//Part of the Winsock networking tutorial by Thomas Bleeker
//Modified and tested on Microsoft Visual Studio 2008 - Zahid Ghadialy

#include <iostream>
#include <string>
#include <sstream>

#define WIN32_MEAN_AND_LEAN
#include <winsock2.h>
#include <windows.h>

//Add ws2_32.lib in Properties->Linker->Input->Additional Dependencies

using namespace
std;

const
int REQ_WINSOCK_VER = 2; // Minimum winsock version required
const int DEFAULT_PORT = 4444;
const
int TEMP_BUFFER_SIZE = 128;

//Forward Declarations
bool RunServer(int portNumber);

//MAIN
int main()
{

int
iRet = 1;
WSADATA wsaData;

cout << "SERVER STARTED" << endl;
cout << "Initializing winsock... ";

if
(WSAStartup(MAKEWORD(REQ_WINSOCK_VER,0), &wsaData)==0)
{

// Check if major version is at least REQ_WINSOCK_VER
if (LOBYTE(wsaData.wVersion) >= REQ_WINSOCK_VER)
{

cout << "initialized.\n";

int
port = DEFAULT_PORT;
iRet = !RunServer(port);
}

else

{

cerr << "required version not supported!";
}


cout << "Cleaning up winsock... ";

// Cleanup winsock
if (WSACleanup()!=0)
{

cerr << "cleanup failed!\n";
iRet = 1;
}

cout << "done.\n";
}

else

{

cerr << "startup failed!\n";
}

return
iRet;
}



string GetHostDescription(const sockaddr_in &sockAddr)
{

ostringstream stream;
stream << inet_ntoa(sockAddr.sin_addr) << ":" << ntohs(sockAddr.sin_port);
return
stream.str();
}


void
SetServerSockAddr(sockaddr_in *pSockAddr, int portNumber)
{

// Set family, port and find IP
pSockAddr->sin_family = AF_INET;
pSockAddr->sin_port = htons(portNumber);
pSockAddr->sin_addr.S_un.S_addr = INADDR_ANY;
}


void
HandleConnection(SOCKET hClientSocket, const sockaddr_in &sockAddr)
{

// Print description (IP:port) of connected client
cout << "Connected with " << GetHostDescription(sockAddr) << ".\n";
exception e;

char
tempBuffer[TEMP_BUFFER_SIZE];

// Read data
while(true)
{

int
retval;
retval = recv(hClientSocket, tempBuffer, sizeof(tempBuffer), 0);
if
(retval==0)
{

break
; // Connection has been closed
}
else if
(retval==SOCKET_ERROR)
{

exception e("socket error while receiving.");
throw
e;
}

else

{

string tempBufferString(tempBuffer);
cout<<"Received over the socket :"<<tempBufferString<<endl;
string tempString = "Loopbacked: " + tempBufferString + '\0';
strcpy_s(tempBuffer, tempString.length() + 1, tempString.c_str());
if
(send(hClientSocket, tempBuffer, strlen(tempBuffer)+1, 0)==SOCKET_ERROR)
{

exception e("socket error while sending.");
throw
e;
}
}
}

cout << "Connection closed.\n";
}


bool
RunServer(int portNumber)
{

SOCKET hSocket = INVALID_SOCKET, hClientSocket = INVALID_SOCKET;
bool
bSuccess = true;
sockaddr_in sockAddr = {0};

try

{

// Create socket
cout << "Creating socket... ";
if
((hSocket = socket(AF_INET, SOCK_STREAM, IPPROTO_TCP)) == INVALID_SOCKET)
{

cout << "failed Creating socket... \n";
return
false;
}

cout << "created.\n";

// Bind socket
cout << "Binding socket... ";
SetServerSockAddr(&sockAddr, portNumber);
if
(bind(hSocket, reinterpret_cast<sockaddr*>(&sockAddr), sizeof(sockAddr))!=0)
{

cout << "failed Binding socket... \n";
return
false;
}

cout << "bound.\n";

// Put socket in listening mode
cout << "Putting socket in listening mode... ";
if
(listen(hSocket, SOMAXCONN)!=0)
{

cout << "failed Putting socket in listening mode... \n";
return
false;
}

cout << "done.\n";

// Wait for connection
cout << "Waiting for incoming connection... ";

sockaddr_in clientSockAddr;
int
clientSockSize = sizeof(clientSockAddr);

// Accept connection:
hClientSocket = accept(hSocket,
reinterpret_cast
<sockaddr*>(&clientSockAddr),
&
clientSockSize);

// Check if accept succeeded
if (hClientSocket==INVALID_SOCKET)
{

cout << "accept function failed... \n";
return
false;
}

cout << "accepted.\n";

// Wait for and accept a connection:
HandleConnection(hClientSocket, clientSockAddr);

}

catch
(exception& e)
{

cerr << "\nError: " << e.what() << endl;
bSuccess = false;
}


if
(hSocket!=INVALID_SOCKET)
closesocket(hSocket);

if
(hClientSocket!=INVALID_SOCKET)
closesocket(hClientSocket);

return
bSuccess;
}




Client code:




//Original Client-Server code from www.MadWizard.org
//Part of the Winsock networking tutorial by Thomas Bleeker
//Modified and tested on Microsoft Visual Studio 2008 - Zahid Ghadialy

#include <iostream>
#include <sstream>

#define WIN32_MEAN_AND_LEAN
#include <winsock2.h>
#include <windows.h>

using namespace
std;

//Add ws2_32.lib in Properties->Linker->Input->Additional Dependencies

using namespace
std;

const
int REQ_WINSOCK_VER = 2; // Minimum winsock version required
const char DEF_SERVER_NAME[] = "127.0.0.1"; //localhost - can be your server name like "www.google.com"
const int SERVER_PORT = 4444;
const
int TEMP_BUFFER_SIZE = 128;

// IP number typedef for IPv4
typedef unsigned long IPNumber;

//Forward Declarations
bool RunClient(const char *pServername);

//MAIN
int main(int argc, char* argv[])
{

int
iRet = 1;
WSADATA wsaData;

cout << "CLIENT STARTED" << endl;
cout << "Initializing winsock... ";

if
(WSAStartup(MAKEWORD(REQ_WINSOCK_VER,0), &wsaData)==0)
{

// Check if major version is at least REQ_WINSOCK_VER
if (LOBYTE(wsaData.wVersion) >= REQ_WINSOCK_VER)
{

cout << "initialized.\n";

// Set default hostname:
const char *pHostname = DEF_SERVER_NAME;
iRet = !RunClient(pHostname);
}

else

{

cerr << "required version not supported!";
}


cout << "Cleaning up winsock... ";

// Cleanup winsock
if (WSACleanup()!=0)
{

cerr << "cleanup failed!\n";
iRet = 1;
}

cout << "done.\n";
}

else

{

cerr << "startup failed!\n";
}

return
iRet;
}



IPNumber FindHostIP(const char *pServerName)
{

HOSTENT *pHostent;

// Get hostent structure for hostname:
if (!(pHostent = gethostbyname(pServerName)))
{

exception e("could not resolve hostname.");
throw
e;
}


// Extract primary IP address from hostent structure:
if (pHostent->h_addr_list && pHostent->h_addr_list[0])
return
*reinterpret_cast<IPNumber*>(pHostent->h_addr_list[0]);

return
0;
}


void
FillSockAddr(sockaddr_in *pSockAddr, const char *pServerName, int portNumber)
{

// Set family, port and find IP
pSockAddr->sin_family = AF_INET;
pSockAddr->sin_port = htons(portNumber);
pSockAddr->sin_addr.S_un.S_addr = FindHostIP(pServerName);
}


bool
RunClient(const char *pServername)
{

SOCKET hSocket = INVALID_SOCKET;
char
tempBuffer[TEMP_BUFFER_SIZE];
sockaddr_in sockAddr = {0};
bool
bSuccess = true;

try

{

// Lookup hostname and fill sockaddr_in structure:
cout << "Looking up hostname " << pServername << "... ";
FillSockAddr(&sockAddr, pServername, SERVER_PORT);
cout << "found.\n";

// Create socket
cout << "Creating socket... ";
if
((hSocket = socket(AF_INET, SOCK_STREAM, IPPROTO_TCP)) == INVALID_SOCKET)
{

cout<<"could not create socket. "<<endl;
return
false;
}

cout << "created.\n";

// Connect to server
cout << "Attempting to connect to " << inet_ntoa(sockAddr.sin_addr)
<<
":" << SERVER_PORT << "... ";
if
(connect(hSocket, reinterpret_cast<sockaddr*>(&sockAddr), sizeof(sockAddr))!=0)
{

cout<<"could not connect. "<<endl;
return
false;
}

cout << "connected.\n";

cout << "Sending requests and checking for loopbacks... "<<endl;

//Lets sent 100 packets and get it looped back from Server
for(int i = 0; i < 10; i++)
{

int
retval = 0;
stringstream ss (stringstream::in | stringstream::out);
ss << "Message " << i <<"\n";

std::string s = ss.str() + '\0'; //Adding the null charachter
if (send(hSocket, s.c_str(), s.size() + 1, 0)==SOCKET_ERROR)
{

cout<<"failed to send data. "<<endl;
return
false;
}


retval = recv(hSocket, tempBuffer, sizeof(tempBuffer), 0);
if
(retval==0)
{

cout<<"Connection closed"<<endl;
break
;
}

else if
(retval==SOCKET_ERROR)
{

exception e("socket error while receiving.");
throw
e;
}

else

{

// retval is number of bytes read
// Terminate buffer with zero and print as string
tempBuffer[retval] = 0;
cout << "Received " << retval << " bytes. Received : " <<tempBuffer;
}
}
}

catch
(exception& e)
{

cerr << "\nError: " << e.what() << endl;
bSuccess = false;
}


if
(hSocket!=INVALID_SOCKET)
{

closesocket(hSocket);
}

return
bSuccess;
}





The Server Output is as follows:


The Client output is as follows:

Google Pregel Graph Processing

A lot of real life problems can be expressed in terms of entities related to each other and best captured using graphical models. Well defined graph theory can be applied to processing the graph and return interesting results. The general processing patterns can be categorized into the following ...
  1. Capture (e.g. When John is connected to Peter in a social network, a link is created between two Person nodes)
  2. Query (e.g. Find out all of John's friends of friends whose age is less than 30 and is married)
  3. Mining (e.g. Find out the most influential person in Silicon Valley)

Distributed and Parallel Graph Processing

Although using a Graph to represent a relationship network is not new, the size of network has been dramatically increase in the past decade such that storing the whole graph in one place is impossible. Therefore, the graph need to be broken down into multiple partitions and stored in different places. Traditional graph algorithm that assume the whole graph can be resided in memory becomes invalid. We need to redesign the algorithm such that it can work in a distributed environment. On the other hand, by breaking the graph into different partitions, we can manipulate the graph in parallel to speed up the processing.

Property Graph Model

The paper “Constructions from Dots and Lines” by Marko A. Rodriguez and Peter Neubauer illustrate the idea very well. Basically, a graph contains nodes and arcs.

A node has a "type" which defines a set of properties (name/value pairs) that the node can be associated with.

An arc defines a directed relationship between nodes, and hence contains the fromNode, toNode as well as a set of properties defined by the "type" of the arc.



General Parallel Graph Processing

Most of the graph processing algorithm can be expressed in terms of a combination of "traversal" and "transformation".

Parallel Graph Traversal

In the case of "traversal", it can be expressed as a path which contains a sequence of segments. Each segment contains a traversal from a node to an arc, followed by a traversal from an arc to a node. In Marko and Peter's model, a Node (Vertex) contains a collection of "inE" and another collection of "outE". On the other hand, an Arc (Edge) contains one "inV", one "outV". So to expressed a "Friend-of-a-friend" relationship over a social network, we can use the following

./outE[@type='friend']/inV/outE[@type='friend']/inV

Loops can also be expressed in the path, to expressed all persons that is reachable from this person, we can use the following

.(/outE[@type='friend']/inV)*[@cycle='infinite']

On the implementation side, a traversal can be processed in the following way
  1. Start with a set of "context nodes", which can be defined by a list of node ids, or a search criteria (in this case, the search result determines the starting context nodes)
  2. Repeat until all segments in the path are exhausted. Perform a walk from all context nodes in parallel. Evaluate all outward arcs (ie: outE) with conditions (ie: @type='friend'). The nodes that this arc points to (ie: inV) will become the context node of next round
  3. Return the final context nodes
Such traversal path can also be used to expressed inference (or derived) relationships, which doesn't have a physical arc stored in the graph model.

Parallel Graph Transformation

The main goal of Graph transformation is to modify the graph. This include modifying the properties of existing nodes and arcs, creating new arcs / nodes and removing existing arcs / nodes. The modification logic is provided by a user-defined function, which will be applied to all active nodes.

The Graph transformation process can be implemented in the following steps
  1. Start with a set of "active nodes", which can be defined by a lost of node ids, or a search criteria (in this case, the search result determines the starting context nodes)
  2. Repeat until there is no more active nodes. Execute the user-defined transformation which modifies the properties of the context nodes and outward arcs. It can also remove outwards arcs or create new arcs that point to existing or new nodes (in other words, the graph connectivity can be modified). It can also send message to other nodes (the message will be picked up in the next round) as well as receive message sent from other nodes in the previous round.
  3. Return the transformed graph, or a traversal can be performed to return a subset of the transformed graph.
Google's Pregel

Pregel can be thought as a generalized parallel graph transformation framework. In this model, the most basic (atomic) unit is a "node" that contains its properties, outward arcs (and its properties) as well as the node id (just the id) that the outward arc points to. The node also has a logical inbox to receive all messages sent to it.


The whole graph is broken down into multiple "partitions", each contains a large number of nodes. Partition is a unit of execution and typically has an execution thread associated with it. A "worker" machine can host multiple "partitions".


The execution model is based on BSP (Bulk Synchronous Processing) model. In this model, there are multiple processing units proceeding in parallel in a sequence of "supersteps". Within each "superstep", each processing units first receive all messages delivered to them from the preceding "superstep", and then manipulate their local data and may queue up the message that it intends to send to other processing units. This happens asynchronously and simultaneously among all processing units. The queued up message will be delivered to the destined processing units but won't be seen until the next "superstep". When all the processing unit finishes the message delivery (hence the synchronization point), the next superstep can be started, and the cycle repeats until the termination condition has been reached.

Notice that depends on the graph algorithms, the assignment of nodes to a partition may have an overall performance impact. Pregel provides a default assignment where partition = nodeId % N but user can overwrite this assignment algorithm if they want. In general, it is a good idea to put close-neighbor nodes into the same partition so that message between these nodes doesn't need to flow into the network and hence reduce communication overhead. Of course, this also means traversing the neighboring nodes all happen within the same machine and hinder parallelism. This usually is not a problem when the context nodes are very diverse. In my experience of parallel graph processing, coarse-grain parallelism is preferred over fine-grain parallelism as it reduces communication overhead.

The complete picture of execution can be implemented as follows:


The basic processing unit is a "thread" associated with each partition, running inside a worker. Each worker receive messages from previous "superstep" from its "inQ" and dispatch the message to the corresponding partition that the destination node is residing. After that, a user defined "compute()" function is invoked on each node of the partition. Notice that there is a single thread per partition so nodes within a partition are executed sequentially and the order of execution is undeterministic.

The "master" is playing a central role to coordinate the execute of supersteps in sequence. It signals the beginning of a new superstep to all workers after knowing all of them has completed the previous one. It also pings each worker to know their processing status and periodically issue "checkpoint" command to all workers who will then save its partition to a persistent graph store. Pregel doesn't define or mandate the graph storage model so any persistent mechanism should work well. There is a "load" phase at the beginning where each partition starts empty and read a slice of the graph storage. For each node read from the storage, a "partition()" function will be invoked and load the node in the current partition if the function returns the same node, otherwise the node is queue to another partition who the node is assigned to.

Fault resilience is achieved by having the checkpoint mechanism where each worker is instructed to save its in-memory graph partition to the graph storage periodically (at the beginning of a superstep). If the worker is detected to be dead (not responding to the "ping" message from the master), the master will instruct the surviving workers to take up the partitions of the failed worker. The whole processing will be reverted back to the previous checkpoint and proceed again from there (even the healthy worker need to redo the previous processing). The Pregel paper mention a potential optimization to just re-execute the processing of the failed partitions from the previous checkpoint by replaying the previous received message, of course this requires keeping a log of all received messages between nodes at every super steps since previous checkpoint. This optimization, however, rely on the algorithm to be deterministic (in other words, same input execute at a later time will achieve the same output).

Further optimization is available in Pregel to reduce the network bandwidth usage. Messages destined to the same node can be combined using a user-defined "combine()" function, which is required to be associative and commutative. This is similar to the same combine() method in Google Map/Reduce model.

In addition, each node can also emit an "aggregate value" at the end of "compute()". Worker will invoke an user-defined "aggregate()" function that aggregate all node's aggregate value into a partition level aggregate value and all the way to the master. The final aggregated value will be made available to all nodes in the next superstep. Just aggregate value can be used to calculate summary statistic of each node as well as coordinating the progress of each processing units.

I think the Pregel model is general enough for a large portion of classical graph algorithm. I'll cover how we map these traditional algorithms in Pregel in subsequent postings.

Reference

http://www.slideshare.net/slidarko/graph-windycitydb2010

How to Extend existing enums

Picked up this very interesting example on extending enum's. The program is self explanatory and is as follows:



//Program tested on Microsoft Visual Studio 2008 - Zahid Ghadialy
#include<iostream>

using namespace
std;

int
main()
{

enum
Enum1
{

value1,
value2,
value3,
final_value = value3
};


//Print out the enum values
cout<<"Enum1 values : ";
for
(int i = 0; i <= final_value; i++)
cout<<Enum1(i)<<" ";
cout<<endl;

enum
extendedEnum1
{

value4 = final_value + 1,
value5,
value6,
new_final_value = value6
};


//Print out the enum values
cout<<"extendedEnum1 values : ";
for
(int i = 0; i <= new_final_value; i++)
cout<<extendedEnum1(i)<<" ";
cout<<endl;

return
0;
}



The output is as follows:


Check out this stream