Basic concepts

The graph classes

The most important classes in LEMON are the graph classes. An instance of a graph class is the representation of the mathematical graph. It holds the topology and every structural information of the graph. The structural manipulations are also provided by the graph object. There is no universal graph class instead we have different classes for different purposes. They can differ in many ways, but all have to satisfy one or more graph concepts which are standardized interfaces to work with the rest of the library. The most basic concept is the Graph.
A good example is the ListGraph which we already know from Hello World and will be used in our examples as well.

One main advantage of the templates are, that you can write your own graph classes. As long as they provide the interface a concept is defining all the LEMON algorithms and classes will work with it properly - no representation or implementation is written into stone.

Nodes

To refer to a node of a graph we need some kind of typed variable. Graph classes have the Node public type for this purpose. Stacking by the last example:

 lemon::ListGraph::Node 

If the graph fits the ExtendableGraphComponent concept, then you can add new nodes to the graph with the addNode() member function. It returns the newly added node (as value). So if you need the new node to do something useful with, for example create an edge, assign a value to it through Maps I. maps.

 lemon::ListGraph::Node  new_node = graph.addNode(); 

If the graph fits into the ErasableGraphComponent concept you can also remove nodes from the graph with the erase() member function.

 graph.erase( new_node ); 

You don't have to store every node in a variable, you can access individual nodes with node iterators discussed in the next section. But how do you know which node is which?
The graph class has the id( Node n ) member function providing an unique identifier assigned to every node.

Edges

An Edge is what you think it is. It goes from one node to another node (they can be identical if the edge is a loop). If the graph class is directed, the Edge is directed too. Otherwise the edge is considered undirected and called UEdge.

 lemon::ListUGraph::UEdge 

The addEdge() member function will create a new edge. It has two arguments, the source node and the target node. The graph class must be extendable.

 lemon::ListGraph::Edge  new_edge = graph.addEdge( src_node, trg_node ); 

You can handle edges similar as nodes. The erase() member function has an edge taking overload too.

You can ask for the source or target node of the edge by the corresponding member functions:

graph.source( new_edge );
lemon::ListGraph::Node  n = graph.target( new_edge ); 

These functions are always legal even if the graph is undirected. UEdge has a default direction.

Iterators

Graphs are some kind of containers. And as you expect they have iterator types. One for nodes and a couple for edges - and special classes can have additional iterators too. An example:

 lemon::ListGraph::NodeIt 

This is a node iterator. Every iterator type starts with a name that refers to the iterated object, and ends with 'It'.

LEMON style iterators differ from stl or boost iterators in a very tasty way. A graph has no begin or end - or at least a generic graph class has none. If by some topology you could pick a good begin node, it would be misleading and incorrect. A LEMON style iterator must be initialized at construction time. The constructor takes the needed parameters - by a node iterator it's the graph object. And will be compared to the lemon::INVALID to check if it's still valid. Every iterator can be compared to INVALID. No begin() or end() needed.
Let's see these things working together:

for( ListGraph::NodeIt n(graph); n != INVALID; ++n )
    do_useful_things_with_node(n);

Note that the function do_useful_things_with_node() expects a Node type argument ad we just gave him the iterator. LEMON style iterators must provide "on demand dereferencing". For example a NodeIt can be used everywhere a Node could. (In some graph classes Node is the base class of NodeIt. But in other cases this is implemented through typecast operator.)

Very important! The iteration has no defined order. There is absolutely no warranty that the next time the iteration will give us the nodes in the same order. Don't use this order to identify nodes! Use the id() member function of the graph class described above. (There is a powerful technique using maps right in the next page.)

The EdgeIt works exactly the same - nothing more to say. But there are InEdgeIt and OutEdgeIt by directed graphs and IncEdgeIt by undirected graphs. They take two arguments. The first is a graph, the second is certain node of the graph. InEdgeIt iterates on the incoming edges of that node and OutEdgeIt does it on the outgoing edges. The IncEdgeIt of course iterates every edge connecting to the given node.

for( ListGraph::NodeIt n(graph); n != INVALID; ++n ) {
  int in = 0, out = 0;
  for( ListGraph::InEdgeIt e(graph,n); e != INVALID; ++e ) ++in;
  for( ListGraph::OutEdgeIt e(graph,n); e != INVALID; ++e ) ++out;

  std::cout << "#" << graph.id(n) << " node has " << in << " incoming and "
    << out << "outgoing edges." << std::endl;
}

ListGraph - a versatile directed graph

As you see ListGraph satisfies most of the basic concepts and ideal for general graph representations. It has an undirected version too: ListUGraph.