Algoritmi per creare una rappresentazione tabellare di un DAG?

Question

Dato un DAG, in cui ogni nodo appartiene a una categoria, come può questo grafico essere trasformato in una tabella con una colonna per ciascuna categoria? La trasformazione non deve essere reversibile, ma dovrebbe conservare informazioni utili sulla struttura del grafico; e dovrebbe essere una trasformazione 'naturale', nel senso che una persona guardando il grafico e la tabella non dovrebbe essere sorpresa da una delle righe. Dovrebbe anche essere compatto, cioè hanno poche righe.

Ad esempio in un grafico di nodi a1, b1, b2, c1 con bordi A1-> b1, A1-> b2, B1-> c1, B2> c1 (cioè un grafico a forma di diamante) che ci si aspetta di vedere la tabella seguente:

a  b  c
--------
a1 b1 c1
a1 b2 c1

Ho pensato a questo problema un po ', ma sto avendo problemi a venire con un algoritmo che dà risultati intuitivi su alcuni grafici. Si consideri il grafico A1, B1, C1 con bordi A1-> c1, B1-> c1. Mi piacerebbe l'algoritmo per produrre questa tabella:

a  b  c 
--------
a1 b1 c1

Ma forse dovrebbe produrre questo, invece:

a  b  c 
--------
a1    c1
a1 b1

Sto cercando idee creative e intuizioni sul problema. Sentitevi liberi di variare a semplificare o limitare il problema se si pensa che sarà di aiuto.

Brainstorm via!

Modifica:

La trasformazione deve sempre produrre lo stesso insieme di righe, anche se l'ordine delle righe non è importante.

La tabella dovrebbe comportarsi bene durante l'ordinamento e filtraggio utilizzando, ad esempio, Excel. Ciò significa che i nodi mutliple non può essere imballato in una singola cella della tabella -. Solo nodo per cella

Answer 1

Ecco quello che ho finito per fare:

• Trova tutti i percorsi provenienti da un nodo, senza in-bordi. (Potrebbe essere costoso per alcuni grafici, ma funziona per il mio)
• Traverse ciascun percorso per raccogliere una fila di valori
• compatte le righe

compattando le righe è dones come segue.

• Per ogni coppia di colonne x, y
  • costruire una mappa di ogni valore di x alla sua possibili valori di y
  • Crea un'altra mappa Per le voci che hanno solo un valore distinto di y, mappando il valore di x al valore di y singola.
• Riempire gli spazi vuoti che utilizzano queste mappe. Nel compilare un valore, per controllare sbozzati correlati che possono essere riempiti.

Questo dà un'uscita molto compatto e sembra soddisfare tutte le mie esigenze.

Answer 2

Quello che vi serve è una variante del topologica di smistamento . Questo è un algoritmo che "ordinamenti" vertici grafico come bordo a---->b significava a > b. Poiché il grafico è un DAG, non ci sono cicli in esso e questo rapporto > è transitiva, quindi esiste almeno un ordine di ordinamento.

Per il grafico a forma di diamante esistono due ordini topologici:

a1 b1 b2 c1
a1 b2 b1 c1

articoli b1 e b2 non sono collegati, anche indirettamente, di conseguenza, possono essere collocati in qualsiasi ordine.

Dopo aver risolto il grafico, si sa un'approssimazione di ordine. La mia proposta è di riempire il tavolo in maniera semplice (1 vertex per riga) e poi "compatta" il tavolo. Effettuare una cernita e scegliere la sequenza che hai come output. Riempire il tavolo da cima a fondo, l'assegnazione di un vertice alla relativa colonna:

a  b  c
--------
a1 
   b2 
   b1
      c1

Ora compatta tabella a piedi da cima a fondo (e quindi far passare simile dal basso in alto). Su ogni iterazione, si dà un'occhiata più da vicino a una riga "corrente" (contrassegnato come =>) e alla riga "next".

1. Se in una colonna nodi nodo corrente e successivo differiscono , fare nulla per questa colonna:

        from     ---->      to
      X  b  c            X  b  c
      --------           --------
   => X1 .  .           X1 .  .
      X2 .  .        => X2 .  .
   

2. Se in un X colonna della riga successiva v'è nessun vertice (cella è vuota) e nella riga corrente c'è vertice X1, allora talvolta necessario riempire la cella vuota con un vertice della riga corrente . Ma non sempre: si desidera che la tabella di essere logico, non è vero? Quindi copiare il vertice se e solo se non c'è b--->X1 bordo, c--->X1, ecc, per tutti i vertici in riga corrente.

        from     --->      to
      X  b  c           X  b  c
      --------          --------
   => X1 b  c           X1 b  c
         b1 c1       => X1 b1 c1
   

(Modifica :) Dopo la prima (in avanti) e secondo (indietro) passa, avrete tali tabelle:

 first       second
a  b  c     a  b  c 
--------    --------
a1          a1 b2 c1     
a1 b2       a1 b2 c1  
a1 b1       a1 b1 c1  
a1 b1 c1    a1 b1 c1

Quindi, è sufficiente rimuovere righe pari e il gioco è fatto:

a  b  c 
--------
a1 b2 c1  
a1 b1 c1  

E si dovrebbe ottenere un buon tavolo. O (n ^ 2).

Answer 3

Che ne dite di compattare tutti i nodi raggiungibili da un nodo insieme in una cella? Ad esempio, il primo DAG dovrebbe essere simile:

a   b        c
---------------
a1  [b1,b2]  
    b1       c1
    b2       c1

Answer 4

Sembra una mappa sistema ferroviario con le stazioni all'interno di zone (a, b, c).

Si potrebbe essere generando una tabella di tutti i percorsi possibili in una direzione. In questo caso "A1, B1, C1" sembrerebbe implicare A1-> b1 in modo da non formattare in quel modo, se avete solo A1-> C1, B1-> c1

Si potrebbe decidere di produrre una tabella che elenca i percorsi più lunghi di partenza nella zona A, con ciascun bordo solo una volta, terminando con brevi percorsi rimanenti. O consentono bordi per essere riutilizzati solo se si collegano i bordi inutilizzati o estendere un percorso.

In altre parole, fare una ricerca in profondità, cercando di non riutilizzare bordi (rifiutano qualsiasi percorso che non include margini inutilizzati, e facoltativamente Tagliare i bordi utilizzati alle estremità).