Algoritmos para identificar todas as Bases de ciclo em um grafo não direcionado

Question

Eu tenho um grafo não direcionado com Vertex V e Edge E. Eu estou procurando um algoritmo para identificar todas as bases de ciclo em que gráfico.

Tarjans algoritmo é um bom começo. Mas referência que eu tenho é sobre encontrar todos os ciclos , não base de ciclo de (que, por definição, é o ciclo de que não pode ser construída por união de outros ciclos).

Por exemplo, dê uma olhada no abaixo do gráfico:

Assim, um algoritmo seria útil. Se houver uma implementação existente (de preferência em C #), é ainda melhor!

Answer 1

Do que eu posso dizer, não só é o ponto palpite de Brian, mas uma proposição ainda mais forte mantém: cada aresta que não é na árvore geradora mínima acrescenta exatamente um novo "ciclo de base".

Para ver isto, vamos ver o que acontece quando você adiciona uma borda E isso não é no MST. Vamos fazer a maneira favorita de matemática para as coisas complicar e adicionar um pouco de notação;) Chame o gráfico original G, o gráfico antes de adicionar E G', e o gráfico depois de adicionar E G ''. Então, nós precisamos descobrir como é que a mudança "contagem de ciclo base" de G' a G ''.

Adicionando E devem fechar, pelo menos, um ciclo (de outro modo seria E no MST de L, em primeiro lugar). Então, obviamente, ele deve adicionar pelo menos um "ciclo de base" para os já existentes em G'. Mas será que isso adicionar mais de um?

Não pode adicionar mais de dois, uma vez que nenhuma vantagem pode ser um membro de mais de dois ciclos de base. Mas se E é um membro de dois ciclos de base, então a "união" destes dois ciclos de base deve ter sido um ciclo de base em G', por isso novamente temos que a mudança no número de ciclos é ainda um.

Ergo, para cada aresta não em MST você começa um novo ciclo de base. Assim, a "contar" parte é simples. Encontrar todas as arestas para cada ciclo de base é um pouco mais complicado, mas seguindo o raciocínio acima, eu acho que isso poderia fazê-lo (em pseudo-Python):

for v in vertices[G]:
    cycles[v] = []

for e in (edges[G] \ mst[G]):
    cycle_to_split = intersect(cycles[e.node1], cycles[e.node2])
    if cycle_to_split == None:
        # we're adding a completely new cycle
        path = find_path(e.node1, e.node2, mst[G])
        for vertex on path:
            cycles[vertex].append(path + [e]) 
        cycles
    else:
        # we're splitting an existing base cycle
        cycle1, cycle2 = split(cycle_to_split, e)
        for vertex on cycle_to_split:
            cycles[vertex].remove(cycle_to_split)
            if vertex on cycle1:
                cycles[vertex].append(cycle1)
            if vertex on cycle2:
                cycles[vertex].append(cycle2)

base_cycles = set(cycles)

Editar : o código deve encontrar todos os ciclos de base em um gráfico (as base_cycles definidos na parte inferior). As hipóteses são de que você sabe como:

• encontrar a árvore geradora mínima de um gráfico (MST [G])
• encontrar a diferença entre duas listas (bordas \ mst [G])
• encontrar uma interseção de duas listas
• encontrar o caminho entre dois vértices em um MST
• dividir um ciclo em duas adicionando uma vantagem extra para que (a função de divisão)

E principalmente segue a discussão acima. Para cada aresta não no MST, você tem dois casos: ou ele traz um novo ciclo de base, ou se divide um já existente em dois. Para controlar qual dos dois é o caso, nós acompanhamos todos os ciclos de base que um vértice é uma parte (usando os ciclos de dicionário).

Answer 2

fora do topo da minha cabeça, eu ia começar por olhar para qualquer algoritmo Minimum Spanning Tree (Prim, Kruskal, etc). Não pode haver ciclos mais bases (Se eu entendi corretamente) do que as arestas que não estão no MST ....

Answer 3

A seguir é a minha real não testado C # código para encontrar todos esses "ciclos de base":

public HashSet<List<EdgeT>> FindBaseCycles(ICollection<VertexT> connectedComponent)
{
   Dictionary<VertexT, HashSet<List<EdgeT>>> cycles =
       new Dictionary<VertexT, HashSet<List<EdgeT>>>();

   // For each vertex, initialize the dictionary with empty sets of lists of
   // edges
   foreach (VertexT vertex in connectedComponent)
       cycles.Add(vertex, new HashSet<List<EdgeT>>());

   HashSet<EdgeT> spanningTree = FindSpanningTree(connectedComponent);

   foreach (EdgeT edgeNotInMST in
           GetIncidentEdges(connectedComponent).Except(spanningTree)) {
       // Find one cycle to split, the HashSet resulted from the intersection
       // operation will contain just one cycle
       HashSet<List<EdgeT>> cycleToSplitSet =
           cycles[(VertexT)edgeNotInMST.StartPoint]
               .Intersect(cycles[(VertexT)edgeNotInMST.EndPoint]);

       if (cycleToSplitSet.Count == 0) {
           // Find the path between the current edge not in ST enpoints using
           // the spanning tree itself
           List<EdgeT> path =
               FindPath(
                   (VertexT)edgeNotInMST.StartPoint,
                   (VertexT)edgeNotInMST.EndPoint,
                   spanningTree);

           // The found path plus the current edge becomes a cycle
           path.Add(edgeNotInMST);

           foreach (VertexT vertexInCycle in VerticesInPathSet(path))
               cycles[vertexInCycle].Add(path);
       } else {
            // Get the cycle to split from the set produced before
            List<EdgeT> cycleToSplit = cycleToSplitSet.GetEnumerator().Current;
            List<EdgeT> cycle1 = new List<EdgeT>();
            List<EdgeT> cycle2 = new List<EdgeT>();
            SplitCycle(cycleToSplit, edgeNotInMST, cycle1, cycle2);

            // Remove the cycle that has been splitted from the vertices in the
            // same cicle and add the results from the split operation to them 
            foreach (VertexT vertex in VerticesInPathSet(cycleToSplit)) {
                cycles[vertex].Remove(cycleToSplit);
                if (VerticesInPathSet(cycle1).Contains(vertex))
                     cycles[vertex].Add(cycle1);
                     if (VerticesInPathSet(cycle2).Contains(vertex))
                         cycles[vertex].Add(cycle2); ;
            }
       }
   }
   HashSet<List<EdgeT>> ret = new HashSet<List<EdgeT>>();
   // Create the set of cycles, in each vertex should be remained only one
   // incident cycle
       foreach (HashSet<List<EdgeT>> remainingCycle in cycles.Values)
           ret.AddAll(remainingCycle);

       return ret;
}

Oggy de código era muito bom e clara , mas eu tenho certeza que ele contém um erro, ou ele me que não entendem seu código python pseudo é:)

cycles[v] = []

não pode ser um vértice indexada dicionário de listas de bordas. Na minha opinião, ele tem que ser um vértice indexada dicionário de conjuntos de listas de bordas.

E, para adicionar um precisation:

for vertex on cycle_to_split:

ciclo-a-divisão é provavelmente um ordenou lista de bordas para fazer uma iteração através vértices que você tem de convertê-lo em um conjunto de vértices. Ordem aqui é insignificante, por isso é uma alghoritm muito simples.

repito, este é não testado e uncomplete código, mas é um passo em frente. Ele ainda requer uma estrutura gráfico apropriado (i usar uma lista incidency) e muitas alghoritms gráfico você pode encontrar em livros de texto como Cormen. Eu não era capaz de encontrar FindPath () e SplitCycle () nos livros de texto, e são muito difícil de código-los em tempo linear do número de arestas + vértices no gráfico. Irá relatá-los aqui quando eu vou testá-los.

Muito obrigado Oggy!

Answer 4

A forma padrão para detectar um ciclo é usar dois iterators - para cada iteração, uma avança um passo e os outros dois. Deve haver um ciclo, eles vão em algum ponto ponto para o outro.

Esta abordagem pode ser estendida para registrar os ciclos de modo encontrados e seguir em frente.