[Lemon-devel] Search algs and paths.

[Balazs Dezso]

Dear Alpar,

> I don't think this would be a good solution.
> Let's consider the simplest possible Path structure, an
> std::vector<Edge>.In this case the addFront() function cannot be
> implemented efficiently, and - due to the backward behavior of the
> search algorithms -- this would be the most frequently used operation.
> (What is more, the std::vector<> has a considerable amount of memory
> overhead. If you try to avoid it by using dynamically allocated arrays
> of the size that is actually needed, the addFront() becomes even a
> non-constant time operation.)

I don't think that the simplest Path structure should be used in algorithms, 
it should not have addFront method so it will not unefficient.

> In theory, I can imagine two basic concepts:
>      1. Define an unified way to built up a path. Then we pass empty
>         paths to the algorithms, and they will build the paths. So, this
>         interface should be efficient for the possible path
>         implementations.
>      2. Define how a path can "list" its contents. In this way we can
>         make template copy constructors and operator=()s that can copy
>         from any kinds of path. Then the algorithms return the path in a
>         data structure they like the most, then it's the assignment
>         operator's responsibility to efficiently convert it to the data
>         structure we actually use. In this case we don't have to define
>         a unified way to build up the paths, as the algorithm will only
>         work with paths of their own choice. Note, that in many cases it
>         is possible the avoid the actual copying of the path. For
>         example Dijkstra::getPath() may return a "virtual path", i.e. a
>         class that does not store the path but use the underlying
>         Dijkstra structure to answer the queries.

In generally I suggest both of the two concepts. As there are extensible and 
eresable graphs  there could be different types of paths. I think the Path 
class should be an easy-to-use path type and it should not be the most space 
efficient solution. It could be used to get a path from algorithm and write 
result to somewhere. There should be a very space efficient implementation, 
the StaticGraph, it could not be modified, just build and store it. There 
should be a less efficient implementation with splitting and glueing 
possibilty. And there should be a path type for performance of getting 
results from algorithms, which is just front insertable and it is implemented 
with one vector. It can be used, when we want to run lot of shortest path 
algorithm and we want to get the paths very efficient.

> Your proposal is somewhere in between. First, you define an interface
> for building the paths. This however
>       * cannot be implemented efficiently in many cases.
As I wrote, if something cannot be implemented efficient, that should not be 
implemented.
>       * It misses some important thing:
>               * How to make a path empty?
>               * How to handle path with zero edge? (When source==target)
I forgot these. I think the setStartNode() or just simply start() member 
should be added to the interface, which sets the start node before one edge 
added to the graph. There should be clear() function to make empty the path. 
The empty() function is not equal to length() == 0 because there are empty 
paths(without edge and node) and there are zero length path with just one 
node. When the path is empty() then the length() is undefinied.

> When we worked out the Path structure, actually we started with an
> interface that was similar to your proposal. Then we recognized the
> shortcomings above, thus finally extended this idea to the Builder
> interface,  which is efficient in the most cases and more or less easy
> to use.

It efficient for getting the results from our current algorithms. But If I 
want to build on the fly more paths in the algorithm and in each iteration I 
may add one edge to the path, and the algorithms provides step-by-step 
execution, this will not enough efficient.

On the other hand, I want to run a lot of dijkstra, with the current 
implementation it will makes an extra copy of the path. Instead of we use an 
efficient FrontInsertablePath. /And if you want to use a not efficient 
solution, the compiler refuse it./ 

> You also propose that paths should be copy constructible and assignable
> (like concept No 2. above.) For this however we should define how to
> "dump" the contents of a path instead of how to build them. This
> operation is not necessarily the same as that provides a convenient
> access to the path for the user.

>         work with paths of their own choice. Note, that in many cases it
>         is possible the avoid the actual copying of the path. For
>         example Dijkstra::getPath() may return a "virtual path", i.e. a
>         class that does not store the path but use the underlying
>         Dijkstra structure to answer the queries.

I think there should be both of getPath(Path& p) and getPath(). The second 
usually could be more efficient if we give the right path type for the 
algorithm. The second should be just a helper for easy path usage, which ask 
the path into the most efficient path type and gives it back. I suggest 
virtual paths just when it could be much more efficient then the creating the 
real paths. And I do not suggest to create different dumping interface, 
because efficiency of dumping could be depend on the path type.

The most important point of my approach is that the algorithms should not 
handle each the path types. The algorithm should use the most efficient 
possibility and if you give the correct path type then it could not be 
terrible unefficient.

Best, Balazs

>
> All the best,
> Alpar
>
> On Mon, 2006-11-20 at 17:26 +0100, Balazs Dezso wrote:
> > 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
> >
> > _______________________________________________
> > Lemon-devel mailing list
> > Lemon-devel at lemon.cs.elte.hu
> > http://lemon.cs.elte.hu/mailman/listinfo/lemon-devel