Question on Graph

Question

I am trying to implement a graph data structure in C#. I have the following interfaces:

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);
}

From this, you can see that it is the responsibility of the Vertex class (the class implementing IVertex interface) to tell about its adjacent vertices (Neighbors function), its in degree, out degree etc. While I was designing this, I was told by a friend of mine that the Graph class (the one that will implement IGraph) should take the responsibility of operations like retrieving adjacent vertices ,finding the in/out degrees etc. His point is that the above operations are valid only when a vertex becomes part of a Graph. But my point is that a Vertex is standalone; it can exist even outside of a graph. So, the vertex should provide the operations on it.

Which one you think is correct? Please share your thoughts on this.

Answer 1

I would say your friend has a point, albeit it can be elaborated in a bit more detail regarding its advantages:

Firstly, mathematically speaking, a vertex cannot exist without a graph, simply because a vertex itself is already forming a graph.

Secondly, and much more importantly, vertices can be shared by different graphs. Consider operations like creating sub-graphs, embedded graphs, vertex cover graphs, etc etc.. - the common notion here is that you create a graph, that contains some vertices from your original graph, but different edge sets. For example, if you create a subgraph that has only some nodes, you lose the edges that are adjacent to other nodes, which are not part of that subgraph's vertex set.

Now if you look at the implementation side of things you do not want to create a copy of these vertices due to the size of some of these graphs. But if you want to reuse the original vertex objects, you will have a hard time to provide different edge sets for different context graphs.

When the graph class itself is responsible for keeping track of which edges are part of the graph, you can reuse all edge and vertex objects in the above operations.