Re: [Neo4j] Multiple-source lowest-cost path search
The Dijkstra algorithm continues until it finds the end node. It could
easily be modified to not stop there, just exhaust the graph and output it's
entire set instead. Look at:
https://github.com/neo4j/community/blob/master/graph-algo/src/main/java/org/neo4j/graphalgo/impl/path/Dijkstra.java
...and I'd rewrite the findAllPaths method to something like:
public Iterable findAllPaths( Node start, final Node end )
{
final Traverser traverser = TRAVERSAL.expand( expander ).order(
new SelectorFactory( costEvaluator ) ).traverse( start );
return new Iterable()
{
public Iterator iterator()
{
return new StopAfterWeightIterator( traverser.iterator(),
costEvaluator );
}
};
}
and also in:
https://github.com/neo4j/community/blob/master/graph-algo/src/main/java/org/neo4j/graphalgo/impl/util/StopAfterWeightIterator.java
I'd rewrite fetchNextOrNull to something like (of course, by then the class
name would not be true anymore :) ):
protected WeightedPath fetchNextOrNull()
{
if ( !paths.hasNext() )
{
return null;
}
return new WeightedPathImpl( costEvaluator, paths.next() );
}
These are just thoughts, but they ought to work right out out of this box.
Best,
Mattias
2011/6/20 Giacomo Bernardi
> I'm not sure I understand your answer.
>
> What I'd like to build is a graph where every node that is not a
> source has a shortest path to any one of the sources.
>
> Any idea?
>
> I see that neo4j's Dijkstra implementation requires to specify a start
> AND and end node. Isn't there at least a version that calculates the
> path for a start node and every other end node?
>
> Thanks!
>
>
> On 20 June 2011 03:53, Akhil wrote:
> > On 6/19/2011 7:11 PM, Giacomo Bernardi wrote:
> >> I'd like to build a second graph in which each e in (S-E) is connected
> > From what i understood, connecting S-E to an arbitary node A1 and S
> > with another arbitary node A2 and finding the lowest cost shortest path
> > between A1 and A2 should give you the solution
> > ___
> > Neo4j mailing list
> > User@lists.neo4j.org
> > https://lists.neo4j.org/mailman/listinfo/user
> >
>
>
>
> --
> Giacomo "mino" Bernardi
> ___
> Neo4j mailing list
> User@lists.neo4j.org
> https://lists.neo4j.org/mailman/listinfo/user
>
--
Mattias Persson, [matt...@neotechnology.com]
Hacker, Neo Technology
www.neotechnology.com
___
Neo4j mailing list
User@lists.neo4j.org
https://lists.neo4j.org/mailman/listinfo/user
Re: [Neo4j] Multiple-source lowest-cost path search
Hi Mino, > What I'd like to build is a graph where every node that is not a > source has a shortest path to any one of the sources. That is the answer, surely? But it means running the shortest path algorithm on each non-source node to a given source node. Jim ___ Neo4j mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
Re: [Neo4j] Multiple-source lowest-cost path search
I'm not sure I understand your answer. What I'd like to build is a graph where every node that is not a source has a shortest path to any one of the sources. Any idea? I see that neo4j's Dijkstra implementation requires to specify a start AND and end node. Isn't there at least a version that calculates the path for a start node and every other end node? Thanks! On 20 June 2011 03:53, Akhil wrote: > On 6/19/2011 7:11 PM, Giacomo Bernardi wrote: >> I'd like to build a second graph in which each e in (S-E) is connected > From what i understood, connecting S-E to an arbitary node A1 and S > with another arbitary node A2 and finding the lowest cost shortest path > between A1 and A2 should give you the solution > ___ > Neo4j mailing list > User@lists.neo4j.org > https://lists.neo4j.org/mailman/listinfo/user > -- Giacomo "mino" Bernardi ___ Neo4j mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
Re: [Neo4j] Multiple-source lowest-cost path search
On 6/19/2011 7:11 PM, Giacomo Bernardi wrote: > I'd like to build a second graph in which each e in (S-E) is connected From what i understood, connecting S-E to an arbitary node A1 and S with another arbitary node A2 and finding the lowest cost shortest path between A1 and A2 should give you the solution ___ Neo4j mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
[Neo4j] Multiple-source lowest-cost path search
Hello everyone, could you advice on the best way to do the following in neo4j? Given: - a graph G= on which each node has an associated positive cost - a subset of "source" nodes S in E. I'd like to build a second graph in which each e in (S-E) is connected to any one of the source nodes S via the lowest-cost path. I don't seem to find anything ready to use for this purpose in neo4j, am I right? Thanks! mino ___ Neo4j mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
