1.1 --- a/doc/graphs.dox	Wed Aug 04 19:04:42 2004 +0000
     1.2 +++ b/doc/graphs.dox	Thu Aug 05 07:57:20 2004 +0000
     1.3 @@ -2,6 +2,65 @@
     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 +provide a node list - edge list interface, i.e. they have
     1.9 +functionalities to list the nodes and the edges of the graph as well
    1.10 +as in incoming and outgoing edges of a given node. 
    1.11 +
    1.12 +
    1.13 +Each graph should meet the \ref ConstGraph concept. This concept does
    1.14 +makes it possible to change the graph (i.e. it is not possible to add
    1.15 +or delete edges or nodes). Most of the graph algorithms will run on
    1.16 +these graphs.
    1.17 +
    1.18 +The graphs meeting the \ref ExtendableGraph concept allow node and
    1.19 +edge addition. You can also "clear" (i.e. erase all edges and nodes)
    1.20 +such a graph.
    1.21 +
    1.22 +In case of graphs meeting the full feature \ref ErasableGraph concept
    1.23 +you can also erase individual edges and node in arbitrary order.
    1.24 +
    1.25 +The implemented graph structures are the following.
    1.26 +\li \ref hugo::ListGraph "ListGraph" is the most versatile graph class. It meets
    1.27 +the ErasableGraph concept and it also have some convenience features.
    1.28 +\li \ref hugo::SmartGraph "SmartGraph" is a more memory
    1.29 +efficient version of \ref hugo::ListGraph "ListGraph". The
    1.30 +price of it is that it only meets the \ref ExtendableGraph concept,
    1.31 +so you cannot delete individual edges or nodes.
    1.32 +\li \ref hugo::SymListGraph "SymListGraph" and
    1.33 +\ref hugo::SymSmartGraph "SymSmartGraph" classes are very similar to
    1.34 +\ref hugo::ListGraph "ListGraph" and \ref hugo::SmartGraph "SmartGraph".
    1.35 +The difference is that whenever you add a
    1.36 +new edge to the graph, it actually adds a pair of oppositely directed edges.
    1.37 +They are linked together so it is possible to access the counterpart of an
    1.38 +edge. An even more important feature is that using these classes you can also
    1.39 +attach data to the edges in such a way that the stored data
    1.40 +are shared by the edge pairs. 
    1.41 +\li \ref hugo::FullGraph "FullGraph"
    1.42 +implements a full graph. It is a \ref ConstGraph, so you cannot
    1.43 +change the number of nodes once it is constructed. It is extremely memory
    1.44 +efficient: it uses constant amount of memory independently from the number of
    1.45 +the nodes of the graph. Of course, the size of the \ref maps "NodeMap"'s and
    1.46 +\ref maps "EdgeMap"'s will depend on the number of nodes.
    1.47 +
    1.48 +\li \ref hugo::NodeSet "NodeSet" implements a graph with no edges. This class
    1.49 +can be used as a base class of \ref hugo::EdgeSet "EdgeSet".
    1.50 +\li \ref hugo::EdgeSet "EdgeSet" can be used to create a new graph on
    1.51 +the edge set of another graph. The base graph can be an arbitrary graph and it
    1.52 +is possible to attach several \ref hugo::EdgeSet "EdgeSet"'s to a base graph.
    1.53 +
    1.54 +\todo Don't we need SmartNodeSet and SmartEdgeSet?
    1.55 +\todo Some cross-refs are wrong.
    1.56 +
    1.57 +
    1.58 +The graph structures itself can not store data attached
    1.59 +to the edges and nodes. However they all provide
    1.60 +\ref maps "map classes"
    1.61 +to dynamically attach data the to graph components.
    1.62 +
    1.63 +
    1.64 +
    1.65 +
    1.66  The following program demonstrates the basic features of HugoLib's graph
    1.67  structures.
    1.68