Summing Edges from HoffmanPavleyRankedShortestPathAlgorithm

Topics: algorithm, graph
Jun 16, 2010 at 4:30 PM
I am programming in VB.NET. I am quite happy with the QuickGraph library and the Shortest Path calculated using the HoffmanPavley method. However, I am struggling with easily obtaining the sum of the weights for the shortest path. I have supplied the code that generates my BidirectionalGraph. Private Sub CreateGraph() 'we need to fill the graph with vertices Dim verts = (From v In IBMDataSet.GraphTable.AsEnumerable _ Select v.Fnode).Distinct For Each vts In verts adjGraph.AddVertex(vts) Next 'we need to fill the graph with edges For Each edges In IBMDataSet.GraphTable.AsEnumerable adjEdge = New Edge(Of String)(edges.Fnode, edges.Tnode) adjGraph.AddEdge(adjEdge) edgeCost.Add(adjEdge, edges.Distance) Next IBMDataSet.GraphTable.Clear() 'free up some memory End Sub 'here is where I am running the ShortestPath and can see the array of paths used to find the shortest between the Source and Target Dim test1 As New HoffmanPavleyRankedShortestPathAlgorithm(Of String, Edge(Of String))(adjGraph, AlgorithmExtensions.GetIndexer(Of Edge(Of String), Double)(edgeCost)) test1.ShortestPathCount = 1 'int.MaxValue; test1.Compute("HB019_0", "HB019_50") Can someone provide an example of an efficient/best way to sum the weights for the edges used in the shortest path? Thanks.
Jun 17, 2010 at 4:10 PM
Edited Jun 17, 2010 at 4:10 PM
Well, I think that I have come up with a solution. Not sure if it is the most ideal/best, but here is the code. If anyone has a better solution, I would love to see it! Private Sub CreateGraph() 'we need to fill the graph with vertices Dim verts = (From v In IBMDataSet.GraphTable.AsEnumerable _ Select v.Fnode).Distinct For Each vts In verts adjGraph.AddVertex(vts) Next 'we need to fill the graph with edges For Each edges In IBMDataSet.GraphTable.AsEnumerable adjEdge = New Edge(Of String)(edges.Fnode, edges.Tnode) adjGraph.AddEdge(adjEdge) edgeCost.Add(adjEdge, edges.Distance) Next IBMDataSet.GraphTable.Clear() 'free up some memory End Sub Public Function GetShortestPath() As Double Dim shortPath As New HoffmanPavleyRankedShortestPathAlgorithm(Of String, Edge(Of String))(adjGraph, AlgorithmExtensions.GetIndexer(Of Edge(Of String), Double)(edgeCost)) 'only return the shortest path shortPath.ShortestPathCount = 1 shortPath.Compute("HB019_0", "HB019_50") 'for a give pair of nodes dblDist = 0 'loop through the list of edges and grab the cost to sum the total For i As Integer = 0 To (shortPath.ComputedShortestPaths(0).ToArray.Length - 1) 'we only find shortest path, so index will always be 0 dblDist += edgeCost(shortPath.ComputedShortestPaths(0)(i)) 'keep a running total of distances Next shortPath = Nothing 'clear the object End Sub