Example FloydWarshallAllShortestPathAlgorithm

Topics: algorithm, graph
Oct 15, 2009 at 9:57 AM

Hi !

 

I'm new to FloydWarshallAllShortestPathAlgorithm...

 

Could anyone please give me an example how to use FloydWarshallAllShortestPathAlgorithm?

 

What I have:

            /*
             *     Easy creation with extension methods
             *     QuickGraph provides several extension methods in QuickGraph.GraphExtensions to create graph from list of edge or vertices. For example, from an IEnumerable<Edge<int>>
             */
            var edges = new SEdge<int>[] { new SEdge<int>(1, 2), new SEdge<int>(0, 1) };
            var graph = edges.ToAdjacencyGraph<int, SEdge<int>>(edges);

            /*
             * Create a graph instance
             * Let us assume we need integer vertices and edges tagged with string. Int is the vertex type and we can use the MarkedEdge generic type for the edge type:
             *
                * TVertex type: int
                * TEdge type using TaggedEdge<Vertex,Marker>: TaggedEdge<int, string>
             */
            var g = new AdjacencyGraph<int, TaggedEdge<int, string>>();

            //Dictionary<int, int[]> dic = ...; // vertex -> target edges
            /*
            var graph = dic.ToVertexAndEdgeListGraph(
                kv => Array.ConvertAll(kv.Value, v => new SEquatableEdge<int>(kv.Key, v))
                );
             */

            /*
             * Adding vertices
             * This snippet creates two vertices and adds them to the graph.
             */
            int v1 = 1;
            int v2 = 2;

            g.AddVertex(v1);
            g.AddVertex(v2);

            /*
             * Adding edges
             * The edges (v1,v2) and (v2,v1) are created and added to the graph.
            */
            var e1 = new TaggedEdge<int,string>(v1,v2,"hello");

            g.AddEdge(e1);

            /*
             * Adding edges (and vertices)
             * You can also add an edge and implicitely add the vertices if they are missing
             */
            // v3, v4 are not added to the graph yet
            int v3 = 3;
            int v4 = 4;
            var e2 = new TaggedEdge<int,string>(v3,v4,"hello");

            g.AddVerticesAndEdge(e2);

            TaggedEdge<int, string>[] arr = new TaggedEdge<int, string>[2];
            arr[0] = e1;
            arr[1] = e2;

// Run var weights = e ; // a function that maps TEdge -> double var fw = new FloydWarshallAllShortestPathAlgorithm<int, TaggedEdge<int, string>>(g, arr);   // compute fw.Compute(); // get interresting paths, foreach(var source in g.Vertices) foreach(var target in g.Vertices) { IEnumerable<TEdge> path; if(fw.TryGetPath(source, target, out path) foreach(var edge in path) Console.WriteLine(edge); }

But it doesn't work ! :(

This line is the first problem:

var graph = edges.ToAdjacencyGraph<int, SEdge<int>>(edges); 

 

The second is:

var fw = new FloydWarshallAllShortestPathAlgorithm<int, TaggedEdge<int, string>>(g, arr);


Thanks for your help! :)
Marco
Oct 19, 2009 at 2:08 PM

hello, im not too sure about what you try to do but if you want to use this algorith you can simply do the following:

static void Main(string[] args)
{
 var edges = new SEdge<int>[] { new SEdge<int>(1, 2), new SEdge<int>(0, 1) };
  
 var g = new AdjacencyGraph<int, TaggedEdge<int, string>>();

 const int v1 = 1;g.AddVertex(v1);
 const int v2 = 2;g.AddVertex(v2);

   // Adding edges
 var e1 = new TaggedEdge<int,string>(v1,v2,"hello");
 g.AddEdge(e1);

 // Run
 var fw = new FloydWarshallAllShortestPathAlgorithm<int, TaggedEdge<int, string>>(g, e=>1);
  
 // compute
 fw.Compute();
 
 // get interresting paths,
 foreach(var source in g.Vertices)
  foreach(var target in g.Vertices)
  {
   IEnumerable<TaggedEdge<int,string>> path;
   if(fw.TryGetPath(source, target, out path))

    foreach(var edge in path)
     Console.WriteLine(edge);
  }
 Console.WriteLine("Press <ENTER> to complete");
 Console.ReadKey();

}

i hope it help

Oct 24, 2009 at 6:29 PM

Hi graphTest!

 

Thanks a lot for your reply.

 

My problem is how to assign a weight to a link.

 

E.g:

Edge 1-2 : Weight 1,3

Edge 2-3: Weight 2,1

Edge 3-1: Weight: 3

 

 

// Run
 var fw = new FloydWarshallAllShortestPathAlgorithm<int, TaggedEdge<int, string>>(g, e=>1);

If I'm right this Method uses a weight of "1" (e => 1) for each egde.

 

How can I assign the weight to the edge?

 

Have I to use this method

// Adding edges
var e2 = new TaggedEdge<int, double>(v1, v2, 1.4);

 

Thanks,

Marco