Refactoring the Network in DelftShell and adding support for graph algorithms.

Currently Network in DelftShell has specific properties of a hydrological network: cross section, structures, boundaries. We need to extract the hydrological specific properties and use a general purpose interface. This will enable other plugins in the DelfShell family to reuse the network but also to use freely available algorithm implementations.

Terminology (from wikipedia)

Graph:
In mathematics a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links.

Network:
In graph theory, a network is a directed graph with weighted edges

There are several libraries in the public domain that can be used for graph support. Either directly or as reference:

QuickGraph

http://www.codeplex.com/quickgraph

QuickGraph provides generic directed/undirected graph datastructures and algorithms for .Net 2.0 and up. QuickGraph comes with algorithms such as depth first seach, breath first search. QuickGraph is bases on the Boost library (C++).
http://www.boost.org/doc/libs/1_39_0/libs/graph/doc/index.html

NTS - Net Topology Suite

NetTopologySuite is a C#/.NET port of JTS Topology Suite, a Java library for GIS operations, (OpenGIS compliant).
NTS is also used by SharpMap, it implements for example the OpenGiS geometry interfaces like LineString. Although NTS has some classes for graphs (see folder GeometriesGraph) these classes are used internally for the Topology Graph which is used to calculate the Intersection Matrix (relate algorithm; see also http://www.vividsolutions.com/jts/bin/JTS%20Technical 20Specs.pdf chapter 10).

The NTS site has some examples/tests for routing algorithms, see: http://code.google.com/p/nettopologysuite/source/browse/trunk/NetTopologySuite.Samples.Console/Tests/Various/PathFinderTest.cs and GraphBuilderTest.cs
These implementations use the QuickGraph library.

Jung

Java Universal Network/Graph Frameworkhttp://jung.sourceforge.net/index.html
This appears a very widely used general purpose graph library. I have found no port for .Net.

Some general purpose libraries with graph support

The C5 Generic Collection Library

\http://www.itu.dk/research/c5/
C5 is a library of generic collection classes. The core classes do not implement a graph but there is an implementation in the samples: Graph.cs

NGenerics

http://ngenerics.codeplex.com/
NGenerics is a more comprehensive general purpose collection library than the C5 library.
For an interface description see:http://www.codeproject.com/KB/recipes/DotNet2Datastructures.aspx

QuickGraph seems a logical choice to use as library for DelftShell. It extensively uses interfaces which enables us to reuse our current classes in DelftShell and offers a large number of graph algorithm implementations.

As proof of concept a simple test has been written that uses the Dijkstra algorithm for the shortest path but only uses interfaces from QuickGraph.

INetwork network = new Network();

INode nodeA = new Node {Name = "A"};
INode nodeB1 = new Node { Name = "B1" };
INode nodeB2 = new Node { Name = "B2" };
INode nodeC = new Node { Name = "C" };

IBranch edgeAB1 = new Branch(nodeA, nodeB1);
IBranch edgeAB2 = new Branch(nodeA, nodeB2);
IBranch edgeB1C = new Branch(nodeB1, nodeC);
IBranch edgeB2C = new Branch(nodeB2, nodeC);

network.Nodes.Add(nodeA);
network.Nodes.Add(nodeB1);
network.Nodes.Add(nodeB2);
network.Nodes.Add(nodeC);

network.Branches.Add(edgeAB1);
network.Branches.Add(edgeAB2);
network.Branches.Add(edgeB1C);
network.Branches.Add(edgeB2C);

IDictionary<IBranch, double> branchCost = new Dictionary<IBranch, double>();

branchCost.Add(edgeAB1, 100);
branchCost.Add(edgeAB2, 200);
branchCost.Add(edgeB1C, 50);
branchCost.Add(edgeB2C, 200);

var dijkstra = new UndirectedDijkstraShortestPathAlgorithm<INode, IBranch>(network, branchCost, new ShortestDistanceRelaxer());

VertexPredecessorRecorderObserver<INode, IBranch> predecessorObserver = new VertexPredecessorRecorderObserver<INode, IBranch>();

using (ObserverScope.Create(dijkstra1, predecessorObserver))
{
// Run the algorithm with A set to be the source
  dijkstra1.Compute(nodeA);
}

...

double distance = AlgoUtility.ComputePredecessorCost(predecessorObserver.VertexPredecessors, branchCost, nodeC);
Debug.WriteLine(string.Format("A -> {0}: {1}", nodeC, distance));

result is :
A -> Node C: 150

The interface of INode, IBranch and INetwork are defined outside the QuickGraph library.

public interface INode
public interface IBranch : IEdge<INode>
public interface INetwork : IUndirectedGraph<INode, IBranch>

IEdge and IUndirectedGraph are defined in the QuickGraph library.

Blog