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.

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

## Digraph graph data type.

We implement the following 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.

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

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.

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

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

### 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:

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.

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 boolean[] marked;
int flag =0;

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)
{
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)
{

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

}

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;
if (this.hasCycle()) return;
else if (!marked[(Integer)w])
{  edgeTo[(Integer)w] = v; dfs(G, (Integer)w);  }
else if (onStack[(Integer)w])
{
for (int x = v; x != (Integer)w; x = edgeTo[x])
}
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;
for (int v = 0; v < V; v++) {
}
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) {
E++;
}

// returns the list of vertices adjacency to v

}

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

public boolean containsEdge(int v, int 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
}
}

// 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
}
}

// 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;
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;
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
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);
if (list1!=null)
for(Object item: list1){
}
if (list2!=null)
for(Object item: list2){
int i = (Integer) item;
if (i!=w)
}

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);
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());
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("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);