****************
Graph Algorithms
****************


Now we have the tools to see some graph algorithms. 


Topological Sort
================

*  A **topological sort** is an ordering of nodes in a directed acyclic graph.
*  If there is a path from :math:`v_i` to :math:`v_j`.
*  Then :math:`v_j` appears after :math:`v_i` in the ordering.

.. admonition:: Example
    :class: example
    
    *  Following an acyclic graph.

    .. figure:: ./img/acyclic_graph.png
        :align: center

    * An example of a topological ordering: :math:`v_1, v_2, v_5, v_4, v_7, v_3, v_6`.

.. admonition:: Activity
    :class: activity

    *  Give another topological ordering.

A Simple Algorithm
------------------

*  We define the indegree of a node :math:`v`, as the number of edges :math:`(u,v)`.
*  A simple algorithm to find topological ordering is:

   *  Find any vertex with an indegree of 0.
   *  Remove it along with its edges.
   *  Apply the strategy with another vertex.


*  We obtain the following pseudocode:

.. code-block:: java
    :linenos:

    void topsort()
    {
        for (int counter = 0; counter < NUM_VERTICES; counter++){
            Vertex v = findNewVertexOfIndegreeZero();
            if (v == NOT_A_VERTEX){
                throw CycleFoundException();
            }
            v.topNum = counter;
            for each Vertex w adjacent to v{
                w.indegree--;
            }
        }
    }

*  Where :code:`findNewVertexOfIndegreeZero()` scans the array of vertices looking for a vertex with indegree 0.
*  If it returns :code:`NOT_A_VERTEX` it indicates that the graph has a cycle.
*  The complexity of this algorithm :math:`O(|V|^2)`.


A Second Algorithm
------------------

*  The graph could be parsed, so checking each vertex could be a waste of time.
*  A second way to make a topological sort is to place every vertex of indegree 0 in a queue.
*  While the queue is not empty we remove one vertex.
*  All the adjacent vertices have their indegree decremented.


Following a pseudo-code of the algorithm:

.. code-block:: java
    :linenos:

    void topsort()
    {
        Queue<Vertex> q;
        int counter = 0;

        q.makeEmpty( );
        for each Vertex v
            if( v.indegree == 0 )
                q.enqueue( v );

        while( !q.isEmpty( ) )
        {
            Vertex v = q.dequeue( );
            v.topNum = ++counter; // Assign next number
            for each Vertex w adjacent to v
                if( --w.indegree == 0 )
                    q.enqueue( w );
        }

        if( counter != NUM_VERTICES )
            throw CycleFoundException();
    }


*  The running time of this algorithm is :math:`O(|E|+|V|)`.

.. admonition:: Activity
    :class: activity

    *  Can you explain the running time?
    *  Apply this algorithm to the previous graph.


Shortest-Path Algorithms
========================

*  There are different shortest-path algorithms.
*  But, they have common properties:

   *  The input is a weighted graph.
   *  The weight for each edge :math:`(v_i, v_j)` is a cost :math:`c_{i,j}` to traverse the edge.
   *  The cost of a path :math:`v_1v_2\dots v_N` is :math:`\sum_{i=1}^{N-1}c_{i,i+1}`.

.. figure:: ./img/bfs.drawio.png
    :align: center

|

.. admonition:: Activity
    :class: activity

    *  What would be the cost of the path in an unweighted graph?
    *  Consider the previous graph:

       * What is the cost of the path :math:`v_1, v_2, v_5, v_7`.
       * Do you have a shorter path from :math:`v_1` to :math:`v_7`?


Breadth-First Search
--------------------

*  Finding the shortest path in an unweighted graph is considering a weighted graph where all the edges have a cost of 1.
*  It is minimizing the number of edges in the path.
*  We will introduce a single source shortest-path algorithm for unweighted graph :math:`G = (V, E)`.

   *  Single source means that we calculate the shortest path from a specific node :math:`s \in V` to any other nodes :math:`v_k \in V`.

A very simple algorithm is **breadth-first search**.

The idea is to process nodes in layers.


.. admonition:: Example
    :class: example

    *  Consider the previous unweighted directed graph.
    *  We want to apply breadth first to find the shortest path from :math:`v_1` to :math:`v_6`.
    *  We obtain the following steps:
    
    .. figure:: ./img/bfs_01.drawio.png
        :align: center

    |

    We start with the first node :math:`v_1`.

    .. figure:: ./img/bfs_02.drawio.png
        :align: center
    
    |

    We check each arc leaving :math:`v_2`.

    .. figure:: ./img/bfs_03.drawio.png
        :align: center

    |

    We check each arc leaving :math:`v_4`.

    .. figure:: ./img/bfs_04.drawio.png
        :align: center

    |

    Finally, the arcs leaving :math:`v_3`.

    .. figure:: ./img/bfs_05.drawio.png
        :align: center

    |


.. admonition:: Activity
    :class: activity

    *  Apply the algorithm to find the shortest path from :math:`v_4` to :math:`v_1`.

Implementation
**************

*  First we create a table that will keep track of the algorithm progress.
*  The table will keep track for each node it was visited or marked.


The pseudo-code is given below:

.. code-block::

    function BFS(Graph, source):

        Create a queue Q.
        Q.insert(s).

        while Q not empty:
            u = Q.pop()
            visit(u)
            for all v adjacent to u:
                if v not marked or visited:
                    Mark v
                    Q.insert(v)

*  The complexity of this algorithm is :math:`O(|V|^2)`.

.. admonition:: Activity
    :class: activity

    *  Is the algorithm efficient?
    *  If not, how would you improve it?