欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Directed Graph

程序员文章站 2022-07-10 09:18:02
...

1.  Digraph: Set of vertices connected pairwise by directed edges.

 

2.  Digraph applications :


Directed Graph
            
    
    博客分类: Algorithm II -- Princeton 学习笔记 Directed GraphTopological OrderStrongly Connected ComponentsDFSBFS 
 

3.  Some digraph problems:

    --  Path: Is there a directed path from s to t ?

    --  Shortest path: What is the shortest directed path from s to t ?

    --  Topological sort: Can you draw a digraph so that all edges point upwards?

    --  Strong connectivity: Is there a directed path between all pairs of vertices?

    --  Transitive closure: For which vertices v and w is there a path from v to w ?

    --  PageRank: What is the importance of a web page?

 

4.  Digraph API:

public class Digraph {
    Digraph(int V) {} //create an empty digraph with V vertices
    Digraph(In in) {} //create a digraph from input stream
    void addEdge(int v, int w) {} //add a directed edge v→w
    Iterable<Integer> adj(int v) {} //vertices pointing from v
    int V() {} //number of vertices
    int E() {} //number of edges
    Digraph reverse() {} //reverse of this digraph
    String toString() {} //string representation
}

 

5.  Adjacency-lists digraph representation

    --  Maintain vertex-indexed array of lists


Directed Graph
            
    
    博客分类: Algorithm II -- Princeton 学习笔记 Directed GraphTopological OrderStrongly Connected ComponentsDFSBFS 
 

    --  Java implementation

public class Digraph
{
    private final int V;
    private final Bag<Integer>[] adj;
    public Digraph(int V)
    {
        this.V = V;
        adj = (Bag<Integer>[]) new Bag[V];
        for (int v = 0; v < V; v++)
            adj[v] = new Bag<Integer>();
    }
    public void addEdge(int v, int w)
    {
        adj[v].add(w);
    }
    public Iterable<Integer> adj(int v)
    { return adj[v]; }
}

 

    --  Performance :


Directed Graph
            
    
    博客分类: Algorithm II -- Princeton 学习笔记 Directed GraphTopological OrderStrongly Connected ComponentsDFSBFS 
 

6.  Depth-first search in digraphs : Same method as for undirected graphs.

    --  Every undirected graph is a digraph (with edges in both directions).

    --  DFS is a digraph algorithm.

    --  Algorithm:

Directed Graph
            
    
    博客分类: Algorithm II -- Princeton 学习笔记 Directed GraphTopological OrderStrongly Connected ComponentsDFSBFS 
     --  Java Implementation :

public class DirectedDFS
{
    private boolean[] marked;
    public DirectedDFS(Digraph G, int s)
    {
        marked = new boolean[G.V()];
        dfs(G, s);
    }

    private void dfs(Digraph G, int v)
    {
        marked[v] = true;
        for (int w : G.adj(v))
            if (!marked[w]) dfs(G, w);
    }
    
    public boolean visited(int v)
    { return marked[v]; }
}

 

7.  Reachability application:

    --  program control-flow analysis:

        1)  Every program is a digraph.

             --  Vertex = basic block of instructions (straight-line program).

             --  Edge = jump.

        2)  Dead-code elimination.

             --  Find (and remove) unreachable code.

        3)  Infinite-loop detection.

             --  Determine whether exit is unreachable.

    --  mark-sweep garbage collector:

        1)  Every data structure is a digraph.

             --  Vertex = object.

             --  Edge = reference.

         2)  Roots: Objects known to be directly accessible by program (e.g., stack).

         3)  Reachable objects: Objects indirectly accessible by program

         4)  Mark-sweep algorithm:

             --  Mark: mark all reachable objects.

             --  Sweep: if object is unmarked, it is garbage (so add to free list).

         5)  Memory cost: Uses 1 extra mark bit per object (plus DFS stack).

 

8.  Breadth-first search in digraphs : Same method as for undirected graphs.

    --  Every undirected graph is a digraph (with edges in both directions).

    --  BFS is a digraph algorithm.

    --  BFS algorithm :


Directed Graph
            
    
    博客分类: Algorithm II -- Princeton 学习笔记 Directed GraphTopological OrderStrongly Connected ComponentsDFSBFS 
    --  BFS computes shortest paths (fewest number of edges) from s to all other vertices in a digraph in time proportional to E + V.

 

9.  Multiple-source shortest paths: Given a digraph and a set of source vertices, find shortest path from any vertex in the set to each other vertex. Solution: use BFS, but initialize by enqueuing all source vertices.

 

10.  Web crawler :

    --  Goal: Crawl web, starting from some root web page.

    --  Solution:

        --  Choose root web page as source s.

        --  Maintain a Queue of websites to explore.

        --  Maintain a SET of discovered websites.

        --  Dequeue the next website and enqueue websites to which it links (provided you haven't done so before).

    --  Java Implementation:

Queue<String> queue = new Queue<String>();
SET<String> marked = new SET<String>();
String root = "http://www.princeton.edu";
queue.enqueue(root);
marked.add(root);
while (!queue.isEmpty())
{
    String v = queue.dequeue();
    StdOut.println(v);
    In in = new In(v);
    String input = in.readAll();
    String regexp = "http://(\\w+\\.)*(\\w+)";
    Pattern pattern = Pattern.compile(regexp);
    Matcher matcher = pattern.matcher(input);
    while (matcher.find())
    {
        String w = matcher.group();
        if (!marked.contains(w))
        {
            marked.add(w);
            queue.enqueue(w);
        }
    }
}

 

 

11.  Precedence scheduling :

    --  Goal. Given a set of tasks to be completed with precedence constraints, in which order should we schedule the tasks?

    --  Digraph model. vertex = task; edge = precedence constraint.

    --  Solution : Topological sort : Redraw DAG (Directed Acyclic Graph) so all edges point upwards.

 

12.  Topological sort :

    --  Algorithm:

        1)  Run depth-first search.

        2)  Return vertices in reverse postorder.

    --  Java Implementation:

public class DepthFirstOrder
{
    private boolean[] marked;
    private Stack<Integer> reversePost;
    public DepthFirstOrder(Digraph G)
    {
        reversePost = new Stack<Integer>();
        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 (int w : G.adj(v))
            if (!marked[w]) dfs(G, w);
                reversePost.push(v);
    }

    public Iterable<Integer> reversePost()
    { return reversePost; }
}

     --  Proposition. Reverse DFS postorder of a DAG is a topological order.

         Pf. Consider any edge v→w. When dfs(v) is called:

          --  Case 1: dfs(w) has already been called and returned.

              Thus, w was done before v.

          --  Case 2: dfs(w) has not yet been called.

              dfs(w) will get called directly or indirectly by dfs(v) and will finish before dfs(v).

              Thus, w will be done before v.

          --  Case 3: dfs(w) has already been called, but has not yet returned.

              Can’t happen in a DAG: function call stack contains path from w to v, so v→w would complete a cycle.

 

13.  Proposition. A digraph has a topological order iff no directed cycle.

    --  If directed cycle, topological order impossible.

    --  If no directed cycle, DFS-based algorithm finds a topological order.

 

14.  Directed cycle detection application :

    --  precedence scheduling, a directed cycle implies scheduling problem is infeasible.

    --  cyclic inheritance. The Java compiler does cycle detection.

    --  spreadsheet recalculation

 

 15.  Strongly Connected: Vertices v and w are strongly connected if there is both a directed path

from v to w and a directed path from w to v. Strong connectivity is an equivalence relation:

    --  v is strongly connected to v.

    --  If v is strongly connected to w, then w is strongly connected to v.

    --  If v is strongly connected to w and w to x, then v is strongly connected to x.

A strong component is a maximal subset of strongly-connected vertices.

 

16.  Strong component application :

    --  ecological food webs

        1)  Food web graph. Vertex = species; Edge = from producer to consumer.

        2)  Strong component. Subset of species with common energy flow.

    --  software modules

        1)  Software module dependency graph. Vertex = software module; Edge: from module to dependency.

        2)  Strong component. Subset of mutually interacting modules.

        3)  Usage : 

             --  Package strong components together.

             --  Use to improve design.

 

16.  Kosaraju-Sharir algorithm:

    --  Reverse graph: Strong components in G are same as in G-reverse.

    --  Kernel DAG: Contract each strong component into a single vertex.


Directed Graph
            
    
    博客分类: Algorithm II -- Princeton 学习笔记 Directed GraphTopological OrderStrongly Connected ComponentsDFSBFS 
 

    --  Algorithm : 

        --  Phase 1: run DFS on G-reverse to compute reverse postorder.

        --  Phase 2: run DFS on G, considering vertices in order given by first DFS.

    --  Java Implementation :

public class KosarajuSharirSCC
{
    private boolean marked[];
    private int[] id;
    private int count;
    public KosarajuSharirSCC(Digraph G)
    {
        marked = new boolean[G.V()];
        id = new int[G.V()];
        DepthFirstOrder dfs = new DepthFirstOrder(G.reverse());
        for (int v : dfs.reversePost())
        {
            if (!marked[v])
            {
                dfs(G, v);
                count++;
            }
        }
    }
    private void dfs(Digraph G, int v)
    {
        marked[v] = true;
        id[v] = count;
        for (int w : G.adj(v))
            if (!marked[w])
                dfs(G, w);
    }
    public boolean stronglyConnected(int v, int w)
    { return id[v] == id[w]; }
}

 

  • Directed Graph
            
    
    博客分类: Algorithm II -- Princeton 学习笔记 Directed GraphTopological OrderStrongly Connected ComponentsDFSBFS 
  • 大小: 46.3 KB
  • Directed Graph
            
    
    博客分类: Algorithm II -- Princeton 学习笔记 Directed GraphTopological OrderStrongly Connected ComponentsDFSBFS 
  • 大小: 41 KB
  • Directed Graph
            
    
    博客分类: Algorithm II -- Princeton 学习笔记 Directed GraphTopological OrderStrongly Connected ComponentsDFSBFS 
  • 大小: 24 KB
  • Directed Graph
            
    
    博客分类: Algorithm II -- Princeton 学习笔记 Directed GraphTopological OrderStrongly Connected ComponentsDFSBFS 
  • 大小: 8.5 KB
  • Directed Graph
            
    
    博客分类: Algorithm II -- Princeton 学习笔记 Directed GraphTopological OrderStrongly Connected ComponentsDFSBFS 
  • 大小: 14.6 KB
  • Directed Graph
            
    
    博客分类: Algorithm II -- Princeton 学习笔记 Directed GraphTopological OrderStrongly Connected ComponentsDFSBFS 
  • 大小: 40.2 KB