Changeset 2037:32e4bebee616 in lemon-0.x
- Timestamp:
- 04/04/06 19:43:23 (18 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2676
- Location:
- lemon
- Files:
-
- 8 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/edmonds_karp.h
r2036 r2037 102 102 /// 103 103 /// The constructor of the class. 104 /// \param _graph The directed graph the algorithm runs on.105 /// \param _source The source node.106 /// \param _target The target node.107 /// \param _capacity The capacity of the edges.108 /// \param _flow The flow of the edges.109 /// \param _tolerance Tolerance class.104 /// \param graph The directed graph the algorithm runs on. 105 /// \param source The source node. 106 /// \param target The target node. 107 /// \param capacity The capacity of the edges. 108 /// \param flow The flow of the edges. 109 /// \param tolerance Tolerance class. 110 110 /// Except the graph, all of these parameters can be reset by 111 111 /// calling \ref source, \ref target, \ref capacityMap and \ref … … 253 253 /// Sets \c cut to the characteristic vector of a minimum value cut 254 254 /// It simply calls the minMinCut member. 255 /// \retval cut Write node bool map. 255 256 template <typename CutMap> 256 257 void minCut(CutMap& cut) const { … … 263 264 /// which is inclusionwise minimum. It is computed by processing a 264 265 /// bfs from the source node \c source in the residual graph. 266 /// \retval cut Write node bool map. 265 267 template <typename CutMap> 266 268 void minMinCut(CutMap& cut) const { … … 284 286 /// which is inclusionwise minimum. It is computed by processing a 285 287 /// bfs from the source node \c source in the residual graph. 288 /// \retval cut Write node bool map. 286 289 template <typename CutMap> 287 290 void maxMinCut(CutMap& cut) const { -
lemon/graph_adaptor.h
r2034 r2037 20 20 #define LEMON_GRAPH_ADAPTOR_H 21 21 22 /// 23 /// 24 /// 22 ///\ingroup graph_adaptors 23 ///\file 24 ///\brief Several graph adaptors. 25 25 /// 26 /// 26 ///This file contains several useful graph adaptor functions. 27 27 /// 28 /// 28 ///\author Marton Makai and Balazs Dezso 29 29 30 30 #include <lemon/bits/invalid.h> … … 75 75 GraphAdaptorBase(Graph& _graph) : graph(&_graph) { } 76 76 77 Graph& getGraph() { return *graph; }78 const Graph& getGraph() const { return *graph; }79 80 77 typedef typename Graph::Node Node; 81 78 typedef typename Graph::Edge Edge; … … 1480 1477 ///\brief An adaptor for composing the residual 1481 1478 ///graph for directed flow and circulation problems. 1479 /// 1482 1480 ///\ingroup graph_adaptors 1483 1481 /// 1484 1482 ///An adaptor for composing the residual graph for 1485 1483 ///directed flow and circulation problems. 1486 ///Let \f$ G=(V, A) \f$ be a directed graph and let \f$ F \f$ be a 1487 ///number type. Let moreover 1488 ///\f$ f,c:A\to F \f$, be functions on the edge-set. 1489 ///In the appications of ResGraphAdaptor, \f$ f \f$ usually stands for a flow 1490 ///and \f$ c \f$ for a capacity function. 1491 ///Suppose that a graph instange \c g of type 1492 ///\c ListGraph implements \f$ G \f$. 1493 ///\code 1494 /// ListGraph g; 1495 ///\endcode 1496 ///Then RevGraphAdaptor implements the graph structure with node-set 1497 ///\f$ V \f$ and edge-set \f$ A_{forward}\cup A_{backward} \f$, where 1498 ///\f$ A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\} \f$ and 1499 ///\f$ A_{backward}=\{vu : uv\in A, f(uv)>0\} \f$, 1500 ///i.e. the so called residual graph. 1501 ///When we take the union \f$ A_{forward}\cup A_{backward} \f$, 1502 ///multilicities are counted, i.e. if an edge is in both 1503 ///\f$ A_{forward} \f$ and \f$ A_{backward} \f$, then in the adaptor it 1504 ///appears twice. 1505 ///The following code shows how 1506 ///such an instance can be constructed. 1507 ///\code 1508 ///typedef ListGraph Graph; 1509 ///Graph::EdgeMap<int> f(g); 1510 ///Graph::EdgeMap<int> c(g); 1511 ///ResGraphAdaptor<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > ga(g); 1512 ///\endcode 1513 ///\author Marton Makai 1514 /// 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 // /// 1515 1512 template<typename Graph, typename Number, 1516 1513 typename CapacityMap, typename FlowMap, … … 1561 1558 1562 1559 public: 1563 1564 const Graph& getGraph() const { return ugraph.getGraph(); }1565 1560 1566 1561 /// \brief Constructor of the residual graph. -
lemon/graph_reader.h
r1956 r2037 40 40 /// description of \ref graph-io-page "Graph Input-Output". 41 41 /// 42 /// If you don't need very sophisticated43 /// behaviour then you can use the versions of the public function44 /// \ref readGraph() to read a graph (or a max flow instance etc).45 ///46 42 /// The file to be read may contain several maps and labeled nodes or 47 43 /// edges. … … 385 381 /// description of \ref graph-io-page "Graph Input-Output". 386 382 /// 387 /// If you don't need very sophisticated388 /// behaviour then you can use the versions of the public function389 /// \ref readGraph() to read a graph (or a max flow instance etc).390 ///391 383 /// The given file format may contain several maps and labeled nodes or 392 384 /// edges. -
lemon/graph_writer.h
r1956 r2037 41 41 /// description of \ref graph-io-page "Graph Input-Output". 42 42 /// 43 /// If you don't need very sophisticated44 /// behaviour then you can use the versions of the public function45 /// \ref writeGraph() to output a graph (or a max flow instance etc).46 ///47 43 /// To write a graph 48 44 /// you should first give writing commands to the writer. You can declare -
lemon/grid_ugraph.h
r1999 r2037 372 372 ///\endcode 373 373 /// 374 /// The graph type is fully conform to the \ref concept::U UGraph375 /// "Undirected UGraph" concept.374 /// The graph type is fully conform to the \ref concept::UGraph 375 /// "Undirected Graph" concept. 376 376 /// 377 377 /// \author Balazs Dezso -
lemon/min_cost_arborescence.h
r2025 r2037 58 58 /// 59 59 /// The type of the map that stores which edges are in the arborescence. 60 /// It must meet the \ref concept::Write dMap "WriteMap" concept.60 /// It must meet the \ref concept::WriteMap "WriteMap" concept. 61 61 /// Initially it will be setted to false on each edge. After it 62 62 /// will set all arborescence edges once. -
lemon/min_cut.h
r1993 r2037 121 121 /// 122 122 /// This function instantiates a \ref ProcessedMap. 123 /// \param g is the graph, to which123 /// \param graph is the graph, to which 124 124 /// we would like to define the \ref ProcessedMap 125 125 #ifdef DOXYGEN … … 363 363 /// \brief Constructor. 364 364 /// 365 ///\param _graph the graph the algorithm will run on.366 ///\param _capacity the capacity map used by the algorithm.365 ///\param graph the graph the algorithm will run on. 366 ///\param capacity the capacity map used by the algorithm. 367 367 MaxCardinalitySearch(const Graph& graph, const CapacityMap& capacity) : 368 368 _graph(&graph), _capacity(&capacity), -
lemon/ugraph_adaptor.h
r2031 r2037 64 64 65 65 void setGraph(Graph& _graph) { graph=&_graph; } 66 67 Graph& getGraph() { return *graph; }68 const Graph& getGraph() const { return *graph; }69 66 70 67 public:
Note: See TracChangeset
for help on using the changeset viewer.