Fórum de discussão

Ois,

Vitor, muito obrigado por levantar essa questão no fórum!

Tive um leve problema ao testar meu EP por conta do cloneDigraph.

Foi necessário arrumar o comportamento da minha cloneDigraph pra coisas funcionarem corretamente.

Opsss.
Desculpem.
A sua função estava funcionando corretamente!
A especificação que dei de cloneDigraph() foi despretensiosa.
A sua cloneDigraph() estava melhor que a minha!
Eu deveria ter feito como você e o algs4 e retornar um clone da representação de G.
Isso parece ser mais apropriado.
A minha cloneDigraph() clonava o digrafo, não sua representação.

Algumas funções que têm sido pedidas a vocês não tem resultado único.
O EP14 fala de uma representação topológica de G.
A representação obtida depende da representação do digrafo e da maneira que fazemos a busca DFS.

A propósito, só para insistir, esse negócio de representação topológica não existe, Ok?!
Foi apenas um nome que por falta de criativiade inventei para chamar a bagaça.

Vou aproveitar a oportunidade e me estender um pouco negócio de digrafos e suas represetações.

Um digrafo (grafo = digrafo simétrico) é um objeto combinátorio: vértice + arcos (arestas) + relação de adjacência.
Um digrafo pode ser representado no computador de várias formas, inclusive vetor de listas de adjacência que temos usado.

Um mesmo digrafo tem várias representações.
Embaralhar a linhas do arquivo tinyDG.txt correspondente aos arcos alteram a representação do digrafo.
Todas são representações do mesmo digrafo.

Um coisa bacana dos algoritmos que temos visto é que a representação do digrafo é irrelevante.
Inclusive temos construído florestas DFS de maneiras arbitrárias.
O trecho de código abaixo é conveniente para explorarmos um digrafo em ordem DFS, mas é arbitrário:

for (int v = 0; v < G.V(); v++) {
    if (!marked[v]) {
        dfs(G, v);
    }
}

Por alguma razão misteriosa poderíamos construir as florestas DFS de outra maneira:

for (int v = G.V()-1; v >= 0; v--) {
    if (!marked[v]) {
        dfs(G, v);
    }
}

É muito bacana que independentemente da representação do digrafo e independentemente da maneira que que fazemos a busca DFS (independentemente da floresta DFS) as funções que vimos (e uma infinidade que não vimos) fazemo o seu serviço com perfeição encontrando:

• um caminho até um dado vértice
• o corte separando dois vértices
• uma ordenação topológica;
• um ciclo;
• uma bipartição;
• um ciclo ímpar;
• as componentes conexas de um grafo;
• as componentes fortes de um digrafo;
• ...

Certamente há problemas em que a representação do (di)grafo e a maneira que o exploramos faz diferença.

Esse foram os meus dois centevas.
Novamente, Vitor, muito obrigado por compartilhar as suas observações.