Algorithms_in_C++  1.0.0
Set of algorithms implemented in C++.
CycleCheck Class Reference

Static Public Member Functions

static bool isCyclicDFS (Graph const &graph)
 
static bool isCyclicBFS (Graph const &graph)
 

Private Types

enum  nodeStates : uint8_t { not_visited = 0, in_stack, visited }
 

Static Private Member Functions

static bool isCyclicDFSHelper (AdjList const &adjList, std::vector< nodeStates > *state, unsigned int node)
 

Detailed Description

Check if a directed graph has a cycle or not.

This class provides 2 methods to check for cycle in a directed graph: isCyclicDFS & isCyclicBFS.

  • isCyclicDFS uses DFS traversal method to check for cycle in a graph.
  • isCyclidBFS used BFS traversal method to check for cycle in a graph.

Member Function Documentation

◆ isCyclicBFS()

static bool CycleCheck::isCyclicBFS ( Graph const &  graph)
inlinestatic

Check if a graph has cycle or not.

This function uses BFS to check if a graph is cyclic or not.

Parameters
graphwhich needs to be evaluated for the presence of cycle.
Returns
true if a cycle is detected, else false.
249  {
250  auto graphAjdList = graph.getAdjList();
251  auto vertices = graph.getVertices();
252 
253  std::vector<unsigned int> indegree(vertices, 0);
254  // Calculate the indegree i.e. the number of incident edges to the node.
255  for (auto const& list : graphAjdList) {
256  auto children = list.second;
257  for (auto const& child : children) {
258  indegree[child]++;
259  }
260  }
261 
262  std::queue<unsigned int> can_be_solved;
263  for (unsigned int node = 0; node < vertices; node++) {
264  // If a node doesn't have any input edges, then that node will
265  // definately not result in a cycle and can be visited safely.
266  if (!indegree[node]) {
267  can_be_solved.emplace(node);
268  }
269  }
270 
271  // Vertices that need to be traversed.
272  auto remain = vertices;
273  // While there are safe nodes that we can visit.
274  while (!can_be_solved.empty()) {
275  auto solved = can_be_solved.front();
276  // Visit the node.
277  can_be_solved.pop();
278  // Decrease number of nodes that need to be traversed.
279  remain--;
280 
281  // Visit all the children of the visited node.
282  auto it = graphAjdList.find(solved);
283  if (it != graphAjdList.end()) {
284  for (auto child : it->second) {
285  // Check if we can visited the node safely.
286  if (--indegree[child] == 0) {
287  // if node can be visited safely, then add that node to
288  // the visit queue.
289  can_be_solved.emplace(child);
290  }
291  }
292  }
293  }
294 
295  // If there are still nodes that we can't visit, then it means that
296  // there is a cycle and return true, else return false.
297  return !(remain == 0);
298  }
Here is the call graph for this function:

◆ isCyclicDFS()

static bool CycleCheck::isCyclicDFS ( Graph const &  graph)
inlinestatic

Driver function to check if a graph has a cycle.

This function uses DFS to check for cycle in the graph.

Parameters
graphwhich needs to be evaluated for the presence of cycle.
Returns
true if a cycle is detected, else false.

State of the node.

It is a vector of "nodeStates" which represents the state node is in. It can take only 3 values: "not_visited", "in_stack", and "visited".

Initially, all nodes are in "not_visited" state.

212  {
213  auto vertices = graph.getVertices();
214 
215  /** State of the node.
216  *
217  * It is a vector of "nodeStates" which represents the state node is in.
218  * It can take only 3 values: "not_visited", "in_stack", and "visited".
219  *
220  * Initially, all nodes are in "not_visited" state.
221  */
222  std::vector<nodeStates> state(vertices, not_visited);
223 
224  // Start visiting each node.
225  for (unsigned int node = 0; node < vertices; node++) {
226  // If a node is not visited, only then check for presence of cycle.
227  // There is no need to check for presence of cycle for a visited
228  // node as it has already been checked for presence of cycle.
229  if (state[node] == not_visited) {
230  // Check for cycle.
231  if (isCyclicDFSHelper(graph.getAdjList(), &state, node)) {
232  return true;
233  }
234  }
235  }
236 
237  // All nodes have been safely traversed, that means there is no cycle in
238  // the graph. Return false.
239  return false;
240  }
Here is the call graph for this function:

◆ isCyclicDFSHelper()

static bool CycleCheck::isCyclicDFSHelper ( AdjList const &  adjList,
std::vector< nodeStates > *  state,
unsigned int  node 
)
inlinestaticprivate

Helper function of "isCyclicDFS".

Parameters
adjListis the adjacency list representation of some graph.
stateis the state of the nodes of the graph.
nodeis the node being evaluated.
Returns
true if graph has a cycle, else false.
172  {
173  // Add node "in_stack" state.
174  (*state)[node] = in_stack;
175 
176  // If the node has children, then recursively visit all children of the
177  // node.
178  auto const it = adjList.find(node);
179  if (it != adjList.end()) {
180  for (auto child : it->second) {
181  // If state of child node is "not_visited", evaluate that child
182  // for presence of cycle.
183  auto state_of_child = (*state)[child];
184  if (state_of_child == not_visited) {
185  if (isCyclicDFSHelper(adjList, state, child)) {
186  return true;
187  }
188  } else if (state_of_child == in_stack) {
189  // If child node was "in_stack", then that means that there
190  // is a cycle in the graph. Return true for presence of the
191  // cycle.
192  return true;
193  }
194  }
195  }
196 
197  // Current node has been evaluated for the presence of cycle and had no
198  // cycle. Mark current node as "visited".
199  (*state)[node] = visited;
200  // Return that current node didn't result in any cycles.
201  return false;
202  }
Here is the call graph for this function:

The documentation for this class was generated from the following file:
std::vector< unsigned int >
std::queue::emplace
T emplace(T... args)
node
Definition: avltree.cpp:13
node
struct list node
std::queue
STL class.
std::queue::front
T front(T... args)
CycleCheck::isCyclicDFSHelper
static bool isCyclicDFSHelper(AdjList const &adjList, std::vector< nodeStates > *state, unsigned int node)
Definition: cycle_check_directed_graph.cpp:170
std::queue::pop
T pop(T... args)
graph
Graph algorithms.
std::queue::empty
T empty(T... args)
list
Definition: list_array.cpp:8