doc/graphs.dox
author athos
Thu, 24 Feb 2005 17:04:49 +0000
changeset 1175 6205eebd62fc
parent 1043 52a2201a88e9
child 1200 ae69f556b429
permissions -rw-r--r--
Everithing is half-done, but some progress has been made in writing documentation.
ladanyi@666
     1
/*!
ladanyi@666
     2
ladanyi@666
     3
\page graphs How to use graphs
ladanyi@666
     4
alpar@921
     5
The primary data structures of LEMON are the graph classes. They all
alpar@756
     6
provide a node list - edge list interface, i.e. they have
alpar@756
     7
functionalities to list the nodes and the edges of the graph as well
athos@1168
     8
as  incoming and outgoing edges of a given node. 
alpar@756
     9
alpar@756
    10
alpar@873
    11
Each graph should meet the
klao@959
    12
\ref lemon::concept::StaticGraph "StaticGraph" concept.
alpar@873
    13
This concept does not
athos@1168
    14
make it possible to change the graph (i.e. it is not possible to add
alpar@756
    15
or delete edges or nodes). Most of the graph algorithms will run on
alpar@756
    16
these graphs.
alpar@756
    17
alpar@873
    18
The graphs meeting the
klao@959
    19
\ref lemon::concept::ExtendableGraph "ExtendableGraph"
alpar@873
    20
concept allow node and
athos@1168
    21
edge addition. You can also "clear" such a graph (i.e. erase all edges and nodes ).
alpar@756
    22
alpar@873
    23
In case of graphs meeting the full feature
klao@959
    24
\ref lemon::concept::ErasableGraph "ErasableGraph"
alpar@873
    25
concept
athos@1168
    26
you can also erase individual edges and nodes in arbitrary order.
alpar@756
    27
alpar@756
    28
The implemented graph structures are the following.
alpar@921
    29
\li \ref lemon::ListGraph "ListGraph" is the most versatile graph class. It meets
klao@959
    30
the \ref lemon::concept::ErasableGraph "ErasableGraph" concept
athos@1168
    31
and it also has some convenient extra features.
alpar@921
    32
\li \ref lemon::SmartGraph "SmartGraph" is a more memory
alpar@921
    33
efficient version of \ref lemon::ListGraph "ListGraph". The
athos@1168
    34
price of this is that it only meets the
klao@959
    35
\ref lemon::concept::ExtendableGraph "ExtendableGraph" concept,
alpar@756
    36
so you cannot delete individual edges or nodes.
alpar@921
    37
\li \ref lemon::SymListGraph "SymListGraph" and
alpar@921
    38
\ref lemon::SymSmartGraph "SymSmartGraph" classes are very similar to
alpar@921
    39
\ref lemon::ListGraph "ListGraph" and \ref lemon::SmartGraph "SmartGraph".
alpar@756
    40
The difference is that whenever you add a
alpar@756
    41
new edge to the graph, it actually adds a pair of oppositely directed edges.
alpar@756
    42
They are linked together so it is possible to access the counterpart of an
alpar@756
    43
edge. An even more important feature is that using these classes you can also
alpar@756
    44
attach data to the edges in such a way that the stored data
alpar@756
    45
are shared by the edge pairs. 
alpar@921
    46
\li \ref lemon::FullGraph "FullGraph"
athos@1168
    47
implements a complete graph. It is a \ref lemon::concept::StaticGraph, so you cannot
alpar@756
    48
change the number of nodes once it is constructed. It is extremely memory
alpar@756
    49
efficient: it uses constant amount of memory independently from the number of
alpar@1043
    50
the nodes of the graph. Of course, the size of the \ref maps-page "NodeMap"'s and
alpar@1043
    51
\ref maps-page "EdgeMap"'s will depend on the number of nodes.
alpar@756
    52
alpar@921
    53
\li \ref lemon::NodeSet "NodeSet" implements a graph with no edges. This class
alpar@921
    54
can be used as a base class of \ref lemon::EdgeSet "EdgeSet".
alpar@921
    55
\li \ref lemon::EdgeSet "EdgeSet" can be used to create a new graph on
alpar@873
    56
the node set of another graph. The base graph can be an arbitrary graph and it
alpar@921
    57
is possible to attach several \ref lemon::EdgeSet "EdgeSet"'s to a base graph.
alpar@756
    58
alpar@756
    59
\todo Don't we need SmartNodeSet and SmartEdgeSet?
alpar@756
    60
\todo Some cross-refs are wrong.
alpar@756
    61
athos@1168
    62
The graph structures themselves can not store data attached
alpar@756
    63
to the edges and nodes. However they all provide
alpar@1043
    64
\ref maps-page "map classes"
alpar@756
    65
to dynamically attach data the to graph components.
alpar@756
    66
alpar@921
    67
The following program demonstrates the basic features of LEMON's graph
ladanyi@666
    68
structures.
ladanyi@666
    69
ladanyi@666
    70
\code
ladanyi@666
    71
#include <iostream>
alpar@921
    72
#include <lemon/list_graph.h>
ladanyi@666
    73
alpar@921
    74
using namespace lemon;
ladanyi@666
    75
ladanyi@666
    76
int main()
ladanyi@666
    77
{
ladanyi@666
    78
  typedef ListGraph Graph;
ladanyi@666
    79
\endcode
ladanyi@666
    80
alpar@921
    81
ListGraph is one of LEMON's graph classes. It is based on linked lists,
ladanyi@666
    82
therefore iterating throuh its edges and nodes is fast.
ladanyi@666
    83
ladanyi@666
    84
\code
ladanyi@666
    85
  typedef Graph::Edge Edge;
ladanyi@666
    86
  typedef Graph::InEdgeIt InEdgeIt;
ladanyi@666
    87
  typedef Graph::OutEdgeIt OutEdgeIt;
ladanyi@666
    88
  typedef Graph::EdgeIt EdgeIt;
ladanyi@666
    89
  typedef Graph::Node Node;
ladanyi@666
    90
  typedef Graph::NodeIt NodeIt;
ladanyi@666
    91
ladanyi@666
    92
  Graph g;
ladanyi@666
    93
  
ladanyi@666
    94
  for (int i = 0; i < 3; i++)
ladanyi@666
    95
    g.addNode();
ladanyi@666
    96
  
ladanyi@875
    97
  for (NodeIt i(g); i!=INVALID; ++i)
ladanyi@875
    98
    for (NodeIt j(g); j!=INVALID; ++j)
ladanyi@666
    99
      if (i != j) g.addEdge(i, j);
ladanyi@666
   100
\endcode
ladanyi@666
   101
athos@1168
   102
After some convenient typedefs we create a graph and add three nodes to it.
athos@1168
   103
Then we add edges to it to form a complete graph.
ladanyi@666
   104
ladanyi@666
   105
\code
ladanyi@666
   106
  std::cout << "Nodes:";
ladanyi@875
   107
  for (NodeIt i(g); i!=INVALID; ++i)
ladanyi@666
   108
    std::cout << " " << g.id(i);
ladanyi@666
   109
  std::cout << std::endl;
ladanyi@666
   110
\endcode
ladanyi@666
   111
ladanyi@666
   112
Here we iterate through all nodes of the graph. We use a constructor of the
ladanyi@875
   113
node iterator to initialize it to the first node. The operator++ is used to
ladanyi@875
   114
step to the next node. Using operator++ on the iterator pointing to the last
ladanyi@875
   115
node invalidates the iterator i.e. sets its value to
alpar@921
   116
\ref lemon::INVALID "INVALID". This is what we exploit in the stop condition.
ladanyi@666
   117
ladanyi@875
   118
The previous code fragment prints out the following:
ladanyi@666
   119
ladanyi@666
   120
\code
ladanyi@666
   121
Nodes: 2 1 0
ladanyi@666
   122
\endcode
ladanyi@666
   123
ladanyi@666
   124
\code
ladanyi@666
   125
  std::cout << "Edges:";
ladanyi@875
   126
  for (EdgeIt i(g); i!=INVALID; ++i)
alpar@986
   127
    std::cout << " (" << g.id(g.source(i)) << "," << g.id(g.target(i)) << ")";
ladanyi@666
   128
  std::cout << std::endl;
ladanyi@666
   129
\endcode
ladanyi@666
   130
ladanyi@666
   131
\code
ladanyi@666
   132
Edges: (0,2) (1,2) (0,1) (2,1) (1,0) (2,0)
ladanyi@666
   133
\endcode
ladanyi@666
   134
athos@1168
   135
We can also iterate through all edges of the graph very similarly. The 
athos@1168
   136
\c target and
athos@1168
   137
\c source member functions can be used to access the endpoints of an edge.
ladanyi@666
   138
ladanyi@666
   139
\code
ladanyi@666
   140
  NodeIt first_node(g);
ladanyi@666
   141
ladanyi@666
   142
  std::cout << "Out-edges of node " << g.id(first_node) << ":";
ladanyi@875
   143
  for (OutEdgeIt i(g, first_node); i!=INVALID; ++i)
alpar@986
   144
    std::cout << " (" << g.id(g.source(i)) << "," << g.id(g.target(i)) << ")"; 
ladanyi@666
   145
  std::cout << std::endl;
ladanyi@666
   146
ladanyi@666
   147
  std::cout << "In-edges of node " << g.id(first_node) << ":";
ladanyi@875
   148
  for (InEdgeIt i(g, first_node); i!=INVALID; ++i)
alpar@986
   149
    std::cout << " (" << g.id(g.source(i)) << "," << g.id(g.target(i)) << ")"; 
ladanyi@666
   150
  std::cout << std::endl;
ladanyi@666
   151
\endcode
ladanyi@666
   152
ladanyi@666
   153
\code
ladanyi@666
   154
Out-edges of node 2: (2,0) (2,1)
ladanyi@666
   155
In-edges of node 2: (0,2) (1,2)
ladanyi@666
   156
\endcode
ladanyi@666
   157
ladanyi@666
   158
We can also iterate through the in and out-edges of a node. In the above
ladanyi@666
   159
example we print out the in and out-edges of the first node of the graph.
ladanyi@666
   160
ladanyi@666
   161
\code
ladanyi@666
   162
  Graph::EdgeMap<int> m(g);
ladanyi@666
   163
ladanyi@875
   164
  for (EdgeIt e(g); e!=INVALID; ++e)
ladanyi@666
   165
    m.set(e, 10 - g.id(e));
ladanyi@666
   166
  
ladanyi@666
   167
  std::cout << "Id Edge  Value" << std::endl;
ladanyi@875
   168
  for (EdgeIt e(g); e!=INVALID; ++e)
alpar@986
   169
    std::cout << g.id(e) << "  (" << g.id(g.source(e)) << "," << g.id(g.target(e))
ladanyi@666
   170
      << ") " << m[e] << std::endl;
ladanyi@666
   171
\endcode
ladanyi@666
   172
ladanyi@666
   173
\code
ladanyi@666
   174
Id Edge  Value
ladanyi@666
   175
4  (0,2) 6
ladanyi@666
   176
2  (1,2) 8
ladanyi@666
   177
5  (0,1) 5
ladanyi@666
   178
0  (2,1) 10
ladanyi@666
   179
3  (1,0) 7
ladanyi@666
   180
1  (2,0) 9
ladanyi@666
   181
\endcode
ladanyi@666
   182
alpar@873
   183
As we mentioned above, graphs are not containers rather
alpar@921
   184
incidence structures which are iterable in many ways. LEMON introduces
ladanyi@666
   185
concepts that allow us to attach containers to graphs. These containers are
ladanyi@666
   186
called maps.
ladanyi@666
   187
athos@1168
   188
In the example above we create an EdgeMap which assigns an integer value to all
ladanyi@666
   189
edges of the graph. We use the set member function of the map to write values
ladanyi@666
   190
into the map and the operator[] to retrieve them.
ladanyi@666
   191
ladanyi@666
   192
Here we used the maps provided by the ListGraph class, but you can also write
alpar@1043
   193
your own maps. You can read more about using maps \ref maps-page "here".
ladanyi@666
   194
ladanyi@666
   195
*/