BFS and DFS (Breadth First Search and Depth First Search)

Files

• frmgraphs.ui
• ui_frmgraphs.h
• frmgraphs.h/cpp
• graphwidget.h/cpp A widget to draw and handle graphs
• gnode.h/cpp Has the code to draw a node into the graph widget.
• gedge.h/cpp Has the code to draw a edge into the graph widget.
• graphs.h/cpp Has the basic Graph structure that will be used into the algorithms.
• afirstsearch.h/cpp Has the algorithms BFS, DFS, validation of Bipartiteness and validation of DAC.

Description

This section talks about the tow menus:

• Breadth First Search (BFS) and Depth First Search (DFS) for undirected graphs.
• Breadth First Search (BFS) and Depth First Search (DFS) for directed.

Both of them use the same files and algorithms to perform BFS and DFS (afirstsearch.h/cpp), which has the implementation of each algorithm, and (graphs.h), which handles the basic representation of the graph that each algorithm needs.

How to use

In any of both case (Directed or Undirected) you must create nodes and connect each them. These are the instructions for create and connect:

• Create: Double Click into the canvas space. Once the canvas space received the double click a new node, indexed from cero (0), will be created.
• Connect: To connect tow nodes, you must hold press the key Shift and make a single click over each of them nodes. If the Graph is directed, the sense of arrow will be the orden in which the nodes has been selected.
• Each node can be drop at any place into the canvas.

Once the Graph has been built, press the button Build Tree to execute the algorithm BFS or DFS.

• In the case of undirected graph, BFS add a Bipartiteness property validation.
• In the case of directed graph, it's possible to validate the Directed Acyclic Graph (ADG) propertie, checking over the option Check DAG Property.

The result of operation will be showed into the log section.

The Algorithm

BFS and DFS work with a .

BFS and Bipartiteness validation

This algorithm processes a Breath First Search, over a graph G and validate if it accomplish the Bipartiteness property. This algorithm use the next structures:

• queue<long> levelQueue structure used to handle each node in an order as they are discovered.
• vector<bool> discovey to check if a node has been discovered. Each index corresponds to node from the graph G.
• vector<int> parents to set the parent to which each node is owned. Each index corresponds to node from the graph G and its value has the Id of the Node Parent for this node. For the root node its value is -1.
• vector<int> layerByNode . This vector stores the Id of layer to which each node owned to.
• vector<bool> isOdd is used to check the Bipartiteness property. If one node has been register as odd node, in its vector position, it has a true value.

void AFirstSearch::BFS(long root, Graph &T, stringstream &steps, bool checkBipartitenes)
{
    queue<long> levelQueue;

    steps << "Tree BFS:" << endl;
    if(T.empty())
    {
        steps << "\tError: It's not possible to build a Tree from an empty Graphic." << endl;
        return;
    }

    vector<bool> discovey(T.countNodes(),false);
    vector<int> parents(T.countNodes(), -1);
    vector<int> layerByNode(T.countNodes(), -1);
    vector<bool> isOdd(T.countNodes(), false);

    T.disableAll();

    T[root].enable(true);
    levelQueue.push(root);
    discovey[root] = true;
    parents[root] = -1;
    layerByNode[root] = 0; //The root node is layer 0.
    isOdd[root] = true; //The fisrt node is Odd

    steps << "\tStart to build Tree with BFS, from node [" << root << "]" << endl;

    while(!levelQueue.empty())
    {
        long node = levelQueue.front();
        vector<std::pair<long,long>> adjNodes = T[node].getAdyacentNodes();
        levelQueue.pop();

        //Check childs
        for(std::pair<long,long> p : adjNodes )
        {
            long idNode_ = p.first;
            long idEdge_ = p.second;

            if(!discovey[idNode_])
            {
                steps << "\t\tNew Node [" << idNode_ << "] discovery from Node [" << node << "] with Edge (" <<  idEdge_ << ")" << endl;

                T[idNode_].enable(true);
                T(idEdge_).enable(true);
                parents[idNode_] = node;
                levelQueue.push(idNode_); //Add the node into the queue (Adding to one level upper)..
                discovey[idNode_] = true;

                layerByNode[idNode_] = layerByNode[node] + 1; //The new child discovered has a upper level.
                isOdd[idNode_] = !isOdd[node]; //The child must be the opposit of its parent (Odd or Even).
            }
            else 
            {
                if(!checkBipartitenes && isOdd[idNode_] == isOdd[node])
                    steps << "\t\t**The edge with nodes [" << idNode_ << "] and [" << node << "] are not allowing the Graph to comply with the Bipartiteness propertie.**" << endl;
            }
        }
    }
}

This algorithm has a runtime execution of O(|e| + |n|).

DFS

**
 * @brief AFirstSearch::DFS Is the main function which prepare al the parameters to invoke the recursive function DFS
 * @param root Node which the algorithm start to build the resulting tree.
 * @param G The Original graph.
 * @param T The resulting tree.
 * @param steps The log output.
 */
void AFirstSearch::DFS(long root, Graph &T, stringstream &steps)
{

    steps << "Tree DFS:" << endl;
    if(T.empty())
    {
        steps << "\tError: It's not possible to build a Tree from an empty Graphic." << endl;
        return;
    }

    T.disableAll();
    steps << "\tStart to build Tree with DFS, from node [" << root << "]" << endl;

    vector<short> explored(T.countNodes(),0);
    vector<int> parents(T.countNodes(),-1);

    DFS(root, explored, parents, T, steps); //recursive function to replace a stack structure, use the call stack

}

/**
 * @brief AFirstSearch::DFS this is the recursive function wich implement a Stak (Call Sctack) that is used to implement the
 * DFS algorithm instead a Stack structure.
 * @param root Node which the algorithm continue building the resulting tree.
 * @param explored Array of nodes which has been explored and haven't.
 * @param parents Array of nodes which are parents into the tree.
 * @param G The Original graph.
 * @param T The resulting tree.
 * @param steps The log output.
 */
void AFirstSearch::DFS(long root, vector<short>& explored, vector<int>& parents,
                       Graph &T, stringstream &steps )
{

    T[root].enable(true);
    explored[root] = 1; //explored

    steps << "\t\tNew Node [" << root << "] explored from Parent Node [" << parents[root] << "]" << endl;

    Node rv = T[root];
    vector<pair<long,long>>adj = rv.getAdyacentNodes();
    for(pair<long,long> vAd : adj)
    {
        int idNode_ = vAd.first;
        int idEdge_ = vAd.second;

        if(!explored[idNode_])
        {
            parents[idNode_] = root;
            DFS(idNode_, explored, parents, T, steps);
            T(idEdge_).enable(true);
        }
    }
}

DAG validation

This algorithm check if a Graph is an Directed Acyclic Graph. This algorithm uses the Basic Graph Structure to eliminate each node from the graph, each time that it is discovered, and get the amount of incoming adyacentes nodes. The algorithm is mounted over a recursive function and its steps are:

1. Find one node which has no adyacentes nodes. If there is no nodes without incoming adyacente nodes, the Graph doesn't met the DAG property and must return false..
2. Register the Node at the Topologic, a queue<long>
3. Remove the node from the Graph
4. If only remain one node, register it into the topologic and return true. In the other way, repeat the step 1.

/**
 * @brief AFirstSearch::checkDAG
 *
 * + The activeNode vector has Ids of each node which is active into the DGA's algorithm tree.
 * + The array incommingCount has the total node that are incomming to the node, each time that a node is removed it drecrease
 * the incommins count from its adjancents nodes.
 *
 * @param G
 * @param steps
 */
void AFirstSearch::checkDAG(Graph &G, stringstream &steps)
{
    steps << "Checking Directed Acyclic Graph (DGA) propertie:" << endl;

    queue<long> topologic;

    if(checkDAG(G,topologic,steps))
    {
        steps << "\tThis graph meets the DAG property and its topologyc founded is:" << endl
              << "\t\t[ ";
        while(!topologic.empty())
        {
            steps << topologic.front() << " ";
            topologic.pop();
        }
        steps << "]" << endl;
    }
    else
    {
        vector<long> vrtxs = G.NodeKeys();

        steps << "\tThis graph doesn´t meet the DAG property because has been found a cicle betwen nodes:" << endl
              << "\t\t[ ";

        for(long k : vrtxs)
            steps << k << " ";
        steps << "]" << endl;

        steps << "\tThis was the topologic that could be detected before found the cycle:" << endl
              << "\t\t[ ";
        while(!topologic.empty())
        {
            steps << topologic.front() << " ";
            topologic.pop();
        }
        steps << "]" << endl;
    }
}

bool AFirstSearch::checkDAG(graphs::Graph &G, queue<long>& topologic , std::stringstream &steps)
{
    vector<long> vrtxs = G.NodeKeys();  //retive all the node's key.

    //1.- find a Vertex without incoming nodes.
    for(size_t i=0; i < vrtxs.size(); i++)
    {
        if(G[vrtxs[i]].countNodesAdy(true) == 0)
        {
            topologic.push(vrtxs[i]);
            G.removeNode(vrtxs[i]);

            if(G.countNodes() > 0)
                return checkDAG(G,topologic,steps);
            else
                return true;
        }
    }

    return false;
}

References

• Algorithm Design, by Jon Kleinberg