[Lemon-devel] Search algs and paths.

[Balazs Dezso]

Dear Developers,

I would like to suggest another interface for the path construction. I would 
like to use rather more simplified interface without builder classes. I think 
the current implementation is too complicated, sometimes it is not efficient 
or too hard to use.

I would like front and back extension functions, which could be implemented in 
any path type:
void addFront(const Edge&)
void addBack(const Edge&)

Each path should be copyconstructible and assignable by any other path type.
StaticPath<Graph> sp;
Path<Grpah> p;
dijkstra.getPath(p, t);
sp = p;

I would like several implementation:
Path - front/back insertion /two vector/
ListPath - front/back insertion, spliting...
StaticPath - just copy
? Front/BackPath - just front or back insertion /one vector/

The interface is quite simple and it can be used very efficiently.

Best, Balazs



On 2006. November 20. 16:46, Alpár Jüttner wrote:
> Dear all,
>
> as a next step, we should clean up the interfaces of the path related
> algorithms (BFS, DFS, Dijkstra etc.). For this however, we also have to
> clarify the Path concept.
>
> The current design is the best we have found so far, but I'm still quite
> unsatisfied with it.
>
> The major difficulty is that the algorithms above can typically list the
> edges of a path backwards and cannot determine the length (the number of
> the edges) of a path in advance. Of course we would like to minimize the
> copying/counting overhead when working with path. The concept should
> also enable implementing path structures with small memory footprint.
>
> I kindly ask everyone to comment the current concept and also try to
> come up with alternative approaches.
>
> Regards,
> Alpar