Rimozione delle dipendenze del ciclo da un grafico diretto con bordi fissi

Question

Ho un grafico ciclico diretto. Alcuni bordi sono FISSI e potrebbero non essere rimossi. Gli altri bordi possono essere rimossi per interrompere un ciclo.

Qual è il modo migliore per rimuovere i cicli in questo grafico? Il traversal dovrebbe essere il più possibile un DFS e iniziare in un dato nodo.

Answer 1

Ho usato il seguente algoritmo per risolvere il mio problema:

Inizia con un grafico di tutti i bordi fissi contrassegnati come confermati

Da un nodo iniziale, ricorrere a tutti i bordi confermati nonché a quelli non ancora confermati. Ma quando stai per riemergere un bordo non ancora confermato, controlla innanzitutto se il nodo a cui va il bordo ha un percorso, seguendo i bordi confermati, a un nodo nella struttura di ricerca corrente (ovvero un nodo con un < em> visitando set di flag). Questo controllo deve essere eseguito in modo ricorsivo seguendo tutti i bordi confermati, ma questo è troppo lento per me, quindi mi accontenterò qui solo per verificare se il nodo è in visita o se qualcuno dei nodi a cui è confermato è connesso sta visitando. Questo coprirà la maggior parte dei miei casi ma lascerà occasionalmente dei cicli nel grafico.

Dopo il passaggio precedente uso l'algoritmo di Tarjan per trovare i componenti fortemente connessi lasciati nel grafico (questo può essere fatto in tempo O (V + E)). Il numero di componenti fortemente connessi sarà molto piccolo nei miei casi, quindi passo attraverso ogni componente fortemente connesso e rimuovo un bordo rimovibile ciascuno. Quindi faccio di nuovo questo passaggio fino a quando non rimangono più cicli nel grafico.

Funziona bene ed è abbastanza veloce.

Answer 2

Quello che puoi fare è usare l'algoritmo di Dijkstra: inizia con un grafico contenente solo i bordi FISSI. Quindi applica un adattamento dell'algoritmo a partire dal grafico che hai già:

1. Inizia con il nodo iniziale e tutti i bordi FISSI nel componente del nodo iniziale. Supponiamo che questo sia un albero.
2. Aggiungi il nodo più vicino all'albero.
3. Aggiungi anche tutti i bordi FISSI nel componente del nodo che hai appena aggiunto.
4. Se tutti i nodi sono nella struttura, terminare. Altrimenti, vai al passaggio 4.

Questo, ovviamente, presuppone che il grafico costituito solo dai bordi FISSI non contenga cicli. In tal caso, non esiste una soluzione (vale a dire un sottografo senza bordi, ma contenente tutti i bordi FISSI).

Per i grafici diretti, è un po 'più complicato. In questo caso, qualsiasi componente del grafico dei bordi FISSI dovrebbe essere un albero. Nell'algoritmo simile a Dijkstra, solo le radici di questi nodi dovrebbero essere candidate da aggiungere all'albero.

Answer 3

il problema è sottovalutato perché non è stato specificato ad es. se il grafico deve rimanere collegato o se si desidera rimuovere un "piccolo" numero di bordi non fissi per interrompere tutti i cicli o se è veramente necessario rimuovere il numero minimo globale di bordi non fissi.

Se il grafico non deve rimanere collegato, basta attraversare tutti i bordi e rimuovere tutti quelli non FISSI. Ciò rimuove tutti i cicli che è possibile rimuovere senza rimuovere i bordi FISSI.

Se vuoi un semplice algoritmo avido per rimuovere i bordi che è DFS puro, puoi usare qualcosa del genere SE il grafico rimane collegato anche quando rimuovi alcuni dei bordi non FISSI:

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]