Question About QuickGraph

Topics: algorithm
Oct 18, 2007 at 2:28 PM
This post is in the name of Vitaliy:

Hello Jonathan,

I am working with the Quick graph package, and I encountered some implementation difficulties when trying to use it for an undirected graph. I consider myself to be a beginner software developer.

In this letter I describe the problem and give two possible but incomplete design solutions to it.
Most of all I ask whether you happened to encounter the same problem and if so- how did you solve it.

It seems that the package gives a very natural solution to directed graphs.
Indeed when we add an edge using AddEdge the line

vertexEdgese.Source.Add(e);

makes sure that e.Target is adjacent to e.Source but not vice versa.

But What happens when I wish to work with an undirected graph?

The current method for adding an edge obviously does not suit,
When adding an edge from Vertex v to Vertex w, adjecence is not symmetric.

I will describe two ideas that I had to solve that problem, but non of them seems to be complete.
I would appreciate your honest oppinion about them,
and which is more, your own idea of implementing an undirected graph.

1. My first, and rather cumbersome solution, is to add the back edge of each inserted edge,
meaning the AddEdge method will look something like this:

AddEdge(IVertex s, IVertex t)
{
IEdge e = EdgeProveider(s, t);
_vertexEdgess.Add(e);

If(_isDirectred)
{
IEdge reverse_e = EdgeProvider(t, s);
vertexEdget.Add(reversee);
}
}

This way, I maintain the correctness of all traversal algorithms,
Since each vertex is reachable from every vertex it reaches.

Alas, when the need arises to associate data with edges (such as weights)
and since additional data is concentrated in dictionaries-
I have to store each value twice:
Once under a forward edge and another time for its corresponding backward edge.
This causes initialization to be very ugly and empasizes that holding two edges to model a single,
undirected edge is bad practice.

2. Naturally, my next solution is not to create a different back edge but to add the same edge twice:
once to the source and one more for the target.
The method AddEdge will look like this:

AddEdge(IVertex s, IVertex t)
{
IEdge e = EdgeProveider(s, t);
_vertexEdgess.Add(e); // Add edge under s

If(!_isDirectred)
{
_vertexEdget.Add(e); //Add the same edge undet t
}
}

Thus, I have no “redundent” edges and each vertex knows what edges are incident to it.
But! And that is a serious “But!” In my first solution, when accessing vertexEdgesv,
I knew for certain the the returned Edge Collection has edges directed from v:

Foreach (IEdge e in vertexEdgespv)
{
// e.Target always returns a vertex other then v.
}

So if I replace it with the second solution, where I add the same edge twice, this may not be so.
In an iteration such as above (one which BFS heavily relies on)
may return an IEdge e that its Target equals the vertex whos edges we are enumerating:
e.Target will return v, giving incorrect results.

This may be the case in the following example:

Say I have an undirected instance of an Adjacency graph called _g.
It has two vertices, whose corresponding objects are v1 and v2.

_g.AddEdge(v1, v2)

Causes an edge e to be inserted to _g.VertexEdgesv1,
such that e.source is v1 and e.Target is v2 and the same edge to be inserted to _g.VertexEdgesv2 .


But then When I do:

foreach (IEdge e in _g.VertexEdgesv2)
{
// I get an edge that e.Target equals v2.
}

So I have no way of knowing whether e.Target is a neighbour of v2 (as I axpect) or v2 itself.

How do you handle undirected graphs.

Thank you in advance.
Vitaliy.












Coordinator
Oct 20, 2007 at 11:59 PM
it'll take some time for an answer, i'm on vacation till nov