Quantcast

Dijktra shorthest problem with subgraphs

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Dijktra shorthest problem with subgraphs

Julien Thomas de Boer
Hello everyone,
Does someone know why this problem occurs :
Given a ListenableDirectedWeighted graph g. I build the subgraph s from
g. Imagine now I want to check the path between two nodes, A and B
(connected in g but not in s). When I use :
List chemin = DijkstraShortestPath.findPathBetween(s,"A","B");
In chemin, it returns the path in g but not in s.
How is it possible ? Do you know how to solve this problem ? Thanks a
lot for your attention.


--
Sincerely,

Julien THOMAS DE BOER
Swiss Federal Institute of Technology of Lausanne (EPFL)




Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Dijktra shorthest problem with subgraphs

Kyle Lahnakoski

I looked at the code

The Subgraph class has a bug (or more).  TheDijkstraShortestPath will eventually use Subgraph.outgoingEdgesOf().  Here is the code:

    public List outgoingEdgesOf( Object vertex ) {
        return ( (DirectedGraph) m_base ).outgoingEdgesOf( vertex );
    }

Notice that the m_base is the original supergraph, not some subset.


Julien Thomas de Boer wrote:
Hello everyone,
Does someone know why this problem occurs :
Given a ListenableDirectedWeighted graph g. I build the subgraph s from
g. Imagine now I want to check the path between two nodes, A and B
(connected in g but not in s). When I use :
List chemin = DijkstraShortestPath.findPathBetween(s,"A","B");
In chemin, it returns the path in g but not in s.
How is it possible ? Do you know how to solve this problem ? Thanks a
lot for your attention.


  


-- 
----------------------------------------------------------------------
Kyle Lahnakoski                                       [hidden email]
(416) 892-7784                                    Arcavia Software Ltd
Loading...