fork download
copy 
  1. #include <iostream>
  2. #include <sstream>
  3. #include <string>
  4. #include <cassert>
  5. #include <map>
  6. #include <set>
  7. #include <list>
  8. #include <queue>
  9. #include <stack>
  10.  
  11. namespace Graph
  12. {
  13.  
  14. template<typename T>
  15. class AdjacencyList
  16. {
  17. public:
  18. 	AdjacencyList(std::istringstream & _ss, const T & _default_val, const bool _directed = false) :
  19. 		m_list(), m_val(), m_default_value(_default_val), directed(_directed)
  20. 	{
  21. 		using namespace std;
  22. 		string edge;
  23. 		while(getline(_ss, edge, ';'))
  24. 		{
  25. 			istringstream ss_edge(edge);
  26. 			string vertex_from;
  27. 			getline(ss_edge, vertex_from, ',');
  28. 			istringstream ss_vertex_from(vertex_from);
  29. 			int from, to;
  30. 			ss_vertex_from >> from;
  31. 			ss_edge >> to;
  32. 			Add(from, to);
  33. 			m_val[from] = m_default_value;
  34. 			m_val[to] = m_default_value;
  35. 		}
  36. 	}
  37.  
  38. 	virtual ~AdjacencyList()
  39. 	{
  40. 	}
  41.  
  42. 	virtual bool Adjacent(int _x, int _y) const
  43. 	{
  44. 		std::map<int, std::set<int> >::const_iterator it = m_list.find(_x);
  45. 		return (it->second.find(_y) != it->second.end());
  46. 	}
  47.  
  48. 	virtual std::set<int> Neighbours(const int _x) const
  49. 	{
  50. 		std::set<int> s;
  51. 		std::map<int, std::set<int> >::const_iterator it = m_list.find(_x);
  52. 		if (it != m_list.end())
  53. 		{
  54. 			s = m_list.find(_x)->second;
  55. 		}
  56. 		return s;
  57. 	}
  58.  
  59. 	virtual std::set<int> Parents(const int _x) const
  60. 	{
  61. 		using namespace std;
  62. 		set<int> parents;
  63. 		for (map<int, set<int> >::const_iterator it = m_list.begin(); it != m_list.end(); ++it)
  64. 		{
  65. 			if (it->second.find(_x) != it->second.end())
  66. 			{
  67. 				parents.insert(it->first);
  68. 			}
  69. 		}
  70. 		return parents;
  71. 	}
  72.  
  73. 	virtual bool Add(const int _x, const int _y)
  74. 	{
  75. 		std::pair<std::set<int>::iterator, bool> ret = m_list[_x].insert(_y);
  76. 		if (directed)
  77. 		{
  78. 			if (m_list.count(_y) == 0)
  79. 			{
  80. 				m_list[_y].clear(); // Initialize with empty set
  81. 			}
  82. 		}
  83. 		else
  84. 		{
  85. 			m_list[_y].insert(_x);
  86. 		}
  87. 		return ret.second;
  88. 	}
  89.  
  90. 	virtual bool Delete(const int _x, const int _y)
  91. 	{
  92. 		m_list[_x].erase(_y);
  93. 		return (m_list[_y].erase(_x) == 1 ? true : false);
  94. 	}
  95.  
  96. 	virtual T GetValue(const int _x) const
  97. 	{
  98. 		typename std::map<int, T>::const_iterator it = m_val.find(_x);
  99. 		if (it == m_val.end())
  100. 		{
  101. 			return m_default_value;
  102. 		}
  103. 		return it->second;
  104. 	}
  105.  
  106. 	virtual void SetValue(int _x, const T & _val)
  107. 	{
  108. 		m_val[_x] = _val;
  109. 	}
  110.  
  111. 	virtual void PrintBFS(const int _x) const
  112. 	{
  113. 		using namespace std;
  114. 		if (m_list.find(_x) == m_list.end())
  115. 		{
  116. 			cout << _x << " not a vertex\n";
  117. 			return;
  118. 		}
  119. 		queue<int> q;
  120. 		set<int> visited;
  121. 		q.push(_x);
  122. 		size_t curr_level = 1;
  123. 		bool print_newline = false;
  124. 		while (!q.empty())
  125. 		{
  126. 			int vertex = q.front();
  127. 			q.pop();
  128. 			if (visited.find(vertex) == visited.end())
  129. 			{
  130. 				visited.insert(vertex);
  131. 				cout << vertex << ", ";
  132. 				set<int> n = Neighbours(vertex);
  133. 				for (set<int>::const_iterator it = n.begin(); it != n.end(); ++it)
  134. 				{
  135. 					q.push(*it);
  136. 				}
  137. 				print_newline = true;
  138. 			}
  139. 			--curr_level;
  140. 			if (curr_level == 0)
  141. 			{
  142. 				cout << (print_newline ? "\n" : "");
  143. 				curr_level = q.size();
  144. 				print_newline = false;
  145. 			}
  146. 		}
  147. 	}
  148.  
  149. 	virtual void PrintDFS(const int _x) const
  150. 	{
  151. 		using namespace std;
  152. 		if (m_list.find(_x) == m_list.end())
  153. 		{
  154. 			cout << _x << " not a vertex\n";
  155. 			return;
  156. 		}
  157. 		stack<int> s;
  158. 		set<int> visited;
  159. 		s.push(_x);
  160. 		while (!s.empty())
  161. 		{
  162. 			int vertex = s.top();
  163. 			s.pop();
  164. 			if (visited.find(vertex) == visited.end())
  165. 			{
  166. 				visited.insert(vertex);
  167. 				cout << vertex << ", ";
  168. 				set<int> n = Neighbours(vertex);
  169. 				for (set<int>::const_iterator it = n.begin(); it != n.end(); ++it)
  170. 				{
  171. 					s.push(*it);
  172. 				}
  173. 			}
  174. 		}
  175. 		cout << "\n";
  176. 	}
  177.  
  178. private:
  179. 	std::map< int, std::set<int> > m_list;
  180. 	std::map< int, T > m_val; // Use set instead of list because set is
  181. 	                          // implemented as a bst -> better performance in
  182. 	                          // search and use iterators to iterate
  183. 	T m_default_value;
  184. 	bool directed;
  185. };
  186.  
  187. }
  188.  
  189. using namespace std;
  190.  
  191. template<typename T>
  192. void list_neighbours(const Graph::AdjacencyList<T> & _adjlist, const int _vertex)
  193. {
  194. 	set<int> n = _adjlist.Neighbours(_vertex);
  195. 	cout << _vertex << "->";
  196. 	for (set<int>::const_iterator it = n.begin(); it != n.end(); ++it)
  197. 	{
  198. 		cout << *it << ", ";
  199. 	}
  200. 	cout << "\n";
  201. }
  202.  
  203. int main(int argc, char **argv)
  204. {
  205. 	/**
  206. 	 * K(3,4) graph
  207. 	 */
  208. 	istringstream ss("1,4;1,5;1,6;1,7;2,4;2,5;2,6;2,7;3,4;3,5;3,6;3,7;");
  209. 	const char default_val = ' ';
  210. 	Graph::AdjacencyList<char> adjlist(ss, default_val);
  211.  
  212. 	assert(!adjlist.Adjacent(0, 10));
  213.  
  214. 	assert(!adjlist.Adjacent(1, 0));
  215. 	assert(!adjlist.Adjacent(1, 1));
  216. 	assert(!adjlist.Adjacent(1, 2));
  217. 	assert(!adjlist.Adjacent(1, 3));
  218. 	assert(adjlist.Adjacent(1, 4));
  219. 	assert(adjlist.Adjacent(1, 5));
  220. 	assert(adjlist.Adjacent(1, 6));
  221. 	assert(adjlist.Adjacent(1, 7));
  222. 	assert(!adjlist.Adjacent(1, 8));
  223.  
  224. 	assert(!adjlist.Adjacent(2, 0));
  225. 	assert(!adjlist.Adjacent(2, 1));
  226. 	assert(!adjlist.Adjacent(2, 2));
  227. 	assert(!adjlist.Adjacent(2, 3));
  228. 	assert(adjlist.Adjacent(2, 4));
  229. 	assert(adjlist.Adjacent(2, 5));
  230. 	assert(adjlist.Adjacent(2, 6));
  231. 	assert(adjlist.Adjacent(2, 7));
  232. 	assert(!adjlist.Adjacent(2, 8));
  233.  
  234. 	assert(!adjlist.Adjacent(3, 0));
  235. 	assert(!adjlist.Adjacent(3, 1));
  236. 	assert(!adjlist.Adjacent(3, 2));
  237. 	assert(!adjlist.Adjacent(3, 3));
  238. 	assert(adjlist.Adjacent(3, 4));
  239. 	assert(adjlist.Adjacent(3, 5));
  240. 	assert(adjlist.Adjacent(3, 6));
  241. 	assert(adjlist.Adjacent(3, 7));
  242. 	assert(!adjlist.Adjacent(3, 8));
  243.  
  244. 	assert(adjlist.Neighbours(1).size() == adjlist.Parents(1).size());
  245. 	list_neighbours(adjlist, 1);
  246. 	assert(adjlist.Neighbours(2).size() == adjlist.Parents(2).size());
  247. 	list_neighbours(adjlist, 2);
  248. 	assert(adjlist.Neighbours(3).size() == adjlist.Parents(3).size());
  249. 	list_neighbours(adjlist, 3);
  250. 	assert(adjlist.Neighbours(4).size() == adjlist.Parents(4).size());
  251. 	list_neighbours(adjlist, 4);
  252. 	assert(adjlist.Neighbours(5).size() == adjlist.Parents(5).size());
  253. 	list_neighbours(adjlist, 5);
  254. 	assert(adjlist.Neighbours(6).size() == adjlist.Parents(6).size());
  255. 	list_neighbours(adjlist, 6);
  256. 	assert(adjlist.Neighbours(7).size() == adjlist.Parents(7).size());
  257. 	list_neighbours(adjlist, 7);
  258.  
  259. 	assert(adjlist.Neighbours(8).size() == 0);
  260. 	assert(adjlist.Parents(8).size() == 0);
  261.  
  262. 	assert(adjlist.Add(2, 8));
  263. 	assert(!adjlist.Add(8, 2));
  264. 	assert(adjlist.Adjacent(2, 8));
  265. 	assert(adjlist.Adjacent(8, 2));
  266. 	assert(!adjlist.Adjacent(8, 3));
  267. 	list_neighbours(adjlist, 2);
  268. 	list_neighbours(adjlist, 8);
  269. 	adjlist.Delete(2, 8);
  270. 	list_neighbours(adjlist, 2);
  271. 	list_neighbours(adjlist, 8);
  272. 	assert(!adjlist.Adjacent(2, 8));
  273. 	assert(!adjlist.Adjacent(8, 2));
  274. 	assert(adjlist.GetValue(4) == ' ');
  275. 	adjlist.SetValue(4, 'f');
  276. 	assert(adjlist.GetValue(4) == 'f');
  277. 	cout << "BFS: ";
  278. 	adjlist.PrintBFS(6);
  279. 	cout << "DFS: ";
  280. 	adjlist.PrintDFS(6);
  281. 	cout << "\n";
  282.  
  283. 	/**
  284. 	 * This graph:
  285. 	 * https://e...content-available-to-author-only...a.org/wiki/File:Directed_acyclic_graph.png
  286. 	 */
  287. 	istringstream ss2("7,11;7,8;5,11;3,8;3,10;11,2;11,9;11,10;8,9;");
  288. 	Graph::AdjacencyList<char> adjlist2(ss2, default_val, true);
  289. 	assert(adjlist2.Neighbours(7).size() == 2 && adjlist2.Parents(7).size() == 0);
  290. 	assert(adjlist2.Neighbours(5).size() == 1 && adjlist2.Parents(5).size() == 0);
  291. 	assert(adjlist2.Neighbours(3).size() == 2 && adjlist2.Parents(3).size() == 0);
  292. 	assert(adjlist2.Neighbours(11).size() == 3 && adjlist2.Parents(11).size() == 2);
  293. 	assert(adjlist2.Neighbours(8).size() == 1 && adjlist2.Parents(8).size() == 2);
  294. 	assert(adjlist2.Neighbours(2).size() == 0 && adjlist2.Parents(2).size() == 1);
  295. 	assert(adjlist2.Neighbours(9).size() == 0 && adjlist2.Parents(9).size() == 2);
  296. 	assert(adjlist2.Neighbours(10).size() == 0 && adjlist2.Parents(10).size() == 2);
  297. 	list_neighbours(adjlist2, 7);
  298. 	list_neighbours(adjlist2, 5);
  299. 	list_neighbours(adjlist2, 3);
  300. 	list_neighbours(adjlist2, 11);
  301. 	list_neighbours(adjlist2, 8);
  302. 	list_neighbours(adjlist2, 2);
  303. 	list_neighbours(adjlist2, 9);
  304. 	list_neighbours(adjlist2, 10);
  305. 	cout << "BFS: ";
  306. 	adjlist2.PrintBFS(7);
  307. 	cout << "DFS: ";
  308. 	adjlist2.PrintDFS(7);
  309. 	cout << "\n";
  310.  
  311. 	return 0;
  312. }
  313.  
Success #stdin #stdout 0s 3452KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1->4, 5, 6, 7, 
2->4, 5, 6, 7, 
3->4, 5, 6, 7, 
4->1, 2, 3, 
5->1, 2, 3, 
6->1, 2, 3, 
7->1, 2, 3, 
2->4, 5, 6, 7, 8, 
8->2, 
2->4, 5, 6, 7, 
8->
BFS: 6, 
1, 2, 3, 
4, 5, 7, 
DFS: 6, 3, 7, 2, 5, 1, 4, 

7->8, 11, 
5->11, 
3->8, 10, 
11->2, 9, 10, 
8->9, 
2->
9->
10->
BFS: 7, 
8, 11, 
9, 2, 10, 
DFS: 7, 11, 10, 9, 2, 8,
https://ideone.com/9D7Yty
Implementation of a graph as adjacency list using stl.
language:
C++14 (gcc 8.3)
created:
10 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!