grafos dirigidos -j. b. hayet

PAII-7: Grafos dirigidos

Dr. J.B. Hayet

CENTRO DE INVESTIGACION EN MATEMATICAS

Febrero 2008

,J.B. Hayet Programacion, Febrero 2008 1 / 57

Outline

1 Grafos dirigidos

2 Cerradura transitiva

3 Grafos dirigidos acıclicos


Grafos dirigidos

Outline

1 Grafos dirigidos




Grafos dirigidos

Grafos dirigidos

Un grafo dirigido es un grafo cuyas aristas son todas dirigidas (arcos)

4

1

3

0

5

2

67

8

Aplicaciones: transporte, planificacion de tareas, cadena alimentar,calificacion de sitios www, cadenas de dependencia. . .


Grafos dirigidos

Grafos dirigidos

De la misma manera que los no dirigidos, les podemos notar:

G = (V , A)

Un arco (v , w) difiere de (w , v)

Si G es simple, |A| ≤ |V |(|V | − 1)

Muchos grafos posibles con |V | aristas: 2|V |(|V |−1)

El grafo inverso es el grafo que se obtiene al cambiar la direccionde todos los arcos


Grafos dirigidos

Grafos dirigidos

Un camino dirigido es una lista de vertices en la que hay un arcoconectando cada vertice a su sucesor en la lista

Un vertice w es alcanzable desde otro vertice v si existe uncamino dirigido desde v hasta w

La conectividad de esos grafos no se ve tan facilmente que en elcaso no dirigido; ademas, su estudio implica mas cosas que ver:en un grafo dirigido, si existe un camino de s a t, eso no permiteinferir nada de que si existe entre t y s

no obstante, vamos a re-utilizar mucho de lo que vimos para losno dirigidos


Grafos dirigidos

Grafos dirigidos

Grado entrante g+(v): para un vertice v , es el numero de arcosque llevan a este vertice

Grado saliente g−(v): para un vertice, es el numero de arcos quesalen de este vertice

Una fuente es un vertice v tal que g+(v) = 0 (no se puedealcanzar desde cualquier otro vertice)

Un pozo es un vertice v tal que g−(v) = 0 (no se puedealcanzar ningun vertice desde este)


Grafos dirigidos

Grafos dirigidos: representacion

Con matriz de adyacencia:

4

1

3

0

5

2

67

8

0 1 1 0 0 0 0 0 00 0 0 1 0 1 0 0 01 0 0 0 0 0 1 0 00 0 1 0 0 1 0 0 00 0 0 0 0 0 1 1 00 0 0 1 0 0 0 0 10 0 0 0 0 0 0 1 00 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0

Ya no tenemos simetrıa. . . Y AT corresponde al grafo inverso


Grafos dirigidos

Grafos dirigidos: representacion

Con lista de adyacencia:

Una opcion es representar cada arco una y una sola vez en lalista de adyacencia del vertice incidente (igual que para grafosno dirigidos, pero con la mitad de arcos)

Ahora en muchos algoritmos se puede necesitar saber no solo sihay arcos saliendo de un vertice sino tambien si hay arcosentrantes:

usar dos grafos, el grafo y su inversousar dos listas en cada vertice: los entrantes y los salientesusar la misma representacion que los grafos no dirigidos perocon un bit de direccion


Grafos dirigidos

Ciclo dirigido

Un ciclo dirigido es un camino simple de tamano al menos dosque conecte un vertice con sı mismo (un vertice de un ciclodirigido tiene g+(v) > 0 y g−(v) > 0)

v − w − v es un ciclo dirigido (pero no en el caso no dirigido)

en muchas aplicaciones, no se quiere tener de esos ciclos: sedefine un grafo dirigido aciclico (DAG) como un grafo dirigidosin ciclos dirigidos


Grafos dirigidos

Conectividad

v y w son fuertemente conectados (o mutuamente alcanzables)si existe un camino dirigido de v a w y otro de w a v : nocionmas fuerte que la “alcanzabilidad”

Otra manera de decirlo: v y w estan ubicados sobre un caminocıclico

Por ejemplo, 5 y 0 estan fuertemente conectados (pero no estanun ciclo)

el grafo es fuertemente conectado si todos sus pares de verticesson fuertemente conectados

El grafo no fuertemente conectado se puede particionar en unconjunto de subgrafos (componentes) fuertemente conectados yde arcos que conectan esos subgrafos


Grafos dirigidos

Terminologıa

conectada (0-1-5-3-2)

1

3

0

5

2

67

8

4

pozo

fuente

ciclo dirigido

componente fuertemente


Grafos dirigidos

Conectividad

La conectividad fuerte define una relacion de equivalencia cuyasclase de equivalencia son las componentes fuertementeconectadas

Un grafo-ciclo es compuesto de una sola componentefuertemente conectada

Un DAG es formado por puros vertices-componentesfuertemente conectadas (por que ?)

Notar la diferencia con la conectividad en grafos no dirigidos:aquı hay arcos que no pertenecen a una componentefuertemente conectada


Grafos dirigidos

Conectividad

Propriedad: el grafo que se puede construir al usando cadacomponente fuertemente conectada por vertice y cada arco que noentra en uno de los componentes es un DAG, y lo llamamos DAGnucleo (kernel DAG )

Solo falta probar que no tiene ciclos: es obvio, ya que si doscomponentes distintas estan en un ciclo entonces para cualquier parde dos vertices en esas componentes podrıamos encontrar un caminoen ambos sentidos


Grafos dirigidos

DAG nucleo

DAG nucleo

8

6

4

7

1

3

0

5

2


Grafos dirigidos

Conectividad

Distinguir:

conectividad: grafos no dirigidos, cuestion de saber si existe uncamino simple entre dos nodos

alcanzabilidad: grafos dirigidos, cuestion de saber si a partir deun vertice se puede alcanzar otro con un camino dirigido

conectividad fuerte: grafos dirigidos, cuestion de saber si dosvertices pueden alcanzar uno al otro


Grafos dirigidos

Problemas tıpicos

existencia de ciclos orientados

ordenamiento topologico: corresponde a encontrar una nuevamanera de poner numeros a los vertices de tal manera que si(v , w) es una arco, v < w

calculo de la cerradura transitiva (otro grafo donde todos losvertices alcanzables uno desde el otro en el grafo original estanconectados)

calculo de la conectividad fuerte y de sus componentesrelacionadas: subgrafos maximos donde cada vertice puedealcanzar todos los otros


Grafos dirigidos

DFS, otra vez

Podemos aplicar DFS tal cual, despues de todo: la diferencia esque vamos a examinar los arcos salientes de cada nodo y que nonecesariamente nos encontraremos al arco inverso

Eso no hace el DFS mas estructuralmente “facil”

Conservamos nodos internos en el arbol correspondiendo a lasllamadas recursivas, y nodos externos que corresponden a:

vertices ya visitadospozos


Grafos dirigidos

DFS en grafos dirigidos

4

1

3

0

5

2

67

8


Grafos dirigidos


El arbol DFS correspondiente:

3

2 5

86

7

0

1

2

5

30


Grafos dirigidos


Clasificacion de las aristas del arbol en grafos no dirigidos: 4clases (con dos criterios: tree edge o no, primera vez o no)

Clasificacion de las aristas del arbol en grafos dirigidos:

tree edge (llamada recursiva): 1-3back edge (liga hacia un ancestro): 2-0down edge (liga hacia un descendiente): 0-2cross edge (liga hacia un vertice que no es ancestro odescendiente): si exitiera, 5-6

Por que no hay cross-edges en grafos no dirigidos?


Grafos dirigidos


Una caracterizacion eficiente: usar ordenes preorden Y postorden!Comparar los vertices del arco:

pre post ejemplo tipo< > 0-2 down> < 2-0 back> > 5-6 cross

Una arista hacia un vertice visitado es

back ssi lleva a un postorden superior

down ssi lleva a un postorden inferior y un preorden superior

cross ssi lleva a un postorden inferior y un preorden inferior

Por que no hay dual de los cross-edges?


Grafos dirigidos


t emp la t e <c l a s s Graph> c l a s s DFS {const Graph &G;i n t depth , cnt , cntP ;vec to r <int> pre , po s t ;void show ( char ∗ s , Edge e ) {

f o r ( i n t i = 0 ; i < depth ; i++) cout << ” ” ;cout << e . v << ”−” << e .w << s << end l ;

}void dfsR ( Edge e ) {

i n t w = e .w; show ( ” t r e e ” , e ) ;p re [w] = cnt++; depth++;typename Graph : : a d j I t e r a t o r A(G, w) ;f o r ( i n t t = A. beg ( ) ; !A . end ( ) ; t = A. nxt ( ) ) {

Edge x (w, t ) ;i f ( p re [ t ] == −1) dfsR ( x ) ;


Grafos dirigidos


e l s e i f ( pos t [ t ] == −1) show ( ” back” , x ) ;e l s e i f ( p re [ t ] > pre [w ] ) show ( ” down” , x ) ;e l s e show ( ” c r o s s ” , x ) ;

}pos t [w] = cntP++; depth−−;

}p u b l i c :

DFS( const Graph &G) : G(G) , cnt ( 0 ) , cntP (0 ) ,p re (G .V( ) , −1) , po s t (G .V( ) , −1) {f o r ( i n t v = 0 ; v < G.V ( ) ; v++)

i f ( p re [ v ] == −1) dfsR ( Edge ( v , v ) ) ; }} ;


Grafos dirigidos


Complejidad lineal, otra vez; en el peor caso O(|A|+ |V |) oO(|V |2)Las propiedades de los diferentes arcos en el arbol no son tantopropiedades intrınsecas del grafo, sino de la busqueda

Buscar a partir de diferentes vertices puede llevar resultados muydiferentes


Grafos dirigidos


Deteccion de ciclos: un grafo es un DAG ssi el DFS aplicado a estegrafo no conduce a ningun back edge al examinar todos los arcos.

(1) ⇒ (2) si hay un back edge construimos con ese unciclo dirigido con la sucesion de tree edges

(2) ⇒ (1) suponemos que no es un DAG y que hay unciclo. DFS va a visitar un primero vertice del ciclo, v .Los vertices siguientes tendran un orden preorden masalto; el precedente en el ciclo apuntara hacia el: eso seraun back edge


Grafos dirigidos


Una consecuencia: todo grafo puede estar transformado en DAG:aplicar una DFS y quitar los arcos de tipo back

1

3

0

5

2

67

8


Grafos dirigidos


Diferencia con grafos no dirigidos: la implementacion es un pocodiferente porque no tenemos que descartar esta vez las aristas detipo “hijo-padre”: esta vez son aristas de tipo back como lasotras

Entender que DFS, en grafos dirigidos, nos da informacion dealcanzabilidad fuertemente ligada al vertice de inicio; en grafosno dirigidos, deducıamos informacion de conectividad global

Perdimos informacion “global” al olvidar los cross, back, down

Para obtener toda la informacion de alcanzabilidad, a prioripodrıamos hacer una sucesion de DFS sobre cada vertice; perose puede hacer mejor


Grafos dirigidos


Aplicaciones:

determinar en un programa que esta corriendo cuales son losapuntadores que se van a poder alcanzar o no. . . : GarbageCollector que libera los objetos que no se puede alcanzar

determinar pedazos de codigo “muerto” entre todos los archivos:que no van a estar usados en el programa


Grafos dirigidos

BFS en grafos dirigidos

BFS y mas generalmente todos los recorridos lineales con colageneralizada funcionan igual que en el caso de grafos dirigidos

exploran los mismos vertices al empezar en uno en particular: losvertices alcanzables por este

toman tiempo lineal


Grafos dirigidos

BFS en grafos dirigidos

Ejemplo: web crawlers con sitios web y hyperlinks

partir de un sitio www

poner los sitios ligados de este www en una cola generalizada

poner los sitios visitados en un conjunto a parte

DFS o BFS?


Cerradura transitiva

Outline

1 Grafos dirigidos






La cerradura transitiva de un grafo dirigido G es otro grafo dirigidocon los mismos vertices y donde vertices v y w son conectados ssiexiste en G un camino dirigido de v a w

1

3

0

5

2

67

8

4




Usando DFS, podemos soportar pedidas de cerradura transitiva entiempo constante, espacio proporcional a |V 2| y tiempo depreprocesamiento proporcional a |V |(|V |+ |A|)

Aplicar |V | veces, en cada vertice, el DFS para establecer los verticesalcanzables por cada vertice




t emp la t e <c l a s s Graph> c l a s s t c {Graph T; const Graph &G;void tcR ( i n t v , i n t w) {

T. i n s e r t ( Edge ( v , w ) ) ;typename Graph : : a d j I t e r a t o r A(G, w) ;f o r ( i n t t = A. beg ( ) ; !A . end ( ) ; t = A. nxt ( ) )

i f ( !T . edge ( v , t ) ) tcR ( v , t ) ;}

p u b l i c :t c ( const Graph &G) : G(G) , T(G .V( ) , t r u e ){ f o r ( i n t v = 0 ; v < G.V ( ) ; v++) tcR ( v , v ) ; }

boo l r e a c h ab l e ( i n t v , i n t w) { return T. edge ( v , w) ; }} ;




Una buena idea de la cerradura transitiva con la multiplicacion“logica” de matrices de adyacencia:

f o r ( i n t i =0; i<V; i++)f o r ( i n t j =0; j<V; j++) {

C[ i ] [ j ]=0;f o r ( i n t k=0;k<V; k++)

i f (A[ i ] [ k ] && B[ k ] [ j ] ) C [ i ] [ j ]=1;

Si se pone 1 en las bucles, entonces A2[i ][j ] indica nada mas laaccesibilidad de j a partir de i en un camino de tamano 1 o 2

f o r ( i n t k=0;k<V; k++)i f (A[ i ] [ k ] && A[ k ] [ j ] ) A2 [ i ] [ j ]=1;




Consecuencia: se puede calcular la cerradura transitiva de cualquiergrafo dirigido a partir de su matriz de adyacencia, anadiendo lasbucles i − i y calculando A|V |

Es la generalizacion del principio de A2: con A|V | examinaremos laalcanzabilidad con caminos de tamano inferior o igual a |V |. Loscaminos de tamano superior no son interesantes: pasannecesariamente por dos veces el mismo vertice, lo que induce uncamino de tamano ≤ |V |




Complejidad: necesitamos |V | multiplicaciones de matrices |V | × |V |.Cada multiplicacion cuesta como |V |3, lo que nos lleva a |V |4. . .

Ahora se puede mejorar un poco: nos podemos contentar de calcularA2, A4, . . .A2p

hasta que 2p > |V |. En este momento, tendremosA2p

= A|V | ya que no anade ningun otro camino las multiplicaciones> |V |. En total, complejidad |V |3 log |V |




Hay mucho mas eficiente: algoritmo de Warshall, en sitio sobre lamatriz de adyacencia y en una sola fase

f o r ( i n t k=0;k<V; k++)f o r ( i n t i =0; i<V; i++)

f o r ( i n t j =0; j<V; j++) {i f (A[ i ] [ k ] && A[ k ] [ j ] ) A [ i ] [ j ]=1;

Por que funciona?

primera iteracion: k = 0, despues tenemos A[i ][j ] = 1 si estanconectados desde el principio o si pueden ser conectados por 0(i-j o i-0-j)

segunda iteracion; k = 1, despues tenemos A[i ][j ] = 1 si estanconectados desde el principio o si pueden ser conectados por 0 y1 (i-j, i-0-j, i-1-j, i-0-1-j, i-1-0-j,i-0-1-0-j)




Por recursion: en la iteracion k , A[i ][j ] = 1 ssi existe un caminoorientado entre i y j que no incluye los vertices > k (excepto lasextremidades)

en k + 1, existe un camino orientado entre i y j que no incluyelos vertices > k +1 ssi o existe un camino que no incluye vertices> k (y entonces A[i ][j ] = 1 por la hipotesis de recursion) oexiste un camino que va de i a k + 1 (y no tiene vertices > k) yotro de k + 1 a j (igual) entonces el ciclo k + 1 lo habra activado

en O(|V |3) en tiempo, en O(|V |2) en espacio

se puede mejorar un poquitın, como?




t emp la t e <c l a s s tcGraph , c l a s s Graph> c l a s s TC {tcGraph T;p u b l i c :TC( const Graph &G) : T(G) {

f o r ( i n t s = 0 ; s < T.V ( ) ; s++)T. i n s e r t ( Edge ( s , s ) ) ;

f o r ( i n t i = 0 ; i < T.V ( ) ; i++)f o r ( i n t s = 0 ; s < T.V ( ) ; s++)

i f (T. edge ( s , i ) )f o r ( i n t t = 0 ; t < T.V ( ) ; t++)

i f (T. edge ( i , t ) )T. i n s e r t ( Edge ( s , t ) ) ;

}boo l r e a c h ab l e ( i n t s , i n t t ) const{ return T. edge ( s , t ) ; }

} ; ,J.B. Hayet Programacion, Febrero 2008 41 / 57



Aplicacion 1: calculo de los caminos mas cortos para todo par devertices; necesita un pequena modificacion de Warshall:

f o r ( i n t k=0;k<V; k++)f o r ( i n t i =0; i<V; i++)

f o r ( i n t j =0; j<V; j++) {i f (A[ i ] [ k ] + A[ k ] [ j ]<A[ i ] [ j ] )

A [ i ] [ j ]=A[ i ] [ k ] + A[ k ] [ j ] ;

Como inicializarlo para que funcione?




Aplicacion 1: tomar por ejemplo A[i ][j ] = V si no estan conectadosdirectamente, A[i ][j ] = 1 si lo estan, ası seleccionara el camino mascorto cada vez entre los que incluyen 0, 1, 2, . . . k

Estamos en un caso particular del algoritmo de Floyd (que es definidopara grafos ponderados)




Aplicacion 2: multiplicacion logica de matrices A y B . Formar:

C =

I A 00 I B0 0 I

y remarcar que la cerradura transitiva C 2 =

I A AB0 I B0 0 I

Deduces que puedes calcular el producto logico de dos matrices concualquier algoritmo de cerradura transitiva. Por el momento, en untiempo proporcional a |V |3 (pero tal vez se puede mejor ?)


Grafos dirigidos acıclicos

Outline

1 Grafos dirigidos





Interes

Gran interes en muchas areas en particular para representardependencias, causalidades, precedencias:

1

13

5

8

3

5

23

2 13 2

2

1112

1 1 1 1 1 1

11

85

32

1

13

Calculos de scheduling con restricciones de precedencia. . . Verificarque es DAG es facil (DFS)




Hay similaridad muy grande con arboles: son como arbolesdonde los nodos presentes varias veces han sido “hundidos” enun solo vertice (la unica diferencia es que

Notar que un recorrido sobre un arbol (sin checar si los nodos yahan sido visitados) (1) funciona sobre el DAG (porque no hayciclos) y (2) recorre exactamente como si el DAG habıa sidotransformado otra vez en arbol (vertices dedoblados)

de la misma manera que Arboles Binarios se puede definir DAGbinario como un DAG cuyos vertices tienen al maximo dos arcossalientes: sirven de representacion alternativa para arbolesbinarios (cual es la ventaja ?)



Ordenamiento topologico

Forma mas basica del scheduling:

encontrar una transformacion en el grafo de tal manera que nosde un orden de procesamiento de los vertices donde cada verticeesta procesado antes de los vertices que pueda alcanzar

tiene sentido solo para DAG, por que?

aplicaciones: robotica, clases que seguir. . .




Dos maneras de verlo:

1 Relabelling: cambias la manera de numerar a los vertices de talmanera que los arcos apuntan solo entre indices crecientes; es unmapeo mL sobre [0, V − 1], mL(v) representando los nuevosindices

2 Rearrangement: mueves tus vertices de tal manera a ponerles enuna linea horizontal, y tal que todas los arcos apunten deizquierda a la derecha, es otro mapeo mR que asigna un orden

Los dos son inversos: con un rearrangement deduces un relabeling yvice-versa: mL(mR(i)) = i . No hay unicidad!




5 4 2 3 1

5

42 1

3

12435

mR5 3 4 2 1

mL




El mR es el que buscamos, es un orden de visita de los vertices.

Propriedad: el reverso del orden postorden de los vertices en el grafonos da inmediatamente un mR posible para solucionar nuestroproblema.

Prueba: si v y w aparecen en este orden en la lista post-ordenentonces no puede haber v − w , y solo puede haber w − v . Enefecto, si habıa v − w , (1) no hubiera podido ser un back (no hayciclos) y (2) si es down, tree o cross, w hubiera sido terminado deexaminar antes de v (contradiccion)




El reverso:

t emp la t e <c l a s s Dag> c l a s s dagTS {const Dag &D;i n t cnt , t c n t ;v e c to r <int> pre , post , p o s t I ;void tsR ( i n t v ) {

pre [ v ] = cnt++;typename Dag : : a d j I t e r a t o r A(D, v ) ;f o r ( i n t t = A. beg ( ) ; !A . end ( ) ; t = A. nxt ( ) )

i f ( p re [ t ] == −1) tsR ( t ) ;po s t [ v ] = t cn t ; p o s t I [ t c n t++] = v ;

}




El reverso:

p u b l i c :dagTS ( const Dag &D) : D(D) , t c n t ( 0 ) , cnt ( 0 ) ,

p re (D.V( ) , −1) , po s t (D.V( ) , −1) , p o s t I (D.V( ) , −1){ f o r ( i n t v = 0 ; v < D.V ( ) ; v++)

i f ( p re [ v ] == −1) tsR ( v ) ; }i n t op e r a t o r [ ] ( i n t v ) const { return p o s t I [ v ] ; }i n t r e l a b e l ( i n t v ) const { return pos t [ v ] ; }




Para el orden correcto, usar los :

void tsR ( i n t v ) {pre [ v ] = cnt++;f o r ( i n t w = 0 ; w < D.V ( ) ; w++)

i f (D. edge (w, v ) )i f ( p re [w] == −1) tsR (w) ;

pos t [ v ] = t cn t ; p o s t I [ t c n t++] = v ;}




Post-orden con arcos entrantes: 5-3-4-2-1

5

42 1

3

12435,

J.B. Hayet Programacion, Febrero 2008 55 / 57


Ordenamiento topologico, otro metodo

Propriedad: un DAG tiene al menos un pozo y al menos una fuente.

Tiene al menos un pozo: sino se puede facilmente construir un ciclo.Y si tiene un pozo, su reverso (un DAG tambien) tambien, entoncestiene una fuente.Luego remarcar que puedes poner en tu orden cualquiera de lasfuentes existentes: mantener una cola de fuentes y mientras no estavacıa:

quitar una fuente y marcarla

actualizar grados entrantes

si hay grados entrante nulo, poner el vertice en la cola


grafos dirigidos -j. b. hayet

Documents