Directed Graphs

Digraphs

  • A digraph is a graph whose edges are all directed
    • Short for “directed graph”
  • Applications: one-way streets, flights, task scheduling

Biconnectivity_Seperation

Properties

  • A graph G=(V,E) such that
    • Each edge goes in one direction:
      • Edge (a,b) goes from a to b, but not b to a.
  • If G is simple, m < n(n-1).
  • If we keep in-edges and out-edges in separate adjacency lists, we can perform listing of of the sets of in-edges and out-edges in time proportional to their size.

Directed DFS

  • We can specialize the traversal algorithms (DFS and BFS) to digraphs by traversing edges only along their direction
  • In the directed DFS algorithm, we have four types of edges 􀂄
    • discovery edges
    • back edges
    • forward edges
    • cross edges
  • A directed DFS starting at a vertex s determines the vertices reachable from s

Digraph_DFS

Reachability

  • DFS tree rooted at v: vertices reachable from v via directed paths

Digraph_DFS_Reachability

Strong Connectivity

  • Each vertex can reach all other vertices

Digraph_Connectivity

Strong Connectivity Algorithm

  • Pick a vertex v in G.
  • Perform a DFS from v in G.
    • If there’s a w not visited, print “no”.
  • Let G’ be G with edges reversed.
  • Perform a DFS from v in G’.
    • If there’s a w not visited, print “no”.
    • Else, print “yes”.
  • Running time: O(n+m).

Digraph_Connectivity_Alogrithm

Strongly Connected Components

  • Maximal subgraphs such that each vertex can reach all other vertices in the subgraph
  • Can also be done in O(n+m) time using DFS, but is more complicated (similar to biconnectivity). Digraph_Connectivity_Components

Transitive Closure

  • Given a digraph G, the transitive closure of G is the digraph G* such that
    • G* has the same vertices as G
    • if G has a directed path from u to v (u ≠ v), G* has a directed edge from u to v
  • The transitive closure provides reachability information about a digraph Digraph_Transitive_Closure

Computing the Transitive Closure

  • We can perform DFS starting at each vertex
    • O(n(n+m))
  • Alternatively ... Use dynamic programming: the Floyd-Warshall Algorithm

Floyd-Warshall Transitive Closure

  • Idea #1: Number the vertices 1, 2, …, n.
  • Idea #2: Consider paths that use only vertices numbered 1, 2, …, k, as intermediate vertices: Digraph_Floyd_Warshall

Floyd-Warshall’s Algorithm

Floyd-Warshall’s algorithm numbers the vertices of G as v1 , …, vn and computes a series of digraphs G0, …, Gn

  • G0=G
  • Gk has a directed edge (vi, vj) if G has a directed path from vi to vj with intermediate vertices in the set {v1 , …, vk}
    • We have that Gn = G*
    • In phase k, digraph Gk is computed from Gk − 1</Sub>
    • Running time: O(n3), assuming areAdjacent is O(1) (e.g., adjacency matrix)
Algorithm FloydWarshall(G)
  Input digraph G
  Output transitive closure G* of G
  i ← 1
  for all v ∈ G.vertices()
    denote v as vi
    i ← i + 1
  G0 ← G
  for k ← 1 to n do
    Gk ← Gk − 1
    for i ← 1 to n (i ≠ k) do
      for j ← 1 to n (j ≠ i, k) do
        if Gk − 1.areAdjacent(vi, vk) ∧
      Gk − 1.areAdjacent(vk, vj)
        if ¬Gk.areAdjacent(vi, vj)
      Gk.insertDirectedEdge(vi, vj , k)
  return Gn

TODO: Examples

DAGs and Topological Ordering

  • A directed acyclic graph (DAG) is a digraph that has no directed cycles
  • A topological ordering of a digraph is a numbering v1 , …, vn of the vertices such that for every edge (vi , vj), we have i < j
  • Example: in a task scheduling digraph, a topological ordering a task sequence that satisfies the precedence constraints

  • Theorem: A digraph admits a topological ordering if and only if it is a DAG Digraph_Topological_Ordering

  • Number vertices, so that (u,v) in E implies u < v Digraph_Topological_Ordering_Example

Algorithm for Topological Sorting

  • Note: This algorithm is different than the one in Goodrich-Tamassia
    Method TopologicalSort(G)
H ← G // Temporary copy of G
n ← G.numVertices()
while H is not empty do
  Let v be a vertex with no outgoing edges
  Label v ← n
  n ← n - 1
  Remove v from H
  • Running time: O(n + m). How…?

Topological Sorting Algorithm using DFS

  • Simulate the algorithm by using depth-first search ```java Algorithm topologicalDFS(G) Input dag G Output topological ordering of G n ← G.numVertices() for all u ∈ G.vertices() setLabel(u, UNEXPLORED) for all e ∈ G.edges() setLabel(e, UNEXPLORED) for all v ∈ G.vertices() if getLabel(v) = UNEXPLORED
    topologicalDFS(G, v)

Algorithm topologicalDFS(G, v) Input graph G and a start vertex v of G Output labeling of the vertices of G in the connected component of v setLabel(v, VISITED) for all e ∈ G.incidentEdges(v) if getLabel(e) = UNEXPLORED w ← opposite(v,e) if getLabel(w) = UNEXPLORED setLabel(e, DISCOVERY) topologicalDFS(G, w) else {e is a forward or cross edge} Label v with topological number n n ← n - 1


## Code
```java
package examples;
import graphLib.*;
import graphTool.Algorithm;
import graphTool.Attribute;
import graphTool.GraphTool;

import java.awt.Color;
import java.io.Serializable;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Random;


public class GraphExamples<V,E> {

    @Algorithm
    public void topologicalNumbering(Graph<V,E> g, GraphTool<V,E> t){
        if ( ! g.isDirected()) throw new RuntimeException("should be a directed graph");
        Iterator<Vertex<V>> it = g.vertices();
        LinkedList<Vertex> s = new LinkedList();
        while(it.hasNext()){
            Vertex v = it.next();
            v.set(Attribute.DEPENDENCIES,g.inDegree(v));
            if (g.inDegree(v)==0) s.push(v);
        }
        int num=0;
        while (! s.isEmpty()){
            Vertex<V> v = s.pop();
            v.set(Attribute.string,""+num);
            num++;
            v.set(Attribute.color,Color.GREEN);
            t.show(g);
            Iterator<Edge<E>> eit = g.incidentOutEdges(v);
            while (eit.hasNext()){
                Vertex<V> w = g.opposite(eit.next(),v);
                int depcnt = ((Integer)w.get(Attribute.DEPENDENCIES))-1;
                w.set(Attribute.DEPENDENCIES,depcnt);
                if (depcnt==0) s.push(w);            
            }
        }
        if (num!= g.numberOfVertices()) throw new RuntimeException("graph is not acyclic!");
    }

    /**
     * @param args
     *
     */
    public static void main(String[] args) {

        //         make an undirected graph
        IncidenceListGraph<String,String> g =
                new IncidenceListGraph<>(true);
        GraphExamples<String,String> ge = new GraphExamples<>();
        Vertex vA = g.insertVertex("A");
        vA.set(Attribute.name,"A");
        Vertex vB = g.insertVertex("B");
        vB.set(Attribute.name,"B");
        Vertex vC = g.insertVertex("C");
        vC.set(Attribute.name,"C");
        Vertex vD = g.insertVertex("D");
        vD.set(Attribute.name,"D");
        Vertex vE = g.insertVertex("E");
        vE.set(Attribute.name,"E");
        Vertex vF = g.insertVertex("F");
        vF.set(Attribute.name,"F");
        Vertex vG = g.insertVertex("G");
        vG.set(Attribute.name,"G");

        Edge e_a = g.insertEdge(vA,vB,"AB");
        Edge e_b = g.insertEdge(vD,vC,"DC");
        Edge e_c = g.insertEdge(vD,vB,"DB");
        Edge e_d = g.insertEdge(vC,vB,"CB");
        Edge e_e = g.insertEdge(vC,vE,"CE");
        e_e.set(Attribute.weight,2.0);
        Edge e_f = g.insertEdge(vB,vE,"BE");
        e_f.set(Attribute.weight, 7.0);
        Edge e_g = g.insertEdge(vD,vE,"DE");
        Edge e_h = g.insertEdge(vE,vG,"EG");
        e_h.set(Attribute.weight,3.0);
        Edge e_i = g.insertEdge(vG,vF,"GF");
        Edge e_j = g.insertEdge(vF,vE,"FE");
        GraphTool t = new GraphTool(g,ge);

        //    A__B     F
        //      /|\   /|
        //     / | \ / |
        //    C__D__E__G   
        //    \     /
        //     \___/
        //   
    }
}