[Lemon-devel] Search algs and paths.
Alpár Jüttner
alpar at cs.elte.hu
Tue Nov 21 21:24:28 CET 2006
Some random questions and remarks.
* As far as I see, the concept that you suggest is a subset of
what is currently implemented. Then how can this imporve on the
performance issues? Perhaps, I misunderstood something.
* The most obvious algorithms providing paths are
BFS/DFS/Dijkstra. The most obvious data structure for storing
path is something resembling std::vector<Edge>. We _should_ make
it possible to use them directly and efficiently with each
other.
* Consider a path structure that is even less flexible, but has
even less memory overhead: a dynamically allocated array of
edges. Dijkstra could quite efficiently create a paths like this
as follows. First it counts the number of edges in the path,
then allocates an array of this size and finally it fills this
array from back to front. I would like to see an
interface/concept that makes it possible the implement this
array-path in such a way that Dijkstra will do exactly this when
it is asked to put a route into a path data structure.
* I think that the algorithms _should_ work with each path
implementation. There are already big number of things the user
must keep in mind when working with LEMON. The extra
requirements on the path type the algorithms are willing to work
with would just increase this by one. Moreover, the decreased
interoperability will make the usage less convenient.
All the best,
Alpar
On Tue, 2006-11-21 at 15:00 +0100, Balazs Dezso wrote:
> 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
> _______________________________________________
> 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.
More information about the Lemon-devel
mailing list