c++lemon-graph-library

Lemon Graph iterate edges


From Lemon's hello world (hello_lemon.cc, see here) I've copied the following code :

#include <iostream>
#include <lemon/list_graph.h>

int main()
{
  typedef lemon::ListGraph Graph;
  typedef Graph::EdgeIt EdgeIt;
  typedef Graph::Edge Edge;
  typedef Graph::NodeIt NodeIt;
  typedef Graph::Node Node;
  typedef Graph::EdgeMap<int> LengthMap;
  using lemon::INVALID;

  Graph g;

  Node s=g.addNode();
  Node v2=g.addNode();
  Node v3=g.addNode();
  Node v4=g.addNode();
  Node v5=g.addNode();
  Node t=g.addNode();

  Edge s_v2=g.addEdge(s, v2);
  Edge s_v3=g.addEdge(s, v3);
  Edge v2_v4=g.addEdge(v2, v4);
  Edge v2_v5=g.addEdge(v2, v5);
  Edge v3_v5=g.addEdge(v3, v5);
  Edge v4_t=g.addEdge(v4, t);
  Edge v5_t=g.addEdge(v5, t);

  std::cout << "Nodes:";
  for (NodeIt i(g); i!=INVALID; ++i)
    std::cout << " " << g.id(i);
  std::cout << std::endl;

  std::cout << "Edges:";
  for (EdgeIt i(g); i!=INVALID; ++i)
    std::cout << " (" << g.id(g.source(i)) << "," << g.id(g.target(i)) << ")";
}

All I want to do is iterate over the nodes/edges and print them. However, when I try to compile this, I get the following errors:

g++ -I"/opt/lemon/include" -I"/opt/lemon/lib"  -Wall -Werror -fpic -DNDEBUG -O3 test.cc
test.cc: In function ‘int main()’:
test.cc:68:41: error: no matching function for call to ‘lemon::ListGraph::source(EdgeIt&)’
test.cc:68:41: note: candidate is:
In file included from test.cc:22:0:
/opt/lemon/include/lemon/list_graph.h:878:10: note: lemon::ListGraphBase::Node lemon::ListGraphBase::source(lemon::ListGraphBase::Arc) const
/opt/lemon/include/lemon/list_graph.h:878:10: note:   no known conversion for argument 1 from ‘EdgeIt {aka lemon::GraphExtender<lemon::ListGraphBase>::EdgeIt}’ to ‘lemon::ListGraphBase::Arc’
test.cc:68:69: error: no matching function for call to ‘lemon::ListGraph::target(EdgeIt&)’
test.cc:68:69: note: candidate is:
In file included from test.cc:22:0:
/opt/lemon/include/lemon/list_graph.h:879:10: note: lemon::ListGraphBase::Node lemon::ListGraphBase::target(lemon::ListGraphBase::Arc) const
/opt/lemon/include/lemon/list_graph.h:879:10: note:   no known conversion for argument 1 from ‘EdgeIt {aka lemon::GraphExtender<lemon::ListGraphBase>::EdgeIt}’ to ‘lemon::ListGraphBase::Arc’

Any idea how to fix this? I'm using Lemon 1.3.1 which is currently the latest version.


Solution

  • It turns out that the hello_lemon.cc is incorrect! The functions source(edge) and target(edge) are only defined for directed graphs and hence arcs. For undirected graphs, as in the example, you need to use u(edge) and v(edge) resp. (who comes up with this logic...). So the correct code to iterate the set of edges would be:

    std::cout << "Edges:";
      for (EdgeIt i(g); i!=INVALID; ++i)
        std::cout << " (" << g.id(g.u(i)) << "," << g.id(g.v(i)) << ")";