COIN-OR::LEMON - Graph Library

Changeset 2042:bdc953f2a449 in lemon-0.x


Ignore:
Timestamp:
04/07/06 11:54:35 (14 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2681
Message:

New Algorithm group for matchings

LaTeX formulas
Bug fix => /\f$ will cause parsing error in doxygen

Files:
14 edited

Legend:

Unmodified
Added
Removed
  • demo/tight_edge_filter_map.h

    r1956 r2042  
    3333    edge-distance.
    3434   
    35     Let \f$G=(V,A)\f$ be a directed graph (graph for short) and
    36     let \f$\mathbb{F}\f$ be a number type.
     35    Let \f$ G=(V,A) \f$ be a directed graph (graph for short) and
     36    let \f$ \mathbb{F} \f$ be a number type.
    3737    Given a distance function
    38     \f$d:E\to\mathbb{F}\f$,
    39     \f$\pi:V\to\mathbb{F}\f$ is said to be a potetial
    40     w.r.t. \f$d\f$
     38    \f$ d:E\to\mathbb{F} \f$,
     39    \f$ \pi:V\to\mathbb{F} \f$ is said to be a potetial
     40    w.r.t. \f$ d \f$
    4141    if and only if
    42     \f$\pi(v)\le d(uv)+\pi(u)\f$ holds for each edge \f$uv\in E\f$
     42    \f$ \pi(v)\le d(uv)+\pi(u) \f$ holds for each edge \f$ uv\in E \f$
    4343    (or the reverse inequality holds for each edge).
    4444    An edge is said to be tight if this inequality holds with equality,
  • doc/groups.dox

    r2016 r2042  
    142142
    143143/**
     144@defgroup matching Matching algorithms in graphs and bipartite graphs
     145@ingroup galgs
     146\brief This group describes the algorithms
     147for find matchings in graphs and bipartite graphs.
     148*/
     149
     150/**
    144151@defgroup exceptions Exceptions
    145152This group contains the exceptions thrown by LEMON library
  • lemon/bellman_ford.h

    r2010 r2042  
    156156  /// should be used rather.
    157157  ///
    158   /// The complexity of the algorithm is O(n * e).
     158  /// The maximal time complexity of the algorithm is \f$ O(ne) \f$.
    159159  ///
    160160  /// The type of the length is determined by the
  • lemon/bucket_heap.h

    r2038 r2042  
    3838  /// priorities in such a way that finding the item with minimum priority is
    3939  /// efficient. The bucket heap is very simple implementation, it can store
    40   /// only integer priorities and it stores for each priority in the [0..C]
    41   /// range a list of items. So it should be used only when the priorities
    42   /// are small. It is not intended to use as dijkstra heap.
     40  /// only integer priorities and it stores for each priority in the
     41  /// \f$ [0..C) \f$ range a list of items. So it should be used only when
     42  /// the priorities are small. It is not intended to use as dijkstra heap.
    4343  ///
    4444  /// \param _Item Type of the items to be stored. 
  • lemon/floyd_warshall.h

    r1993 r2042  
    160160  /// there are negative circles then the johnson algorithm.
    161161  ///
    162   /// The complexity of this algorithm is O(n^3 + e).
     162  /// The complexity of this algorithm is \f$ O(n^3+e) \f$.
    163163  ///
    164164  /// The type of the length is determined by the
  • lemon/fredman_tarjan.h

    r1993 r2042  
    4545  ///Default traits class of FredmanTarjan class.
    4646  ///\param GR Graph type.
    47   ///\param LM Type of cost map.
    48   template<class GR, class LM>
     47  ///\param CM Type of cost map.
     48  template<class GR, class CM>
    4949  struct FredmanTarjanDefaultTraits{
    5050    ///The graph type the algorithm runs on.
     
    5454    ///The type of the map that stores the edge costs.
    5555    ///It must meet the \ref concept::ReadMap "ReadMap" concept.
    56     typedef LM CostMap;
     56    typedef CM CostMap;
    5757    //The type of the cost of the edges.
    58     typedef typename LM::Value Value;
     58    typedef typename CM::Value Value;
    5959    ///The type of the map that stores whether an edge is in the
    6060    ///spanning tree or not.
     
    7777  ///%FredmanTarjan algorithm class to find a minimum spanning tree.
    7878 
    79   /// \ingroup spantree
    80   ///This class provides an efficient implementation of %FredmanTarjan algorithm
    81   ///whitch is sometimes a bit quicker than the Prim algorithm on larger graphs.
    82   ///Due to the structure of the algorithm, it has less controll functions than
    83   ///Prim.
    84   ///
    85   ///The running time is O(e*B(e,n)) where e is the number of edges, n is the
    86   ///number of nodes in the graph and B(e,n) is min { i | log^(i) n <= e/n}
    87   ///( log^(i+1) n = log(log^(i)) n )
    88   ///
    89   ///The edge costs are passed to the algorithm using a
    90   ///\ref concept::ReadMap "ReadMap",
    91   ///so it is easy to change it to any kind of cost.
    92   ///
    93   ///The type of the cost is determined by the
    94   ///\ref concept::ReadMap::Value "Value" of the cost map.
     79  /// \ingroup spantree
     80  ///
     81  ///This class provides an efficient implementation of %FredmanTarjan
     82  ///algorithm whitch is sometimes a bit quicker than the Prim
     83  ///algorithm on larger graphs.  Due to the structure of the
     84  ///algorithm, it has less controll functions than Prim.
     85  ///
     86  /// The running time is \f$ O(e\beta(e,n)) \f$ where
     87  /// \f$ \beta(e,n) = \min\{ i | \log^{i}(n) \le e/n\} \f$ and
     88  /// \f$ \log^{i+1}(n)=\log(\log^{i}(n)) \f$
     89  ///
     90  ///The edge costs are passed to the algorithm using a \ref
     91  ///concept::ReadMap "ReadMap", so it is easy to change it to any
     92  ///kind of cost.
     93  ///
     94  ///The type of the cost is determined by the \ref
     95  ///concept::ReadMap::Value "Value" of the cost map.
    9596  ///
    9697  ///\param GR The graph type the algorithm runs on. The default value
    9798  ///is \ref ListUGraph. The value of GR is not used directly by
    98   ///FredmanTarjan, it is only passed to \ref FredmanTarjanDefaultTraits.
    99   ///
    100   ///\param LM This read-only UEdgeMap determines the costs of the
     99  ///FredmanTarjan, it is only passed to \ref
     100  ///FredmanTarjanDefaultTraits.
     101  ///
     102  ///\param CM This read-only UEdgeMap determines the costs of the
    101103  ///edges. It is read once for each edge, so the map may involve in
    102   ///relatively time consuming process to compute the edge cost if
    103   ///it is necessary. The default map type is \ref
    104   ///concept::UGraph::UEdgeMap "UGraph::UEdgeMap<int>". The value
    105   ///of LM is not used directly by FredmanTarjan, it is only passed to \ref
    106   ///FredmanTarjanDefaultTraits.
    107   ///
    108   ///\param TR Traits class to set
    109   ///various data types used by the algorithm.  The default traits
    110   ///class is \ref FredmanTarjanDefaultTraits
    111   ///"FredmanTarjanDefaultTraits<GR,LM>".  See \ref
    112   ///FredmanTarjanDefaultTraits for the documentation of a FredmanTarjan traits
    113   ///class.
     104  ///relatively time consuming process to compute the edge cost if it
     105  ///is necessary. The default map type is \ref
     106  ///concept::UGraph::UEdgeMap "UGraph::UEdgeMap<int>". The value of
     107  ///CM is not used directly by FredmanTarjan, it is only passed to
     108  ///\ref FredmanTarjanDefaultTraits.
     109  ///
     110  ///\param TR Traits class to set various data types used by the
     111  ///algorithm.  The default traits class is \ref
     112  ///FredmanTarjanDefaultTraits "FredmanTarjanDefaultTraits<GR,CM>".
     113  ///See \ref FredmanTarjanDefaultTraits for the documentation of a
     114  ///FredmanTarjan traits class.
    114115  ///
    115116  ///\author Balazs Attila Mihaly
     
    117118#ifdef DOXYGEN
    118119  template <typename GR,
    119             typename LM,
     120            typename CM,
    120121            typename TR>
    121122#else
    122123  template <typename GR=ListUGraph,
    123             typename LM=typename GR::template UEdgeMap<int>,
    124             typename TR=FredmanTarjanDefaultTraits<GR,LM> >
     124            typename CM=typename GR::template UEdgeMap<int>,
     125            typename TR=FredmanTarjanDefaultTraits<GR,CM> >
    125126#endif
    126127  class FredmanTarjan {
    127128  public:
    128     /**
    129      * \brief \ref Exception for uninitialized parameters.
    130      *
    131      * This error represents problems in the initialization
    132      * of the parameters of the algorithms.
    133      */
     129    ///\brief \ref Exception for uninitialized parameters.
     130    ///
     131    ///This error represents problems in the initialization
     132    ///of the parameters of the algorithms.
    134133    class UninitializedParameter : public lemon::UninitializedParameter {
    135134    public:
  • lemon/graph_adaptor.h

    r2037 r2042  
    4646  ///Base type for the Graph Adaptors
    4747  ///
    48   ///\warning Graph adaptors are in even
    49   ///more experimental state than the other
    50   ///parts of the lib. Use them at you own risk.
    51   ///
    5248  ///This is the base type for most of LEMON graph adaptors.
    5349  ///This class implements a trivial graph adaptor i.e. it only wraps the
     
    252248  ///\brief A graph adaptor which reverses the orientation of the edges.
    253249  ///\ingroup graph_adaptors
    254   ///
    255   ///\warning Graph adaptors are in even more experimental
    256   ///state than the other
    257   ///parts of the lib. Use them at you own risk.
    258250  ///
    259251  /// If \c g is defined as
     
    648640  /// \brief A graph adaptor for hiding nodes and edges from a graph.
    649641  /// \ingroup graph_adaptors
    650   ///
    651   /// \warning Graph adaptors are in even more experimental state than the
    652   /// other parts of the lib. Use them at you own risk.
    653642  ///
    654643  /// SubGraphAdaptor shows the graph with filtered node-set and
     
    771760  ///\ingroup graph_adaptors
    772761  ///
    773   ///\warning Graph adaptors are in even more experimental state
    774   ///than the other
    775   ///parts of the lib. Use them at you own risk.
    776   ///
    777762  ///An adaptor for hiding nodes from a graph.
    778763  ///This adaptor specializes SubGraphAdaptor in the way that only
     
    827812
    828813  ///\brief An adaptor for hiding edges from a graph.
    829   ///
    830   ///\warning Graph adaptors are in even more experimental state
    831   ///than the other parts of the lib. Use them at you own risk.
    832814  ///
    833815  ///An adaptor for hiding edges from a graph.
     
    14801462  ///\ingroup graph_adaptors
    14811463  ///
    1482   ///An adaptor for composing the residual graph for
    1483   ///directed flow and circulation problems.
    1484 //   ///Let \f$ G=(V, A) \f$ be a directed graph and let \f$ F \f$ be a
    1485 //   ///number type. Let moreover
    1486 //   ///\f$ f,c:A\to F \f$, be functions on the edge-set.
    1487 //   ///In the appications of ResGraphAdaptor, \f$ f \f$ usually stands for a
    1488 //   ///flow and \f$ c \f$ for a capacity function.   
    1489 //   ///Suppose that a graph instange \c g of type
    1490 //   ///\c ListGraph implements \f$ G \f$.
    1491 //   ///\code
    1492 //   /// ListGraph g;
    1493 //   ///\endcode
    1494 //   ///Then RevGraphAdaptor implements the graph structure with node-set
    1495 //   ///\f$ V \f$ and edge-set \f$ A_{forward}\cup A_{backward} \f$, where
    1496 //   ///\f$ A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\} \f$ and
    1497 //   ///\f$ A_{backward}=\{vu : uv\in A, f(uv)>0\} \f$,
    1498 //   ///i.e. the so called residual graph.
    1499 //   ///When we take the union \f$ A_{forward}\cup A_{backward} \f$,
    1500 //   ///multilicities are counted, i.e. if an edge is in both
    1501 //   ///\f$ A_{forward} \f$ and \f$ A_{backward} \f$, then in the adaptor it
    1502 //   ///appears twice. The following code shows how such an instance can be
    1503 //   ///constructed.
    1504 //   ///\code
    1505 //   /// typedef ListGraph Graph;
    1506 //   /// Graph::EdgeMap<int> f(g);
    1507 //   /// Graph::EdgeMap<int> c(g);
    1508 //   /// ResGraphAdaptor<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > ga(g);
    1509 //   ///\endcode
    1510 //   ///\author Marton Makai
    1511 //   ///
     1464  ///An adaptor for composing the residual graph for directed flow and
     1465  ///circulation problems.  Let \f$ G=(V, A) \f$ be a directed graph
     1466  ///and let \f$ F \f$ be a number type. Let moreover \f$ f,c:A\to F \f$,
     1467  ///be functions on the edge-set.
     1468  ///
     1469  ///In the appications of ResGraphAdaptor, \f$ f \f$ usually stands
     1470  ///for a flow and \f$ c \f$ for a capacity function.  Suppose that a
     1471  ///graph instange \c g of type \c ListGraph implements \f$ G \f$.
     1472  ///
     1473  ///\code
     1474  ///  ListGraph g;
     1475  ///\endcode
     1476  ///
     1477  ///Then RevGraphAdaptor implements the graph structure with node-set
     1478  /// \f$ V \f$ and edge-set \f$ A_{forward}\cup A_{backward} \f$,
     1479  ///where \f$ A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\} \f$ and
     1480  /// \f$ A_{backward}=\{vu : uv\in A, f(uv)>0\} \f$, i.e. the so called
     1481  ///residual graph.  When we take the union
     1482  /// \f$ A_{forward}\cup A_{backward} \f$, multilicities are counted, i.e.
     1483  ///if an edge is in both \f$ A_{forward} \f$ and \f$ A_{backward} \f$,
     1484  ///then in the adaptor it appears twice. The following code shows how
     1485  ///such an instance can be constructed.
     1486  ///
     1487  ///\code
     1488  ///  typedef ListGraph Graph;
     1489  ///  Graph::EdgeMap<int> f(g);
     1490  ///  Graph::EdgeMap<int> c(g);
     1491  ///  ResGraphAdaptor<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > ga(g);
     1492  ///\endcode
     1493  ///\author Marton Makai
     1494  ///
    15121495  template<typename Graph, typename Number,
    15131496           typename CapacityMap, typename FlowMap,
     
    16861669  ///\ingroup graph_adaptors
    16871670  ///
    1688   ///\warning Graph adaptors are in even more
    1689   ///experimental state than the other
    1690   ///parts of the lib. Use them at you own risk.
    1691   ///
    16921671  ///This graph adaptor is used for on-the-fly
    16931672  ///Dinits blocking flow computations.
  • lemon/johnson.h

    r1993 r2042  
    192192  /// should be used from each node.
    193193  ///
    194   /// The complexity of this algorithm is $O(n^2 * log(n) + n * log(n) * e)$ or
    195   /// with fibonacci heap O(n^2 * log(n) + n * e). Usually the fibonacci heap
     194  /// The complexity of this algorithm is \f$ O(n^2\log(n)+n\log(n)e) \f$ or
     195  /// with fibonacci heap \f$ O(n^2\log(n)+ne) \f$. Usually the fibonacci heap
    196196  /// implementation is slower than either binary heap implementation or the
    197197  /// Floyd-Warshall algorithm.
  • lemon/max_matching.h

    r2023 r2042  
    2525#include <lemon/graph_utils.h>
    2626
    27 ///\ingroup galgs
     27///\ingroup matching
    2828///\file
    29 ///\brief Maximum matching algorithm.
     29///\brief Maximum matching algorithm in undirected graph.
    3030
    3131namespace lemon {
    3232
    33   /// \addtogroup galgs
    34   /// @{
     33  /// \ingroup matching
    3534
    3635  ///Edmonds' alternating forest maximum matching algorithm.
     
    565564  }
    566565
    567   /// @}
    568566 
    569567} //END OF NAMESPACE LEMON
  • lemon/min_cost_arborescence.h

    r2037 r2042  
    9898  /// the minimum cost subgraph which are union of arborescences with the
    9999  /// given sources and spans all the nodes which are reachable from the
    100   /// sources. The time complexity of the algorithm is O(n^2 + e).
     100  /// sources. The time complexity of the algorithm is \f$ O(n^2+e) \f$.
    101101  ///
    102102  /// The algorithm provides also an optimal dual solution to arborescence
    103   /// that way the optimality of the algorithm can be proofed easily.
     103  /// that way the optimality of the solution can be proofed easily.
    104104  ///
    105105  /// \param _Graph The graph type the algorithm runs on. The default value
  • lemon/min_cut.h

    r2038 r2042  
    840840  /// at least two distinict subnetaux.
    841841  ///
    842   /// The complexity of the algorithm is O(n*e*log(n)) but with Fibonacci
    843   /// heap it can be decreased to O(n*e+n^2*log(n)). When the neutral capacity
    844   /// map is used then it uses BucketHeap which results O(n*e) time complexity.
     842  /// The complexity of the algorithm is \f$ O(ne\log(n)) \f$ but with
     843  /// Fibonacci heap it can be decreased to \f$ O(ne+n^2\log(n)) \f$. When
     844  /// the neutral capacity map is used then it uses BucketHeap which
     845  /// results \f$ O(ne) \f$ time complexity.
    845846#ifdef DOXYGEN
    846847  template <typename _Graph, typename _CapacityMap, typename _Traits>
  • lemon/prim.h

    r2030 r2042  
    137137  ///This class provides an efficient implementation of %Prim algorithm.
    138138  ///
    139   ///The running time is O(e*log n) where e is the number of edges and
     139  ///The running time is \f$ O(e\log(n)) \f$ where e is the number of edges and
    140140  ///n is the number of nodes in the graph.
    141141  ///
  • lemon/radix_sort.h

    r2033 r2042  
    209209  /// is choosen to partite the items on the next bit. This way, let be
    210210  /// \c c the maximal capacity and \c n the number of the items in
    211   /// the container, the time complexity of the algorithm \c O(log(c)*n)
    212   /// and the additional space complexity is \c O(log(c)).
     211  /// the container, the time complexity of the algorithm
     212  /// \f$ O(\log(c)n) \f$ and the additional space complexity is
     213  /// \f$ O(\log(c)) \f$.
    213214  ///
    214215  /// \param first The begin of the given range.
     
    430431  /// whole value. This way, let be \c c the maximal capacity of the integer
    431432  /// type and \c n the number of the items in
    432   /// the container, the time complexity of the algorithm \c O(log(c)*n)
    433   /// and the additional space complexity is \c O(n).
     433  /// the container, the time complexity of the algorithm \f$ O(\log(c)n) \f$
     434  /// and the additional space complexity is \f$ O(n) \f$.
    434435  ///
    435436  /// This sorting algorithm is stable so the order of two equal element
  • lemon/ugraph_adaptor.h

    r2037 r2042  
    835835  }
    836836
     837  /// \ingroup graph_adaptors
     838  ///
    837839  /// \brief An adaptor for hiding undirected edges from an undirected graph.
    838840  ///
Note: See TracChangeset for help on using the changeset viewer.