Graph Theory Class

Documentation

About

The Graph Theory Templated class is a data structure to handle theoretical graphs. If the term G has {E,V} is familiar to you, this may assist you in any programs your have to write. Its internal structure contains a double-linked-list that contains nodes. Then each node contains links to other nodes which are the edges. Edges only go in one direction when they are created (that is, if you make a edge from A to B, there is not an edge that goes from B to A).

Below you will find documentation about how to use the class as provided and information to extend the templated class as you may need it.

Class Declarations

The following classes are defined. All classes are in the namespace GraphTheory.

GraphTheory::Graph<typename T, typename S>

This basic Graph class holds all the data in the graph and manages the nodes and edges. It is the only class you should need to use directly. Typename T is the data type used to identify nodes. Typename S is the data type stored in edges (can be used to give edges a weight, etc). In this class defines the following other classes and functions.
class GraphTheory::Graph<typename T, typename S>::Node

This class manages the node details. It has a public variable named ident of type T defined when defining the class. This has user stored information in it, and may be changed at any time. This ident is used to identify the node, so it must have the operator== defined. The following are important functions.
Constructor() and Constructor(const T &v)
Sets the ident in the edge during construction.
const T &getIdent()const
Returns constant reference to the ident value stored in the node.
EdgeIterator begin_edge()const
Returns the beginning of the iterator for edges contained by this node.
EdgeIterator end_edge()const
Returns the end iterator for the edges used by this node.
int EdgeCount()const
Returns the number of edges in this node.

class GraphTheory::Graph<typename T, typename S>::Edge

This class contains information about edges. It has now functions besides the constructor (which you shouldn't be using) and only has one public variable you need. It is of type S and is named evalue ("Edge Value"). You can use this to assign things such as weights to edges or give them names.

class GraphTheory::Graph<typename T, typename S>::NodeIterator

The NodeIterator is used to iterate through all the nodes within the class. It can be used like an std::vector::iterator in that it has some main operators. It has operator==, operator!=, operator++, operator*, operator->. In addition it has a member function named ptr() which will return a pointer to the node it's pointing to (though you should be able to use operator-> as a substitute).

You can find an example of the iterator being used below.

class GraphTheory::Graph<typename T, typename S>::EdgeIterator

EdgeIterator has all the same member functions as NodeIterator except it is used to iterate through edges. You can find examples of use below.

Additional functions

std::ostream &operator<<(std::ostream&, Graph::GraphTheory)

Used to output plain text describing the current state of the graph.

Writing your own Node class

Sometimes it is necessary to be able to write your own structure to contain nodes or edges. I made it quite simple to do this. In order to make your own node class it requires that operator==, and operator<< for std::ostream is defined. One example of this is done for the dijsktra's implementation (seen below, in Examples). Because of the way Dijsktra's algorithm is written, each node needs two pieces of data. An identifying part, as well as a return part telling the best distance from the starting point. Then each edge needs one piece of data, which is a cost, and this is easily satisfied in the original class.

Here is the implementation of WeightedNode (Which is simply a node that stores two pieces of data). You can see how this class is used in the Example section. The graph class is created by using GraphTheory::Graph<WeightedNode<int,int>, ...>

Writing your own Edge Class

Writing your own edge class is the same as writing your own Node class. The only difference is the only operator needed to be defined is operator<< for std::ostream capabilities.

Examples

Simple Example

This example will create a graph with four nodes and four edges.

Using Iterators

This example shows how to use iterators for nodes and edges to fetch data.

#include <iostream>
#include <string>
using namespace std;
#include "graph.h"
int main(){
	GraphTheory::Graph<std::string, int> graph;
	
	//Add nodes to graph.  Nodes are of type std::string
	graph.AddNode("node1");
	graph.AddNode("node2");
	graph.AddNode("node3");
	graph.AddNode("node4");
	
	//Add edges from first node to second node. These edges don't have values.
	graph.AddEdge("node1", "node2");
	graph.AddEdge("node1", "node3");
	graph.AddEdge("node2", "node3");
	graph.AddEdge("node2", "node3");
	
	//Change a value of an edge
	//We should check for NULL pointer here, but we know it exists thus is not necessary.
	graph.FindEdge("node1", "node2")->evalue = 1;
	
	//Print out all nodes
	cout << "List: " << endl;
	for (GraphTheory::Graph<std::string>::NodeIterator i = graph.begin(); i != graph.end(); ++i){
		cout << "Node " << (*i).getIdent() << endl;
	}
	
	//Print out ALL edges
	for (GraphTheory::Graph<std::string>::EdgeIterator i = graph.begin_edge(); i != graph.end_edge(); ++i){
		cout << "Edge "	<< (*i).owner->getIdent() << " to " << (*i).dst->getIdent() << endl;
	}
	
	//Prints out edges only owned by node1
	cout << "Edges owned by node1" << endl;
	GraphTheory::Graph<std::string>::Node *node2 = graph.FindNode("node1");
	if (node2){	//Check if node2 exists
		for (GraphTheory::Graph<std::string>::EdgeIterator i = node2->begin_edge(); i != node2->end_edge(); ++i)
			cout << "Edge " << i->owner->getIdent() << " to " << i->dst->getIdent() << endl; 
	}
	
	return 0;
}

More Complex - Dijkstra Implementation

This example loads in a file which contains a graph and runs dijkstra's algorithm and outputs it to the screen. An example of an input file can be found in input1.txt.

#include <iostream>
#include <fstream>
using namespace std;
#include "graph.h"
int main(){
	//Note how we have weighted nodes as first value.  This is an "extra" class.
	GraphTheory::Graph< GraphTheory::WeightedNode<int,int>, int > graph;
	std::cout << "Dijkstra's Algorithm!" << std::endl;
	
	//Open the file
	ifstream file("input1.txt");	//Change input as appropriate. Suggested to make command line argument.
	if (!file)
		return 1;
		
	
	
	//loading file-------
	char type;
	int v1,v2,v3;	//Temp values
	while (file >> type){
		if (type == 'V'){
			//Load in a vertex
			file >> v1;
			graph.AddNode( GraphTheory::WeightedNode<int,int>(v1, -1) );	//Make initial value of node -1
		}else if (type == 'E'){
			//Load in an edge
			file >> v1 >> v2 >> v3;
			graph.AddEdge(v1, v2 ,v3);
		}else{
			//Found bad data. Exit.
			cerr << "Invalid type " << type << std::endl;
			return 1;
		}
	}
	
	//Run dijkstra on it: Inputs graph, and the source node (source node is defined as a node)
	GraphTheory::Dijkstra(graph, GraphTheory::WeightedNode<int,int>(1, 0) );
	
	//Output the graph
	cout << "Output graph:" << endl;
	cout << graph; //output it
	cout << "DONE" << endl;
	return 0;
}

Implementation in graph.h:

template <typename T> class PQ_CompareVertex{
public:
	bool operator()(const T &n1, const T &n2){
		return n1->ident.dist < n2->ident.dist;
	}
};

//Shortest path algorithm when S  is WeightedNode<M,N> and S is a numerical type, matching N
template <typename T, typename S> void Dijkstra(const GraphTheory::Graph<T,S> &input, const T &source){
	
	//Create the priority queue
	std::priority_queue<typename Graph<T,S>::Node*, std::vector<typename Graph<T,S>::Node* >, PQ_CompareVertex<typename Graph<T,S>::Node*> > vqueue;
	
	//Set all distances to -1
	for (typename Graph<T,S>::NodeIterator i = input.begin(); i != input.end(); ++i)
		i->ident.dist = -1; 
	
	//Get the source
	typename Graph<T,S>::Node *first = input.FindNode(source);
	first->ident.dist = 0;
	vqueue.push( first );
	
	//loop through queue until empty
	while (!vqueue.empty()){
		typename Graph<T,S>::Node *curr = vqueue.top();
		vqueue.pop();
		
		//Go through each edge connecting curr
		for (typename Graph<T,S>::EdgeIterator e = curr->begin_edge(); e != curr->end_edge(); ++e){
			if (e->dst->ident.dist == -1 || e->dst->ident.dist > curr->ident.dist + e->evalue){
				e->dst->ident.dist = curr->ident.dist + e->evalue;
				vqueue.push(e->dst);
			}
		}
	}
	
	//DONE
}

License

This software is licensed under the GPLv3.

GraphClass is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.

GraphClass is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with GraphClass. If not, see <http://www.gnu.org/licenses/>.

Download

The latest plain text version can be viewed in graph.h.

Version	Release Date	Formats
1.0	5/25/2008	zip \| tar.bz2

Versions

5/25/2008 - Version 1.0
Basic graph theory program released.

Contact

If you have a question please post it on the RedGalaxy QA website. You can contact me by sending an email to