1

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.

  • 2
    I wonder how you will retrieve any edges from a given graph. There seems to be no method for that. Even if you had such a method, how do you retrieve a list of all vertexes, without doubles? – Doc Brown Jan 24 '14 at 10:53
  • @ Doc Brown, I have just given a subset of the actual class that contains only the method that are relevant to the question...Thanks.. – Pradeep Jan 27 '14 at 13:20
2

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.

  • Thank you Frank..One more question..If we are going to add the operations to Graph, we may not need an object type for the vertex. In that case, do you think reusing vertices is a big issue? – Pradeep Jan 25 '14 at 8:16
  • It often is, because at some time you may want to be able to ask questions like "is this vertex from graph G also in its subgraph H?". For this it's easy, if your graphs' vertex sets actually contain the same vertex objects – Frank Jan 27 '14 at 6:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.