Remoção de dependências do ciclo de um gráfico direcionado com bordas fixas

Question

Eu tenho um gráfico cíclico direcionado. Algumas arestas são fixas e não podem ser removidas. As outras arestas podem ser removidas para quebrar um ciclo.

Qual é a melhor maneira de remover os ciclos neste gráfico? A travessia deve ser o máximo possível de DFS e começar em um determinado nó.

Answer 1

Eu usei o algoritmo a seguir para resolver meu problema:

Comece com um gráfico de todas as bordas fixas marcadas como confirmado

De um nó de início, recorrente a todas as bordas confirmadas e também das ainda não confirmadas. Mas quando você está prestes a recorrer a uma borda ainda não confirmada, verifique se o nó que a borda segue tem um caminho, seguindo as bordas confirmadas, para um nó na árvore de busca atual (ou seja, um nó com um visitando conjunto de bandeira). Essa verificação deve ser feita de forma recursiva seguindo todas as bordas confirmadas, mas isso é muito lento para mim, então vou me estabelecer aqui para verificar se o nó está visitando ou se algum dos nós é confirmado conectado está visitando. Isso cobrirá a maioria dos meus casos, mas ocasionalmente deixará ciclos no gráfico.

Após a etapa acima, uso o algoritmo de Tarjan para encontrar os componentes fortemente conectados deixados no gráfico (isso pode ser feito no tempo O (V + E)). O número de componentes fortemente conectados será muito pequeno nos meus casos, então eu apenas passo por cada componente fortemente conectado e removo uma borda removível cada. Então eu faço essa etapa novamente até que não haja mais ciclos no gráfico.

Isso funciona bem e é rápido o suficiente.

Answer 2

O que você pode fazer é usar o algoritmo de Dijkstra: inicie com um gráfico que contém apenas as bordas fixas. Em seguida, aplique uma adaptação do algoritmo começando com o gráfico que você já possui:

1. Comece com o nó inicial e todas as bordas fixas no componente do nó inicial. Suponha que essa seja uma árvore.
2. Adicione o nó mais próximo da árvore.
3. Adicione também quaisquer arestas fixas no componente do nó que você acabou de adicionar.
4. Se todos os nós estiverem na árvore, termine. Caso contrário, vá para a etapa 4.

Obviamente, isso pressupõe que o gráfico consistindo apenas nas bordas fixas não contenha ciclos. Se isso acontecer, não há solução (isto é, um subgraph sem arestas, mas contendo todas as bordas fixas).

Para gráficos direcionados, é um pouco mais complicado. Nesse caso, qualquer componente do gráfico de bordas fixas deve ser uma árvore. No algoritmo do tipo Dijkstra, apenas raízes desses nós devem ser candidatos a serem adicionados à árvore.

Answer 3

O problema é subestimado porque você não especificou, por exemplo, se o gráfico precisar permanecer conectado ou se você deseja remover um número "pequeno" de bordas não fixadas para quebrar todos os ciclos, ou se você realmente precisar do número mínimo global de bordas não fixadas a serem removidas.

Se o gráfico não precisar permanecer conectado, basta atravessar todas as bordas e remover todas as não fixadas. Isso remove todos os ciclos que você pode remover sem remover bordas fixas.

Se você deseja um algoritmo ganancioso simples para remover as bordas que são puras DFs, você pode usar algo assim se o gráfico permanecer conectado também quando você remover algumas das bordas não fixadas:

proc recurse(vertex n, vertex_set ns)
  if (n appers_in ns) // it is a cycle
    return BREAK_CYCLE
  else for (e in list_outgoing_edges_from(n))
    np = e.destination
    result = recurse(np, add_to_set(ns, np))
    if (result == BREAK_CYCLE)
      if (e.FIXED)
        return BREAK_CYCLE
      else
        [remove e from the graph]
        return RETRY
      else if (result == RETRY)
        return recurse(n, ns)
    return FINISHED

if (recurse (your_initial_node, empty_vertex_set()))
  [graph contains a cycle through only FIXED edges]
else
  [the reachable component from initial_node has no longer cycles]