[Lemon-user] GraphCopy - directed vs. undirected

[Kovács Péter]

Dear Attila,

The key for your problem is what Balazs wrote at the end of his answer. 
In LEMON, each undirected graph can also be used as a directed graph, in 
such a way that each edge can be regarded as two oppositely directed 
arcs. An undirected graph has Arc, ArcIt, ArcMap<> etc. types in 
addition to Edge, EdgeIt, EdgeMap<>, etc. As a result, all directed 
graph algorithms automatically run on undirected graphs, as well 
(provided it makes sense).

Therefore an undirected graph can be copied to a directed one using 
digraphCopy(), as Balazs wrote. However, you probably don't need to copy 
the graph, since you can directly use it as a digraph with arc maps. In 
the arc maps, the oppositely directed arcs may have different assigned 
values. If you don't need such distinction, then you can even use an 
edge map instead of an arc map (e.g. when you run Dijkstra's algorithm 
on the graph), since an arc converts to the corresponding edge.

Regards,
Peter


> Hi,
> 
> I could make directed copy of undirected graph, my code is the following:
> #include <lemon/smart_graph.h>
> #include <lemon/lgf_writer.h>
> 
> using namespace lemon;
> 
> int main(int argc, const char *argv[]) {
>   SmartDigraph target;
>   SmartDigraph::ArcMap<int> tmap(target);
> 
>   SmartGraph source;
>   SmartGraph::Node n1 = source.addNode();
>   SmartGraph::Node n2 = source.addNode();
>   SmartGraph::Edge e = source.addEdge(n1, n2);
>   SmartGraph::EdgeMap<int> map(source);
>   map[e] = 42;
> 
>   digraphCopy(source, target).arcMap(map, tmap).run();
> 
>   digraphWriter(target, std::cout).arcMap("map", tmap).run();
>   
>   return 0;
> }
> 
> I think, the order of source and destination graphs in the parameter list are 
> changed in 1.x versions. Because each undirected graph is at the same time 
> directed graph, therefore you can use digraphCopy().
> 
> Best regards, Balazs
> 
> 
> On Tuesday 02 February 2010 21:02:24 Mitcsenkov Attila wrote:
>> Hi,
>>
>> I would like to create a directed copy of an undirected graph.
>> More detailed: I have a ListGraph instance, and based on that I want to
>>  create a directed graph, with two directed arcs instead of any undirected
>>  edge, with some edgemap values "duplicated", e.g. if length[e] was 5 in
>>  the undirected graph, I want to have two directed arcs, both with length
>>  5.
>>
>> Once I was using Lemon 0.x, it was working by using graphcopy.
>>
>> Now I cannot solve the problem, since the GraphCopy and DigraphCopy needs
>>  two undirected or two directed graphs. I have tried to use the
>>  Orienter/Undirector adaptors, but with those I have the following error
>>  messages:
>>
>> 3>.\OptimalLP.cpp(52) : error C2664:
>>  'lemon::DigraphCopy<From,To>::DigraphCopy(const From &,To &)' : cannot
>>  convert parameter 1 from 'lemon::Orienter<GR,DM>' to 'const
>>  lemon::ListDigraph &' 3>        with
>> 3>        [
>> 3>            From=lemon::ListDigraph,
>> 3>            To=lemon::ListDigraph
>> 3>        ]
>> 3>        and
>> 3>        [
>> 3>            GR=const lemon::ListGraph,
>> 3>            DM=const
>>  lemon::GraphExtender<lemon::ListGraphBase>::EdgeMap<bool> 3>        ]
>> 3>        Reason: cannot convert from 'lemon::Orienter<GR,DM>' to 'const
>>  lemon::ListDigraph' 3>        with
>> 3>        [
>> 3>            GR=const lemon::ListGraph,
>> 3>            DM=const
>>  lemon::GraphExtender<lemon::ListGraphBase>::EdgeMap<bool> 3>        ]
>> 3>        No user-defined-conversion operator available that can perform
>>  this conversion, or the operator cannot be called
>>
>> As far as I understand the concept of graph adaptors, it should be
>>  available to use instead of ListDigraph...
>>
>> Could you please help to solve this?
>>
>> Thanks:
>> Attila Mitcsenkov
>>
> _______________________________________________
> Lemon-user mailing list
> Lemon-user at lemon.cs.elte.hu
> http://lemon.cs.elte.hu/mailman/listinfo/lemon-user