[Lemon-devel] Search algs and paths.

[Alpár Jüttner]

Dear Deba,

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.)

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.

Your proposal is somewhere in between. First, you define an interface
for building the paths. This however
      * cannot be implemented efficiently in many cases.
      * It misses some important thing:
              * How to make a path empty?
              * How to handle path with zero edge? (When source==target)

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. 

_Nota bene_, non of us are satisfied with it, that's why we write these
longish e-mails.

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.

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
-- 
In order to prevent people from receiving viruses
that would seem to originate from my email,
if you use Microsoft Windows you do not have permission
to add this address to your address book.
If I am in your address book, please remove me.
Of course, this does not apply to GNU/Linux users. 
Thank you.