Problems with ShortestPathsBellmanFord

Topics: algorithm, graph
Dec 4, 2008 at 12:54 PM
Edited Dec 4, 2008 at 12:54 PM
Hi everybody,

I was just trying out the AlgorithmExtension.ShortestPathsBellmanFord with this small example:

            AdjacencyGraph<int, Edge<int>> testGraph = new AdjacencyGraph<int, Edge<int>>();
            testGraph.AddVerticesAndEdge(new Edge<int>(1, 2));
            testGraph.AddVerticesAndEdge(new Edge<int>(1, 3));
            testGraph.AddVerticesAndEdge(new Edge<int>(3, 4));
            testGraph.AddVerticesAndEdge(new Edge<int>(1, 4));
            var testPath = testGraph.ShortestPathsBellmanFord<int, Edge<int>>(e => 1.0, 1);


But somehow testPath(1) (and any other node) is always empty. What did I do wrong?

Any help appreciated!

Hendrik.
Coordinator
Dec 4, 2008 at 4:06 PM
testPath is basically a function that returns paths from vertex 1 to any other vertex. The shortest path from 1 to 1 is empty.
Dec 5, 2008 at 8:04 AM
Hi Pelikhan,

thanks for your reply.
testPath(1) was indeed a bad example as it is the source node.
But as I wrote, testPath is empty for any other node, too.
Can anybody verify that? Here is a complete test example:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using QuickGraph;
using QuickGraph.Algorithms;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            AdjacencyGraph<int, Edge<int>> testGraph = new AdjacencyGraph<int, Edge<int>>();
            testGraph.AddVerticesAndEdge(new Edge<int>(1, 2));
            testGraph.AddVerticesAndEdge(new Edge<int>(1, 3));
            testGraph.AddVerticesAndEdge(new Edge<int>(3, 4));
            testGraph.AddVerticesAndEdge(new Edge<int>(1, 4));
            var testPath = testGraph.ShortestPathsBellmanFord<int, Edge<int>>(e => 1.0, 1);
            for (int i = 1; i <= 4; i++)
            {
                Console.WriteLine(testPath(i).Count());
            }
        }
    }
}

Coordinator
Dec 6, 2008 at 4:20 AM
This discussion has been copied to a work item. Click here to go to the work item and continue the discussion.
Coordinator
Dec 6, 2008 at 5:10 AM
Problem fixed and tested.
Dec 17, 2008 at 4:35 PM
Edited Dec 17, 2008 at 4:35 PM
Sorry, but i have another problem with ShortestPaths.

QuickGraph.AdjacencyGraph<int,QuickGraph.Edge<int>>' does not contain a definition for 'ShortestPathsBellmanFord'

Coordinator
Dec 17, 2008 at 11:42 PM
ShortestPathsBellmanFord is an extension method. You need to add an import for QuickGraph.Algorithms at the top of the file.

{{
using QuickGraph.Algorithms;
}}

 

Dec 23, 2008 at 2:53 PM
Of course I have added this string =)

[code]
using QuickGraph;
using QuickGraph.Algorithms;
using QuickGraph.Algorithms.ShortestPath;

......................

 private void quickGraphCalculation()
        {
            AdjacencyGraph<int, Edge<int>> testGraph = new AdjacencyGraph<int, Edge<int>>();
            testGraph.AddVerticesAndEdge(new Edge<int>(1, 2));
            testGraph.AddVerticesAndEdge(new Edge<int>(1, 3));
            testGraph.AddVerticesAndEdge(new Edge<int>(3, 4));
            testGraph.AddVerticesAndEdge(new Edge<int>(1, 4));
            var testPath = testGraph.ShortestPathsBellmanFord<int, Edge<int>>(1.0, 1);
            for (int i = 1; i <= 4; i++)
            {
                MessageBox.Show(testPath(i).Count());
            }
        }
[/code]

Error    2    'QuickGraph.AdjacencyGraph<int,QuickGraph.Edge<int>>' does not contain a definition for 'ShortestPathsBellmanFord'    C:\Documents and Settings\vikhmyro\My Documents\Visual Studio 2005\Projects\ITKurs1\ITKurs1\Form2.cs    335

Coordinator
Dec 23, 2008 at 5:26 PM

Are you using VS2005? In that case, you do not have the extension methods. If that's the case, you need to explicitely name the static method

{{
var testPath = AlgorithmExtensions.ShortestPathsBellmanFord<int, Edge<int>>(testGraph, 1.0, 1);
}}