Directed Graphs PDF

Preview

Summary

Swami Iyer...

Description

Directed Graphs

1 / 24

Outline

1 Directed Graphs

2 Depth-First Search (DFS)

3 Breadth-First Search (BFS)

4 Topological Sort

5 Strong Components

2 / 24

Directed Graphs

Digraph applications digraph transportation web food web WordNet scheduling financial cell phone infectious disease game citation object graph inheritance hierarchy control flow

vertex street intersection web page species synset task bank person person board position journal article object class code block

edge one-way street hyperlink predator-prey relationship hypernym precedence constraint transaction placed call infection legal move citation pointer inherits from jump

4 / 24

Directed Graphs

Some digraph problems problem shortest s → t path directed cycle topological sort strong connectivity

page rank

description is there a path from s to t? what is the shortest path from s to t? is there a directed cycle in the graph? can the digraph be drawn so that all edges point in a single direction? is there a directed path between all pairs of vertices? for which vertices v and w is there a directed path from v to w ? what is the importance of a web page?

5 / 24

Directed Graphs Implementation of

Digraph

data type using an adjacency list

package edu . p ri nce to n . cs . algs 4 ; import java . util . I np utM i sm at chE xc ept i on ; import java . util . N oS uch E le me ntE xc ept i on ; publ ic class Digraph { pri vat e final int V ; private int E; private LinkedBag < Integer >[] adj ; public Dig rap h ( int V ) { if ( V < 0) { t hrow new IllegalArgumentException (); } this . V = V ; this . E = 0; adj = ( LinkedBag < Integer >[]) new L in ked Ba g [ V ]; for ( int v = 0; v < V; v ++) { adj [ v] = new LinkedBag < Integer >(); } } public Dig ra ph ( In in ) { this ( in . re ad In t ()); int E = in . re ad Int (); if ( E < 0) { t hrow new IllegalArgumentException (); } for ( int i = 0; i < E; i ++) { int v = in . re ad Int (); int w = in . re ad Int (); add Ed ge (v , w ); } }

7 / 24

Directed Graphs public int V () { return V ; } public int E () { return E ; } private void validateVertex ( int v ) { if ( v < 0 || v >= V) { thr ow new IndexOutOfBoundsExcepti on (); } } publ ic void addEdge ( int v , int w ) { va lid at eV er te x (v ); va lid at eV er te x (w ); adj [ v ]. add (w ); E ++; } public Iterable < Integer > adj ( int v ) { va lid at eV er te x (v ); return adj [v ]; } public Digraph reverse () { Dig rap h R = new D igr ap h ( V ); for ( int v = 0; v < V; v ++) { for ( int w : adj ( v )) { R . ad dE dge (w , v ); } } return R ; } }

8 / 24

Same method as for undirected graphs, ie, to visit a vertex v • Mark a vertex v as visited • Recursively visit all unmarked vertices pointing from v

Reachability problem : given a digraph and a source vertex s, support queries

•

of the form : given a digraph and a set of source vertices, support

•

queries of the form

Applications • Program control-flow analysis such as dead-code elimination and infinite-loop

detection • Mark and sweep garbage collector

9 / 24

Breadth-First Search (BFS)

Same method as for undirected graphs, ie, repeat until

is empty

• Remove vertex v from • Add to queue all unmarked vertices pointing from v and mark them

(fewest number of edges) in time proportional to 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 / 24

Breadth-First Search (BFS) Application (web crawler) import edu . p ri nce to n . cs . algs 4 .*; import java . util . regex .*; publ ic class We bC ra wl er { publ ic s tati c void main ( St ring [] args ) { Stri ng s = args [0]; Linke dQueu e < String > queue = new L inked Queu e < String >(); queue . en que ue ( s ); SET < String > mar ked = new SET < String >(); mark ed . add ( s ); while (! q ueue . is Emp ty ()) { Stri ng v = queue . de que ue (); Syst em . out . p rin tln ( v ); In in = new In ( v ); if (! in . exis ts ()) { co nt inu e ; } Stri ng i nput = in . rea dA ll (); if ( inpu t == null) { cont in ue ; } = " http :/ /(\ \ w +\\ .)+ (\ \ w +) " ; Pat ter n pa tte rn = Pa tte rn . co mpi le ( reg exp ); Mat che r ma tch er = pa tte rn . ma tch er ( input ); while ( m atc her . find ()) { Stri ng w = ma tch er . gro up (); if (! ma rked . con ta ins ( w )) { qu eue . en que ue ( w ); mark ed . add ( w ); } } } } } $ java We bC ra wl er http :// www . s wa mii ye r . net / http :// www . sw am ii yer . net / http :// www . w3 . org http :// j emdo c . ja boc . net ... 11 / 24

Topological Sort Directed cycle detection package edu . p ri nce to n . cs . algs 4 ; publ ic class Di r ec te dC y cl e { pri vat e bo ole an [] marked ; private int [] edgeTo ; pri vat e bo ole an [] on Sta ck ; private Linke dStac k < Integer > cycle ; public Di re c te dC yc le ( D igr aph G) { marked = new boolean [ G. V ()]; onS tac k = new boo lea n [ G. V ()]; edgeTo = new int [ G . V ()]; for ( int v = 0; v < G . V (); v ++) { if (! ma rked [ v] && cycle == null ) { dfs (G , v ); } } } private void dfs ( Dig ra ph G , int v ) { onS tac k [ v] = true ; mark ed [ v ] = true ; for ( int w : G . adj ( v )) { if ( cycl e != null) { return ; } else if (! m ark ed [ w ]) { edge To [ w ] = v ; dfs (G , w ); } else if ( o nS ta ck [ w ]) { cycle = new L inked Stack < Integer >(); for ( int x = v ; x != w ; x = e dge To [ x ]) { c ycle . push ( x ); } cycle . push ( w ); cy cle . push ( v ); } } onS tac k [ v] = fals e ; }

14 / 24

Topological Sort publ ic bo ole an ha sC ycl e () { return cycl e != null ; } public Iterable < Integer > c ycle () { return cycl e ; } publ ic s tati c void main ( St ring [] args ) { In in = new In ( args [0]); Dig rap h G = new D igr ap h ( in ); Di re ct e dC yc le fin der = new D ir ec te dC yc le ( G ); if ( fi nder . h as Cyc le ()) { StdO ut . prin t (" D ir ec te d cy cle : " ); for ( int v : fin der . cy cle ()) { StdO ut . prin t (v + " " ); } StdO ut . pr int ln (); } else { StdO ut . pri ntl n ( " No dir ec ted c ycle " ); } StdO ut . pr int ln (); } } $ java edu . pr in cet on . cs . algs4 . Di rec ted Cyc le tinyD G . txt Dir ec ted cycle : 3 5 4 3

Directed cycle detection applications • Cyclic inheritance • Circular references in spreadsheet calculations 15 / 24

Topological Sort DFS orders • • •

: order in which

dfs()

: order in which

is called

dfs()

returns

: reverse order in which

dfs()

returns

Implementation of DFS orders package edu . p ri nce to n . cs . algs 4 ; publ ic class D ep th F ir st O rd er { pri vat e bo ole an [] marked ; private int [] pre ; private int [] post ; private Linke dQueu e < Integer > p reo rde r ; private Linke dQueu e < Integer > p os tor de r ; private int pr eC ou nt er ; private int postCounter ; public De pt h Fi r st Or d er ( D igr aph G) { pre = new int [ G . V ()]; post = new int [ G. V ()]; po sto rd er = new Lin kedQu eue < Integer >(); pre or der = new Li nkedQ ueue < Integer >(); marked = new boolean [ G. V ()]; for ( int v = 0; v < G . V (); v ++) { if (! ma rk ed [v ]) { dfs ( G , v ); } } }

16 / 24

Topological Sort

private void dfs ( Dig ra ph G , int v ) { mark ed [ v ] = true ; pre [ v] = pr eC ou nt er ++; pre or der . e nqu eue ( v ); for ( int w : G . adj ( v )) { if (! ma rk ed [w ]) { dfs (G , w ); } } po sto rd er . e nqu eue ( v ); post [ v] = p os t Co un te r ++; } public int pre ( int v ) { return pre [ v ]; } public int post( int v ) { return post [ v ]; } public Iterable < Integer > post () { return p ost or de r ; } public Iterable < Integer > pre () { return p reo rd er ; } public Iterable < Integer > rev er se Po st () { Linke dStac k < Integer > rev ers e = new Lin kedS tack < Integer >(); for ( int v : p ost or de r ) { re ver se . push ( v ); } return reverse ; }

17 / 24

Topological Sort

publ ic s tati c void main ( St ring [] args ) { In in = new In ( args [0]); Dig rap h G = new D igr ap h ( in ); De pt h Fi r st Or d er dfs = new D ep th Fi rst Or de r ( G ); StdO ut . pri ntl n ( " v pre post " ); StdO ut . pri ntl n ( " - -- -- -- -- -- --- " ); for ( int v = 0; v < G . V (); v ++) { StdOut . printf ( " %4 d %4 d %4 d \n " , v , dfs . pre ( v) , dfs . post ( v )); } StdO ut . prin t (" P re or de r : " ); for ( int v : dfs . pre ()) { StdO ut . prin t (v + " " ); } StdO ut . pr int ln (); StdO ut . prin t (" P os to rd er : " ); for ( int v : dfs . post ()) { StdO ut . prin t (v + " " ); } StdO ut . pr int ln (); StdO ut . prin t (" Re ve rs e pos tor de r : " ); for ( int v : dfs . re ve rs eP os t ()) { StdO ut . prin t (v + " " ); } StdO ut . pr int ln (); } }

18 / 24

Topological Sort

$ java edu . pr in cet on . cs . algs4 . De pt hF ir st Or der tin yDG . txt v pre post -- - - -- - -- - - -- 0 0 5 1 5 4 2 4 0 3 3 1 4 2 2 5 1 3 6 6 11 7 12 12 8 11 10 9 7 9 10 10 8 11 8 7 12 9 6 Pre or der : 0 5 4 3 2 1 6 9 11 12 10 8 7 Po sto rd er : 2 3 4 5 1 0 12 11 10 9 8 6 7 Rev ers e p ost or de r : 7 6 8 9 10 11 12 0 1 5 4 3 2

19 / 24

Topological Sort Topological sort (solution) • Run depth-first search • Return vertices in reverse postorder Topological sort (implementation) package edu . p ri nce to n . cs . algs 4 ; publ ic class Topological { private Iterable < Integer > or der ; public To po lo gi ca l ( Di gra ph G ) { Di re ct e dC yc le fin der = new D ir ec te dC yc le ( G ); if (! fi nder . ha sC ycl e ()) { De pt h Fi r st Or d er dfs = new D ep th Fi rst Or de r ( G ); order = dfs . r ev er se Po st (); } } public Iterable < Integer > o rder () { return orde r ; } publ ic bo ole an ha sO rde r () { return orde r != null ; } publ ic s tati c void main ( St ring [] args ) { Stri ng f ile na me = args [0]; Stri ng d el im ite r = args [1]; Sy mb ol D ig ra ph sg = new S y mb ol Di g ra ph ( filename , deli mi te r ); To po lo gi ca l to po lo gi ca l = new To pol ogi cal ( sg . G ()); for ( int v : t op ol og ic al . ord er ()) { StdO ut . p ri nt ln ( sg . name ( v )); } } } 20 / 24

Topological Sort

$ more jobs . txt Al go ri thm s / Th e or et ic al CS / Da ta ba ses / S ci en ti fi c C om pu ti ng In tr od uc t io n to CS / Ad van ce d P ro gr am mi ng / A lg or it hm s Adv an ced P ro gr am mi ng / S ci en ti fic C omp ut in g Sc ie nt ifi c Com pu ti ng / C om pu t at io na l Bio log y Th eo ret ica l CS / Co mpu ta ti ona l Bi ol og y / Ar ti fic ia l I nt el li gen ce Line ar A lge bra / T he or e ti ca l CS Cal cu lus / L inea r Al geb ra Ar ti fi cia l In te ll ig e nc e / Neur al N et wor ks / R obo ti cs / Ma chi ne L ea rni ng Mac hin e L ear nin g / Ne ural Net wo rks $ java edu . pr in cet on . cs . algs4 . To po log ica l jobs . txt "/" Cal cu lus Line ar Al geb ra Introduction to CS Adv an ced P ro gr am m in g Al go ri thm s Th eo re ti ca l CS Ar ti fi cia l I nt el li ge nc e Rob ot ics Mac hin e Lea rn ing Neur al Ne two rk s Databases Sc ie nt ifi c Co mp ut ing Co mp ut a ti on al B iol ogy

21 / 24

Strong Components Computing strong components (solution: Kosaraju-Sharir algorithm) • Given a digraph G, use DepthFirstOrder 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 Kosaraju-Sharir algorithm (implementation) package edu . p ri nce to n . cs . algs 4 ; publ ic class KosarajuSharirSCC { pri vat e bo ole an [] marked ; private int [] id ; private int coun t ; public Ko s ar aj u Sh a ri r SC C ( Di gra ph G ) { De pt h Fi r st Or d er dfs = new D e pt hF i rs tO r de r ( G . re ver se ()); marked = new boo lea n [G .V ()]; id = new int [ G. V ()]; for ( int v : dfs . re ve rs eP os t ()) { if (! ma rk ed [v ]) { dfs ( G , v ); co unt ++; } } } private void dfs ( Dig ra ph G , int v ) { mark ed [ v ] = true ; id [ v] = count ; for ( int w : G . adj ( v )) { if (! ma rke d [ w ]) { dfs ( G , w ); } } } 23 / 24

Strong Components public int count () { return co unt ; } publ ic bo ole an stronglyConnected ( int v , int w ) { return id [ v ] == id [ w ]; } public int id ( int v ) { return id [ v ]; } publ ic s tati c void main ( St ring [] args ) { In in = new In ( args [0]); Dig rap h G = new D igr ap h ( in ); Ko s ar aj u Sh a ri r SC C scc = new Ko sa ra ju Sha ri rSC C ( G ); int M = scc . cou nt (); StdO ut . pri ntl n ( M + " c omp one nt s " ); Linke dQueu e < Integer >[] c om po ne nt s = ( Lin kedQu eue < Integer >[]) new Q ueue [ M ]; for ( int i = 0; i < M; i ++) { co mp on en ts [ i ] = new L inked Queue < Integer >(); } for ( int v = 0; v < G .V (); v ++) { com po nen ts [ scc . id ( v )]. en qu eu e ( v ); } for ( int i = 0; i < M; i ++) { for ( int v : c om pon en ts [ i ]) { St dOu t . p rint ( v + " " ); } StdO ut . pr int ln (); } } } $ 5 1 0 9 6 7

java edu . pr in cet on . cs . algs4 . Ko sa raj uS ha ri rSC C ti nyD G . txt co mp on en ts 2 3 4 5 10 11 12 8

24 / 24...