doc/basic_concepts.dox
author kpeter
Tue, 05 Feb 2008 12:45:23 +0000
changeset 2565 4f411276c767
parent 2476 059dcdda37c5
permissions -rw-r--r--
Bug fix in heap_test.cc.
     1 /* -*- C++ -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library
     4  *
     5  * Copyright (C) 2003-2008
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 namespace lemon {
    20 
    21 /**
    22 \page basic_concepts Basic concepts
    23 
    24 \section basic_graph The graph classes
    25 The most important classes in LEMON are the graph classes. An instance of a graph
    26 class is the representation of the mathematical graph. It holds the topology and
    27 every structural information of the graph. The structural manipulations are also
    28 provided by the graph object. There is no universal graph class instead we have
    29 different classes for different purposes. They can differ in many ways, but all
    30 have to satisfy one or more \ref concept "graph concepts" which are standardized
    31 interfaces to work with the rest of the library. The most basic concept is the
    32 \ref concepts::Graph "Graph".<br>
    33 A good example is the \ref ListGraph which we already know from Hello World and
    34 will be used in our examples as well.
    35 
    36 One main advantage of the templates are, that you can write your own graph classes.
    37 As long as they provide the interface a concept is defining all the LEMON algorithms
    38 and classes will work with it properly - no representation or implementation is
    39 written into stone.
    40 
    41 
    42 \subsection basic_node Nodes
    43 To refer to a node of a graph we need some kind of typed variable. Graph classes
    44 have the Node public type for this purpose. Stacking by the last example:
    45 \code lemon::ListGraph::Node \endcode
    46 
    47 If the graph fits the ExtendableGraphComponent concept, then you can add new nodes
    48 to the graph with the addNode() member function. It returns the newly added node
    49 (as value). So if you need the new node to do something useful with, for example
    50 create an edge, assign a value to it through \ref maps1 maps.
    51 \code lemon::ListGraph::Node  new_node = graph.addNode(); \endcode
    52 
    53 If the graph fits into the ErasableGraphComponent concept you can also remove nodes
    54 from the graph with the erase() member function.
    55 \code graph.erase( new_node ); \endcode
    56 
    57 You don't have to store every node in a variable, you can access individual nodes
    58 with node iterators discussed in the next section. But how do you know which
    59 node is which?<br>
    60 The graph class has the id( Node n ) member function providing an unique identifier
    61 assigned to every node.
    62 
    63 
    64 \subsection basic_edge Edges
    65 An Edge is what you think it is. It goes from one node to another node (they can
    66 be identical if the edge is a loop). If the graph class is directed, the Edge is directed too. Otherwise
    67 the edge is considered undirected and called UEdge.
    68 \code lemon::ListUGraph::UEdge \endcode
    69 
    70 The addEdge() member function will create a new edge. It has two arguments, the
    71 source node and the target node. The graph class must be extendable.
    72 \code lemon::ListGraph::Edge  new_edge = graph.addEdge( src_node, trg_node ); \endcode
    73 You can handle edges similar as nodes. The erase() member function has an edge taking
    74 overload too.
    75 
    76 You can ask for the source or target node of the edge by the corresponding member
    77 functions:
    78 \code
    79 graph.source( new_edge );
    80 lemon::ListGraph::Node  n = graph.target( new_edge ); \endcode
    81 These functions are always legal even if the graph is undirected. UEdge has a
    82 default direction.
    83 
    84 
    85 \section basic_iterators Iterators
    86 Graphs are some kind of containers. And as you expect they have iterator types.
    87 One for nodes and a couple for edges - and special classes can have additional
    88 iterators too. An example:
    89 \code lemon::ListGraph::NodeIt \endcode
    90 This is a node iterator. Every iterator type starts with a name that refers to
    91 the iterated object, and ends with 'It'.
    92 
    93 LEMON style iterators differ from \c stl or \c boost iterators in a very tasty
    94 way. A graph has no begin or end - or at least a generic graph class has none.
    95 If by some topology you could pick a good begin node, it would be misleading and
    96 incorrect. A LEMON style iterator must be initialized at construction time.
    97 The constructor takes the needed parameters - by a node iterator it's the graph
    98 object. And will be compared to the lemon::INVALID to check if it's still valid.
    99 Every iterator can be compared to INVALID. No \c begin() or \c end() needed.<br>
   100 Let's see these things working together:
   101 \code
   102 for( ListGraph::NodeIt n(graph); n != INVALID; ++n )
   103     do_useful_things_with_node(n);
   104 \endcode
   105 Note that the function \c do_useful_things_with_node() expects a Node type argument
   106 ad we just gave him the iterator. LEMON style iterators must provide "on demand
   107 dereferencing". For example a NodeIt can be used everywhere a Node could. (In some
   108 graph classes Node is the base class of NodeIt. But in other cases this is implemented
   109 through typecast operator.)
   110 
   111 <b>Very important!</b> The iteration has no defined order. There is absolutely no
   112 warranty that the next time the iteration will give us the nodes in the same order.
   113 Don't use this order to identify nodes! Use the \c id() member function of the
   114 graph class described above. (There is a powerful technique using maps right in
   115 the next page.)
   116 
   117 The \ref concepts::Graph::EdgeIt "EdgeIt" works exactly the same - nothing more to say.
   118 But there are \ref concepts::Graph::InEdgeIt "InEdgeIt" and
   119 \ref concepts::Graph::OutEdgeIt "OutEdgeIt" by directed graphs and
   120 \ref concepts::UGraph::IncEdgeIt "IncEdgeIt" by undirected graphs.
   121 They take two arguments. The first is a graph, the second is certain node of the
   122 graph. InEdgeIt iterates on the incoming edges of that node and OutEdgeIt does it
   123 on the outgoing edges. The IncEdgeIt of course iterates every edge connecting to
   124 the given node.
   125 
   126 \code
   127 for( ListGraph::NodeIt n(graph); n != INVALID; ++n ) {
   128   int in = 0, out = 0;
   129   for( ListGraph::InEdgeIt e(graph,n); e != INVALID; ++e ) ++in;
   130   for( ListGraph::OutEdgeIt e(graph,n); e != INVALID; ++e ) ++out;
   131 
   132   std::cout << "#" << graph.id(n) << " node has " << in << " incoming and "
   133     << out << "outgoing edges." << std::endl;
   134 }
   135 \endcode
   136 
   137 
   138 \section basic_ListGraph ListGraph - a versatile directed graph
   139 As you see ListGraph satisfies most of the basic concepts and ideal for general
   140 graph representations. It has an undirected version too: ListUGraph.
   141 */
   142 
   143 }