doc/basic_concepts.dox
author deba
Wed, 21 Feb 2007 13:49:19 +0000
changeset 2377 83775fab25dc
parent 2288 ef8af928c54e
child 2391 14a343be7a5a
permissions -rw-r--r--
Minor changes
alpar@2350
     1
namespace lemon {
alpar@2350
     2
alpar@2195
     3
/**
alpar@2195
     4
\page basic_concepts Basic concepts
alpar@2195
     5
alpar@2195
     6
\section basic_graph The graph classes
athos@2288
     7
The most important classes in LEMON are the graph classes. An instance of a graph
alpar@2195
     8
class is the representation of the mathematical graph. It holds the topology and
alpar@2195
     9
every structural information of the graph. The structural manipulations are also
alpar@2195
    10
provided by the graph object. There is no universal graph class instead we have
alpar@2195
    11
different classes for different purposes. They can differ in many ways, but all
alpar@2195
    12
have to satisfy one or more \ref concept "graph concepts" which are standardized
athos@2288
    13
interfaces to work with the rest of the library. The most basic concept is the
alpar@2195
    14
\ref Graph.<br>
alpar@2195
    15
A good example is the \ref ListGraph which we already know from Hello World and
alpar@2195
    16
will be used in our examples as well.
alpar@2195
    17
alpar@2195
    18
One main advantage of the templates are, that you can write your own graph classes.
alpar@2195
    19
As long as they provide the interface a concept is defining all the LEMON algorithms
alpar@2195
    20
and classes will work with it properly - no representation or implementation is
alpar@2195
    21
written into stone.
alpar@2195
    22
alpar@2195
    23
alpar@2195
    24
\subsection basic_node Nodes
alpar@2195
    25
To refer to a node of a graph we need some kind of typed variable. Graph classes
alpar@2195
    26
have the Node public type for this purpose. Stacking by the last example:
alpar@2195
    27
\code lemon::ListGraph::Node \endcode
alpar@2195
    28
alpar@2195
    29
If the graph fits the ExtendableGraphComponent concept, then you can add new nodes
alpar@2195
    30
to the graph with the addNode() member function. It returns the newly added node
athos@2288
    31
(as value). So if you need the new node to do something useful with, for example
athos@2288
    32
create an edge, assign a value to it through \ref map1 maps.
alpar@2195
    33
\code lemon::ListGraph::Node  new_node = graph.addNode(); \endcode
alpar@2195
    34
athos@2288
    35
If the graph fits into the ErasableGraphComponent concept you can also remove nodes
alpar@2195
    36
from the graph with the erase() member function.
alpar@2195
    37
\code graph.erase( new_node ); \endcode
alpar@2195
    38
alpar@2195
    39
You don't have to store every node in a variable, you can access individual nodes
alpar@2195
    40
with node iterators discussed in the next section. But how do you know which
alpar@2195
    41
node is which?<br>
alpar@2195
    42
The graph class has the id( Node n ) member function providing an unique identifier
alpar@2195
    43
assigned to every node.
alpar@2195
    44
alpar@2195
    45
alpar@2195
    46
\subsection basic_edge Edges
alpar@2195
    47
An Edge is what you think it is. It goes from one node to another node (they can
athos@2288
    48
be identical if the edge is a loop). If the graph class is directed, the Edge is directed too. Otherwise
alpar@2195
    49
the edge is considered undirected and called UEdge.
alpar@2195
    50
\code lemon::ListUGraph::UEdge \endcode
alpar@2195
    51
alpar@2195
    52
The addEdge() member function will create a new edge. It has two arguments, the
alpar@2195
    53
source node and the target node. The graph class must be extendable.
alpar@2195
    54
\code lemon::ListGraph::Edge  new_edge = graph.addEdge( src_node, trg_node ); \endcode
athos@2288
    55
You can handle edges similar as nodes. The erase() member function has an edge taking
alpar@2195
    56
overload too.
alpar@2195
    57
alpar@2195
    58
You can ask for the source or target node of the edge by the corresponding member
alpar@2195
    59
functions:
alpar@2195
    60
\code
alpar@2195
    61
graph.source( new_edge );
alpar@2195
    62
lemon::ListGraph::Node  n = graph.target( new_edge ); \endcode
alpar@2195
    63
These functions are always legal even if the graph is undirected. UEdge has a
alpar@2195
    64
default direction.
alpar@2195
    65
alpar@2195
    66
alpar@2195
    67
\section basic_iterators Iterators
alpar@2195
    68
Graphs are some kind of containers. And as you expect they have iterator types.
athos@2288
    69
One for nodes and a couple for edges - and special classes can have additional
alpar@2195
    70
iterators too. An example:
alpar@2195
    71
\code lemon::ListGraph::NodeIt \endcode
athos@2288
    72
This is a node iterator. Every iterator type starts with a name that refers to
athos@2288
    73
the iterated object, and ends with 'It'.
alpar@2195
    74
athos@2288
    75
LEMON style iterators differ from \c stl or \c boost iterators in a very tasty
alpar@2195
    76
way. A graph has no begin or end - or at least a generic graph class has none.
alpar@2195
    77
If by some topology you could pick a good begin node, it would be misleading and
alpar@2195
    78
incorrect. A LEMON style iterator must be initialized at construction time.
alpar@2195
    79
The constructor takes the needed parameters - by a node iterator it's the graph
alpar@2195
    80
object. And will be compared to the lemon::INVALID to check if it's still valid.
alpar@2195
    81
Every iterator can be compared to INVALID. No \c begin() or \c end() needed.<br>
alpar@2195
    82
Let's see these things working together:
alpar@2195
    83
\code
alpar@2195
    84
for( ListGraph::NodeIt n(graph); n != INVALID; ++n )
athos@2288
    85
    do_useful_things_with_node(n);
alpar@2195
    86
\endcode
alpar@2195
    87
Note that the function \c do_useful_things_with_node() expects a Node type argument
alpar@2195
    88
ad we just gave him the iterator. LEMON style iterators must provide "on demand
alpar@2195
    89
dereferencing". For example a NodeIt can be used everywhere a Node could. (In some
alpar@2195
    90
graph classes Node is the base class of NodeIt. But in other cases this is implemented
alpar@2195
    91
through typecast operator.)
alpar@2195
    92
alpar@2195
    93
<b>Very important!</b> The iteration has no defined order. There is absolutely no
athos@2288
    94
warranty that the next time the iteration will give us the nodes in the same order.
alpar@2195
    95
Don't use this order to identify nodes! Use the \c id() member function of the
alpar@2195
    96
graph class described above. (There is a powerful technique using maps right in
alpar@2195
    97
the next page.)
alpar@2195
    98
alpar@2195
    99
The \ref EdgeIt works exactly the same - nothing more to say. But there are \ref InEdgeIt
alpar@2195
   100
and \ref OutEdgeIt by directed graphs and \ref IncEdgeIt by undirected graphs.
alpar@2195
   101
They take two arguments. The first is a graph, the second is certain node of the
alpar@2195
   102
graph. InEdgeIt iterates on the incoming edges of that node and OutEdgeIt does it
alpar@2195
   103
on the outgoing edges. The IncEdgeIt of course iterates every edge connecting to
alpar@2195
   104
the given node.
alpar@2195
   105
alpar@2195
   106
\code
alpar@2195
   107
for( ListGraph::NodeIt n(graph); n != INVALID; ++n ) {
alpar@2195
   108
  int in = 0, out = 0;
alpar@2195
   109
  for( ListGraph::InEdgeIt e(graph,n); e != INVALID; ++e ) ++in;
alpar@2195
   110
  for( ListGraph::OutEdgeIt e(graph,n); e != INVALID; ++e ) ++out;
alpar@2195
   111
alpar@2195
   112
  std::cout << "#" << graph.id(n) << " node has " << in << " incoming and "
alpar@2195
   113
    << out << "outgoing edges." << std::endl;
alpar@2195
   114
}
alpar@2195
   115
\endcode
alpar@2195
   116
alpar@2195
   117
alpar@2195
   118
\section basic_ListGraph ListGraph - a versatile directed graph
alpar@2195
   119
As you see ListGraph satisfies most of the basic concepts and ideal for general
alpar@2195
   120
graph representations. It has an undirected version too: ListUGraph.
alpar@2195
   121
*/
alpar@2350
   122
alpar@2350
   123
}