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 Enumeration Documentation

nodeStates

enum CycleCheck::nodeStates : uint8_t

private

: uint8_t { not_visited = 0, in_stack, visited };

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

graph

which needs to be evaluated for the presence of cycle.

Returns

true if a cycle is detected, else false.

                                                {
        auto graphAjdList = graph.getAdjList();
        auto vertices = graph.getVertices();
 
        std::vector<unsigned int> indegree(vertices, 0);
        // Calculate the indegree i.e. the number of incident edges to the node.
        for (auto const& list : graphAjdList) {
            auto children = list.second;
            for (auto const& child : children) {
                indegree[child]++;
            }
        }
 
        std::queue<unsigned int> can_be_solved;
        for (unsigned int node = 0; node < vertices; node++) {
            // If a node doesn't have any input edges, then that node will
            // definately not result in a cycle and can be visited safely.
            if (!indegree[node]) {
                can_be_solved.emplace(node);
            }
        }
 
        // Vertices that need to be traversed.
        auto remain = vertices;
        // While there are safe nodes that we can visit.
        while (!can_be_solved.empty()) {
            auto solved = can_be_solved.front();
            // Visit the node.
            can_be_solved.pop();
            // Decrease number of nodes that need to be traversed.
            remain--;
 
            // Visit all the children of the visited node.
            auto it = graphAjdList.find(solved);
            if (it != graphAjdList.end()) {
                for (auto child : it->second) {
                    // Check if we can visited the node safely.
                    if (--indegree[child] == 0) {
                        // if node can be visited safely, then add that node to
                        // the visit queue.
                        can_be_solved.emplace(child);
                    }
                }
            }
        }
 
        // If there are still nodes that we can't visit, then it means that
        // there is a cycle and return true, else return false.
        return !(remain == 0);
    }

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

graph

which 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.

                                                {
        auto vertices = graph.getVertices();
 
        /** 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.
         */
        std::vector<nodeStates> state(vertices, not_visited);
 
        // Start visiting each node.
        for (unsigned int node = 0; node < vertices; node++) {
            // If a node is not visited, only then check for presence of cycle.
            // There is no need to check for presence of cycle for a visited
            // node as it has already been checked for presence of cycle.
            if (state[node] == not_visited) {
                // Check for cycle.
                if (isCyclicDFSHelper(graph.getAdjList(), &state, node)) {
                    return true;
                }
            }
        }
 
        // All nodes have been safely traversed, that means there is no cycle in
        // the graph. Return false.
        return false;
    }

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

adjList	is the adjacency list representation of some graph.
state	is the state of the nodes of the graph.
node	is the node being evaluated.

Returns

true if graph has a cycle, else false.

                                                     {
        // Add node "in_stack" state.
        (*state)[node] = in_stack;
 
        // If the node has children, then recursively visit all children of the
        // node.
        auto const it = adjList.find(node);
        if (it != adjList.end()) {
            for (auto child : it->second) {
                // If state of child node is "not_visited", evaluate that child
                // for presence of cycle.
                auto state_of_child = (*state)[child];
                if (state_of_child == not_visited) {
                    if (isCyclicDFSHelper(adjList, state, child)) {
                        return true;
                    }
                } else if (state_of_child == in_stack) {
                    // If child node was "in_stack", then that means that there
                    // is a cycle in the graph. Return true for presence of the
                    // cycle.
                    return true;
                }
            }
        }
 
        // Current node has been evaluated for the presence of cycle and had no
        // cycle. Mark current node as "visited".
        (*state)[node] = visited;
        // Return that current node didn't result in any cycles.
        return false;
    }

Here is the call graph for this function:

---

The documentation for this class was generated from the following file:

• graph/cycle_check_directed_graph.cpp