Changeset 756:c54cf1e83039 in lemon-0.x for doc/graphs.dox

Timestamp:

08/05/04 09:57:20 (20 years ago)

Author:

Alpar Juttner

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1016

Message:

• A summary of the implemented graph structures.
• Some words on the different (and still nonexisting) graph concepts.

File:

• doc/graphs.dox (modified) (1 diff)

doc/graphs.dox

@@ -2 +2 @@
 
 \page graphs How to use graphs
+
+The primary data structures of HugoLib are the graph classes. They all
+provide a node list - edge list interface, i.e. they have
+functionalities to list the nodes and the edges of the graph as well
+as in incoming and outgoing edges of a given node. 
+
+
+Each graph should meet the \ref ConstGraph concept. This concept does
+makes it possible to change the graph (i.e. it is not possible to add
+or delete edges or nodes). Most of the graph algorithms will run on
+these graphs.
+
+The graphs meeting the \ref ExtendableGraph concept allow node and
+edge addition. You can also "clear" (i.e. erase all edges and nodes)
+such a graph.
+
+In case of graphs meeting the full feature \ref ErasableGraph concept
+you can also erase individual edges and node in arbitrary order.
+
+The implemented graph structures are the following.
+\li \ref hugo::ListGraph "ListGraph" is the most versatile graph class. It meets
+the ErasableGraph concept and it also have some convenience features.
+\li \ref hugo::SmartGraph "SmartGraph" is a more memory
+efficient version of \ref hugo::ListGraph "ListGraph". The
+price of it is that it only meets the \ref ExtendableGraph concept,
+so you cannot delete individual edges or nodes.
+\li \ref hugo::SymListGraph "SymListGraph" and
+\ref hugo::SymSmartGraph "SymSmartGraph" classes are very similar to
+\ref hugo::ListGraph "ListGraph" and \ref hugo::SmartGraph "SmartGraph".
+The difference is that whenever you add a
+new edge to the graph, it actually adds a pair of oppositely directed edges.
+They are linked together so it is possible to access the counterpart of an
+edge. An even more important feature is that using these classes you can also
+attach data to the edges in such a way that the stored data
+are shared by the edge pairs. 
+\li \ref hugo::FullGraph "FullGraph"
+implements a full graph. It is a \ref ConstGraph, so you cannot
+change the number of nodes once it is constructed. It is extremely memory
+efficient: it uses constant amount of memory independently from the number of
+the nodes of the graph. Of course, the size of the \ref maps "NodeMap"'s and
+\ref maps "EdgeMap"'s will depend on the number of nodes.
+
+\li \ref hugo::NodeSet "NodeSet" implements a graph with no edges. This class
+can be used as a base class of \ref hugo::EdgeSet "EdgeSet".
+\li \ref hugo::EdgeSet "EdgeSet" can be used to create a new graph on
+the edge set of another graph. The base graph can be an arbitrary graph and it
+is possible to attach several \ref hugo::EdgeSet "EdgeSet"'s to a base graph.
+
+\todo Don't we need SmartNodeSet and SmartEdgeSet?
+\todo Some cross-refs are wrong.
+
+
+The graph structures itself can not store data attached
+to the edges and nodes. However they all provide
+\ref maps "map classes"
+to dynamically attach data the to graph components.
+
+
+
 
 The following program demonstrates the basic features of HugoLib's graph