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