Integer weighted directed graph + Strongly Connected Components (SCC) implementation

graph.h

#include <iostream>
#include <vector>
#include <map>
#include <string>

using namespace std;
extern unsigned int time;

// vertex data structure
// employs STL pair and vector to store adjacent list
// name  : vertex name
// parent: its parent when traversal
// d     : discovery time
// f     : finish time
struct vertex{
	vector<pair<int, vertex*> > adj; //cost of edge, destination vertex
	string name, parent;
	size_t d, f;
	vertex(string s) : d(0), f(0)
	{
		name = s;
	}
};

// graph employs STL map data structure
// to store graph vertices.
// To query a vertex in the graph,
// find([VERTEX NAME]) can be used
class graph
{
public:
	// constructors and destructor
	graph() : V(){}
	~graph();
	graph(const graph& rhs);
	graph& operator=(const graph& rhs);

	typedef map<string, vertex *> vmap;

	// add a new vertex
	void addVertex(const string&);

	// add a new edge
	void addEdge(const string& from, const string& to, int weight);

	// do depth first search
	void DFS(const string& s, map<string, bool>& visited);
	const vmap& getV() const;

	// return the graph with edge transposed
	graph& Transposed() const;

	// find set of Strongly Connected Components
	void SCC(graph& transposed);

	// print time stamp
	void print() const;

private:
	vmap V;
	void DFSVisit(vertex& v, map<string, bool>& visited, bool print=false);
};

const graph::vmap& graph::getV() const
{
	return V;
}

// destructor
graph::~graph()
{
	vmap::iterator itr = V.begin();
	for (; itr != V.end(); ++itr)
	{
		delete itr->second;
	}
}

// copy constructor
graph::graph(const graph& rhs)
{
	vmap::const_iterator itr = rhs.V.begin();
	// copy vertices
	for (; itr != rhs.V.end(); ++itr)
	{
		vertex* f = new vertex(itr->first);
		V[f->name] = f;
	}

	// copy edges
	vmap::const_iterator eitr = rhs.V.begin();
	for (; eitr != rhs.V.end(); ++eitr)
	{
		for (size_t i = 0; i < eitr->second->adj.size(); i++)
		{
			vertex *from = V.find(eitr->first)->second;
			vertex *to = V.find(eitr->second->adj[i].second->name)->second;
			pair<int, vertex*> pair = make_pair(eitr->second->adj[i].first, to);
			from->adj.push_back(pair);
		}
	}
}

// copy operator
graph& graph::operator=(const graph& rhs)
{
	vmap::const_iterator itr = rhs.V.begin();
	// copy vertices
	for (; itr != rhs.V.end(); ++itr)
	{
		vertex* f = new vertex(itr->first);
		V[f->name] = f;
	}

	// copy edges
	vmap::const_iterator eitr = rhs.V.begin();
	for (; eitr != rhs.V.end(); ++eitr)
	{
		for (size_t i = 0; i < eitr->second->adj.size(); i++)
		{
			vertex *from = V.find(eitr->first)->second;
			vertex *to = V.find(eitr->second->adj[i].second->name)->second;
			pair<int, vertex*> pair = make_pair(eitr->second->adj[i].first, to);
			from->adj.push_back(pair);
		}
	}
	return *this;
}

// print all Vertex with its information
void graph::print() const
{
	vmap::const_iterator itr = V.begin();
	for (; itr != V.end(); ++itr)
	{
		cout << "Vertex     : " << itr->first << endl;
		cout << "Its parent : " << itr->second->parent << endl;
		cout << "Discoverty : " << itr->second->d << endl;
		cout << "Finish     : " << itr->second->f << endl << endl;
	}
	cout << endl;
}

// Add a vertex in a graph
void graph::addVertex(const string &name)
{
	vmap::iterator itr = V.begin();
	itr = V.find(name);
	if (itr == V.end())
	{
		vertex *v;
		v = new vertex(name);
		V[name] = v;
		return;
	}
	cerr << "\nVertex already exists!" << endl;
}

// Add an edge to the vertex 'from' heading to 'to' of weight 
void graph::addEdge(const string& from, const string& to, int weight)
{
	vertex *f = (V.find(from)->second);
	vertex *t = (V.find(to)->second);
	pair<int, vertex *> edge = make_pair(weight, t);
	f->adj.push_back(edge);
}

// Return Transposed Graph
graph& graph::Transposed() const
{
	// Transpose edges
	graph* gt = new graph();
	vmap::const_iterator itr = V.begin();
	// copy vertices
	for (; itr != V.end(); ++itr)
	{
		vertex* f = new vertex(itr->first);
		gt->V[f->name] = f;
	}
	// copy edges but transposed
	vmap::const_iterator eitr = V.begin();
	for (; eitr != V.end(); ++eitr)
	{
		for (size_t i = 0; i < eitr->second->adj.size(); i++)
		{
			vertex *from = V.find(eitr->first)->second;
			vertex *to = gt->V.find(eitr->second->adj[i].second->name)->second;
			pair<int, vertex*> pair = make_pair(eitr->second->adj[i].first, from);
			to->adj.push_back(pair);
		}
	}
	return *gt;
}

// DFS traversal
void graph::DFS(const string& s, map<string, bool>& visited)
{
	// DFS start with vertex s
	vmap::iterator vIter = V.find(s);
	DFSVisit(*(vIter->second), visited);

	// loop DFS for the rest of vertices
	vmap::iterator itr = V.begin();
	map<string, bool>::iterator isVisit;
	for (; itr != V.end(); ++itr)
	{
		isVisit = visited.find(itr->first);
		if (isVisit == visited.end())
		{
			// not visited
			DFSVisit(*(itr->second), visited);
		}
	}
}

// helper function for DFS traversal
void graph::DFSVisit(vertex& v, map<string, bool>& visited, bool print)
{
	time = time + 1;
	// discovery time
	v.d = time;
	// mark visited
	visited[v.name] = true;
	for (size_t i = 0; i<v.adj.size(); i++)
	{
		map<string, bool>::iterator itr = visited.find(v.adj[i].second->name);
		if (itr == visited.end())
		{
			if (print)
				cout << v.adj[i].second->name << " ";

			// mark visited and recursively visit
			// set its parent
			v.adj[i].second->parent = v.name;

			// recursively visit
			DFSVisit(*(v.adj[i].second), visited, print);
		}
	}
	time = time + 1;
	v.f = time;
}

// Print strongly connected components
void graph::SCC(graph& transposed)
{
	// traverse transposed graph in order of decreasing f
	// save vertices by its name(string)
	map<int, string> orderedv;
	vmap::iterator itr = V.begin();
	for (; itr != V.end(); ++itr)
	{
		pair<int, string> v = make_pair(itr->second->f, itr->first);
		orderedv.insert(v);
	}
	// DFS transposed graph
	map<int, string>::reverse_iterator vitr = orderedv.rbegin();
	map<string, bool> visited;
	const vmap trnposV = transposed.getV();
	for (; vitr != orderedv.rend(); ++vitr)
	{
		map<string, bool>::iterator vstitr = visited.find(vitr->second);
		if (vstitr == visited.end())
		{
			cout << "------Strongly connected components------" << endl;
			cout << vitr->second << " ";
			vertex* v = trnposV.find(vitr->second)->second;
			DFSVisit(*v, visited, true);
			cout << "\n-----------------------------------------" << endl;
		}
	}
}

main.cpp

#include "graph.h"

unsigned int time = 0;

int main(int argc, char* argv[])
{
	// array set up for vertices and edges
	string vertices[] = { "a", "b", "c", "d", "e", "f", "g", "h" };
	int edges[][3] = { 
		{ 0, 1, 0 },
		{ 1, 2, 0 },
		{ 1, 4, 0 },
		{ 1, 5, 0 },
		{ 2, 6, 0 },
		{ 2, 3, 0 },
		{ 3, 2, 0 },
		{ 3, 7, 0 },
		{ 4, 0, 0 },
		{ 4, 5, 0 },
		{ 5, 6, 0 },
		{ 6, 5, 0 },
		{ 6, 7, 0 },
		{ 7, 7, 0 }
	};
	
	// initialization
	size_t nV = 8, nE = 14;
	graph g;
	for (size_t i = 0; i<nV; i++)
		g.addVertex(vertices[i]);
	for (size_t i = 0; i<nE; i++)
		g.addEdge(vertices[edges[i][0]], vertices[edges[i][1]], edges[i][2]);

	// DFS
	map<string, bool> visit;
	g.DFS("c", visit);
	g.print();

	// Create a Transposed Graph
	graph gt = g.Transposed();

	// Operate SCC
	g.SCC(gt);
	
	return 0;
}