LEMON/LEMON-main Changeset - r710:f1fe0ddad6f7

Repositories » LEMON » LEMON-main

Summary
Changelog
Files
Switch To
- loading...
Options
- Lightweight changelog
- Search
Pull Requests

Changeset - r710:f1fe0ddad6f7

« 709:0747f3

711:28cfac »

r710:f1fe0ddad6f7

Wed, 08 Jul 2009 17:22:36

[Not Reviewed]

0 comments (0 inline)

kpeter (Peter Kovacs)
kpeter@inf.elte.hu

Move the heaps to a separate group (#299)

0 6 0

default

6 files changed with 40 insertions and 19 deletions:

doc/groups.dox

lemon/bin_heap.h

lemon/bucket_heap.h

lemon/concepts/heap.h

lemon/fib_heap.h

lemon/radix_heap.h

↑ Collapse diff ↑

doc/groups.dox

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2009
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		namespace lemon {
 		/**
 		@defgroup datas Data Structures
 		This group contains the several data structures implemented in LEMON.
 		*/
 		/**
 		@defgroup graphs Graph Structures
 		@ingroup datas
 		\brief Graph structures implemented in LEMON.
 		The implementation of combinatorial algorithms heavily relies on
 		efficient graph implementations. LEMON offers data structures which are
 		planned to be easily used in an experimental phase of implementation studies,
 		and thereafter the program code can be made efficient by small modifications.
 		The most efficient implementation of diverse applications require the
 		usage of different physical graph implementations. These differences
 		appear in the size of graph we require to handle, memory or time usage
 		limitations or in the set of operations through which the graph can be
 		accessed.  LEMON provides several physical graph structures to meet
 		the diverging requirements of the possible users.  In order to save on
 		running time or on memory usage, some structures may fail to provide
 		some graph features like arc/edge or node deletion.
 		Alteration of standard containers need a very limited number of
 		operations, these together satisfy the everyday requirements.
 		In the case of graph structures, different operations are needed which do
 		not alter the physical graph, but gives another view. If some nodes or
 		arcs have to be hidden or the reverse oriented graph have to be used, then
 		this is the case. It also may happen that in a flow implementation
 		the residual graph can be accessed by another algorithm, or a node-set
 		is to be shrunk for another algorithm.
 		LEMON also provides a variety of graphs for these requirements called
 		\ref graph_adaptors "graph adaptors". Adaptors cannot be used alone but only
 		in conjunction with other graph representations.
 		You are free to use the graph structure that fit your requirements
 		the best, most graph algorithms and auxiliary data structures can be used
 		with any graph structure.
 		<b>See also:</b> \ref graph_concepts "Graph Structure Concepts".
 		*/
 		/**
 		@defgroup graph_adaptors Adaptor Classes for Graphs
 		@ingroup graphs
 		\brief Adaptor classes for digraphs and graphs
 		This group contains several useful adaptor classes for digraphs and graphs.
 		The main parts of LEMON are the different graph structures, generic
 		graph algorithms, graph concepts, which couple them, and graph
 		adaptors. While the previous notions are more or less clear, the
 		latter one needs further explanation. Graph adaptors are graph classes
 		which serve for considering graph structures in different ways.
 		A short example makes this much clearer.  Suppose that we have an
 		instance \c g of a directed graph type, say ListDigraph and an algorithm
 		\code
 		template <typename Digraph>
 		int algorithm(const Digraph&);
 		\endcode
 		is needed to run on the reverse oriented graph.  It may be expensive
 		(in time or in memory usage) to copy \c g with the reversed
 		arcs.  In this case, an adaptor class is used, which (according
 		to LEMON \ref concepts::Digraph "digraph concepts") works as a digraph.
 		The adaptor uses the original digraph structure and digraph operations when
 		methods of the reversed oriented graph are called.  This means that the adaptor
 		have minor memory usage, and do not perform sophisticated algorithmic
 		actions.  The purpose of it is to give a tool for the cases when a
 		graph have to be used in a specific alteration.  If this alteration is
 		obtained by a usual construction like filtering the node or the arc set or
 		considering a new orientation, then an adaptor is worthwhile to use.
 		To come back to the reverse oriented graph, in this situation
 		\code
 		template<typename Digraph> class ReverseDigraph;
 		\endcode
 		template class can be used. The code looks as follows
 		\code
 		ListDigraph g;
 		ReverseDigraph<ListDigraph> rg(g);
 		int result = algorithm(rg);
 		\endcode
 		During running the algorithm, the original digraph \c g is untouched.
 		This techniques give rise to an elegant code, and based on stable
 		graph adaptors, complex algorithms can be implemented easily.
 		In flow, circulation and matching problems, the residual
 		graph is of particular importance. Combining an adaptor implementing
 		this with shortest path algorithms or minimum mean cycle algorithms,
 		a range of weighted and cardinality optimization algorithms can be
 		obtained. For other examples, the interested user is referred to the
 		detailed documentation of particular adaptors.
 		The behavior of graph adaptors can be very different. Some of them keep
 		capabilities of the original graph while in other cases this would be
 		meaningless. This means that the concepts that they meet depend
 		on the graph adaptor, and the wrapped graph.
 		For example, if an arc of a reversed digraph is deleted, this is carried
 		out by deleting the corresponding arc of the original digraph, thus the
 		adaptor modifies the original digraph.
 		However in case of a residual digraph, this operation has no sense.
 		Let us stand one more example here to simplify your work.
 		ReverseDigraph has constructor
 		\code
 		ReverseDigraph(Digraph& digraph);
 		\endcode
 		This means that in a situation, when a <tt>const %ListDigraph&</tt>
 		reference to a graph is given, then it have to be instantiated with
 		<tt>Digraph=const %ListDigraph</tt>.
 		\code
 		int algorithm1(const ListDigraph& g) {
 		  ReverseDigraph<const ListDigraph> rg(g);
 		  return algorithm2(rg);
+		}
 		\endcode
 		*/
 		/**
 		@defgroup maps Maps
 		@ingroup datas
 		\brief Map structures implemented in LEMON.
 		This group contains the map structures implemented in LEMON.
 		LEMON provides several special purpose maps and map adaptors that e.g. combine
 		new maps from existing ones.
 		<b>See also:</b> \ref map_concepts "Map Concepts".
 		*/
 		/**
 		@defgroup graph_maps Graph Maps
 		@ingroup maps
 		\brief Special graph-related maps.
 		This group contains maps that are specifically designed to assign
 		values to the nodes and arcs/edges of graphs.
 		If you are looking for the standard graph maps (\c NodeMap, \c ArcMap,
 		\c EdgeMap), see the \ref graph_concepts "Graph Structure Concepts".
 		*/
 		/**
 		\defgroup map_adaptors Map Adaptors
 		\ingroup maps
 		\brief Tools to create new maps from existing ones
 		This group contains map adaptors that are used to create "implicit"
 		maps from other maps.
 		Most of them are \ref concepts::ReadMap "read-only maps".
 		They can make arithmetic and logical operations between one or two maps
 		(negation, shifting, addition, multiplication, logical 'and', 'or',
 		'not' etc.) or e.g. convert a map to another one of different Value type.
 		The typical usage of this classes is passing implicit maps to
 		algorithms.  If a function type algorithm is called then the function
 		type map adaptors can be used comfortable. For example let's see the
 		usage of map adaptors with the \c graphToEps() function.
 		\code
 		  Color nodeColor(int deg) {
 		    if (deg >= 2) {
 		      return Color(0.5, 0.0, 0.5);
 		    } else if (deg == 1) {
 		      return Color(1.0, 0.5, 1.0);
 		    } else {
 		      return Color(0.0, 0.0, 0.0);
+		    }
+		  }
 		  Digraph::NodeMap<int> degree_map(graph);
 		  graphToEps(graph, "graph.eps")
 		    .coords(coords).scaleToA4().undirected()
 		    .nodeColors(composeMap(functorToMap(nodeColor), degree_map))
 		    .run();
 		\endcode
 		The \c functorToMap() function makes an \c int to \c Color map from the
 		\c nodeColor() function. The \c composeMap() compose the \c degree_map
 		and the previously created map. The composed map is a proper function to
 		get the color of each node.
 		The usage with class type algorithms is little bit harder. In this
 		case the function type map adaptors can not be used, because the
 		function map adaptors give back temporary objects.
 		\code
 		  Digraph graph;
 		  typedef Digraph::ArcMap<double> DoubleArcMap;
 		  DoubleArcMap length(graph);
 		  DoubleArcMap speed(graph);
 		  typedef DivMap<DoubleArcMap, DoubleArcMap> TimeMap;
 		  TimeMap time(length, speed);
 		  Dijkstra<Digraph, TimeMap> dijkstra(graph, time);
 		  dijkstra.run(source, target);
 		\endcode
 		We have a length map and a maximum speed map on the arcs of a digraph.
 		The minimum time to pass the arc can be calculated as the division of
 		the two maps which can be done implicitly with the \c DivMap template
 		class. We use the implicit minimum time map as the length map of the
 		\c Dijkstra algorithm.
 		*/
 		/**
 		@defgroup matrices Matrices
 		@ingroup datas
 		\brief Two dimensional data storages implemented in LEMON.
 		This group contains two dimensional data storages implemented in LEMON.
 		*/
 		/**
 		@defgroup paths Path Structures
 		@ingroup datas
 		\brief %Path structures implemented in LEMON.
 		This group contains the path structures implemented in LEMON.
 		LEMON provides flexible data structures to work with paths.
 		All of them have similar interfaces and they can be copied easily with
 		assignment operators and copy constructors. This makes it easy and
 		efficient to have e.g. the Dijkstra algorithm to store its result in
 		any kind of path structure.
-		\sa lemon::concepts::Path
+		\sa \ref concepts::Path "Path concept"
 		*/
 		/**
 		@defgroup heaps Heap Structures
 		@ingroup datas
 		\brief %Heap structures implemented in LEMON.
 		This group contains the heap structures implemented in LEMON.
 		LEMON provides several heap classes. They are efficient implementations
 		of the abstract data type \e priority \e queue. They store items with
 		specified values called \e priorities in such a way that finding and
 		removing the item with minimum priority are efficient.
 		The basic operations are adding and erasing items, changing the priority
 		of an item, etc.
 		Heaps are crucial in several algorithms, such as Dijkstra and Prim.
 		The heap implementations have the same interface, thus any of them can be
 		used easily in such algorithms.
 		\sa \ref concepts::Heap "Heap concept"
 		*/
 		/**
 		@defgroup matrices Matrices
 		@ingroup datas
 		\brief Two dimensional data storages implemented in LEMON.
 		This group contains two dimensional data storages implemented in LEMON.
 		*/
 		/**
 		@defgroup auxdat Auxiliary Data Structures
 		@ingroup datas
 		\brief Auxiliary data structures implemented in LEMON.
 		This group contains some data structures implemented in LEMON in
 		order to make it easier to implement combinatorial algorithms.
 		*/
 		/**
 		@defgroup algs Algorithms
 		\brief This group contains the several algorithms
 		implemented in LEMON.
 		This group contains the several algorithms
 		implemented in LEMON.
 		*/
 		/**
 		@defgroup search Graph Search
 		@ingroup algs
 		\brief Common graph search algorithms.
 		This group contains the common graph search algorithms, namely
 		\e breadth-first \e search (BFS) and \e depth-first \e search (DFS).
 		*/
 		/**
 		@defgroup shortest_path Shortest Path Algorithms
 		@ingroup algs
 		\brief Algorithms for finding shortest paths.
 		This group contains the algorithms for finding shortest paths in digraphs.
 		 - \ref Dijkstra algorithm for finding shortest paths from a source node
 		   when all arc lengths are non-negative.
 		 - \ref BellmanFord "Bellman-Ford" algorithm for finding shortest paths
 		   from a source node when arc lenghts can be either positive or negative,
 		   but the digraph should not contain directed cycles with negative total
 		   length.
 		 - \ref FloydWarshall "Floyd-Warshall" and \ref Johnson "Johnson" algorithms
 		   for solving the \e all-pairs \e shortest \e paths \e problem when arc
 		   lenghts can be either positive or negative, but the digraph should
 		   not contain directed cycles with negative total length.
 		 - \ref Suurballe A successive shortest path algorithm for finding
 		   arc-disjoint paths between two nodes having minimum total length.
 		*/
 		/**
 		@defgroup max_flow Maximum Flow Algorithms
 		@ingroup algs
 		\brief Algorithms for finding maximum flows.
 		This group contains the algorithms for finding maximum flows and
 		feasible circulations.
 		The \e maximum \e flow \e problem is to find a flow of maximum value between
 		a single source and a single target. Formally, there is a \f$G=(V,A)\f$
 		digraph, a \f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function and
 		\f$s, t \in V\f$ source and target nodes.
 		A maximum flow is an \f$f: A\rightarrow\mathbf{R}^+_0\f$ solution of the
 		following optimization problem.
 		\f[ \max\sum_{sv\in A} f(sv) - \sum_{vs\in A} f(vs) \f]
 		\f[ \sum_{uv\in A} f(uv) = \sum_{vu\in A} f(vu)
 		    \quad \forall u\in V\setminus\{s,t\} \f]
 		\f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f]
 		LEMON contains several algorithms for solving maximum flow problems:
 		- \ref EdmondsKarp Edmonds-Karp algorithm.
 		- \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm.
 		- \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees.
 		- \ref GoldbergTarjan Preflow push-relabel algorithm with dynamic trees.
 		In most cases the \ref Preflow "Preflow" algorithm provides the
 		fastest method for computing a maximum flow. All implementations
 		also provide functions to query the minimum cut, which is the dual
 		problem of maximum flow.
 		\ref Circulation is a preflow push-relabel algorithm implemented directly
 		for finding feasible circulations, which is a somewhat different problem,
 		but it is strongly related to maximum flow.
 		For more information, see \ref Circulation.
 		*/
 		/**
 		@defgroup min_cost_flow_algs Minimum Cost Flow Algorithms
 		@ingroup algs
 		\brief Algorithms for finding minimum cost flows and circulations.
 		This group contains the algorithms for finding minimum cost flows and
 		circulations. For more information about this problem and its dual
 		solution see \ref min_cost_flow "Minimum Cost Flow Problem".
 		LEMON contains several algorithms for this problem.
 		 - \ref NetworkSimplex Primal Network Simplex algorithm with various
 		   pivot strategies.
 		 - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on
 		   cost scaling.
 		 - \ref CapacityScaling Successive Shortest %Path algorithm with optional
 		   capacity scaling.
 		 - \ref CancelAndTighten The Cancel and Tighten algorithm.
 		 - \ref CycleCanceling Cycle-Canceling algorithms.
 		In general NetworkSimplex is the most efficient implementation,
 		but in special cases other algorithms could be faster.
 		For example, if the total supply and/or capacities are rather small,
 		CapacityScaling is usually the fastest algorithm (without effective scaling).
 		*/
 		/**
 		@defgroup min_cut Minimum Cut Algorithms
 		@ingroup algs
 		\brief Algorithms for finding minimum cut in graphs.
 		This group contains the algorithms for finding minimum cut in graphs.
 		The \e minimum \e cut \e problem is to find a non-empty and non-complete
 		\f$X\f$ subset of the nodes with minimum overall capacity on
 		outgoing arcs. Formally, there is a \f$G=(V,A)\f$ digraph, a
 		\f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum
 		cut is the \f$X\f$ solution of the next optimization problem:
 		\f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}
 		    \sum_{uv\in A, u\in X, v\not\in X}cap(uv) \f]
 		LEMON contains several algorithms related to minimum cut problems:
 		- \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut
 		  in directed graphs.
 		- \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for
 		  calculating minimum cut in undirected graphs.
 		- \ref GomoryHu "Gomory-Hu tree computation" for calculating
 		  all-pairs minimum cut in undirected graphs.
 		If you want to find minimum cut just between two distinict nodes,
 		see the \ref max_flow "maximum flow problem".
 		*/
 		/**
 		@defgroup graph_properties Connectivity and Other Graph Properties
 		@ingroup algs
 		\brief Algorithms for discovering the graph properties
 		This group contains the algorithms for discovering the graph properties
 		like connectivity, bipartiteness, euler property, simplicity etc.
 		\image html edge_biconnected_components.png
 		\image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
 		*/
 		/**
 		@defgroup planar Planarity Embedding and Drawing
 		@ingroup algs
 		\brief Algorithms for planarity checking, embedding and drawing
 		This group contains the algorithms for planarity checking,
 		embedding and drawing.
 		\image html planar.png
 		\image latex planar.eps "Plane graph" width=\textwidth
 		*/
 		/**
 		@defgroup matching Matching Algorithms
 		@ingroup algs
 		\brief Algorithms for finding matchings in graphs and bipartite graphs.
 		This group contains the algorithms for calculating
 		matchings in graphs and bipartite graphs. The general matching problem is
 		finding a subset of the edges for which each node has at most one incident
 		edge.
 		There are several different algorithms for calculate matchings in
 		graphs.  The matching problems in bipartite graphs are generally
 		easier than in general graphs. The goal of the matching optimization
 		can be finding maximum cardinality, maximum weight or minimum cost
 		matching. The search can be constrained to find perfect or
 		maximum cardinality matching.
 		The matching algorithms implemented in LEMON:
 		- \ref MaxBipartiteMatching Hopcroft-Karp augmenting path algorithm
 		  for calculating maximum cardinality matching in bipartite graphs.
 		- \ref PrBipartiteMatching Push-relabel algorithm
 		  for calculating maximum cardinality matching in bipartite graphs.
 		- \ref MaxWeightedBipartiteMatching
 		  Successive shortest path algorithm for calculating maximum weighted
 		  matching and maximum weighted bipartite matching in bipartite graphs.
 		- \ref MinCostMaxBipartiteMatching
 		  Successive shortest path algorithm for calculating minimum cost maximum
 		  matching in bipartite graphs.
 		- \ref MaxMatching Edmond's blossom shrinking algorithm for calculating
 		  maximum cardinality matching in general graphs.
 		- \ref MaxWeightedMatching Edmond's blossom shrinking algorithm for calculating
 		  maximum weighted matching in general graphs.
 		- \ref MaxWeightedPerfectMatching
 		  Edmond's blossom shrinking algorithm for calculating maximum weighted
 		  perfect matching in general graphs.
 		\image html bipartite_matching.png
 		\image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth
 		*/
 		/**
 		@defgroup spantree Minimum Spanning Tree Algorithms
 		@ingroup algs
 		\brief Algorithms for finding minimum cost spanning trees and arborescences.
 		This group contains the algorithms for finding minimum cost spanning
 		trees and arborescences.
 		*/
 		/**
 		@defgroup auxalg Auxiliary Algorithms
 		@ingroup algs
 		\brief Auxiliary algorithms implemented in LEMON.
 		This group contains some algorithms implemented in LEMON
 		in order to make it easier to implement complex algorithms.
 		*/
 		/**
 		@defgroup approx Approximation Algorithms
 		@ingroup algs
 		\brief Approximation algorithms.
 		This group contains the approximation and heuristic algorithms
 		implemented in LEMON.
 		*/
 		/**
 		@defgroup gen_opt_group General Optimization Tools
 		\brief This group contains some general optimization frameworks
 		implemented in LEMON.
 		This group contains some general optimization frameworks
 		implemented in LEMON.
 		*/
 		/**
 		@defgroup lp_group Lp and Mip Solvers
 		@ingroup gen_opt_group
 		\brief Lp and Mip solver interfaces for LEMON.
 		This group contains Lp and Mip solver interfaces for LEMON. The
 		various LP solvers could be used in the same manner with this
 		interface.
 		*/
 		/**
 		@defgroup lp_utils Tools for Lp and Mip Solvers
 		@ingroup lp_group
 		\brief Helper tools to the Lp and Mip solvers.
 		This group adds some helper tools to general optimization framework
 		implemented in LEMON.
 		*/
 		/**
 		@defgroup metah Metaheuristics
 		@ingroup gen_opt_group
 		\brief Metaheuristics for LEMON library.
 		This group contains some metaheuristic optimization tools.
 		*/
 		/**
 		@defgroup utils Tools and Utilities
 		\brief Tools and utilities for programming in LEMON
 		Tools and utilities for programming in LEMON.
 		*/
 		/**
 		@defgroup gutils Basic Graph Utilities
 		@ingroup utils
 		\brief Simple basic graph utilities.
 		This group contains some simple basic graph utilities.
 		*/
 		/**
 		@defgroup misc Miscellaneous Tools
 		@ingroup utils
 		\brief Tools for development, debugging and testing.
 		This group contains several useful tools for development,
 		debugging and testing.
 		*/
 		/**
 		@defgroup timecount Time Measuring and Counting
 		@ingroup misc
 		\brief Simple tools for measuring the performance of algorithms.
 		This group contains simple tools for measuring the performance
 		of algorithms.
 		*/
 		/**
 		@defgroup exceptions Exceptions
 		@ingroup utils
 		\brief Exceptions defined in LEMON.
 		This group contains the exceptions defined in LEMON.
 		*/
 		/**
 		@defgroup io_group Input-Output
 		\brief Graph Input-Output methods
 		This group contains the tools for importing and exporting graphs
 		and graph related data. Now it supports the \ref lgf-format
 		"LEMON Graph Format", the \c DIMACS format and the encapsulated
 		postscript (EPS) format.
 		*/
 		/**
 		@defgroup lemon_io LEMON Graph Format
 		@ingroup io_group
 		\brief Reading and writing LEMON Graph Format.
 		This group contains methods for reading and writing
 		\ref lgf-format "LEMON Graph Format".
 		*/
 		/**
 		@defgroup eps_io Postscript Exporting
 		@ingroup io_group
 		\brief General \c EPS drawer and graph exporter
 		This group contains general \c EPS drawing methods and special
 		graph exporting tools.
 		*/
 		/**
 		@defgroup dimacs_group DIMACS format
 		@ingroup io_group
 		\brief Read and write files in DIMACS format
 		Tools to read a digraph from or write it to a file in DIMACS format data.
 		*/
 		/**
 		@defgroup nauty_group NAUTY Format
 		@ingroup io_group
 		\brief Read \e Nauty format
 		Tool to read graphs from \e Nauty format data.
 		*/
 		/**
 		@defgroup concept Concepts
 		\brief Skeleton classes and concept checking classes
 		This group contains the data/algorithm skeletons and concept checking
 		classes implemented in LEMON.
 		The purpose of the classes in this group is fourfold.
 		- These classes contain the documentations of the %concepts. In order
 		  to avoid document multiplications, an implementation of a concept
 		  simply refers to the corresponding concept class.
 		- These classes declare every functions, <tt>typedef</tt>s etc. an
 		  implementation of the %concepts should provide, however completely
 		  without implementations and real data structures behind the
 		  interface. On the other hand they should provide nothing else. All
 		  the algorithms working on a data structure meeting a certain concept
 		  should compile with these classes. (Though it will not run properly,
 		  of course.) In this way it is easily to check if an algorithm
 		  doesn't use any extra feature of a certain implementation.
 		- The concept descriptor classes also provide a <em>checker class</em>
 		  that makes it possible to check whether a certain implementation of a
 		  concept indeed provides all the required features.
 		- Finally, They can serve as a skeleton of a new implementation of a concept.
 		*/
 		/**
 		@defgroup graph_concepts Graph Structure Concepts
 		@ingroup concept
 		\brief Skeleton and concept checking classes for graph structures
 		This group contains the skeletons and concept checking classes of LEMON's
 		graph structures and helper classes used to implement these.
 		*/
 		/**
 		@defgroup map_concepts Map Concepts
 		@ingroup concept
 		\brief Skeleton and concept checking classes for maps
 		This group contains the skeletons and concept checking classes of maps.
 		*/
 		/**
 		\anchor demoprograms
 		@defgroup demos Demo Programs
 		Some demo programs are listed here. Their full source codes can be found in
 		the \c demo subdirectory of the source tree.
 		In order to compile them, use the <tt>make demo</tt> or the
 		<tt>make check</tt> commands.
 		*/
 		/**
 		@defgroup tools Standalone Utility Applications
 		Some utility applications are listed here.
 		The standard compilation procedure (<tt>./configure;make</tt>) will compile
 		them, as well.
 		*/
+		}

lemon/bin_heap.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2009
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_BIN_HEAP_H
 		#define LEMON_BIN_HEAP_H
-		///\ingroup auxdat
+		///\ingroup heaps
 		///\file
 		///\brief Binary heap implementation.
 		#include <vector>
 		#include <utility>
 		#include <functional>
 		namespace lemon {
-		  /// \ingroup auxdat
+		  /// \ingroup heaps
 		  ///
 		  /// \brief Binary heap data structure.
 		  ///
 		  /// This class implements the \e binary \e heap data structure.
 		  /// It fully conforms to the \ref concepts::Heap "heap concept".
 		  ///
 		  /// \tparam PR Type of the priorities of the items.
 		  /// \tparam IM A read-writable item map with \c int values, used
 		  /// internally to handle the cross references.
 		  /// \tparam CMP A functor class for comparing the priorities.
 		  /// The default is \c std::less<PR>.
 		#ifdef DOXYGEN
 		  template <typename PR, typename IM, typename CMP>
 		#else
 		  template <typename PR, typename IM, typename CMP = std::less<PR> >
 		#endif
 		  class BinHeap {
 		  public:
 		    /// Type of the item-int map.
 		    typedef IM ItemIntMap;
 		    /// Type of the priorities.
 		    typedef PR Prio;
 		    /// Type of the items stored in the heap.
 		    typedef typename ItemIntMap::Key Item;
 		    /// Type of the item-priority pairs.
 		    typedef std::pair<Item,Prio> Pair;
 		    /// Functor type for comparing the priorities.
 		    typedef CMP Compare;
 		    /// \brief Type to represent the states of the items.
 		    ///
 		    /// Each item has a state associated to it. It can be "in heap",
 		    /// "pre-heap" or "post-heap". The latter two are indifferent from the
 		    /// heap's point of view, but may be useful to the user.
 		    ///
 		    /// The item-int map must be initialized in such way that it assigns
 		    /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
 		    enum State {
 		      IN_HEAP = 0,    ///< = 0.
 		      PRE_HEAP = -1,  ///< = -1.
 		      POST_HEAP = -2  ///< = -2.
 		    };
 		  private:
 		    std::vector<Pair> _data;
 		    Compare _comp;
 		    ItemIntMap &_iim;
 		  public:
 		    /// \brief Constructor.
 		    ///
 		    /// Constructor.
 		    /// \param map A map that assigns \c int values to the items.
 		    /// It is used internally to handle the cross references.
 		    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
 		    explicit BinHeap(ItemIntMap &map) : _iim(map) {}
 		    /// \brief Constructor.
 		    ///
 		    /// Constructor.
 		    /// \param map A map that assigns \c int values to the items.
 		    /// It is used internally to handle the cross references.
 		    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
 		    /// \param comp The function object used for comparing the priorities.
 		    BinHeap(ItemIntMap &map, const Compare &comp)
 		      : _iim(map), _comp(comp) {}
 		    /// \brief The number of items stored in the heap.
 		    ///
 		    /// This function returns the number of items stored in the heap.
 		    int size() const { return _data.size(); }
 		    /// \brief Check if the heap is empty.
 		    ///
 		    /// This function returns \c true if the heap is empty.
 		    bool empty() const { return _data.empty(); }
 		    /// \brief Make the heap empty.
 		    ///
 		    /// This functon makes the heap empty.
 		    /// It does not change the cross reference map. If you want to reuse
 		    /// a heap that is not surely empty, you should first clear it and
 		    /// then you should set the cross reference map to \c PRE_HEAP
 		    /// for each item.
 		    void clear() {
 		      _data.clear();
+		    }
 		  private:
 		    static int parent(int i) { return (i-1)/2; }
 		    static int second_child(int i) { return 2*i+2; }
 		    bool less(const Pair &p1, const Pair &p2) const {
 		      return _comp(p1.second, p2.second);
+		    }
 		    int bubble_up(int hole, Pair p) {
 		      int par = parent(hole);
 		      while( hole>0 && less(p,_data[par]) ) {
 		        move(_data[par],hole);
 		        hole = par;
 		        par = parent(hole);
+		      }
 		      move(p, hole);
 		      return hole;
+		    }
 		    int bubble_down(int hole, Pair p, int length) {
 		      int child = second_child(hole);
 		      while(child < length) {
 		        if( less(_data[child-1], _data[child]) ) {
 		          --child;
+		        }
 		        if( !less(_data[child], p) )
 		          goto ok;
 		        move(_data[child], hole);
 		        hole = child;
 		        child = second_child(hole);
+		      }
 		      child--;
 		      if( child<length && less(_data[child], p) ) {
 		        move(_data[child], hole);
 		        hole=child;
+		      }
 		    ok:
 		      move(p, hole);
 		      return hole;
+		    }
 		    void move(const Pair &p, int i) {
 		      _data[i] = p;
 		      _iim.set(p.first, i);
+		    }
 		  public:
 		    /// \brief Insert a pair of item and priority into the heap.
 		    ///
 		    /// This function inserts \c p.first to the heap with priority
 		    /// \c p.second.
 		    /// \param p The pair to insert.
 		    /// \pre \c p.first must not be stored in the heap.
 		    void push(const Pair &p) {
 		      int n = _data.size();
 		      _data.resize(n+1);
 		      bubble_up(n, p);
+		    }
 		    /// \brief Insert an item into the heap with the given priority.
 		    ///
 		    /// This function inserts the given item into the heap with the
 		    /// given priority.
 		    /// \param i The item to insert.
 		    /// \param p The priority of the item.
 		    /// \pre \e i must not be stored in the heap.
 		    void push(const Item &i, const Prio &p) { push(Pair(i,p)); }
 		    /// \brief Return the item having minimum priority.
 		    ///
 		    /// This function returns the item having minimum priority.
 		    /// \pre The heap must be non-empty.
 		    Item top() const {
 		      return _data[0].first;
+		    }
 		    /// \brief The minimum priority.
 		    ///
 		    /// This function returns the minimum priority.
 		    /// \pre The heap must be non-empty.
 		    Prio prio() const {
 		      return _data[0].second;
+		    }
 		    /// \brief Remove the item having minimum priority.
 		    ///
 		    /// This function removes the item having minimum priority.
 		    /// \pre The heap must be non-empty.
 		    void pop() {
 		      int n = _data.size()-1;
 		      _iim.set(_data[0].first, POST_HEAP);
 		      if (n > 0) {
 		        bubble_down(0, _data[n], n);
+		      }
 		      _data.pop_back();
+		    }
 		    /// \brief Remove the given item from the heap.
 		    ///
 		    /// This function removes the given item from the heap if it is
 		    /// already stored.
 		    /// \param i The item to delete.
 		    /// \pre \e i must be in the heap.
 		    void erase(const Item &i) {
 		      int h = _iim[i];
 		      int n = _data.size()-1;
 		      _iim.set(_data[h].first, POST_HEAP);
 		      if( h < n ) {
 		        if ( bubble_up(h, _data[n]) == h) {
 		          bubble_down(h, _data[n], n);
+		        }
+		      }
 		      _data.pop_back();
+		    }
 		    /// \brief The priority of the given item.
 		    ///
 		    /// This function returns the priority of the given item.
 		    /// \param i The item.
 		    /// \pre \e i must be in the heap.
 		    Prio operator[](const Item &i) const {
 		      int idx = _iim[i];
 		      return _data[idx].second;
+		    }
 		    /// \brief Set the priority of an item or insert it, if it is
 		    /// not stored in the heap.
 		    ///
 		    /// This method sets the priority of the given item if it is
 		    /// already stored in the heap. Otherwise it inserts the given
 		    /// item into the heap with the given priority.
 		    /// \param i The item.
 		    /// \param p The priority.
 		    void set(const Item &i, const Prio &p) {
 		      int idx = _iim[i];
 		      if( idx < 0 ) {
 		        push(i,p);
+		      }
 		      else if( _comp(p, _data[idx].second) ) {
 		        bubble_up(idx, Pair(i,p));
+		      }
 		      else {
 		        bubble_down(idx, Pair(i,p), _data.size());
+		      }
+		    }
 		    /// \brief Decrease the priority of an item to the given value.
 		    ///
 		    /// This function decreases the priority of an item to the given value.
 		    /// \param i The item.
 		    /// \param p The priority.
 		    /// \pre \e i must be stored in the heap with priority at least \e p.
 		    void decrease(const Item &i, const Prio &p) {
 		      int idx = _iim[i];
 		      bubble_up(idx, Pair(i,p));
+		    }
 		    /// \brief Increase the priority of an item to the given value.
 		    ///
 		    /// This function increases the priority of an item to the given value.
 		    /// \param i The item.
 		    /// \param p The priority.
 		    /// \pre \e i must be stored in the heap with priority at most \e p.
 		    void increase(const Item &i, const Prio &p) {
 		      int idx = _iim[i];
 		      bubble_down(idx, Pair(i,p), _data.size());
+		    }
 		    /// \brief Return the state of an item.
 		    ///
 		    /// This method returns \c PRE_HEAP if the given item has never
 		    /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
 		    /// and \c POST_HEAP otherwise.
 		    /// In the latter case it is possible that the item will get back
 		    /// to the heap again.
 		    /// \param i The item.
 		    State state(const Item &i) const {
 		      int s = _iim[i];
 		      if( s>=0 )
 		        s=0;
 		      return State(s);
+		    }
 		    /// \brief Set the state of an item in the heap.
 		    ///
 		    /// This function sets the state of the given item in the heap.
 		    /// It can be used to manually clear the heap when it is important
 		    /// to achive better time complexity.
 		    /// \param i The item.
 		    /// \param st The state. It should not be \c IN_HEAP.
 		    void state(const Item& i, State st) {
 		      switch (st) {
 		      case POST_HEAP:
 		      case PRE_HEAP:
 		        if (state(i) == IN_HEAP) {
 		          erase(i);
+		        }
 		        _iim[i] = st;
 		        break;
 		      case IN_HEAP:
 		        break;
+		      }
+		    }
 		    /// \brief Replace an item in the heap.
 		    ///
 		    /// This function replaces item \c i with item \c j.
 		    /// Item \c i must be in the heap, while \c j must be out of the heap.
 		    /// After calling this method, item \c i will be out of the
 		    /// heap and \c j will be in the heap with the same prioriority
 		    /// as item \c i had before.
 		    void replace(const Item& i, const Item& j) {
 		      int idx = _iim[i];
 		      _iim.set(i, _iim[j]);
 		      _iim.set(j, idx);
 		      _data[idx].first = j;
+		    }
 		  }; // class BinHeap
 		} // namespace lemon
 		#endif // LEMON_BIN_HEAP_H

lemon/bucket_heap.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2009
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_BUCKET_HEAP_H
 		#define LEMON_BUCKET_HEAP_H
-		///\ingroup auxdat
+		///\ingroup heaps
 		///\file
 		///\brief Bucket heap implementation.
 		#include <vector>
 		#include <utility>
 		#include <functional>
 		namespace lemon {
 		  namespace _bucket_heap_bits {
 		    template <bool MIN>
 		    struct DirectionTraits {
 		      static bool less(int left, int right) {
 		        return left < right;
+		      }
 		      static void increase(int& value) {
 		        ++value;
+		      }
 		    };
 		    template <>
 		    struct DirectionTraits<false> {
 		      static bool less(int left, int right) {
 		        return left > right;
+		      }
 		      static void increase(int& value) {
 		        --value;
+		      }
 		    };
+		  }
-		  /// \ingroup auxdat
+		  /// \ingroup heaps
 		  ///
 		  /// \brief Bucket heap data structure.
 		  ///
 		  /// This class implements the \e bucket \e heap data structure.
 		  /// It practically conforms to the \ref concepts::Heap "heap concept",
 		  /// but it has some limitations.
 		  ///
 		  /// The bucket heap is a very simple structure. It can store only
 		  /// \c int priorities and it maintains a list of items for each priority
 		  /// in the range <tt>[0..C)</tt>. So it should only be used when the
 		  /// priorities are small. It is not intended to use as a Dijkstra heap.
 		  ///
 		  /// \tparam IM A read-writable item map with \c int values, used
 		  /// internally to handle the cross references.
 		  /// \tparam MIN Indicate if the heap is a \e min-heap or a \e max-heap.
 		  /// The default is \e min-heap. If this parameter is set to \c false,
 		  /// then the comparison is reversed, so the top(), prio() and pop()
 		  /// functions deal with the item having maximum priority instead of the
 		  /// minimum.
 		  ///
 		  /// \sa SimpleBucketHeap
 		  template <typename IM, bool MIN = true>
 		  class BucketHeap {
 		  public:
 		    /// Type of the item-int map.
 		    typedef IM ItemIntMap;
 		    /// Type of the priorities.
 		    typedef int Prio;
 		    /// Type of the items stored in the heap.
 		    typedef typename ItemIntMap::Key Item;
 		    /// Type of the item-priority pairs.
 		    typedef std::pair<Item,Prio> Pair;
 		  private:
 		    typedef _bucket_heap_bits::DirectionTraits<MIN> Direction;
 		  public:
 		    /// \brief Type to represent the states of the items.
 		    ///
 		    /// Each item has a state associated to it. It can be "in heap",
 		    /// "pre-heap" or "post-heap". The latter two are indifferent from the
 		    /// heap's point of view, but may be useful to the user.
 		    ///
 		    /// The item-int map must be initialized in such way that it assigns
 		    /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
 		    enum State {
 		      IN_HEAP = 0,    ///< = 0.
 		      PRE_HEAP = -1,  ///< = -1.
 		      POST_HEAP = -2  ///< = -2.
 		    };
 		  public:
 		    /// \brief Constructor.
 		    ///
 		    /// Constructor.
 		    /// \param map A map that assigns \c int values to the items.
 		    /// It is used internally to handle the cross references.
 		    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
 		    explicit BucketHeap(ItemIntMap &map) : _iim(map), _minimum(0) {}
 		    /// \brief The number of items stored in the heap.
 		    ///
 		    /// This function returns the number of items stored in the heap.
 		    int size() const { return _data.size(); }
 		    /// \brief Check if the heap is empty.
 		    ///
 		    /// This function returns \c true if the heap is empty.
 		    bool empty() const { return _data.empty(); }
 		    /// \brief Make the heap empty.
 		    ///
 		    /// This functon makes the heap empty.
 		    /// It does not change the cross reference map. If you want to reuse
 		    /// a heap that is not surely empty, you should first clear it and
 		    /// then you should set the cross reference map to \c PRE_HEAP
 		    /// for each item.
 		    void clear() {
 		      _data.clear(); _first.clear(); _minimum = 0;
+		    }
 		  private:
 		    void relocate_last(int idx) {
 		      if (idx + 1 < int(_data.size())) {
 		        _data[idx] = _data.back();
 		        if (_data[idx].prev != -1) {
 		          _data[_data[idx].prev].next = idx;
 		        } else {
 		          _first[_data[idx].value] = idx;
+		        }
 		        if (_data[idx].next != -1) {
 		          _data[_data[idx].next].prev = idx;
+		        }
 		        _iim[_data[idx].item] = idx;
+		      }
 		      _data.pop_back();
+		    }
 		    void unlace(int idx) {
 		      if (_data[idx].prev != -1) {
 		        _data[_data[idx].prev].next = _data[idx].next;
 		      } else {
 		        _first[_data[idx].value] = _data[idx].next;
+		      }
 		      if (_data[idx].next != -1) {
 		        _data[_data[idx].next].prev = _data[idx].prev;
+		      }
+		    }
 		    void lace(int idx) {
 		      if (int(_first.size()) <= _data[idx].value) {
 		        _first.resize(_data[idx].value + 1, -1);
+		      }
 		      _data[idx].next = _first[_data[idx].value];
 		      if (_data[idx].next != -1) {
 		        _data[_data[idx].next].prev = idx;
+		      }
 		      _first[_data[idx].value] = idx;
 		      _data[idx].prev = -1;
+		    }
 		  public:
 		    /// \brief Insert a pair of item and priority into the heap.
 		    ///
 		    /// This function inserts \c p.first to the heap with priority
 		    /// \c p.second.
 		    /// \param p The pair to insert.
 		    /// \pre \c p.first must not be stored in the heap.
 		    void push(const Pair& p) {
 		      push(p.first, p.second);
+		    }
 		    /// \brief Insert an item into the heap with the given priority.
 		    ///
 		    /// This function inserts the given item into the heap with the
 		    /// given priority.
 		    /// \param i The item to insert.
 		    /// \param p The priority of the item.
 		    /// \pre \e i must not be stored in the heap.
 		    void push(const Item &i, const Prio &p) {
 		      int idx = _data.size();
 		      _iim[i] = idx;
 		      _data.push_back(BucketItem(i, p));
 		      lace(idx);
 		      if (Direction::less(p, _minimum)) {
 		        _minimum = p;
+		      }
+		    }
 		    /// \brief Return the item having minimum priority.
 		    ///
 		    /// This function returns the item having minimum priority.
 		    /// \pre The heap must be non-empty.
 		    Item top() const {
 		      while (_first[_minimum] == -1) {
 		        Direction::increase(_minimum);
+		      }
 		      return _data[_first[_minimum]].item;
+		    }
 		    /// \brief The minimum priority.
 		    ///
 		    /// This function returns the minimum priority.
 		    /// \pre The heap must be non-empty.
 		    Prio prio() const {
 		      while (_first[_minimum] == -1) {
 		        Direction::increase(_minimum);
+		      }
 		      return _minimum;
+		    }
 		    /// \brief Remove the item having minimum priority.
 		    ///
 		    /// This function removes the item having minimum priority.
 		    /// \pre The heap must be non-empty.
 		    void pop() {
 		      while (_first[_minimum] == -1) {
 		        Direction::increase(_minimum);
+		      }
 		      int idx = _first[_minimum];
 		      _iim[_data[idx].item] = -2;
 		      unlace(idx);
 		      relocate_last(idx);
+		    }
 		    /// \brief Remove the given item from the heap.
 		    ///
 		    /// This function removes the given item from the heap if it is
 		    /// already stored.
 		    /// \param i The item to delete.
 		    /// \pre \e i must be in the heap.
 		    void erase(const Item &i) {
 		      int idx = _iim[i];
 		      _iim[_data[idx].item] = -2;
 		      unlace(idx);
 		      relocate_last(idx);
+		    }
 		    /// \brief The priority of the given item.
 		    ///
 		    /// This function returns the priority of the given item.
 		    /// \param i The item.
 		    /// \pre \e i must be in the heap.
 		    Prio operator[](const Item &i) const {
 		      int idx = _iim[i];
 		      return _data[idx].value;
+		    }
 		    /// \brief Set the priority of an item or insert it, if it is
 		    /// not stored in the heap.
 		    ///
 		    /// This method sets the priority of the given item if it is
 		    /// already stored in the heap. Otherwise it inserts the given
 		    /// item into the heap with the given priority.
 		    /// \param i The item.
 		    /// \param p The priority.
 		    void set(const Item &i, const Prio &p) {
 		      int idx = _iim[i];
 		      if (idx < 0) {
 		        push(i, p);
 		      } else if (Direction::less(p, _data[idx].value)) {
 		        decrease(i, p);
 		      } else {
 		        increase(i, p);
+		      }
+		    }
 		    /// \brief Decrease the priority of an item to the given value.
 		    ///
 		    /// This function decreases the priority of an item to the given value.
 		    /// \param i The item.
 		    /// \param p The priority.
 		    /// \pre \e i must be stored in the heap with priority at least \e p.
 		    void decrease(const Item &i, const Prio &p) {
 		      int idx = _iim[i];
 		      unlace(idx);
 		      _data[idx].value = p;
 		      if (Direction::less(p, _minimum)) {
 		        _minimum = p;
+		      }
 		      lace(idx);
+		    }
 		    /// \brief Increase the priority of an item to the given value.
 		    ///
 		    /// This function increases the priority of an item to the given value.
 		    /// \param i The item.
 		    /// \param p The priority.
 		    /// \pre \e i must be stored in the heap with priority at most \e p.
 		    void increase(const Item &i, const Prio &p) {
 		      int idx = _iim[i];
 		      unlace(idx);
 		      _data[idx].value = p;
 		      lace(idx);
+		    }
 		    /// \brief Return the state of an item.
 		    ///
 		    /// This method returns \c PRE_HEAP if the given item has never
 		    /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
 		    /// and \c POST_HEAP otherwise.
 		    /// In the latter case it is possible that the item will get back
 		    /// to the heap again.
 		    /// \param i The item.
 		    State state(const Item &i) const {
 		      int idx = _iim[i];
 		      if (idx >= 0) idx = 0;
 		      return State(idx);
+		    }
 		    /// \brief Set the state of an item in the heap.
 		    ///
 		    /// This function sets the state of the given item in the heap.
 		    /// It can be used to manually clear the heap when it is important
 		    /// to achive better time complexity.
 		    /// \param i The item.
 		    /// \param st The state. It should not be \c IN_HEAP.
 		    void state(const Item& i, State st) {
 		      switch (st) {
 		      case POST_HEAP:
 		      case PRE_HEAP:
 		        if (state(i) == IN_HEAP) {
 		          erase(i);
+		        }
 		        _iim[i] = st;
 		        break;
 		      case IN_HEAP:
 		        break;
+		      }
+		    }
 		  private:
 		    struct BucketItem {
 		      BucketItem(const Item& _item, int _value)
 		        : item(_item), value(_value) {}
 		      Item item;
 		      int value;
 		      int prev, next;
 		    };
 		    ItemIntMap& _iim;
 		    std::vector<int> _first;
 		    std::vector<BucketItem> _data;
 		    mutable int _minimum;
 		  }; // class BucketHeap
-		  /// \ingroup auxdat
+		  /// \ingroup heaps
 		  ///
 		  /// \brief Simplified bucket heap data structure.
 		  ///
 		  /// This class implements a simplified \e bucket \e heap data
 		  /// structure. It does not provide some functionality, but it is
 		  /// faster and simpler than BucketHeap. The main difference is
 		  /// that BucketHeap stores a doubly-linked list for each key while
 		  /// this class stores only simply-linked lists. It supports erasing
 		  /// only for the item having minimum priority and it does not support
 		  /// key increasing and decreasing.
 		  ///
 		  /// Note that this implementation does not conform to the
 		  /// \ref concepts::Heap "heap concept" due to the lack of some
 		  /// functionality.
 		  ///
 		  /// \tparam IM A read-writable item map with \c int values, used
 		  /// internally to handle the cross references.
 		  /// \tparam MIN Indicate if the heap is a \e min-heap or a \e max-heap.
 		  /// The default is \e min-heap. If this parameter is set to \c false,
 		  /// then the comparison is reversed, so the top(), prio() and pop()
 		  /// functions deal with the item having maximum priority instead of the
 		  /// minimum.
 		  ///
 		  /// \sa BucketHeap
 		  template <typename IM, bool MIN = true >
 		  class SimpleBucketHeap {
 		  public:
 		    /// Type of the item-int map.
 		    typedef IM ItemIntMap;
 		    /// Type of the priorities.
 		    typedef int Prio;
 		    /// Type of the items stored in the heap.
 		    typedef typename ItemIntMap::Key Item;
 		    /// Type of the item-priority pairs.
 		    typedef std::pair<Item,Prio> Pair;
 		  private:
 		    typedef _bucket_heap_bits::DirectionTraits<MIN> Direction;
 		  public:
 		    /// \brief Type to represent the states of the items.
 		    ///
 		    /// Each item has a state associated to it. It can be "in heap",
 		    /// "pre-heap" or "post-heap". The latter two are indifferent from the
 		    /// heap's point of view, but may be useful to the user.
 		    ///
 		    /// The item-int map must be initialized in such way that it assigns
 		    /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
 		    enum State {
 		      IN_HEAP = 0,    ///< = 0.
 		      PRE_HEAP = -1,  ///< = -1.
 		      POST_HEAP = -2  ///< = -2.
 		    };
 		  public:
 		    /// \brief Constructor.
 		    ///
 		    /// Constructor.
 		    /// \param map A map that assigns \c int values to the items.
 		    /// It is used internally to handle the cross references.
 		    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
 		    explicit SimpleBucketHeap(ItemIntMap &map)
 		      : _iim(map), _free(-1), _num(0), _minimum(0) {}
 		    /// \brief The number of items stored in the heap.
 		    ///
 		    /// This function returns the number of items stored in the heap.
 		    int size() const { return _num; }
 		    /// \brief Check if the heap is empty.
 		    ///
 		    /// This function returns \c true if the heap is empty.
 		    bool empty() const { return _num == 0; }
 		    /// \brief Make the heap empty.
 		    ///
 		    /// This functon makes the heap empty.
 		    /// It does not change the cross reference map. If you want to reuse
 		    /// a heap that is not surely empty, you should first clear it and
 		    /// then you should set the cross reference map to \c PRE_HEAP
 		    /// for each item.
 		    void clear() {
 		      _data.clear(); _first.clear(); _free = -1; _num = 0; _minimum = 0;
+		    }
 		    /// \brief Insert a pair of item and priority into the heap.
 		    ///
 		    /// This function inserts \c p.first to the heap with priority
 		    /// \c p.second.
 		    /// \param p The pair to insert.
 		    /// \pre \c p.first must not be stored in the heap.
 		    void push(const Pair& p) {
 		      push(p.first, p.second);
+		    }
 		    /// \brief Insert an item into the heap with the given priority.
 		    ///
 		    /// This function inserts the given item into the heap with the
 		    /// given priority.
 		    /// \param i The item to insert.
 		    /// \param p The priority of the item.
 		    /// \pre \e i must not be stored in the heap.
 		    void push(const Item &i, const Prio &p) {
 		      int idx;
 		      if (_free == -1) {
 		        idx = _data.size();
 		        _data.push_back(BucketItem(i));
 		      } else {
 		        idx = _free;
 		        _free = _data[idx].next;
 		        _data[idx].item = i;
+		      }
 		      _iim[i] = idx;
 		      if (p >= int(_first.size())) _first.resize(p + 1, -1);
 		      _data[idx].next = _first[p];
 		      _first[p] = idx;
 		      if (Direction::less(p, _minimum)) {
 		        _minimum = p;
+		      }
 		      ++_num;
+		    }
 		    /// \brief Return the item having minimum priority.
 		    ///
 		    /// This function returns the item having minimum priority.
 		    /// \pre The heap must be non-empty.
 		    Item top() const {
 		      while (_first[_minimum] == -1) {
 		        Direction::increase(_minimum);
+		      }
 		      return _data[_first[_minimum]].item;
+		    }
 		    /// \brief The minimum priority.
 		    ///
 		    /// This function returns the minimum priority.
 		    /// \pre The heap must be non-empty.
 		    Prio prio() const {
 		      while (_first[_minimum] == -1) {
 		        Direction::increase(_minimum);
+		      }
 		      return _minimum;
+		    }
 		    /// \brief Remove the item having minimum priority.
 		    ///
 		    /// This function removes the item having minimum priority.
 		    /// \pre The heap must be non-empty.
 		    void pop() {
 		      while (_first[_minimum] == -1) {
 		        Direction::increase(_minimum);
+		      }
 		      int idx = _first[_minimum];
 		      _iim[_data[idx].item] = -2;
 		      _first[_minimum] = _data[idx].next;
 		      _data[idx].next = _free;
 		      _free = idx;
 		      --_num;
+		    }
 		    /// \brief The priority of the given item.
 		    ///
 		    /// This function returns the priority of the given item.
 		    /// \param i The item.
 		    /// \pre \e i must be in the heap.
 		    /// \warning This operator is not a constant time function because
 		    /// it scans the whole data structure to find the proper value.
 		    Prio operator[](const Item &i) const {
 		      for (int k = 0; k < int(_first.size()); ++k) {
 		        int idx = _first[k];
 		        while (idx != -1) {
 		          if (_data[idx].item == i) {
 		            return k;
+		          }
 		          idx = _data[idx].next;
+		        }
+		      }
 		      return -1;
+		    }
 		    /// \brief Return the state of an item.
 		    ///
 		    /// This method returns \c PRE_HEAP if the given item has never
 		    /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
 		    /// and \c POST_HEAP otherwise.
 		    /// In the latter case it is possible that the item will get back
 		    /// to the heap again.
 		    /// \param i The item.
 		    State state(const Item &i) const {
 		      int idx = _iim[i];
 		      if (idx >= 0) idx = 0;
 		      return State(idx);
+		    }
 		  private:
 		    struct BucketItem {
 		      BucketItem(const Item& _item)
 		        : item(_item) {}
 		      Item item;
 		      int next;
 		    };
 		    ItemIntMap& _iim;
 		    std::vector<int> _first;
 		    std::vector<BucketItem> _data;
 		    int _free, _num;
 		    mutable int _minimum;
 		  }; // class SimpleBucketHeap
+		}
 		#endif

lemon/concepts/heap.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2009
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_CONCEPTS_HEAP_H
 		#define LEMON_CONCEPTS_HEAP_H
 		///\ingroup concept
 		///\file
 		///\brief The concept of heaps.
 		#include <lemon/core.h>
 		#include <lemon/concept_check.h>
 		namespace lemon {
 		  namespace concepts {
 		    /// \addtogroup concept
 		    /// @{
 		    /// \brief The heap concept.
 		    ///
 		    /// This concept class describes the main interface of heaps.
 		    /// The various heap structures are efficient
+		    /// The various \ref heaps "heap structures" are efficient
 		    /// implementations of the abstract data type \e priority \e queue.
 		    /// They store items with specified values called \e priorities
 		    /// in such a way that finding and removing the item with minimum
 		    /// priority are efficient. The basic operations are adding and
 		    /// erasing items, changing the priority of an item, etc.
 		    ///
 		    /// Heaps are crucial in several algorithms, such as Dijkstra and Prim.
 		    /// Any class that conforms to this concept can be used easily in such
 		    /// algorithms.
 		    ///
 		    /// \tparam PR Type of the priorities of the items.
 		    /// \tparam IM A read-writable item map with \c int values, used
 		    /// internally to handle the cross references.
 		    /// \tparam CMP A functor class for comparing the priorities.
 		    /// The default is \c std::less<PR>.
 		#ifdef DOXYGEN
 		    template <typename PR, typename IM, typename CMP>
 		#else
 		    template <typename PR, typename IM, typename CMP = std::less<PR> >
 		#endif
 		    class Heap {
 		    public:
 		      /// Type of the item-int map.
 		      typedef IM ItemIntMap;
 		      /// Type of the priorities.
 		      typedef PR Prio;
 		      /// Type of the items stored in the heap.
 		      typedef typename ItemIntMap::Key Item;
 		      /// \brief Type to represent the states of the items.
 		      ///
 		      /// Each item has a state associated to it. It can be "in heap",
 		      /// "pre-heap" or "post-heap". The latter two are indifferent from the
 		      /// heap's point of view, but may be useful to the user.
 		      ///
 		      /// The item-int map must be initialized in such way that it assigns
 		      /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
 		      enum State {
 		        IN_HEAP = 0,    ///< = 0. The "in heap" state constant.
 		        PRE_HEAP = -1,  ///< = -1. The "pre-heap" state constant.
 		        POST_HEAP = -2  ///< = -2. The "post-heap" state constant.
 		      };
 		      /// \brief Constructor.
 		      ///
 		      /// Constructor.
 		      /// \param map A map that assigns \c int values to keys of type
 		      /// \c Item. It is used internally by the heap implementations to
 		      /// handle the cross references. The assigned value must be
 		      /// \c PRE_HEAP (<tt>-1</tt>) for each item.
 		      explicit Heap(ItemIntMap &map) {}
 		      /// \brief Constructor.
 		      ///
 		      /// Constructor.
 		      /// \param map A map that assigns \c int values to keys of type
 		      /// \c Item. It is used internally by the heap implementations to
 		      /// handle the cross references. The assigned value must be
 		      /// \c PRE_HEAP (<tt>-1</tt>) for each item.
 		      /// \param comp The function object used for comparing the priorities.
 		      explicit Heap(ItemIntMap &map, const CMP &comp) {}
 		      /// \brief The number of items stored in the heap.
 		      ///
 		      /// This function returns the number of items stored in the heap.
 		      int size() const { return 0; }
 		      /// \brief Check if the heap is empty.
 		      ///
 		      /// This function returns \c true if the heap is empty.
 		      bool empty() const { return false; }
 		      /// \brief Make the heap empty.
 		      ///
 		      /// This functon makes the heap empty.
 		      /// It does not change the cross reference map. If you want to reuse
 		      /// a heap that is not surely empty, you should first clear it and
 		      /// then you should set the cross reference map to \c PRE_HEAP
 		      /// for each item.
 		      void clear() {}
 		      /// \brief Insert an item into the heap with the given priority.
 		      ///
 		      /// This function inserts the given item into the heap with the
 		      /// given priority.
 		      /// \param i The item to insert.
 		      /// \param p The priority of the item.
 		      /// \pre \e i must not be stored in the heap.
 		      void push(const Item &i, const Prio &p) {}
 		      /// \brief Return the item having minimum priority.
 		      ///
 		      /// This function returns the item having minimum priority.
 		      /// \pre The heap must be non-empty.
 		      Item top() const {}
 		      /// \brief The minimum priority.
 		      ///
 		      /// This function returns the minimum priority.
 		      /// \pre The heap must be non-empty.
 		      Prio prio() const {}
 		      /// \brief Remove the item having minimum priority.
 		      ///
 		      /// This function removes the item having minimum priority.
 		      /// \pre The heap must be non-empty.
 		      void pop() {}
 		      /// \brief Remove the given item from the heap.
 		      ///
 		      /// This function removes the given item from the heap if it is
 		      /// already stored.
 		      /// \param i The item to delete.
 		      /// \pre \e i must be in the heap.
 		      void erase(const Item &i) {}
 		      /// \brief The priority of the given item.
 		      ///
 		      /// This function returns the priority of the given item.
 		      /// \param i The item.
 		      /// \pre \e i must be in the heap.
 		      Prio operator[](const Item &i) const {}
 		      /// \brief Set the priority of an item or insert it, if it is
 		      /// not stored in the heap.
 		      ///
 		      /// This method sets the priority of the given item if it is
 		      /// already stored in the heap. Otherwise it inserts the given
 		      /// item into the heap with the given priority.
 		      ///
 		      /// \param i The item.
 		      /// \param p The priority.
 		      void set(const Item &i, const Prio &p) {}
 		      /// \brief Decrease the priority of an item to the given value.
 		      ///
 		      /// This function decreases the priority of an item to the given value.
 		      /// \param i The item.
 		      /// \param p The priority.
 		      /// \pre \e i must be stored in the heap with priority at least \e p.
 		      void decrease(const Item &i, const Prio &p) {}
 		      /// \brief Increase the priority of an item to the given value.
 		      ///
 		      /// This function increases the priority of an item to the given value.
 		      /// \param i The item.
 		      /// \param p The priority.
 		      /// \pre \e i must be stored in the heap with priority at most \e p.
 		      void increase(const Item &i, const Prio &p) {}
 		      /// \brief Return the state of an item.
 		      ///
 		      /// This method returns \c PRE_HEAP if the given item has never
 		      /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
 		      /// and \c POST_HEAP otherwise.
 		      /// In the latter case it is possible that the item will get back
 		      /// to the heap again.
 		      /// \param i The item.
 		      State state(const Item &i) const {}
 		      /// \brief Set the state of an item in the heap.
 		      ///
 		      /// This function sets the state of the given item in the heap.
 		      /// It can be used to manually clear the heap when it is important
 		      /// to achive better time complexity.
 		      /// \param i The item.
 		      /// \param st The state. It should not be \c IN_HEAP.
 		      void state(const Item& i, State st) {}
 		      template <typename _Heap>
 		      struct Constraints {
 		      public:
 		        void constraints() {
 		          typedef typename _Heap::Item OwnItem;
 		          typedef typename _Heap::Prio OwnPrio;
 		          typedef typename _Heap::State OwnState;
 		          Item item;
 		          Prio prio;
 		          item=Item();
 		          prio=Prio();
 		          ignore_unused_variable_warning(item);
 		          ignore_unused_variable_warning(prio);
 		          OwnItem own_item;
 		          OwnPrio own_prio;
 		          OwnState own_state;
 		          own_item=Item();
 		          own_prio=Prio();
 		          ignore_unused_variable_warning(own_item);
 		          ignore_unused_variable_warning(own_prio);
 		          ignore_unused_variable_warning(own_state);
 		          _Heap heap1(map);
 		          _Heap heap2 = heap1;
 		          ignore_unused_variable_warning(heap1);
 		          ignore_unused_variable_warning(heap2);
 		          int s = heap.size();
 		          ignore_unused_variable_warning(s);
 		          bool e = heap.empty();
 		          ignore_unused_variable_warning(e);
 		          prio = heap.prio();
 		          item = heap.top();
 		          prio = heap[item];
 		          own_prio = heap.prio();
 		          own_item = heap.top();
 		          own_prio = heap[own_item];
 		          heap.push(item, prio);
 		          heap.push(own_item, own_prio);
 		          heap.pop();
 		          heap.set(item, prio);
 		          heap.decrease(item, prio);
 		          heap.increase(item, prio);
 		          heap.set(own_item, own_prio);
 		          heap.decrease(own_item, own_prio);
 		          heap.increase(own_item, own_prio);
 		          heap.erase(item);
 		          heap.erase(own_item);
 		          heap.clear();
 		          own_state = heap.state(own_item);
 		          heap.state(own_item, own_state);
 		          own_state = _Heap::PRE_HEAP;
 		          own_state = _Heap::IN_HEAP;
 		          own_state = _Heap::POST_HEAP;
+		        }
 		        _Heap& heap;
 		        ItemIntMap& map;
 		      };
 		    };
 		    /// @}
 		  } // namespace lemon
+		}
 		#endif

lemon/fib_heap.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2009
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_FIB_HEAP_H
 		#define LEMON_FIB_HEAP_H
 		///\file
-		///\ingroup auxdat
+		///\ingroup heaps
 		///\brief Fibonacci heap implementation.
 		#include <vector>
 		#include <utility>
 		#include <functional>
 		#include <lemon/math.h>
 		namespace lemon {
-		  /// \ingroup auxdat
+		  /// \ingroup heaps
 		  ///
 		  /// \brief Fibonacci heap data structure.
 		  ///
 		  /// This class implements the \e Fibonacci \e heap data structure.
 		  /// It fully conforms to the \ref concepts::Heap "heap concept".
 		  ///
 		  /// The methods \ref increase() and \ref erase() are not efficient in a
 		  /// Fibonacci heap. In case of many calls of these operations, it is
 		  /// better to use other heap structure, e.g. \ref BinHeap "binary heap".
 		  ///
 		  /// \tparam PR Type of the priorities of the items.
 		  /// \tparam IM A read-writable item map with \c int values, used
 		  /// internally to handle the cross references.
 		  /// \tparam CMP A functor class for comparing the priorities.
 		  /// The default is \c std::less<PR>.
 		#ifdef DOXYGEN
 		  template <typename PR, typename IM, typename CMP>
 		#else
 		  template <typename PR, typename IM, typename CMP = std::less<PR> >
 		#endif
 		  class FibHeap {
 		  public:
 		    /// Type of the item-int map.
 		    typedef IM ItemIntMap;
 		    /// Type of the priorities.
 		    typedef PR Prio;
 		    /// Type of the items stored in the heap.
 		    typedef typename ItemIntMap::Key Item;
 		    /// Type of the item-priority pairs.
 		    typedef std::pair<Item,Prio> Pair;
 		    /// Functor type for comparing the priorities.
 		    typedef CMP Compare;
 		  private:
 		    class Store;
 		    std::vector<Store> _data;
 		    int _minimum;
 		    ItemIntMap &_iim;
 		    Compare _comp;
 		    int _num;
 		  public:
 		    /// \brief Type to represent the states of the items.
 		    ///
 		    /// Each item has a state associated to it. It can be "in heap",
 		    /// "pre-heap" or "post-heap". The latter two are indifferent from the
 		    /// heap's point of view, but may be useful to the user.
 		    ///
 		    /// The item-int map must be initialized in such way that it assigns
 		    /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
 		    enum State {
 		      IN_HEAP = 0,    ///< = 0.
 		      PRE_HEAP = -1,  ///< = -1.
 		      POST_HEAP = -2  ///< = -2.
 		    };
 		    /// \brief Constructor.
 		    ///
 		    /// Constructor.
 		    /// \param map A map that assigns \c int values to the items.
 		    /// It is used internally to handle the cross references.
 		    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
 		    explicit FibHeap(ItemIntMap &map)
 		      : _minimum(0), _iim(map), _num() {}
 		    /// \brief Constructor.
 		    ///
 		    /// Constructor.
 		    /// \param map A map that assigns \c int values to the items.
 		    /// It is used internally to handle the cross references.
 		    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
 		    /// \param comp The function object used for comparing the priorities.
 		    FibHeap(ItemIntMap &map, const Compare &comp)
 		      : _minimum(0), _iim(map), _comp(comp), _num() {}
 		    /// \brief The number of items stored in the heap.
 		    ///
 		    /// This function returns the number of items stored in the heap.
 		    int size() const { return _num; }
 		    /// \brief Check if the heap is empty.
 		    ///
 		    /// This function returns \c true if the heap is empty.
 		    bool empty() const { return _num==0; }
 		    /// \brief Make the heap empty.
 		    ///
 		    /// This functon makes the heap empty.
 		    /// It does not change the cross reference map. If you want to reuse
 		    /// a heap that is not surely empty, you should first clear it and
 		    /// then you should set the cross reference map to \c PRE_HEAP
 		    /// for each item.
 		    void clear() {
 		      _data.clear(); _minimum = 0; _num = 0;
+		    }
 		    /// \brief Insert an item into the heap with the given priority.
 		    ///
 		    /// This function inserts the given item into the heap with the
 		    /// given priority.
 		    /// \param item The item to insert.
 		    /// \param prio The priority of the item.
 		    /// \pre \e item must not be stored in the heap.
 		    void push (const Item& item, const Prio& prio) {
 		      int i=_iim[item];
 		      if ( i < 0 ) {
 		        int s=_data.size();
 		        _iim.set( item, s );
 		        Store st;
 		        st.name=item;
 		        _data.push_back(st);
 		        i=s;
 		      } else {
 		        _data[i].parent=_data[i].child=-1;
 		        _data[i].degree=0;
 		        _data[i].in=true;
 		        _data[i].marked=false;
+		      }
 		      if ( _num ) {
 		        _data[_data[_minimum].right_neighbor].left_neighbor=i;
 		        _data[i].right_neighbor=_data[_minimum].right_neighbor;
 		        _data[_minimum].right_neighbor=i;
 		        _data[i].left_neighbor=_minimum;
 		        if ( _comp( prio, _data[_minimum].prio) ) _minimum=i;
 		      } else {
 		        _data[i].right_neighbor=_data[i].left_neighbor=i;
 		        _minimum=i;
+		      }
 		      _data[i].prio=prio;
 		      ++_num;
+		    }
 		    /// \brief Return the item having minimum priority.
 		    ///
 		    /// This function returns the item having minimum priority.
 		    /// \pre The heap must be non-empty.
 		    Item top() const { return _data[_minimum].name; }
 		    /// \brief The minimum priority.
 		    ///
 		    /// This function returns the minimum priority.
 		    /// \pre The heap must be non-empty.
 		    Prio prio() const { return _data[_minimum].prio; }
 		    /// \brief Remove the item having minimum priority.
 		    ///
 		    /// This function removes the item having minimum priority.
 		    /// \pre The heap must be non-empty.
 		    void pop() {
 		      /*The first case is that there are only one root.*/
 		      if ( _data[_minimum].left_neighbor==_minimum ) {
 		        _data[_minimum].in=false;
 		        if ( _data[_minimum].degree!=0 ) {
 		          makeroot(_data[_minimum].child);
 		          _minimum=_data[_minimum].child;
 		          balance();
+		        }
 		      } else {
 		        int right=_data[_minimum].right_neighbor;
 		        unlace(_minimum);
 		        _data[_minimum].in=false;
 		        if ( _data[_minimum].degree > 0 ) {
 		          int left=_data[_minimum].left_neighbor;
 		          int child=_data[_minimum].child;
 		          int last_child=_data[child].left_neighbor;
 		          makeroot(child);
 		          _data[left].right_neighbor=child;
 		          _data[child].left_neighbor=left;
 		          _data[right].left_neighbor=last_child;
 		          _data[last_child].right_neighbor=right;
+		        }
 		        _minimum=right;
 		        balance();
 		      } // the case where there are more roots
 		      --_num;
+		    }
 		    /// \brief Remove the given item from the heap.
 		    ///
 		    /// This function removes the given item from the heap if it is
 		    /// already stored.
 		    /// \param item The item to delete.
 		    /// \pre \e item must be in the heap.
 		    void erase (const Item& item) {
 		      int i=_iim[item];
 		      if ( i >= 0 && _data[i].in ) {
 		        if ( _data[i].parent!=-1 ) {
 		          int p=_data[i].parent;
 		          cut(i,p);
 		          cascade(p);
+		        }
 		        _minimum=i;     //As if its prio would be -infinity
 		        pop();
+		      }
+		    }
 		    /// \brief The priority of the given item.
 		    ///
 		    /// This function returns the priority of the given item.
 		    /// \param item The item.
 		    /// \pre \e item must be in the heap.
 		    Prio operator[](const Item& item) const {
 		      return _data[_iim[item]].prio;
+		    }
 		    /// \brief Set the priority of an item or insert it, if it is
 		    /// not stored in the heap.
 		    ///
 		    /// This method sets the priority of the given item if it is
 		    /// already stored in the heap. Otherwise it inserts the given
 		    /// item into the heap with the given priority.
 		    /// \param item The item.
 		    /// \param prio The priority.
 		    void set (const Item& item, const Prio& prio) {
 		      int i=_iim[item];
 		      if ( i >= 0 && _data[i].in ) {
 		        if ( _comp(prio, _data[i].prio) ) decrease(item, prio);
 		        if ( _comp(_data[i].prio, prio) ) increase(item, prio);
 		      } else push(item, prio);
+		    }
 		    /// \brief Decrease the priority of an item to the given value.
 		    ///
 		    /// This function decreases the priority of an item to the given value.
 		    /// \param item The item.
 		    /// \param prio The priority.
 		    /// \pre \e item must be stored in the heap with priority at least \e prio.
 		    void decrease (const Item& item, const Prio& prio) {
 		      int i=_iim[item];
 		      _data[i].prio=prio;
 		      int p=_data[i].parent;
 		      if ( p!=-1 && _comp(prio, _data[p].prio) ) {
 		        cut(i,p);
 		        cascade(p);
+		      }
 		      if ( _comp(prio, _data[_minimum].prio) ) _minimum=i;
+		    }
 		    /// \brief Increase the priority of an item to the given value.
 		    ///
 		    /// This function increases the priority of an item to the given value.
 		    /// \param item The item.
 		    /// \param prio The priority.
 		    /// \pre \e item must be stored in the heap with priority at most \e prio.
 		    void increase (const Item& item, const Prio& prio) {
 		      erase(item);
 		      push(item, prio);
+		    }
 		    /// \brief Return the state of an item.
 		    ///
 		    /// This method returns \c PRE_HEAP if the given item has never
 		    /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
 		    /// and \c POST_HEAP otherwise.
 		    /// In the latter case it is possible that the item will get back
 		    /// to the heap again.
 		    /// \param item The item.
 		    State state(const Item &item) const {
 		      int i=_iim[item];
 		      if( i>=0 ) {
 		        if ( _data[i].in ) i=0;
 		        else i=-2;
+		      }
 		      return State(i);
+		    }
 		    /// \brief Set the state of an item in the heap.
 		    ///
 		    /// This function sets the state of the given item in the heap.
 		    /// It can be used to manually clear the heap when it is important
 		    /// to achive better time complexity.
 		    /// \param i The item.
 		    /// \param st The state. It should not be \c IN_HEAP.
 		    void state(const Item& i, State st) {
 		      switch (st) {
 		      case POST_HEAP:
 		      case PRE_HEAP:
 		        if (state(i) == IN_HEAP) {
 		          erase(i);
+		        }
 		        _iim[i] = st;
 		        break;
 		      case IN_HEAP:
 		        break;
+		      }
+		    }
 		  private:
 		    void balance() {
 		      int maxdeg=int( std::floor( 2.08*log(double(_data.size()))))+1;
 		      std::vector<int> A(maxdeg,-1);
 		      /*
 		       *Recall that now minimum does not point to the minimum prio element.
 		       *We set minimum to this during balance().
 		       */
 		      int anchor=_data[_minimum].left_neighbor;
 		      int next=_minimum;
 		      bool end=false;
 		      do {
 		        int active=next;
 		        if ( anchor==active ) end=true;
 		        int d=_data[active].degree;
 		        next=_data[active].right_neighbor;
 		        while (A[d]!=-1) {
 		          if( _comp(_data[active].prio, _data[A[d]].prio) ) {
 		            fuse(active,A[d]);
 		          } else {
 		            fuse(A[d],active);
 		            active=A[d];
+		          }
 		          A[d]=-1;
 		          ++d;
+		        }
 		        A[d]=active;
 		      } while ( !end );
 		      while ( _data[_minimum].parent >=0 )
 		        _minimum=_data[_minimum].parent;
 		      int s=_minimum;
 		      int m=_minimum;
 		      do {
 		        if ( _comp(_data[s].prio, _data[_minimum].prio) ) _minimum=s;
 		        s=_data[s].right_neighbor;
 		      } while ( s != m );
+		    }
 		    void makeroot(int c) {
 		      int s=c;
 		      do {
 		        _data[s].parent=-1;
 		        s=_data[s].right_neighbor;
 		      } while ( s != c );
+		    }
 		    void cut(int a, int b) {
 		      /*
 		       *Replacing a from the children of b.
 		       */
 		      --_data[b].degree;
 		      if ( _data[b].degree !=0 ) {
 		        int child=_data[b].child;
 		        if ( child==a )
 		          _data[b].child=_data[child].right_neighbor;
 		        unlace(a);
+		      }
 		      /*Lacing a to the roots.*/
 		      int right=_data[_minimum].right_neighbor;
 		      _data[_minimum].right_neighbor=a;
 		      _data[a].left_neighbor=_minimum;
 		      _data[a].right_neighbor=right;
 		      _data[right].left_neighbor=a;
 		      _data[a].parent=-1;
 		      _data[a].marked=false;
+		    }
 		    void cascade(int a) {
 		      if ( _data[a].parent!=-1 ) {
 		        int p=_data[a].parent;
 		        if ( _data[a].marked==false ) _data[a].marked=true;
 		        else {
 		          cut(a,p);
 		          cascade(p);
+		        }
+		      }
+		    }
 		    void fuse(int a, int b) {
 		      unlace(b);
 		      /*Lacing b under a.*/
 		      _data[b].parent=a;
 		      if (_data[a].degree==0) {
 		        _data[b].left_neighbor=b;
 		        _data[b].right_neighbor=b;
 		        _data[a].child=b;
 		      } else {
 		        int child=_data[a].child;
 		        int last_child=_data[child].left_neighbor;
 		        _data[child].left_neighbor=b;
 		        _data[b].right_neighbor=child;
 		        _data[last_child].right_neighbor=b;
 		        _data[b].left_neighbor=last_child;
+		      }
 		      ++_data[a].degree;
 		      _data[b].marked=false;
+		    }
 		    /*
 		     *It is invoked only if a has siblings.
 		     */
 		    void unlace(int a) {
 		      int leftn=_data[a].left_neighbor;
 		      int rightn=_data[a].right_neighbor;
 		      _data[leftn].right_neighbor=rightn;
 		      _data[rightn].left_neighbor=leftn;
+		    }
 		    class Store {
 		      friend class FibHeap;
 		      Item name;
 		      int parent;
 		      int left_neighbor;
 		      int right_neighbor;
 		      int child;
 		      int degree;
 		      bool marked;
 		      bool in;
 		      Prio prio;
 		      Store() : parent(-1), child(-1), degree(), marked(false), in(true) {}
 		    };
 		  };
 		} //namespace lemon
 		#endif //LEMON_FIB_HEAP_H

lemon/radix_heap.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2009
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_RADIX_HEAP_H
 		#define LEMON_RADIX_HEAP_H
-		///\ingroup auxdat
+		///\ingroup heaps
 		///\file
 		///\brief Radix heap implementation.
 		#include <vector>
 		#include <lemon/error.h>
 		namespace lemon {
-		  /// \ingroup auxdat
+		  /// \ingroup heaps
 		  ///
 		  /// \brief Radix heap data structure.
 		  ///
 		  /// This class implements the \e radix \e heap data structure.
 		  /// It practically conforms to the \ref concepts::Heap "heap concept",
 		  /// but it has some limitations due its special implementation.
 		  /// The type of the priorities must be \c int and the priority of an
 		  /// item cannot be decreased under the priority of the last removed item.
 		  ///
 		  /// \tparam IM A read-writable item map with \c int values, used
 		  /// internally to handle the cross references.
 		  template <typename IM>
 		  class RadixHeap {
 		  public:
 		    /// Type of the item-int map.
 		    typedef IM ItemIntMap;
 		    /// Type of the priorities.
 		    typedef int Prio;
 		    /// Type of the items stored in the heap.
 		    typedef typename ItemIntMap::Key Item;
 		    /// \brief Exception thrown by RadixHeap.
 		    ///
 		    /// This exception is thrown when an item is inserted into a
 		    /// RadixHeap with a priority smaller than the last erased one.
 		    /// \see RadixHeap
 		    class UnderFlowPriorityError : public Exception {
 		    public:
 		      virtual const char* what() const throw() {
 		        return "lemon::RadixHeap::UnderFlowPriorityError";
+		      }
 		    };
 		    /// \brief Type to represent the states of the items.
 		    ///
 		    /// Each item has a state associated to it. It can be "in heap",
 		    /// "pre-heap" or "post-heap". The latter two are indifferent from the
 		    /// heap's point of view, but may be useful to the user.
 		    ///
 		    /// The item-int map must be initialized in such way that it assigns
 		    /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
 		    enum State {
 		      IN_HEAP = 0,    ///< = 0.
 		      PRE_HEAP = -1,  ///< = -1.
 		      POST_HEAP = -2  ///< = -2.
 		    };
 		  private:
 		    struct RadixItem {
 		      int prev, next, box;
 		      Item item;
 		      int prio;
 		      RadixItem(Item _item, int _prio) : item(_item), prio(_prio) {}
 		    };
 		    struct RadixBox {
 		      int first;
 		      int min, size;
 		      RadixBox(int _min, int _size) : first(-1), min(_min), size(_size) {}
 		    };
 		    std::vector<RadixItem> data;
 		    std::vector<RadixBox> boxes;
 		    ItemIntMap &_iim;
 		  public:
 		    /// \brief Constructor.
 		    ///
 		    /// Constructor.
 		    /// \param map A map that assigns \c int values to the items.
 		    /// It is used internally to handle the cross references.
 		    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
 		    /// \param minimum The initial minimum value of the heap.
 		    /// \param capacity The initial capacity of the heap.
 		    RadixHeap(ItemIntMap &map, int minimum = 0, int capacity = 0)
 		      : _iim(map)
+		    {
 		      boxes.push_back(RadixBox(minimum, 1));
 		      boxes.push_back(RadixBox(minimum + 1, 1));
 		      while (lower(boxes.size() - 1, capacity + minimum - 1)) {
 		        extend();
+		      }
+		    }
 		    /// \brief The number of items stored in the heap.
 		    ///
 		    /// This function returns the number of items stored in the heap.
 		    int size() const { return data.size(); }
 		    /// \brief Check if the heap is empty.
 		    ///
 		    /// This function returns \c true if the heap is empty.
 		    bool empty() const { return data.empty(); }
 		    /// \brief Make the heap empty.
 		    ///
 		    /// This functon makes the heap empty.
 		    /// It does not change the cross reference map. If you want to reuse
 		    /// a heap that is not surely empty, you should first clear it and
 		    /// then you should set the cross reference map to \c PRE_HEAP
 		    /// for each item.
 		    /// \param minimum The minimum value of the heap.
 		    /// \param capacity The capacity of the heap.
 		    void clear(int minimum = 0, int capacity = 0) {
 		      data.clear(); boxes.clear();
 		      boxes.push_back(RadixBox(minimum, 1));
 		      boxes.push_back(RadixBox(minimum + 1, 1));
 		      while (lower(boxes.size() - 1, capacity + minimum - 1)) {
 		        extend();
+		      }
+		    }
 		  private:
 		    bool upper(int box, Prio pr) {
 		      return pr < boxes[box].min;
+		    }
 		    bool lower(int box, Prio pr) {
 		      return pr >= boxes[box].min + boxes[box].size;
+		    }
 		    // Remove item from the box list
 		    void remove(int index) {
 		      if (data[index].prev >= 0) {
 		        data[data[index].prev].next = data[index].next;
 		      } else {
 		        boxes[data[index].box].first = data[index].next;
+		      }
 		      if (data[index].next >= 0) {
 		        data[data[index].next].prev = data[index].prev;
+		      }
+		    }
 		    // Insert item into the box list
 		    void insert(int box, int index) {
 		      if (boxes[box].first == -1) {
 		        boxes[box].first = index;
 		        data[index].next = data[index].prev = -1;
 		      } else {
 		        data[index].next = boxes[box].first;
 		        data[boxes[box].first].prev = index;
 		        data[index].prev = -1;
 		        boxes[box].first = index;
+		      }
 		      data[index].box = box;
+		    }
 		    // Add a new box to the box list
 		    void extend() {
 		      int min = boxes.back().min + boxes.back().size;
 		      int bs = 2 * boxes.back().size;
 		      boxes.push_back(RadixBox(min, bs));
+		    }
 		    // Move an item up into the proper box.
 		    void bubble_up(int index) {
 		      if (!lower(data[index].box, data[index].prio)) return;
 		      remove(index);
 		      int box = findUp(data[index].box, data[index].prio);
 		      insert(box, index);
+		    }
 		    // Find up the proper box for the item with the given priority
 		    int findUp(int start, int pr) {
 		      while (lower(start, pr)) {
 		        if (++start == int(boxes.size())) {
 		          extend();
+		        }
+		      }
 		      return start;
+		    }
 		    // Move an item down into the proper box
 		    void bubble_down(int index) {
 		      if (!upper(data[index].box, data[index].prio)) return;
 		      remove(index);
 		      int box = findDown(data[index].box, data[index].prio);
 		      insert(box, index);
+		    }
 		    // Find down the proper box for the item with the given priority
 		    int findDown(int start, int pr) {
 		      while (upper(start, pr)) {
 		        if (--start < 0) throw UnderFlowPriorityError();
+		      }
 		      return start;
+		    }
 		    // Find the first non-empty box
 		    int findFirst() {
 		      int first = 0;
 		      while (boxes[first].first == -1) ++first;
 		      return first;
+		    }
 		    // Gives back the minimum priority of the given box
 		    int minValue(int box) {
 		      int min = data[boxes[box].first].prio;
 		      for (int k = boxes[box].first; k != -1; k = data[k].next) {
 		        if (data[k].prio < min) min = data[k].prio;
+		      }
 		      return min;
+		    }
 		    // Rearrange the items of the heap and make the first box non-empty
 		    void moveDown() {
 		      int box = findFirst();
 		      if (box == 0) return;
 		      int min = minValue(box);
 		      for (int i = 0; i <= box; ++i) {
 		        boxes[i].min = min;
 		        min += boxes[i].size;
+		      }
 		      int curr = boxes[box].first, next;
 		      while (curr != -1) {
 		        next = data[curr].next;
 		        bubble_down(curr);
 		        curr = next;
+		      }
+		    }
 		    void relocate_last(int index) {
 		      if (index != int(data.size()) - 1) {
 		        data[index] = data.back();
 		        if (data[index].prev != -1) {
 		          data[data[index].prev].next = index;
 		        } else {
 		          boxes[data[index].box].first = index;
+		        }
 		        if (data[index].next != -1) {
 		          data[data[index].next].prev = index;
+		        }
 		        _iim[data[index].item] = index;
+		      }
 		      data.pop_back();
+		    }
 		  public:
 		    /// \brief Insert an item into the heap with the given priority.
 		    ///
 		    /// This function inserts the given item into the heap with the
 		    /// given priority.
 		    /// \param i The item to insert.
 		    /// \param p The priority of the item.
 		    /// \pre \e i must not be stored in the heap.
 		    /// \warning This method may throw an \c UnderFlowPriorityException.
 		    void push(const Item &i, const Prio &p) {
 		      int n = data.size();
 		      _iim.set(i, n);
 		      data.push_back(RadixItem(i, p));
 		      while (lower(boxes.size() - 1, p)) {
 		        extend();
+		      }
 		      int box = findDown(boxes.size() - 1, p);
 		      insert(box, n);
+		    }
 		    /// \brief Return the item having minimum priority.
 		    ///
 		    /// This function returns the item having minimum priority.
 		    /// \pre The heap must be non-empty.
 		    Item top() const {
 		      const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown();
 		      return data[boxes[0].first].item;
+		    }
 		    /// \brief The minimum priority.
 		    ///
 		    /// This function returns the minimum priority.
 		    /// \pre The heap must be non-empty.
 		    Prio prio() const {
 		      const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown();
 		      return data[boxes[0].first].prio;
+		     }
 		    /// \brief Remove the item having minimum priority.
 		    ///
 		    /// This function removes the item having minimum priority.
 		    /// \pre The heap must be non-empty.
 		    void pop() {
 		      moveDown();
 		      int index = boxes[0].first;
 		      _iim[data[index].item] = POST_HEAP;
 		      remove(index);
 		      relocate_last(index);
+		    }
 		    /// \brief Remove the given item from the heap.
 		    ///
 		    /// This function removes the given item from the heap if it is
 		    /// already stored.
 		    /// \param i The item to delete.
 		    /// \pre \e i must be in the heap.
 		    void erase(const Item &i) {
 		      int index = _iim[i];
 		      _iim[i] = POST_HEAP;
 		      remove(index);
 		      relocate_last(index);
+		   }
 		    /// \brief The priority of the given item.
 		    ///
 		    /// This function returns the priority of the given item.
 		    /// \param i The item.
 		    /// \pre \e i must be in the heap.
 		    Prio operator[](const Item &i) const {
 		      int idx = _iim[i];
 		      return data[idx].prio;
+		    }
 		    /// \brief Set the priority of an item or insert it, if it is
 		    /// not stored in the heap.
 		    ///
 		    /// This method sets the priority of the given item if it is
 		    /// already stored in the heap. Otherwise it inserts the given
 		    /// item into the heap with the given priority.
 		    /// \param i The item.
 		    /// \param p The priority.
 		    /// \pre \e i must be in the heap.
 		    /// \warning This method may throw an \c UnderFlowPriorityException.
 		    void set(const Item &i, const Prio &p) {
 		      int idx = _iim[i];
 		      if( idx < 0 ) {
 		        push(i, p);
+		      }
 		      else if( p >= data[idx].prio ) {
 		        data[idx].prio = p;
 		        bubble_up(idx);
 		      } else {
 		        data[idx].prio = p;
 		        bubble_down(idx);
+		      }
+		    }
 		    /// \brief Decrease the priority of an item to the given value.
 		    ///
 		    /// This function decreases the priority of an item to the given value.
 		    /// \param i The item.
 		    /// \param p The priority.
 		    /// \pre \e i must be stored in the heap with priority at least \e p.
 		    /// \warning This method may throw an \c UnderFlowPriorityException.
 		    void decrease(const Item &i, const Prio &p) {
 		      int idx = _iim[i];
 		      data[idx].prio = p;
 		      bubble_down(idx);
+		    }
 		    /// \brief Increase the priority of an item to the given value.
 		    ///
 		    /// This function increases the priority of an item to the given value.
 		    /// \param i The item.
 		    /// \param p The priority.
 		    /// \pre \e i must be stored in the heap with priority at most \e p.
 		    void increase(const Item &i, const Prio &p) {
 		      int idx = _iim[i];
 		      data[idx].prio = p;
 		      bubble_up(idx);
+		    }
 		    /// \brief Return the state of an item.
 		    ///
 		    /// This method returns \c PRE_HEAP if the given item has never
 		    /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
 		    /// and \c POST_HEAP otherwise.
 		    /// In the latter case it is possible that the item will get back
 		    /// to the heap again.
 		    /// \param i The item.
 		    State state(const Item &i) const {
 		      int s = _iim[i];
 		      if( s >= 0 ) s = 0;
 		      return State(s);
+		    }
 		    /// \brief Set the state of an item in the heap.
 		    ///
 		    /// This function sets the state of the given item in the heap.
 		    /// It can be used to manually clear the heap when it is important
 		    /// to achive better time complexity.
 		    /// \param i The item.
 		    /// \param st The state. It should not be \c IN_HEAP.
 		    void state(const Item& i, State st) {
 		      switch (st) {
 		      case POST_HEAP:
 		      case PRE_HEAP:
 		        if (state(i) == IN_HEAP) {
 		          erase(i);
+		        }
 		        _iim[i] = st;
 		        break;
 		      case IN_HEAP:
 		        break;
+		      }
+		    }
 		  }; // class RadixHeap
 		} // namespace lemon
 		#endif // LEMON_RADIX_HEAP_H

0 comments (0 inline)

RhodeCode

Login to your account