/**
* A template graph and bfs algorithm
*
* Author: Erel Segal
* Date: 2010-10-17
*/
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <queue>
using namespace std;
typedef unsigned int uint;
/**
* A graph that stores edges in adjacency list.
*/
template <class VertexKey, class Vertex> class Graph {
typedef set<VertexKey> AdjacencyList;
typedef map<VertexKey,Vertex> VertexMap;
typedef map<VertexKey,AdjacencyList> EdgeMap;
VertexMap myVertices;
EdgeMap myOutgoingEdges;
public:
Graph<VertexKey,Vertex> () {}
Graph<VertexKey,Vertex>& addVertex(VertexKey key, const Vertex& newVertex) {
myVertices[key]=newVertex;
return *this;
}
Graph<VertexKey,Vertex>& addEdge (VertexKey keyFrom, VertexKey keyTo) {
// add the two vertices if they doesn't exist:
myVertices[keyFrom];
myVertices[keyTo];
myOutgoingEdges[keyFrom].insert(keyTo);
return *this;
}
void printOutgoingEdges(VertexKey key, ostream& out) {
out << key << " -> ";
myVertices[key]; // may add a new vertex if not exists
const AdjacencyList& targets = myOutgoingEdges[key];
typename AdjacencyList::const_iterator f;
for (f=targets.begin(); f!=targets.end(); ++f) {
out << " " << (*f);
}
out << endl;
}
void printIncomingEdges(VertexKey key, ostream& out) {
out << key << " <- ";
myVertices[key]; // may add a new vertex if not exists
typename EdgeMap::const_iterator e;
for (e=myOutgoingEdges.begin(); e!=myOutgoingEdges.end(); ++e) {
VertexKey currentSource = e->first;
const AdjacencyList& currentTargets = e->second;
if (currentTargets.count(key)) {
out << currentSource << " ";
}
}
out << endl;
}
void print(ostream& out) const {
out << "VERTICES:" << endl;
out << myVertices;
out << "EDGES:" << endl;
typename EdgeMap::const_iterator e;
for (e=myOutgoingEdges.begin(); e!=myOutgoingEdges.end(); ++e) {
VertexKey currentSource = e->first;
const AdjacencyList& currentTargets = e->second;
typename AdjacencyList::const_iterator f;
for (f=currentTargets.begin(); f!=currentTargets.end(); ++f) {
out << " " << currentSource << "-" << (*f) << endl;
}
}
}
friend ostream& operator<< (ostream& out, Graph<VertexKey,Vertex> g) {
g.print(out);
return out;
}
/// @see http://w...content-available-to-author-only...t.org/doc/libs/1_43_0/libs/graph/doc/breadth_first_search.html
void breadth_first_search(VertexKey source, map<VertexKey,uint>& distances) const {
enum {white, gray, black};
map<VertexKey,int> vertexColor;
queue<VertexKey> vertexQueue;
// Initialize vertices:
typename VertexMap::const_iterator v;
for (v=myVertices.begin(); v!=myVertices.end(); ++v) {
vertexColor[v->first] = white;
distances[v->first] = 0-1; // max uint
}
// Initlaize source:
vertexColor[source] = gray;
distances[source] = 0;
vertexQueue.push(source);
// Loop over all vertices:
while (!vertexQueue.empty()) {
VertexKey current = vertexQueue.front(); // finish a vertex
vertexQueue.pop();
uint current_distance = distances[current];
// Loop over all outgoing edges of the current vertex:
const AdjacencyList& nextTargets = (myOutgoingEdges.find(current))->second;
typename AdjacencyList::const_iterator neighbour;
for (neighbour=nextTargets.begin(); neighbour!=nextTargets.end(); ++neighbour) {
if (vertexColor[*neighbour]==white) { // a tree edge
vertexColor[*neighbour] = gray;
distances[*neighbour] = current_distance+1;
vertexQueue.push(*neighbour);
} else { // a non-tree edge
// don't do anything
}
}
vertexColor[current] = black; // finish a vertex
}
// cleanup:
for (v=myVertices.begin(); v!=myVertices.end(); ++v) {
if (distances[v->first] == 0-1) // max uint
distances.erase(v->first);
}
}
};
template <class K, class T> ostream& operator<< (ostream& out, const map<K,T>& theMap) {
typename map<K,T>::const_iterator v;
for (v=theMap.begin(); v!=theMap.end(); ++v) {
out << " " << v->first << ": " << v->second << endl;
}
return out;
}
int main() {
Graph <char,bool> g;
g.addEdge('a','b').addEdge('b','c').addEdge('c','d').addEdge('d','a').addEdge('a','c');
cout << g << endl;
g.printOutgoingEdges('a',cout);
g.printOutgoingEdges('b',cout);
g.printOutgoingEdges('c',cout);
g.printOutgoingEdges('d',cout);
g.printOutgoingEdges('e',cout);
cout << endl;
g.printIncomingEdges('a',cout);
g.printIncomingEdges('b',cout);
g.printIncomingEdges('c',cout);
g.printIncomingEdges('d',cout);
g.printIncomingEdges('e',cout);
cout << endl;
map<char,uint> distances;
g.breadth_first_search('a', distances);
cout << "BFS from a: " << endl << distances << endl;
g.breadth_first_search('b', distances);
cout << "BFS from b: " << endl << distances << endl;
g.breadth_first_search('c', distances);
cout << "BFS from c: " << endl << distances << endl;
g.breadth_first_search('d', distances);
cout << "BFS from d: " << endl << distances << endl;
g.breadth_first_search('e', distances);
cout << "BFS from e: " << endl << distances << endl;
}