3 Basic Concepts

Throughout the tutorial 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

The core features of LEMON are the data structures, algorithms and auxiliary tools that make it possible to represent graphs and working with them easily and efficiently. This section tells you how to work with a directed graph (digraph, for short) in LEMON. Here we use ListDigraph, the most versatile digraph structure. (The library also provides other digraph types, see later.)

For using ListDigraph, you must include the header file list_graph.h like this:

#include <lemon/list_graph.h>

The default constructor of the class creates an empty digraph.

  ListDigraph g;

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

  ListDigraph::Node x = g.addNode();
  ListDigraph::Node y = g.addNode();
  ListDigraph::Node z = g.addNode();

  g.addArc(x,y);
  g.addArc(y,z);
  g.addArc(z,x);

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

  ListDigraph::Arc arc = g.addArc(x,z);

Parallel and loop arcs are also supported.

  ListDigraph::Arc parallel = g.addArc(x,y);
  ListDigraph::Arc loop = g.addArc(x,x);

Note:

Using ListDigraph, you can also remove nodes or arcs with the erase() function. Moreover, this class provides several other operations, see its documentation for more information. However, not all graph structures support the addition and deletion of graph items (see 8.1 Graph Concepts).

Two important member functions of the directed graphs are source() and target(). They give back the two end nodes of an arc (as Node objects).

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

Each graph item has a non-negative integer identifier, which can be obtained using the id() function of the graph structure. These identifiers are unique with respect to a certain item type in a graph, but a node and an arc may have the same id.

  std::cout << "Arc " << g.id(arc) << " goes from node "
    << g.id(g.source(arc)) << " to node " << g.id(g.target(arc)) << std::endl;

Note:

In fact, the Node and Arc types are typically simple wrapper classes for a single int value, which is the identifier of the item.

3.2 Iterators

Let us assume you want to list the elements of the graph. For this purpose, the graph structures provide several iterators. For example, the following code will count 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;

ListDigraph::NodeIt is an iterator class that lists the nodes. The name of an iterator type starts with a name that refers to the iterated objects and ends with 'It'.

Using NodeIt, you must give the graph object to the constructor and the iterator will be set to the first node. The next node is obtained by the prefix ++ operator. If there are no more nodes in the graph, the iterator will be set to INVALID, which is exploited in the stop condition of the loop.

Note:

INVALID is a constant in the lemon namespace, which converts to and compares with each and every iterator and graph item type. Thus, you can even assign INVALID to a Node or Arc object.

The iterators convert to the corresponding item types. For example, the identifiers of the nodes can be printed like this.

  for (ListDigraph::NodeIt n(g); n != INVALID; ++n)
    std::cout << g.id(n) << std::endl;

As an other example, the following code adds 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);

Note:

Contrary to the iterators in the C++ Standard Template Library (STL), LEMON iterators are convertible to the corresponding item types without having to use operator*(). This is not confusing, since the program context always indicates whether we refer to the iterator or to the graph item (they do not have conflicting functionalities).

The graph items are also ordered by the 'less than' operator (with respect to their integer identifiers). 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:

The order in which the iterators visit 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 is the same, but you must also give the node to the constructor.

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

Note:

LEMON provides functions for counting the nodes and arcs of a digraph: countNodes(), countArcs(), countInArcs(), countOutArcs(). Using them is not just simpler than the above loops, but they could be much faster, since several graph types support constant time item counting.

3.3 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 standard maps provided by the graph structures have a couple of nice properties.

• Fast. Accessing (reading/writing) the values is 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.

By principle, the graph classes represent only the pure structure of the graph (i.e. the nodes and arcs and their connections). All data that are assigned to the items of the graph (e.g. node labels, arc costs or capacities) must be stored separately using maps.

Note:

These maps must not be confused with std::map, since they provide O(1) time access to the elements instead of O(log n).

So, if you want to assign int values to each node, you have to allocate a 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[x] = 2;
  map[y] = 3;
  map[z] = map[x] + map[y];

Any kind of data can be assigned to the graph items (assuming that the type has a default constructor).

  ListDigraph::NodeMap<std::string> name(g);
  name[x] = "Node A";
  name[y] = "Node B";

As a more complex example, let us create a map that assigns char labels to the nodes.

  ListDigraph::NodeMap<char> label(g);
  char ch = 'A';
  for (ListDigraph::NodeIt n(g); n != INVALID; ++n)
    label[n] = ch++;

When you create a map, you can also give an initial value of the elements as a second parameter. For example, the following code puts the number of outgoing arcs for each node 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 currently 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.

3.4 Naming Conventions

In LEMON, there are some naming conventions you might already notice in the above examples.

The name of a source file is written lowercase and the words are separated with underscores (e.g. list_graph.h). All header files are located in the lemon subdirectory, so you can include them like this.

#include <lemon/header_file.h>

The name of a class or any type looks like the following (e.g. ListDigraph, Node, NodeIt etc.).

AllWordsCapitalizedWithoutUnderscores

The name of a function looks like the following (e.g. source(), target(), countNodes(), countArcs() etc.).

firstWordLowerCaseRestCapitalizedWithoutUnderscores

The names of constants and macros look like the following (e.g. INVALID).

ALL_UPPER_CASE_WITH_UNDERSCORES

For more details, see LEMON Coding Style.

<< 2 Compile Your First Code | Home | 4 Algorithms >>