Digraphs

 A directed graph (or digraph) is a set of vertices and a collection of directed edges that each connects an ordered pair of vertices. We say that a directed edge points from the first vertex in the pair and points to the second vertex in the pair. We use the names 0 through V-1 for the vertices in a V-vertex graph.

 

Digraph

 

 

Glossary.

 Here are some definitions that we use.

  • self-loop is an edge that connects a vertex to itself.
  • Two edges are parallel if they connect the same ordered pair of vertices.
  • The outdegree of a vertex is the number of edges pointing from it. The indegree of a vertex is the number of edges pointing to it.
  • subgraph is a subset of a digraph's edges (and associated vertices) that constitutes a digraph.
  • directed path in a digraph is a sequence of vertices in which there is a (directed) edge pointing from each vertex in the sequence to its successor in the sequence. A simple path is one with no repeated vertices.
  • directed cycle is a directed path (with at least one edge) whose first and last vertices are the same. A simple cycle is a cycle with no repeated edges or vertices (except the requisite repetition of the first and last vertices).
  • The length of a path or a cycle is its number of edges.
  • We say that a vertex w is reachable from a vertex v if there exists a directed path from v to w.
  • We say that two vertices v and w are strongly connected if they are mutually reachable: there is a directed path from v to w and a directed path from w to v.
  • A digraph is strongly connected if there is a directed path from every vertex to every other vertex.
  • A digraph that is not strongly connected consists of a set of strongly-connected components, which are maximal strongly-connected subgraphs.
  • directed acyclic graph (or DAG) is a digraph with no directed cycles.

 

Anatomy of a Graph     A digraph and its strong components

 

 

Digraph graph data type.

 We implement the following digraph API.

 

Digraph API

The key method adj() allows client code to iterate through the vertices adjacent from a given vertex.

We prepare the test data tinyDG.txt and tinyDAG.txt using the following input file format.

 

Digraph input format

 

Graph representation.

 We use the adjacency-lists representation, where we maintain a vertex-indexed array of lists of the vertices connected by an edge to each vertex.

 

Adjacency-lists
representation of an undirected graph

Digraph.java implements the digraph API using the adjacency-lists representation. AdjMatrixDigraph.java implements the same API using the adjacency-matrix representation.

 

Reachability in digraphs.

 Depth-first search and breadth-first search are fundamentally digraph-processing algorithms.

 

  • Single-source reachability: Given a digraph and source s, is there a directed path from s to v? If so, find such a path. DirectedDFS.java uses depth-first search to solve this problem.

     

  • Multiple-source reachability: Given a digraph and a set of source vertices, is there a directed path from any vertex in the set to v? DirectedDFS.java uses depth-first search to solve this problem.

     

  • Single-source directed paths: given a digraph and source s, is there a directed path from s to v? If so, find such a path. DepthFirstDirectedPaths.java uses depth-first search to solve this problem.

     

  • Single-source shortest directed paths: given a digraph and source s, is there a directed path from s to v? If so, find a shortest such path. BreadthFirstDirectedPaths.java uses breadth-first search to solve this problem.

 

Cycles and DAGs.

 Directed cycles are of particular importance in applications that involve processing digraphs.

 

DAG

 

 

  • Directed cycle detection: does a given digraph have a directed cycle? If so, find such a cycle. DirectedCycle.java solves this problem using depth-first search.

     

  • Depth-first orders: Depth-first search search visits each vertex exactly once. Three vertex orderings are of interest in typical applications:

     

    • Preorder: Put the vertex on a queue before the recursive calls.

       

    • Postorder: Put the vertex on a queue after the recursive calls.

       

    • Reverse postorder: Put the vertex on a stack after the recursive calls.

    DepthFirstOrder.java computes these orders.

     

    Preorder, postorder, and reverse postorder

     

  • Topological sort: given a digraph, put the vertices in order such that all its directed edges point from a vertex earlier in the order to a vertex later in the order (or report that doing so is not possible). Topological.java solves this problem using depth-first search. Remarkably, a reverse postorder in a DAG provides a topological order.

     

    Topologial sort

     

 

Proposition.

 A digraph has a topological order if and only if it is a DAG.

 

Proposition.

 Reverse postorder in a DAG is a topological sort.

 

Proposition.

 With depth-first search, we can topologically sort a DAG in time proportional to V + E.

 

Strong connectivity.

 Strong connectivity is an equivalence relation on the set of vertices:

 

  • Reflexive: Every vertex v is strongly connected to itself.

     

  • Symmetric: If v is strongly connected to w, then w is strongly connected to v.

     

  • Transitive: If v is strongly connected to w and w is strongly connected to x, then v is also strongly connected to x.

Strong connectivity partitions the vertices into equivalence classes, which we refer to as strong components for short. We seek to implement the following API:

 

API for strong components

Remarkably, KosarajuSharirSCC.java implements the API with just a few lines of code added to CC.java, as follows:

 

  • Given a digraph G, use DepthFirstOrder.java to compute the reverse postorder of its reverse, GR.

     

  • Run standard DFS on G, but consider the unmarked vertices in the order just computed instead of the standard numerical order.

     

  • All vertices reached on a call to the recursive dfs() from the constructor are in a strong component (!), so identify them as in CC.

Proposition.

 The Kosaraju-Sharir algorithm uses preprocessing time and space proportional to V + E to support constant-time strong connectivity queries in a digraph.

 

Transitive closure.

 The transitive closure of a digraph G is another digraph with the same set of vertices, but with an edge from v to w if and only if w is reachable from v in G.

 

Transitive closure


TransitiveClosure.java computes the transitive closure of a digraph by running depth-first search from each vertex and storing the results. This solution is ideal for small or dense digraphs, but it is not a solution for the large digraphs we might encounter in practice because the constructor uses space proportional to V^2 and time proportional to V (V + E).

Digraph as a class and several digraph problems:

import java.util.LinkedList;

public class Digraph {

    private int V;                         // number of vertices
    private int E;                         // number of edges
    private LinkedList[] adjlist; // adjecency lists
    private boolean[] marked;
    int flag =0;
    LinkedList path;

    public class DepthFirstOrder
    {
        private boolean[] marked;

        private LinkedList pre;          // vertices in preorder Queue
        private LinkedList post;         // vertices in postorder Queue
        private LinkedList reversePost;  // vertices in reverse postorder Stack

        public DepthFirstOrder(Digraph G)
        {
            pre           = new LinkedList();
            post          = new LinkedList();
            reversePost   = new LinkedList();
            marked  = new boolean[G.V()];

            for (int v = 0; v < G.V(); v++)
                if (!marked[v]) dfs(G, v);
        }

        private void dfs(Digraph G, int v)
        {
            pre.add(v);

            marked[v] = true;
            for (Object w : G.adj(v)) {
                int we = (Integer) w;
                if (!marked[we])
                    dfs(G, we);
            }

            post.add(v);
            reversePost.add(v);
        }

        public Iterable pre()
        {  return pre;  }
        public Iterable post()
        {  return post;  }
        public Iterable reversePost()
        {  return reversePost;  }
    }

    public class DirectedCycle
    {
        private boolean[] marked;
        private int[] edgeTo;
        private LinkedList cycle;   // vertices on a cycle (if one exists) Stack
        private boolean[] onStack;      // vertices on recursive call stack

        public DirectedCycle(Digraph G)
        {
            onStack = new boolean[G.V()];
            edgeTo  = new int[G.V()];
            marked  = new boolean[G.V()];
            for (int v = 0; v < G.V(); v++)
                if (!marked[v]) dfs(G, v);
        }
        private void dfs(Digraph G, int v)
        {
            onStack[v] = true;
            marked[v] = true;
            for (Object w : G.adj(v))
                if (this.hasCycle()) return;
                else if (!marked[(Integer)w])
                {  edgeTo[(Integer)w] = v; dfs(G, (Integer)w);  }
                else if (onStack[(Integer)w])
                {
                    cycle = new LinkedList();
                    for (int x = v; x != (Integer)w; x = edgeTo[x])
                        cycle.add(x);
                    cycle.add((Integer)w);
                    cycle.add(v);
                }
            onStack[v] = false;
        }

        public boolean hasCycle()
        {  return cycle != null;  }

        public Iterable cycle()
        {  return cycle;  }
    }


// creates a graph with V vertices and 0 edges

    @SuppressWarnings("unchecked")
    public Digraph(int V) {
        this.V = V;
        adjlist = (LinkedList[])new LinkedList[V];
        for (int v = 0; v < V; v++) {
            adjlist[v] = new LinkedList();
        }
        marked = new boolean[V];
    }


// returns the number of vertices in this graph

    public int V() {
        return V;
    }


// returns the number of edges in this graph

    public int E() {
        return E;
    }


// adds an edge to this graph

    public void addEdge(int v, int w) {
        adjlist[v].add(w);
        E++;
    }


// returns the list of vertices adjacency to v

    public Iterable adj(int v) {

        return adjlist[v];

    }


// does this graph contain the edge (v,w)?

    public boolean containsEdge(int v, int w) {
        return adjlist[v].contains(w);
    }


// returns the reverse of this graph which is:

// the graph on the same vertices with the same edges except that each edge is reversed in direction

    public Digraph reverse() {
        Digraph d = new Digraph(V);
        for (int i = 0; i<V; i++)
            DigraphOneVertex(i, d);
        return d;
    }

    public void DigraphOneVertex(int v, Digraph d){
        for(int i = 0; i < adjlist[v].size(); i++) {
            // idea is created opposite edge : from i to v
            d.addEdge((Integer)adjlist[v].get(i),v);
        }
    }

// returns the complement of this graph which is:
// the graph on the same vertices containing all of the edges that are not in this graph

    public Digraph complement() {
        Digraph d = new Digraph(V);
        for (int i = 0; i<V; i++)
            ComplementOneVertex(i, d);
        return d;
    }

    public void ComplementOneVertex(int v, Digraph d){
        for (int i = 0; i<V; i++) {
            if (i!=v) //Except edges to itself - May be don't need this part
                if (! adjlist[v].contains((Integer) i))
                    d.addEdge(v, i);
        }
    }

// determines whether the given iterable list of vertices is a topological sort or not

        public boolean isTopological(Iterable sort) {

            StringBuilder str = new StringBuilder();
            for (Object i: sort){

                int w = (Integer) i;
                str.append(w);
                str.append(",");
            }
            System.out.println(str.toString());
            DepthFirstOrder firstOrder = new DepthFirstOrder(this);
            Iterable order =  firstOrder.pre();

            StringBuilder strFull = new StringBuilder();
            for (Object i: order){

                int w = (Integer) i;
                strFull.append(w);
                strFull.append(",");
            }
            System.out.println(strFull.toString());
            if (strFull.indexOf(str.toString())!=-1) return true;
            return false;
        }


// finds and returns a path from v to w, if there exists one, or returns null otherwise

    public Iterable pathTo(int v, int w) {
        flag = 0;
        LinkedList list = new LinkedList();
     for(int i=0; i<V; i++)
            marked[i]=false;
        dfs(v, v, w, list);
        if (marked[w])
        return list;
        else return null;
    }

    private void dfs(int i, int v, int w, LinkedList l){
        if (flag==1 || flag==2) return;
        marked[i] = true;
        l.add(i);
        if (i==w) { flag=1; return; } // we in the end
        if (i==v && flag==3 ) { flag=2; return; } // we have a circle
        if (i==v && flag==0 ) { flag=3;} //first step
        for (Object w1 : adjlist[i])
            if (!marked[(Integer)w1])
             { dfs((Integer)w1, v, w, l);  }
        return;
    }

// finds a directed cycle that contains the given two vertices v and w (if there exists one)
// otherwise (if there are no cycles between v and w), this method returns null

    public Iterable cycleBetween(int v, int w) {
        Iterable list1= pathTo(v, w);
        Iterable list2= pathTo(w, v);
        LinkedList list = new LinkedList();
        if (list1!=null)
        for(Object item: list1){
            list.add((Integer) item);
        }
        if (list2!=null)
        for(Object item: list2){
            int i = (Integer) item;
            if (i!=w)
            list.add(i);
        }

        if (list1!=null && list2!=null) {
           return list;
        }
        else return null;
    }



    public String toString() {
        StringBuilder s = new StringBuilder();
        String NEWLINE = "\n";
        s.append(V + " vertices, " + E + " edges " + NEWLINE);
        for (int v = 0; v < V; v++) {
            s.append(String.format("%d: ", v));
            for (Object w : adjlist[v]) {
                s.append(String.format("%d ", w));
            }
            s.append(NEWLINE);
        }
        return s.toString();
    }

    public static void main(String...arg){
        Digraph d = new Digraph(7);
        d.addEdge(0,1);
        d.addEdge(0,2);
        d.addEdge(0,3);
        d.addEdge(0,4);
        d.addEdge(1,2);
        d.addEdge(1,3);
        d.addEdge(1,4);
        d.addEdge(2,3);
        d.addEdge(2,5);
        d.addEdge(2,6);
        d.addEdge(3,4);
        d.addEdge(3,5);
        d.addEdge(3,6);
        d.addEdge(4,5);
        d.addEdge(4,6);
        d.addEdge(5,6);
        d.addEdge(6,0);
        System.out.println("reverse");
        System.out.println(d.toString());
        Digraph d1 = d.reverse();
        System.out.println(d1.toString());
        System.out.println("complement");
        Digraph d2 = d.complement();
        System.out.println(d2.toString());
        LinkedList list = new LinkedList();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        System.out.println("isTopological "+list.toString());
        System.out.println(d.isTopological(list));
        System.out.println(d1.isTopological(list));
        System.out.println(d2.isTopological(list));
        list = new LinkedList();
        list.add(4);
        list.add(6);
        list.add(2);
        list.add(3);
        System.out.println("isTopological "+list.toString());
        System.out.println(d.isTopological(list));
        System.out.println(d1.isTopological(list));
        System.out.println(d2.isTopological(list));
        System.out.println("pathTo  (0,3)");
        Iterable test = d.pathTo(0,3);
        if (test!= null)
            System.out.println(test.toString());
        else System.out.println("null");
        test = d1.pathTo(0,3);
        if (test!= null)
            System.out.println(test.toString());
        else System.out.println("null");
        test = d2.pathTo(0,3);
        if (test!= null)
            System.out.println(test.toString());
        else System.out.println("null");
        System.out.println("cycleBetween  (0,3)");
        test = d.cycleBetween(0,3);
        if (test!= null)
        System.out.println(test.toString());
        else System.out.println("null");
        test = d1.cycleBetween(0,3);
        if (test!= null)
            System.out.println(test.toString());
        else System.out.println("null");
        test = d2.cycleBetween(0,3);
        if (test!= null)
            System.out.println(test.toString());
        else System.out.println("null");
        System.out.println("cycleBetween  (0,3)");
        Digraph d3 = new Digraph(6);
        d3.addEdge(0,1);
        d3.addEdge(0,5);
        d3.addEdge(1,2);
        d3.addEdge(2,3);
        d3.addEdge(2,4);
        d3.addEdge(4,1);
        d3.addEdge(5,3);
        test = d3.cycleBetween(0,3);
        if (test!= null)
            System.out.println(test.toString());
        else System.out.println("null");

    }

}