COIN-OR::LEMON - Graph Library

Changeset 921:818510fa3d99 in lemon-0.x for doc/graphs.dox


Ignore:
Timestamp:
09/29/04 17:30:04 (15 years ago)
Author:
Alpar Juttner
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1232
Message:

hugo -> lemon

File:
1 edited

Legend:

Unmodified
Added
Removed
  • doc/graphs.dox

    r911 r921  
    33\page graphs How to use graphs
    44
    5 The primary data structures of HugoLib are the graph classes. They all
     5The primary data structures of LEMON are the graph classes. They all
    66provide a node list - edge list interface, i.e. they have
    77functionalities to list the nodes and the edges of the graph as well
     
    1010
    1111Each graph should meet the
    12 \ref hugo::skeleton::StaticGraph "StaticGraph" concept.
     12\ref lemon::skeleton::StaticGraph "StaticGraph" concept.
    1313This concept does not
    1414makes it possible to change the graph (i.e. it is not possible to add
     
    1717
    1818The graphs meeting the
    19 \ref hugo::skeleton::ExtendableGraph "ExtendableGraph"
     19\ref lemon::skeleton::ExtendableGraph "ExtendableGraph"
    2020concept allow node and
    2121edge addition. You can also "clear" (i.e. erase all edges and nodes)
     
    2323
    2424In case of graphs meeting the full feature
    25 \ref hugo::skeleton::ErasableGraph "ErasableGraph"
     25\ref lemon::skeleton::ErasableGraph "ErasableGraph"
    2626concept
    2727you can also erase individual edges and node in arbitrary order.
    2828
    2929The implemented graph structures are the following.
    30 \li \ref hugo::ListGraph "ListGraph" is the most versatile graph class. It meets
    31 the \ref hugo::skeleton::ErasableGraph "ErasableGraph" concept
     30\li \ref lemon::ListGraph "ListGraph" is the most versatile graph class. It meets
     31the \ref lemon::skeleton::ErasableGraph "ErasableGraph" concept
    3232and it also have some convenience features.
    33 \li \ref hugo::SmartGraph "SmartGraph" is a more memory
    34 efficient version of \ref hugo::ListGraph "ListGraph". The
     33\li \ref lemon::SmartGraph "SmartGraph" is a more memory
     34efficient version of \ref lemon::ListGraph "ListGraph". The
    3535price of it is that it only meets the
    36 \ref hugo::skeleton::ExtendableGraph "ExtendableGraph" concept,
     36\ref lemon::skeleton::ExtendableGraph "ExtendableGraph" concept,
    3737so you cannot delete individual edges or nodes.
    38 \li \ref hugo::SymListGraph "SymListGraph" and
    39 \ref hugo::SymSmartGraph "SymSmartGraph" classes are very similar to
    40 \ref hugo::ListGraph "ListGraph" and \ref hugo::SmartGraph "SmartGraph".
     38\li \ref lemon::SymListGraph "SymListGraph" and
     39\ref lemon::SymSmartGraph "SymSmartGraph" classes are very similar to
     40\ref lemon::ListGraph "ListGraph" and \ref lemon::SmartGraph "SmartGraph".
    4141The difference is that whenever you add a
    4242new edge to the graph, it actually adds a pair of oppositely directed edges.
     
    4545attach data to the edges in such a way that the stored data
    4646are shared by the edge pairs.
    47 \li \ref hugo::FullGraph "FullGraph"
    48 implements a full graph. It is a \ref hugo::skeleton::StaticGraph, so you cannot
     47\li \ref lemon::FullGraph "FullGraph"
     48implements a full graph. It is a \ref lemon::skeleton::StaticGraph, so you cannot
    4949change the number of nodes once it is constructed. It is extremely memory
    5050efficient: it uses constant amount of memory independently from the number of
     
    5252\ref maps "EdgeMap"'s will depend on the number of nodes.
    5353
    54 \li \ref hugo::NodeSet "NodeSet" implements a graph with no edges. This class
    55 can be used as a base class of \ref hugo::EdgeSet "EdgeSet".
    56 \li \ref hugo::EdgeSet "EdgeSet" can be used to create a new graph on
     54\li \ref lemon::NodeSet "NodeSet" implements a graph with no edges. This class
     55can be used as a base class of \ref lemon::EdgeSet "EdgeSet".
     56\li \ref lemon::EdgeSet "EdgeSet" can be used to create a new graph on
    5757the 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.
     58is possible to attach several \ref lemon::EdgeSet "EdgeSet"'s to a base graph.
    5959
    6060\todo Don't we need SmartNodeSet and SmartEdgeSet?
     
    6666to dynamically attach data the to graph components.
    6767
    68 The following program demonstrates the basic features of HugoLib's graph
     68The following program demonstrates the basic features of LEMON's graph
    6969structures.
    7070
    7171\code
    7272#include <iostream>
    73 #include <hugo/list_graph.h>
     73#include <lemon/list_graph.h>
    7474
    75 using namespace hugo;
     75using namespace lemon;
    7676
    7777int main()
     
    8080\endcode
    8181
    82 ListGraph is one of HugoLib's graph classes. It is based on linked lists,
     82ListGraph is one of LEMON's graph classes. It is based on linked lists,
    8383therefore iterating throuh its edges and nodes is fast.
    8484
     
    115115step to the next node. Using operator++ on the iterator pointing to the last
    116116node 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.
    118118
    119119The previous code fragment prints out the following:
     
    182182
    183183As we mentioned above, graphs are not containers rather
    184 incidence structures which are iterable in many ways. HugoLib introduces
     184incidence structures which are iterable in many ways. LEMON introduces
    185185concepts that allow us to attach containers to graphs. These containers are
    186186called maps.
Note: See TracChangeset for help on using the changeset viewer.