[Lemon-user] output from suurballe.path(i)

[Jan-Willem Elion]

Péter,

This is great, it works. My network problem was a 600-node graph that is really impossible to do manually but the Lemon implementation has just mastered it.

I have used the vector as you suggested to cover a list of around 200 demands. But can you clarify what vector is? Is it a standard part of c++, and the statement 'std::vector<Node> sources, targets;' allocates a standard vector with two dimensions (sources and targets) each being of type Node? I guess this is basic C++ stuff, I would imagine you need to say vector<Node,Node> because you may want to store items of different type in the same vector? 

Anyway, it works, I will take time out for some further C++ study..

Thanks again,

Jan Willem

-----Original Message-----
From: Kovács Péter [mailto:kpeter at inf.elte.hu] 
Sent: Friday, November 20, 2009 11:16 AM
To: Elion, Jan-Willem (HOOF4:5091)
Cc: lemon-user at lemon.cs.elte.hu
Subject: Re: [Lemon-user] output from suurballe.path(i)

Dear Jan Willem,

> Thank you very much, this worked instantaneously!
> 
>> Paths are lists of arcs. These arcs can be iterated using the ArcIt 
>> type or the
>> nth() function of the path structure. The ID of an arc or the IDs of 
>> its source and target nodes can be printed (e.g. g.id(a), g.id(g.source(a)) etc.).
> 
> Is it right to say that you instantiate these types, such as ArcIt, 
> with the
 > 'DIGRAPH_TYPEDEFS(Digraph)' statement?

It's better to say 'define' the types, 'instantiate' means something else.

> I am also a little confused about
 > why the documentation for Basic Graph Utilities refers to this as '#define  > DIGRAPH_TYPEDEFS(Digraph)', what if you don't say #define?

First, you should get familiar with 'typedef'. Using this keyword you can define types, more precisely aliases to types. A typical useage of this is shortening or simplifying the code. E.g.

   typedef std::vector<std::pair<int, int> > MyVector;

We have a lot of embedded types in LEMON, e.g. ListDigraph::Node, ListDigraph::Arc etc. If you would like to shorten these names, you could use typedefs.

   typedef ListDigraph::Node Node;
   typedef ListDigraph::Arc Arc;
   typedef ListDigraph::NodeIt NodeIt;
   typedef ListDigraph::ArcIt ArcIt;
   ...

DIGRAPH_TYPEDEFS is nothing more than a pack of such usual typedefs. It is a macro, created with a #define command, but when you use it, you don't have to say '#define' (see the example code I sent).

> The next step for me I guess would be to be able to call srb.run
 > iteratively to find the paths for subsequent items in a list.
 > Is the class ListEdgeSet<> intended to be used to store items such as traffic  > demands and can you say:
> e ListEdgeSet<>;
> srb.run(e.id(e.source(1)),e.id(e.source(1)),2);
> //this would find the path for the first entry in e, being an instance 
> of
 > ListEdgeSet<>

Be aware with ListEdgeSet, ListArcSet etc. They are special purpose graph data structures and they have nothing to do with the use case you need.

I suggest a solution like this:

   std::vector<Node> sources, targets;
   sources.push_back(s1);
   sources.push_back(s2);
   sources.push_back(s3);
   // add more sources
   targets.push_back(t1);
   targets.push_back(t2);
   targets.push_back(t3);
   // add more targets

   for (int i = 0; i != sources.size(); ++i) {
     Suurballe<ListDigraph, Length> srb(g, length);
     srb.run(sources[i], targets[i], 2);
     // obtain the solution
   }

>>> I believe it is something to do with the data type of 
>>> suurballe.path(), so I am trying to assign a variable routestring:
>>> typedef const SimplePath <ListDigraph> routestring;
> 
>> Note that routestring is a type here!
> 
> Sorry, VisualBasic background..
> 
> Thanks again, Jan Willem

Regards,
Peter