Domanda sul grafico

1

Sto cercando di implementare una struttura di dati del grafico in C #. Ho le seguenti interfacce:

public interface IVertex<TValue>
{
    TValue  Value { get;}        
    VertexList<IVertex<TValue>> Neighbours { get;}
    int InDegree { get;}
    int OutDegree { get;}
}

public interface IWeightedEdge<TValue, TWeight> 
{
    IVertex<TValue> source { get;}
    IVertex<TValue> destination { get;}
    TWeight weight { get; }
} 
public interface IWeightedGraph<TVertexValue, TEdgeWeight> 
{
    bool AddVertex(TVertexValue value);
    TVertexValue RemoveVertex(IVertex<TVertexValue> vertex);
    bool RemoveVertex(TVertexValue value);
    bool AddEdge(IVertex<TVertexValue> source, IVertex<TVertexValue> dest, TEdgeWeight weight);
    bool RemoveEdge(IVertex<TVertexValue> source, IVertex<TVertexValue> dest);
}

Da questo, puoi vedere che è responsabilità della classe Vertex (la classe che implementa l'interfaccia IVertex) per dire dei suoi vertici adiacenti (funzione Vicini), il suo grado, il suo grado ecc. Mentre stavo progettando questo, Mi è stato detto da un mio amico che la classe Graph (quella che implementerà IGraph) dovrebbe assumersi la responsabilità di operazioni come recuperare i vertici adiacenti, trovare i gradi in / out ecc. Il suo punto è che le operazioni di cui sopra sono valide solo quando un vertice diventa parte di un grafico. Ma il mio punto è che un vertice è indipendente; può esistere anche al di fuori di un grafico. Quindi, il vertice dovrebbe fornire le operazioni su di esso.

Quale pensi sia corretto? Per favore condividi le tue opinioni su questo.

    
posta Pradeep 24.01.2014 - 11:38
fonte

1 risposta

2

Direi che il tuo amico ha un punto, anche se può essere elaborato in modo un po 'più dettagliato riguardo ai suoi vantaggi:

In primo luogo, matematicamente parlando, un vertice non può esistere senza un grafico, semplicemente perché un vertice stesso sta già formando un grafico.

In secondo luogo, e molto più importante, i vertici possono essere condivisi da diversi grafici. Prendi in considerazione operazioni come la creazione di sotto-grafici, grafici incorporati, grafici di copertine di vertici, ecc. Ecc. - la nozione comune qui è che crei un grafico, che contiene alcuni vertici del tuo grafico originale, ma diversi set di spigoli. Ad esempio, se crei un sottografo con solo alcuni nodi, perdi i bordi adiacenti ad altri nodi, che non fanno parte del set di vertici di quel sottografo.

Ora se guardi al lato dell'implementazione di cose che non vuoi creare una copia di questi vertici a causa della dimensione di alcuni di questi grafici. Ma se vuoi riutilizzare gli oggetti di vertice originali, avrai difficoltà a fornire set di spigoli diversi per i diversi grafici di contesto.

Quando la classe del grafico è responsabile di tenere traccia di quali bordi fanno parte del grafico, è possibile riutilizzare tutti gli oggetti di bordo e di vertice nelle operazioni di cui sopra.

    
risposta data 24.01.2014 - 12:16
fonte

Leggi altre domande sui tag