lemon-0.x: lemon/min_cut.h@c9e5de6e3eac (annotated)

deba@1967	1	/* -- C++ --
deba@1975	2	* lemon/min_cut.h - Part of LEMON, a generic C++ optimization library
deba@1967	3	*
deba@1967	4	* Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@1967	5	* (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@1967	6	*
deba@1967	7	* Permission to use, modify and distribute this software is granted
deba@1967	8	* provided that this copyright notice appears in all copies. For
deba@1967	9	* precise terms see the accompanying LICENSE file.
deba@1967	10	*
deba@1967	11	* This software is provided "AS IS" with no warranty of any kind,
deba@1967	12	* express or implied, and with no claim as to its suitability for any
deba@1967	13	* purpose.
deba@1967	14	*
deba@1967	15	*/
deba@1967	16
deba@1975	17	#ifndef LEMON_MIN_CUT_H
deba@1975	18	#define LEMON_MIN_CUT_H
deba@1967	19
deba@1967	20
deba@1967	21	/// \ingroup topology
deba@1967	22	/// \file
deba@1975	23	/// \brief Maximum cardinality search and min cut in undirected graphs.
deba@1967	24
deba@1967	25	#include <lemon/list_graph.h>
deba@1967	26	#include <lemon/bin_heap.h>
deba@1967	27	#include <lemon/linear_heap.h>
deba@1967	28
deba@1993	29	#include <lemon/bits/invalid.h>
deba@1967	30	#include <lemon/error.h>
deba@1967	31	#include <lemon/maps.h>
deba@1967	32
deba@1967	33	#include <functional>
deba@1967	34
deba@1967	35	namespace lemon {
deba@1967	36
deba@1975	37	namespace _min_cut_bits {
deba@1967	38
deba@1967	39	template <typename CapacityMap>
deba@1967	40	struct HeapSelector {
deba@1967	41	template <typename Key, typename Value, typename Ref>
deba@1967	42	struct Selector {
deba@1967	43	typedef BinHeap<Key, Value, Ref, std::greater<Value> > Heap;
deba@1967	44	};
deba@1967	45	};
deba@1967	46
deba@1967	47	template <typename CapacityKey>
deba@1967	48	struct HeapSelector<ConstMap<CapacityKey, Const<int, 1> > > {
deba@1967	49	template <typename Key, typename Value, typename Ref>
deba@1967	50	struct Selector {
deba@1967	51	typedef LinearHeap<Key, Ref, false > Heap;
deba@1967	52	};
deba@1967	53	};
deba@1967	54
deba@1967	55	}
deba@1967	56
deba@1967	57	/// \brief Default traits class of MaxCardinalitySearch class.
deba@1967	58	///
deba@1967	59	/// Default traits class of MaxCardinalitySearch class.
deba@1967	60	/// \param Graph Graph type.
deba@1967	61	/// \param CapacityMap Type of length map.
deba@1967	62	template <typename _Graph, typename _CapacityMap>
deba@1967	63	struct MaxCardinalitySearchDefaultTraits {
deba@1967	64	/// The graph type the algorithm runs on.
deba@1967	65	typedef _Graph Graph;
deba@1967	66
deba@1967	67	/// \brief The type of the map that stores the edge capacities.
deba@1967	68	///
deba@1967	69	/// The type of the map that stores the edge capacities.
deba@1967	70	/// It must meet the \ref concept::ReadMap "ReadMap" concept.
deba@1967	71	typedef _CapacityMap CapacityMap;
deba@1967	72
deba@1967	73	/// \brief The type of the capacity of the edges.
deba@1967	74	typedef typename CapacityMap::Value Value;
deba@1967	75
deba@1967	76	/// \brief The cross reference type used by heap.
deba@1967	77	///
deba@1967	78	/// The cross reference type used by heap.
deba@1967	79	/// Usually it is \c Graph::NodeMap<int>.
deba@1967	80	typedef typename Graph::template NodeMap<int> HeapCrossRef;
deba@1967	81
deba@1967	82	/// \brief Instantiates a HeapCrossRef.
deba@1967	83	///
deba@1967	84	/// This function instantiates a \ref HeapCrossRef.
deba@1967	85	/// \param graph is the graph, to which we would like to define the
deba@1967	86	/// HeapCrossRef.
deba@1967	87	static HeapCrossRef *createHeapCrossRef(const Graph &graph) {
deba@1967	88	return new HeapCrossRef(graph);
deba@1967	89	}
deba@1967	90
deba@1967	91	/// \brief The heap type used by MaxCardinalitySearch algorithm.
deba@1967	92	///
deba@1967	93	/// The heap type used by MaxCardinalitySearch algorithm. It should
deba@1967	94	/// maximalize the priorities. The default heap type is
deba@1967	95	/// the \ref BinHeap, but it is specialized when the
deba@1967	96	/// CapacityMap is ConstMap<Graph::Node, Const<int, 1> >
deba@1967	97	/// to LinearHeap.
deba@1967	98	///
deba@1967	99	/// \sa MaxCardinalitySearch
deba@1975	100	typedef typename _min_cut_bits
deba@1967	101	::HeapSelector<CapacityMap>
deba@1967	102	::template Selector<typename Graph::Node, Value, HeapCrossRef>
deba@1967	103	::Heap Heap;
deba@1967	104
deba@1967	105	/// \brief Instantiates a Heap.
deba@1967	106	///
deba@1967	107	/// This function instantiates a \ref Heap.
deba@1967	108	/// \param crossref The cross reference of the heap.
deba@1967	109	static Heap *createHeap(HeapCrossRef& crossref) {
deba@1967	110	return new Heap(crossref);
deba@1967	111	}
deba@1967	112
deba@1967	113	/// \brief The type of the map that stores whether a nodes is processed.
deba@1967	114	///
deba@1967	115	/// The type of the map that stores whether a nodes is processed.
deba@1967	116	/// It must meet the \ref concept::WriteMap "WriteMap" concept.
deba@1967	117	/// By default it is a NullMap.
deba@1967	118	typedef NullMap<typename Graph::Node, bool> ProcessedMap;
deba@1967	119
deba@1967	120	/// \brief Instantiates a ProcessedMap.
deba@1967	121	///
deba@1967	122	/// This function instantiates a \ref ProcessedMap.
deba@1967	123	/// \param g is the graph, to which
deba@1967	124	/// we would like to define the \ref ProcessedMap
deba@1967	125	#ifdef DOXYGEN
deba@1967	126	static ProcessedMap *createProcessedMap(const Graph &graph)
deba@1967	127	#else
deba@1967	128	static ProcessedMap *createProcessedMap(const Graph &)
deba@1967	129	#endif
deba@1967	130	{
deba@1967	131	return new ProcessedMap();
deba@1967	132	}
deba@1967	133
deba@1967	134	/// \brief The type of the map that stores the cardinalties of the nodes.
deba@1967	135	///
deba@1967	136	/// The type of the map that stores the cardinalities of the nodes.
deba@1967	137	/// It must meet the \ref concept::WriteMap "WriteMap" concept.
deba@1967	138	typedef typename Graph::template NodeMap<Value> CardinalityMap;
deba@1967	139
deba@1967	140	/// \brief Instantiates a CardinalityMap.
deba@1967	141	///
deba@1967	142	/// This function instantiates a \ref CardinalityMap.
deba@1967	143	/// \param graph is the graph, to which we would like to define the \ref
deba@1967	144	/// CardinalityMap
deba@1967	145	static CardinalityMap *createCardinalityMap(const Graph &graph) {
deba@1967	146	return new CardinalityMap(graph);
deba@1967	147	}
deba@1967	148
deba@1967	149	};
deba@1967	150
deba@1967	151	/// \ingroup topology
deba@1967	152	///
deba@1967	153	/// \brief Maximum Cardinality Search algorithm class.
deba@1967	154	///
deba@1967	155	/// This class provides an efficient implementation of Maximum Cardinality
deba@1967	156	/// Search algorithm. The maximum cardinality search chooses first time any
alpar@1973	157	/// node of the graph. Then every time it chooses the node which is connected
deba@1967	158	/// to the processed nodes at most in the sum of capacities on the out
deba@1967	159	/// edges. If there is a cut in the graph the algorithm should choose
alpar@1973	160	/// again any unprocessed node of the graph. Each node cardinality is
deba@1967	161	/// the sum of capacities on the out edges to the nodes which are processed
deba@1967	162	/// before the given node.
deba@1967	163	///
deba@1967	164	/// The edge capacities are passed to the algorithm using a
deba@1967	165	/// \ref concept::ReadMap "ReadMap", so it is easy to change it to any
deba@1967	166	/// kind of capacity.
deba@1967	167	///
deba@1967	168	/// The type of the capacity is determined by the \ref
deba@1967	169	/// concept::ReadMap::Value "Value" of the capacity map.
deba@1967	170	///
deba@1967	171	/// It is also possible to change the underlying priority heap.
deba@1967	172	///
deba@1967	173	///
deba@1967	174	/// \param _Graph The graph type the algorithm runs on. The default value
deba@1967	175	/// is \ref ListGraph. The value of Graph is not used directly by
deba@1967	176	/// the search algorithm, it is only passed to
deba@1967	177	/// \ref MaxCardinalitySearchDefaultTraits.
deba@1967	178	/// \param _CapacityMap This read-only EdgeMap determines the capacities of
deba@1967	179	/// the edges. It is read once for each edge, so the map may involve in
deba@1967	180	/// relatively time consuming process to compute the edge capacity if
deba@1967	181	/// it is necessary. The default map type is \ref
deba@1967	182	/// concept::StaticGraph::EdgeMap "Graph::EdgeMap<int>". The value
deba@1967	183	/// of CapacityMap is not used directly by search algorithm, it is only
deba@1967	184	/// passed to \ref MaxCardinalitySearchDefaultTraits.
deba@1967	185	/// \param _Traits Traits class to set various data types used by the
deba@1967	186	/// algorithm. The default traits class is
deba@1967	187	/// \ref MaxCardinalitySearchDefaultTraits
deba@1967	188	/// "MaxCardinalitySearchDefaultTraits<_Graph, _CapacityMap>".
deba@1967	189	/// See \ref MaxCardinalitySearchDefaultTraits
deba@1967	190	/// for the documentation of a MaxCardinalitySearch traits class.
deba@1967	191	///
deba@1967	192	/// \author Balazs Dezso
deba@1967	193
deba@1967	194	#ifdef DOXYGEN
deba@1967	195	template <typename _Graph, typename _CapacityMap, typename _Traits>
deba@1967	196	#else
deba@1967	197	template <typename _Graph = ListUGraph,
deba@1967	198	typename _CapacityMap = typename _Graph::template EdgeMap<int>,
deba@1967	199	typename _Traits =
deba@1967	200	MaxCardinalitySearchDefaultTraits<_Graph, _CapacityMap> >
deba@1967	201	#endif
deba@1967	202	class MaxCardinalitySearch {
deba@1967	203	public:
deba@1967	204	/// \brief \ref Exception for uninitialized parameters.
deba@1967	205	///
deba@1967	206	/// This error represents problems in the initialization
deba@1967	207	/// of the parameters of the algorithms.
deba@1967	208	class UninitializedParameter : public lemon::UninitializedParameter {
deba@1967	209	public:
deba@1967	210	virtual const char* exceptionName() const {
deba@1967	211	return "lemon::MaxCardinalitySearch::UninitializedParameter";
deba@1967	212	}
deba@1967	213	};
deba@1967	214
deba@1967	215	typedef _Traits Traits;
deba@1967	216	///The type of the underlying graph.
deba@1967	217	typedef typename Traits::Graph Graph;
deba@1967	218
deba@1967	219	///The type of the capacity of the edges.
deba@1967	220	typedef typename Traits::CapacityMap::Value Value;
deba@1967	221	///The type of the map that stores the edge capacities.
deba@1967	222	typedef typename Traits::CapacityMap CapacityMap;
deba@1967	223	///The type of the map indicating if a node is processed.
deba@1967	224	typedef typename Traits::ProcessedMap ProcessedMap;
deba@1967	225	///The type of the map that stores the cardinalities of the nodes.
deba@1967	226	typedef typename Traits::CardinalityMap CardinalityMap;
deba@1967	227	///The cross reference type used for the current heap.
deba@1967	228	typedef typename Traits::HeapCrossRef HeapCrossRef;
deba@1967	229	///The heap type used by the algorithm. It maximize the priorities.
deba@1967	230	typedef typename Traits::Heap Heap;
deba@1967	231	private:
deba@1967	232	/// Pointer to the underlying graph.
deba@1967	233	const Graph *_graph;
deba@1967	234	/// Pointer to the capacity map
deba@1967	235	const CapacityMap *_capacity;
deba@1967	236	///Pointer to the map of cardinality.
deba@1967	237	CardinalityMap *_cardinality;
deba@1967	238	///Indicates if \ref _cardinality is locally allocated (\c true) or not.
deba@1967	239	bool local_cardinality;
deba@1967	240	///Pointer to the map of processed status of the nodes.
deba@1967	241	ProcessedMap *_processed;
deba@1967	242	///Indicates if \ref _processed is locally allocated (\c true) or not.
deba@1967	243	bool local_processed;
deba@1967	244	///Pointer to the heap cross references.
deba@1967	245	HeapCrossRef *_heap_cross_ref;
deba@1967	246	///Indicates if \ref _heap_cross_ref is locally allocated (\c true) or not.
deba@1967	247	bool local_heap_cross_ref;
deba@1967	248	///Pointer to the heap.
deba@1967	249	Heap *_heap;
deba@1967	250	///Indicates if \ref _heap is locally allocated (\c true) or not.
deba@1967	251	bool local_heap;
deba@1967	252
deba@1967	253	public :
deba@1967	254
deba@1967	255	typedef MaxCardinalitySearch Create;
deba@1967	256
deba@1967	257	///\name Named template parameters
deba@1967	258
deba@1967	259	///@{
deba@1967	260
deba@1967	261	template <class T>
deba@1967	262	struct DefCardinalityMapTraits : public Traits {
deba@1967	263	typedef T CardinalityMap;
deba@1967	264	static CardinalityMap *createCardinalityMap(const Graph &)
deba@1967	265	{
deba@1967	266	throw UninitializedParameter();
deba@1967	267	}
deba@1967	268	};
deba@1967	269	/// \brief \ref named-templ-param "Named parameter" for setting
deba@1967	270	/// CardinalityMap type
deba@1967	271	///
deba@1967	272	/// \ref named-templ-param "Named parameter" for setting CardinalityMap
deba@1967	273	/// type
deba@1967	274	template <class T>
deba@1967	275	struct DefCardinalityMap
deba@1967	276	: public MaxCardinalitySearch<Graph, CapacityMap,
deba@1967	277	DefCardinalityMapTraits<T> > {
deba@1967	278	typedef MaxCardinalitySearch<Graph, CapacityMap,
deba@1967	279	DefCardinalityMapTraits<T> > Create;
deba@1967	280	};
deba@1967	281
deba@1967	282	template <class T>
deba@1967	283	struct DefProcessedMapTraits : public Traits {
deba@1967	284	typedef T ProcessedMap;
deba@1967	285	static ProcessedMap *createProcessedMap(const Graph &) {
deba@1967	286	throw UninitializedParameter();
deba@1967	287	}
deba@1967	288	};
deba@1967	289	/// \brief \ref named-templ-param "Named parameter" for setting
deba@1967	290	/// ProcessedMap type
deba@1967	291	///
deba@1967	292	/// \ref named-templ-param "Named parameter" for setting ProcessedMap type
deba@1967	293	///
deba@1967	294	template <class T>
deba@1967	295	struct DefProcessedMap
deba@1967	296	: public MaxCardinalitySearch<Graph, CapacityMap,
deba@1967	297	DefProcessedMapTraits<T> > {
deba@1967	298	typedef MaxCardinalitySearch<Graph, CapacityMap,
deba@1967	299	DefProcessedMapTraits<T> > Create;
deba@1967	300	};
deba@1967	301
deba@1967	302	template <class H, class CR>
deba@1967	303	struct DefHeapTraits : public Traits {
deba@1967	304	typedef CR HeapCrossRef;
deba@1967	305	typedef H Heap;
deba@1967	306	static HeapCrossRef *createHeapCrossRef(const Graph &) {
deba@1967	307	throw UninitializedParameter();
deba@1967	308	}
deba@1967	309	static Heap *createHeap(HeapCrossRef &) {
deba@1967	310	throw UninitializedParameter();
deba@1967	311	}
deba@1967	312	};
deba@1967	313	/// \brief \ref named-templ-param "Named parameter" for setting heap
deba@1967	314	/// and cross reference type
deba@1967	315	///
deba@1967	316	/// \ref named-templ-param "Named parameter" for setting heap and cross
deba@1967	317	/// reference type
deba@1967	318	template <class H, class CR = typename Graph::template NodeMap<int> >
deba@1967	319	struct DefHeap
deba@1967	320	: public MaxCardinalitySearch<Graph, CapacityMap,
deba@1967	321	DefHeapTraits<H, CR> > {
deba@1967	322	typedef MaxCardinalitySearch< Graph, CapacityMap,
deba@1967	323	DefHeapTraits<H, CR> > Create;
deba@1967	324	};
deba@1967	325
deba@1967	326	template <class H, class CR>
deba@1967	327	struct DefStandardHeapTraits : public Traits {
deba@1967	328	typedef CR HeapCrossRef;
deba@1967	329	typedef H Heap;
deba@1967	330	static HeapCrossRef *createHeapCrossRef(const Graph &graph) {
deba@1967	331	return new HeapCrossRef(graph);
deba@1967	332	}
deba@1967	333	static Heap *createHeap(HeapCrossRef &crossref) {
deba@1967	334	return new Heap(crossref);
deba@1967	335	}
deba@1967	336	};
deba@1967	337
deba@1967	338	/// \brief \ref named-templ-param "Named parameter" for setting heap and
deba@1967	339	/// cross reference type with automatic allocation
deba@1967	340	///
deba@1967	341	/// \ref named-templ-param "Named parameter" for setting heap and cross
deba@1967	342	/// reference type. It can allocate the heap and the cross reference
deba@1967	343	/// object if the cross reference's constructor waits for the graph as
deba@1967	344	/// parameter and the heap's constructor waits for the cross reference.
deba@1967	345	template <class H, class CR = typename Graph::template NodeMap<int> >
deba@1967	346	struct DefStandardHeap
deba@1967	347	: public MaxCardinalitySearch<Graph, CapacityMap,
deba@1967	348	DefStandardHeapTraits<H, CR> > {
deba@1967	349	typedef MaxCardinalitySearch<Graph, CapacityMap,
deba@1967	350	DefStandardHeapTraits<H, CR> >
deba@1967	351	Create;
deba@1967	352	};
deba@1967	353
deba@1967	354	///@}
deba@1967	355
deba@1967	356
deba@1967	357	protected:
deba@1967	358
deba@1967	359	MaxCardinalitySearch() {}
deba@1967	360
deba@1967	361	public:
deba@1967	362
deba@1967	363	/// \brief Constructor.
deba@1967	364	///
deba@1967	365	///\param _graph the graph the algorithm will run on.
deba@1967	366	///\param _capacity the capacity map used by the algorithm.
deba@1967	367	MaxCardinalitySearch(const Graph& graph, const CapacityMap& capacity) :
deba@1967	368	_graph(&graph), _capacity(&capacity),
deba@1967	369	_cardinality(0), local_cardinality(false),
deba@1967	370	_processed(0), local_processed(false),
deba@1967	371	_heap_cross_ref(0), local_heap_cross_ref(false),
deba@1967	372	_heap(0), local_heap(false)
deba@1967	373	{ }
deba@1967	374
deba@1967	375	/// \brief Destructor.
deba@1967	376	~MaxCardinalitySearch() {
deba@1967	377	if(local_cardinality) delete _cardinality;
deba@1967	378	if(local_processed) delete _processed;
deba@1967	379	if(local_heap_cross_ref) delete _heap_cross_ref;
deba@1967	380	if(local_heap) delete _heap;
deba@1967	381	}
deba@1967	382
deba@1967	383	/// \brief Sets the capacity map.
deba@1967	384	///
deba@1967	385	/// Sets the capacity map.
deba@1967	386	/// \return <tt> (*this) </tt>
deba@1967	387	MaxCardinalitySearch &capacityMap(const CapacityMap &m) {
deba@1967	388	_capacity = &m;
deba@1967	389	return *this;
deba@1967	390	}
deba@1967	391
deba@1967	392	/// \brief Sets the map storing the cardinalities calculated by the
deba@1967	393	/// algorithm.
deba@1967	394	///
deba@1967	395	/// Sets the map storing the cardinalities calculated by the algorithm.
deba@1967	396	/// If you don't use this function before calling \ref run(),
deba@1967	397	/// it will allocate one. The destuctor deallocates this
deba@1967	398	/// automatically allocated map, of course.
deba@1967	399	/// \return <tt> (*this) </tt>
deba@1967	400	MaxCardinalitySearch &cardinalityMap(CardinalityMap &m) {
deba@1967	401	if(local_cardinality) {
deba@1967	402	delete _cardinality;
deba@1967	403	local_cardinality=false;
deba@1967	404	}
deba@1967	405	_cardinality = &m;
deba@1967	406	return *this;
deba@1967	407	}
deba@1967	408
deba@1967	409	/// \brief Sets the map storing the processed nodes.
deba@1967	410	///
deba@1967	411	/// Sets the map storing the processed nodes.
deba@1967	412	/// If you don't use this function before calling \ref run(),
deba@1967	413	/// it will allocate one. The destuctor deallocates this
deba@1967	414	/// automatically allocated map, of course.
deba@1967	415	/// \return <tt> (*this) </tt>
deba@1967	416	MaxCardinalitySearch &processedMap(ProcessedMap &m)
deba@1967	417	{
deba@1967	418	if(local_processed) {
deba@1967	419	delete _processed;
deba@1967	420	local_processed=false;
deba@1967	421	}
deba@1967	422	_processed = &m;
deba@1967	423	return *this;
deba@1967	424	}
deba@1967	425
deba@1967	426	/// \brief Sets the heap and the cross reference used by algorithm.
deba@1967	427	///
deba@1967	428	/// Sets the heap and the cross reference used by algorithm.
deba@1967	429	/// If you don't use this function before calling \ref run(),
deba@1967	430	/// it will allocate one. The destuctor deallocates this
deba@1967	431	/// automatically allocated map, of course.
deba@1967	432	/// \return <tt> (*this) </tt>
deba@1967	433	MaxCardinalitySearch &heap(Heap& heap, HeapCrossRef &crossRef) {
deba@1967	434	if(local_heap_cross_ref) {
deba@1967	435	delete _heap_cross_ref;
deba@1967	436	local_heap_cross_ref = false;
deba@1967	437	}
deba@1967	438	_heap_cross_ref = &crossRef;
deba@1967	439	if(local_heap) {
deba@1967	440	delete _heap;
deba@1967	441	local_heap = false;
deba@1967	442	}
deba@1967	443	_heap = &heap;
deba@1967	444	return *this;
deba@1967	445	}
deba@1967	446
deba@1967	447	private:
deba@1967	448
deba@1967	449	typedef typename Graph::Node Node;
deba@1967	450	typedef typename Graph::NodeIt NodeIt;
deba@1967	451	typedef typename Graph::Edge Edge;
deba@1967	452	typedef typename Graph::InEdgeIt InEdgeIt;
deba@1967	453
deba@1967	454	void create_maps() {
deba@1967	455	if(!_cardinality) {
deba@1967	456	local_cardinality = true;
deba@1967	457	_cardinality = Traits::createCardinalityMap(*_graph);
deba@1967	458	}
deba@1967	459	if(!_processed) {
deba@1967	460	local_processed = true;
deba@1967	461	_processed = Traits::createProcessedMap(*_graph);
deba@1967	462	}
deba@1967	463	if (!_heap_cross_ref) {
deba@1967	464	local_heap_cross_ref = true;
deba@1967	465	_heap_cross_ref = Traits::createHeapCrossRef(*_graph);
deba@1967	466	}
deba@1967	467	if (!_heap) {
deba@1967	468	local_heap = true;
deba@1967	469	_heap = Traits::createHeap(*_heap_cross_ref);
deba@1967	470	}
deba@1967	471	}
deba@1967	472
deba@1967	473	void finalizeNodeData(Node node, Value capacity) {
deba@1967	474	_processed->set(node, true);
deba@1967	475	_cardinality->set(node, capacity);
deba@1967	476	}
deba@1967	477
deba@1967	478	public:
deba@1967	479	/// \name Execution control
deba@1967	480	/// The simplest way to execute the algorithm is to use
deba@1967	481	/// one of the member functions called \c run(...).
deba@1967	482	/// \n
deba@1967	483	/// If you need more control on the execution,
deba@1967	484	/// first you must call \ref init(), then you can add several source nodes
deba@1967	485	/// with \ref addSource().
deba@1967	486	/// Finally \ref start() will perform the actual path
deba@1967	487	/// computation.
deba@1967	488
deba@1967	489	///@{
deba@1967	490
deba@1967	491	/// \brief Initializes the internal data structures.
deba@1967	492	///
deba@1967	493	/// Initializes the internal data structures.
deba@1967	494	void init() {
deba@1967	495	create_maps();
deba@1967	496	_heap->clear();
deba@1967	497	for (NodeIt it(*_graph) ; it != INVALID ; ++it) {
deba@1967	498	_processed->set(it, false);
deba@1967	499	_heap_cross_ref->set(it, Heap::PRE_HEAP);
deba@1967	500	}
deba@1967	501	}
deba@1967	502
deba@1967	503	/// \brief Adds a new source node.
deba@1967	504	///
deba@1967	505	/// Adds a new source node to the priority heap.
deba@1967	506	///
deba@1967	507	/// It checks if the node has not yet been added to the heap.
deba@1967	508	void addSource(Node source, Value capacity = 0) {
deba@1967	509	if(_heap->state(source) == Heap::PRE_HEAP) {
deba@1967	510	_heap->push(source, capacity);
deba@1967	511	}
deba@1967	512	}
deba@1967	513
deba@1967	514	/// \brief Processes the next node in the priority heap
deba@1967	515	///
deba@1967	516	/// Processes the next node in the priority heap.
deba@1967	517	///
deba@1967	518	/// \return The processed node.
deba@1967	519	///
deba@1967	520	/// \warning The priority heap must not be empty!
deba@1967	521	Node processNextNode() {
deba@1967	522	Node node = _heap->top();
deba@1967	523	finalizeNodeData(node, _heap->prio());
deba@1967	524	_heap->pop();
deba@1967	525
deba@1967	526	for (InEdgeIt it(*_graph, node); it != INVALID; ++it) {
deba@1967	527	Node source = _graph->source(it);
deba@1967	528	switch (_heap->state(source)) {
deba@1967	529	case Heap::PRE_HEAP:
deba@1967	530	_heap->push(source, (*_capacity)[it]);
deba@1967	531	break;
deba@1967	532	case Heap::IN_HEAP:
deba@1967	533	_heap->decrease(source, (_heap)[source] + (_capacity)[it]);
deba@1967	534	break;
deba@1967	535	case Heap::POST_HEAP:
deba@1967	536	break;
deba@1967	537	}
deba@1967	538	}
deba@1967	539	return node;
deba@1967	540	}
deba@1967	541
deba@1967	542	/// \brief Next node to be processed.
deba@1967	543	///
deba@1967	544	/// Next node to be processed.
deba@1967	545	///
deba@1967	546	/// \return The next node to be processed or INVALID if the
deba@1967	547	/// priority heap is empty.
deba@1967	548	Node nextNode() {
deba@1967	549	return _heap->empty() ? _heap->top() : INVALID;
deba@1967	550	}
deba@1967	551
deba@1967	552	/// \brief Returns \c false if there are nodes
deba@1967	553	/// to be processed in the priority heap
deba@1967	554	///
deba@1967	555	/// Returns \c false if there are nodes
deba@1967	556	/// to be processed in the priority heap
deba@1967	557	bool emptyQueue() { return _heap->empty(); }
deba@1967	558	/// \brief Returns the number of the nodes to be processed
deba@1967	559	/// in the priority heap
deba@1967	560	///
deba@1967	561	/// Returns the number of the nodes to be processed in the priority heap
deba@1967	562	int queueSize() { return _heap->size(); }
deba@1967	563
deba@1967	564	/// \brief Executes the algorithm.
deba@1967	565	///
deba@1967	566	/// Executes the algorithm.
deba@1967	567	///
deba@1967	568	///\pre init() must be called and at least one node should be added
deba@1967	569	/// with addSource() before using this function.
deba@1967	570	///
deba@1967	571	/// This method runs the Maximum Cardinality Search algorithm from the
deba@1967	572	/// source node(s).
deba@1967	573	void start() {
deba@1967	574	while ( !_heap->empty() ) processNextNode();
deba@1967	575	}
deba@1967	576
deba@1967	577	/// \brief Executes the algorithm until \c dest is reached.
deba@1967	578	///
deba@1967	579	/// Executes the algorithm until \c dest is reached.
deba@1967	580	///
deba@1967	581	/// \pre init() must be called and at least one node should be added
deba@1967	582	/// with addSource() before using this function.
deba@1967	583	///
deba@1967	584	/// This method runs the %MaxCardinalitySearch algorithm from the source
deba@1967	585	/// nodes.
deba@1967	586	void start(Node dest) {
deba@1967	587	while ( !_heap->empty() && _heap->top()!=dest ) processNextNode();
deba@1967	588	if ( !_heap->empty() ) finalizeNodeData(_heap->top(), _heap->prio());
deba@1967	589	}
deba@1967	590
deba@1967	591	/// \brief Executes the algorithm until a condition is met.
deba@1967	592	///
deba@1967	593	/// Executes the algorithm until a condition is met.
deba@1967	594	///
deba@1967	595	/// \pre init() must be called and at least one node should be added
deba@1967	596	/// with addSource() before using this function.
deba@1967	597	///
deba@1967	598	/// \param nm must be a bool (or convertible) node map. The algorithm
deba@1967	599	/// will stop when it reaches a node \c v with <tt>nm[v]==true</tt>.
deba@1967	600	template <typename NodeBoolMap>
deba@1967	601	void start(const NodeBoolMap &nm) {
deba@1967	602	while ( !_heap->empty() && !nm[_heap->top()] ) processNextNode();
deba@1967	603	if ( !_heap->empty() ) finalizeNodeData(_heap->top(),_heap->prio());
deba@1967	604	}
deba@1967	605
deba@1967	606	/// \brief Runs the maximal cardinality search algorithm from node \c s.
deba@1967	607	///
deba@1967	608	/// This method runs the %MaxCardinalitySearch algorithm from a root
deba@1967	609	/// node \c s.
deba@1967	610	///
deba@1967	611	///\note d.run(s) is just a shortcut of the following code.
deba@1967	612	///\code
deba@1967	613	/// d.init();
deba@1967	614	/// d.addSource(s);
deba@1967	615	/// d.start();
deba@1967	616	///\endcode
deba@1967	617	void run(Node s) {
deba@1967	618	init();
deba@1967	619	addSource(s);
deba@1967	620	start();
deba@1967	621	}
deba@1967	622
deba@1967	623	/// \brief Runs the maximal cardinality search algorithm for the
deba@1967	624	/// whole graph.
deba@1967	625	///
deba@1967	626	/// This method runs the %MaxCardinalitySearch algorithm from all
deba@1967	627	/// unprocessed node of the graph.
deba@1967	628	///
deba@1967	629	///\note d.run(s) is just a shortcut of the following code.
deba@1967	630	///\code
deba@1967	631	/// d.init();
deba@1967	632	/// for (NodeIt it(graph); it != INVALID; ++it) {
deba@1967	633	/// if (!d.reached(it)) {
deba@1967	634	/// d.addSource(s);
deba@1967	635	/// d.start();
deba@1967	636	/// }
deba@1967	637	/// }
deba@1967	638	///\endcode
deba@1967	639	void run() {
deba@1967	640	init();
deba@1967	641	for (NodeIt it(*_graph); it != INVALID; ++it) {
deba@1967	642	if (!reached(it)) {
deba@1967	643	addSource(it);
deba@1967	644	start();
deba@1967	645	}
deba@1967	646	}
deba@1967	647	}
deba@1967	648
deba@1967	649	///@}
deba@1967	650
deba@1967	651	/// \name Query Functions
deba@1967	652	/// The result of the maximum cardinality search algorithm can be
deba@1967	653	/// obtained using these functions.
deba@1967	654	/// \n
deba@1967	655	/// Before the use of these functions, either run() or start() must be
deba@1967	656	/// called.
deba@1967	657
deba@1967	658	///@{
deba@1967	659
deba@1967	660	/// \brief The cardinality of a node.
deba@1967	661	///
deba@1967	662	/// Returns the cardinality of a node.
deba@1967	663	/// \pre \ref run() must be called before using this function.
deba@1967	664	/// \warning If node \c v in unreachable from the root the return value
deba@1967	665	/// of this funcion is undefined.
deba@1967	666	Value cardinality(Node node) const { return (*_cardinality)[node]; }
deba@1967	667
deba@1967	668	/// \brief Returns a reference to the NodeMap of cardinalities.
deba@1967	669	///
deba@1967	670	/// Returns a reference to the NodeMap of cardinalities. \pre \ref run()
deba@1967	671	/// must be called before using this function.
deba@1967	672	const CardinalityMap &cardinalityMap() const { return *_cardinality;}
deba@1967	673
deba@1967	674	/// \brief Checks if a node is reachable from the root.
deba@1967	675	///
deba@1967	676	/// Returns \c true if \c v is reachable from the root.
deba@1967	677	/// \warning The source nodes are inditated as unreached.
deba@1967	678	/// \pre \ref run() must be called before using this function.
deba@1967	679	bool reached(Node v) { return (*_heap_cross_ref)[v] != Heap::PRE_HEAP; }
deba@1967	680
deba@1967	681	/// \brief Checks if a node is processed.
deba@1967	682	///
deba@1967	683	/// Returns \c true if \c v is processed, i.e. the shortest
deba@1967	684	/// path to \c v has already found.
deba@1967	685	/// \pre \ref run() must be called before using this function.
deba@1967	686	bool processed(Node v) { return (*_heap_cross_ref)[v] == Heap::POST_HEAP; }
deba@1967	687
deba@1967	688	///@}
deba@1967	689	};
deba@1967	690
deba@1975	691	/// \brief Default traits class of MinCut class.
deba@1967	692	///
deba@1975	693	/// Default traits class of MinCut class.
deba@1967	694	/// \param Graph Graph type.
deba@1967	695	/// \param CapacityMap Type of length map.
deba@1967	696	template <typename _Graph, typename _CapacityMap>
deba@1975	697	struct MinCutDefaultTraits {
deba@1967	698	/// \brief The type of the capacity of the edges.
deba@1967	699	typedef typename _CapacityMap::Value Value;
deba@1967	700
deba@1967	701	/// The graph type the algorithm runs on.
deba@1967	702	typedef _Graph Graph;
deba@1967	703
deba@1975	704	/// The AuxGraph type which is an EraseableGraph
deba@1975	705	typedef ListUGraph AuxGraph;
deba@1967	706
deba@1975	707	/// \brief Instantiates a AuxGraph.
deba@1967	708	///
deba@1975	709	/// This function instantiates a \ref AuxGraph.
deba@1975	710	static AuxGraph *createAuxGraph() {
deba@1975	711	return new AuxGraph();
deba@1967	712	}
deba@1967	713
deba@1967	714	/// \brief The type of the map that stores the edge capacities.
deba@1967	715	///
deba@1967	716	/// The type of the map that stores the edge capacities.
deba@1967	717	/// It must meet the \ref concept::ReadMap "ReadMap" concept.
deba@1967	718	typedef _CapacityMap CapacityMap;
deba@1967	719
deba@1967	720	/// \brief Instantiates a CapacityMap.
deba@1967	721	///
deba@1967	722	/// This function instantiates a \ref CapacityMap.
deba@1967	723	#ifdef DOXYGEN
deba@1967	724	static CapacityMap *createCapacityMap(const Graph& graph)
deba@1967	725	#else
deba@1967	726	static CapacityMap *createCapacityMap(const Graph&)
deba@1967	727	#endif
deba@1967	728	{
deba@1967	729	throw UninitializedParameter();
deba@1967	730	}
deba@1967	731
deba@1975	732	/// \brief The AuxCapacityMap type
deba@1967	733	///
deba@1975	734	/// The type of the map that stores the auxing edge capacities.
deba@1975	735	typedef AuxGraph::UEdgeMap<Value> AuxCapacityMap;
deba@1967	736
deba@1975	737	/// \brief Instantiates a AuxCapacityMap.
deba@1967	738	///
deba@1975	739	/// This function instantiates a \ref AuxCapacityMap.
deba@1975	740	static AuxCapacityMap *createAuxCapacityMap(const AuxGraph& graph) {
deba@1975	741	return new AuxCapacityMap(graph);
deba@1967	742	}
deba@1967	743
deba@1967	744	/// \brief The cross reference type used by heap.
deba@1967	745	///
deba@1967	746	/// The cross reference type used by heap.
deba@1967	747	/// Usually it is \c Graph::NodeMap<int>.
deba@1975	748	typedef AuxGraph::NodeMap<int> HeapCrossRef;
deba@1967	749
deba@1967	750	/// \brief Instantiates a HeapCrossRef.
deba@1967	751	///
deba@1967	752	/// This function instantiates a \ref HeapCrossRef.
deba@1967	753	/// \param graph is the graph, to which we would like to define the
deba@1967	754	/// HeapCrossRef.
deba@1975	755	static HeapCrossRef *createHeapCrossRef(const AuxGraph &graph) {
deba@1967	756	return new HeapCrossRef(graph);
deba@1967	757	}
deba@1967	758
deba@1975	759	/// \brief The heap type used by MinCut algorithm.
deba@1967	760	///
deba@1975	761	/// The heap type used by MinCut algorithm. It should
deba@1967	762	/// maximalize the priorities and the heap's key type is
deba@1975	763	/// the aux graph's node.
deba@1967	764	///
deba@1967	765	/// \sa BinHeap
deba@1975	766	/// \sa MinCut
deba@1975	767	typedef typename _min_cut_bits
deba@1967	768	::HeapSelector<CapacityMap>
deba@1975	769	::template Selector<typename AuxGraph::Node, Value, HeapCrossRef>
deba@1967	770	::Heap Heap;
deba@1967	771
deba@1967	772	/// \brief Instantiates a Heap.
deba@1967	773	///
deba@1967	774	/// This function instantiates a \ref Heap.
deba@1967	775	/// \param crossref The cross reference of the heap.
deba@1967	776	static Heap *createHeap(HeapCrossRef& crossref) {
deba@1967	777	return new Heap(crossref);
deba@1967	778	}
deba@1967	779
deba@1975	780	/// \brief Map from the AuxGraph's node type to the Graph's node type.
deba@1967	781	///
deba@1975	782	/// Map from the AuxGraph's node type to the Graph's node type.
deba@1975	783	typedef typename AuxGraph
deba@1967	784	::template NodeMap<typename Graph::Node> NodeRefMap;
deba@1967	785
deba@1967	786	/// \brief Instantiates a NodeRefMap.
deba@1967	787	///
deba@1967	788	/// This function instantiates a \ref NodeRefMap.
deba@1975	789	static NodeRefMap *createNodeRefMap(const AuxGraph& graph) {
deba@1967	790	return new NodeRefMap(graph);
deba@1967	791	}
deba@1967	792
deba@1967	793	/// \brief Map from the Graph's node type to the Graph's node type.
deba@1967	794	///
deba@1967	795	/// Map from the Graph's node type to the Graph's node type.
deba@1967	796	typedef typename Graph
deba@1967	797	::template NodeMap<typename Graph::Node> ListRefMap;
deba@1967	798
deba@1967	799	/// \brief Instantiates a ListRefMap.
deba@1967	800	///
deba@1967	801	/// This function instantiates a \ref ListRefMap.
deba@1967	802	static ListRefMap *createListRefMap(const Graph& graph) {
deba@1967	803	return new ListRefMap(graph);
deba@1967	804	}
deba@1967	805
deba@1967	806
deba@1967	807	};
deba@1967	808
deba@1975	809	namespace _min_cut_bits {
deba@1967	810	template <typename _Key>
deba@1967	811	class LastTwoMap {
deba@1967	812	public:
deba@1967	813	typedef _Key Key;
deba@1967	814	typedef bool Value;
deba@1967	815
deba@1967	816	LastTwoMap(int _num) : num(_num) {}
deba@1967	817	void set(const Key& key, bool val) {
deba@1967	818	if (!val) return;
deba@1967	819	--num;
deba@1967	820	if (num > 1) return;
deba@1967	821	keys[num] = key;
deba@1967	822	}
deba@1967	823
deba@1967	824	Key operator[](int index) const { return keys[index]; }
deba@1967	825	private:
deba@1967	826	Key keys[2];
deba@1967	827	int num;
deba@1967	828	};
deba@1967	829	}
deba@1967	830
deba@1967	831	/// \ingroup topology
deba@1967	832	///
deba@1975	833	/// \brief Calculates the min cut in an undirected graph.
deba@1967	834	///
deba@1975	835	/// Calculates the min cut in an undirected graph.
deba@1967	836	/// The algorithm separates the graph's nodes to two partitions with the
deba@1975	837	/// min sum of edge capacities between the two partitions. The
deba@1975	838	/// algorithm can be used to test the netaux reliability specifically
deba@1975	839	/// to test how many links have to be destroyed in the netaux to split it
deba@1975	840	/// at least two distinict subnetaux.
deba@1967	841	///
deba@1967	842	/// The complexity of the algorithm is O(nelog(n)) but with Fibonacci
deba@1967	843	/// heap it can be decreased to O(ne+n^2log(n)). When the neutral capacity
deba@1967	844	/// map is used then it uses LinearHeap which results O(n*e) time complexity.
deba@1967	845	#ifdef DOXYGEN
deba@1967	846	template <typename _Graph, typename _CapacityMap, typename _Traits>
deba@1967	847	#else
deba@1967	848	template <typename _Graph = ListUGraph,
deba@1967	849	typename _CapacityMap = typename _Graph::template UEdgeMap<int>,
deba@1975	850	typename _Traits = MinCutDefaultTraits<_Graph, _CapacityMap> >
deba@1967	851	#endif
deba@1975	852	class MinCut {
deba@1967	853	public:
deba@1967	854	/// \brief \ref Exception for uninitialized parameters.
deba@1967	855	///
deba@1967	856	/// This error represents problems in the initialization
deba@1967	857	/// of the parameters of the algorithms.
deba@1967	858	class UninitializedParameter : public lemon::UninitializedParameter {
deba@1967	859	public:
deba@1967	860	virtual const char* exceptionName() const {
deba@1975	861	return "lemon::MinCut::UninitializedParameter";
deba@1967	862	}
deba@1967	863	};
deba@1967	864
deba@1967	865
deba@1967	866	private:
deba@1967	867
deba@1967	868	typedef _Traits Traits;
deba@1967	869	/// The type of the underlying graph.
deba@1967	870	typedef typename Traits::Graph Graph;
deba@1967	871
deba@1967	872	/// The type of the capacity of the edges.
deba@1967	873	typedef typename Traits::CapacityMap::Value Value;
deba@1967	874	/// The type of the map that stores the edge capacities.
deba@1967	875	typedef typename Traits::CapacityMap CapacityMap;
deba@1975	876	/// The type of the aux graph
deba@1975	877	typedef typename Traits::AuxGraph AuxGraph;
deba@1975	878	/// The type of the aux capacity map
deba@1975	879	typedef typename Traits::AuxCapacityMap AuxCapacityMap;
deba@1967	880	/// The cross reference type used for the current heap.
deba@1967	881	typedef typename Traits::HeapCrossRef HeapCrossRef;
deba@1967	882	/// The heap type used by the max cardinality algorithm.
deba@1967	883	typedef typename Traits::Heap Heap;
deba@1975	884	/// The node refrefernces between the original and aux graph type.
deba@1967	885	typedef typename Traits::NodeRefMap NodeRefMap;
deba@1967	886	/// The list node refrefernces in the original graph type.
deba@1967	887	typedef typename Traits::ListRefMap ListRefMap;
deba@1967	888
deba@1967	889	public:
deba@1967	890
deba@1967	891	///\name Named template parameters
deba@1967	892
deba@1967	893	///@{
deba@1967	894
deba@1967	895	struct DefNeutralCapacityTraits : public Traits {
deba@1967	896	typedef ConstMap<typename Graph::UEdge, Const<int, 1> > CapacityMap;
deba@1967	897	static CapacityMap *createCapacityMap(const Graph&) {
deba@1967	898	return new CapacityMap();
deba@1967	899	}
deba@1967	900	};
deba@1967	901	/// \brief \ref named-templ-param "Named parameter" for setting
deba@1967	902	/// the capacity type to constMap<UEdge, int, 1>()
deba@1967	903	///
deba@1967	904	/// \ref named-templ-param "Named parameter" for setting
deba@1967	905	/// the capacity type to constMap<UEdge, int, 1>()
deba@1967	906	struct DefNeutralCapacity
deba@1975	907	: public MinCut<Graph, CapacityMap, DefNeutralCapacityTraits> {
deba@1975	908	typedef MinCut<Graph, CapacityMap, DefNeutralCapacityTraits> Create;
deba@1967	909	};
deba@1967	910
deba@1967	911
deba@1967	912	template <class H, class CR>
deba@1967	913	struct DefHeapTraits : public Traits {
deba@1967	914	typedef CR HeapCrossRef;
deba@1967	915	typedef H Heap;
deba@1975	916	static HeapCrossRef *createHeapCrossRef(const AuxGraph &) {
deba@1967	917	throw UninitializedParameter();
deba@1967	918	}
deba@1967	919	static Heap *createHeap(HeapCrossRef &) {
deba@1967	920	throw UninitializedParameter();
deba@1967	921	}
deba@1967	922	};
deba@1967	923	/// \brief \ref named-templ-param "Named parameter" for setting heap
deba@1967	924	/// and cross reference type
deba@1967	925	///
deba@1967	926	/// \ref named-templ-param "Named parameter" for setting heap and cross
deba@1967	927	/// reference type
deba@1967	928	template <class H, class CR = typename Graph::template NodeMap<int> >
deba@1967	929	struct DefHeap
deba@1975	930	: public MinCut<Graph, CapacityMap, DefHeapTraits<H, CR> > {
deba@1975	931	typedef MinCut< Graph, CapacityMap, DefHeapTraits<H, CR> > Create;
deba@1967	932	};
deba@1967	933
deba@1967	934	template <class H, class CR>
deba@1967	935	struct DefStandardHeapTraits : public Traits {
deba@1967	936	typedef CR HeapCrossRef;
deba@1967	937	typedef H Heap;
deba@1975	938	static HeapCrossRef *createHeapCrossRef(const AuxGraph &graph) {
deba@1967	939	return new HeapCrossRef(graph);
deba@1967	940	}
deba@1967	941	static Heap *createHeap(HeapCrossRef &crossref) {
deba@1967	942	return new Heap(crossref);
deba@1967	943	}
deba@1967	944	};
deba@1967	945
deba@1967	946	/// \brief \ref named-templ-param "Named parameter" for setting heap and
deba@1967	947	/// cross reference type with automatic allocation
deba@1967	948	///
deba@1967	949	/// \ref named-templ-param "Named parameter" for setting heap and cross
deba@1967	950	/// reference type. It can allocate the heap and the cross reference
deba@1967	951	/// object if the cross reference's constructor waits for the graph as
deba@1967	952	/// parameter and the heap's constructor waits for the cross reference.
deba@1967	953	template <class H, class CR = typename Graph::template NodeMap<int> >
deba@1967	954	struct DefStandardHeap
deba@1975	955	: public MinCut<Graph, CapacityMap, DefStandardHeapTraits<H, CR> > {
deba@1975	956	typedef MinCut<Graph, CapacityMap, DefStandardHeapTraits<H, CR> >
deba@1967	957	Create;
deba@1967	958	};
deba@1967	959
deba@1967	960	///@}
deba@1967	961
deba@1967	962
deba@1967	963	private:
deba@1967	964	/// Pointer to the underlying graph.
deba@1967	965	const Graph *_graph;
deba@1967	966	/// Pointer to the capacity map
deba@1967	967	const CapacityMap *_capacity;
deba@1967	968	/// \brief Indicates if \ref _capacity is locally allocated
deba@1967	969	/// (\c true) or not.
deba@1967	970	bool local_capacity;
deba@1967	971
deba@1975	972	/// Pointer to the aux graph.
deba@1975	973	AuxGraph *_aux_graph;
deba@1975	974	/// \brief Indicates if \ref _aux_graph is locally allocated
deba@1967	975	/// (\c true) or not.
deba@1975	976	bool local_aux_graph;
deba@1975	977	/// Pointer to the aux capacity map
deba@1975	978	AuxCapacityMap *_aux_capacity;
deba@1975	979	/// \brief Indicates if \ref _aux_capacity is locally allocated
deba@1967	980	/// (\c true) or not.
deba@1975	981	bool local_aux_capacity;
deba@1967	982	/// Pointer to the heap cross references.
deba@1967	983	HeapCrossRef *_heap_cross_ref;
deba@1967	984	/// \brief Indicates if \ref _heap_cross_ref is locally allocated
deba@1967	985	/// (\c true) or not.
deba@1967	986	bool local_heap_cross_ref;
deba@1967	987	/// Pointer to the heap.
deba@1967	988	Heap *_heap;
deba@1967	989	/// Indicates if \ref _heap is locally allocated (\c true) or not.
deba@1967	990	bool local_heap;
deba@1967	991
deba@1975	992	/// The min cut value.
deba@1975	993	Value _min_cut;
deba@1975	994	/// The number of the nodes of the aux graph.
deba@1967	995	int _node_num;
deba@1967	996	/// The first and last node of the min cut in the next list;
deba@1967	997	typename Graph::Node _first_node, _last_node;
deba@1967	998
deba@1967	999	/// \brief The first and last element in the list associated
deba@1975	1000	/// to the aux graph node.
deba@1967	1001	NodeRefMap _first, _last;
deba@1967	1002	/// \brief The next node in the node lists.
deba@1967	1003	ListRefMap *_next;
deba@1967	1004
deba@1967	1005	void create_structures() {
deba@1967	1006	if (!_capacity) {
deba@1967	1007	local_capacity = true;
deba@1967	1008	_capacity = Traits::createCapacityMap(*_graph);
deba@1967	1009	}
deba@1975	1010	if(!_aux_graph) {
deba@1975	1011	local_aux_graph = true;
deba@1975	1012	_aux_graph = Traits::createAuxGraph();
deba@1967	1013	}
deba@1975	1014	if(!_aux_capacity) {
deba@1975	1015	local_aux_capacity = true;
deba@1975	1016	_aux_capacity = Traits::createAuxCapacityMap(*_aux_graph);
deba@1967	1017	}
deba@1967	1018
deba@1975	1019	_first = Traits::createNodeRefMap(*_aux_graph);
deba@1975	1020	_last = Traits::createNodeRefMap(*_aux_graph);
deba@1967	1021
deba@1967	1022	_next = Traits::createListRefMap(*_graph);
deba@1967	1023
deba@1975	1024	typename Graph::template NodeMap<typename AuxGraph::Node> ref(*_graph);
deba@1967	1025
deba@1967	1026	for (typename Graph::NodeIt it(*_graph); it != INVALID; ++it) {
deba@1967	1027	_next->set(it, INVALID);
deba@1975	1028	typename AuxGraph::Node node = _aux_graph->addNode();
deba@1967	1029	_first->set(node, it);
deba@1967	1030	_last->set(node, it);
deba@1967	1031	ref.set(it, node);
deba@1967	1032	}
deba@1967	1033
deba@1967	1034	for (typename Graph::UEdgeIt it(*_graph); it != INVALID; ++it) {
deba@1967	1035	if (_graph->source(it) == _graph->target(it)) continue;
deba@1975	1036	typename AuxGraph::UEdge uedge =
deba@1975	1037	_aux_graph->addEdge(ref[_graph->source(it)],
deba@1967	1038	ref[_graph->target(it)]);
deba@1975	1039	_aux_capacity->set(uedge, (*_capacity)[it]);
deba@1967	1040
deba@1967	1041	}
deba@1967	1042
deba@1967	1043	if (!_heap_cross_ref) {
deba@1967	1044	local_heap_cross_ref = true;
deba@1975	1045	_heap_cross_ref = Traits::createHeapCrossRef(*_aux_graph);
deba@1967	1046	}
deba@1967	1047	if (!_heap) {
deba@1967	1048	local_heap = true;
deba@1967	1049	_heap = Traits::createHeap(*_heap_cross_ref);
deba@1967	1050	}
deba@1967	1051	}
deba@1967	1052
deba@1967	1053	public :
deba@1967	1054
deba@1975	1055	typedef MinCut Create;
deba@1967	1056
deba@1967	1057
deba@1967	1058	/// \brief Constructor.
deba@1967	1059	///
deba@1967	1060	///\param graph the graph the algorithm will run on.
deba@1967	1061	///\param capacity the capacity map used by the algorithm.
deba@1975	1062	MinCut(const Graph& graph, const CapacityMap& capacity)
deba@1967	1063	: _graph(&graph),
deba@1967	1064	_capacity(&capacity), local_capacity(false),
deba@1975	1065	_aux_graph(0), local_aux_graph(false),
deba@1975	1066	_aux_capacity(0), local_aux_capacity(false),
deba@1967	1067	_heap_cross_ref(0), local_heap_cross_ref(false),
deba@1967	1068	_heap(0), local_heap(false),
deba@1967	1069	_first(0), _last(0), _next(0) {}
deba@1967	1070
deba@1967	1071	/// \brief Constructor.
deba@1967	1072	///
deba@1967	1073	/// This constructor can be used only when the Traits class
deba@1967	1074	/// defines how can we instantiate a local capacity map.
deba@1967	1075	/// If the DefNeutralCapacity used the algorithm automatically
deba@1967	1076	/// construct the capacity map.
deba@1967	1077	///
deba@1967	1078	///\param graph the graph the algorithm will run on.
deba@1975	1079	MinCut(const Graph& graph)
deba@1967	1080	: _graph(&graph),
deba@1967	1081	_capacity(0), local_capacity(false),
deba@1975	1082	_aux_graph(0), local_aux_graph(false),
deba@1975	1083	_aux_capacity(0), local_aux_capacity(false),
deba@1967	1084	_heap_cross_ref(0), local_heap_cross_ref(false),
deba@1967	1085	_heap(0), local_heap(false),
deba@1967	1086	_first(0), _last(0), _next(0) {}
deba@1967	1087
deba@1967	1088	/// \brief Destructor.
deba@1967	1089	///
deba@1967	1090	/// Destructor.
deba@1975	1091	~MinCut() {
deba@1967	1092	if (local_heap) delete _heap;
deba@1967	1093	if (local_heap_cross_ref) delete _heap_cross_ref;
deba@1967	1094	if (_first) delete _first;
deba@1967	1095	if (_last) delete _last;
deba@1967	1096	if (_next) delete _next;
deba@1975	1097	if (local_aux_capacity) delete _aux_capacity;
deba@1975	1098	if (local_aux_graph) delete _aux_graph;
deba@1967	1099	if (local_capacity) delete _capacity;
deba@1967	1100	}
deba@1967	1101
deba@1967	1102	/// \brief Sets the heap and the cross reference used by algorithm.
deba@1967	1103	///
deba@1967	1104	/// Sets the heap and the cross reference used by algorithm.
deba@1967	1105	/// If you don't use this function before calling \ref run(),
deba@1967	1106	/// it will allocate one. The destuctor deallocates this
deba@1967	1107	/// automatically allocated heap and cross reference, of course.
deba@1967	1108	/// \return <tt> (*this) </tt>
deba@1975	1109	MinCut &heap(Heap& heap, HeapCrossRef &crossRef)
deba@1967	1110	{
deba@1967	1111	if (local_heap_cross_ref) {
deba@1967	1112	delete _heap_cross_ref;
deba@1967	1113	local_heap_cross_ref=false;
deba@1967	1114	}
deba@1967	1115	_heap_cross_ref = &crossRef;
deba@1967	1116	if (local_heap) {
deba@1967	1117	delete _heap;
deba@1967	1118	local_heap=false;
deba@1967	1119	}
deba@1967	1120	_heap = &heap;
deba@1967	1121	return *this;
deba@1967	1122	}
deba@1967	1123
deba@1975	1124	/// \brief Sets the aux graph.
deba@1967	1125	///
deba@1975	1126	/// Sets the aux graph used by algorithm.
deba@1967	1127	/// If you don't use this function before calling \ref run(),
deba@1967	1128	/// it will allocate one. The destuctor deallocates this
deba@1967	1129	/// automatically allocated graph, of course.
deba@1967	1130	/// \return <tt> (*this) </tt>
deba@1975	1131	MinCut &auxGraph(AuxGraph& aux_graph)
deba@1967	1132	{
deba@1975	1133	if(local_aux_graph) {
deba@1975	1134	delete _aux_graph;
deba@1975	1135	local_aux_graph=false;
deba@1967	1136	}
deba@1975	1137	_aux_graph = &aux_graph;
deba@1967	1138	return *this;
deba@1967	1139	}
deba@1967	1140
deba@1975	1141	/// \brief Sets the aux capacity map.
deba@1967	1142	///
deba@1975	1143	/// Sets the aux capacity map used by algorithm.
deba@1967	1144	/// If you don't use this function before calling \ref run(),
deba@1967	1145	/// it will allocate one. The destuctor deallocates this
deba@1967	1146	/// automatically allocated graph, of course.
deba@1967	1147	/// \return <tt> (*this) </tt>
deba@1975	1148	MinCut &auxCapacityMap(AuxCapacityMap& aux_capacity_map)
deba@1967	1149	{
deba@1975	1150	if(local_aux_capacity) {
deba@1975	1151	delete _aux_capacity;
deba@1975	1152	local_aux_capacity=false;
deba@1967	1153	}
deba@1975	1154	_aux_capacity = &aux_capacity_map;
deba@1967	1155	return *this;
deba@1967	1156	}
deba@1967	1157
deba@1967	1158	/// \name Execution control
deba@1967	1159	/// The simplest way to execute the algorithm is to use
deba@1967	1160	/// one of the member functions called \c run().
deba@1967	1161	/// \n
deba@1967	1162	/// If you need more control on the execution,
deba@1967	1163	/// first you must call \ref init() and then call the start()
deba@1967	1164	/// or proper times the processNextPhase() member functions.
deba@1967	1165
deba@1967	1166	///@{
deba@1967	1167
deba@1967	1168	/// \brief Initializes the internal data structures.
deba@1967	1169	///
deba@1967	1170	/// Initializes the internal data structures.
deba@1967	1171	void init() {
deba@1967	1172	create_structures();
deba@1967	1173	_first_node = _last_node = INVALID;
deba@1967	1174	_node_num = countNodes(*_graph);
deba@1967	1175	}
deba@1967	1176
deba@1967	1177	/// \brief Processes the next phase
deba@1967	1178	///
deba@1967	1179	/// Processes the next phase in the algorithm. The function
deba@1967	1180	/// should be called countNodes(graph) - 1 times to get
deba@1975	1181	/// surely the min cut in the graph. The
deba@1967	1182	///
deba@1967	1183	///\return %True when the algorithm finished.
deba@1967	1184	bool processNextPhase() {
deba@1967	1185	if (_node_num <= 1) return true;
deba@1975	1186	using namespace _min_cut_bits;
deba@1967	1187
deba@1975	1188	typedef typename AuxGraph::Node Node;
deba@1975	1189	typedef typename AuxGraph::NodeIt NodeIt;
deba@1975	1190	typedef typename AuxGraph::UEdge UEdge;
deba@1975	1191	typedef typename AuxGraph::IncEdgeIt IncEdgeIt;
deba@1967	1192
deba@1975	1193	typedef typename MaxCardinalitySearch<AuxGraph, AuxCapacityMap>::
deba@1967	1194	template DefHeap<Heap, HeapCrossRef>::
deba@1967	1195	template DefCardinalityMap<NullMap<Node, Value> >::
deba@1967	1196	template DefProcessedMap<LastTwoMap<Node> >::
deba@1967	1197	Create MaxCardinalitySearch;
deba@1967	1198
deba@1975	1199	MaxCardinalitySearch mcs(_aux_graph, _aux_capacity);
deba@1975	1200	for (NodeIt it(*_aux_graph); it != INVALID; ++it) {
deba@1967	1201	_heap_cross_ref->set(it, Heap::PRE_HEAP);
deba@1967	1202	}
deba@1967	1203	mcs.heap(_heap, _heap_cross_ref);
deba@1967	1204
deba@1967	1205	LastTwoMap<Node> last_two_nodes(_node_num);
deba@1967	1206	mcs.processedMap(last_two_nodes);
deba@1967	1207
deba@1967	1208	NullMap<Node, Value> cardinality;
deba@1967	1209	mcs.cardinalityMap(cardinality);
deba@1967	1210
deba@1967	1211	mcs.run();
deba@1967	1212
deba@1975	1213	Node new_node = _aux_graph->addNode();
deba@1967	1214
deba@1975	1215	typename AuxGraph::template NodeMap<UEdge> edges(*_aux_graph, INVALID);
deba@1967	1216
deba@1967	1217	Node first_node = last_two_nodes[0];
deba@1967	1218	Node second_node = last_two_nodes[1];
deba@1967	1219
deba@1967	1220	_next->set((_last)[first_node], (_first)[second_node]);
deba@1967	1221	_first->set(new_node, (*_first)[first_node]);
deba@1967	1222	_last->set(new_node, (*_last)[second_node]);
deba@1967	1223
deba@1967	1224	Value current_cut = 0;
deba@1975	1225	for (IncEdgeIt it(*_aux_graph, first_node); it != INVALID; ++it) {
deba@1975	1226	Node node = _aux_graph->runningNode(it);
deba@1975	1227	current_cut += (*_aux_capacity)[it];
deba@1967	1228	if (node == second_node) continue;
deba@1967	1229	if (edges[node] == INVALID) {
deba@1975	1230	edges[node] = _aux_graph->addEdge(new_node, node);
deba@1975	1231	(_aux_capacity)[edges[node]] = (_aux_capacity)[it];
deba@1967	1232	} else {
deba@1975	1233	(_aux_capacity)[edges[node]] += (_aux_capacity)[it];
deba@1967	1234	}
deba@1967	1235	}
deba@1967	1236
deba@1975	1237	if (_first_node == INVALID \|\| current_cut < _min_cut) {
deba@1967	1238	_first_node = (*_first)[first_node];
deba@1967	1239	_last_node = (*_last)[first_node];
deba@1975	1240	_min_cut = current_cut;
deba@1967	1241	}
deba@1967	1242
deba@1975	1243	_aux_graph->erase(first_node);
deba@1967	1244
deba@1975	1245	for (IncEdgeIt it(*_aux_graph, second_node); it != INVALID; ++it) {
deba@1975	1246	Node node = _aux_graph->runningNode(it);
deba@1967	1247	if (edges[node] == INVALID) {
deba@1975	1248	edges[node] = _aux_graph->addEdge(new_node, node);
deba@1975	1249	(_aux_capacity)[edges[node]] = (_aux_capacity)[it];
deba@1967	1250	} else {
deba@1975	1251	(_aux_capacity)[edges[node]] += (_aux_capacity)[it];
deba@1967	1252	}
deba@1967	1253	}
deba@1975	1254	_aux_graph->erase(second_node);
deba@1967	1255
deba@1967	1256	--_node_num;
deba@1967	1257	return _node_num == 1;
deba@1967	1258	}
deba@1967	1259
deba@1967	1260	/// \brief Executes the algorithm.
deba@1967	1261	///
deba@1967	1262	/// Executes the algorithm.
deba@1967	1263	///
deba@1967	1264	/// \pre init() must be called
deba@1967	1265	void start() {
deba@1967	1266	while (!processNextPhase());
deba@1967	1267	}
deba@1967	1268
deba@1967	1269
deba@1975	1270	/// \brief Runs %MinCut algorithm.
deba@1967	1271	///
deba@1975	1272	/// This method runs the %Min cut algorithm
deba@1967	1273	///
deba@1967	1274	/// \note mc.run(s) is just a shortcut of the following code.
deba@1967	1275	///\code
deba@1967	1276	/// mc.init();
deba@1967	1277	/// mc.start();
deba@1967	1278	///\endcode
deba@1967	1279	void run() {
deba@1967	1280	init();
deba@1967	1281	start();
deba@1967	1282	}
deba@1967	1283
deba@1967	1284	///@}
deba@1967	1285
deba@1967	1286	/// \name Query Functions
deba@1975	1287	/// The result of the %MinCut algorithm can be obtained using these
deba@1967	1288	/// functions.\n
deba@1967	1289	/// Before the use of these functions,
deba@1967	1290	/// either run() or start() must be called.
deba@1967	1291
deba@1967	1292	///@{
deba@1967	1293
deba@1975	1294	/// \brief Returns the min cut value.
deba@1967	1295	///
deba@1975	1296	/// Returns the min cut value if the algorithm finished.
deba@1967	1297	/// After the first processNextPhase() it is a value of a
deba@1967	1298	/// valid cut in the graph.
deba@1967	1299	Value minCut() const {
deba@1975	1300	return _min_cut;
deba@1967	1301	}
deba@1967	1302
deba@1975	1303	/// \brief Returns a min cut in a NodeMap.
deba@1967	1304	///
deba@1967	1305	/// It sets the nodes of one of the two partitions to true in
deba@1967	1306	/// the given BoolNodeMap. The map contains a valid cut if the
alpar@1973	1307	/// map have been set false previously.
deba@1967	1308	template <typename NodeMap>
deba@1967	1309	Value quickMinCut(NodeMap& nodeMap) const {
deba@1967	1310	for (typename Graph::Node it = _first_node;
deba@1967	1311	it != _last_node; it = (*_next)[it]) {
deba@1967	1312	nodeMap.set(it, true);
deba@1967	1313	}
deba@1967	1314	nodeMap.set(_last_node, true);
deba@1967	1315	return minCut();
deba@1967	1316	}
deba@1967	1317
deba@1975	1318	/// \brief Returns a min cut in a NodeMap.
deba@1967	1319	///
deba@1967	1320	/// It sets the nodes of one of the two partitions to true and
deba@1967	1321	/// the other partition to false. The function first set all of the
deba@1967	1322	/// nodes to false and after it call the quickMinCut() member.
deba@1967	1323	template <typename NodeMap>
deba@1967	1324	Value minCut(NodeMap& nodeMap) const {
deba@1967	1325	for (typename Graph::NodeIt it(*_graph); it != INVALID; ++it) {
deba@1967	1326	nodeMap.set(it, false);
deba@1967	1327	}
deba@1967	1328	quickMinCut(nodeMap);
deba@1967	1329	return minCut();
deba@1967	1330	}
deba@1967	1331
deba@1975	1332	/// \brief Returns a min cut in an EdgeMap.
deba@1967	1333	///
deba@1975	1334	/// If an undirected edge is in a min cut then it will be
alpar@1973	1335	/// set to true and the others will be set to false in the given map.
deba@1967	1336	template <typename EdgeMap>
deba@1967	1337	Value cutEdges(EdgeMap& edgeMap) const {
deba@1967	1338	typename Graph::template NodeMap<bool> cut(*_graph, false);
deba@1967	1339	quickMinCut(cut);
deba@1967	1340	for (typename Graph::EdgeIt it(*_graph); it != INVALID; ++it) {
deba@1967	1341	edgeMap.set(it, cut[_graph->source(it)] ^ cut[_graph->target(it)]);
deba@1967	1342	}
deba@1967	1343	return minCut();
deba@1967	1344	}
deba@1967	1345
deba@1967	1346	///@}
deba@1967	1347
deba@1967	1348	};
deba@1967	1349	}
deba@1967	1350
deba@1967	1351	#endif

author	deba
	Tue, 07 Mar 2006 11:06:57 +0000
changeset 2001	c9e5de6e3eac
parent 1975	64db671eda28
child 2037	32e4bebee616
permissions	-rw-r--r--