1.1 --- a/doc/graphs.dox Wed Sep 29 14:12:26 2004 +0000
1.2 +++ b/doc/graphs.dox Wed Sep 29 15:30:04 2004 +0000
1.3 @@ -2,60 +2,60 @@
1.4
1.5 \page graphs How to use graphs
1.6
1.7 -The primary data structures of HugoLib are the graph classes. They all
1.8 +The primary data structures of LEMON are the graph classes. They all
1.9 provide a node list - edge list interface, i.e. they have
1.10 functionalities to list the nodes and the edges of the graph as well
1.11 as in incoming and outgoing edges of a given node.
1.12
1.13
1.14 Each graph should meet the
1.15 -\ref hugo::skeleton::StaticGraph "StaticGraph" concept.
1.16 +\ref lemon::skeleton::StaticGraph "StaticGraph" concept.
1.17 This concept does not
1.18 makes it possible to change the graph (i.e. it is not possible to add
1.19 or delete edges or nodes). Most of the graph algorithms will run on
1.20 these graphs.
1.21
1.22 The graphs meeting the
1.23 -\ref hugo::skeleton::ExtendableGraph "ExtendableGraph"
1.24 +\ref lemon::skeleton::ExtendableGraph "ExtendableGraph"
1.25 concept allow node and
1.26 edge addition. You can also "clear" (i.e. erase all edges and nodes)
1.27 such a graph.
1.28
1.29 In case of graphs meeting the full feature
1.30 -\ref hugo::skeleton::ErasableGraph "ErasableGraph"
1.31 +\ref lemon::skeleton::ErasableGraph "ErasableGraph"
1.32 concept
1.33 you can also erase individual edges and node in arbitrary order.
1.34
1.35 The implemented graph structures are the following.
1.36 -\li \ref hugo::ListGraph "ListGraph" is the most versatile graph class. It meets
1.37 -the \ref hugo::skeleton::ErasableGraph "ErasableGraph" concept
1.38 +\li \ref lemon::ListGraph "ListGraph" is the most versatile graph class. It meets
1.39 +the \ref lemon::skeleton::ErasableGraph "ErasableGraph" concept
1.40 and it also have some convenience features.
1.41 -\li \ref hugo::SmartGraph "SmartGraph" is a more memory
1.42 -efficient version of \ref hugo::ListGraph "ListGraph". The
1.43 +\li \ref lemon::SmartGraph "SmartGraph" is a more memory
1.44 +efficient version of \ref lemon::ListGraph "ListGraph". The
1.45 price of it is that it only meets the
1.46 -\ref hugo::skeleton::ExtendableGraph "ExtendableGraph" concept,
1.47 +\ref lemon::skeleton::ExtendableGraph "ExtendableGraph" concept,
1.48 so you cannot delete individual edges or nodes.
1.49 -\li \ref hugo::SymListGraph "SymListGraph" and
1.50 -\ref hugo::SymSmartGraph "SymSmartGraph" classes are very similar to
1.51 -\ref hugo::ListGraph "ListGraph" and \ref hugo::SmartGraph "SmartGraph".
1.52 +\li \ref lemon::SymListGraph "SymListGraph" and
1.53 +\ref lemon::SymSmartGraph "SymSmartGraph" classes are very similar to
1.54 +\ref lemon::ListGraph "ListGraph" and \ref lemon::SmartGraph "SmartGraph".
1.55 The difference is that whenever you add a
1.56 new edge to the graph, it actually adds a pair of oppositely directed edges.
1.57 They are linked together so it is possible to access the counterpart of an
1.58 edge. An even more important feature is that using these classes you can also
1.59 attach data to the edges in such a way that the stored data
1.60 are shared by the edge pairs.
1.61 -\li \ref hugo::FullGraph "FullGraph"
1.62 -implements a full graph. It is a \ref hugo::skeleton::StaticGraph, so you cannot
1.63 +\li \ref lemon::FullGraph "FullGraph"
1.64 +implements a full graph. It is a \ref lemon::skeleton::StaticGraph, so you cannot
1.65 change the number of nodes once it is constructed. It is extremely memory
1.66 efficient: it uses constant amount of memory independently from the number of
1.67 the nodes of the graph. Of course, the size of the \ref maps "NodeMap"'s and
1.68 \ref maps "EdgeMap"'s will depend on the number of nodes.
1.69
1.70 -\li \ref hugo::NodeSet "NodeSet" implements a graph with no edges. This class
1.71 -can be used as a base class of \ref hugo::EdgeSet "EdgeSet".
1.72 -\li \ref hugo::EdgeSet "EdgeSet" can be used to create a new graph on
1.73 +\li \ref lemon::NodeSet "NodeSet" implements a graph with no edges. This class
1.74 +can be used as a base class of \ref lemon::EdgeSet "EdgeSet".
1.75 +\li \ref lemon::EdgeSet "EdgeSet" can be used to create a new graph on
1.76 the node set of another graph. The base graph can be an arbitrary graph and it
1.77 -is possible to attach several \ref hugo::EdgeSet "EdgeSet"'s to a base graph.
1.78 +is possible to attach several \ref lemon::EdgeSet "EdgeSet"'s to a base graph.
1.79
1.80 \todo Don't we need SmartNodeSet and SmartEdgeSet?
1.81 \todo Some cross-refs are wrong.
1.82 @@ -65,21 +65,21 @@
1.83 \ref maps "map classes"
1.84 to dynamically attach data the to graph components.
1.85
1.86 -The following program demonstrates the basic features of HugoLib's graph
1.87 +The following program demonstrates the basic features of LEMON's graph
1.88 structures.
1.89
1.90 \code
1.91 #include <iostream>
1.92 -#include <hugo/list_graph.h>
1.93 +#include <lemon/list_graph.h>
1.94
1.95 -using namespace hugo;
1.96 +using namespace lemon;
1.97
1.98 int main()
1.99 {
1.100 typedef ListGraph Graph;
1.101 \endcode
1.102
1.103 -ListGraph is one of HugoLib's graph classes. It is based on linked lists,
1.104 +ListGraph is one of LEMON's graph classes. It is based on linked lists,
1.105 therefore iterating throuh its edges and nodes is fast.
1.106
1.107 \code
1.108 @@ -114,7 +114,7 @@
1.109 node iterator to initialize it to the first node. The operator++ is used to
1.110 step to the next node. Using operator++ on the iterator pointing to the last
1.111 node invalidates the iterator i.e. sets its value to
1.112 -\ref hugo::INVALID "INVALID". This is what we exploit in the stop condition.
1.113 +\ref lemon::INVALID "INVALID". This is what we exploit in the stop condition.
1.114
1.115 The previous code fragment prints out the following:
1.116
1.117 @@ -181,7 +181,7 @@
1.118 \endcode
1.119
1.120 As we mentioned above, graphs are not containers rather
1.121 -incidence structures which are iterable in many ways. HugoLib introduces
1.122 +incidence structures which are iterable in many ways. LEMON introduces
1.123 concepts that allow us to attach containers to graphs. These containers are
1.124 called maps.
1.125