HoffmanPavleyRankedShortestPathAlgorithm

Topics: algorithm
Mar 18, 2009 at 7:48 PM
Edited Mar 18, 2009 at 7:56 PM
Hi,

I have added the HoffmanPavleyRankedShortestPathAlgorithm functionality to my program but I'm getting always exception throwing regarding the source and target vertex when NOT running the program in 'Start Debugging' mode. This happens always when the compute() function is called...
I does not matter whether I run the release20 or debug version.

Thus, I get valid results when running in Start Debugging mode it does not matter wheter there are breakpoints or not.

Some output in Debug console...

Vertices;

Name = SR(7) -> 131: 133

Name = SR(7) -> 133: 131

Name = SR(8) -> 129: 131

Name = SR(8) -> 131: 129

Name = SR(17) -> 855: 857

Name = SR(17) -> 857: 855

Name = SR(18) -> 851: 853

Name = SR(18) -> 853: 851

Name = CR(2) -> 133: 256

Name = CR(2) -> 256: 133

Name = CR(3) -> 499: 740

Name = CR(3) -> 740: 499

Name = CR(4) -> 859: 740

Name = CR(4) -> 740: 859

Name = CR(5) -> 728: 851

Name = CR(5) -> 851: 728

Name = CR(6) -> 485: 728

Name = CR(6) -> 728: 485

Name = CR(7) -> 244: 485

Name = CR(7) -> 485: 244

Name = CR(8) -> 244: 125

Name = CR(8) -> 125: 244

Name = SR(26) -> 853: 855

Name = SR(26) -> 855: 853

Name = SR(9) -> 127: 129

Name = SR(9) -> 129: 127

Name = SR(12) -> 248: 492

Name = SR(12) -> 492: 248

Name = CR(9) -> 256: 499

Name = CR(9) -> 499: 256

Name = SR(25) -> 492: 736

Name = SR(25) -> 736: 492

Name = RT(1) -> 125: 127

Name = RT(1) -> 127: 125

Name = RT(1) -> 125: 248

Name = RT(1) -> 248: 125

Name = RT(2) -> 859: 736

Name = RT(2) -> 736: 859

Name = RT(2) -> 859: 857

Name = RT(2) -> 857: 859


Source = 125 target is 129.

+++++NEW PATH+++++

Name = RT(1) -> 125: 127

Name = SR(9) -> 127: 129

+++++NEW PATH+++++

Name = RT(1) -> 125: 248

Name = SR(12) -> 248: 492

Name = SR(25) -> 492: 736

Name = RT(2) -> 736: 859

Name = CR(4) -> 859: 740

Name = CR(3) -> 740: 499

Name = CR(9) -> 499: 256

Name = CR(2) -> 256: 133

Name = SR(7) -> 133: 131

Name = SR(8) -> 131: 129

+++++NEW PATH+++++

Name = CR(8) -> 125: 244

Name = CR(7) -> 244: 485

Name = CR(6) -> 485: 728

Name = CR(5) -> 728: 851

Name = SR(18) -> 851: 853

Name = SR(26) -> 853: 855

Name = SR(17) -> 855: 857

Name = RT(2) -> 857: 859

Name = CR(4) -> 859: 740

Name = CR(3) -> 740: 499

Name = CR(9) -> 499: 256

Name = CR(2) -> 256: 133

Name = SR(7) -> 133: 131

Name = SR(8) -> 131: 129



I'm using QuickGraph version 3 build 31880.  Further I'm using Micrsoft C# sharp Expression 2008 and Framework 2.0.


Any idea what could be wrong!

Thanks in advance,
Best regards,
Frank
Coordinator
Mar 19, 2009 at 12:03 AM
Please provide a repro for this issue.
Mar 22, 2009 at 3:51 PM
Hi Jonathan,

Sorry my mistake, some fault initialization in my program and all vertices were wrongly dimensioned. Thus NO bug in the Graph code!

Best regards,
Frank
Coordinator
Mar 23, 2009 at 1:39 AM
feww! I like this kind of message better :)
Mar 29, 2009 at 10:41 AM
Hi Jonathan,

Yes I can imagine you prefer no bug reports :).
Anyway... as far as I remember there has already been some discussions about the topic 'finding all paths'.

Currently I'm integrating QuickGraph in LocCommander (model railroad software : http://users.telenet.be/loccommander) to find out all the paths between track A and track B in a track layout.
Eg. See http://users.telenet.be/loccommander/images/RouteCalculator.png
I know the algo HoffmanPavley will only give back all the 'shortest' paths between vertices A and B. I'm interested to get all! In this way the user of LocCommander can have a full overview of all the possible routes between 2 tracks he has indicated as source and target.
Is there a possibility already to accomplish this with QuickGraph or in the future?

Thanks in advance.

Best regards,
Frank
Coordinator
Mar 29, 2009 at 4:51 PM
Have you tried setting MaxShortestPath = int.MaxValue in the Hoffman algorithm? It should execute and build shortest path until it runs out of options.
Apr 24, 2009 at 8:47 PM
Hi Jonathan,

Thanks for the tip but unfortunately the compute function seems to come in an infinite loop.

HoffmanPavleyRankedShortestPathAlgorithm

 

<int, TaggedEdge<int, MRBaseObject>> test = new HoffmanPavleyRankedShortestPathAlgorithm<int, TaggedEdge<int, MRBaseObject>>(mvGraph, E => 20.0);
test.ShortestPathCount =
int.MaxValue;
test.Compute(source, target);

Also when I try to set it to 10 the result is an infinite loop.

Any other things I could do?

Thanks for the given support.

Best regards and have a nice weekend,
Frank

 

Coordinator
Apr 24, 2009 at 10:17 PM
> Any other things I could do?
A repro would be welcome :)
Apr 25, 2009 at 9:00 AM
Hi Jonathan,

This repro should do :

int

 

ii = 0;

 

 

BidirectionalGraph<int, TaggedEdge<int, int>> mvGraph2 = new BidirectionalGraph<int, TaggedEdge<int, int>>();

 

mvGraph2.AddVerticesAndEdge(

new TaggedEdge<int, int>(0, 1, ii++));

 

mvGraph2.AddVerticesAndEdge(

new TaggedEdge<int, int>(1, 2, ii++));

 

mvGraph2.AddVerticesAndEdge(

new TaggedEdge<int, int>(2, 3, ii++));

 

mvGraph2.AddVerticesAndEdge(

new TaggedEdge<int, int>(3, 4, ii++));

 

mvGraph2.AddVerticesAndEdge(

new TaggedEdge<int, int>(4, 5, ii++));

 

mvGraph2.AddVerticesAndEdge(

new TaggedEdge<int, int>(5, 0, ii++));

 

mvGraph2.AddVerticesAndEdge(

new TaggedEdge<int, int>(1, 5, ii++));

 

mvGraph2.AddVerticesAndEdge(

new TaggedEdge<int, int>(5, 1, ii++));

 

mvGraph2.AddVerticesAndEdge(

new TaggedEdge<int, int>(2, 5, ii++));

 

mvGraph2.AddVerticesAndEdge(

new TaggedEdge<int, int>(1, 0, ii++));

 

mvGraph2.AddVerticesAndEdge(

new TaggedEdge<int, int>(2, 1, ii++));

 

mvGraph2.AddVerticesAndEdge(

new TaggedEdge<int, int>(3, 2, ii++));

 

mvGraph2.AddVerticesAndEdge(

new TaggedEdge<int, int>(4, 3, ii++));

 

mvGraph2.AddVerticesAndEdge(

new TaggedEdge<int, int>(5, 4, ii++));

 

mvGraph2.AddVerticesAndEdge(

new TaggedEdge<int, int>(0, 5, ii++));

 

mvGraph2.AddVerticesAndEdge(

new TaggedEdge<int, int>(5, 2, ii++));

 

 

HoffmanPavleyRankedShortestPathAlgorithm<int, TaggedEdge<int, int>> test1 = new HoffmanPavleyRankedShortestPathAlgorithm<int, TaggedEdge<int, int>>(mvGraph2, E => 1.0);

 

test1.ShortestPathCount = 5;

//int.MaxValue;

 

test1.Compute(5, 2);


Thanks for the support!


Have a nice weekend,
Frank

Coordinator
Apr 25, 2009 at 10:02 AM
This discussion has been copied to a work item. Click here to go to the work item and continue the discussion.
May 15, 2009 at 7:51 PM

Hi Jonathan,

What kind of arguments needed to be added now to the constructor??

 

HoffmanPavleyRankedShortestPathAlgorithm<int, TaggedEdge<int, MRBaseObject>> test1 = new HoffmanPavleyRankedShortestPathAlgorithm<int, TaggedEdge<int, MRBaseObject

>>(graph, ??? ); it seems  E => 1.0 is no longer supported?

Thanks,

Frank

 

Jun 4, 2009 at 7:32 AM

Hi,

Can anyone help me out with the constructor arguments for the HoffmanPavleyRankedShortestPathAlgorithm (second argument)?

Best regards,

Frank

Coordinator
Jun 4, 2009 at 1:11 PM

The signature of the .ctor is:

public HoffmanPavleyRankedShortestPathAlgorithm(
            IBidirectionalGraph<TVertex, TEdge> visitedGraph,
            Func<TEdge, double> edgeWeights)
In that sense, e => 1.0 should work. Could you make sure the graph implement IBidirectionalGraph<TVertex,TEdge>? 
What is the compiler complaining about?
The released binaries might not be in sync, so you could try to build QuickGraph.dll from sources too.

Jun 5, 2009 at 6:41 PM

Hi Jonathan,

Sorry my mistake, I mixed Framework versions (own projects with 2.0 and Quickgraph with 3.5) for my different projects in my solution.

When all are compiled with V3.5 all works fine... (Quickgraph version [assembly: AssemblyVersion("3.2.40408.00")])

But, I still don't understand when the  parameter ShortestPathCount is set to a big value... (it does not seem to have an effect...)<font size="2">

 

</font>

[HoffmanPavleyRankedShortestPathAlgorithm <int, TaggedEdge<int, MRBaseObject>> test = new HoffmanPavleyRankedShortestPathAlgorithm<int, TaggedEdge<int, MRBaseObject>>(mvGraph, E => 1.0);]

I only get one path. For sure it is the shortest. Please see the screenshot in the link : http://users.telenet.be/loccommander/images/1Path.png

Normally, I should expect to see at least 3 paths in this graph...between start and end vertex as pointed in the layout.

Thanks for the support.

Have a nice weekend,

Frank

 

 

 

 

 

 

 

Jun 9, 2009 at 4:04 PM

Hi,

Anyone having some experience with the ShortestPatCount parameter in the HoffmanPavleyRankedShortestPathAlgorithm? Usually I only get 1 path (the shortest altough there are many more).

Best regards,

Frank

Coordinator
Jun 10, 2009 at 2:19 AM

I'll take a look at your repro somewhere this week when i get the time.

Coordinator
Jun 10, 2009 at 7:34 AM

The count is simply used to cap the number of path. Indeed, there could be many of them. Are you using the latest version from the sources?

Jun 16, 2009 at 5:13 PM

Hi Jonathan,

Sorry for the late reply, I'm using QuickGraph version 34552 (.NET Framework 3.5).

I would expect to see more than one path in the example : http://users.telenet.be/loccommander/images/1Path.png when the parameter ShortestPatCount is set to a big value...

Thanks,

Best regards,

Frank

 

 

Jun 21, 2009 at 4:48 PM

Hi Jonathan,

Any idea yet what could be wrong regarding this algo and the ShortestPatCounter parameter?

Thanks,

Frank

 

 

Coordinator
Jun 22, 2009 at 5:46 AM

Could you reopen this as an issue with the self-contained repro that creates issue?