Come rappresentare un grafico con più spigoli consentiti tra nodi e spigoli che possono scomparire in modo selettivo

Question

Come rappresentare un grafico con più spigoli consentiti tra nodi e spigoli che possono scomparire in modo selettivo

#1 da (6 voti)
#2 da (1 voti)

11

Sto cercando di capire quale tipo di struttura dati utilizzare per modellare un utilizzo ipotetico e idealizzato della rete.

Nel mio scenario, un certo numero di utenti che sono ostili l'un l'altro stanno tutti cercando di formare reti di computer in cui sono note tutte le potenziali connessioni. I computer che un utente deve connettere potrebbero non essere uguali a quelli che un altro utente ha bisogno di connettere, però; l'utente 1 potrebbe aver bisogno di collegare i computer A, B e D mentre l'utente 2 potrebbe aver bisogno di collegare i computer B, C ed E.

^{Immaginegenerataconl'aiutodi Creatore grafico NCTM}

Penso che il nucleo di questo sarà un grafico ciclico non orientato, con nodi che rappresentano computer e spigoli che rappresentano cavi Ethernet. Tuttavia, a causa della natura dello scenario, ci sono alcune caratteristiche non comuni che escludono le liste di adiacenza e le matrici di adiacenza (almeno, senza modifiche non banali):

possono diventare limitati: utilizzare; cioè, se un utente acquisisce una determinata connessione di rete, nessun altro utente può utilizzare quella connessione
- nell'esempio, l'utente verde non può connettersi al computer A, ma l'utente rosso ha collegato B a E pur non avendo un collegamento diretto tra loro
in alcuni casi, una data coppia di nodi sarà collegata da più di un bordo
- nell'esempio, ci sono due cavi indipendenti che vanno da D a E, quindi gli utenti verdi e blu erano entrambi in grado di connettere direttamente quelle macchine; tuttavia, il rosso non può più effettuare tale connessione
se due computer sono collegati da più di un cavo, ciascun utente può possedere non più di uno di quei cavi

Avrò bisogno di fare diverse operazioni su questo grafico, come ad esempio:

determinare se una determinata coppia di computer è connessa per un determinato utente
identificare il percorso ottimale per un determinato utente per connettere computer di destinazione
che identifica la connessione del computer a latenza più elevata per un determinato utente (ovvero il percorso più lungo senza diramazione)

Il mio primo pensiero è stato semplicemente creare una collezione di tutti i bordi, ma è terribile per la ricerca. La cosa migliore che posso pensare di fare ora è modificare un elenco di adiacenza in modo che ogni elemento dell'elenco contenga non solo la lunghezza del bordo ma anche il suo costo e il suo attuale proprietario. È un approccio sensato? Supponendo che lo spazio non sia un problema, sarebbe ragionevole creare più copie del grafico (una per ogni utente) piuttosto che un singolo grafico?

data-structures graph

posta Pops 15.08.2014 - 18:02

fonte

2 risposte

Leggi altre domande sui tag data-structures graph

Git workflow per più team La migliore strategia per segnalare i progressi nell'interfaccia utente - come dovrebbe avvenire la richiamata?

score 6 · Answer 1

Assuming space is not a concern, would it be reasonable to create multiple copies of the graph (one for each user) rather than a single graph?

Mi sembra che dovresti usare quello che potremmo etichettare come "grafici stratificati", ad esempio aggiungere un combinatore per i grafici, ad esempio @ , in modo che:

Se A e B sono grafici allora A @ B è anche un grafico (cioè può essere alimentato agli algoritmi della tua libreria di grafi).
L'insieme di vertici in A @ B è l'unione dei vertici in A e B.
L'insieme di spigoli in A @ B è l'unione dei bordi in A e B.
La struttura A @ B non possiede alcun vertice o spigolo, ma utilizza A e B come contenitori di dati.

Con tali grafici stratificati, puoi definire K come informazioni disponibili sul kommon e R, G, B ogni informazione privata in modo che ogni giocatore stia effettivamente vedendo R @ K, G @ K, B @ K.

Per implementare effettivamente questo, puoi cercare una libreria di grafici che implementa algoritmi genericamente, cioè che l'algoritmo di percorso più lungo, ecc., sia parametrizzato dalla rappresentazione reale del tuo grafico. Quindi se la tua biblioteca dice

ConcreteGraphAlgorithms = GenericAlgorithms(ConcreteGraphImplementation)

puoi facilmente sostituirlo con

LayeredGraphAlgorithms = GenericAlgorithms(LayeredGraphs(ConcreteGraphImplementation))

dove stai fornendo LayeredGraphs e prendi in prestito il resto dalla libreria.

score 1 · Answer 2

Ciò di cui hai bisogno è chiamato "grafico attribuito". In un grafico attribuito, le informazioni (attributi) sono associate agli archi. Un grafico pesato uno dei più semplici grafici attribuiti.

Per rappresentare un grafico attribuito, puoi utilizzare un elenco di adiacenze aggiungendo ulteriori colonne o matrici di adiacenza aggiungendo ulteriori informazioni in ogni cella. La maggior parte degli algoritmi per i grafici non attribuiti funzionerà se si filtrano gli archi, in base agli attributi. Molti algoritmi sono stati sviluppati per i grafici attribuiti, quindi non li descriverò qui.