Shortest path algorithms with .Net

[DEX graphdb]

Since 4.5 DEX includes shortest path algorithms for .Net (see old blog announcement: http://sparsity-technologies.com/blog/?p=540).

Here is an example of use for .Net:

First, remember to include in your code the algorithms package by adding:

using com.sparsity.dex.algorithms;

We assume here, that you already have a created db with nodes and edges included.

If you do not have weights in your edges you should perform a BFS (More info: http://en.wikipedia.org/wiki/Breadth-first_search):

System.Console.WriteLine("SinglePairShortestPath BFS");
// Create a new unweighted shortest path from "startingNode" to "endingNode"
SinglePairShortestPathBFS spBFS = new SinglePairShortestPathBFS(sess, startingNode, endingNode);
// Allow the use of all the edge types in Any direction
spBFS.AddAllEdgeTypes(EdgesDirection.Any);
// Allow the use of all the node types
spBFS.AddAllNodeTypes();
// Calculate the shortest path
spBFS.Run();
// Check the path if it exists
if (spBFS.Exists())
 {
            // Get the total path cost
            System.Console.WriteLine("A shortest path exists with cost: "+spBFS.GetCost()+".");
            // Get the path
            OIDList pathAsNodes = spBFS.GetPathAsNodes();
            OIDListIterator pathIt = pathAsNodes.Iterator();
            while (pathIt.HasNext())
            {
                long nodeid = pathIt.Next();
                System.Console.WriteLine("Node: "+nodeid);
            }
}
 else
{
            System.Console.WriteLine("No path found");
 }
        // Close the shortest path
        spBFS.Close();

But if you wish to consider the weights in the edges to find the shortest path you should consider using Dijkstra (More about Dijkstra: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm) :

System.Console.WriteLine("SinglePairShortestPath Dijkstra");
// Create a new weighted shortest path from "startingNode" to "endingNode"
SinglePairShortestPathDijkstra spDijkstra = new SinglePairShortestPathDijkstra(sess, startingNode, endingNode);
// Allow the user of the edge type "anEdgeType" in outgoing direction and using "edgeWeight" as the edge weight attribute
spDijkstra.AddWeightedEdgeType(anEdgeType, EdgesDirection.Outgoing, edgeWeight);
// Allow the use of all the node types
spDijkstra.AddAllNodeTypes();
// Calculate the shortest path
spDijkstra.Run();
// Check the path if it exists
if (spDijkstra.Exists())
{
            // Get the total path cost
            System.Console.WriteLine("A shortest path exists with cost: "+spDijkstra.GetCost()+".");
            // Get the path
            OIDList pathAsNodes = spDijkstra.GetPathAsNodes();
            OIDListIterator pathIt = pathAsNodes.Iterator();
            while (pathIt.HasNext())
            {
                long nodeid = pathIt.Next();
                System.Console.WriteLine("Node: "+nodeid);
            }
}
else
{
            System.Console.WriteLine("No path found");
}
        // Close the shortest path
        spDijkstra.Close();