COIN-OR::LEMON - Graph Library

Changeset 455:5a1e9fdcfd3a in lemon-1.2 for doc


Ignore:
Timestamp:
01/11/09 16:09:53 (11 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Children:
456:aff6888e71c9, 463:a2fd8b8d0b30
Parents:
445:75a5df083951 (diff), 454:f599fa651202 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Phase:
public
Message:

Merge

Files:
2 edited

Legend:

Unmodified
Added
Removed
  • doc/groups.dox

    r440 r455  
    6363
    6464/**
    65 @defgroup graph_adaptors Adaptor Classes for graphs
     65@defgroup graph_adaptors Adaptor Classes for Graphs
    6666@ingroup graphs
    67 \brief This group contains several adaptor classes for digraphs and graphs
     67\brief Adaptor classes for digraphs and graphs
     68
     69This group contains several useful adaptor classes for digraphs and graphs.
    6870
    6971The main parts of LEMON are the different graph structures, generic
    70 graph algorithms, graph concepts which couple these, and graph
     72graph algorithms, graph concepts, which couple them, and graph
    7173adaptors. While the previous notions are more or less clear, the
    7274latter one needs further explanation. Graph adaptors are graph classes
     
    7476
    7577A short example makes this much clearer.  Suppose that we have an
    76 instance \c g of a directed graph type say ListDigraph and an algorithm
     78instance \c g of a directed graph type, say ListDigraph and an algorithm
    7779\code
    7880template <typename Digraph>
     
    8284(in time or in memory usage) to copy \c g with the reversed
    8385arcs.  In this case, an adaptor class is used, which (according
    84 to LEMON digraph concepts) works as a digraph.  The adaptor uses the
    85 original digraph structure and digraph operations when methods of the
    86 reversed oriented graph are called.  This means that the adaptor have
    87 minor memory usage, and do not perform sophisticated algorithmic
     86to LEMON \ref concepts::Digraph "digraph concepts") works as a digraph.
     87The adaptor uses the original digraph structure and digraph operations when
     88methods of the reversed oriented graph are called.  This means that the adaptor
     89have minor memory usage, and do not perform sophisticated algorithmic
    8890actions.  The purpose of it is to give a tool for the cases when a
    8991graph have to be used in a specific alteration.  If this alteration is
    90 obtained by a usual construction like filtering the arc-set or
     92obtained by a usual construction like filtering the node or the arc set or
    9193considering a new orientation, then an adaptor is worthwhile to use.
    9294To come back to the reverse oriented graph, in this situation
     
    9799\code
    98100ListDigraph g;
    99 ReverseDigraph<ListGraph> rg(g);
     101ReverseDigraph<ListDigraph> rg(g);
    100102int result = algorithm(rg);
    101103\endcode
    102 After running the algorithm, the original graph \c g is untouched.
    103 This techniques gives rise to an elegant code, and based on stable
     104During running the algorithm, the original digraph \c g is untouched.
     105This techniques give rise to an elegant code, and based on stable
    104106graph adaptors, complex algorithms can be implemented easily.
    105107
    106 In flow, circulation and bipartite matching problems, the residual
     108In flow, circulation and matching problems, the residual
    107109graph is of particular importance. Combining an adaptor implementing
    108 this, shortest path algorithms and minimum mean cycle algorithms,
     110this with shortest path algorithms or minimum mean cycle algorithms,
    109111a range of weighted and cardinality optimization algorithms can be
    110112obtained. For other examples, the interested user is referred to the
     
    113115The behavior of graph adaptors can be very different. Some of them keep
    114116capabilities of the original graph while in other cases this would be
    115 meaningless. This means that the concepts that they are models of depend
    116 on the graph adaptor, and the wrapped graph(s).
    117 If an arc of \c rg is deleted, this is carried out by deleting the
    118 corresponding arc of \c g, thus the adaptor modifies the original graph.
    119 
    120 But for a residual graph, this operation has no sense.
     117meaningless. This means that the concepts that they meet depend
     118on the graph adaptor, and the wrapped graph.
     119For example, if an arc of a reversed digraph is deleted, this is carried
     120out by deleting the corresponding arc of the original digraph, thus the
     121adaptor modifies the original digraph.
     122However in case of a residual digraph, this operation has no sense.
     123
    121124Let us stand one more example here to simplify your work.
    122 RevGraphAdaptor has constructor
     125ReverseDigraph has constructor
    123126\code
    124127ReverseDigraph(Digraph& digraph);
    125128\endcode
    126 This means that in a situation, when a <tt>const ListDigraph&</tt>
     129This means that in a situation, when a <tt>const %ListDigraph&</tt>
    127130reference to a graph is given, then it have to be instantiated with
    128 <tt>Digraph=const ListDigraph</tt>.
     131<tt>Digraph=const %ListDigraph</tt>.
    129132\code
    130133int algorithm1(const ListDigraph& g) {
    131   RevGraphAdaptor<const ListDigraph> rg(g);
     134  ReverseDigraph<const ListDigraph> rg(g);
    132135  return algorithm2(rg);
    133136}
  • doc/groups.dox

    r451 r455  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
Note: See TracChangeset for help on using the changeset viewer.