fork(1) download
copy 
  1. #include <string>
  2.  
  3. // vertex header
  4.  
  5. class Vertex
  6. {
  7. public:
  8. 	Vertex(std::string name, int weight = 1);
  9.     virtual ~Vertex() = default;
  10.  
  11. 	const std::string& name() const { return _name; }
  12. 	int weight() const { return _weight; }
  13. protected:
  14. 	std::string _name;
  15. 	int         _weight;
  16. };
  17.  
  18. // vertex definitions
  19.  
  20. Vertex::Vertex(std::string name, int weight)
  21. 	: _name(std::move(name))
  22. 	, _weight(weight)
  23. {}
  24.  
  25. // graph header
  26.  
  27. #include <vector>
  28. #include <unordered_map>
  29.  
  30. class Graph
  31. {
  32. public:
  33. 	template<typename T>
  34. 	using VertexMap     = std::unordered_map<Vertex*, T>;
  35. 	using AdjacencyList = VertexMap<std::vector<Vertex*>>;
  36.  
  37. 	void addEdge(Vertex* u, Vertex* v);
  38.  
  39. 	std::vector<Vertex*> topoSort();
  40.  
  41. 	VertexMap<int> indegrees() const;
  42. 	int indegree(Vertex*) const;
  43.  
  44. 	const AdjacencyList& adjacencyList() const;
  45. protected:
  46. 	AdjacencyList _vertices;
  47. };
  48.  
  49. // graph definitions
  50.  
  51. void Graph::addEdge(Vertex* u, Vertex* v)
  52. {
  53. 	_vertices[v]; 				// initialise adjacency list for v
  54. 	_vertices[u].push_back(v);  // add v as being adjacent to u
  55. }
  56.  
  57. enum Colour { White, Grey, Black };
  58.  
  59. void topoSortVertex(Vertex* vertex,
  60. 					Colour& colour,
  61. 					const Graph::AdjacencyList& adjacencyList,
  62. 					Graph::VertexMap<Colour>& visited,
  63. 					std::vector<Vertex*>& sorted)
  64. {
  65. 	colour = Grey;
  66.  
  67. 	for (Vertex* neighbour : adjacencyList.at(vertex))
  68.     {
  69. 		Colour& neighbour_colour = visited[neighbour];
  70.         if (neighbour_colour == White)
  71.         {
  72.             topoSortVertex(neighbour, neighbour_colour, adjacencyList, visited, sorted);
  73.         }
  74.         else
  75.         if (neighbour_colour == Grey)
  76.         {
  77.         	throw std::runtime_error("cycle in graph");
  78.         }
  79.     }
  80.  
  81. 	colour = Black;
  82.     sorted.push_back(vertex);
  83. }
  84.  
  85. std::vector<Vertex*> Graph::topoSort()
  86. {
  87.     VertexMap<int> indegs = indegrees();
  88.  
  89.     std::vector<Vertex*> sorted;
  90.     sorted.reserve(indegs.size());
  91.  
  92.     VertexMap<Colour> visited;
  93.     visited.reserve(indegs.size());
  94.  
  95. 	for (auto& pair : indegs)
  96. 	{
  97. 		if (pair.second == 0) // vertex has indegree of 0
  98. 		{
  99. 			Vertex* vertex = pair.first;
  100. 			Colour& colour = visited[vertex];
  101. 			if (colour == White)
  102. 			{
  103. 				topoSortVertex(vertex, colour, _vertices, visited, sorted);
  104. 			}
  105. 		}
  106.     }
  107.  
  108. 	return sorted;
  109. }
  110.  
  111. Graph::VertexMap<int> Graph::indegrees() const
  112. {
  113. 	VertexMap<int> indegrees;
  114.  
  115.     for (auto& pair : _vertices)
  116.     {
  117.     	indegrees[pair.first]; // initialise indegree for this vertex
  118.     	for (Vertex* neighbour : pair.second)
  119.     	{
  120.     		++indegrees[neighbour];
  121.     	}
  122.     }
  123.  
  124.     return indegrees;
  125. }
  126.  
  127. int Graph::indegree(Vertex* v) const
  128. {
  129. 	return indegrees().at(v);
  130. }
  131.  
  132. const Graph::AdjacencyList& Graph::adjacencyList() const
  133. {
  134. 	return _vertices;
  135. }
  136.  
  137. // test
  138.  
  139. #include <iostream>
  140.  
  141. int main()
  142. {
  143. 	Graph g;
  144. 	Vertex v2  {  "2" };
  145. 	Vertex v3  {  "3" };
  146. 	Vertex v5  {  "5" };
  147. 	Vertex v7  {  "7" };
  148. 	Vertex v8  {  "8" };
  149. 	Vertex v9  {  "9" };
  150. 	Vertex v10 { "10" };
  151. 	Vertex v11 { "11" };
  152.  
  153. 	g.addEdge(&v7,  &v11);
  154. 	g.addEdge(&v7,  &v8);
  155. 	g.addEdge(&v5,  &v11);
  156. 	g.addEdge(&v3,  &v8);
  157. 	g.addEdge(&v3,  &v10);
  158. 	g.addEdge(&v8,  &v9);
  159. 	g.addEdge(&v11, &v9);
  160. 	g.addEdge(&v9,  &v2);
  161.  
  162. 	/*
  163. 	 *    3   7    5
  164. 	 *   / \ / \  /
  165. 	 * 10   8   11
  166. 	 *       \ /
  167. 	 *        9
  168. 	 *        |
  169. 	 *        2
  170. 	 */
  171.  
  172. 	std::cout << "adjacency list:\n";
  173.     for (auto& pair : g.adjacencyList())
  174.     {
  175.     	std::cout << pair.first->name() << ": ";
  176.         for (const Vertex* neighbour : pair.second)
  177.         	std::cout << neighbour->name() << ", ";
  178.         std::cout << '\n';
  179.     }
  180.  
  181. 	std::cout << "indegrees:\n";
  182.     for (auto& pair : g.indegrees())
  183.     	std::cout << pair.first->name() << ": " << pair.second << '\n';
  184.  
  185.     std::cout << "topoSort:\n";
  186.     for (Vertex* v : g.topoSort())
  187.     	std::cout << v->name() << ", ";
  188.     std::cout << '\n';
  189.  
  190. 	// add cycle
  191. 	g.addEdge(&v9, &v3);
  192. 	try
  193. 	{
  194. 		g.topoSort();
  195. 	}
  196. 	catch (const std::exception& e)
  197. 	{
  198. 		std::cerr << e.what() << std::endl;
  199. 	}
  200.  
  201. }
Success #stdin #stdout #stderr 0s 3284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
adjacency list:
2: 
9: 2, 
10: 
3: 8, 10, 
5: 11, 
8: 9, 
7: 11, 8, 
11: 9, 
indegrees:
7: 0
11: 2
5: 0
8: 2
3: 0
10: 1
9: 2
2: 1
topoSort:
2, 9, 11, 8, 7, 5, 10, 3,
stderr
copy 
cycle in graph
https://ideone.com/JObMRV
language:
C++14 (gcc 8.3)
created:
9 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!