fork download
copy 
  1. /**
  2.  * A template graph and bfs algorithm
  3.  *
  4.  * Author: Erel Segal
  5.  * Date: 2010-10-17
  6.  */
  7.  
  8. #include <iostream>
  9. #include <map>
  10. #include <set>
  11. #include <string>
  12. #include <queue>
  13. using namespace std;
  14.  
  15. typedef unsigned int uint;
  16.  
  17. /**
  18.  * A graph that stores edges in adjacency list.
  19.  */
  20. template <class VertexKey, class Vertex> class Graph {
  21. 	typedef set<VertexKey> AdjacencyList;
  22. 	typedef map<VertexKey,Vertex> VertexMap;
  23. 	typedef map<VertexKey,AdjacencyList> EdgeMap;
  24.  
  25. 	VertexMap myVertices;
  26. 	EdgeMap myOutgoingEdges;
  27.  
  28. public:
  29. 	Graph<VertexKey,Vertex> () {}
  30.  
  31. 	Graph<VertexKey,Vertex>& addVertex(VertexKey key, const Vertex& newVertex) {
  32. 		myVertices[key]=newVertex;
  33. 		return *this;
  34. 	}
  35.  
  36. 	Graph<VertexKey,Vertex>& addEdge  (VertexKey keyFrom, VertexKey keyTo) {
  37. 		// add the two vertices if they doesn't exist:
  38. 		myVertices[keyFrom];
  39. 		myVertices[keyTo];
  40. 		myOutgoingEdges[keyFrom].insert(keyTo);
  41. 		return *this;
  42. 	}
  43.  
  44. 	void printOutgoingEdges(VertexKey key, ostream& out) {
  45. 		out << key << " -> ";
  46. 		myVertices[key];  // may add a new vertex if not exists
  47. 		const AdjacencyList& targets = myOutgoingEdges[key];
  48. 		typename AdjacencyList::const_iterator f;
  49. 		for (f=targets.begin(); f!=targets.end(); ++f) {
  50. 			out << " " << (*f);
  51. 		}
  52. 		out << endl;
  53. 	}
  54.  
  55. 	void printIncomingEdges(VertexKey key, ostream& out) {
  56. 		out << key << " <- ";
  57. 		myVertices[key];  // may add a new vertex if not exists
  58.  
  59. 		typename EdgeMap::const_iterator e;
  60. 		for (e=myOutgoingEdges.begin(); e!=myOutgoingEdges.end(); ++e) {
  61. 			VertexKey currentSource = e->first;
  62. 			const AdjacencyList& currentTargets = e->second;
  63. 			if (currentTargets.count(key)) {
  64. 				out << currentSource << " ";
  65. 			}
  66. 		}
  67. 		out << endl;
  68. 	}
  69.  
  70. 	void print(ostream& out) const {
  71. 		out << "VERTICES:" << endl;
  72. 		out << myVertices;
  73. 		out << "EDGES:" << endl;
  74. 		typename EdgeMap::const_iterator e;
  75. 		for (e=myOutgoingEdges.begin(); e!=myOutgoingEdges.end(); ++e) {
  76. 			VertexKey currentSource = e->first;
  77. 			const AdjacencyList& currentTargets = e->second;
  78. 			typename AdjacencyList::const_iterator f;
  79. 			for (f=currentTargets.begin(); f!=currentTargets.end(); ++f) {
  80. 				out << "  "  << currentSource << "-" << (*f) << endl;
  81. 			}
  82. 		}
  83. 	}
  84.  
  85. 	friend ostream& operator<< (ostream& out, Graph<VertexKey,Vertex> g) {
  86. 		g.print(out);
  87. 		return out;
  88. 	}
  89.  
  90.  
  91. 	/// @see http://w...content-available-to-author-only...t.org/doc/libs/1_43_0/libs/graph/doc/breadth_first_search.html
  92. 	void breadth_first_search(VertexKey source, map<VertexKey,uint>& distances) const {
  93. 		enum {white, gray, black};
  94. 		map<VertexKey,int> vertexColor;
  95. 		queue<VertexKey> vertexQueue;
  96.  
  97. 		// Initialize vertices:
  98. 		typename VertexMap::const_iterator v;
  99. 		for (v=myVertices.begin();  v!=myVertices.end();  ++v) {
  100. 			vertexColor[v->first] = white;
  101. 			distances[v->first] = 0-1; // max uint
  102. 		}
  103.  
  104. 		// Initlaize source:
  105. 		vertexColor[source] = gray;
  106. 		distances[source] = 0;
  107. 		vertexQueue.push(source);
  108.  
  109. 		// Loop over all vertices:
  110. 		while (!vertexQueue.empty()) {
  111. 			VertexKey current = vertexQueue.front();     // finish a vertex
  112. 			vertexQueue.pop();
  113. 			uint current_distance = distances[current];
  114.  
  115. 			// Loop over all outgoing edges of the current vertex:
  116. 			const AdjacencyList& nextTargets = (myOutgoingEdges.find(current))->second;
  117. 			typename AdjacencyList::const_iterator neighbour;
  118. 			for (neighbour=nextTargets.begin(); neighbour!=nextTargets.end(); ++neighbour) {
  119. 				if (vertexColor[*neighbour]==white) {   // a tree edge
  120. 					vertexColor[*neighbour] = gray;
  121. 					distances[*neighbour] = current_distance+1;
  122. 					vertexQueue.push(*neighbour);
  123. 				} else {                        // a non-tree edge
  124. 					// don't do anything
  125. 				}
  126. 			}
  127.  
  128. 			vertexColor[current] = black;   // finish a vertex
  129. 		}
  130.  
  131. 		// cleanup:
  132. 		for (v=myVertices.begin();  v!=myVertices.end();  ++v) {
  133. 			if (distances[v->first] == 0-1) // max uint
  134. 				distances.erase(v->first);
  135. 		}
  136. 	}
  137. };
  138.  
  139.  
  140. template <class K, class T> ostream& operator<< (ostream& out, const map<K,T>& theMap) {
  141. 	typename map<K,T>::const_iterator v;
  142. 	for (v=theMap.begin();  v!=theMap.end();  ++v) {
  143. 		out << "  "  << v->first << ": " << v->second << endl;
  144. 	}
  145. 	return out;
  146. }
  147.  
  148.  
  149. int main() {
  150. 	Graph <char,bool> g;
  151. 	g.addEdge('a','b').addEdge('b','c').addEdge('c','d').addEdge('d','a').addEdge('a','c');
  152. 	cout << g << endl;
  153. 	g.printOutgoingEdges('a',cout);
  154. 	g.printOutgoingEdges('b',cout);
  155. 	g.printOutgoingEdges('c',cout);
  156. 	g.printOutgoingEdges('d',cout);
  157. 	g.printOutgoingEdges('e',cout);
  158. 	cout << endl;
  159. 	g.printIncomingEdges('a',cout);
  160. 	g.printIncomingEdges('b',cout);
  161. 	g.printIncomingEdges('c',cout);
  162. 	g.printIncomingEdges('d',cout);
  163. 	g.printIncomingEdges('e',cout);
  164. 	cout << endl;
  165.  
  166. 	map<char,uint> distances;
  167. 	g.breadth_first_search('a', distances);
  168. 	cout << "BFS from a: " << endl << distances << endl;
  169. 	g.breadth_first_search('b', distances);
  170. 	cout << "BFS from b: " << endl << distances << endl;
  171. 	g.breadth_first_search('c', distances);
  172. 	cout << "BFS from c: " << endl << distances << endl;
  173. 	g.breadth_first_search('d', distances);
  174. 	cout << "BFS from d: " << endl << distances << endl;
  175. 	g.breadth_first_search('e', distances);
  176. 	cout << "BFS from e: " << endl << distances << endl;
  177. }
  178.  
stdin
copy 
Standard input is empty
compilation info 
prog.cpp: In member function ‘void Graph<VertexKey, Vertex>::breadth_first_search(VertexKey, std::map<VertexKey, unsigned int, std::less<_Key>, std::allocator<std::pair<const VertexKey, unsigned int> > >&) const [with VertexKey = char, Vertex = bool]’:
prog.cpp:167:   instantiated from here
prog.cpp:133: warning: comparison between signed and unsigned integer expressions
stdout
copy 
VERTICES:
  a: 0
  b: 0
  c: 0
  d: 0
EDGES:
  a-b
  a-c
  b-c
  c-d
  d-a

a ->  b c
b ->  c
c ->  d
d ->  a
e -> 

a <- d 
b <- a 
c <- a b 
d <- c 
e <- 

BFS from a: 
  a: 0
  b: 1
  c: 1
  d: 2

BFS from b: 
  a: 3
  b: 0
  c: 1
  d: 2

BFS from c: 
  a: 2
  b: 3
  c: 0
  d: 1

BFS from d: 
  a: 1
  b: 2
  c: 2
  d: 0

BFS from e: 
  e: 0
https://ideone.com/XG1WD
language:
C++ (gcc 8.3)
created:
13 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!