fork download
copy 
  1. /**
  2.  * A graph where the nodes are integers, and an implementation of the 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. typedef set<uint> AdjacencyList;
  17. const uint MAXINT = 999999999u;
  18.  
  19. template <class Iterator> ostream& print (Iterator iFrom, Iterator iTo) {
  20. 	for (; iFrom!=iTo; ++iFrom) cout << *iFrom << " ";
  21. 	return (cout << endl);
  22. }
  23.  
  24. template <class T> ostream& operator<< (ostream& out, const vector<T>& theVector) {
  25. 	return print (theVector.begin(), theVector.end());
  26. }
  27.  
  28. template <class T> ostream& operator<< (ostream& out, const set<T>& theVector) {
  29. 	return print (theVector.begin(), theVector.end());
  30. }
  31.  
  32.  
  33.  
  34. /**
  35.  * A graph where the vertices are integers; stores edges in adjacency list.
  36.  */
  37. class IntegerGraph {
  38. 	vector<AdjacencyList> myVertices;
  39.  
  40. public:
  41. 	IntegerGraph (uint nVertices): myVertices(nVertices) {}
  42. 	uint size() const { return myVertices.size(); }
  43.  
  44. 	IntegerGraph& addEdge (uint iFrom, uint iTo) {
  45. 		if (iFrom >= size()) {
  46. 			throw string("trying to add an edge from a nonexisting vertex index");
  47. 		}
  48. 		if (iTo >= size()) {
  49. 			throw string("trying to add an edge to a nonexisting vertex index");
  50. 		}
  51. 		myVertices[iFrom].insert(iTo);
  52. 		return *this;
  53. 	}
  54.  
  55. 	void createClique() {     // for testing
  56. 		for (uint iFrom=0; iFrom<size(); ++iFrom) {
  57. 			for (uint iTo=0; iTo<size(); ++iTo) {
  58. 				if (iFrom!=iTo)
  59. 					addEdge(iFrom,iTo);
  60. 			}
  61. 		}
  62. 	}
  63.  
  64. 	void printOutgoingEdges(uint iFrom, ostream& out) const {
  65. 		out << iFrom << " -> ";
  66. 		const AdjacencyList& targets = myVertices[iFrom];
  67. 		AdjacencyList::const_iterator f;
  68. 		for (f=targets.begin(); f!=targets.end(); ++f) {
  69. 			out << " " << (*f);
  70. 		}
  71. 		out << endl;
  72. 	}
  73.  
  74. 	void printIncomingEdges(uint iTo, ostream& out) {
  75. 		out << iTo << " <- ";
  76. 		for (uint iFrom=0; iFrom<myVertices.size(); ++iFrom) {
  77. 			const AdjacencyList& currentTargets = myVertices[iFrom];
  78. 			if (currentTargets.count(iTo)) {
  79. 				out << iFrom << " ";
  80. 			}
  81. 		}
  82. 		out << endl;
  83. 	}
  84.  
  85. 	// Print the graph, using the vertex indices
  86. 	void printIndices(ostream& out) const {
  87. 		for (uint i=0; i<myVertices.size(); ++i)
  88. 			out << i << " -> " << myVertices[i];
  89. 	}
  90.  
  91. 	friend ostream& operator<< (ostream& out, const IntegerGraph& g) {
  92. 		g.printIndices(out);
  93. 		return out;
  94. 	}
  95.  
  96.  
  97. 	/// @see http://w...content-available-to-author-only...t.org/doc/libs/1_43_0/libs/graph/doc/breadth_first_search.html
  98. 	void breadth_first_search(uint source, vector<uint>& distances, vector<uint>& previous) const {
  99. 		typedef unsigned char color;
  100. 		const color white=0, gray=1, black=2;
  101.  
  102. 		vector<color> vertexColor(size());
  103. 		distances.resize(size());
  104. 		previous.resize(size());
  105. 		queue<uint> vertexQueue;
  106.  
  107. 		fill(vertexColor.begin(), vertexColor.end(), white);
  108. 		fill(distances.begin(), distances.end(), MAXINT);
  109. 		fill(previous.begin(), previous.end(), MAXINT);
  110.  
  111. 		// Initlaize source:
  112. 		vertexColor[source] = gray;
  113. 		distances[source] = 0;
  114. 		previous[source] = MAXINT;
  115. 		vertexQueue.push(source);
  116.  
  117. 		// Loop over all vertices:
  118. 		while (!vertexQueue.empty()) {
  119. 			uint current = vertexQueue.front();     // finish a vertex
  120. 			vertexQueue.pop();
  121. 			uint current_distance = distances[current];
  122.  
  123. 			// Loop over all outgoing edges of the current vertex:
  124. 			const AdjacencyList& nextTargets = myVertices[current];
  125. 			AdjacencyList::const_iterator iNeighbour;
  126. 			for (iNeighbour=nextTargets.begin(); iNeighbour!=nextTargets.end(); ++iNeighbour) {
  127. 				uint neighbour = *iNeighbour;
  128. 				if (vertexColor[neighbour]==white) {   // a tree edge
  129. 					vertexColor[neighbour] = gray;
  130. 					distances[neighbour] = current_distance+1;
  131. 					previous[neighbour] = current;
  132. 					vertexQueue.push(neighbour);
  133. 				}
  134. 			}
  135. 			vertexColor[current] = black;   // finish a vertex
  136. 		}
  137. 	}
  138.  
  139.  
  140. 	void print_bfs_from(uint iFrom) {
  141. 		vector<uint> distances, previous;
  142. 		breadth_first_search(iFrom, distances, previous);
  143. 		cout << "BFS from " << iFrom << ": " << endl << "distances: " << distances << "previouses: " << previous << endl;
  144. 	}
  145. }; // end of class IntegerGraph
  146.  
  147.  
  148. int main() {
  149. 	IntegerGraph g(5);
  150. 	g.addEdge(0,1).addEdge(1,2).addEdge(2,3).addEdge(3,0).addEdge(0,2);
  151. 	cout << g << endl;
  152. 	g.printOutgoingEdges(0,cout);
  153. 	g.printOutgoingEdges(1,cout);
  154. 	g.printOutgoingEdges(2,cout);
  155. 	g.printOutgoingEdges(3,cout);
  156. 	g.printOutgoingEdges(4,cout);
  157. 	cout << endl;
  158. 	g.printIncomingEdges(0,cout);
  159. 	g.printIncomingEdges(1,cout);
  160. 	g.printIncomingEdges(2,cout);
  161. 	g.printIncomingEdges(3,cout);
  162. 	g.printIncomingEdges(4,cout);
  163. 	cout << endl;
  164.  
  165. 	g.print_bfs_from(0);
  166. 	g.print_bfs_from(1);
  167. 	g.print_bfs_from(2);
  168. 	g.print_bfs_from(3);
  169. 	g.print_bfs_from(4);
  170. }
  171.  
Success #stdin #stdout 0s 2868KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 -> 1 2 
1 -> 2 
2 -> 3 
3 -> 0 
4 -> 

0 ->  1 2
1 ->  2
2 ->  3
3 ->  0
4 -> 

0 <- 3 
1 <- 0 
2 <- 0 1 
3 <- 2 
4 <- 

BFS from 0: 
distances: 0 1 1 2 999999999 
previouses: 999999999 0 0 2 999999999 

BFS from 1: 
distances: 3 0 1 2 999999999 
previouses: 3 999999999 1 2 999999999 

BFS from 2: 
distances: 2 3 0 1 999999999 
previouses: 3 0 999999999 2 999999999 

BFS from 3: 
distances: 1 2 2 0 999999999 
previouses: 3 0 0 999999999 999999999 

BFS from 4: 
distances: 999999999 999999999 999999999 999999999 0 
previouses: 999999999 999999999 999999999 999999999 999999999
https://ideone.com/ocFRt
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!