3 Basic Concepts

Throughout the document we are working with the lemon namespace. To save a lot of typing we assume that a

using namespace lemon;

directive is added to the code at the beginning.

3.1 Directed Graphs

This section tells you how to work with a directed graph. We use ListDigraph, the most versatile graph structure.

The nodes and the arcs of a graph are identified by two datatypes called ListDigraph::Node and ListDigraph::Arc. You can add new components the graph by the addNode() and the addArc() member functions, like this:

  ListDigraph g;
  ListDigraph::Node a = g.addNode();
  ListDigraph::Node b = g.addNode();
  ListDigraph::Node c = g.addNode();
  ListDigraph::Node d = g.addNode();

  g.addArc(a,b);
  g.addArc(b,c);
  g.addArc(c,d);
  g.addArc(d,a);

Of course, addArc() also returns the created arc:

  ListDigraph::Arc diag = g.addArc(a,c);

Note:

You can also remove nodes or arcs with the erase(), but this operation may not be available with all graph structures.

Two other important member functions are source() and target(). They gives back the to end nodes of and arc.

  if(g.source(e)==g.target(e))
    std::cout << "This is a loop arc" << std::endl;

3.1.1 Iterators

Now assume you want to list the elements of the graph. For this purpose the the graphs provides several iterators. For example for following code will cound the number of nodes in a graph.

  int cnt = 0;
  for(ListDigraph::NodeIt n(g); n!=INVALID; ++n)
    cnt++;
  std::cout << "Number of nodes: " << cnt << std::endl;

Here ListDigraph::NodeIt is an iterator class that lists the nodes. You must give the graph to the constructor and it will be set to the first node. The next node is obtained by the prefix ++ operator. If there is no more nodes in the graph, the iterator will be set to INVALID.

Note:

INVALID is a global constant in lemon and it converts to and compares with each and every iterators in LEMON.

The iterators converts to the corresponding descriptor types. For example to following code will add a full graph to the existing nodes.

  for(ListDigraph::NodeIt u(g); u!=INVALID; ++u)
    for(ListDigraph::NodeIt v(g); v!=INVALID; ++v)
      if(u!=v) g.addArc(u,v);

The items are also ordered by the 'less than' operator. For example this code will add only one of the opposite arcs.

  for(ListDigraph::NodeIt u(g); u!=INVALID; ++u)
    for(ListDigraph::NodeIt v(g); v!=INVALID; ++v)
      if(u<v) g.addArc(u,v);

Warning:

There order in which the iterator visits the items is undefined. The only thing you may assume that they will list the items in the same order until the graph is not changed.

Similarly, ListDigraph::ArcIt lists the arcs. Its usage is the same as of ListDigraph::NodeIt.

  int cnt = 0;
  for(ListDigraph::ArcIt a(g); a!=INVALID; ++a)
    cnt++;
  std::cout << "Number of arcs: " << cnt << std::endl;

Finally, you can also list the arcs starting from or arriving at a certain node with ListDigraph::OutArcIt and ListDigraph::InArcIt. Their usage are the same, but you must also give the node to the constructor.

  int cnt = 0;
  for(ListDigraph::OutArcIt a(g,start); a!=INVALID; ++a)
    cnt++;
  std::cout << "Number of arcs leaving the node 'start': " << cnt << std::endl;

3.1.2 Maps

The concept of "Maps" is another fundamental part of LEMON. They allow assigning values of any type to the nodes or arcs of a graph. The default maps provided by the graph structures have a couple of nice properties.

• Fast. Accessing (reading/writing) the values are as fast as a simple vector reading/writing
• Dynamic. Whenever you need, you can allocate new maps in your code, just as a local variable. So when you leave its scope, it will be de-allocated automatically.
• Automatic. If you add new nodes or arcs to the graph, the storage of the existing maps will automatically expanded and the new slots will be initialized. On the removal of an item, the corresponding values in the maps are properly destructed.

So, if you want to assign int values to each node, you have to allocate a concepts::Digraph::Node Map "NodeMap<int>".

  ListDigraph::NodeMap<int> map(g);

As you see, the graph you want to assign a map is given to the constructor. Then you can access its element as if it were a vector.

  map[a]=2;
  map[b]=3;
  map[c]=map[a]+map[b];

As a more complex example, let's create a map that assigns a unique integer number to each node.

  ListDigraph::NodeMap<int> id(g);
  int cnt=0;
  for(ListDigraph::NodeIt n(g); n!=INVALID; ++n, ++cnt)
    id[n]=cnt;

You can also give an initial value of the elements as a second parameter.

For example the following code puts the number of outgoing edges in a map.

  ListDigraph::NodeMap<int> out_deg(g,0);

  for(ListDigraph::ArcIt a(g); a!=INVALID; ++a)
    out_deg[g.source(a)]++;

Warning:

The initial value will apply to the existing items only. If you add new nodes/arcs to the graph, then the corresponding values in the map will be initialized with the default constructor of the type.

<< 2 Compile Your First Code | Home | License Terms >>