• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Cycle Detection

arsovski Jan 21st, 2020 74 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include<iostream>
2. #include<vector>
3. #include<list>
4. #include <queue>
5. // INPUTS:
6. //    7
7. //    8
8. //
9. //    0 1 1
10. //    1 1 2
11. //    0 1 2
12. //    1 1 3
13. //    2 1 4
14. //    3 1 4
15. //    4 1 5
16. //    5 1 6
17.
18.
19. //Cycle Detection Input
20. //    7
21. //    8
22. //
23. //    0 1 1
24. //    1 1 2
25. //    2 1 0
26. //    1 1 3
27. //    2 1 4
28. //    3 1 4
29. //    4 1 5
30. //    5 1 6
31.
32.
33.
34. struct Vertex
35. {
36.     int weight;
37.     int vertex_number;
38.
39.     Vertex(int weight, int vertex_number)
40.     {
41.         this->weight = weight;
42.         this->vertex_number = vertex_number;
43.     }
44. };
45.
46.
47. //undirected weight graph
48. std::vector<std::list<Vertex>> graph;
49.
50. //TODO make bfs and dfs
51.
52. bool connection_exists(int from, int to)
53. {
54.     for (auto element : graph[from])
55.     {
56.         if (element.vertex_number == to)
57.         {
58.             return true;
59.         }
60.     }
61.
62.     return false;
63. }
64.
65. void add_connection(int from, int weight, int to)
66. {
67.     if (!connection_exists(from, to))
68.     {
69.         graph[from].push_back({ weight, to });
70.         //graph[to].push_back({ weight, from });
71.     }
72. }
73.
74. void print_graph()
75. {
76.     for (int i = 0; i < graph.size(); i++)
77.     {
78.         std::cout << "Vertex " << i << ": ";
79.
80.         for (auto element : graph[i])
81.         {
82.             std::cout << element.vertex_number << "->" << element.weight << " ";
83.         }
84.
85.         std::cout << std::endl;
86.     }
87. }
88.
89.
90. std::vector<bool> visited;
91.
92. void bfs(int from)
93. {
94.     std::queue<int> next_to_process;
95.     next_to_process.push(from);
96.
97.     while (!next_to_process.empty())
98.     {
99.         int next_index = next_to_process.front();
100.         next_to_process.pop();
101.         visited[next_index] = true;
102.
103.         std::cout << next_index << " ";
104.
105.         for (auto neighbor : graph[next_index])
106.         {
107.             if (!visited[neighbor.vertex_number])
108.             {
109.                 visited[neighbor.vertex_number] = true;
110.                 next_to_process.push(neighbor.vertex_number);
111.             }
112.         }
113.     }
114.
115.     std::cout << std::endl;
116. }
117.
118.
119. std::vector<bool> visited_dfs;
120.
121. void dfs(int from)
122. {
123.     std::cout << from << " ";
124.     visited_dfs[from] = true;
125.
126.     for (auto neighbor : graph[from])
127.     {
128.         if (!visited_dfs[neighbor.vertex_number])
129.         {
130.             visited_dfs[neighbor.vertex_number] = true;
131.             dfs(neighbor.vertex_number);
132.         }
133.     }
134. }
135.
136. std::vector<bool> visited_topo;
137. std::list<int>  ordered_nodes;
138.
139. //DFS na svi nodes
140. void _recursive_topological(int from)
141. {
142.     visited_topo[from] = true;
143.
144.     //go through neighbors
145.     for (auto element : graph[from])
146.     {
147.         if (!visited_topo[element.vertex_number])
148.         {
149.             visited_topo[element.vertex_number] = true;
150.             _recursive_topological(element.vertex_number);
151.         }
152.     }
153.
154.
155.     ordered_nodes.push_back(from);
156.
157.
158. }
159.
160. void topological_sort()
161. {
162.     for (int i = 0; i < graph.size(); i++)
163.     {
164.         if (!visited_topo[i])
165.             _recursive_topological(i);
166.     }
167.
168.     ordered_nodes.reverse();
169.
170.     for (auto element : ordered_nodes)
171.     {
172.         std::cout << element << " ";
173.     }
174.
175.     std::cout << std::endl;
176.
177. }
178.
179. std::vector<char> detected_nodes;
180. void _detect_cycle(int from,bool& has_cycle)
181. {
182.     detected_nodes[from] = 'o';
183.
184.     if (has_cycle)
185.         return;
186.
187.     for(auto element : graph[from])
188.     {
189.         if(detected_nodes[element.vertex_number] == 'u')
190.         {
191.             _detect_cycle(element.vertex_number,has_cycle);
192.         }
193.         else if(detected_nodes[element.vertex_number] =='o')
194.         {
195.             has_cycle = true;
196.             return;
197.         }
198.     }
199.
200.     detected_nodes[from] = 'c';
201. }
202.
203. void cycle_detection()
204. {
205.     bool has_cycle = false;
206.
207.     for(int i=0;i<graph.size();i++)
208.     {
209.         if(detected_nodes[i] == 'u')
210.         {
211.             _detect_cycle(i,has_cycle);
212.         }
213.     }
214.
215.     if(has_cycle)
216.     {
217.         std::cout << "Cycle detected " << std::endl;
218.     }
219.     else
220.     {
221.         std::cout<<"No cycle detected "<<std::endl;
222.     }
223. }
224.
225.
226. int main()
227. {
228.     int nodes, edges;
229.     std::cin >> nodes >> edges;
230.
231.     graph.resize(nodes);
232.     visited_dfs.resize(nodes, false);
233.     visited.resize(nodes, false);
234.     visited_topo.resize(nodes, false);
235.     detected_nodes.resize(nodes, 'u');
236.     for (int i = 0; i < edges; i++)
237.     {
238.         int from, weight, to;
239.         std::cin >> from >> weight >> to;
240.         add_connection(from, weight, to);
241.     }
242.
243.
244.     //print_graph();
245.
246.     //dfs(6);
247.     std::cout << std::endl;
248.
249.     //bfs(6);
250.
251.
252.     //topological_sort();
253.
254.     cycle_detection();
255.
256.     return 0;
257. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.
Top