COIN-OR::LEMON - Graph Library

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


Ignore:
Timestamp:
08/05/04 09:57:20 (15 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:
1 edited

Legend:

Unmodified
Added
Removed
  • doc/graphs.dox

    r666 r756  
    22
    33\page graphs How to use graphs
     4
     5The primary data structures of HugoLib are the graph classes. They all
     6provide a node list - edge list interface, i.e. they have
     7functionalities to list the nodes and the edges of the graph as well
     8as in incoming and outgoing edges of a given node.
     9
     10
     11Each graph should meet the \ref ConstGraph concept. This concept does
     12makes it possible to change the graph (i.e. it is not possible to add
     13or delete edges or nodes). Most of the graph algorithms will run on
     14these graphs.
     15
     16The graphs meeting the \ref ExtendableGraph concept allow node and
     17edge addition. You can also "clear" (i.e. erase all edges and nodes)
     18such a graph.
     19
     20In case of graphs meeting the full feature \ref ErasableGraph concept
     21you can also erase individual edges and node in arbitrary order.
     22
     23The implemented graph structures are the following.
     24\li \ref hugo::ListGraph "ListGraph" is the most versatile graph class. It meets
     25the ErasableGraph concept and it also have some convenience features.
     26\li \ref hugo::SmartGraph "SmartGraph" is a more memory
     27efficient version of \ref hugo::ListGraph "ListGraph". The
     28price of it is that it only meets the \ref ExtendableGraph concept,
     29so you cannot delete individual edges or nodes.
     30\li \ref hugo::SymListGraph "SymListGraph" and
     31\ref hugo::SymSmartGraph "SymSmartGraph" classes are very similar to
     32\ref hugo::ListGraph "ListGraph" and \ref hugo::SmartGraph "SmartGraph".
     33The difference is that whenever you add a
     34new edge to the graph, it actually adds a pair of oppositely directed edges.
     35They are linked together so it is possible to access the counterpart of an
     36edge. An even more important feature is that using these classes you can also
     37attach data to the edges in such a way that the stored data
     38are shared by the edge pairs.
     39\li \ref hugo::FullGraph "FullGraph"
     40implements a full graph. It is a \ref ConstGraph, so you cannot
     41change the number of nodes once it is constructed. It is extremely memory
     42efficient: it uses constant amount of memory independently from the number of
     43the nodes of the graph. Of course, the size of the \ref maps "NodeMap"'s and
     44\ref maps "EdgeMap"'s will depend on the number of nodes.
     45
     46\li \ref hugo::NodeSet "NodeSet" implements a graph with no edges. This class
     47can be used as a base class of \ref hugo::EdgeSet "EdgeSet".
     48\li \ref hugo::EdgeSet "EdgeSet" can be used to create a new graph on
     49the edge set of another graph. The base graph can be an arbitrary graph and it
     50is possible to attach several \ref hugo::EdgeSet "EdgeSet"'s to a base graph.
     51
     52\todo Don't we need SmartNodeSet and SmartEdgeSet?
     53\todo Some cross-refs are wrong.
     54
     55
     56The graph structures itself can not store data attached
     57to the edges and nodes. However they all provide
     58\ref maps "map classes"
     59to dynamically attach data the to graph components.
     60
     61
     62
    463
    564The following program demonstrates the basic features of HugoLib's graph
Note: See TracChangeset for help on using the changeset viewer.