Graph Ready:
For a layman graphs are visual representation of representing relationship between the related quantities.We can summarise graph as it represent how one quantity changes effect the other quantity.
In mathematics we learn to draw graph in two dimensional space X-axis and Y-axis.
In following example we can see graph represent the number of student register for the summer camp in various streams. X-axis represent the streams and y-axis represent the number of sign ups.
For example in graph we can easily identify for drama 3 student has been register. So graph represent the data visually and it can be understand quickly.
In Programming World graphs are used to represent the relationship between the similar objects. A graph is made of vertices(objects) and edges or lines connected to objects represent the relationship between the object. So graph is an ordered pair G = (V, E) comprising a set of vertices with a set of E edges.
In above example graphs are ordered pair of G=(Cities, Distance).It represent the distance (relationship) between the cities (Objects). Above graph is an example of undirected graph. Let learn various graph terms before the detail of implementation.
Graph Terms:
1) Vertex : Objects are represent by vertex in a graph. Vertex is represented by circle by label. In above graph all the cities are vertex.
2) Edge: Relationship or connection between the objects are represented by edges. In above example lines with KM are Edges. Edges can be directed or undirected. Above graph has all the undirected edges.
3) Degree of Vertex: Number of edges touches to the vertex are degree of vertex. For example Delhi has 2 degree in above graph.
4) Undirected Graph: If all the edges in a graph is bidirectional than graph is undirected graph. Above graph is Undirected graph.
5) Directed Graph: A graph in which edges are one direction. So edges graph can be use to represent the data flow. If we represent the web links in web site as a graph then it will be directed graph.
6) Connected Graph: A graph is connected graph if there is path between any two pints in graph.
7) Disconnected Graph: A graph is disconnected if there has certain nodes, which are different from the existing graph.
Graph Steady:
This section explain about how we can implement graph using various programming language. We will discuss about the two commonly used representation of graph:
1) Adjacency Matrix (2-D Array)
2) Adjacency List (Array of Link List)
Let dig into detail of this implementation. Suppose you just reached office and you met your colleagues. So Following is the graph which represent the relationship whether you met the particular person on that day or not. Obviously everybody must see his/her manager every day :( . Not a sad thing some manager are really good ;). Let come to point so following picture represent the graph which represent the relationship (seen/ Not Seen) to the objects(You and your colleagues.)
This graph is an ordered pair G (Person, Met/ Not).
We can come to following conclusion from the graph:
1) You met with Manager and Team Member 1
2) Manager met to everyone.
3) Team Member 1 met to you and manager.
4) Team Member 2 met to manager.
Adjacency Matrix (2-D Array):
In adjacency matrix we represent graph as 2-D array. A graph with n vertices will be represented by n*n matrix. If we need to check whether there is an edge exist between the vertices we can simply access it a[i][j].
Where a represent the base address of 2-D array and i and j represent the vertex 1 and vertex 2.
It can be represent in mathematical form:
graphij = {1 if Vi -> Vj
For weighted graph in place of one we have Wij.
Following is the pictorial representation of above graph as 2-D array:
We can access the relationship between the objects in following manner:
1) You and manager met ?
graph[0][1]
2) Team Member(1) and Team member(2) met ?
graph[2][3]
So look up is very easy in the above representation. We have some cons for this approach:
Pros:
1) Look up is very fast in this approach. it takes constant running time O(1). As we seen in above query we can easily check whether a edge exist or not.
2) Insertion, Delation and Updating is also constant time process O(1). We directly need to update the value in array location by accessing index.
Cons:
1) Space is problem in this approach. It always take O(N*N) memory. Let suppose you have a graph with 10 vertices and 5 edges. You need 10*10*4(sizeof int) space only for storing 5*4(SizeofInt) bytes data. This approach is not suggested for sparse graph.
Adjacency List[] si an array which contain reference for the link list related to all the vertices. So in this representation we are stop ring based on the edges in graph. It takes less space and always recommended for sparse graph. Let first discuss pros and cons of the approach then we will dig into implementation of graph.
Pros:
1) It takes less space to represent the graph in comparison of adjacency matrix. Space complexity of with this approach is O(|V| + |E|) .
2) Insertion an edge is also take constant time O(1) in link list. Simply add after head.
Cons:
1) Look Up of edges in this approach is more complex and takes O(degree of vertex) time. We need to look for the each element in the link list.
2) Deletion and updating is also takes O(degree of vertex) time. We need to look for the element then it take constant time.
So we have two enums in the graph API first use for define the constants for storage type and second for define the graph type.
Where a represent the base address of 2-D array and i and j represent the vertex 1 and vertex 2.
It can be represent in mathematical form:
graphij = {1 if Vi -> Vj
0 otherwise}
For weighted graph in place of one we have Wij.
Following is the pictorial representation of above graph as 2-D array:
1) You and manager met ?
graph[0][1]
2) Team Member(1) and Team member(2) met ?
graph[2][3]
So look up is very easy in the above representation. We have some cons for this approach:
Pros:
1) Look up is very fast in this approach. it takes constant running time O(1). As we seen in above query we can easily check whether a edge exist or not.
2) Insertion, Delation and Updating is also constant time process O(1). We directly need to update the value in array location by accessing index.
Cons:
1) Space is problem in this approach. It always take O(N*N) memory. Let suppose you have a graph with 10 vertices and 5 edges. You need 10*10*4(sizeof int) space only for storing 5*4(SizeofInt) bytes data. This approach is not suggested for sparse graph.
Adjacency List (Array of Link List):
In this representation an array of link list is used and size of array is equal to the vertices of the graph.
Let suppose you have declared an array graph[verticesCount]. Each element in the array will point to head of the link list. For example if you need to check for "manager"
graph["manager"] or graph[1] will point to link list and link list has all the vertex to which the manager is connected.
So in our case following will be link list:
You -> Team Member(1) -> Team Member(2).
Following is the visual representation of adjacency list of the above graph:
Pros:
1) It takes less space to represent the graph in comparison of adjacency matrix. Space complexity of with this approach is O(|V| + |E|) .
2) Insertion an edge is also take constant time O(1) in link list. Simply add after head.
Cons:
1) Look Up of edges in this approach is more complex and takes O(degree of vertex) time. We need to look for the each element in the link list.
2) Deletion and updating is also takes O(degree of vertex) time. We need to look for the element then it take constant time.
Graph Go:
In this section we will discuss the implementation of graph using c language. We will use a single code base or method to implement the both the representation.
Let go one by one all the Variables used in graph:
Let go one by one all the Variables used in graph:
Enum:
/*
*It conatains constants for the storage type used for graph (2-D Array or link list)
*/
typedef enum {
graph_storage_adjacency_matrix,
graph_storage_adjacency_list
}graph_storage_type_e;
/*
*It conatains constants various graph type Directed or Undirected
*/
typedef enum {
graph_type_Directed,
graph_type_Undirected
}graph_type;
So we have two enums in the graph API first use for define the constants for storage type and second for define the graph type.
Struct (Public):
/*
*It represent the graph and the newly created garph will be refrence of this struct.
*/
struct graph_struct{
graph_vertex_count vertexCount;
graph_internal *graph_data;
};
typedef struct graph_struct SNGraph;
/*
*It represent the vertex of graph and the newly created vertex will be refrence of this struct.
*/
struct graph_vertex_struct{
char* vertexName;
};
typedef struct graph_vertex_struct SNGraphVertex;
/*
*It represent the edge of graph and the newly created edge will be refrence of this struct.
*/
struct graph_vertex_edge{
int weight;
};
typedef struct graph_vertex_edge SNGraphEdge;
/*
*It contains the graph properties and to create a new graph this property need to specify.
*/
typedef struct graph_properties_struct{
graph_type graphType;
graph_storage_type_e storageType;
}graph_properties;
Struct (Private):
/*
*It contains the graph internal member.
*/
struct graph_internal_struct{
graph_storage_type_e storageType; //Storage type for graph
graph_type type; //Type of graph
graph_vertex_count currentCount; //Current Count of vertices added in graph
void **vertices; //Array contains all the vertices of graph
void **graph; //refrence for all the edges of graph and structure depend
upon the storage type
};
typedef struct graph_internal_struct graph_internal;
/*
*It contains the adjacency matrix member.
*/
typedef struct adjacency_matrix{
int **graph_matrix; //2-D array for adjacency Matrix
}graph_matrix;
/*
*This structure represent the link list for adjacency list.
*/
struct graph_adjacency_list_struct{
SNGraphVertex *toVertex; //refrence for the vertex
void* data; //any Data related to relationship like for weighted graph
weight
adjacency_list *next_vertex; //Pointer to next vertex
};
typedef struct graph_adjacency_list_struct adjacency_list;
/*
*This structure represent the head of adjacency list.
*/
struct graph_adjacency_head_struct{
int degreeOfvertex; // It will have degree of vertex
adjacency_list *headVertex; // It contain refrence for head for all the vertices
};
typedef struct graph_adjacency_head_struct adjacency_head;
Private and public here are only visibility shown. The private struct added in Graph.C file and public in Graph.h
Function (Public):
/*
* Function: newGraph
* ----------------------------
* allocate a new graph and return the refernce for it
*
* properties: contain the properties for the graph
* count: the number of vertices in graph
*
* returns: the refernce for the graph
*/
SNGraph* newGraph(graph_properties *properties, graph_vertex_count count);
/*
* Function: addVertex
* ----------------------------
* add a vertex in a graph
*
* graph: the refrence for the graph in which vertex has to be add
* name: the name of vertex
*
* returns: the refernce of the added vertex
*/
SNGraphVertex* addVertex(SNGraph *graph, const char* name);
/*
* Function: addEdge
* ----------------------------
* add a edge in a graph between the vertex
*
* graph: the refrence for the graph in which edge has to be add
* vertex1: the start vertex of edge
* vertex2: the end vertex of edge
* data : the data related to the edge (Specefic to weighted graph)
*
* returns: the refernce of the added edge
*/
SNGraphEdge* addEdge(SNGraph *graph, SNGraphVertex *vertex1, SNGraphVertex *vertex2, void* data);
/*
* Function: displayGraph
* ----------------------------
* prints all the vertices with its connected neighbour
*
* graph: the refrence for the graph in which vertex has to be add
*
*
* returns:
*/
void displayGraph(SNGraph *graph);
/*
* Function: releaseGraph
* ----------------------------
* release the memory used by graph.
*
* graph: the pointer to refrence for the graph in which vertex has to be add
*
*
* returns:
*/
void releaseGraph(SNGraph **graphPtr);
Let us discuss the implementation in detail:
I have kept all the vertices of graph in SNGraph->graph_internal->vertices.
It is pointer to a void pointer. It is a single dimension array in which element is pointer to a vertex of graph.
For storage of edges information or connection between the vertex i have used the pointer to a void pointer that is :
SNGraph->graph_internal->graph
It store all the edge information but implementation is different based on the storage type of graph.
Following is the implementation:
SNGraph->graph_internal->graph
It store all the edge information but implementation is different based on the storage type of graph.
Following is the implementation:
Adjacency Matrix Implementation:
//Count here is number of vertex
//Count here is number of vertex
int** graph_matrix = calloc(sizeof(int*), count);
for (int i = 0; i < count; i++) {
graph_matrix[i] = calloc(sizeof(int*), count);
}
newGraph->graph_data->graph = (void**)graph_matrix;
Let suppose you want to check all the edges connected by Delhi. First you need to check the index of Delhi in vertices array. In our case it is zero. Then Following array will contain all the edges information for the Delhi:
newGraph->graph_data->graph[0]
You can loop through the degree of Delhi vertex and check for all the edges.
Following is pictorial representation of that:
Adjacency List Implementation:
In case of adjacency list the same graph reference store the heads for the link list of all the vertex.
//Count here is number of vertex
In case of adjacency list the same graph reference store the heads for the link list of all the vertex.
//Count here is number of vertex
newGraph->graph_data->graph = malloc(sizeof(adjacency_head*) * count);
for (int i = 0; i < count; i++) {
newGraph->graph_data->graph[i] = malloc(sizeof(adjacency_head));
adjacency_head* graphHead = (adjacency_head*)newGraph->graph_data->graph[i];
graphHead[i].degreeOfvertex = 0;
graphHead[i].headVertex = NULL;
}
Same case if you want to check for the connected vertex for Kanpur. First check the index in vertices. In our case it 3. So graph[3] will contain head for the link list of Kanpur.
Following is pictorial representation of that:
I have shown for first vertex. Similar link list for all the other vertices are there.
To download the full source code please click the link.
You can mail me for any issue or concern :).
No comments:
Post a Comment