Back to Code List
c++

Graphs

Here are three files with different types of graphs and their traversal. I can't take much claim to these as I don't fully understand all of the code, but hopefully it may help someone in the future.

   1.cpp

#include <iostream>
#include <fstream>
using namespace std;

enum colorType {white, blue, red};

struct Vertex
{
	int id;//the id of the vertex
	Vertex * next;
	Vertex(int id_input, Vertex * input_next = NULL)
	{
		id = id_input;
		next = input_next;
	}
};

class Graph
{
	private:
		colorType * color;
		int * pre;
		int * dis;

	public:
		int n;//the number of vertices, the ids of the vertices are from 0 to n-1  
		Vertex ** adj;//adj[i] points the head of the adjacency list of vertex i

		void printSP(int source, int v);//print shortest path from the source to v
		Graph(int n_input);//constructor
		void setAdjLists(int * adjM);//build the adjacency lists from the adecency matrix adjM
		void printAdjLists();//print the adjacency lists of the graph

		void printTraversal();
		void traverse(int);
};

void Graph::traverse(int v)
{
    // Mark the current node as visited and print it
    color[v] = blue;
    cout << v << " ";
 
    // Recur for all the vertices adjacent to this vertex
	Vertex * curr = adj[v];
    while (curr != NULL) {
        if(color[curr->id] == white)
            traverse(curr->id);
		curr = curr->next;
	}
}

void Graph::printTraversal() {
	// Mark all the vertices as not visited
    color = new colorType[n];
    for(int i = 0; i < n; i++)
        color[i] = white;
 
    // Call the recursive helper function to print DFS traversal
    // starting from all vertices one by one
    for(int i = 0; i < n; i++)
        if(color[i] == white) {
            traverse(i);
		} else {
			color[i] = red;
		}
}

//initialize the graph by getting the number of vertices from n_input
Graph::Graph(int n_input)
{
	n = n_input;
	adj = new Vertex * [n];
	//initialize adj[i] to NULL
	for(int i = 0; i < n; i++)
		adj[i] = NULL;
}

//construct the adj lists from the adj matrix adjM
void Graph::setAdjLists(int * adjM)
{
	for(int i = 0; i < n; i++)
	{
		//create the i-th adj list adj[i], note that I consider the
		//vertices in the reverse order from n-1 to 0 so that I can
		//construct the list in order from 0 to n-1 because a new
		//vertex is always inserted to the front
		for(int j = n-1; j >= 0; j--)
		{
			if(adjM[i * n + j] == 1)
			{
				//create a new node and add it to the front of adj[i]
				Vertex * v = new Vertex (j);
				v->next = adj[i];
				adj[i] = v;
			}
		}
	}
}

//print the adj lists
void Graph::printAdjLists()
{
	for(int i = 0; i < n; i++)
	{
		cout << "Adj list of vertex " << i << ": "; 
		Vertex *v = adj[i];
		while(v != NULL)
		{
			if (v->next != NULL)
				cout << v->id << "->";
			else
				cout << v->id;
			v = v->next;
		}
		cout << endl;
	}

	cout << endl;
}

int main()
{
	//open files
	ifstream inputFile;
	inputFile.open("1_input.txt");
	if (!inputFile)
		cout << "Error opening the input file " << endl;
	
	int n;
	//read the number in the first line, which is the number of vertices of
	//the input graph
	inputFile >> n;

	//cout << "The number of vertices is: " << n << endl;

	//next we read the adjacency matrix from the file to an array M.
	//Here we use a one-dimensional array to simulate a two-dimesional
	//adjacency matrix because we already know the length of each row
	//is n
	int * M = new int [n * n];
	int i = 0;
	int value;
	while(inputFile >> value)
	{
		M[i] = value;
		i++;
	}

	//uncomment the following piece of code if you want to check
	//whether the adj matrix is read correctly from the input file
	/*
	cout << "The following is the matrix:" << endl;
	for(int i = 0; i < n * n; i++)
	{
		if(i % n == 0)
			cout << endl;
		cout << M[i] << " ";
	}
	cout << endl;
	*/

	//initialize the graph by passing n to it and construct the
	//adjacency lists
	Graph graph(n);
	graph.setAdjLists(M);

	//uncomment the following line if you want to print the adj lists
	//graph.printAdjLists();

	cout << "The following is the DFS traversal vertex order, staring from vertex 0:" << endl;
	graph.printTraversal();
	cout << endl;

	inputFile.close();
	return 0;
}

    

   1_input.txt

8
0 1 1 0 0 0 0 0
0 0 0 1 0 0 0 0
0 1 0 0 0 0 0 0
0 0 1 0 0 0 1 0
0 1 0 1 0 1 0 1
0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0
    

   2.cpp

#include <iostream>
#include <fstream>
using namespace std;

struct Vertex
{
	int id;//the id of the vertex
	Vertex * next;
	Vertex(int id_input, Vertex * input_next = NULL)
	{
		id = id_input;
		next = input_next;
	}
};

class Graph
{
	public:
		int n;//the number of vertices, the ids of the vertices are from 0 to n-1  
		Vertex ** adj;//adj[i] points the head of the adjacency list of vertex i

		void topSort();//do topological sort

		Graph(int n_input);//constructor
		void setAdjLists(int * adjM);//build the adjacency lists from the adecency matrix adjM
		void printAdjLists();//print the adjacency lists of the graph
};

void Graph::topSort()
{
	int *degArr = new int[n];
	int *queue = new int[n];

	for (int i = 0; i < n; i++)
		degArr[i] = 0;

	//get degress for each vertex
	for (int i = 0; i < n; i++)
	{
		Vertex * v = adj[i];
		while (v != NULL)
		{
			degArr[v->id]++;
			v = v->next;
		}
	}

	int qFront, qRear;
	qFront = -1;

	//queue initial verticies
	for (int i = 0; i < n; i++)
	{
		if (degArr[i] == 0)
		{
			if (qFront > -1)
			{
				// add to queue
				qRear++;
				queue[qRear] = i;
			}
			else
			{
				//start queue
				qFront = qRear = 0;
				queue[0] = i;
			}

		}
	}

	int count = 0;

	while (qFront != -1 && qFront <= qRear)
	{
		int curr = queue[qFront];
		//dequeue and print
		cout << curr << " ";
		qFront++;
		count++;

		//check the adjacecy list of u
		Vertex * v = adj[curr];
		while (v != NULL)
		{
			degArr[v->id]--;
			if (degArr[v->id] == 0)
			{
				qRear++;
				queue[qRear] = v->id;
			}
			v = v->next;
		}
	}

	cout << endl;

	if (count < n)
		cout << "Not a DAG. ";
}

Graph::Graph(int n_input)
{
	n = n_input;
	adj = new Vertex * [n];
	//initialize adj[i] to NULL
	for(int i = 0; i < n; i++)
		adj[i] = NULL;
}


//construct the adj lists from the adj matrix adjM
void Graph::setAdjLists(int * adjM)
{
	for(int i = 0; i < n; i++)
	{
		//create the i-th adj list adj[i], note that I consider the
		//vertices in the reverse order from n-1 to 0 so that I can
		//construct the list in order from 0 to n-1 because a new
		//vertex is always inserted to the front
		for(int j = n-1; j >= 0; j--)
		{
			if(adjM[i * n + j] == 1)
			{
				//create a new node and add it to the front of adj[i]
				Vertex * v = new Vertex (j);
				v->next = adj[i];
				adj[i] = v;
			}
		}
	}
}

//print the adj lists
void Graph::printAdjLists()
{
	for(int i = 0; i < n; i++)
	{
		cout << "Adj list of vertex " << i << ": "; 
		Vertex *v = adj[i];
		while(v != NULL)
		{
			if (v->next != NULL)
				cout << v->id << "->";
			else
				cout << v->id;
			v = v->next;
		}
		cout << endl;
	}

	cout << endl;
}


int main()
{
	//open files
	ifstream inputFile;
	inputFile.open("2_input.txt");
	if (!inputFile)
		cout << "Error opening the input file " << endl;
	
	int n;
	//read the number in the first line, which is the number of vertices of
	//the input graph
	inputFile >> n;

	cout << "The number of vertices is: " << n << endl;

	//next we read the adjacency matrix from the file to an array M.
	//Here we use a one-dimensional array to simulate a two-dimesional
	//adjacency matrix because we already know the length of each row
	//is n
	int * M = new int [n * n];
	int i = 0;
	int value;
	while(inputFile >> value)
	{
		M[i] = value;
		i++;
	}
	inputFile.close();

	//uncomment the following piece of code if you want to check
	//whether the adj matrix is read correctly from the input file
	
	cout << "The following is the matrix:" << endl;
	for(int i = 0; i < n * n; i++)
	{
		if(i % n == 0)
			cout << endl;
		cout << M[i] << " ";
	}
	cout << endl;
	

	//initialize the graph by passing n to it
	Graph graph(n);
	graph.setAdjLists(M);

	//uncomment the following line if you want to print the adj lists
	graph.printAdjLists();

	cout << "The following is a topological order:" << endl;
	graph.topSort();

	cout << endl;

	return 0;
}
    

   2_input.txt

7
0 1 0 0 1 0 0 
0 0 1 0 1 0 0 
0 0 0 0 0 1 0 
0 0 0 0 1 0 0 
0 0 0 0 0 1 0 
0 0 0 0 0 0 0 
0 0 0 1 1 0 0

    

   3.cpp

#include <iostream>
#include <fstream>
using namespace std;

//enum colorType {white, blue, red};

const int MAX = 10000;

struct Vertex
{
	int id;//the id of the vertex
	int weight; //the weight of an edge (u,v), where v is the current node and v is in the adj list of vertex u
	Vertex * next;
	Vertex(int id_input, int weight_input = 1, Vertex * next_input = NULL)
	{
		id = id_input;
		weight = weight_input;
		next = next_input;
	}
};

class Graph
{
	private:
		int * pre;//the predecessor array
		int * dis;//the shortest path distance array

	public:
		int n;//the number of vertices, the ids of the vertices are from 0 to n-1  
		Vertex ** adj;//adj[i] points the head of the adjacency list of vertex i
		
		Graph(int n_input);//the class constructor

		void Dijkstra(int s);//compute a shortest path tree from the source vertex s in a general graph

		void printSP(int source, int v);//print the shortest path from the source vertex to v
		int getSPdis(int v);//return the shortest path distance from the source vertex to v

		void setAdjLists(int * adjM);// convert the adj matrix M to adj list
		void printAdjLists();//print the adj list of the graph
};

//compute the correct information for the two
//arrays pre[] and dis[]
void Graph::Dijkstra(int s)
{
	int count = n;
	int *queue = new int[n];
	
	for (int i = 0; i < n; i++)
	{
		dis[i] = MAX;
		pre[i] = -1;
	}

	dis[s] = 0;

	for (int i = 0; i < n; i++)
		queue[i] = 1;

	while (count > 0)
	{
		//extract min
		int min;
		int currmin = MAX;
		for (int i = 0; i < n; i++)
		{
			if (queue[i] == 1 && dis[i] < currmin)
			{
				min = i;
				currmin = dis[i];
			}
		}

		//dequeue
		int idx = min;
		queue[idx] = 0;
		count--;

		//update weights
		Vertex * v = adj[idx];
		while (v != NULL)
		{
			if (dis[v->id] > dis[idx] + v->weight)
			{
				dis[v->id] = dis[idx] + v->weight;
				pre[v->id] = idx;
			}
			v = v->next;
		}
	}
}

//return
int Graph::getSPdis(int v)
{
	return dis[v];
}

void Graph::printSP(int source, int v)
{
	if(v == source)
		cout << source;
	else
	{
		printSP(source, pre[v]);
		cout << "->" << v; 
	}
}


Graph::Graph(int n_input)
{
	n = n_input;
	adj = new Vertex * [n];
	//initialize adj[i] to NULL
	for(int i = 0; i < n; i++)
		adj[i] = NULL;
	
	//create the two arrays of size n for the n vertices
	pre = new int [n];
	dis = new int [n];
}

void Graph::setAdjLists(int * adjM)
{
	for(int i = 0; i < n; i++)
	{
		//create the i-th adj list adj[i], note that I consider the
		//vertices in the reverse order from n-1 to 0 so that I can
		//construct the list in order from 0 to n-1 because a new
		//vertex is always inserted to the front
		for(int j = n-1; j >= 0; j--)
		{
			if(adjM[i * n + j] > 0)
			{
				//create a new node and add it to the front of adj[i]
				Vertex * v = new Vertex (j, adjM[i * n + j]);
				v->next = adj[i];
				adj[i] = v;
			}
		}
	}
}

void Graph::printAdjLists()
{
	cout << "The following are the adjacent lists with edge weights in the parentheses:" << endl;
	for(int i = 0; i < n; i++)
	{
		cout << "Adj list of vertex " << i << ": "; 
		Vertex *v = adj[i];
		while(v != NULL)
		{
			if (v->next != NULL)
				cout << v->id << "(" << v->weight << ")" << "->";
			else
				cout << v->id << "(" << v->weight << ")";
			v = v->next;
		}
		cout << endl;
	}

	cout << endl;
}

int main()
{	
	//open files
	ifstream inputFile;
	inputFile.open("3_input.txt");
	if (!inputFile)
		cout << "Error opening the input file " << endl;
	
	int n;
	//read the number in the first line, which is the number of vertices of
	//the input graph
	inputFile >> n;

	cout << "The number of vertices is: " << n << endl << endl;

	//next we read the adjacency matrix from the file to an array M.
	//Here we use a one-dimensional array to simulate a two-dimesional
	//adjacency matrix because we already know the length of each row
	//is n
	int * M = new int [n * n];
	int i = 0;
	int value;
	while(inputFile >> value)
	{
		M[i] = value;
		i++;
	}
	inputFile.close();

	//uncomment the following piece of code if you want to check
	//whether the adj matrix is read correctly from the input file
	
	cout << "The following is the matrix:" << endl;
	for(int i = 0; i < n * n; i++)
	{
		if(i % n == 0)
			cout << endl;
		cout << M[i] << " ";
	}
	cout << endl;
	

	//initialize the graph by passing n to it
	Graph graph(n);
	graph.setAdjLists(M);

	//print the adj lists with edge weights
	graph.printAdjLists();

	int source_vertex = 0;//the source vertex is 0

	graph.Dijkstra(source_vertex);

	//after the Dijkstra's algorithm, the following for loop is supposed to
	//print the shortest paths from the source vertex to all other
	//vertices
	for(int i = 1; i <= n-1; i++)
	{
		cout << "The shortest path from the source vertex " << source_vertex << " to vertex " << i <<": ";
		graph.printSP(source_vertex, i);// print the shortest path from 0 to 5 with source 0
		cout << endl;
	}

	cout << endl;

	//after the Dijkstra's algorithm, the following for loop is supposed to
	//print the shortest path distances from the source vertex to all other
	//vertices
	for(int i = 1; i <= n-1; i++)
	{
		cout << "The shortest path distance from the source vertex " << source_vertex << " to vertex " << i <<" is: ";
	    cout << graph.getSPdis(i) << endl;
	}

	return 0;
}
    

   3_input.txt

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