59
Mestrado em Informática Programa de Pós Graduação em Informática Universidade Federal do Espírito Santo Teoria dos Grafos 2014-1 Seminário: enumeração de ciclos elementares Professora: Maria Claudia Silva Boeres Luiz Kill Vitória, Junho de 2014

Elementary Circuits Enumeration in Graphs

Embed Size (px)

Citation preview

Page 1: Elementary Circuits Enumeration in Graphs

Mestrado em InformáticaPrograma de Pós Graduação em Informática

Universidade Federal do Espírito Santo

Teoria dos Grafos 2014-1Seminário: enumeração de ciclos elementares

Professora: Maria Claudia Silva Boeres

Luiz Kill

Vitória, Junho de 2014

Page 2: Elementary Circuits Enumeration in Graphs

Trabalho apresentado na disciplina “Teoria dos Grafos”, integrante do Programa de Pós Graduação em Informática da Universidade Federal do Espírito Santo, período 2014-1.

2

Page 3: Elementary Circuits Enumeration in Graphs

Agenda

• Definição do problema

• Revisão de conceitos

• Modelagem do problema

• Revisão bibliográfica

• Implementação

• Conclusão

3

Page 4: Elementary Circuits Enumeration in Graphs

Agenda

4

• Definição do problema

• Revisão de conceitos

• Modelagem do problema

• Revisão bibliográfica

• Implementação

• Conclusão

Page 5: Elementary Circuits Enumeration in Graphs

Definição do problemaCadastro de serviços compostos do ERP SAP

5

Page 6: Elementary Circuits Enumeration in Graphs

Definição do problema

Quando o Insumo X tem seu preço atualizado:– Recalcular o preço do Serviço 3– Recalcular o preço do Serviço 2– Recalcular o preço do Serviço 1

6

Cadastro de serviços compostos do ERP SAP

Page 7: Elementary Circuits Enumeration in Graphs

Definição do problema

Quando o Insumo X tem seu preço atualizado:– Recalcular o preço do Serviço 3 -> preço errado!– Recalcular o preço do Serviço 2 -> preço errado!– Recalcular o preço do Serviço 1 -> preço errado!

7

Cadastro de serviços compostos do ERP SAP

Page 8: Elementary Circuits Enumeration in Graphs

Definição do problema

8

Como detectar a existência de ciclos na estrutura?

DFT, ordenação topológica...

Como listar todos os ciclos existentes? ???

 

Page 9: Elementary Circuits Enumeration in Graphs

Agenda

9

• Definição do problema

• Revisão de conceitos

• Modelagem do problema

• Revisão bibliográfica

• Implementação

• Conclusão

Page 10: Elementary Circuits Enumeration in Graphs

Revisão de conceitos

CicloPercurso fechado sem repetição de arestas, pode repetir vértices.

Ciclo elementarPercurso fechado sem repetição de arestas e com repetição apenas do vértice inicial.

10

Fo

nte:

http

://en

.wik

iped

ia.o

rg/w

iki/C

ycle

_(g

rap

h_th

eory

)

Page 11: Elementary Circuits Enumeration in Graphs

Revisão de conceitos

Componente fortemente conexo

Subgrafo onde todos os vértices são acessíveis a partir de qualquer vértice.

11

http

://e

n.w

ikip

edia

.org

/wik

i/Str

ong

ly_c

onne

cted

_com

pone

nt

Subgrafo induzido por vértices

Subgrafo de G cujo conjunto de vértices é V´ e o conjunto de arestas é o conjunto de todas as arestas de G com ambos extremos em V´ é chamado de subgrafo de G induzido por V'.

Page 12: Elementary Circuits Enumeration in Graphs

Agenda

12

• Definição do problema

• Revisão de conceitos

• Modelagem do problema

• Revisão bibliográfica

• Implementação

• Conclusão

Page 13: Elementary Circuits Enumeration in Graphs

Modelagem do problema

13

Grafo de serviços compostos:

- Desconexo- Direcionado- Insumos nos vértices

terminais- Número de vértices: 21319- Número de arestas: 115227

Page 14: Elementary Circuits Enumeration in Graphs

Modelagem do problema

14

Grafo de serviços compostos:

Page 15: Elementary Circuits Enumeration in Graphs

Modelagem do problema

15

* http://stackoverflow.com/questions/14146165/find-all-the-paths-forming-simple-cycles-on-an-undirected-graph

 

1019* 

Page 16: Elementary Circuits Enumeration in Graphs

Modelagem do problema

16

Número de ciclos elementares em um grafo direcionado completo [1]

 

Page 17: Elementary Circuits Enumeration in Graphs

Modelagem do problema

17

http://flowproblem.ru/cycles/all-simple-cycles

Número de ciclos elementares em um grid nxn

Page 18: Elementary Circuits Enumeration in Graphs

Modelagem do problema

18

NP-completo [4]

Page 19: Elementary Circuits Enumeration in Graphs

Modelagem do problema

19

http://people.mpi-inf.mpg.de/~mehlhorn/ftp/EriceTalks.pdf

O problema de enumeração de ciclos possui muitas aplicações práticas:

• Reconstrução de superfícies

Page 20: Elementary Circuits Enumeration in Graphs

Modelagem do problema

20

O problema de enumeração de ciclos possui muitas aplicações práticas:

• Prevenção e recuperação de deadlocks em SOs e RDMSs

http://en.wikipedia.org/wiki/Wait-for_graph

Page 21: Elementary Circuits Enumeration in Graphs

Modelagem do problema

O problema de enumeração de ciclos possui muitas aplicações práticas:

• Problema do isomorfismo de grafos [7]

• Análise da estrutura de compostos químicos [8]

• Design e análise de redes de comunicação confiáveis

• Análise de causa em redes de relacionamento celular [9]

• ...

21

Page 22: Elementary Circuits Enumeration in Graphs

Modelagem do problema

22

Ciclos é uma

área ativa da

teoria dos

grafos!

Page 23: Elementary Circuits Enumeration in Graphs

Agenda

23

• Definição do problema

• Revisão de conceitos

• Modelagem do problema

• Revisão bibliográfica

• Implementação

• Conclusão

Page 24: Elementary Circuits Enumeration in Graphs

Revisão bibliográfica

Classificação dos algoritmos:

• Search space algorithms• Backtrack algorithms• Adjacency matrix algorithms

24

Page 25: Elementary Circuits Enumeration in Graphs

Search space algorithms

• Nessa abordagem os ciclos são investigados em um espaço de busca apropriado

• Para grafos não direcionados o cycle space vector foi a estrutura mais abordada ao longo do tempo [6]

• Cycle space -> contém todos os ciclos do grafo

• Cycle basis -> contém todos os ciclos elementares a partir dos quais todos os ciclos do espaço podem ser derivados

25Revisão bibliográfica

Page 26: Elementary Circuits Enumeration in Graphs

Search space algorithms• Algoritmo construtivo:

– Gere uma cycle basis

– Gere todos os vetores (ciclos) do cycle space vector a partir da

cycle basis ([21])

• Esses algoritmos são exponenciais no tamanho do espaço de busca, logo são exponenciais em

• No caso especial de grafos planares foi proposto em [10] um algoritmo com tempo

26Revisão bibliográfica

Page 27: Elementary Circuits Enumeration in Graphs

Backtrack algorithms•

27Revisão bibliográfica

Page 28: Elementary Circuits Enumeration in Graphs

Backtrack algorithms

28Revisão bibliográfica

DFT é um algoritmo de backtracking:

Page 29: Elementary Circuits Enumeration in Graphs

Adjacency matrix algorithms•

29Revisão bibliográfica

Page 30: Elementary Circuits Enumeration in Graphs

 

Adjacency matrix algorithms

30Revisão bibliográfica

Page 31: Elementary Circuits Enumeration in Graphs

O algoritmo de Johnson (1975) [1]

31Revisão bibliográfica

 

Page 32: Elementary Circuits Enumeration in Graphs

O algoritmo de Johnson (1975) [1]

32Revisão bibliográfica

Page 33: Elementary Circuits Enumeration in Graphs

O algoritmo de Johnson (1975) [1]

33Revisão bibliográfica

Page 34: Elementary Circuits Enumeration in Graphs

O algoritmo de Johnson (1975) [1]

34Revisão bibliográfica

Page 35: Elementary Circuits Enumeration in Graphs

O algoritmo de Hawick & James (2008) [15]

35Revisão bibliográfica

• Estende Johnson’s para laços e arestas múltiplas

Page 36: Elementary Circuits Enumeration in Graphs

O algoritmo de Ferreira (2012) [2]

36Revisão bibliográfica

 

Page 37: Elementary Circuits Enumeration in Graphs

O algoritmo de Ferreira (2012) [2]

37Revisão bibliográfica

Page 38: Elementary Circuits Enumeration in Graphs

Agenda

38

• Definição do problema

• Revisão de conceitos

• Modelagem do problema

• Revisão bibliográfica

• Implementação

• Conclusão

Page 39: Elementary Circuits Enumeration in Graphs

Implementação

39

Page 40: Elementary Circuits Enumeration in Graphs

Implementação

40

• Algoritmo escolhido: Hawick & James [15]

– Queremos identificar a presença de laços e arestas múltiplas no domínio do

problema

• Biblioteca de apoio: JGraphT 0.9.0 (Java)

– DirectedPseudograph

– DefaultDirectedGraph

– addVertex()

– addEdge()

– successorListOf()

– vertexSet()

– edgeSet()

Page 41: Elementary Circuits Enumeration in Graphs

Implementação

41

• Benchmark (usando grafos simples): JGraphT

– Johnson

– Szwarcfiter and Lauer

– Tarjan

– Tiernan

Page 42: Elementary Circuits Enumeration in Graphs

Cenário de teste 1

42

Implementação

Page 43: Elementary Circuits Enumeration in Graphs

Cenário de teste 1

43Implementação

Page 44: Elementary Circuits Enumeration in Graphs

Cenário de teste 2

44

Implementação

(Hands on)

Page 45: Elementary Circuits Enumeration in Graphs

Cenário de teste 3

45

Implementação

* http://mathworld.wolfram.com/Pseudograph.html

Page 46: Elementary Circuits Enumeration in Graphs

Cenário 3

46Implementação

Page 47: Elementary Circuits Enumeration in Graphs

Cenário 3

47Implementação

Page 48: Elementary Circuits Enumeration in Graphs

Benchmark

48

Implementação

Page 49: Elementary Circuits Enumeration in Graphs

Benchmark

49Implementação

Page 50: Elementary Circuits Enumeration in Graphs

Benchmark

50Implementação

Page 51: Elementary Circuits Enumeration in Graphs

Benchmark

51Implementação

Page 52: Elementary Circuits Enumeration in Graphs

Agenda

52

• Definição do problema

• Revisão de conceitos

• Modelagem do problema

• Revisão bibliográfica

• Implementação

• Conclusão

Page 53: Elementary Circuits Enumeration in Graphs

Conclusão

53

Page 54: Elementary Circuits Enumeration in Graphs

Conclusão

54

• O algoritmo implementado deve estar disponível na próxima versão da API

JGraphT

Page 55: Elementary Circuits Enumeration in Graphs

55

Dúvidas

Page 56: Elementary Circuits Enumeration in Graphs

56

Obrigado!

Luiz [email protected]

Page 57: Elementary Circuits Enumeration in Graphs

Referências[1] D. B. Johnson. Finding all the elementary circuits of a directed graph. SIAM J. Comput., 4(1):77–84, 1975.

[2] R. Ferreira, R. Grossi, A. Marino, N. Pisanti, R. Rizzi, and G. Sacomoto. Optimal Listing of Cycles and st-Paths in Undirected Graphs. Eprint arXiv:1205.2766, 2012.

[3] M. Safar, F. Mahdi and K. Mahdi. An Algorithm for Detecting Cycles in Undirected Graphs using CUDA Technology. International Journal on New Computer Architectures and Their Applications (IJNCAA) 2(1): 194-213, 2012.

[4] R. M. Karp. Reducibility among combinatorial problems, Complexity of Computer Computations. Plenum, New York, 1972, 85-103.

57

Page 58: Elementary Circuits Enumeration in Graphs

Referências[6] R. Diestel. Graph Theory (Graduate Texts in Mathematics). Springer, 2005.

[7] J. T. Welch, Jr. A mechanical analysis of the cyclic structure of undirected linear graphs. J. ACM, 13:205–210, 1966.

[8] E.H. Sussenguth. A graph-theoretical algorithm for matching chemical structures. J. Chem. Doc., 5:36–43, 1965.

[9] S. Klamt, A. Kamp. Computing paths and cycles in biological interaction graphs. BMC Bioinformatics 2009, 10:181.

[10 M. M. Syslo. An efficient cycle vector space algorithm for listing all cycles of a planar graph. SIAM J. Comput., 10(4):797–808, 1981.

58

Page 59: Elementary Circuits Enumeration in Graphs

Referências[11] J. C. Tiernan. An efficient search algorithm to find the elementary circuits of a graph. Communonications ACM, 13:722–726, 1970.

[12] R. E. Tarjan. Enumeration of the elementary circuits of a directed graph. SIAM J. Comput., 2(3):211–216, 1973.

[13] J. Ponstein. Self-avoiding paths and the adjacency matrix of a graph. SIAM Journal on Applied Mathematics, 14:600–609, 1966.

[14] F. Harary. The Determinant of the Adjacency Matrix of a Graph. SIAM Review, Vol. 4, No. 3. (Jul., 1962), pp. 202-210.

[15] K. A. Hawick, H. A. James. Enumerating Circuits and Loops in Graphs with Self-Arcs and Multiple-Arcs. Computational Science Technical Note CSTN-013, 2008.

59