[Lemon-user] Multi-source Dijkstra search

[Alpar Juttner]

Hi,



> 1. Is there a way to initialize Dijkstra search with multiple
> roots/sources? (I find it difficult to believe that there isn't, but
> the documentation seems to talk only about single-source).

Yes, there is, and even the documentation
(http://lemon.cs.elte.hu/pub/doc/latest/a00126.html )
is quite clear about it:

"If you need better control on the execution, you have to call init()
first, then you can add several source nodes with addSource(). Finally
the actual path computation can be performed with one of the start()
functions."

In fact, you can do even more, such as conditional termination,
step-by-step executions, visitor functions, custom length computation
etc.


> 2. ListDigraph provides an iterator to explore the outgoing arcs of a
> node. Sometimes however, I need to quickly get an array of all such
> arcs (or, better yet, an array of adjacent nodes). Can I get this
> array without using the iterator?

No, you cannot. You can obtain the (out)adjacent nodes in a vector like
this:

std::vector<ListDigraph::Node> n_list;
for(ListDigraph::OutArcIt a(g,n);a!=INVALID;++a)
  n_list.push_back(g.target(a));

There is also an ongoing work on implementing STL style iterators, see
https://lemon.cs.elte.hu/trac/lemon/ticket/325

>  (using the iterator seems to be a terribly inefficient way to go
> about the task...)

It is actually pretty efficient.
The arc iterators directly exposes the internal graph representation
with basically zero overhead.
std::vector::push_back() is also efficient enough in most cases.

Regards,
Alpár

P.S. Note that this is a subscribers-only mailing list. Your email was
almost discarded automatically. Please subscribe to avoid delayed/lost
posts.