Mercuriallemon-0.x / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
doc/graphs.dox
changeset 955 0a066f80e05f
parent 911 89a4fbb99cad
child 959 c80ef5912903
equal deleted inserted replaced
6:948b69fa7164 7:f5f3b081330f 
     1 /*!
 
     1 /*!
 
     2 
     2 
     3 \page graphs How to use graphs
 
     3 \page graphs How to use graphs
 
     4 
     4 
     5 The primary data structures of HugoLib are the graph classes. They all
 
     5 The primary data structures of LEMON are the graph classes. They all
 
     6 provide a node list - edge list interface, i.e. they have
 
     6 provide a node list - edge list interface, i.e. they have
 
     7 functionalities to list the nodes and the edges of the graph as well
 
     7 functionalities to list the nodes and the edges of the graph as well
 
     8 as in incoming and outgoing edges of a given node. 
     8 as in incoming and outgoing edges of a given node. 
     9 
     9 
    10 
    10 
    11 Each graph should meet the
 
    11 Each graph should meet the
 
    12 \ref hugo::skeleton::StaticGraph "StaticGraph" concept.
 
    12 \ref lemon::skeleton::StaticGraph "StaticGraph" concept.
 
    13 This concept does not
 
    13 This concept does not
 
    14 makes it possible to change the graph (i.e. it is not possible to add
 
    14 makes it possible to change the graph (i.e. it is not possible to add
 
    15 or delete edges or nodes). Most of the graph algorithms will run on
 
    15 or delete edges or nodes). Most of the graph algorithms will run on
 
    16 these graphs.
 
    16 these graphs.
 
    17 
    17 
    18 The graphs meeting the
 
    18 The graphs meeting the
 
    19 \ref hugo::skeleton::ExtendableGraph "ExtendableGraph"
 
    19 \ref lemon::skeleton::ExtendableGraph "ExtendableGraph"
 
    20 concept allow node and
 
    20 concept allow node and
 
    21 edge addition. You can also "clear" (i.e. erase all edges and nodes)
 
    21 edge addition. You can also "clear" (i.e. erase all edges and nodes)
 
    22 such a graph.
 
    22 such a graph.
 
    23 
    23 
    24 In case of graphs meeting the full feature
 
    24 In case of graphs meeting the full feature
 
    25 \ref hugo::skeleton::ErasableGraph "ErasableGraph"
 
    25 \ref lemon::skeleton::ErasableGraph "ErasableGraph"
 
    26 concept
 
    26 concept
 
    27 you can also erase individual edges and node in arbitrary order.
 
    27 you can also erase individual edges and node in arbitrary order.
 
    28 
    28 
    29 The implemented graph structures are the following.
 
    29 The implemented graph structures are the following.
 
    30 \li \ref hugo::ListGraph "ListGraph" is the most versatile graph class. It meets
 
    30 \li \ref lemon::ListGraph "ListGraph" is the most versatile graph class. It meets
 
    31 the \ref hugo::skeleton::ErasableGraph "ErasableGraph" concept
 
    31 the \ref lemon::skeleton::ErasableGraph "ErasableGraph" concept
 
    32 and it also have some convenience features.
 
    32 and it also have some convenience features.
 
    33 \li \ref hugo::SmartGraph "SmartGraph" is a more memory
 
    33 \li \ref lemon::SmartGraph "SmartGraph" is a more memory
 
    34 efficient version of \ref hugo::ListGraph "ListGraph". The
 
    34 efficient version of \ref lemon::ListGraph "ListGraph". The
 
    35 price of it is that it only meets the
 
    35 price of it is that it only meets the
 
    36 \ref hugo::skeleton::ExtendableGraph "ExtendableGraph" concept,
 
    36 \ref lemon::skeleton::ExtendableGraph "ExtendableGraph" concept,
 
    37 so you cannot delete individual edges or nodes.
 
    37 so you cannot delete individual edges or nodes.
 
    38 \li \ref hugo::SymListGraph "SymListGraph" and
 
    38 \li \ref lemon::SymListGraph "SymListGraph" and
 
    39 \ref hugo::SymSmartGraph "SymSmartGraph" classes are very similar to
 
    39 \ref lemon::SymSmartGraph "SymSmartGraph" classes are very similar to
 
    40 \ref hugo::ListGraph "ListGraph" and \ref hugo::SmartGraph "SmartGraph".
 
    40 \ref lemon::ListGraph "ListGraph" and \ref lemon::SmartGraph "SmartGraph".
 
    41 The difference is that whenever you add a
 
    41 The difference is that whenever you add a
 
    42 new edge to the graph, it actually adds a pair of oppositely directed edges.
 
    42 new edge to the graph, it actually adds a pair of oppositely directed edges.
 
    43 They are linked together so it is possible to access the counterpart of an
 
    43 They are linked together so it is possible to access the counterpart of an
 
    44 edge. An even more important feature is that using these classes you can also
 
    44 edge. An even more important feature is that using these classes you can also
 
    45 attach data to the edges in such a way that the stored data
 
    45 attach data to the edges in such a way that the stored data
 
    46 are shared by the edge pairs. 
    46 are shared by the edge pairs. 
    47 \li \ref hugo::FullGraph "FullGraph"
 
    47 \li \ref lemon::FullGraph "FullGraph"
 
    48 implements a full graph. It is a \ref hugo::skeleton::StaticGraph, so you cannot
 
    48 implements a full graph. It is a \ref lemon::skeleton::StaticGraph, so you cannot
 
    49 change the number of nodes once it is constructed. It is extremely memory
 
    49 change the number of nodes once it is constructed. It is extremely memory
 
    50 efficient: it uses constant amount of memory independently from the number of
 
    50 efficient: it uses constant amount of memory independently from the number of
 
    51 the nodes of the graph. Of course, the size of the \ref maps "NodeMap"'s and
 
    51 the nodes of the graph. Of course, the size of the \ref maps "NodeMap"'s and
 
    52 \ref maps "EdgeMap"'s will depend on the number of nodes.
 
    52 \ref maps "EdgeMap"'s will depend on the number of nodes.
 
    53 
    53 
    54 \li \ref hugo::NodeSet "NodeSet" implements a graph with no edges. This class
 
    54 \li \ref lemon::NodeSet "NodeSet" implements a graph with no edges. This class
 
    55 can be used as a base class of \ref hugo::EdgeSet "EdgeSet".
 
    55 can be used as a base class of \ref lemon::EdgeSet "EdgeSet".
 
    56 \li \ref hugo::EdgeSet "EdgeSet" can be used to create a new graph on
 
    56 \li \ref lemon::EdgeSet "EdgeSet" can be used to create a new graph on
 
    57 the node set of another graph. The base graph can be an arbitrary graph and it
 
    57 the node set of another graph. The base graph can be an arbitrary graph and it
 
    58 is possible to attach several \ref hugo::EdgeSet "EdgeSet"'s to a base graph.
 
    58 is possible to attach several \ref lemon::EdgeSet "EdgeSet"'s to a base graph.
 
    59 
    59 
    60 \todo Don't we need SmartNodeSet and SmartEdgeSet?
 
    60 \todo Don't we need SmartNodeSet and SmartEdgeSet?
 
    61 \todo Some cross-refs are wrong.
 
    61 \todo Some cross-refs are wrong.
 
    62 
    62 
    63 The graph structures itself can not store data attached
 
    63 The graph structures itself can not store data attached
 
    64 to the edges and nodes. However they all provide
 
    64 to the edges and nodes. However they all provide
 
    65 \ref maps "map classes"
 
    65 \ref maps "map classes"
 
    66 to dynamically attach data the to graph components.
 
    66 to dynamically attach data the to graph components.
 
    67 
    67 
    68 The following program demonstrates the basic features of HugoLib's graph
 
    68 The following program demonstrates the basic features of LEMON's graph
 
    69 structures.
 
    69 structures.
 
    70 
    70 
    71 \code
 
    71 \code
 
    72 #include <iostream>
 
    72 #include <iostream>
 
    73 #include <hugo/list_graph.h>
 
    73 #include <lemon/list_graph.h>
 
    74 
    74 
    75 using namespace hugo;
 
    75 using namespace lemon;
 
    76 
    76 
    77 int main()
 
    77 int main()
 
    78 {
 
    78 {
 
    79   typedef ListGraph Graph;
 
    79   typedef ListGraph Graph;
 
    80 \endcode
 
    80 \endcode
 
    81 
    81 
    82 ListGraph is one of HugoLib's graph classes. It is based on linked lists,
 
    82 ListGraph is one of LEMON's graph classes. It is based on linked lists,
 
    83 therefore iterating throuh its edges and nodes is fast.
 
    83 therefore iterating throuh its edges and nodes is fast.
 
    84 
    84 
    85 \code
 
    85 \code
 
    86   typedef Graph::Edge Edge;
 
    86   typedef Graph::Edge Edge;
 
    87   typedef Graph::InEdgeIt InEdgeIt;
 
    87   typedef Graph::InEdgeIt InEdgeIt;
 
   112 
   112 
   113 Here we iterate through all nodes of the graph. We use a constructor of the
 
   113 Here we iterate through all nodes of the graph. We use a constructor of the
 
   114 node iterator to initialize it to the first node. The operator++ is used to
 
   114 node iterator to initialize it to the first node. The operator++ is used to
 
   115 step to the next node. Using operator++ on the iterator pointing to the last
 
   115 step to the next node. Using operator++ on the iterator pointing to the last
 
   116 node invalidates the iterator i.e. sets its value to
 
   116 node invalidates the iterator i.e. sets its value to
 
   117 \ref hugo::INVALID "INVALID". This is what we exploit in the stop condition.
 
   117 \ref lemon::INVALID "INVALID". This is what we exploit in the stop condition.
 
   118 
   118 
   119 The previous code fragment prints out the following:
 
   119 The previous code fragment prints out the following:
 
   120 
   120 
   121 \code
 
   121 \code
 
   122 Nodes: 2 1 0
 
   122 Nodes: 2 1 0
 
   179 3  (1,0) 7
 
   179 3  (1,0) 7
 
   180 1  (2,0) 9
 
   180 1  (2,0) 9
 
   181 \endcode
 
   181 \endcode
 
   182 
   182 
   183 As we mentioned above, graphs are not containers rather
 
   183 As we mentioned above, graphs are not containers rather
 
   184 incidence structures which are iterable in many ways. HugoLib introduces
 
   184 incidence structures which are iterable in many ways. LEMON introduces
 
   185 concepts that allow us to attach containers to graphs. These containers are
 
   185 concepts that allow us to attach containers to graphs. These containers are
 
   186 called maps.
 
   186 called maps.
 
   187 
   187 
   188 In the example above we create an EdgeMap which assigns an int value to all
 
   188 In the example above we create an EdgeMap which assigns an int value to all
 
   189 edges of the graph. We use the set member function of the map to write values
 
   189 edges of the graph. We use the set member function of the map to write values
lemon-0.x