Monday, May 16, 2016

C++ STL Implementaion, Represeantion and Explantion of Weighted, Unweighted, Directed and Undirected Graph

May 16, 2016 , , , , , , , , , , , , , , , , , , ,
Explanation, visualization, c++ implementation code for graph adjacency matrix available in the links below,
  Links:

 Inputting Directed Undirected Weighted Unweighted Graph in C Adjacency Matrix/

 Directed Undirected Weighted Unweighted Graph Representation Adjacency Matrix Cheat Sheet/

Explanation:

Here, the first input for the program is vertex or, node count. Next input is the number of edges, then the input based on weight and direction.
The codes here can be combined into a single code to accept various types of graphs.

Sample Input of a Weighted Undirected Graph:

6
7
0 5 5
0 3 9
1 2 4
1 4 3
1 5 1
2 4 2
3 5 7

Graph for the Sample Input:

Complete Visual Representation of the Adjacency List Structure:

Weighted Undirected vector of list implementation:

/**
* Author: Asif Ahmed
* Site: http://quickgrid.blogspot.com
* Description: Inputting and Representing an Weighted Undirected graph
* in adjacency list vector list pair using C++ STL.
*/
#include<bits/stdc++.h>
using namespace std;
// pair<int, int> pairs node name with weight. Basically each of the boxes
// in the visual representation with arrows points out.
typedef pair<int, int> vertex;
// AdjacencyListType is just a name for vector<list <vertex>>
// The outermost vector is initialized to size v here.
// Think of the outermost vector as the leftmost side or, column in the visual representation
// shown in the books. The inner list is linked list containing nodes and weights. The
// inner vector stores pair<int, int> in each of its slot. Where pair<int, int> is used to
// show the adjacent node and the weight between the nodes. Basically each of the boxes.
typedef vector<list <vertex>> AdjacencyListType;
// Take input of undirected weighted graph
// AdjacencyListType &adjList is pass by reference of the adjacency list of type vector<list <vertex>>
// The const keyword is added wherever I know the value does not need to be modified.
void inputAdjacencyList(AdjacencyListType &adjList, int const& edges){
int source, dest, weight;
for(int i = 0; i < edges; ++i){
cin >> source >> dest >> weight;
adjList[source].push_back(make_pair(dest, weight));
adjList[dest].push_back(make_pair(source, weight));
}
}
// If there are no adjacent node "NONE" is printed.
// Now get the node name and the pair by accessing the first and second property.
// Since I have paired node name with weight so, the first is name and next one is the weight
void printCompleteAdjacencyList( AdjacencyListType &adjList, int &v ){
for(int i = 0; i < adjList.size(); ++i){
int adjNodes = adjList[i].size();
printf("Adjacent of: %d", i);
if(adjNodes > 0){
list<vertex>::iterator it = adjList[i].begin();
while(it != adjList[i].end()){
printf(" -> %d (w:%d)", (*it).first, (*it).second);
++it;
}
}else{
printf(" -> NONE");
}
printf("\n");
}
}
// List nodes adjacent or, connected with current node.
// Get the beginning of the list of certain node using adjList[m].begin()
// So traversing the list one by one we can get all adjacent nodes.
void listAdjacentNodes( AdjacencyListType &adjList, int const& m){
printf("%d", m);
list<vertex>::iterator it = adjList[m].begin();
while(it != adjList[m].end()){
printf(" -> %d (w:%d)", (*it).first, (*it).second);
++it;
}
}
int main(){
// Input the vertex or, node count of the graph
printf("Enter number of nodes:\n");
int v;
cin >> v;
// Create the adjacency list structure with size of v.
AdjacencyListType adjList(v);
// Input the edge count of the graph
printf("Enter Edge count:\n");
int edges;
cin >> edges;
// Input the adjacency list
printf("\nEnter source, destination and weight:\n");
inputAdjacencyList(adjList, edges);
// Show the complete adjacency list structure
printf("\nWhole Adjacency List:\n");
printCompleteAdjacencyList(adjList, v);
// Enter a node number to see its adjacent or connected nodes
printf("\nEnter node number to see adjacent nodes:\n");
int m;
scanf("%d", &m);
// If the given node number is greater than the vertexes or, node count do nothing
if(m < v){
listAdjacentNodes(adjList, m);
}
return 0;
}
view raw WeightedUndirectedAdjacencyListGraphVectorListImplementation.cpp hosted with ❤ by GitHub

Sample Input for Unweighted Undirected Graphs:

6
7
0 5
0 3
1 2
1 4
1 5
2 4
3 5

Graph for the Sample Input:

Complete Visual Representation of the Adjacency List Structure:

Unweighted Undirected Graph vector of vector Code:

/**
* Author: Asif Ahmed
* Site: http://quickgrid.blogspot.com
* Description: Inputting and Representing an Unweighted Undirected graph
* in adjacency list using C++ STL.
*/
#include<bits/stdc++.h>
using namespace std;
// This is a modified code based on the directed/undirected weighted graph.
// In order keep things familiar I kept the typedef vertex but, this time
// int since there is no weight to pair with.
typedef int vertex;
// AdjacencyListType is just a name for vector<vector <vertex>>
// The outermost vector is initialized to size v here.
// Think of the outermost vector as the leftmost side or, column in the visual representation
// shown in the books. The inner vector is each for the rows single dimensional array. The
// inner vector stores the destination or adjacent nodes. Basically each of the boxes.
typedef vector<vector <vertex>> AdjacencyListType;
// Take input of directed unweighted graph
// AdjacencyListType &adjList is pass by reference of the adjacency list of type vector<vector <vertex>>
// The const keyword is added wherever I know the value does not need to be modified.
void inputAdjacencyList(AdjacencyListType &adjList, int const& edges){
int source, dest;
for(int i = 0; i < edges; ++i){
cin >> source >> dest;
vertex vet1(dest);
adjList[source].push_back(vet1);
vertex vet2(source);
adjList[dest].push_back(vet2);
}
}
// If there are no adjacent node "NONE" is printed.
// adjList[m].size() gets the connected node count of the current node.
// Then adjList[m][j] gets a specific node which is of pair<int, int> type.
// Now get the node name and the pair by accessing the first and second property.
// Since I have paired node name with weight so, the first is name and next one is the weight
void printCompleteAdjacencyList( AdjacencyListType const& adjList, int &v ){
for(int i = 0; i < v; ++i){
int adjNodes = adjList[i].size();
printf("Adjacent of: %d", i);
if(adjNodes > 0){
for(int j = 0; j < adjNodes; ++j){
printf(" -> %d", adjList[i][j]);
}
}else{
printf(" -> NONE");
}
printf("\n");
}
}
// List nodes adjacent or, connected with current node.
void listAdjacentNodes( AdjacencyListType const& adjList, int const& m){
printf("%d", m);
for(int j = 0; j < adjList[m].size(); ++j){
printf(" -> %d", adjList[m][j]);
}
}
int main(){
// Input the vertex or, node count of the graph
printf("Enter number of nodes:\n");
int v;
cin >> v;
// Create the adjacency list structure with size of v.
AdjacencyListType adjList(v);
// Input the edge count of the graph
printf("Enter Edge count:\n");
int edges;
cin >> edges;
// Input the adjacency list
printf("\nEnter source, destination and weight:\n");
inputAdjacencyList(adjList, edges);
// Show the complete adjacency list structure
printf("\nWhole Adjacency List:\n");
printCompleteAdjacencyList(adjList, v);
// Enter a node number to see its adjacent or connected nodes
printf("\nEnter node number to see adjacent nodes:\n");
int m;
scanf("%d", &m);
// If the given node number is greater than the vertexes or, node count do nothing
if(m < v){
listAdjacentNodes(adjList, m);
}
return 0;
}
view raw UnweightedUndirectedAdjacencyListGraph.cpp hosted with ❤ by GitHub

Sample Input for Unweighted Directed Graphs:

6
7
0 5
0 3
1 2
1 4
1 5
2 4
3 5

Graph for the Sample Input:

Complete Visual Representation of the Adjacency List Structure:

Unweighted Directed Graph vector of vector Code:

/**
* Author: Asif Ahmed
* Site: http://quickgrid.blogspot.com
* Description: Inputting and Representing an Unweighted Directed graph
* in adjacency list using C++ STL.
*/
#include<bits/stdc++.h>
using namespace std;
// This is a modified code based on the directed/undirected weighted graph.
// In order keep things familiar I kept the typedef vertex but, this time
// int since there is no weight to pair with.
typedef int vertex;
// AdjacencyListType is just a name for vector<vector <vertex>>
// The outermost vector is initialized to size v here.
// Think of the outermost vector as the leftmost side or, column in the visual representation
// shown in the books. The inner vector is each for the rows single dimensional array. The
// inner vector stores the destination or adjacent nodes. Basically each of the boxes.
typedef vector<vector <vertex> > AdjacencyListType;
// Take input of directed unweighted graph
// AdjacencyListType &adjList is pass by reference of the adjacency list of type vector<vector <vertex>>
// The const keyword is added wherever I know the value does not need to be modified.
void inputAdjacencyList(AdjacencyListType &adjList, int const& edges){
int source, dest;
for(int i = 0; i < edges; ++i){
cin >> source >> dest;
vertex vrtx(dest);
adjList[source].push_back(vrtx);
}
}
// If there are no adjacent node "NONE" is printed.
// adjList[m].size() gets the connected node count of the current node.
// Then adjList[m][j] gets a specific node which is of pair<int, int> type.
// Now get the node name and the pair by accessing the first and second property.
// Since I have paired node name with weight so, the first is name and next one is the weight
void printCompleteAdjacencyList( AdjacencyListType const& adjList, int &v ){
for(int i = 0; i < v; ++i){
int adjNodes = adjList[i].size();
printf("Adjacent of: %d", i);
if(adjNodes > 0){
for(int j = 0; j < adjNodes; ++j){
printf(" -> %d", adjList[i][j]);
}
}else{
printf(" -> NONE");
}
printf("\n");
}
}
// List nodes adjacent or, connected with current node.
void listAdjacentNodes( AdjacencyListType const& adjList, int const& m){
printf("%d", m);
for(int j = 0; j < adjList[m].size(); ++j){
printf(" -> %d", adjList[m][j]);
}
}
int main(){
// Input the vertex or, node count of the graph
printf("Enter number of nodes:\n");
int v;
cin >> v;
// Create the adjacency list structure with size of v.
AdjacencyListType adjList(v);
// Input the edge count of the graph
printf("Enter Edge count:\n");
int edges;
cin >> edges;
// Input the adjacency list
printf("\nEnter source, destination:\n");
inputAdjacencyList(adjList, edges);
// Show the complete adjacency list structure
printf("\nWhole Adjacency List:\n");
printCompleteAdjacencyList(adjList, v);
// Enter a node number to see its adjacent or connected nodes
printf("\nEnter node number to see adjacent nodes:\n");
int m;
scanf("%d", &m);
// If the given node number is greater than the vertexes or, node count do nothing
if(m < v){
listAdjacentNodes(adjList, m);
}
return 0;
}
view raw UnweightedDirectedAdjacencyListGraph.cpp hosted with ❤ by GitHub

Sample Input for Weighted Undirected Graphs:

6
7
0 5 5
0 3 9
1 2 4
1 4 3
1 5 1
2 4 2
3 5 7

Graph for the Sample Input:

Complete Visual Representation of the Adjacency List Structure:

Weighted Undirected Graph vector of vector Code:

/**
* Author: Asif Ahmed
* Site: http://quickgrid.blogspot.com
* Description: Inputting and Representing an Weighted undirected graph
* in adjacency list vector of vector using C++ STL.
*/
#include<bits/stdc++.h>
using namespace std;
// pair<int, int> pairs node name with weight. Basically each of the boxes
// in the visual representation with arrows points out.
typedef pair<int, int> vertex;
// AdjacencyListType is just a name for vector<vector <vertex>>
// The outermost vector is initialized to size v here.
// Think of the outermost vector as the leftmost side or, column in the visual representation
// shown in the books. The inner vector is each for the rows single dimensional array. The
// inner vector stores pair<int, int> in each of its slot. Where pair<int, int> is used to
// show the adjacent node and the weight between the nodes. Basically each of the boxes.
typedef vector<vector <vertex>> AdjacencyListType;
// Take input of undirected weighted graph
// AdjacencyListType &adjList is pass by reference of the adjacency list of type vector<vector <vertex>>
// The const keyword is added wherever I know the value does not need to be modified.
void inputAdjacencyList(AdjacencyListType &adjList, int const& edges){
int source, dest, weight;
for(int i = 0; i < edges; ++i){
cin >> source >> dest >> weight;
vertex vet1(dest, weight);
adjList[source].push_back(vet1);
vertex vet2(source, weight);
adjList[dest].push_back(vet2);
}
}
// If there are no adjacent node "NONE" is printed.
// adjList[m].size() gets the connected node count of the current node.
// Then adjList[m][j] gets a specific node which is of pair<int, int> type.
// Now get the node name and the pair by accessing the first and second property.
// Since I have paired node name with weight so, the first is name and next one is the weight
void printCompleteAdjacencyList( AdjacencyListType const& adjList, int &v ){
for(int i = 0; i < v; ++i){
int adjNodes = adjList[i].size();
printf("Adjacent of: %d", i);
if(adjNodes > 0){
for(int j = 0; j < adjNodes; ++j){
printf(" -> %d (w:%d)", adjList[i][j].first, adjList[i][j].second);
}
}else{
printf(" -> NONE");
}
printf("\n");
}
}
// List nodes adjacent or, connected with current node.
void listAdjacentNodes( AdjacencyListType const& adjList, int const& m){
printf("%d", m);
for(int j = 0; j < adjList[m].size(); ++j){
printf(" -> %d (w:%d)", adjList[m][j].first, adjList[m][j].second);
}
}
int main(){
// Input the vertex or, node count of the graph
printf("Enter number of nodes:\n");
int v;
cin >> v;
// Create the adjacency list structure with size of v.
AdjacencyListType adjList(v);
// Input the edge count of the graph
printf("Enter Edge count:\n");
int edges;
cin >> edges;
// Input the adjacency list
printf("\nEnter source, destination and weight:\n");
inputAdjacencyList(adjList, edges);
// Show the complete adjacency list structure
printf("\nWhole Adjacency List:\n");
printCompleteAdjacencyList(adjList, v);
// Enter a node number to see its adjacent or connected nodes
printf("\nEnter node number to see adjacent nodes:\n");
int m;
scanf("%d", &m);
// If the given node number is greater than the vertexes or, node count do nothing
if(m < v){
listAdjacentNodes(adjList, m);
}
return 0;
}
view raw WeightedUndirectedAdjacencyListGraph.cpp hosted with ❤ by GitHub

Sample Input for Weighted Directed Graphs:

6
7
0 5 5
0 3 9
1 2 4
1 4 3
1 5 1
2 4 2
3 5 7

Graph for the Sample Input:

Complete Visual Representation of the Adjacency List Structure:

Weighted Directed Graph vector of vector Code:

/**
* Author: Asif Ahmed
* Site: http://quickgrid.blogspot.com
* Description: Inputting and Representing an Weighted Directed graph
* in adjacency list vector of vector using C++ STL.
*/
#include<bits/stdc++.h>
using namespace std;
// pair<int, int> pairs node name with weight. Basically each of the boxes
// in the visual representation with arrows points out.
typedef pair<int, int> vertex;
// AdjacencyListType is just a name for vector<vector <vertex>>
// The outermost vector is initialized to size v here.
// Think of the outermost vector as the leftmost side or, column in the visual representation
// shown in the books. The inner vector is each for the rows single dimensional array. The
// inner vector stores pair<int, int> in each of its slot. Where pair<int, int> is used to
// show the adjacent node and the weight between the nodes. Basically each of the boxes.
typedef vector<vector <vertex>> AdjacencyListType;
// Take input of directed weighted graph
// AdjacencyListType &adjList is pass by reference of the adjacency list of type vector<vector <vertex>>
// The const keyword is added wherever I know the value does not need to be modified.
void inputAdjacencyList(AdjacencyListType &adjList, int const& edges){
int source, dest, weight;
for(int i = 0; i < edges; ++i){
cin >> source >> dest >> weight;
vertex vet1(dest, weight);
adjList[source].push_back(vet1);
}
}
// If there are no adjacent node "NONE" is printed.
// adjList[m].size() gets the connected node count of the current node.
// Then adjList[m][j] gets a specific node which is of pair<int, int> type.
// Now get the node name and the pair by accessing the first and second property.
// Since I have paired node name with weight so, the first is name and next one is the weight
void printCompleteAdjacencyList( AdjacencyListType const& adjList, int &v ){
for(int i = 0; i < v; ++i){
int adjNodes = adjList[i].size();
printf("Adjacent of: %d", i);
if(adjNodes > 0){
for(int j = 0; j < adjNodes; ++j){
printf(" -> %d (w:%d)", adjList[i][j].first, adjList[i][j].second);
}
}else{
printf(" -> NONE");
}
printf("\n");
}
}
// List nodes adjacent or, connected with current node.
void listAdjacentNodes( AdjacencyListType const& adjList, int const& m){
printf("%d", m);
for(int j = 0; j < adjList[m].size(); ++j){
printf(" -> %d (w:%d)", adjList[m][j].first, adjList[m][j].second);
}
}
int main(){
// Input the vertex or, node count of the graph
printf("Enter number of nodes:\n");
int v;
cin >> v;
// Create the adjacency list structure with size of v.
AdjacencyListType adjList(v);
// Input the edge count of the graph
printf("Enter Edge count:\n");
int edges;
cin >> edges;
// Input the adjacency list
printf("\nEnter source, destination and weight:\n");
inputAdjacencyList(adjList, edges);
// Show the complete adjacency list structure
printf("\nWhole Adjacency List:\n");
printCompleteAdjacencyList(adjList, v);
// Enter a node number to see its adjacent or connected nodes
printf("\nEnter node number to see adjacent nodes:\n");
int m;
scanf("%d", &m);
// If the given node number is greater than the vertexes or, node count do nothing
if(m < v){
listAdjacentNodes(adjList, m);
}
return 0;
}
view raw WeightedDirectedAdjacencyListGraph.cpp hosted with ❤ by GitHub

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)

POPULAR POSTS

BLOG ARCHIVE

Information

This site is continuation of:
https://quickgrid.wordpress.com

Version

QuickGrid Version 0.1.ß

Changelog

- Google Pagespeed ranking decreased to 80/100
- Not Fixed: Navbar scrolling smooth transition
- Not Fixed: Article header redesign
- Not Fixed: Tablet view webpage style