Directed Graph and DAG

Directed Graph

All the edges of directed graph, digraph, have directions associated with them.

Terminology

u and v are vertices of digraph G.

u reaches v if there is a directed path from u to v in G.
G is strongly connected iff for any pair of vertices u and v, if u reaches v then v reaches u.

Directed cycles are cycles where edges are followed in their direction.
G is acyclic if there are no directed cycles.

The transitive closure of digraph G is the digraph G* such that the vertices of G* are the same as G and if u reaches v in G then (u, v) is an edge in G*.

Traversing a Di-graph

The digraph traversals are similar to graph traversals; we only traverse in the direction of the edges.

Algorithm: DirectedDFS(Vertex v)

Mark vertex v as visited
for each outgoing edge (v, w) of v do

if vertex w has not been visited then
    recursively call DirectedDFS(w)

The directed DFS(s) will visit all the vertex that s reaches.  The time is O(m_s + n_s) where m_s and n_s  are the number of edges and vertices reachable by s. Assuming constant time vertex and edge methods.  Because the algorithm is recursive the size created during the search is O(m_s + n_s).

The algorithm creates a spanning tree from the discovery edges.  The edges that are not members of the spanning tree can be labeled:

back - if the edge leads to an ancestor in the spanning tree
forward - if the edge leads to a descendant in the spanning tree
cross - otherwise.

While finding the reachable vertices we can build the transitive closure of G.  Adding edges to the new digraph G* as new vertices are reached.  The time is O(n²).

Testing for Strongly Connected

We can also determine if the di-graph is strongly connected by running DFS for all vertices of G.  All DFS should visit all vertices of G.  The time is again O(n²). 

Actually this test is not the most efficient.  We could do DFS(s) where s is a arbitrary vertex of G.  If not all the vertices of G have been visited then G is not strongly connected.  If all the vertices are visited then reverse the direction of all the edges and performed a DFS(s) if this search finds all the vertices of G then G is strongly connected.  What we have determined is:

any v  → s  → any v

s  → any v:   is the original call of DirectedDFS
any v  → s:   is the call of DirectedDFS with reverse direction for the edges

So all vertices can get to any vertex via s.  The time is O(n+ m).

Directed Acyclic Graph

A directed acyclic graph (DAG) is a directed graph with out cycles.  

Examples

• Inheritance between Java classes

• Prerequisites between courses in computer science degree

• Scheduling of tasks, without dead lock

Topological Sorting

A topological ordering of G is an ordering of the vertices, v₁, ... , v_n, such that for every edge in G (v_i, v_j) then i < j. Only a directed acyclic graphs, DAG, can have a topological ordering.

Use

Proof by construction. The trick is that an topological ordering  must have a vertex with in-degree equal to zero.  The vertex is the start of the ordering.   We keep track of the in-degree of each vertices in a separate array, incounter(v).  We look for vertex with incounter equal to zero  this becomes the start of the sequence then for all the outgoing edges to vertex w we subtract one from incounter(w) and look for a vertex with incounter equal to zero that will be the next vertex in the sequence.

Algorithm: TopologicalSort(G)
let S be initially empty stack
for each vertex u of G do

let incounter(u) be the in-degree of u
if incounter(u) == 0 then
S.push(u)

while S is not empty do

u = S.pop()
let u be vertex number i in the topological ordering
i = i+1
for each outgoing edge (u, w) of u do

incounter(w) = incounter(w) - 1
if incounter(w) = 0 then
    S.push(w)

The time is O(n + m)  and uses space O(n) for the stack.