doc/graphs.dox
author kpeter
Mon, 18 Feb 2008 03:34:16 +0000
changeset 2577 2c6204d4b0f6
parent 2476 059dcdda37c5
permissions -rw-r--r--
Add a cost scaling min cost flow algorithm.

Add a cost scaling algorithm, which is performing generalized
push-relabel operations. It is almost as efficient as the capacity
scaling algorithm, but slower than network simplex.
alpar@2391
     1
/* -*- C++ -*-
alpar@2391
     2
 *
alpar@2391
     3
 * This file is a part of LEMON, a generic C++ optimization library
alpar@2391
     4
 *
alpar@2553
     5
 * Copyright (C) 2003-2008
alpar@2391
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@2391
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@2391
     8
 *
alpar@2391
     9
 * Permission to use, modify and distribute this software is granted
alpar@2391
    10
 * provided that this copyright notice appears in all copies. For
alpar@2391
    11
 * precise terms see the accompanying LICENSE file.
alpar@2391
    12
 *
alpar@2391
    13
 * This software is provided "AS IS" with no warranty of any kind,
alpar@2391
    14
 * express or implied, and with no claim as to its suitability for any
alpar@2391
    15
 * purpose.
alpar@2391
    16
 *
alpar@2391
    17
 */
alpar@2391
    18
kpeter@2476
    19
namespace lemon {
kpeter@2476
    20
ladanyi@666
    21
/*!
ladanyi@1638
    22
\page graphs Graphs
ladanyi@666
    23
deba@2111
    24
\todo Write a new Graphs page. I think it should be contain the Graph,
deba@2111
    25
UGraph and BpUGraph concept. It should be describe the iterators and
deba@2111
    26
the basic functions and the differences of the implementations.
deba@2111
    27
alpar@921
    28
The primary data structures of LEMON are the graph classes. They all
alpar@756
    29
provide a node list - edge list interface, i.e. they have
alpar@756
    30
functionalities to list the nodes and the edges of the graph as well
deba@2116
    31
as  incoming and outgoing edges of a given node. 
alpar@756
    32
kpeter@2476
    33
Each graph should meet the \ref concepts::Graph "Graph" concept.
deba@2116
    34
This concept does not make it possible to change the graph (i.e. it is
deba@2116
    35
not possible to add or delete edges or nodes). Most of the graph
deba@2116
    36
algorithms will run on these graphs.
alpar@756
    37
alpar@756
    38
deba@2116
    39
In case of graphs meeting the full feature
kpeter@2476
    40
\ref concepts::ErasableGraph "ErasableGraph" concept
deba@2116
    41
you can also erase individual edges and nodes in arbitrary order.
deba@2116
    42
deba@2116
    43
The implemented graph structures are the following.
kpeter@2476
    44
\li \ref ListGraph is the most versatile graph class. It meets
kpeter@2476
    45
the \ref concepts::ErasableGraph "ErasableGraph" concept
athos@1168
    46
and it also has some convenient extra features.
kpeter@2476
    47
\li \ref SmartGraph is a more memory efficient version of \ref ListGraph.
kpeter@2476
    48
The price of this is that it only meets the
kpeter@2476
    49
\ref concepts::ExtendableGraph "ExtendableGraph" concept,
alpar@756
    50
so you cannot delete individual edges or nodes.
kpeter@2476
    51
\li \ref FullGraph "FullGraph"
alpar@1200
    52
implements a complete graph. It is a
kpeter@2476
    53
\ref concepts::Graph "Graph", so you cannot
alpar@756
    54
change the number of nodes once it is constructed. It is extremely memory
alpar@756
    55
efficient: it uses constant amount of memory independently from the number of
alpar@1043
    56
the nodes of the graph. Of course, the size of the \ref maps-page "NodeMap"'s and
alpar@1043
    57
\ref maps-page "EdgeMap"'s will depend on the number of nodes.
alpar@756
    58
kpeter@2476
    59
\li \ref NodeSet "NodeSet" implements a graph with no edges. This class
alpar@921
    60
can be used as a base class of \ref lemon::EdgeSet "EdgeSet".
kpeter@2476
    61
\li \ref EdgeSet "EdgeSet" can be used to create a new graph on
alpar@873
    62
the node set of another graph. The base graph can be an arbitrary graph and it
kpeter@2476
    63
is possible to attach several \ref EdgeSet "EdgeSet"'s to a base graph.
alpar@756
    64
alpar@756
    65
\todo Don't we need SmartNodeSet and SmartEdgeSet?
alpar@756
    66
\todo Some cross-refs are wrong.
alpar@756
    67
athos@1168
    68
The graph structures themselves can not store data attached
alpar@756
    69
to the edges and nodes. However they all provide
alpar@1043
    70
\ref maps-page "map classes"
alpar@756
    71
to dynamically attach data the to graph components.
alpar@756
    72
alpar@921
    73
The following program demonstrates the basic features of LEMON's graph
ladanyi@666
    74
structures.
ladanyi@666
    75
ladanyi@666
    76
\code
ladanyi@666
    77
#include <iostream>
alpar@921
    78
#include <lemon/list_graph.h>
ladanyi@666
    79
alpar@921
    80
using namespace lemon;
ladanyi@666
    81
ladanyi@666
    82
int main()
ladanyi@666
    83
{
ladanyi@666
    84
  typedef ListGraph Graph;
ladanyi@666
    85
\endcode
ladanyi@666
    86
alpar@921
    87
ListGraph is one of LEMON's graph classes. It is based on linked lists,
ladanyi@666
    88
therefore iterating throuh its edges and nodes is fast.
ladanyi@666
    89
ladanyi@666
    90
\code
ladanyi@666
    91
  typedef Graph::Edge Edge;
ladanyi@666
    92
  typedef Graph::InEdgeIt InEdgeIt;
ladanyi@666
    93
  typedef Graph::OutEdgeIt OutEdgeIt;
ladanyi@666
    94
  typedef Graph::EdgeIt EdgeIt;
ladanyi@666
    95
  typedef Graph::Node Node;
ladanyi@666
    96
  typedef Graph::NodeIt NodeIt;
ladanyi@666
    97
ladanyi@666
    98
  Graph g;
ladanyi@666
    99
  
ladanyi@666
   100
  for (int i = 0; i < 3; i++)
ladanyi@666
   101
    g.addNode();
ladanyi@666
   102
  
ladanyi@875
   103
  for (NodeIt i(g); i!=INVALID; ++i)
ladanyi@875
   104
    for (NodeIt j(g); j!=INVALID; ++j)
ladanyi@666
   105
      if (i != j) g.addEdge(i, j);
ladanyi@666
   106
\endcode
ladanyi@666
   107
athos@1168
   108
After some convenient typedefs we create a graph and add three nodes to it.
athos@1168
   109
Then we add edges to it to form a complete graph.
ladanyi@666
   110
ladanyi@666
   111
\code
ladanyi@666
   112
  std::cout << "Nodes:";
ladanyi@875
   113
  for (NodeIt i(g); i!=INVALID; ++i)
ladanyi@666
   114
    std::cout << " " << g.id(i);
ladanyi@666
   115
  std::cout << std::endl;
ladanyi@666
   116
\endcode
ladanyi@666
   117
ladanyi@666
   118
Here we iterate through all nodes of the graph. We use a constructor of the
ladanyi@875
   119
node iterator to initialize it to the first node. The operator++ is used to
ladanyi@875
   120
step to the next node. Using operator++ on the iterator pointing to the last
ladanyi@875
   121
node invalidates the iterator i.e. sets its value to
kpeter@2476
   122
\ref INVALID. This is what we exploit in the stop condition.
ladanyi@666
   123
ladanyi@875
   124
The previous code fragment prints out the following:
ladanyi@666
   125
ladanyi@666
   126
\code
ladanyi@666
   127
Nodes: 2 1 0
ladanyi@666
   128
\endcode
ladanyi@666
   129
ladanyi@666
   130
\code
ladanyi@666
   131
  std::cout << "Edges:";
ladanyi@875
   132
  for (EdgeIt i(g); i!=INVALID; ++i)
alpar@986
   133
    std::cout << " (" << g.id(g.source(i)) << "," << g.id(g.target(i)) << ")";
ladanyi@666
   134
  std::cout << std::endl;
ladanyi@666
   135
\endcode
ladanyi@666
   136
ladanyi@666
   137
\code
ladanyi@666
   138
Edges: (0,2) (1,2) (0,1) (2,1) (1,0) (2,0)
ladanyi@666
   139
\endcode
ladanyi@666
   140
athos@1168
   141
We can also iterate through all edges of the graph very similarly. The 
athos@1168
   142
\c target and
athos@1168
   143
\c source member functions can be used to access the endpoints of an edge.
ladanyi@666
   144
ladanyi@666
   145
\code
ladanyi@666
   146
  NodeIt first_node(g);
ladanyi@666
   147
ladanyi@666
   148
  std::cout << "Out-edges of node " << g.id(first_node) << ":";
ladanyi@875
   149
  for (OutEdgeIt i(g, first_node); i!=INVALID; ++i)
alpar@986
   150
    std::cout << " (" << g.id(g.source(i)) << "," << g.id(g.target(i)) << ")"; 
ladanyi@666
   151
  std::cout << std::endl;
ladanyi@666
   152
ladanyi@666
   153
  std::cout << "In-edges of node " << g.id(first_node) << ":";
ladanyi@875
   154
  for (InEdgeIt i(g, first_node); i!=INVALID; ++i)
alpar@986
   155
    std::cout << " (" << g.id(g.source(i)) << "," << g.id(g.target(i)) << ")"; 
ladanyi@666
   156
  std::cout << std::endl;
ladanyi@666
   157
\endcode
ladanyi@666
   158
ladanyi@666
   159
\code
ladanyi@666
   160
Out-edges of node 2: (2,0) (2,1)
ladanyi@666
   161
In-edges of node 2: (0,2) (1,2)
ladanyi@666
   162
\endcode
ladanyi@666
   163
ladanyi@666
   164
We can also iterate through the in and out-edges of a node. In the above
ladanyi@666
   165
example we print out the in and out-edges of the first node of the graph.
ladanyi@666
   166
ladanyi@666
   167
\code
ladanyi@666
   168
  Graph::EdgeMap<int> m(g);
ladanyi@666
   169
ladanyi@875
   170
  for (EdgeIt e(g); e!=INVALID; ++e)
ladanyi@666
   171
    m.set(e, 10 - g.id(e));
ladanyi@666
   172
  
ladanyi@666
   173
  std::cout << "Id Edge  Value" << std::endl;
ladanyi@875
   174
  for (EdgeIt e(g); e!=INVALID; ++e)
alpar@986
   175
    std::cout << g.id(e) << "  (" << g.id(g.source(e)) << "," << g.id(g.target(e))
ladanyi@666
   176
      << ") " << m[e] << std::endl;
ladanyi@666
   177
\endcode
ladanyi@666
   178
ladanyi@666
   179
\code
ladanyi@666
   180
Id Edge  Value
ladanyi@666
   181
4  (0,2) 6
ladanyi@666
   182
2  (1,2) 8
ladanyi@666
   183
5  (0,1) 5
ladanyi@666
   184
0  (2,1) 10
ladanyi@666
   185
3  (1,0) 7
ladanyi@666
   186
1  (2,0) 9
ladanyi@666
   187
\endcode
ladanyi@666
   188
alpar@873
   189
As we mentioned above, graphs are not containers rather
alpar@921
   190
incidence structures which are iterable in many ways. LEMON introduces
ladanyi@666
   191
concepts that allow us to attach containers to graphs. These containers are
ladanyi@666
   192
called maps.
ladanyi@666
   193
athos@1168
   194
In the example above we create an EdgeMap which assigns an integer value to all
ladanyi@666
   195
edges of the graph. We use the set member function of the map to write values
ladanyi@666
   196
into the map and the operator[] to retrieve them.
ladanyi@666
   197
ladanyi@666
   198
Here we used the maps provided by the ListGraph class, but you can also write
alpar@1043
   199
your own maps. You can read more about using maps \ref maps-page "here".
ladanyi@666
   200
ladanyi@666
   201
*/
kpeter@2476
   202
kpeter@2476
   203
}
kpeter@2476
   204