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