Changeset 2042:bdc953f2a449 in lemon-0.x
- Timestamp:
- 04/07/06 11:54:35 (19 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2681
- Files:
-
- 14 edited
Legend:
- Unmodified
- Added
- Removed
-
demo/tight_edge_filter_map.h
r1956 r2042 33 33 edge-distance. 34 34 35 Let \f$ G=(V,A)\f$ be a directed graph (graph for short) and36 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. 37 37 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 potetial40 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$ 41 41 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$ 43 43 (or the reverse inequality holds for each edge). 44 44 An edge is said to be tight if this inequality holds with equality, -
doc/groups.dox
r2016 r2042 142 142 143 143 /** 144 @defgroup matching Matching algorithms in graphs and bipartite graphs 145 @ingroup galgs 146 \brief This group describes the algorithms 147 for find matchings in graphs and bipartite graphs. 148 */ 149 150 /** 144 151 @defgroup exceptions Exceptions 145 152 This group contains the exceptions thrown by LEMON library -
lemon/bellman_ford.h
r2010 r2042 156 156 /// should be used rather. 157 157 /// 158 /// The complexity of the algorithm is O(n * e).158 /// The maximal time complexity of the algorithm is \f$ O(ne) \f$. 159 159 /// 160 160 /// The type of the length is determined by the -
lemon/bucket_heap.h
r2038 r2042 38 38 /// priorities in such a way that finding the item with minimum priority is 39 39 /// 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 priorities42 /// 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. 43 43 /// 44 44 /// \param _Item Type of the items to be stored. -
lemon/floyd_warshall.h
r1993 r2042 160 160 /// there are negative circles then the johnson algorithm. 161 161 /// 162 /// The complexity of this algorithm is O(n^3 + e).162 /// The complexity of this algorithm is \f$ O(n^3+e) \f$. 163 163 /// 164 164 /// The type of the length is determined by the -
lemon/fredman_tarjan.h
r1993 r2042 45 45 ///Default traits class of FredmanTarjan class. 46 46 ///\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> 49 49 struct FredmanTarjanDefaultTraits{ 50 50 ///The graph type the algorithm runs on. … … 54 54 ///The type of the map that stores the edge costs. 55 55 ///It must meet the \ref concept::ReadMap "ReadMap" concept. 56 typedef LM CostMap;56 typedef CM CostMap; 57 57 //The type of the cost of the edges. 58 typedef typename LM::Value Value;58 typedef typename CM::Value Value; 59 59 ///The type of the map that stores whether an edge is in the 60 60 ///spanning tree or not. … … 77 77 ///%FredmanTarjan algorithm class to find a minimum spanning tree. 78 78 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. 95 96 /// 96 97 ///\param GR The graph type the algorithm runs on. The default value 97 98 ///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 101 103 ///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. 114 115 /// 115 116 ///\author Balazs Attila Mihaly … … 117 118 #ifdef DOXYGEN 118 119 template <typename GR, 119 typename LM,120 typename CM, 120 121 typename TR> 121 122 #else 122 123 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> > 125 126 #endif 126 127 class FredmanTarjan { 127 128 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. 134 133 class UninitializedParameter : public lemon::UninitializedParameter { 135 134 public: -
lemon/graph_adaptor.h
r2037 r2042 46 46 ///Base type for the Graph Adaptors 47 47 /// 48 ///\warning Graph adaptors are in even49 ///more experimental state than the other50 ///parts of the lib. Use them at you own risk.51 ///52 48 ///This is the base type for most of LEMON graph adaptors. 53 49 ///This class implements a trivial graph adaptor i.e. it only wraps the … … 252 248 ///\brief A graph adaptor which reverses the orientation of the edges. 253 249 ///\ingroup graph_adaptors 254 ///255 ///\warning Graph adaptors are in even more experimental256 ///state than the other257 ///parts of the lib. Use them at you own risk.258 250 /// 259 251 /// If \c g is defined as … … 648 640 /// \brief A graph adaptor for hiding nodes and edges from a graph. 649 641 /// \ingroup graph_adaptors 650 ///651 /// \warning Graph adaptors are in even more experimental state than the652 /// other parts of the lib. Use them at you own risk.653 642 /// 654 643 /// SubGraphAdaptor shows the graph with filtered node-set and … … 771 760 ///\ingroup graph_adaptors 772 761 /// 773 ///\warning Graph adaptors are in even more experimental state774 ///than the other775 ///parts of the lib. Use them at you own risk.776 ///777 762 ///An adaptor for hiding nodes from a graph. 778 763 ///This adaptor specializes SubGraphAdaptor in the way that only … … 827 812 828 813 ///\brief An adaptor for hiding edges from a graph. 829 ///830 ///\warning Graph adaptors are in even more experimental state831 ///than the other parts of the lib. Use them at you own risk.832 814 /// 833 815 ///An adaptor for hiding edges from a graph. … … 1480 1462 ///\ingroup graph_adaptors 1481 1463 /// 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 /// 1512 1495 template<typename Graph, typename Number, 1513 1496 typename CapacityMap, typename FlowMap, … … 1686 1669 ///\ingroup graph_adaptors 1687 1670 /// 1688 ///\warning Graph adaptors are in even more1689 ///experimental state than the other1690 ///parts of the lib. Use them at you own risk.1691 ///1692 1671 ///This graph adaptor is used for on-the-fly 1693 1672 ///Dinits blocking flow computations. -
lemon/johnson.h
r1993 r2042 192 192 /// should be used from each node. 193 193 /// 194 /// The complexity of this algorithm is $O(n^2 * log(n) + n * log(n) * e)$ or195 /// with fibonacci heap O(n^2 * log(n) + n * e). Usually the fibonacci heap194 /// 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 196 196 /// implementation is slower than either binary heap implementation or the 197 197 /// Floyd-Warshall algorithm. -
lemon/max_matching.h
r2023 r2042 25 25 #include <lemon/graph_utils.h> 26 26 27 ///\ingroup galgs27 ///\ingroup matching 28 28 ///\file 29 ///\brief Maximum matching algorithm .29 ///\brief Maximum matching algorithm in undirected graph. 30 30 31 31 namespace lemon { 32 32 33 /// \addtogroup galgs 34 /// @{ 33 /// \ingroup matching 35 34 36 35 ///Edmonds' alternating forest maximum matching algorithm. … … 565 564 } 566 565 567 /// @}568 566 569 567 } //END OF NAMESPACE LEMON -
lemon/min_cost_arborescence.h
r2037 r2042 98 98 /// the minimum cost subgraph which are union of arborescences with the 99 99 /// 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$. 101 101 /// 102 102 /// The algorithm provides also an optimal dual solution to arborescence 103 /// that way the optimality of the algorithmcan be proofed easily.103 /// that way the optimality of the solution can be proofed easily. 104 104 /// 105 105 /// \param _Graph The graph type the algorithm runs on. The default value -
lemon/min_cut.h
r2038 r2042 840 840 /// at least two distinict subnetaux. 841 841 /// 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. 845 846 #ifdef DOXYGEN 846 847 template <typename _Graph, typename _CapacityMap, typename _Traits> -
lemon/prim.h
r2030 r2042 137 137 ///This class provides an efficient implementation of %Prim algorithm. 138 138 /// 139 ///The running time is O(e*log n)where e is the number of edges and139 ///The running time is \f$ O(e\log(n)) \f$ where e is the number of edges and 140 140 ///n is the number of nodes in the graph. 141 141 /// -
lemon/radix_sort.h
r2033 r2042 209 209 /// is choosen to partite the items on the next bit. This way, let be 210 210 /// \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$. 213 214 /// 214 215 /// \param first The begin of the given range. … … 430 431 /// whole value. This way, let be \c c the maximal capacity of the integer 431 432 /// 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$. 434 435 /// 435 436 /// This sorting algorithm is stable so the order of two equal element -
lemon/ugraph_adaptor.h
r2037 r2042 835 835 } 836 836 837 /// \ingroup graph_adaptors 838 /// 837 839 /// \brief An adaptor for hiding undirected edges from an undirected graph. 838 840 ///
Note: See TracChangeset
for help on using the changeset viewer.