# HG changeset patch # User alpar # Date 1096471804 0 # Node ID 818510fa3d99e8c960874b7074d950a2013098a9 # Parent 2d6c8075d9d0d91c3e6d0572395dbca3334f7f9a hugo -> lemon diff -r 2d6c8075d9d0 -r 818510fa3d99 Makefile.am --- a/Makefile.am Wed Sep 29 14:12:26 2004 +0000 +++ b/Makefile.am Wed Sep 29 15:30:04 2004 +0000 @@ -11,7 +11,7 @@ doc/Makefile.in \ doc/doxygen.log \ src/Makefile.in \ - src/hugo/Makefile.in \ + src/lemon/Makefile.in \ src/test/Makefile.in \ src/benchmark/Makefile.in diff -r 2d6c8075d9d0 -r 818510fa3d99 configure.ac --- a/configure.ac Wed Sep 29 14:12:26 2004 +0000 +++ b/configure.ac Wed Sep 29 15:30:04 2004 +0000 @@ -1,8 +1,8 @@ dnl Process this file with autoconf to produce a configure script. -AC_INIT([HugoLib], [0.2], [etik-ol@cs.elte.hu], [hugo]) +AC_INIT([LEMON], [0.2], [etik-ol@cs.elte.hu], [lemon]) AC_CONFIG_AUX_DIR([config]) AM_INIT_AUTOMAKE(1.7) -AC_CONFIG_SRCDIR([src/hugo/invalid.h]) +AC_CONFIG_SRCDIR([src/lemon/invalid.h]) AC_PREREQ(2.57) dnl Checks for programs. @@ -27,5 +27,5 @@ AC_HEADER_STDC AC_CHECK_FUNCS(gettimeofday) -AC_CONFIG_FILES([Makefile doc/Makefile src/Makefile src/hugo/Makefile src/test/Makefile src/benchmark/Makefile]) +AC_CONFIG_FILES([Makefile doc/Makefile src/Makefile src/lemon/Makefile src/test/Makefile src/benchmark/Makefile]) AC_OUTPUT diff -r 2d6c8075d9d0 -r 818510fa3d99 doc/coding_style.dox --- a/doc/coding_style.dox Wed Sep 29 14:12:26 2004 +0000 +++ b/doc/coding_style.dox Wed Sep 29 15:30:04 2004 +0000 @@ -1,6 +1,6 @@ /*! -\page coding_style Hugo Coding Style +\page coding_style LEMON Coding Style \section naming_conv Naming Conventions @@ -9,7 +9,7 @@ functions, variables, constants and exceptions. If these conventions are met in one's code then it is easier to read and maintain it. Please comply with these conventions if you want to contribute -developing Hugo library. +developing LEMON library. \subsection cs-class Classes and other types diff -r 2d6c8075d9d0 -r 818510fa3d99 doc/graphs.dox --- a/doc/graphs.dox Wed Sep 29 14:12:26 2004 +0000 +++ b/doc/graphs.dox Wed Sep 29 15:30:04 2004 +0000 @@ -2,60 +2,60 @@ \page graphs How to use graphs -The primary data structures of HugoLib are the graph classes. They all +The primary data structures of LEMON are the graph classes. They all provide a node list - edge list interface, i.e. they have functionalities to list the nodes and the edges of the graph as well as in incoming and outgoing edges of a given node. Each graph should meet the -\ref hugo::skeleton::StaticGraph "StaticGraph" concept. +\ref lemon::skeleton::StaticGraph "StaticGraph" concept. This concept does not makes it possible to change the graph (i.e. it is not possible to add or delete edges or nodes). Most of the graph algorithms will run on these graphs. The graphs meeting the -\ref hugo::skeleton::ExtendableGraph "ExtendableGraph" +\ref lemon::skeleton::ExtendableGraph "ExtendableGraph" concept allow node and edge addition. You can also "clear" (i.e. erase all edges and nodes) such a graph. In case of graphs meeting the full feature -\ref hugo::skeleton::ErasableGraph "ErasableGraph" +\ref lemon::skeleton::ErasableGraph "ErasableGraph" concept you can also erase individual edges and node in arbitrary order. The implemented graph structures are the following. -\li \ref hugo::ListGraph "ListGraph" is the most versatile graph class. It meets -the \ref hugo::skeleton::ErasableGraph "ErasableGraph" concept +\li \ref lemon::ListGraph "ListGraph" is the most versatile graph class. It meets +the \ref lemon::skeleton::ErasableGraph "ErasableGraph" concept and it also have some convenience features. -\li \ref hugo::SmartGraph "SmartGraph" is a more memory -efficient version of \ref hugo::ListGraph "ListGraph". The +\li \ref lemon::SmartGraph "SmartGraph" is a more memory +efficient version of \ref lemon::ListGraph "ListGraph". The price of it is that it only meets the -\ref hugo::skeleton::ExtendableGraph "ExtendableGraph" concept, +\ref lemon::skeleton::ExtendableGraph "ExtendableGraph" concept, so you cannot delete individual edges or nodes. -\li \ref hugo::SymListGraph "SymListGraph" and -\ref hugo::SymSmartGraph "SymSmartGraph" classes are very similar to -\ref hugo::ListGraph "ListGraph" and \ref hugo::SmartGraph "SmartGraph". +\li \ref lemon::SymListGraph "SymListGraph" and +\ref lemon::SymSmartGraph "SymSmartGraph" classes are very similar to +\ref lemon::ListGraph "ListGraph" and \ref lemon::SmartGraph "SmartGraph". The difference is that whenever you add a new edge to the graph, it actually adds a pair of oppositely directed edges. They are linked together so it is possible to access the counterpart of an edge. An even more important feature is that using these classes you can also attach data to the edges in such a way that the stored data are shared by the edge pairs. -\li \ref hugo::FullGraph "FullGraph" -implements a full graph. It is a \ref hugo::skeleton::StaticGraph, so you cannot +\li \ref lemon::FullGraph "FullGraph" +implements a full graph. It is a \ref lemon::skeleton::StaticGraph, so you cannot change the number of nodes once it is constructed. It is extremely memory efficient: it uses constant amount of memory independently from the number of the nodes of the graph. Of course, the size of the \ref maps "NodeMap"'s and \ref maps "EdgeMap"'s will depend on the number of nodes. -\li \ref hugo::NodeSet "NodeSet" implements a graph with no edges. This class -can be used as a base class of \ref hugo::EdgeSet "EdgeSet". -\li \ref hugo::EdgeSet "EdgeSet" can be used to create a new graph on +\li \ref lemon::NodeSet "NodeSet" implements a graph with no edges. This class +can be used as a base class of \ref lemon::EdgeSet "EdgeSet". +\li \ref lemon::EdgeSet "EdgeSet" can be used to create a new graph on the node set of another graph. The base graph can be an arbitrary graph and it -is possible to attach several \ref hugo::EdgeSet "EdgeSet"'s to a base graph. +is possible to attach several \ref lemon::EdgeSet "EdgeSet"'s to a base graph. \todo Don't we need SmartNodeSet and SmartEdgeSet? \todo Some cross-refs are wrong. @@ -65,21 +65,21 @@ \ref maps "map classes" to dynamically attach data the to graph components. -The following program demonstrates the basic features of HugoLib's graph +The following program demonstrates the basic features of LEMON's graph structures. \code #include -#include +#include -using namespace hugo; +using namespace lemon; int main() { typedef ListGraph Graph; \endcode -ListGraph is one of HugoLib's graph classes. It is based on linked lists, +ListGraph is one of LEMON's graph classes. It is based on linked lists, therefore iterating throuh its edges and nodes is fast. \code @@ -114,7 +114,7 @@ node iterator to initialize it to the first node. The operator++ is used to step to the next node. Using operator++ on the iterator pointing to the last node invalidates the iterator i.e. sets its value to -\ref hugo::INVALID "INVALID". This is what we exploit in the stop condition. +\ref lemon::INVALID "INVALID". This is what we exploit in the stop condition. The previous code fragment prints out the following: @@ -181,7 +181,7 @@ \endcode As we mentioned above, graphs are not containers rather -incidence structures which are iterable in many ways. HugoLib introduces +incidence structures which are iterable in many ways. LEMON introduces concepts that allow us to attach containers to graphs. These containers are called maps. diff -r 2d6c8075d9d0 -r 818510fa3d99 doc/groups.dox --- a/doc/groups.dox Wed Sep 29 14:12:26 2004 +0000 +++ b/doc/groups.dox Wed Sep 29 15:30:04 2004 +0000 @@ -1,23 +1,23 @@ /** @defgroup datas Data Structures -This group describes the several graph structures implemented in HugoLib. +This group describes the several graph structures implemented in LEMON. */ /** @defgroup graphs Graph Structures @ingroup datas -\brief Graph structures implemented in Hugo. +\brief Graph structures implemented in LEMON. -Hugolib provides several data structures to meet the diverging requirements +LEMON provides several data 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 edge or node deletion. -Hugolib also offers special graphs that cannot be used alone but only +LEMON also offers special graphs that cannot be used alone but only in conjunction with other graph representation. The examples for this are -\ref hugo::EdgeSet "EdgeSet", \ref hugo::NodeSet "NodeSet" +\ref lemon::EdgeSet "EdgeSet", \ref lemon::NodeSet "NodeSet" and the large variety of \ref gwrappers "graph wrappers". You are free to use the graph structure that fit your requirements @@ -28,9 +28,9 @@ /** @defgroup auxdat Auxiliary Data Structures @ingroup datas -\brief Some data structures implemented in HugoLib. +\brief Some data structures implemented in LEMON. -This group describes the data structures implemented in HugoLib in +This group describes the data structures implemented in LEMON in order to make it easier to implement combinatorial algorithms. */ @@ -52,7 +52,7 @@ /** @defgroup galgs Graph Algorithms \brief This group describes the several graph algorithms -implemented in HugoLib. +implemented in LEMON. */ /** @@ -72,7 +72,7 @@ @defgroup skeletons Skeletons \brief Skeletons (a.k.a. concept checking classes) -This group describes the data/algorithm skeletons implemented in HugoLib in +This group describes the data/algorithm skeletons implemented in LEMON in order to make it easier to check if a certain template class or template function is correctly implemented. */ diff -r 2d6c8075d9d0 -r 818510fa3d99 doc/mainpage.dox --- a/doc/mainpage.dox Wed Sep 29 14:12:26 2004 +0000 +++ b/doc/mainpage.dox Wed Sep 29 15:30:04 2004 +0000 @@ -3,9 +3,11 @@ \section intro Introduction -\subsection whatis What is HugoLib +\subsection whatis What is LEMON -HugoLib stands for Hungarian Graph Optimization Library. +LEMON stands for +Library of Efficient Models +and Optimization in Networks. It is a C++ template library aimed at combinatorial optimization tasks which often involve in working @@ -14,7 +16,7 @@ \subsection howtoread How to read this document -Graph structures play central role in HugoLib, so if you are new to it, +Graph structures play central role in LEMON, so if you are new to it, you probably should start \ref graphs "here". You can also find this page along with others under Related Pages diff -r 2d6c8075d9d0 -r 818510fa3d99 doc/maps.dox --- a/doc/maps.dox Wed Sep 29 14:12:26 2004 +0000 +++ b/doc/maps.dox Wed Sep 29 15:30:04 2004 +0000 @@ -4,7 +4,7 @@ \page maps Maps -Maps play central role in HUGOlib. As their name suggests, they map a +Maps play central role in LEMON. As their name suggests, they map a certain range of \e keys to certain \e values. Each map has two typedef's to determine the types of keys and values, like this: @@ -21,7 +21,7 @@ value belonging to a key, so you have a direct access to the memory address where it is stored. -Each graph structure in HUGOlib provides two standard map templates called +Each graph structure in LEMON provides two standard map templates called \c EdgeMap and \c NodeMap. Both are reference maps and you can easily assign data to the nodes and to the edges of the graph. For example if you have a graph \c G defined as @@ -69,7 +69,7 @@ The readable maps are very frequently used as the input of the algorithms. For this purpose the most straightforward way is the use of the -default maps provided by Hugo's graph structures. +default maps provided by LEMON's graph structures. Very often however, it is more convenient and/or more efficient to write your own readable map. diff -r 2d6c8075d9d0 -r 818510fa3d99 doc/namespaces.dox --- a/doc/namespaces.dox Wed Sep 29 14:12:26 2004 +0000 +++ b/doc/namespaces.dox Wed Sep 29 15:30:04 2004 +0000 @@ -1,10 +1,10 @@ -/// The namespace of HugoLib +/// The namespace of LEMON /// \todo Some more detailed description would be nice here. /// -namespace hugo { +namespace lemon { - /// The namespace of HUGOlib concepts and concept checking classes + /// The namespace of LEMON concepts and concept checking classes /// \todo Some more detailed description would be nice here. /// diff -r 2d6c8075d9d0 -r 818510fa3d99 src/Makefile.am --- a/src/Makefile.am Wed Sep 29 14:12:26 2004 +0000 +++ b/src/Makefile.am Wed Sep 29 15:30:04 2004 +0000 @@ -1,1 +1,1 @@ -SUBDIRS = hugo benchmark test +SUBDIRS = lemon benchmark test diff -r 2d6c8075d9d0 -r 818510fa3d99 src/benchmark/bench_tools.h --- a/src/benchmark/bench_tools.h Wed Sep 29 14:12:26 2004 +0000 +++ b/src/benchmark/bench_tools.h Wed Sep 29 15:30:04 2004 +0000 @@ -1,11 +1,11 @@ // -*- mode:C++ -*- -#ifndef HUGO_BENCH_TEST_H -#define HUGO_BENCH_TEST_H +#ifndef LEMON_BENCH_TEST_H +#define LEMON_BENCH_TEST_H #include #include -#include +#include ///An experimental typedef factory #define GRAPH_TYPEDEF_FACTORY(Graph) \ @@ -74,9 +74,9 @@ } }; -inline void PrintTime(char *ID,hugo::Timer &T) +inline void PrintTime(char *ID,lemon::Timer &T) { - hugo::TimeStamp S(T); + lemon::TimeStamp S(T); std::cout << ID << ' ' << S.getUserTime() << ' ' << S.getSystemTime() << ' ' << S.getRealTime() << std::endl; } diff -r 2d6c8075d9d0 -r 818510fa3d99 src/benchmark/bfs-bench.cc --- a/src/benchmark/bfs-bench.cc Wed Sep 29 14:12:26 2004 +0000 +++ b/src/benchmark/bfs-bench.cc Wed Sep 29 15:30:04 2004 +0000 @@ -2,11 +2,11 @@ #include #include -#include +#include #include"bench_tools.h" using namespace std; -using namespace hugo; +using namespace lemon; inline int numOfOnes(int n,int dim) { diff -r 2d6c8075d9d0 -r 818510fa3d99 src/benchmark/graph-bench.cc --- a/src/benchmark/graph-bench.cc Wed Sep 29 14:12:26 2004 +0000 +++ b/src/benchmark/graph-bench.cc Wed Sep 29 15:30:04 2004 +0000 @@ -1,9 +1,9 @@ #include -#include +#include #include"bench_tools.h" -using namespace hugo; +using namespace lemon; ///Makes a full graph by adding and deleting a lot of edges; @@ -45,7 +45,7 @@ int main() { - hugo::Timer T; + lemon::Timer T; makeFullGraph(nextPrim(1000),nextPrim(300),nextPrim(100)); PrintTime("BIG",T); diff -r 2d6c8075d9d0 -r 818510fa3d99 src/benchmark/hcube.cc --- a/src/benchmark/hcube.cc Wed Sep 29 14:12:26 2004 +0000 +++ b/src/benchmark/hcube.cc Wed Sep 29 15:30:04 2004 +0000 @@ -1,15 +1,15 @@ // -*- mode:C++ -*- #include -#include -#include -#include -#include +#include +#include +#include +#include #include"bench_tools.h" using namespace std; -using namespace hugo; +using namespace lemon; inline int numOfOnes(int n,int dim) { diff -r 2d6c8075d9d0 -r 818510fa3d99 src/demo/sub_graph_wrapper_demo.cc --- a/src/demo/sub_graph_wrapper_demo.cc Wed Sep 29 14:12:26 2004 +0000 +++ b/src/demo/sub_graph_wrapper_demo.cc Wed Sep 29 15:30:04 2004 +0000 @@ -8,15 +8,15 @@ #include #include -#include -#include -#include -#include -#include -#include -#include +#include +#include +#include +#include +#include +#include +#include -using namespace hugo; +using namespace lemon; using std::cout; using std::endl; diff -r 2d6c8075d9d0 -r 818510fa3d99 src/hugo/Makefile.am --- a/src/hugo/Makefile.am Wed Sep 29 14:12:26 2004 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,35 +0,0 @@ -pkginclude_HEADERS = \ - array_map.h \ - bfs.h \ - dfs.h \ - bin_heap.h \ - default_map.h \ - dijkstra.h \ - dimacs.h \ - extended_pair.h \ - fib_heap.h \ - full_graph.h \ - graph_wrapper.h \ - invalid.h \ - kruskal.h \ - list_graph.h \ - map_defines.h \ - map_iterator.h \ - map_registry.h \ - map_bits.h \ - maps.h \ - min_cost_flow.h \ - suurballe.h \ - preflow.h \ - path.h \ - smart_graph.h \ - sym_map.h \ - time_measure.h \ - unionfind.h \ - vector_map.h \ - xy.h - -noinst_HEADERS = \ - skeletons/graph.h \ - skeletons/maps.h \ - skeletons/path.h diff -r 2d6c8075d9d0 -r 818510fa3d99 src/hugo/array_map.h --- a/src/hugo/array_map.h Wed Sep 29 14:12:26 2004 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,349 +0,0 @@ -/* -*- C++ -*- - * src/hugo/array_map.h - Part of HUGOlib, a generic C++ optimization library - * - * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport - * (Egervary Combinatorial Optimization Research Group, 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 HUGO_ARRAY_MAP_H -#define HUGO_ARRAY_MAP_H - -#include - -#include -#include - -///\ingroup graphmaps -///\file -///\brief Graph maps that construates and destruates -///their elements dynamically. - -namespace hugo { - - - /// \addtogroup graphmaps - /// @{ - - /** The ArrayMap template class is graph map structure what - * automatically updates the map when a key is added to or erased from - * the map. This map factory uses the allocators to implement - * the container functionality. - * - * The template parameter is the MapRegistry that the maps - * will belong to and the ValueType. - */ - - template - class ArrayMap : public MapRegistry::MapBase { - - template friend class ArrayMap; - - public: - - /// The graph type of the maps. - typedef typename MapRegistry::Graph Graph; - /// The key type of the maps. - typedef typename MapRegistry::KeyType KeyType; - /// The iterator to iterate on the keys. - typedef typename MapRegistry::KeyIt KeyIt; - - /// The MapBase of the Map which imlements the core regisitry function. - typedef typename MapRegistry::MapBase MapBase; - - - public: - - /// The value type of the map. - typedef Value ValueType; - /// The reference type of the map; - typedef Value& ReferenceType; - /// The pointer type of the map; - typedef Value* PointerType; - - /// The const value type of the map. - typedef const Value ConstValueType; - /// The const reference type of the map; - typedef const Value& ConstReferenceType; - /// The pointer type of the map; - typedef const Value* ConstPointerType; - - - typedef std::allocator Allocator; - - - /** Graph and Registry initialized map constructor. - */ - ArrayMap(const Graph& g, MapRegistry& r) : MapBase(g, r) { - allocate_memory(); - for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) { - int id = KeyInfo::id(*MapBase::getGraph(), it); - allocator.construct(&(values[id]), Value()); - } - } - - /** Constructor to use default value to initialize the map. - */ - ArrayMap(const Graph& g, MapRegistry& r, const Value& v) - : MapBase(g, r) { - allocate_memory(); - for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) { - int id = KeyInfo::id(*MapBase::getGraph(), it); - allocator.construct(&(values[id]), v); - } - } - - /** Constructor to copy a map of the same map type. - */ - ArrayMap(const ArrayMap& copy) : MapBase(copy) { - capacity = copy.capacity; - if (capacity == 0) return; - values = allocator.allocate(capacity); - for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) { - int id = KeyInfo::id(*MapBase::getGraph(), it); - allocator.construct(&(values[id]), copy.values[id]); - } - } - - /** Constructor to copy a map of an other map type. - */ - template - ArrayMap(const ArrayMap& copy) - : MapBase(copy) { - capacity = copy.capacity; - if (capacity == 0) return; - values = allocator.allocate(capacity); - for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) { - int id = KeyInfo::id(*MapBase::getGraph(), it); - allocator.construct(&(values[id]), copy.values[id]); - } - } - - /** Assign operator to copy a map of the same map type. - */ - ArrayMap& operator=(const ArrayMap& copy) { - if (© == this) return *this; - - if (MapBase::getGraph() != copy.getGraph()) { - if (capacity != 0) { - MapBase::destroy(); - allocator.deallocate(values, capacity); - } - - MapBase::operator=(copy); - capacity = copy.capacity; - if (capacity == 0) return *this; - values = allocator.allocate(capacity); - } - - for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) { - int id = KeyInfo::id(*MapBase::getGraph(), it); - allocator.construct(&(values[id]), copy.values[id]); - } - - return *this; - } - - /** Assign operator to copy a map of an other map type. - */ - template - ArrayMap& operator=(const ArrayMap& copy) { - - if (MapBase::getGraph() != copy.getGraph()) { - if (capacity != 0) { - MapBase::destroy(); - allocator.deallocate(values, capacity); - } - - MapBase::operator=(copy); - - capacity = copy.capacity; - if (capacity == 0) return *this; - values = allocator.allocate(capacity); - } - - for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) { - int id = KeyInfo::id(*MapBase::getGraph(), it); - allocator.construct(&(values[id]), copy.values[id]); - } - - return *this; - } - - /** The destructor of the map. - */ - virtual ~ArrayMap() { - if (capacity != 0) { - MapBase::destroy(); - allocator.deallocate(values, capacity); - } - } - - - /** - * The subscript operator. The map can be subscripted by the - * actual keys of the graph. - */ - ReferenceType operator[](const KeyType& key) { - int id = KeyInfo::id(*MapBase::getGraph(), key); - return values[id]; - } - - /** - * The const subscript operator. The map can be subscripted by the - * actual keys of the graph. - */ - ConstReferenceType operator[](const KeyType& key) const { - int id = KeyInfo::id(*MapBase::getGraph(), key); - return values[id]; - } - - /** Setter function of the map. Equivalent with map[key] = val. - * This is a compatibility feature with the not dereferable maps. - */ - void set(const KeyType& key, const ValueType& val) { - int id = KeyInfo::id(*MapBase::getGraph(), key); - values[id] = val; - } - - /** Add a new key to the map. It called by the map registry. - */ - void add(const KeyType& key) { - int id = KeyInfo::id(*MapBase::getGraph(), key); - if (id >= capacity) { - int new_capacity = (capacity == 0 ? 1 : capacity); - while (new_capacity <= id) { - new_capacity <<= 1; - } - Value* new_values = allocator.allocate(new_capacity);; - for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) { - int jd = KeyInfo::id(*MapBase::getGraph(), it); - if (id != jd) { - allocator.construct(&(new_values[jd]), values[jd]); - allocator.destroy(&(values[jd])); - } - } - if (capacity != 0) allocator.deallocate(values, capacity); - values = new_values; - capacity = new_capacity; - } - allocator.construct(&(values[id]), Value()); - } - - /** Erase a key from the map. It called by the map registry. - */ - void erase(const KeyType& key) { - int id = KeyInfo::id(*MapBase::getGraph(), key); - allocator.destroy(&(values[id])); - } - - /** Clear the data structure. - */ - void clear() { - if (capacity != 0) { - MapBase::destroy(); - allocator.deallocate(values, capacity); - capacity = 0; - } - } - - /// The stl compatible pair iterator of the map. - typedef MapIterator Iterator; - /// The stl compatible const pair iterator of the map. - typedef MapConstIterator ConstIterator; - - /** Returns the begin iterator of the map. - */ - Iterator begin() { - return Iterator(*this, KeyIt(*MapBase::getGraph())); - } - - /** Returns the end iterator of the map. - */ - Iterator end() { - return Iterator(*this, INVALID); - } - - /** Returns the begin ConstIterator of the map. - */ - ConstIterator begin() const { - return ConstIterator(*this, KeyIt(*MapBase::getGraph())); - } - - /** Returns the end const_iterator of the map. - */ - ConstIterator end() const { - return ConstIterator(*this, INVALID); - } - - /// The KeySet of the Map. - typedef MapConstKeySet ConstKeySet; - - /// KeySet getter function. - ConstKeySet keySet() const { - return ConstKeySet(*this); - } - - /// The ConstValueSet of the Map. - typedef MapConstValueSet ConstValueSet; - - /// ConstValueSet getter function. - ConstValueSet valueSet() const { - return ConstValueSet(*this); - } - - /// The ValueSet of the Map. - typedef MapValueSet ValueSet; - - /// ValueSet getter function. - ValueSet valueSet() { - return ValueSet(*this); - } - - private: - - void allocate_memory() { - int max_id = KeyInfo::maxId(*MapBase::getGraph()); - if (max_id == -1) { - capacity = 0; - values = 0; - return; - } - capacity = 1; - while (capacity <= max_id) { - capacity <<= 1; - } - values = allocator.allocate(capacity); - } - - int capacity; - Value* values; - Allocator allocator; - - public: - // STL compatibility typedefs. - typedef Iterator iterator; - typedef ConstIterator const_iterator; - typedef typename Iterator::PairValueType value_type; - typedef typename Iterator::KeyType key_type; - typedef typename Iterator::ValueType data_type; - typedef typename Iterator::PairReferenceType reference; - typedef typename Iterator::PairPointerType pointer; - typedef typename ConstIterator::PairReferenceType const_reference; - typedef typename ConstIterator::PairPointerType const_pointer; - typedef int difference_type; - }; - -/// @} - -} - -#endif //HUGO_ARRAY_MAP_H diff -r 2d6c8075d9d0 -r 818510fa3d99 src/hugo/attic/debug.h --- a/src/hugo/attic/debug.h Wed Sep 29 14:12:26 2004 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,70 +0,0 @@ -/* -*- C++ -*- - * src/hugo/debug.h - Part of HUGOlib, a generic C++ optimization library - * - * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport - * (Egervary Combinatorial Optimization Research Group, 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 HUGO_DEBUG_H -#define HUGO_DEBUG_H - -//! \file -//! \brief Basic definitions for debug control. - -namespace hugo { - - //! Debug mode for testing/debugging - - //! Use this debug mode if you want exhaustive range and consistency checks. - //! It also produces verbose debug messages. - struct DebugOn { - //! Example: check whether the edges added to a path are adjacent - static const bool consistensy_check = true; - - static const bool range_check = true; - - //! Examples: initialize maps with some value; - //! after deleting an item from UnionFindEnum set its value in the - //! corresponding map to NULL... - static const bool ensure_safe_state = true; - - static const int verbose = 5; - }; - - //! Debug mode for turning off debug aids. - - //! This debud mode switches off all range and consistency checks, - //! as well as the debug messages. - //! - struct DebugOff { - static const bool consistensy_check = false; - static const bool range_check = false; - static const bool ensure_safe_state = false; - static const int verbose = 0; - }; - -#ifdef DEBUG - //! The default debug mode. - - //! The default debug mode. - //! - typedef DebugOn DefaultDebugMode; -#else - //! The default debug mode. - - //! The default debug mode. - //! - typedef DebugOff DefaultDebugMode; -#endif - -} -#endif // HUGO_DEBUG_H diff -r 2d6c8075d9d0 -r 818510fa3d99 src/hugo/attic/error.h --- a/src/hugo/attic/error.h Wed Sep 29 14:12:26 2004 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,82 +0,0 @@ -/* -*- C++ -*- - * src/hugo/error.h - Part of HUGOlib, a generic C++ optimization library - * - * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport - * (Egervary Combinatorial Optimization Research Group, 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 HUGO_ERROR_H -#define HUGO_ERROR_H - -//! \ingroup misc -//! \file -//! \brief Basic error handling (signaling) routines. - -#include -#include -#include - - -namespace hugo { - - /** - * \brief Generic exception class. - * - * \todo Do we need this? - * - * \todo Don't we need different kind of exceptions for different kind - * of errors? - * Shouldn't we use \ instead? - */ - class Exception : public std::exception { - protected: - std::ostringstream buf; - public: - Exception() {} - explicit Exception(const std::string &s) { buf << s; } - Exception(const Exception &e) : std::exception() { - buf << e.buf.str(); - } - virtual ~Exception() throw() {} - - virtual const char* what() const throw() { - return buf.str().c_str(); - } - - Exception& operator<<(std::string const& s) { buf << s; return *this; } - Exception& operator<<(char const *s) { buf << s; return *this; } - Exception& operator<<(int i) { buf << i; return *this; } - }; - - /** - * \brief Generic error signaling function. - * - * \todo Do we really need this? Is it helpful? - */ - inline void fault(const std::string &msg) { - throw Exception(msg); - } - - /** - * \brief Macro for mark not yet implemented features. - * - * \todo Is this the right place for this? It should be used only in - * modules under development. - */ - -# define FIXME(msg) \ - do { throw ::hugo::Exception() << "FIXME: " msg " (in: " \ - __FILE__ ", " << __LINE__ << ")"; \ - } while(false) - -} -#endif // HUGO_ERROR_H diff -r 2d6c8075d9d0 -r 818510fa3d99 src/hugo/attic/tight_edge_filter_map.h --- a/src/hugo/attic/tight_edge_filter_map.h Wed Sep 29 14:12:26 2004 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,63 +0,0 @@ -/* -*- C++ -*- - * src/hugo/tight_edge_filter_map.h - Part of HUGOlib, a generic C++ optimization library - * - * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport - * (Egervary Combinatorial Optimization Research Group, 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 HUGO_TIGHT_EDGE_FILTER_MAP_H -#define HUGO_TIGHT_EDGE_FILTER_MAP_H - -#include - -// /// \file -// /// \brief Maximum flow algorithms. -// /// \ingroup galgs - -namespace hugo { - - /// \brief A map for filtering the edge-set to those edges - /// which are tight w.r.t. some node_potential map and - /// edge_distance map. - /// - /// A node-map node_potential is said to be a potential w.r.t. - /// an edge-map edge_distance - /// if and only if for each edge e, node_potential[g.head(e)] - /// <= edge_distance[e]+node_potential[g.tail(e)] - /// (or the reverse inequality holds for each edge). - /// An edge is said to be tight if this inequality holds with equality, - /// and the map returns true exactly for those edges. - /// To avoid rounding errors, it is recommended to use this class with exact - /// types, e.g. with int. - template - class TightEdgeFilterMap : public MapBase { - protected: - const Graph* g; - NodePotentialMap* node_potential; - EdgeDistanceMap* edge_distance; - public: - TightEdgeFilterMap(Graph& _g, NodePotentialMap& _node_potential, - EdgeDistanceMap& _edge_distance) : - g(&_g), node_potential(&_node_potential), - edge_distance(&_edge_distance) { } - bool operator[](const typename Graph::Edge& e) const { - return ((*node_potential)[g->head(e)] == - (*edge_distance)[e]+(*node_potential)[g->tail(e)]); - } - }; - -} //namespace hugo - -#endif //HUGO_TIGHT_EDGE_FILTER_MAP_H - - diff -r 2d6c8075d9d0 -r 818510fa3d99 src/hugo/bfs.h --- a/src/hugo/bfs.h Wed Sep 29 14:12:26 2004 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,286 +0,0 @@ -/* -*- C++ -*- - * src/hugo/bfs.h - Part of HUGOlib, a generic C++ optimization library - * - * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport - * (Egervary Combinatorial Optimization Research Group, 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 HUGO_BFS_H -#define HUGO_BFS_H - -///\ingroup flowalgs -///\file -///\brief Bfs algorithm. -/// -///\todo Revise Manual. - -#include -#include - -namespace hugo { - -/// \addtogroup flowalgs -/// @{ - - ///%BFS algorithm class. - - ///This class provides an efficient implementation of %BFS algorithm. - ///\param GR The graph type the algorithm runs on. - ///This class does the same as Dijkstra does with constant 1 edge length, - ///but it is faster. - /// - ///\author Alpar Juttner - -#ifdef DOXYGEN - template -#else - template -#endif - class Bfs{ - public: - ///The type of the underlying graph. - typedef GR Graph; - ///\e - typedef typename Graph::Node Node; - ///\e - typedef typename Graph::NodeIt NodeIt; - ///\e - typedef typename Graph::Edge Edge; - ///\e - typedef typename Graph::OutEdgeIt OutEdgeIt; - - ///\brief The type of the map that stores the last - ///edges of the shortest paths. - typedef typename Graph::template NodeMap PredMap; - ///\brief The type of the map that stores the last but one - ///nodes of the shortest paths. - typedef typename Graph::template NodeMap PredNodeMap; - ///The type of the map that stores the dists of the nodes. - typedef typename Graph::template NodeMap DistMap; - - private: - /// Pointer to the underlying graph. - const Graph *G; - ///Pointer to the map of predecessors edges. - PredMap *predecessor; - ///Indicates if \ref predecessor is locally allocated (\c true) or not. - bool local_predecessor; - ///Pointer to the map of predecessors nodes. - PredNodeMap *pred_node; - ///Indicates if \ref pred_node is locally allocated (\c true) or not. - bool local_pred_node; - ///Pointer to the map of distances. - DistMap *distance; - ///Indicates if \ref distance is locally allocated (\c true) or not. - bool local_distance; - - ///The source node of the last execution. - Node source; - - - ///Initializes the maps. - void init_maps() - { - if(!predecessor) { - local_predecessor = true; - predecessor = new PredMap(*G); - } - if(!pred_node) { - local_pred_node = true; - pred_node = new PredNodeMap(*G); - } - if(!distance) { - local_distance = true; - distance = new DistMap(*G); - } - } - - public : - ///Constructor. - - ///\param _G the graph the algorithm will run on. - /// - Bfs(const Graph& _G) : - G(&_G), - predecessor(NULL), local_predecessor(false), - pred_node(NULL), local_pred_node(false), - distance(NULL), local_distance(false) - { } - - ///Destructor. - ~Bfs() - { - if(local_predecessor) delete predecessor; - if(local_pred_node) delete pred_node; - if(local_distance) delete distance; - } - - ///Sets the map storing the predecessor edges. - - ///Sets the map storing the predecessor edges. - ///If you don't use this function before calling \ref run(), - ///it will allocate one. The destuctor deallocates this - ///automatically allocated map, of course. - ///\return (*this) - Bfs &setPredMap(PredMap &m) - { - if(local_predecessor) { - delete predecessor; - local_predecessor=false; - } - predecessor = &m; - return *this; - } - - ///Sets the map storing the predecessor nodes. - - ///Sets the map storing the predecessor nodes. - ///If you don't use this function before calling \ref run(), - ///it will allocate one. The destuctor deallocates this - ///automatically allocated map, of course. - ///\return (*this) - Bfs &setPredNodeMap(PredNodeMap &m) - { - if(local_pred_node) { - delete pred_node; - local_pred_node=false; - } - pred_node = &m; - return *this; - } - - ///Sets the map storing the distances calculated by the algorithm. - - ///Sets the map storing the distances calculated by the algorithm. - ///If you don't use this function before calling \ref run(), - ///it will allocate one. The destuctor deallocates this - ///automatically allocated map, of course. - ///\return (*this) - Bfs &setDistMap(DistMap &m) - { - if(local_distance) { - delete distance; - local_distance=false; - } - distance = &m; - return *this; - } - - ///Runs %BFS algorithm from node \c s. - - ///This method runs the %BFS algorithm from a root node \c s - ///in order to - ///compute a - ///shortest path to each node. The algorithm computes - ///- The %BFS tree. - ///- The distance of each node from the root. - - void run(Node s) { - - init_maps(); - - source = s; - - for ( NodeIt u(*G) ; u!=INVALID ; ++u ) { - predecessor->set(u,INVALID); - pred_node->set(u,INVALID); - } - - int N=G->nodeNum(); - std::vector Q(N); - int Qh=0; - int Qt=0; - - Q[Qh++]=source; - distance->set(s, 0); - do { - Node m; - Node n=Q[Qt++]; - int d= (*distance)[n]+1; - - for(OutEdgeIt e(*G,n);e!=INVALID;++e) - if((m=G->head(e))!=s && (*predecessor)[m]==INVALID) { - Q[Qh++]=m; - predecessor->set(m,e); - pred_node->set(m,n); - distance->set(m,d); - } - } while(Qt!=Qh); - } - - ///The distance of a node from the root. - - ///Returns the distance of a node from the root. - ///\pre \ref run() must be called before using this function. - ///\warning If node \c v in unreachable from the root the return value - ///of this funcion is undefined. - int dist(Node v) const { return (*distance)[v]; } - - ///Returns the 'previous edge' of the %BFS path tree. - - ///For a node \c v it returns the 'previous edge' of the %BFS tree, - ///i.e. it returns the last edge of a shortest path from the root to \c - ///v. It is \ref INVALID - ///if \c v is unreachable from the root or if \c v=s. The - ///%BFS tree used here is equal to the %BFS tree used in - ///\ref predNode(Node v). \pre \ref run() must be called before using - ///this function. - Edge pred(Node v) const { return (*predecessor)[v]; } - - ///Returns the 'previous node' of the %BFS tree. - - ///For a node \c v it returns the 'previous node' on the %BFS tree, - ///i.e. it returns the last but one node from a shortest path from the - ///root to \c /v. It is INVALID if \c v is unreachable from the root or if - ///\c v=s. The shortest path tree used here is equal to the %BFS - ///tree used in \ref pred(Node v). \pre \ref run() must be called before - ///using this function. - Node predNode(Node v) const { return (*pred_node)[v]; } - - ///Returns a reference to the NodeMap of distances. - - ///Returns a reference to the NodeMap of distances. \pre \ref run() must - ///be called before using this function. - const DistMap &distMap() const { return *distance;} - - ///Returns a reference to the %BFS tree map. - - ///Returns a reference to the NodeMap of the edges of the - ///%BFS tree. - ///\pre \ref run() must be called before using this function. - const PredMap &predMap() const { return *predecessor;} - - ///Returns a reference to the map of last but one nodes of shortest paths. - - ///Returns a reference to the NodeMap of the last but one nodes on the - ///%BFS tree. - ///\pre \ref run() must be called before using this function. - const PredNodeMap &predNodeMap() const { return *pred_node;} - - ///Checks if a node is reachable from the root. - - ///Returns \c true if \c v is reachable from the root. - ///\note The root node is reported to be reached! - /// - ///\pre \ref run() must be called before using this function. - /// - bool reached(Node v) { return v==source || (*predecessor)[v]!=INVALID; } - - }; - -/// @} - -} //END OF NAMESPACE HUGO - -#endif - - diff -r 2d6c8075d9d0 -r 818510fa3d99 src/hugo/bin_heap.h --- a/src/hugo/bin_heap.h Wed Sep 29 14:12:26 2004 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,203 +0,0 @@ -/* -*- C++ -*- - * src/hugo/bin_heap.h - Part of HUGOlib, a generic C++ optimization library - * - * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport - * (Egervary Combinatorial Optimization Research Group, 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 HUGO_BIN_HEAP_H -#define HUGO_BIN_HEAP_H - -///\ingroup auxdat -///\file -///\brief Binary Heap implementation. -///\todo It should be documented. - -#include -#include -#include - -namespace hugo { - - /// \addtogroup auxdat - /// @{ - - /// A Binary Heap implementation. - template > - class BinHeap { - - public: - typedef Item ItemType; - // FIXME: stl-ben nem ezt hivjak value_type -nak, hanem a kovetkezot... - typedef Prio PrioType; - typedef std::pair PairType; - typedef ItemIntMap ItemIntMapType; - typedef Compare PrioCompare; - - /** - * Each Item element have a state associated to it. It may be "in heap", - * "pre heap" or "post heap". The later two are indifferent from the - * heap's point of view, but may be useful to the user. - * - * The ItemIntMap _should_ be initialized in such way, that it maps - * PRE_HEAP (-1) to any element to be put in the heap... - */ - ///\todo it is used nowhere - /// - enum state_enum { - IN_HEAP = 0, - PRE_HEAP = -1, - POST_HEAP = -2 - }; - - private: - std::vector data; - Compare comp; - // FIXME: jo ez igy??? - ItemIntMap &iim; - - public: - BinHeap(ItemIntMap &_iim) : iim(_iim) {} - BinHeap(ItemIntMap &_iim, const Compare &_comp) : comp(_comp), iim(_iim) {} - - - int size() const { return data.size(); } - bool empty() const { return data.empty(); } - - private: - static int parent(int i) { return (i-1)/2; } - static int second_child(int i) { return 2*i+2; } - bool less(const PairType &p1, const PairType &p2) const { - return comp(p1.second, p2.second); - } - - int bubble_up(int hole, PairType p); - int bubble_down(int hole, PairType p, int length); - - void move(const PairType &p, int i) { - data[i] = p; - iim.set(p.first, i); - } - - void rmidx(int h) { - int n = data.size()-1; - if( h>=0 && h<=n ) { - iim.set(data[h].first, POST_HEAP); - if ( h=0 ) - s=0; - return state_enum(s); - } - - }; // class BinHeap - - - template - int BinHeap::bubble_up(int hole, PairType 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; - } - - template - int BinHeap::bubble_down(int hole, PairType 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 -#include - -///\ingroup graphmaps -///\file -///\brief Graph maps that construates and destruates -///their elements dynamically. - -namespace hugo { - -/// \addtogroup graphmaps -/// @{ - - /** The ArrayMap template class is graph map structure what - * automatically updates the map when a key is added to or erased from - * the map. This map uses the VectorMap if the ValueType is a primitive - * type and the ArrayMap for the other cases. - * - * The template parameter is the MapRegistry that the maps - * will belong to and the ValueType. - */ - - - /** Macro to implement the DefaultMap. - */ -#define DEFAULT_MAP_BODY(DynMap, Value) \ -{ \ -\ -public: \ -\ -typedef DynMap Parent; \ -\ -typedef typename MapRegistry::Graph Graph; \ -\ -DefaultMap(const Graph& g, MapRegistry& r) : Parent(g, r) {} \ -DefaultMap(const Graph& g, MapRegistry& r, const Value& v) \ - : Parent(g, r, v) {} \ -DefaultMap(const DefaultMap& copy) \ - : Parent(static_cast(copy)) {} \ -template \ -DefaultMap(const DefaultMap& copy) \ - : { \ - Parent::MapBase::operator= \ - (static_cast(copy)); \ - if (Parent::getGraph()) { \ - for (typename Parent::KeyIt it(*Parent::getGraph()); it!=INVALID; ++it) {\ - Parent::add(it); \ - Parent::operator[](it) = copy[it]; \ - } \ - } \ -} \ -DefaultMap& operator=(const DefaultMap& copy) { \ - Parent::operator=(static_cast(copy)); \ - return *this; \ -} \ -template \ -DefaultMap& operator=(const DefaultMap& copy) { \ - if (Parent::getGraph() != copy.getGraph()) { \ - Parent::clear(); \ - Parent::MapBase::operator=(copy); \ - Parent::construct(); \ - } \ - if (Parent::getGraph()) { \ - for (typename Parent::KeyIt it(*Parent::getGraph()); it!=INVALID; ++it) {\ - Parent::operator[](it) = copy[it]; \ - } \ - } \ - return *this; \ -} \ -}; - - - template - class DefaultMap : public ArrayMap - DEFAULT_MAP_BODY(ArrayMap, Type); - - template - class DefaultMap - : public VectorMap - DEFAULT_MAP_BODY(VectorMap, bool); - - template - class DefaultMap - : public VectorMap - DEFAULT_MAP_BODY(VectorMap, char); - - template - class DefaultMap - : public VectorMap - DEFAULT_MAP_BODY(VectorMap, int); - - template - class DefaultMap - : public VectorMap - DEFAULT_MAP_BODY(VectorMap, short); - - template - class DefaultMap - : public VectorMap - DEFAULT_MAP_BODY(VectorMap, long); - - template - class DefaultMap - : public VectorMap - DEFAULT_MAP_BODY(VectorMap, float); - - template - class DefaultMap - : public VectorMap - DEFAULT_MAP_BODY(VectorMap, double); - - template - class DefaultMap - : public VectorMap - DEFAULT_MAP_BODY(VectorMap, long double); - - template - class DefaultMap - : public VectorMap - DEFAULT_MAP_BODY(VectorMap, Type*); - -} - -#endif diff -r 2d6c8075d9d0 -r 818510fa3d99 src/hugo/dfs.h --- a/src/hugo/dfs.h Wed Sep 29 14:12:26 2004 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,290 +0,0 @@ -/* -*- C++ -*- - * src/hugo/dfs.h - Part of HUGOlib, a generic C++ optimization library - * - * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport - * (Egervary Combinatorial Optimization Research Group, 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 HUGO_DFS_H -#define HUGO_DFS_H - -///\ingroup flowalgs -///\file -///\brief %DFS algorithm. -/// -///\todo Revise Manual. - -#include -#include - -namespace hugo { - -/// \addtogroup flowalgs -/// @{ - - ///%DFS algorithm class. - - ///This class provides an efficient implementation of %DFS algorithm. - /// - ///\param GR The graph type the algorithm runs on. - /// - ///\author Alpar Juttner - -#ifdef DOXYGEN - template -#else - template -#endif - class Dfs{ - public: - ///The type of the underlying graph. - typedef GR Graph; - ///\e - typedef typename Graph::Node Node; - ///\e - typedef typename Graph::NodeIt NodeIt; - ///\e - typedef typename Graph::Edge Edge; - ///\e - typedef typename Graph::OutEdgeIt OutEdgeIt; - - ///\brief The type of the map that stores the last - ///edges of the paths on the %DFS tree. - typedef typename Graph::template NodeMap PredMap; - ///\brief The type of the map that stores the last but one - ///nodes of the paths on the %DFS tree. - typedef typename Graph::template NodeMap PredNodeMap; - ///The type of the map that stores the dists of the nodes on the %DFS tree. - typedef typename Graph::template NodeMap DistMap; - - private: - /// Pointer to the underlying graph. - const Graph *G; - ///Pointer to the map of predecessors edges. - PredMap *predecessor; - ///Indicates if \ref predecessor is locally allocated (\c true) or not. - bool local_predecessor; - ///Pointer to the map of predecessors nodes. - PredNodeMap *pred_node; - ///Indicates if \ref pred_node is locally allocated (\c true) or not. - bool local_pred_node; - ///Pointer to the map of distances. - DistMap *distance; - ///Indicates if \ref distance is locally allocated (\c true) or not. - bool local_distance; - - ///The source node of the last execution. - Node source; - - - ///Initializes the maps. - void init_maps() - { - if(!predecessor) { - local_predecessor = true; - predecessor = new PredMap(*G); - } - if(!pred_node) { - local_pred_node = true; - pred_node = new PredNodeMap(*G); - } - if(!distance) { - local_distance = true; - distance = new DistMap(*G); - } - } - - public : - ///Constructor. - - ///\param _G the graph the algorithm will run on. - /// - Dfs(const Graph& _G) : - G(&_G), - predecessor(NULL), local_predecessor(false), - pred_node(NULL), local_pred_node(false), - distance(NULL), local_distance(false) - { } - - ///Destructor. - ~Dfs() - { - if(local_predecessor) delete predecessor; - if(local_pred_node) delete pred_node; - if(local_distance) delete distance; - } - - ///Sets the map storing the predecessor edges. - - ///Sets the map storing the predecessor edges. - ///If you don't use this function before calling \ref run(), - ///it will allocate one. The destuctor deallocates this - ///automatically allocated map, of course. - ///\return (*this) - Dfs &setPredMap(PredMap &m) - { - if(local_predecessor) { - delete predecessor; - local_predecessor=false; - } - predecessor = &m; - return *this; - } - - ///Sets the map storing the predecessor nodes. - - ///Sets the map storing the predecessor nodes. - ///If you don't use this function before calling \ref run(), - ///it will allocate one. The destuctor deallocates this - ///automatically allocated map, of course. - ///\return (*this) - Dfs &setPredNodeMap(PredNodeMap &m) - { - if(local_pred_node) { - delete pred_node; - local_pred_node=false; - } - pred_node = &m; - return *this; - } - - ///Sets the map storing the distances calculated by the algorithm. - - ///Sets the map storing the distances calculated by the algorithm. - ///If you don't use this function before calling \ref run(), - ///it will allocate one. The destuctor deallocates this - ///automatically allocated map, of course. - ///\return (*this) - Dfs &setDistMap(DistMap &m) - { - if(local_distance) { - delete distance; - local_distance=false; - } - distance = &m; - return *this; - } - - ///Runs %DFS algorithm from node \c s. - - ///This method runs the %DFS algorithm from a root node \c s - ///in order to - ///compute - ///- a %DFS tree and - ///- the distance of each node from the root on this tree. - - void run(Node s) { - - init_maps(); - - source = s; - - for ( NodeIt u(*G) ; u!=INVALID ; ++u ) { - predecessor->set(u,INVALID); - pred_node->set(u,INVALID); - } - - int N=G->nodeNum(); - std::vector Q(N); - - int Qh=0; - - G->first(Q[Qh],s); - distance->set(s, 0); - - Node n=s; - Node m; - OutEdgeIt e; - do { - if((e=Q[Qh])!=INVALID) - if((m=G->head(e))!=s && (*predecessor)[m=G->head(e)]==INVALID) { - predecessor->set(m,e); - pred_node->set(m,n); - G->first(Q[++Qh],m); - distance->set(m,Qh); - n=m; - } - else ++Q[Qh]; - else if(--Qh>=0) n=G->tail(Q[Qh]); - } while(Qh>=0); - } - - ///The distance of a node from the root on the %DFS tree. - - ///Returns the distance of a node from the root on the %DFS tree. - ///\pre \ref run() must be called before using this function. - ///\warning If node \c v in unreachable from the root the return value - ///of this funcion is undefined. - int dist(Node v) const { return (*distance)[v]; } - - ///Returns the 'previous edge' of the %DFS path tree. - - ///For a node \c v it returns the last edge of the path on the %DFS tree - ///from the root to \c - ///v. It is \ref INVALID - ///if \c v is unreachable from the root or if \c v=s. The - ///%DFS tree used here is equal to the %DFS tree used in - ///\ref predNode(Node v). \pre \ref run() must be called before using - ///this function. - Edge pred(Node v) const { return (*predecessor)[v]; } - - ///Returns the 'previous node' of the %DFS tree. - - ///For a node \c v it returns the 'previous node' on the %DFS tree, - ///i.e. it returns the last but one node of the path from the - ///root to \c /v on the %DFS tree. - ///It is INVALID if \c v is unreachable from the root or if - ///\c v=s. - ///\pre \ref run() must be called before - ///using this function. - Node predNode(Node v) const { return (*pred_node)[v]; } - - ///Returns a reference to the NodeMap of distances on the %DFS tree. - - ///Returns a reference to the NodeMap of distances on the %DFS tree. - ///\pre \ref run() must - ///be called before using this function. - const DistMap &distMap() const { return *distance;} - - ///Returns a reference to the %DFS tree map. - - ///Returns a reference to the NodeMap of the edges of the - ///%DFS tree. - ///\pre \ref run() must be called before using this function. - const PredMap &predMap() const { return *predecessor;} - - ///Returns a reference to the map of last but one nodes of the %DFS tree. - - ///Returns a reference to the NodeMap of the last but one nodes of the paths - ///on the - ///%DFS tree. - ///\pre \ref run() must be called before using this function. - const PredNodeMap &predNodeMap() const { return *pred_node;} - - ///Checks if a node is reachable from the root. - - ///Returns \c true if \c v is reachable from the root. - ///\note The root node is reported to be reached! - /// - ///\pre \ref run() must be called before using this function. - /// - bool reached(Node v) { return v==source || (*predecessor)[v]!=INVALID; } - - }; - -/// @} - -} //END OF NAMESPACE HUGO - -#endif - - diff -r 2d6c8075d9d0 -r 818510fa3d99 src/hugo/dijkstra.h --- a/src/hugo/dijkstra.h Wed Sep 29 14:12:26 2004 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,344 +0,0 @@ -/* -*- C++ -*- - * src/hugo/dijkstra.h - Part of HUGOlib, a generic C++ optimization library - * - * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport - * (Egervary Combinatorial Optimization Research Group, 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 HUGO_DIJKSTRA_H -#define HUGO_DIJKSTRA_H - -///\ingroup flowalgs -///\file -///\brief Dijkstra algorithm. - -#include -#include - -namespace hugo { - -/// \addtogroup flowalgs -/// @{ - - ///%Dijkstra algorithm class. - - ///This class provides an efficient implementation of %Dijkstra algorithm. - ///The edge lengths are passed to the algorithm using a - ///\ref skeleton::ReadMap "ReadMap", - ///so it is easy to change it to any kind of length. - /// - ///The type of the length is determined by the - ///\ref skeleton::ReadMap::ValueType "ValueType" of the length map. - /// - ///It is also possible to change the underlying priority heap. - /// - ///\param GR The graph type the algorithm runs on. - ///\param LM This read-only - ///EdgeMap - ///determines the - ///lengths of the edges. It is read once for each edge, so the map - ///may involve in relatively time consuming process to compute the edge - ///length if it is necessary. The default map type is - ///\ref skeleton::StaticGraph::EdgeMap "Graph::EdgeMap" - ///\param Heap The heap type used by the %Dijkstra - ///algorithm. The default - ///is using \ref BinHeap "binary heap". - /// - ///\author Jacint Szabo and Alpar Juttner - ///\todo We need a typedef-names should be standardized. (-: - ///\todo Type of \c PredMap, \c PredNodeMap and \c DistMap - ///should not be fixed. (Problematic to solve). - -#ifdef DOXYGEN - template -#else - template , - template class Heap = BinHeap > -#endif - class Dijkstra{ - public: - ///The type of the underlying graph. - typedef GR Graph; - ///\e - typedef typename Graph::Node Node; - ///\e - typedef typename Graph::NodeIt NodeIt; - ///\e - typedef typename Graph::Edge Edge; - ///\e - typedef typename Graph::OutEdgeIt OutEdgeIt; - - ///The type of the length of the edges. - typedef typename LM::ValueType ValueType; - ///The type of the map that stores the edge lengths. - typedef LM LengthMap; - ///\brief The type of the map that stores the last - ///edges of the shortest paths. - typedef typename Graph::template NodeMap PredMap; - ///\brief The type of the map that stores the last but one - ///nodes of the shortest paths. - typedef typename Graph::template NodeMap PredNodeMap; - ///The type of the map that stores the dists of the nodes. - typedef typename Graph::template NodeMap DistMap; - - private: - /// Pointer to the underlying graph. - const Graph *G; - /// Pointer to the length map - const LM *length; - ///Pointer to the map of predecessors edges. - PredMap *predecessor; - ///Indicates if \ref predecessor is locally allocated (\c true) or not. - bool local_predecessor; - ///Pointer to the map of predecessors nodes. - PredNodeMap *pred_node; - ///Indicates if \ref pred_node is locally allocated (\c true) or not. - bool local_pred_node; - ///Pointer to the map of distances. - DistMap *distance; - ///Indicates if \ref distance is locally allocated (\c true) or not. - bool local_distance; - - ///The source node of the last execution. - Node source; - - ///Initializes the maps. - - ///\todo Error if \c G or are \c NULL. What about \c length? - ///\todo Better memory allocation (instead of new). - void init_maps() - { - if(!predecessor) { - local_predecessor = true; - predecessor = new PredMap(*G); - } - if(!pred_node) { - local_pred_node = true; - pred_node = new PredNodeMap(*G); - } - if(!distance) { - local_distance = true; - distance = new DistMap(*G); - } - } - - public : - ///Constructor. - - ///\param _G the graph the algorithm will run on. - ///\param _length the length map used by the algorithm. - Dijkstra(const Graph& _G, const LM& _length) : - G(&_G), length(&_length), - predecessor(NULL), local_predecessor(false), - pred_node(NULL), local_pred_node(false), - distance(NULL), local_distance(false) - { } - - ///Destructor. - ~Dijkstra() - { - if(local_predecessor) delete predecessor; - if(local_pred_node) delete pred_node; - if(local_distance) delete distance; - } - - ///Sets the length map. - - ///Sets the length map. - ///\return (*this) - Dijkstra &setLengthMap(const LM &m) - { - length = &m; - return *this; - } - - ///Sets the map storing the predecessor edges. - - ///Sets the map storing the predecessor edges. - ///If you don't use this function before calling \ref run(), - ///it will allocate one. The destuctor deallocates this - ///automatically allocated map, of course. - ///\return (*this) - Dijkstra &setPredMap(PredMap &m) - { - if(local_predecessor) { - delete predecessor; - local_predecessor=false; - } - predecessor = &m; - return *this; - } - - ///Sets the map storing the predecessor nodes. - - ///Sets the map storing the predecessor nodes. - ///If you don't use this function before calling \ref run(), - ///it will allocate one. The destuctor deallocates this - ///automatically allocated map, of course. - ///\return (*this) - Dijkstra &setPredNodeMap(PredNodeMap &m) - { - if(local_pred_node) { - delete pred_node; - local_pred_node=false; - } - pred_node = &m; - return *this; - } - - ///Sets the map storing the distances calculated by the algorithm. - - ///Sets the map storing the distances calculated by the algorithm. - ///If you don't use this function before calling \ref run(), - ///it will allocate one. The destuctor deallocates this - ///automatically allocated map, of course. - ///\return (*this) - Dijkstra &setDistMap(DistMap &m) - { - if(local_distance) { - delete distance; - local_distance=false; - } - distance = &m; - return *this; - } - - ///Runs %Dijkstra algorithm from node \c s. - - ///This method runs the %Dijkstra algorithm from a root node \c s - ///in order to - ///compute the - ///shortest path to each node. The algorithm computes - ///- The shortest path tree. - ///- The distance of each node from the root. - - void run(Node s) { - - init_maps(); - - source = s; - - for ( NodeIt u(*G) ; u!=INVALID ; ++u ) { - predecessor->set(u,INVALID); - pred_node->set(u,INVALID); - } - - typename GR::template NodeMap heap_map(*G,-1); - - typedef Heap, - std::less > - HeapType; - - HeapType heap(heap_map); - - heap.push(s,0); - - while ( !heap.empty() ) { - - Node v=heap.top(); - ValueType oldvalue=heap[v]; - heap.pop(); - distance->set(v, oldvalue); - - - for(OutEdgeIt e(*G,v); e!=INVALID; ++e) { - Node w=G->head(e); - switch(heap.state(w)) { - case HeapType::PRE_HEAP: - heap.push(w,oldvalue+(*length)[e]); - predecessor->set(w,e); - pred_node->set(w,v); - break; - case HeapType::IN_HEAP: - if ( oldvalue+(*length)[e] < heap[w] ) { - heap.decrease(w, oldvalue+(*length)[e]); - predecessor->set(w,e); - pred_node->set(w,v); - } - break; - case HeapType::POST_HEAP: - break; - } - } - } - } - - ///The distance of a node from the root. - - ///Returns the distance of a node from the root. - ///\pre \ref run() must be called before using this function. - ///\warning If node \c v in unreachable from the root the return value - ///of this funcion is undefined. - ValueType dist(Node v) const { return (*distance)[v]; } - - ///Returns the 'previous edge' of the shortest path tree. - - ///For a node \c v it returns the 'previous edge' of the shortest path tree, - ///i.e. it returns the last edge of a shortest path from the root to \c - ///v. It is \ref INVALID - ///if \c v is unreachable from the root or if \c v=s. The - ///shortest path tree used here is equal to the shortest path tree used in - ///\ref predNode(Node v). \pre \ref run() must be called before using - ///this function. - ///\todo predEdge could be a better name. - Edge pred(Node v) const { return (*predecessor)[v]; } - - ///Returns the 'previous node' of the shortest path tree. - - ///For a node \c v it returns the 'previous node' of the shortest path tree, - ///i.e. it returns the last but one node from a shortest path from the - ///root to \c /v. It is INVALID if \c v is unreachable from the root or if - ///\c v=s. The shortest path tree used here is equal to the shortest path - ///tree used in \ref pred(Node v). \pre \ref run() must be called before - ///using this function. - Node predNode(Node v) const { return (*pred_node)[v]; } - - ///Returns a reference to the NodeMap of distances. - - ///Returns a reference to the NodeMap of distances. \pre \ref run() must - ///be called before using this function. - const DistMap &distMap() const { return *distance;} - - ///Returns a reference to the shortest path tree map. - - ///Returns a reference to the NodeMap of the edges of the - ///shortest path tree. - ///\pre \ref run() must be called before using this function. - const PredMap &predMap() const { return *predecessor;} - - ///Returns a reference to the map of nodes of shortest paths. - - ///Returns a reference to the NodeMap of the last but one nodes of the - ///shortest path tree. - ///\pre \ref run() must be called before using this function. - const PredNodeMap &predNodeMap() const { return *pred_node;} - - ///Checks if a node is reachable from the root. - - ///Returns \c true if \c v is reachable from the root. - ///\note The root node is reported to be reached! - ///\pre \ref run() must be called before using this function. - /// - bool reached(Node v) { return v==source || (*predecessor)[v]!=INVALID; } - - }; - -/// @} - -} //END OF NAMESPACE HUGO - -#endif - - diff -r 2d6c8075d9d0 -r 818510fa3d99 src/hugo/dimacs.h --- a/src/hugo/dimacs.h Wed Sep 29 14:12:26 2004 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,207 +0,0 @@ -/* -*- C++ -*- - * src/hugo/dimacs.h - Part of HUGOlib, a generic C++ optimization library - * - * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport - * (Egervary Combinatorial Optimization Research Group, 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 HUGO_DIMACS_H -#define HUGO_DIMACS_H - -#include -#include -#include -#include - -/// \ingroup misc -/// \file -/// \brief Dimacs file format reader. - -namespace hugo { - - - /// \addtogroup misc - /// @{ - - /// Dimacs min cost flow reader function. - - /// This function reads a min cost flow instance from dimacs format, - /// i.e. from dimacs files having a line starting with \c p \c "min". - /// At the beginning \c g is cleared by \c g.clear(). The edge - /// capacities are written to \c capacity, \c s and \c t are set to - /// the source and the target nodes resp. and the cost of the edges - /// are written to \c cost. - /// - /// \author Marton Makai - template - void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity, - typename Graph::Node &s, typename Graph::Node &t, - CostMap& cost) { - g.clear(); - typename CapacityMap::ValueType _cap; - typename CostMap::ValueType _cost; - char d; - std::string problem; - char c; - int i, j; - std::string str; - int n, m; - typename Graph::Edge e; - std::vector nodes; - while (is>>c) { - switch (c) { - case 'c': //comment - getline(is, str); - break; - case 'p': //problem definition - is >> problem >> n >> m; - getline(is, str); - nodes.resize(n+1); - for (int k=1; k<=n; ++k) nodes[k]=g.addNode(); - break; - case 'n': //node definition - if (problem=="sp") { //shortest path problem - is >> i; - getline(is, str); - s=nodes[i]; - } - if (problem=="max" || problem=="min") { //((max) or (min cost)) flow problem - is >> i >> d; - getline(is, str); - if (d=='s') s=nodes[i]; - if (d=='t') t=nodes[i]; - } - break; - case 'a': - if ( problem == "max" || problem == "sp") { - is >> i >> j >> _cap; - getline(is, str); - e=g.addEdge(nodes[i], nodes[j]); - //capacity.update(); - capacity.set(e, _cap); - } else { - if ( problem == "min" ) { - is >> i >> j >> _cap >> _cost; - getline(is, str); - e=g.addEdge(nodes[i], nodes[j]); - //capacity.update(); - capacity.set(e, _cap); - //cost.update(); - cost.set(e, _cost); - } else { - is >> i >> j; - getline(is, str); - g.addEdge(nodes[i], nodes[j]); - } - } - break; - } - } - } - - - /// Dimacs max flow reader function. - - /// This function reads a max flow instance from dimacs format, - /// i.e. from dimacs files having a line starting with \c p \c - /// "max". At the beginning \c g is cleared by \c g.clear(). The - /// edge capacities are written to \c capacity and \c s and \c t are - /// set to the source and the target nodes. - /// - /// \author Marton Makai - template - void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity, - typename Graph::Node &s, typename Graph::Node &t) { - NullMap n; - readDimacs(is, g, capacity, s, t, n); - } - - - /// Dimacs shortest path reader function. - - /// This function reads a shortest path instance from dimacs format, - /// i.e. from dimacs files having a line starting with \c p \c "sp". - /// At the beginning \c g is cleared by \c g.clear(). The edge - /// capacities are written to \c capacity and \c s is set to the - /// source node. - /// - /// \author Marton Makai - template - void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity, - typename Graph::Node &s) { - NullMap n; - readDimacs(is, g, capacity, s, s, n); - } - - - /// Dimacs capacitated graph reader function. - - /// This function reads an edge capacitated graph instance from - /// dimacs format. At the beginning \c g is cleared by \c g.clear() - /// and the edge capacities are written to \c capacity. - /// - /// \author Marton Makai - template - void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity) { - typename Graph::Node u; - NullMap n; - readDimacs(is, g, capacity, u, u, n); - } - - - /// Dimacs plain graph reader function. - - /// This function reads a graph without any designated nodes and - /// maps from dimacs format, i.e. from dimacs files having a line - /// starting with \c p \c "mat". At the beginning \c g is cleared - /// by \c g.clear(). - /// - /// \author Marton Makai - template - void readDimacs(std::istream& is, Graph &g) { - typename Graph::Node u; - NullMap n; - readDimacs(is, g, n, u, u, n); - } - - - - - /// write matching problem - template - void writeDimacs(std::ostream& os, const Graph &g) { - typedef typename Graph::NodeIt NodeIt; - typedef typename Graph::EdgeIt EdgeIt; - - typename Graph::template NodeMap nodes(g); - - os << "c matching problem" << std::endl; - - int i=1; - for(NodeIt v(g); v!=INVALID; ++v) { - nodes.set(v, i); - ++i; - } - - os << "p mat " << g.nodeNum() << " " << g.edgeNum() << std::endl; - - for(EdgeIt e(g); e!=INVALID; ++e) { - os << "a " << nodes[g.tail(e)] << " " << nodes[g.head(e)] << std::endl; - } - - } - - /// @} - -} //namespace hugo - -#endif //HUGO_DIMACS_H diff -r 2d6c8075d9d0 -r 818510fa3d99 src/hugo/extended_pair.h --- a/src/hugo/extended_pair.h Wed Sep 29 14:12:26 2004 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,80 +0,0 @@ -/* -*- C++ -*- - * src/hugo/extended_pair.h - Part of HUGOlib, a generic C++ optimization library - * - * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport - * (Egervary Combinatorial Optimization Research Group, 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 HUGO_EXTENDED_PAIR_H -#define HUGO_EXTENDED_PAIR_H - -template -struct extended_pair { - typedef T1 first_type; - typedef T2 second_type; - - extended_pair() : first(), second() {} - - extended_pair(A1 f, A2 s) : first(f), second(s) {} - - template - extended_pair(const Pair& pair) : first(pair.first), second(pair.second) {} - - T1 first; - T2 second; -}; - -template -bool operator==(const extended_pair& left, - const extended_pair& right) { - return left.first == right.first && left.second == right.second; -} - -template -bool operator!=(const extended_pair& left, - const extended_pair& right) { - return !(left == right); -} - -template -bool operator<(const extended_pair& left, - const extended_pair& right) { - return left.first < right.first || - (!(right.first -bool operator>(const extended_pair& left, - const extended_pair& right) { - return right < left; -} - -template -bool operator<=(const extended_pair& left, - const extended_pair& right) { - return !(right > left); -} - -template -bool operator>=(const extended_pair& left, - const extended_pair& right) { - return !(right < left); -} - - -#endif diff -r 2d6c8075d9d0 -r 818510fa3d99 src/hugo/fib_heap.h --- a/src/hugo/fib_heap.h Wed Sep 29 14:12:26 2004 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,510 +0,0 @@ -/* -*- C++ -*- - * src/hugo/fib_heap.h - Part of HUGOlib, a generic C++ optimization library - * - * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport - * (Egervary Combinatorial Optimization Research Group, 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 HUGO_FIB_HEAP_H -#define HUGO_FIB_HEAP_H - -///\file -///\ingroup auxdat -///\brief Fibonacci Heap implementation. - -#include -#include -#include - -namespace hugo { - - /// \addtogroup auxdat - /// @{ - - /// Fibonacci Heap. - - ///This class implements the \e Fibonacci \e heap data structure. A \e heap - ///is a data structure for storing items with specified values called \e - ///priorities in such a way that finding the item with minimum priority is - ///efficient. \c Compare specifies the ordering of the priorities. In a heap - ///one can change the priority of an item, add or erase an item, etc. - /// - ///The methods \ref increase and \ref erase are not efficient in a Fibonacci - ///heap. In case of many calls to these operations, it is better to use a - ///\e binary \e heap. - /// - ///\param Item Type of the items to be stored. - ///\param Prio Type of the priority of the items. - ///\param ItemIntMap A read and writable Item int map, for the usage of - ///the heap. - ///\param Compare A class for the ordering of the priorities. The - ///default is \c std::less. - /// - ///\author Jacint Szabo - -#ifdef DOXYGEN - template -#else - template > -#endif - class FibHeap { - public: - typedef Prio PrioType; - - private: - class store; - - std::vector container; - int minimum; - ItemIntMap &iimap; - Compare comp; - int num_items; - - public: - enum state_enum { - IN_HEAP = 0, - PRE_HEAP = -1, - POST_HEAP = -2 - }; - - FibHeap(ItemIntMap &_iimap) : minimum(0), iimap(_iimap), num_items() {} - FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(0), - iimap(_iimap), comp(_comp), num_items() {} - - ///The number of items stored in the heap. - - /** - Returns the number of items stored in the heap. - */ - int size() const { return num_items; } - - ///Checks if the heap stores no items. - - /** - Returns \c true if and only if the heap stores no items. - */ - bool empty() const { return num_items==0; } - - ///\c item gets to the heap with priority \c value independently if \c item was already there. - - /** - This method calls \ref push(\c item, \c value) if \c item is not - stored in the heap and it calls \ref decrease(\c item, \c value) or - \ref increase(\c item, \c value) otherwise. - */ - void set (Item const item, PrioType const value); - - ///Adds \c item to the heap with priority \c value. - - /** - Adds \c item to the heap with priority \c value. - \pre \c item must not be stored in the heap. - */ - void push (Item const item, PrioType const value); - - ///Returns the item with minimum priority relative to \c Compare. - - /** - This method returns the item with minimum priority relative to \c - Compare. - \pre The heap must be nonempty. - */ - Item top() const { return container[minimum].name; } - - ///Returns the minimum priority relative to \c Compare. - - /** - It returns the minimum priority relative to \c Compare. - \pre The heap must be nonempty. - */ - PrioType prio() const { return container[minimum].prio; } - - ///Returns the priority of \c item. - - /** - This function returns the priority of \c item. - \pre \c item must be in the heap. - */ - PrioType& operator[](const Item& item) { - return container[iimap[item]].prio; - } - - ///Returns the priority of \c item. - - /** - It returns the priority of \c item. - \pre \c item must be in the heap. - */ - const PrioType& operator[](const Item& item) const { - return container[iimap[item]].prio; - } - - - ///Deletes the item with minimum priority relative to \c Compare. - - /** - This method deletes the item with minimum priority relative to \c - Compare from the heap. - \pre The heap must be non-empty. - */ - void pop(); - - ///Deletes \c item from the heap. - - /** - This method deletes \c item from the heap, if \c item was already - stored in the heap. It is quite inefficient in Fibonacci heaps. - */ - void erase (const Item& item); - - ///Decreases the priority of \c item to \c value. - - /** - This method decreases the priority of \c item to \c value. - \pre \c item must be stored in the heap with priority at least \c - value relative to \c Compare. - */ - void decrease (Item item, PrioType const value); - - ///Increases the priority of \c item to \c value. - - /** - This method sets the priority of \c item to \c value. Though - there is no precondition on the priority of \c item, this - method should be used only if it is indeed necessary to increase - (relative to \c Compare) the priority of \c item, because this - method is inefficient. - */ - void increase (Item item, PrioType const value) { - erase(item); - push(item, value); - } - - - ///Returns if \c item is in, has already been in, or has never been in the heap. - - /** - This method returns PRE_HEAP if \c item has never been in the - heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP - otherwise. In the latter case it is possible that \c item will - get back to the heap again. - */ - state_enum state(const Item &item) const { - int i=iimap[item]; - if( i>=0 ) { - if ( container[i].in ) i=0; - else i=-2; - } - return state_enum(i); - } - - private: - - void balance(); - void makeroot(int c); - void cut(int a, int b); - void cascade(int a); - void fuse(int a, int b); - void unlace(int a); - - - class store { - friend class FibHeap; - - Item name; - int parent; - int left_neighbor; - int right_neighbor; - int child; - int degree; - bool marked; - bool in; - PrioType prio; - - store() : parent(-1), child(-1), degree(), marked(false), in(true) {} - }; - }; - - - - // ********************************************************************** - // IMPLEMENTATIONS - // ********************************************************************** - - template - void FibHeap::set - (Item const item, PrioType const value) - { - int i=iimap[item]; - if ( i >= 0 && container[i].in ) { - if ( comp(value, container[i].prio) ) decrease(item, value); - if ( comp(container[i].prio, value) ) increase(item, value); - } else push(item, value); - } - - template - void FibHeap::push - (Item const item, PrioType const value) { - int i=iimap[item]; - if ( i < 0 ) { - int s=container.size(); - iimap.set( item, s ); - store st; - st.name=item; - container.push_back(st); - i=s; - } else { - container[i].parent=container[i].child=-1; - container[i].degree=0; - container[i].in=true; - container[i].marked=false; - } - - if ( num_items ) { - container[container[minimum].right_neighbor].left_neighbor=i; - container[i].right_neighbor=container[minimum].right_neighbor; - container[minimum].right_neighbor=i; - container[i].left_neighbor=minimum; - if ( comp( value, container[minimum].prio) ) minimum=i; - } else { - container[i].right_neighbor=container[i].left_neighbor=i; - minimum=i; - } - container[i].prio=value; - ++num_items; - } - - template - void FibHeap::pop() { - /*The first case is that there are only one root.*/ - if ( container[minimum].left_neighbor==minimum ) { - container[minimum].in=false; - if ( container[minimum].degree!=0 ) { - makeroot(container[minimum].child); - minimum=container[minimum].child; - balance(); - } - } else { - int right=container[minimum].right_neighbor; - unlace(minimum); - container[minimum].in=false; - if ( container[minimum].degree > 0 ) { - int left=container[minimum].left_neighbor; - int child=container[minimum].child; - int last_child=container[child].left_neighbor; - - makeroot(child); - - container[left].right_neighbor=child; - container[child].left_neighbor=left; - container[right].left_neighbor=last_child; - container[last_child].right_neighbor=right; - } - minimum=right; - balance(); - } // the case where there are more roots - --num_items; - } - - - template - void FibHeap::erase - (const Item& item) { - int i=iimap[item]; - - if ( i >= 0 && container[i].in ) { - if ( container[i].parent!=-1 ) { - int p=container[i].parent; - cut(i,p); - cascade(p); - } - minimum=i; //As if its prio would be -infinity - pop(); - } - } - - template - void FibHeap::decrease - (Item item, PrioType const value) { - int i=iimap[item]; - container[i].prio=value; - int p=container[i].parent; - - if ( p!=-1 && comp(value, container[p].prio) ) { - cut(i,p); - cascade(p); - } - if ( comp(value, container[minimum].prio) ) minimum=i; - } - - - template - void FibHeap::balance() { - - int maxdeg=int( floor( 2.08*log(double(container.size()))))+1; - - std::vector A(maxdeg,-1); - - /* - *Recall that now minimum does not point to the minimum prio element. - *We set minimum to this during balance(). - */ - int anchor=container[minimum].left_neighbor; - int next=minimum; - bool end=false; - - do { - int active=next; - if ( anchor==active ) end=true; - int d=container[active].degree; - next=container[active].right_neighbor; - - while (A[d]!=-1) { - if( comp(container[active].prio, container[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 ( container[minimum].parent >=0 ) minimum=container[minimum].parent; - int s=minimum; - int m=minimum; - do { - if ( comp(container[s].prio, container[minimum].prio) ) minimum=s; - s=container[s].right_neighbor; - } while ( s != m ); - } - - template - void FibHeap::makeroot - (int c) { - int s=c; - do { - container[s].parent=-1; - s=container[s].right_neighbor; - } while ( s != c ); - } - - - template - void FibHeap::cut - (int a, int b) { - /* - *Replacing a from the children of b. - */ - --container[b].degree; - - if ( container[b].degree !=0 ) { - int child=container[b].child; - if ( child==a ) - container[b].child=container[child].right_neighbor; - unlace(a); - } - - - /*Lacing a to the roots.*/ - int right=container[minimum].right_neighbor; - container[minimum].right_neighbor=a; - container[a].left_neighbor=minimum; - container[a].right_neighbor=right; - container[right].left_neighbor=a; - - container[a].parent=-1; - container[a].marked=false; - } - - - template - void FibHeap::cascade - (int a) - { - if ( container[a].parent!=-1 ) { - int p=container[a].parent; - - if ( container[a].marked==false ) container[a].marked=true; - else { - cut(a,p); - cascade(p); - } - } - } - - - template - void FibHeap::fuse - (int a, int b) { - unlace(b); - - /*Lacing b under a.*/ - container[b].parent=a; - - if (container[a].degree==0) { - container[b].left_neighbor=b; - container[b].right_neighbor=b; - container[a].child=b; - } else { - int child=container[a].child; - int last_child=container[child].left_neighbor; - container[child].left_neighbor=b; - container[b].right_neighbor=child; - container[last_child].right_neighbor=b; - container[b].left_neighbor=last_child; - } - - ++container[a].degree; - - container[b].marked=false; - } - - - /* - *It is invoked only if a has siblings. - */ - template - void FibHeap::unlace - (int a) { - int leftn=container[a].left_neighbor; - int rightn=container[a].right_neighbor; - container[leftn].right_neighbor=rightn; - container[rightn].left_neighbor=leftn; - } - - ///@} - -} //namespace hugo - -#endif //HUGO_FIB_HEAP_H - diff -r 2d6c8075d9d0 -r 818510fa3d99 src/hugo/full_graph.h --- a/src/hugo/full_graph.h Wed Sep 29 14:12:26 2004 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,248 +0,0 @@ -/* -*- C++ -*- - * src/hugo/full_graph.h - Part of HUGOlib, a generic C++ optimization library - * - * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport - * (Egervary Combinatorial Optimization Research Group, 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 HUGO_FULL_GRAPH_H -#define HUGO_FULL_GRAPH_H - -///\ingroup graphs -///\file -///\brief FullGraph and SymFullGraph classes. - -#include -#include - -#include - -#include -#include - -#include - -namespace hugo { - -/// \addtogroup graphs -/// @{ - - ///A full graph class. - - ///This is a simple and fast directed full graph implementation. - ///It is completely static, so you can neither add nor delete either - ///edges or nodes. - ///Thus it conforms to - ///the \ref skeleton::StaticGraph "StaticGraph" concept - ///\sa skeleton::StaticGraph. - ///\todo What about loops? - ///\todo Don't we need SymEdgeMap? - /// - ///\author Alpar Juttner - class FullGraph { - int NodeNum; - int EdgeNum; - public: - - typedef FullGraph Graph; - - class Node; - class Edge; - - class NodeIt; - class EdgeIt; - class OutEdgeIt; - class InEdgeIt; - - - // Create map registries. - CREATE_MAP_REGISTRIES; - // Create node and edge maps. - CREATE_MAPS(ArrayMap); - - public: - - ///Creates a full graph with \c n nodes. - FullGraph(int n) : NodeNum(n), EdgeNum(NodeNum*NodeNum) { } - /// - FullGraph(const FullGraph &_g) - : NodeNum(_g.nodeNum()), EdgeNum(NodeNum*NodeNum) { } - - ///Number of nodes. - int nodeNum() const { return NodeNum; } - ///Number of edges. - int edgeNum() const { return EdgeNum; } - - /// Maximum node ID. - - /// Maximum node ID. - ///\sa id(Node) - int maxNodeId() const { return NodeNum-1; } - /// Maximum edge ID. - - /// Maximum edge ID. - ///\sa id(Edge) - int maxEdgeId() const { return EdgeNum-1; } - - Node tail(Edge e) const { return e.n%NodeNum; } - Node head(Edge e) const { return e.n/NodeNum; } - - NodeIt& first(NodeIt& v) const { - v=NodeIt(*this); return v; } - EdgeIt& first(EdgeIt& e) const { - e=EdgeIt(*this); return e; } - OutEdgeIt& first(OutEdgeIt& e, const Node v) const { - e=OutEdgeIt(*this,v); return e; } - InEdgeIt& first(InEdgeIt& e, const Node v) const { - e=InEdgeIt(*this,v); return e; } - - /// Node ID. - - /// The ID of a valid Node is a nonnegative integer not greater than - /// \ref maxNodeId(). The range of the ID's is not surely continuous - /// and the greatest node ID can be actually less then \ref maxNodeId(). - /// - /// The ID of the \ref INVALID node is -1. - ///\return The ID of the node \c v. - static int id(Node v) { return v.n; } - /// Edge ID. - - /// The ID of a valid Edge is a nonnegative integer not greater than - /// \ref maxEdgeId(). The range of the ID's is not surely continuous - /// and the greatest edge ID can be actually less then \ref maxEdgeId(). - /// - /// The ID of the \ref INVALID edge is -1. - ///\return The ID of the edge \c e. - static int id(Edge e) { return e.n; } - - /// Finds an edge between two nodes. - - /// Finds an edge from node \c u to node \c v. - /// - /// If \c prev is \ref INVALID (this is the default value), then - /// It finds the first edge from \c u to \c v. Otherwise it looks for - /// the next edge from \c u to \c v after \c prev. - /// \return The found edge or INVALID if there is no such an edge. - Edge findEdge(Node u,Node v, Edge prev = INVALID) - { - return prev.n == -1 ? Edge(*this, u.n, v.n) : INVALID; - } - - - class Node { - friend class FullGraph; - template friend class NodeMap; - - friend class Edge; - friend class OutEdgeIt; - friend class InEdgeIt; - friend class SymEdge; - - protected: - int n; - friend int FullGraph::id(Node v); - Node(int nn) {n=nn;} - public: - Node() {} - Node (Invalid) { n=-1; } - bool operator==(const Node i) const {return n==i.n;} - bool operator!=(const Node i) const {return n!=i.n;} - bool operator<(const Node i) const {return n NodeIt. - NodeIt& operator++() { n=(n+2)%(G->NodeNum+1)-1;return *this; } - }; - - class Edge { - friend class FullGraph; - template friend class EdgeMap; - - friend class Node; - friend class NodeIt; - protected: - int n; //NodeNum*head+tail; - friend int FullGraph::id(Edge e); - - Edge(int nn) : n(nn) {} - Edge(const FullGraph &G, int tail, int head) : n(G.NodeNum*head+tail) {} - public: - Edge() { } - Edge (Invalid) { n=-1; } - bool operator==(const Edge i) const {return n==i.n;} - bool operator!=(const Edge i) const {return n!=i.n;} - bool operator<(const Edge i) const {return nNodeNum; if(n>=G->EdgeNum) n=-1; return *this; } - - }; - - class InEdgeIt : public Edge { - const FullGraph *G; - friend class FullGraph; - public: - InEdgeIt() : Edge() { } - InEdgeIt(const FullGraph& _G, Edge e) : Edge(e), G(&_G) { } - InEdgeIt (Invalid i) : Edge(i) { } - InEdgeIt(const FullGraph& _G,Node v) : Edge(v.n*_G.NodeNum), G(&_G) {} - InEdgeIt& operator++() - { if(!((++n)%G->NodeNum)) n=-1; return *this; } - }; - - }; - - /// @} - -} //namespace hugo - - - - -#endif //HUGO_FULL_GRAPH_H diff -r 2d6c8075d9d0 -r 818510fa3d99 src/hugo/graph_wrapper.h --- a/src/hugo/graph_wrapper.h Wed Sep 29 14:12:26 2004 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,1227 +0,0 @@ -/* -*- C++ -*- - * src/hugo/graph_wrapper.h - Part of HUGOlib, a generic C++ optimization library - * - * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport - * (Egervary Combinatorial Optimization Research Group, 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 HUGO_GRAPH_WRAPPER_H -#define HUGO_GRAPH_WRAPPER_H - -///\ingroup gwrappers -///\file -///\brief Several graph wrappers. -/// -///This file contains several useful graph wrapper functions. -/// -///\author Marton Makai - -#include -#include -#include -#include - -namespace hugo { - - // Graph wrappers - - /// \addtogroup gwrappers - /// A main parts of HUGOlib are the different graph structures, - /// generic graph algorithms, graph concepts which couple these, and - /// graph wrappers. While the previous ones are more or less clear, the - /// latter notion needs further explanation. - /// Graph wrappers are graph classes which serve for considering graph - /// structures in different ways. A short example makes the notion much - /// clearer. - /// Suppose that we have an instance \c g of a directed graph - /// type say \c ListGraph and an algorithm - /// \code template int algorithm(const Graph&); \endcode - /// is needed to run on the reversely oriented graph. - /// It may be expensive (in time or in memory usage) to copy - /// \c g with the reverse orientation. - /// Thus, a wrapper class - /// \code template class RevGraphWrapper; \endcode is used. - /// The code looks as follows - /// \code - /// ListGraph g; - /// RevGraphWrapper rgw(g); - /// int result=algorithm(rgw); - /// \endcode - /// After running the algorithm, the original graph \c g - /// remains untouched. Thus the graph wrapper used above is to consider the - /// original graph with reverse orientation. - /// This techniques gives rise to an elegant code, and - /// based on stable graph wrappers, complex algorithms can be - /// implemented easily. - /// In flow, circulation and bipartite matching problems, the residual - /// graph is of particular importance. Combining a wrapper implementing - /// this, shortest path algorithms and minimum mean cycle algorithms, - /// a range of weighted and cardinality optimization algorithms can be - /// obtained. For lack of space, for other examples, - /// the interested user is referred to the detailed documentation of graph - /// wrappers. - /// The behavior of graph wrappers 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 are a model of depend - /// on the graph wrapper, and the wrapped graph(s). - /// If an edge of \c rgw is deleted, this is carried out by - /// deleting the corresponding edge of \c g. But for a residual - /// graph, this operation has no sense. - /// Let we stand one more example here to simplify your work. - /// wrapper class - /// \code template class RevGraphWrapper; \endcode - /// has constructor - /// RevGraphWrapper(Graph& _g). - /// This means that in a situation, - /// when a const ListGraph& reference to a graph is given, - /// then it have to be instantiated with Graph=const ListGraph. - /// \code - /// int algorithm1(const ListGraph& g) { - /// RevGraphWrapper rgw(g); - /// return algorithm2(rgw); - /// } - /// \endcode - - /// \addtogroup gwrappers - /// @{ - - ///Base type for the Graph Wrappers - - ///\warning Graph wrappers are in even more experimental state than the other - ///parts of the lib. Use them at you own risk. - /// - ///This is the base type for the Graph Wrappers. - ///\todo Some more docs... - /// - ///\author Marton Makai - template - class GraphWrapper { - protected: - Graph* graph; - GraphWrapper() : graph(0) { } - void setGraph(Graph& _graph) { graph=&_graph; } - - public: - typedef Graph BaseGraph; - typedef Graph ParentGraph; - - GraphWrapper(Graph& _graph) : graph(&_graph) { } - GraphWrapper(const GraphWrapper& gw) : graph(gw.graph) { } - - typedef typename Graph::Node Node; - class NodeIt : public Node { - const GraphWrapper* gw; - friend class GraphWrapper; - public: - NodeIt() { } - NodeIt(Invalid i) : Node(i) { } - NodeIt(const GraphWrapper& _gw) : - Node(typename Graph::NodeIt(*(_gw.graph))), gw(&_gw) { } - NodeIt(const GraphWrapper& _gw, const Node& n) : - Node(n), gw(&_gw) { } - NodeIt& operator++() { - *(static_cast(this))= - ++(typename Graph::NodeIt(*(gw->graph), *this)); - return *this; - } - }; - typedef typename Graph::Edge Edge; - class OutEdgeIt : public Edge { - const GraphWrapper* gw; - friend class GraphWrapper; - public: - OutEdgeIt() { } - OutEdgeIt(Invalid i) : Edge(i) { } - OutEdgeIt(const GraphWrapper& _gw, const Node& n) : - Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) { } - OutEdgeIt(const GraphWrapper& _gw, const Edge& e) : - Edge(e), gw(&_gw) { } - OutEdgeIt& operator++() { - *(static_cast(this))= - ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); - return *this; - } - }; - class InEdgeIt : public Edge { - const GraphWrapper* gw; - friend class GraphWrapper; - public: - InEdgeIt() { } - InEdgeIt(Invalid i) : Edge(i) { } - InEdgeIt(const GraphWrapper& _gw, const Node& n) : - Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) { } - InEdgeIt(const GraphWrapper& _gw, const Edge& e) : - Edge(e), gw(&_gw) { } - InEdgeIt& operator++() { - *(static_cast(this))= - ++(typename Graph::InEdgeIt(*(gw->graph), *this)); - return *this; - } - }; - class EdgeIt : public Edge { - const GraphWrapper* gw; - friend class GraphWrapper; - public: - EdgeIt() { } - EdgeIt(Invalid i) : Edge(i) { } - EdgeIt(const GraphWrapper& _gw) : - Edge(typename Graph::EdgeIt(*(_gw.graph))), gw(&_gw) { } - EdgeIt(const GraphWrapper& _gw, const Edge& e) : - Edge(e), gw(&_gw) { } - EdgeIt& operator++() { - *(static_cast(this))= - ++(typename Graph::EdgeIt(*(gw->graph), *this)); - return *this; - } - }; - - NodeIt& first(NodeIt& i) const { - i=NodeIt(*this); return i; - } - OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { - i=OutEdgeIt(*this, p); return i; - } - InEdgeIt& first(InEdgeIt& i, const Node& p) const { - i=InEdgeIt(*this, p); return i; - } - EdgeIt& first(EdgeIt& i) const { - i=EdgeIt(*this); return i; - } - - Node tail(const Edge& e) const { - return Node(graph->tail(static_cast(e))); } - Node head(const Edge& e) const { - return Node(graph->head(static_cast(e))); } - - int nodeNum() const { return graph->nodeNum(); } - int edgeNum() const { return graph->edgeNum(); } - - Node addNode() const { return Node(graph->addNode()); } - Edge addEdge(const Node& tail, const Node& head) const { - return Edge(graph->addEdge(tail, head)); } - - void erase(const Node& i) const { graph->erase(i); } - void erase(const Edge& i) const { graph->erase(i); } - - void clear() const { graph->clear(); } - - bool forward(const Edge& e) const { return graph->forward(e); } - bool backward(const Edge& e) const { return graph->backward(e); } - - int id(const Node& v) const { return graph->id(v); } - int id(const Edge& e) const { return graph->id(e); } - - Edge opposite(const Edge& e) const { return Edge(graph->opposite(e)); } - - - IMPORT_NODE_MAP(Graph, *(gw.graph), GraphWrapper, gw); - IMPORT_EDGE_MAP(Graph, *(gw.graph), GraphWrapper, gw); - - - }; - - - - /// A graph wrapper which reverses the orientation of the edges. - - ///\warning Graph wrappers are in even more experimental state than the other - ///parts of the lib. Use them at you own risk. - /// - /// A graph wrapper which reverses the orientation of the edges. - /// Thus \c Graph have to be a directed graph type. - /// - ///\author Marton Makai - template - class RevGraphWrapper : public GraphWrapper { - public: - typedef GraphWrapper Parent; - protected: - RevGraphWrapper() : GraphWrapper() { } - public: - RevGraphWrapper(Graph& _graph) : GraphWrapper(_graph) { } - RevGraphWrapper(const RevGraphWrapper& gw) : Parent(gw) { } - - typedef typename GraphWrapper::Node Node; - typedef typename GraphWrapper::Edge Edge; - //remark: OutEdgeIt and InEdgeIt cannot be typedef-ed to each other - //because this does not work is some of them are not defined in the - //original graph. The problem with this is that typedef-ed stuff - //are instantiated in c++. - class OutEdgeIt : public Edge { - const RevGraphWrapper* gw; - friend class GraphWrapper; - public: - OutEdgeIt() { } - OutEdgeIt(Invalid i) : Edge(i) { } - OutEdgeIt(const RevGraphWrapper& _gw, const Node& n) : - Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) { } - OutEdgeIt(const RevGraphWrapper& _gw, const Edge& e) : - Edge(e), gw(&_gw) { } - OutEdgeIt& operator++() { - *(static_cast(this))= - ++(typename Graph::InEdgeIt(*(gw->graph), *this)); - return *this; - } - }; - class InEdgeIt : public Edge { - const RevGraphWrapper* gw; - friend class GraphWrapper; - public: - InEdgeIt() { } - InEdgeIt(Invalid i) : Edge(i) { } - InEdgeIt(const RevGraphWrapper& _gw, const Node& n) : - Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) { } - InEdgeIt(const RevGraphWrapper& _gw, const Edge& e) : - Edge(e), gw(&_gw) { } - InEdgeIt& operator++() { - *(static_cast(this))= - ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); - return *this; - } - }; - - using GraphWrapper::first; - OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { - i=OutEdgeIt(*this, p); return i; - } - InEdgeIt& first(InEdgeIt& i, const Node& p) const { - i=InEdgeIt(*this, p); return i; - } - - Node tail(const Edge& e) const { - return GraphWrapper::head(e); } - Node head(const Edge& e) const { - return GraphWrapper::tail(e); } - - // KEEP_MAPS(Parent, RevGraphWrapper); - - }; - - - - /// A graph wrapper for hiding nodes and edges from a graph. - - ///\warning Graph wrappers are in even more experimental state than the other - ///parts of the lib. Use them at you own risk. - /// - /// This wrapper shows a graph with filtered node-set and - /// edge-set. Given a bool-valued map on the node-set and one on - /// the edge-set of the graphs, the iterators show only the objects - /// having true value. - /// The quick brown fox iterators jump over - /// the lazy dog nodes or edges if their values for are false in the - /// corresponding bool maps. - /// - ///\author Marton Makai - template - class SubGraphWrapper : public GraphWrapper { - public: - typedef GraphWrapper Parent; - protected: - NodeFilterMap* node_filter_map; - EdgeFilterMap* edge_filter_map; - - SubGraphWrapper() : GraphWrapper(), - node_filter_map(0), edge_filter_map(0) { } - void setNodeFilterMap(NodeFilterMap& _node_filter_map) { - node_filter_map=&_node_filter_map; - } - void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) { - edge_filter_map=&_edge_filter_map; - } - - public: - SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map, - EdgeFilterMap& _edge_filter_map) : - GraphWrapper(_graph), node_filter_map(&_node_filter_map), - edge_filter_map(&_edge_filter_map) { } - - typedef typename GraphWrapper::Node Node; - class NodeIt : public Node { - const SubGraphWrapper* gw; - friend class SubGraphWrapper; - public: - NodeIt() { } - NodeIt(Invalid i) : Node(i) { } - NodeIt(const SubGraphWrapper& _gw) : - Node(typename Graph::NodeIt(*(_gw.graph))), gw(&_gw) { - while (*static_cast(this)!=INVALID && - !(*(gw->node_filter_map))[*this]) - *(static_cast(this))= - ++(typename Graph::NodeIt(*(gw->graph), *this)); - } - NodeIt(const SubGraphWrapper& _gw, - const Node& n) : - Node(n), gw(&_gw) { } - NodeIt& operator++() { - *(static_cast(this))= - ++(typename Graph::NodeIt(*(gw->graph), *this)); - while (*static_cast(this)!=INVALID && - !(*(gw->node_filter_map))[*this]) - *(static_cast(this))= - ++(typename Graph::NodeIt(*(gw->graph), *this)); - return *this; - } - }; - typedef typename GraphWrapper::Edge Edge; - class OutEdgeIt : public Edge { - const SubGraphWrapper* gw; - friend class SubGraphWrapper; - public: - OutEdgeIt() { } - OutEdgeIt(Invalid i) : Edge(i) { } - OutEdgeIt(const SubGraphWrapper& _gw, const Node& n) : - Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) { - while (*static_cast(this)!=INVALID && - !(*(gw->edge_filter_map))[*this]) - *(static_cast(this))= - ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); - } - OutEdgeIt(const SubGraphWrapper& _gw, - const Edge& e) : - Edge(e), gw(&_gw) { } - OutEdgeIt& operator++() { - *(static_cast(this))= - ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); - while (*static_cast(this)!=INVALID && - !(*(gw->edge_filter_map))[*this]) - *(static_cast(this))= - ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); - return *this; - } - }; - class InEdgeIt : public Edge { - const SubGraphWrapper* gw; - friend class SubGraphWrapper; - public: - InEdgeIt() { } - // InEdgeIt(const InEdgeIt& e) : Edge(e), gw(e.gw) { } - InEdgeIt(Invalid i) : Edge(i) { } - InEdgeIt(const SubGraphWrapper& _gw, const Node& n) : - Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) { - while (*static_cast(this)!=INVALID && - !(*(gw->edge_filter_map))[*this]) - *(static_cast(this))= - ++(typename Graph::InEdgeIt(*(gw->graph), *this)); - } - InEdgeIt(const SubGraphWrapper& _gw, - const Edge& e) : - Edge(e), gw(&_gw) { } - InEdgeIt& operator++() { - *(static_cast(this))= - ++(typename Graph::InEdgeIt(*(gw->graph), *this)); - while (*static_cast(this)!=INVALID && - !(*(gw->edge_filter_map))[*this]) - *(static_cast(this))= - ++(typename Graph::InEdgeIt(*(gw->graph), *this)); - return *this; - } - }; - class EdgeIt : public Edge { - const SubGraphWrapper* gw; - friend class SubGraphWrapper; - public: - EdgeIt() { } - EdgeIt(Invalid i) : Edge(i) { } - EdgeIt(const SubGraphWrapper& _gw) : - Edge(typename Graph::EdgeIt(*(_gw.graph))), gw(&_gw) { - while (*static_cast(this)!=INVALID && - !(*(gw->edge_filter_map))[*this]) - *(static_cast(this))= - ++(typename Graph::EdgeIt(*(gw->graph), *this)); - } - EdgeIt(const SubGraphWrapper& _gw, - const Edge& e) : - Edge(e), gw(&_gw) { } - EdgeIt& operator++() { - *(static_cast(this))= - ++(typename Graph::EdgeIt(*(gw->graph), *this)); - while (*static_cast(this)!=INVALID && - !(*(gw->edge_filter_map))[*this]) - *(static_cast(this))= - ++(typename Graph::EdgeIt(*(gw->graph), *this)); - return *this; - } - }; - - NodeIt& first(NodeIt& i) const { - i=NodeIt(*this); return i; - } - OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { - i=OutEdgeIt(*this, p); return i; - } - InEdgeIt& first(InEdgeIt& i, const Node& p) const { - i=InEdgeIt(*this, p); return i; - } - EdgeIt& first(EdgeIt& i) const { - i=EdgeIt(*this); return i; - } - - /// This function hides \c n in the graph, i.e. the iteration - /// jumps over it. This is done by simply setting the value of \c n - /// to be false in the corresponding node-map. - void hide(const Node& n) const { node_filter_map->set(n, false); } - - /// This function hides \c e in the graph, i.e. the iteration - /// jumps over it. This is done by simply setting the value of \c e - /// to be false in the corresponding edge-map. - void hide(const Edge& e) const { edge_filter_map->set(e, false); } - - /// The value of \c n is set to be true in the node-map which stores - /// hide information. If \c n was hidden previuosly, then it is shown - /// again - void unHide(const Node& n) const { node_filter_map->set(n, true); } - - /// The value of \c e is set to be true in the edge-map which stores - /// hide information. If \c e was hidden previuosly, then it is shown - /// again - void unHide(const Edge& e) const { edge_filter_map->set(e, true); } - - /// Returns true if \c n is hidden. - bool hidden(const Node& n) const { return !(*node_filter_map)[n]; } - - /// Returns true if \c n is hidden. - bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; } - - /// \warning This is a linear time operation and works only if - /// \c Graph::NodeIt is defined. - int nodeNum() const { - int i=0; - for (NodeIt n(*this); n!=INVALID; ++n) ++i; - return i; - } - - /// \warning This is a linear time operation and works only if - /// \c Graph::EdgeIt is defined. - int edgeNum() const { - int i=0; - for (EdgeIt e(*this); e!=INVALID; ++e) ++i; - return i; - } - - // KEEP_MAPS(Parent, SubGraphWrapper); - }; - - - - template - class UndirGraphWrapper : public GraphWrapper { - public: - typedef GraphWrapper Parent; - protected: - UndirGraphWrapper() : GraphWrapper() { } - - public: - typedef typename GraphWrapper::Node Node; - typedef typename GraphWrapper::NodeIt NodeIt; - typedef typename GraphWrapper::Edge Edge; - typedef typename GraphWrapper::EdgeIt EdgeIt; - - UndirGraphWrapper(Graph& _graph) : GraphWrapper(_graph) { } - - class OutEdgeIt { - friend class UndirGraphWrapper; - bool out_or_in; //true iff out - typename Graph::OutEdgeIt out; - typename Graph::InEdgeIt in; - public: - OutEdgeIt() { } - OutEdgeIt(const Invalid& i) : Edge(i) { } - OutEdgeIt(const UndirGraphWrapper& _G, const Node& _n) { - out_or_in=true; _G.graph->first(out, _n); - if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, _n); } - } - operator Edge() const { - if (out_or_in) return Edge(out); else return Edge(in); - } - }; - - typedef OutEdgeIt InEdgeIt; - - using GraphWrapper::first; - OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { - i=OutEdgeIt(*this, p); return i; - } - - using GraphWrapper::next; - - OutEdgeIt& next(OutEdgeIt& e) const { - if (e.out_or_in) { - typename Graph::Node n=this->graph->tail(e.out); - this->graph->next(e.out); - if (!this->graph->valid(e.out)) { - e.out_or_in=false; this->graph->first(e.in, n); } - } else { - this->graph->next(e.in); - } - return e; - } - - Node aNode(const OutEdgeIt& e) const { - if (e.out_or_in) return this->graph->tail(e); else - return this->graph->head(e); } - Node bNode(const OutEdgeIt& e) const { - if (e.out_or_in) return this->graph->head(e); else - return this->graph->tail(e); } - - // KEEP_MAPS(Parent, UndirGraphWrapper); - - }; - -// /// \brief An undirected graph template. -// /// -// ///\warning Graph wrappers are in even more experimental state than the other -// ///parts of the lib. Use them at your own risk. -// /// -// /// An undirected graph template. -// /// This class works as an undirected graph and a directed graph of -// /// class \c Graph is used for the physical storage. -// /// \ingroup graphs - template - class UndirGraph : public UndirGraphWrapper { - typedef UndirGraphWrapper Parent; - protected: - Graph gr; - public: - UndirGraph() : UndirGraphWrapper() { - Parent::setGraph(gr); - } - - // KEEP_MAPS(Parent, UndirGraph); - }; - - - - ///\brief A wrapper for composing a subgraph of a - /// bidirected graph made from a directed one. - /// - /// A wrapper for composing a subgraph of a - /// bidirected graph made from a directed one. - /// - ///\warning Graph wrappers are in even more experimental state than the other - ///parts of the lib. Use them at you own risk. - /// - /// Suppose that for a directed graph $G=(V, A)$, - /// two bool valued maps on the edge-set, - /// $forward_filter$, and $backward_filter$ - /// is given, and we are dealing with the directed graph - /// a $G'=(V, \{uv : uv\in A \mbox{ and } forward_filter(uv) \mbox{ is true}\}+\{vu : uv\in A \mbox{ and } backward_filter(uv) \mbox{ is true}\})$. - /// The purpose of writing + instead of union is because parallel - /// edges can arose. - /// In other words, a subgraph of the bidirected graph obtained, which - /// is given by orienting the edges of the original graph in both directions. - /// An example for such a construction is the \c RevGraphWrapper where the - /// forward_filter is everywhere false and the backward_filter is - /// everywhere true. We note that for sake of efficiency, - /// \c RevGraphWrapper is implemented in a different way. - /// But BidirGraphWrapper is obtained from - /// SubBidirGraphWrapper by considering everywhere true - /// valued maps both for forward_filter and backward_filter. - /// Finally, one of the most important applications of SubBidirGraphWrapper - /// is ResGraphWrapper, which stands for the residual graph in directed - /// flow and circulation problems. - /// As wrappers usually, the SubBidirGraphWrapper implements the - /// above mentioned graph structure without its physical storage, - /// that is the whole stuff eats constant memory. - /// As the oppositely directed edges are logically different, - /// the maps are able to attach different values for them. - template - class SubBidirGraphWrapper : public GraphWrapper { - public: - typedef GraphWrapper Parent; - protected: - ForwardFilterMap* forward_filter; - BackwardFilterMap* backward_filter; - - SubBidirGraphWrapper() : GraphWrapper() { } - void setForwardFilterMap(ForwardFilterMap& _forward_filter) { - forward_filter=&_forward_filter; - } - void setBackwardFilterMap(BackwardFilterMap& _backward_filter) { - backward_filter=&_backward_filter; - } - - public: - - SubBidirGraphWrapper(Graph& _graph, ForwardFilterMap& _forward_filter, - BackwardFilterMap& _backward_filter) : - GraphWrapper(_graph), - forward_filter(&_forward_filter), backward_filter(&_backward_filter) { } - SubBidirGraphWrapper(const SubBidirGraphWrapper& gw) : - Parent(gw), - forward_filter(gw.forward_filter), - backward_filter(gw.backward_filter) { } - - class Edge; - class OutEdgeIt; - friend class Edge; - friend class OutEdgeIt; - - template class EdgeMap; - - typedef typename GraphWrapper::Node Node; - - typedef typename Graph::Edge GraphEdge; - /// SubBidirGraphWrapper<..., ..., ...>::Edge is inherited from - /// Graph::Edge. It contains an extra bool flag which is true - /// if and only if the - /// edge is the backward version of the original edge. - class Edge : public Graph::Edge { - friend class SubBidirGraphWrapper; - template friend class EdgeMap; - protected: - bool backward; //true, iff backward - public: - Edge() { } - /// \todo =false is needed, or causes problems? - /// If \c _backward is false, then we get an edge corresponding to the - /// original one, otherwise its oppositely directed pair is obtained. - Edge(const typename Graph::Edge& e, bool _backward/*=false*/) : - Graph::Edge(e), backward(_backward) { } - Edge(Invalid i) : Graph::Edge(i), backward(true) { } - bool operator==(const Edge& v) const { - return (this->backward==v.backward && - static_cast(*this)== - static_cast(v)); - } - bool operator!=(const Edge& v) const { - return (this->backward!=v.backward || - static_cast(*this)!= - static_cast(v)); - } - }; - - class OutEdgeIt : public Edge { - friend class SubBidirGraphWrapper; - protected: - const SubBidirGraphWrapper* gw; - public: - OutEdgeIt() { } - OutEdgeIt(Invalid i) : Edge(i) { } - OutEdgeIt(const SubBidirGraphWrapper& _gw, const Node& n) : - Edge(typename Graph::OutEdgeIt(*(_gw.graph), n), false), gw(&_gw) { - while (*static_cast(this)!=INVALID && - !(*(gw->forward_filter))[*this]) - *(static_cast(this))= - ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); - if (*static_cast(this)==INVALID) { - *static_cast(this)= - Edge(typename Graph::InEdgeIt(*(_gw.graph), n), true); - while (*static_cast(this)!=INVALID && - !(*(gw->backward_filter))[*this]) - *(static_cast(this))= - ++(typename Graph::InEdgeIt(*(gw->graph), *this)); - } - } - OutEdgeIt(const SubBidirGraphWrapper& _gw, const Edge& e) : - Edge(e), gw(&_gw) { } - OutEdgeIt& operator++() { - if (!this->backward) { - Node n=gw->tail(*this); - *(static_cast(this))= - ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); - while (*static_cast(this)!=INVALID && - !(*(gw->forward_filter))[*this]) - *(static_cast(this))= - ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); - if (*static_cast(this)==INVALID) { - *static_cast(this)= - Edge(typename Graph::InEdgeIt(*(gw->graph), n), true); - while (*static_cast(this)!=INVALID && - !(*(gw->backward_filter))[*this]) - *(static_cast(this))= - ++(typename Graph::InEdgeIt(*(gw->graph), *this)); - } - } else { - *(static_cast(this))= - ++(typename Graph::InEdgeIt(*(gw->graph), *this)); - while (*static_cast(this)!=INVALID && - !(*(gw->backward_filter))[*this]) - *(static_cast(this))= - ++(typename Graph::InEdgeIt(*(gw->graph), *this)); - } - return *this; - } - }; - - class InEdgeIt : public Edge { - friend class SubBidirGraphWrapper; - protected: - const SubBidirGraphWrapper* gw; - public: - InEdgeIt() { } - InEdgeIt(Invalid i) : Edge(i) { } - InEdgeIt(const SubBidirGraphWrapper& _gw, const Node& n) : - Edge(typename Graph::InEdgeIt(*(_gw.graph), n), false), gw(&_gw) { - while (*static_cast(this)!=INVALID && - !(*(gw->forward_filter))[*this]) - *(static_cast(this))= - ++(typename Graph::InEdgeIt(*(gw->graph), *this)); - if (*static_cast(this)==INVALID) { - *static_cast(this)= - Edge(typename Graph::OutEdgeIt(*(_gw.graph), n), true); - while (*static_cast(this)!=INVALID && - !(*(gw->backward_filter))[*this]) - *(static_cast(this))= - ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); - } - } - InEdgeIt(const SubBidirGraphWrapper& _gw, const Edge& e) : - Edge(e), gw(&_gw) { } - InEdgeIt& operator++() { - if (!this->backward) { - Node n=gw->tail(*this); - *(static_cast(this))= - ++(typename Graph::InEdgeIt(*(gw->graph), *this)); - while (*static_cast(this)!=INVALID && - !(*(gw->forward_filter))[*this]) - *(static_cast(this))= - ++(typename Graph::InEdgeIt(*(gw->graph), *this)); - if (*static_cast(this)==INVALID) { - *static_cast(this)= - Edge(typename Graph::OutEdgeIt(*(gw->graph), n), true); - while (*static_cast(this)!=INVALID && - !(*(gw->backward_filter))[*this]) - *(static_cast(this))= - ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); - } - } else { - *(static_cast(this))= - ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); - while (*static_cast(this)!=INVALID && - !(*(gw->backward_filter))[*this]) - *(static_cast(this))= - ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); - } - return *this; - } - }; - - class EdgeIt : public Edge { - friend class SubBidirGraphWrapper; - protected: - const SubBidirGraphWrapper* gw; - public: - EdgeIt() { } - EdgeIt(Invalid i) : Edge(i) { } - EdgeIt(const SubBidirGraphWrapper& _gw) : - Edge(typename Graph::EdgeIt(*(_gw.graph)), false), gw(&_gw) { - while (*static_cast(this)!=INVALID && - !(*(gw->forward_filter))[*this]) - *(static_cast(this))= - ++(typename Graph::EdgeIt(*(gw->graph), *this)); - if (*static_cast(this)==INVALID) { - *static_cast(this)= - Edge(typename Graph::EdgeIt(*(_gw.graph)), true); - while (*static_cast(this)!=INVALID && - !(*(gw->backward_filter))[*this]) - *(static_cast(this))= - ++(typename Graph::EdgeIt(*(gw->graph), *this)); - } - } - EdgeIt(const SubBidirGraphWrapper& _gw, const Edge& e) : - Edge(e), gw(&_gw) { } - EdgeIt& operator++() { - if (!this->backward) { - *(static_cast(this))= - ++(typename Graph::EdgeIt(*(gw->graph), *this)); - while (*static_cast(this)!=INVALID && - !(*(gw->forward_filter))[*this]) - *(static_cast(this))= - ++(typename Graph::EdgeIt(*(gw->graph), *this)); - if (*static_cast(this)==INVALID) { - *static_cast(this)= - Edge(typename Graph::EdgeIt(*(gw->graph)), true); - while (*static_cast(this)!=INVALID && - !(*(gw->backward_filter))[*this]) - *(static_cast(this))= - ++(typename Graph::EdgeIt(*(gw->graph), *this)); - } - } else { - *(static_cast(this))= - ++(typename Graph::EdgeIt(*(gw->graph), *this)); - while (*static_cast(this)!=INVALID && - !(*(gw->backward_filter))[*this]) - *(static_cast(this))= - ++(typename Graph::EdgeIt(*(gw->graph), *this)); - } - return *this; - } - }; - - using GraphWrapper::first; - OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { - i=OutEdgeIt(*this, p); return i; - } - InEdgeIt& first(InEdgeIt& i, const Node& p) const { - i=InEdgeIt(*this, p); return i; - } - EdgeIt& first(EdgeIt& i) const { - i=EdgeIt(*this); return i; - } - - - Node tail(Edge e) const { - return ((!e.backward) ? this->graph->tail(e) : this->graph->head(e)); } - Node head(Edge e) const { - return ((!e.backward) ? this->graph->head(e) : this->graph->tail(e)); } - - /// Gives back the opposite edge. - Edge opposite(const Edge& e) const { - Edge f=e; - f.backward=!f.backward; - return f; - } - - /// \warning This is a linear time operation and works only if - /// \c Graph::EdgeIt is defined. - int edgeNum() const { - int i=0; - for (EdgeIt e(*this); e!=INVALID; ++e) ++i; - return i; - } - - bool forward(const Edge& e) const { return !e.backward; } - bool backward(const Edge& e) const { return e.backward; } - - - template - /// \c SubBidirGraphWrapper<..., ..., ...>::EdgeMap contains two - /// Graph::EdgeMap one for the forward edges and - /// one for the backward edges. - class EdgeMap { - template friend class EdgeMap; - typename Graph::template EdgeMap forward_map, backward_map; - public: - typedef T ValueType; - typedef Edge KeyType; - - EdgeMap(const SubBidirGraphWrapper& g) : - forward_map(*(g.graph)), backward_map(*(g.graph)) { } - - EdgeMap(const SubBidirGraphWrapper& g, T a) : - forward_map(*(g.graph), a), backward_map(*(g.graph), a) { } - - template - EdgeMap(const EdgeMap& copy) - : forward_map(copy.forward_map), backward_map(copy.backward_map) {} - - template - EdgeMap& operator=(const EdgeMap& copy) { - forward_map = copy.forward_map; - backward_map = copy.backward_map; - return *this; - } - - void set(Edge e, T a) { - if (!e.backward) - forward_map.set(e, a); - else - backward_map.set(e, a); - } - - typename Graph::template EdgeMap::ConstReferenceType - operator[](Edge e) const { - if (!e.backward) - return forward_map[e]; - else - return backward_map[e]; - } - - typename Graph::template EdgeMap::ReferenceType - operator[](Edge e) { - if (!e.backward) - return forward_map[e]; - else - return backward_map[e]; - } - - void update() { - forward_map.update(); - backward_map.update(); - } - }; - - - // KEEP_NODE_MAP(Parent, SubBidirGraphWrapper); - - }; - - - ///\brief A wrapper for composing bidirected graph from a directed one. - /// - ///\warning Graph wrappers are in even more experimental state than the other - ///parts of the lib. Use them at you own risk. - /// - /// A wrapper for composing bidirected graph from a directed one. - /// A bidirected graph is composed over the directed one without physical - /// storage. As the oppositely directed edges are logically different ones - /// the maps are able to attach different values for them. - template - class BidirGraphWrapper : - public SubBidirGraphWrapper< - Graph, - ConstMap, - ConstMap > { - public: - typedef SubBidirGraphWrapper< - Graph, - ConstMap, - ConstMap > Parent; - protected: - ConstMap cm; - - BidirGraphWrapper() : Parent(), cm(true) { - Parent::setForwardFilterMap(cm); - Parent::setBackwardFilterMap(cm); - } - public: - BidirGraphWrapper(Graph& _graph) : Parent() { - Parent::setGraph(_graph); - Parent::setForwardFilterMap(cm); - Parent::setBackwardFilterMap(cm); - } - - int edgeNum() const { - return 2*this->graph->edgeNum(); - } - // KEEP_MAPS(Parent, BidirGraphWrapper); - }; - - - /// \brief A bidirected graph template. - /// - ///\warning Graph wrappers are in even more experimental state than the other - ///parts of the lib. Use them at you own risk. - /// - /// A bidirected graph template. - /// Such a bidirected graph stores each pair of oppositely directed edges - /// ones in the memory, i.e. a directed graph of type - /// \c Graph is used for that. - /// As the oppositely directed edges are logically different ones - /// the maps are able to attach different values for them. - /// \ingroup graphs - template - class BidirGraph : public BidirGraphWrapper { - public: - typedef UndirGraphWrapper Parent; - protected: - Graph gr; - public: - BidirGraph() : BidirGraphWrapper() { - Parent::setGraph(gr); - } - // KEEP_MAPS(Parent, BidirGraph); - }; - - - - template - class ResForwardFilter { - // const Graph* graph; - const CapacityMap* capacity; - const FlowMap* flow; - public: - ResForwardFilter(/*const Graph& _graph, */ - const CapacityMap& _capacity, const FlowMap& _flow) : - /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { } - ResForwardFilter() : /*graph(0),*/ capacity(0), flow(0) { } - void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; } - void setFlow(const FlowMap& _flow) { flow=&_flow; } - bool operator[](const typename Graph::Edge& e) const { - return (Number((*flow)[e]) < Number((*capacity)[e])); - } - }; - - template - class ResBackwardFilter { - const CapacityMap* capacity; - const FlowMap* flow; - public: - ResBackwardFilter(/*const Graph& _graph,*/ - const CapacityMap& _capacity, const FlowMap& _flow) : - /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { } - ResBackwardFilter() : /*graph(0),*/ capacity(0), flow(0) { } - void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; } - void setFlow(const FlowMap& _flow) { flow=&_flow; } - bool operator[](const typename Graph::Edge& e) const { - return (Number(0) < Number((*flow)[e])); - } - }; - - - /// A wrapper for composing the residual graph for directed flow and circulation problems. - - ///\warning Graph wrappers are in even more experimental state than the other - ///parts of the lib. Use them at you own risk. - /// - /// A wrapper for composing the residual graph for directed flow and circulation problems. - template - class ResGraphWrapper : - public SubBidirGraphWrapper< - Graph, - ResForwardFilter, - ResBackwardFilter > { - public: - typedef SubBidirGraphWrapper< - Graph, - ResForwardFilter, - ResBackwardFilter > Parent; - protected: - const CapacityMap* capacity; - FlowMap* flow; - ResForwardFilter forward_filter; - ResBackwardFilter backward_filter; - ResGraphWrapper() : Parent(), - capacity(0), flow(0) { } - void setCapacityMap(const CapacityMap& _capacity) { - capacity=&_capacity; - forward_filter.setCapacity(_capacity); - backward_filter.setCapacity(_capacity); - } - void setFlowMap(FlowMap& _flow) { - flow=&_flow; - forward_filter.setFlow(_flow); - backward_filter.setFlow(_flow); - } - public: - ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity, - FlowMap& _flow) : - Parent(), capacity(&_capacity), flow(&_flow), - forward_filter(/*_graph,*/ _capacity, _flow), - backward_filter(/*_graph,*/ _capacity, _flow) { - Parent::setGraph(_graph); - Parent::setForwardFilterMap(forward_filter); - Parent::setBackwardFilterMap(backward_filter); - } - - typedef typename Parent::Edge Edge; - - void augment(const Edge& e, Number a) const { - if (Parent::forward(e)) - flow->set(e, (*flow)[e]+a); - else - flow->set(e, (*flow)[e]-a); - } - - /// \brief Residual capacity map. - /// - /// In generic residual graphs the residual capacity can be obtained - /// as a map. - class ResCap { - protected: - const ResGraphWrapper* res_graph; - public: - typedef Number ValueType; - typedef Edge KeyType; - ResCap(const ResGraphWrapper& - _res_graph) : res_graph(&_res_graph) { } - Number operator[](const Edge& e) const { - if (res_graph->forward(e)) - return (*(res_graph->capacity))[e]-(*(res_graph->flow))[e]; - else - return (*(res_graph->flow))[e]; - } - }; - - // KEEP_MAPS(Parent, ResGraphWrapper); - }; - - - /// For blocking flows. - - ///\warning Graph wrappers are in even more experimental state than the other - ///parts of the lib. Use them at you own risk. - /// - /// This graph wrapper is used for on-the-fly - /// Dinits blocking flow computations. - /// For each node, an out-edge is stored which is used when the - /// \code - /// OutEdgeIt& first(OutEdgeIt&, const Node&) - /// \endcode - /// is called. - /// - /// \author Marton Makai - template - class ErasingFirstGraphWrapper : public GraphWrapper { - public: - typedef GraphWrapper Parent; - protected: - FirstOutEdgesMap* first_out_edges; - public: - ErasingFirstGraphWrapper(Graph& _graph, - FirstOutEdgesMap& _first_out_edges) : - GraphWrapper(_graph), first_out_edges(&_first_out_edges) { } - - typedef typename GraphWrapper::Node Node; - typedef typename GraphWrapper::Edge Edge; - class OutEdgeIt : public Edge { - friend class GraphWrapper; - friend class ErasingFirstGraphWrapper; - const ErasingFirstGraphWrapper* gw; - public: - OutEdgeIt() { } - OutEdgeIt(Invalid i) : Edge(i) { } - OutEdgeIt(const ErasingFirstGraphWrapper& _gw, - const Node& n) : - Edge((*(_gw.first_out_edges))[n]), gw(&_gw) { } - OutEdgeIt(const ErasingFirstGraphWrapper& _gw, - const Edge& e) : - Edge(e), gw(&_gw) { } - OutEdgeIt& operator++() { - *(static_cast(this))= - ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); - return *this; - } - }; - - using GraphWrapper::first; - OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { - i=OutEdgeIt(*this, p); return i; - } - void erase(const Edge& e) const { - Node n=tail(e); - typename Graph::OutEdgeIt f(*Parent::graph, n); - ++f; - first_out_edges->set(n, f); - } - - // KEEP_MAPS(Parent, ErasingFirstGraphWrapper); - }; - - ///@} - -} //namespace hugo - -#endif //HUGO_GRAPH_WRAPPER_H - diff -r 2d6c8075d9d0 -r 818510fa3d99 src/hugo/invalid.h --- a/src/hugo/invalid.h Wed Sep 29 14:12:26 2004 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,52 +0,0 @@ -/* -*- C++ -*- - * src/hugo/invalid.h - Part of HUGOlib, a generic C++ optimization library - * - * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport - * (Egervary Combinatorial Optimization Research Group, 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 HUGO_INVALID_H -#define HUGO_INVALID_H - -///\file -///\brief Definition of INVALID. - -namespace hugo { - - /// Dummy type to make it easier to make invalid iterators. - - /// See \ref INVALID, how to use it. - - struct Invalid { - public: - bool operator==(Invalid) { return true; } - bool operator!=(Invalid) { return false; } - bool operator< (Invalid) { return false; } - }; - - /// Invalid iterators. - - /// \ref Invalid is a global type that converts to each iterator - /// in such a way that the value of the target iterator will be invalid. - - // It is also used to convert the \c INVALID constant to the - // node iterator that makes is possible to write - - //extern Invalid INVALID; - - //const Invalid &INVALID = *(Invalid *)0; - const Invalid INVALID = Invalid(); - -} //namespace hugo - -#endif - diff -r 2d6c8075d9d0 -r 818510fa3d99 src/hugo/kruskal.h --- a/src/hugo/kruskal.h Wed Sep 29 14:12:26 2004 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,348 +0,0 @@ -/* -*- C++ -*- - * src/hugo/kruskal.h - Part of HUGOlib, a generic C++ optimization library - * - * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport - * (Egervary Combinatorial Optimization Research Group, 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 HUGO_KRUSKAL_H -#define HUGO_KRUSKAL_H - -#include -#include - -/** -@defgroup spantree Minimum Cost Spanning Tree Algorithms -@ingroup galgs -\brief This group containes the algorithms for finding a minimum cost spanning -tree in a graph - -This group containes the algorithms for finding a minimum cost spanning -tree in a graph -*/ - -///\ingroup spantree -///\file -///\brief Kruskal's algorithm to compute a minimum cost tree -/// -///Kruskal's algorithm to compute a minimum cost tree. - -namespace hugo { - - /// \addtogroup spantree - /// @{ - - /// Kruskal's algorithm to find a minimum cost tree of a graph. - - /// This function runs Kruskal's algorithm to find a minimum cost tree. - /// \param G The graph the algorithm runs on. The algorithm considers the - /// graph to be undirected, the direction of the edges are not used. - /// - /// \param in This object is used to describe the edge costs. It must - /// be an STL compatible 'Forward Container' - /// with std::pair as its value_type, - /// where X is the type of the costs. It must contain every edge in - /// cost-ascending order. - ///\par - /// For the sake of simplicity, there is a helper class KruskalMapInput, - /// which converts a - /// simple edge map to an input of this form. Alternatively, you can use - /// the function \ref kruskalEdgeMap to compute the minimum cost tree if - /// the edge costs are given by an edge map. - /// - /// \retval out This must be a writable \c bool edge map. - /// After running the algorithm - /// this will contain the found minimum cost spanning tree: the value of an - /// edge will be set to \c true if it belongs to the tree, otherwise it will - /// be set to \c false. The value of each edge will be set exactly once. - /// - /// \return The cost of the found tree. - - template - typename IN::value_type::second_type - kruskal(GR const& G, IN const& in, - OUT& out) - { - typedef typename IN::value_type::second_type EdgeCost; - typedef typename GR::template NodeMap NodeIntMap; - typedef typename GR::Node Node; - - NodeIntMap comp(G, -1); - UnionFind uf(comp); - - EdgeCost tot_cost = 0; - for (typename IN::const_iterator p = in.begin(); - p!=in.end(); ++p ) { - if ( uf.join(G.head((*p).first), - G.tail((*p).first)) ) { - out.set((*p).first, true); - tot_cost += (*p).second; - } - else { - out.set((*p).first, false); - } - } - return tot_cost; - } - - /* A work-around for running Kruskal with const-reference bool maps... */ - - /// Helper class for calling kruskal with "constant" output map. - - /// Helper class for calling kruskal with output maps constructed - /// on-the-fly. - /// - /// A typical examle is the following call: - /// kruskal(G, some_input, makeSequenceOutput(iterator)). - /// Here, the third argument is a temporary object (which wraps around an - /// iterator with a writable bool map interface), and thus by rules of C++ - /// is a \c const object. To enable call like this exist this class and - /// the prototype of the \ref kruskal() function with const& OUT - /// third argument. - template - class NonConstMapWr { - const Map &m; - public: - typedef typename Map::ValueType ValueType; - - NonConstMapWr(const Map &_m) : m(_m) {} - - template - void set(KeyType const& k, ValueType const &v) const { m.set(k,v); } - }; - - template - inline - typename IN::value_type::second_type - kruskal(GR const& G, IN const& edges, OUT const& out_map) - { - NonConstMapWr map_wr(out_map); - return kruskal(G, edges, map_wr); - } - - /* ** ** Input-objects ** ** */ - - /// Kruskal input source. - - /// Kruskal input source. - /// - /// In most cases you possibly want to use the \ref kruskalEdgeMap() instead. - /// - /// \sa makeKruskalMapInput() - /// - ///\param GR The type of the graph the algorithm runs on. - ///\param Map An edge map containing the cost of the edges. - ///\par - ///The cost type can be any type satisfying - ///the STL 'LessThan comparable' - ///concept if it also has an operator+() implemented. (It is necessary for - ///computing the total cost of the tree). - /// - template - class KruskalMapInput - : public std::vector< std::pair > { - - public: - typedef std::vector< std::pair > Parent; - typedef typename Parent::value_type value_type; - - private: - class comparePair { - public: - bool operator()(const value_type& a, - const value_type& b) { - return a.second < b.second; - } - }; - - public: - - void sort() { - std::sort(this->begin(), this->end(), comparePair()); - } - - KruskalMapInput(GR const& G, Map const& m) { - typedef typename GR::EdgeIt EdgeIt; - - for(EdgeIt e(G);e!=INVALID;++e) push_back(value_type(e, m[e])); - sort(); - } - }; - - /// Creates a KruskalMapInput object for \ref kruskal() - - /// It makes is easier to use - /// \ref KruskalMapInput by making it unnecessary - /// to explicitly give the type of the parameters. - /// - /// In most cases you possibly - /// want to use the function kruskalEdgeMap() instead. - /// - ///\param G The type of the graph the algorithm runs on. - ///\param m An edge map containing the cost of the edges. - ///\par - ///The cost type can be any type satisfying the - ///STL 'LessThan Comparable' - ///concept if it also has an operator+() implemented. (It is necessary for - ///computing the total cost of the tree). - /// - ///\return An appropriate input source for \ref kruskal(). - /// - template - inline - KruskalMapInput makeKruskalMapInput(const GR &G,const Map &m) - { - return KruskalMapInput(G,m); - } - - - - /* ** ** Output-objects: simple writable bool maps ** ** */ - - - - /// A writable bool-map that makes a sequence of "true" keys - - /// A writable bool-map that creates a sequence out of keys that receives - /// the value "true". - /// - /// \sa makeKruskalSequenceOutput() - /// - /// Very often, when looking for a min cost spanning tree, we want as - /// output a container containing the edges of the found tree. For this - /// purpose exist this class that wraps around an STL iterator with a - /// writable bool map interface. When a key gets value "true" this key - /// is added to sequence pointed by the iterator. - /// - /// A typical usage: - /// \code - /// std::vector v; - /// kruskal(g, input, makeKruskalSequenceOutput(back_inserter(v))); - /// \endcode - /// - /// For the most common case, when the input is given by a simple edge - /// map and the output is a sequence of the tree edges, a special - /// wrapper function exists: \ref kruskalEdgeMap_IteratorOut(). - /// - /// \warning Not a regular property map, as it doesn't know its KeyType - - template - class KruskalSequenceOutput { - mutable Iterator it; - - public: - typedef bool ValueType; - - KruskalSequenceOutput(Iterator const &_it) : it(_it) {} - - template - void set(KeyType const& k, bool v) const { if(v) {*it=k; ++it;} } - }; - - template - inline - KruskalSequenceOutput - makeKruskalSequenceOutput(Iterator it) { - return KruskalSequenceOutput(it); - } - - - - /* ** ** Wrapper funtions ** ** */ - - - - /// \brief Wrapper function to kruskal(). - /// Input is from an edge map, output is a plain bool map. - /// - /// Wrapper function to kruskal(). - /// Input is from an edge map, output is a plain bool map. - /// - ///\param G The type of the graph the algorithm runs on. - ///\param in An edge map containing the cost of the edges. - ///\par - ///The cost type can be any type satisfying the - ///STL 'LessThan Comparable' - ///concept if it also has an operator+() implemented. (It is necessary for - ///computing the total cost of the tree). - /// - /// \retval out This must be a writable \c bool edge map. - /// After running the algorithm - /// this will contain the found minimum cost spanning tree: the value of an - /// edge will be set to \c true if it belongs to the tree, otherwise it will - /// be set to \c false. The value of each edge will be set exactly once. - /// - /// \return The cost of the found tree. - - template - inline - typename IN::ValueType - kruskalEdgeMap(GR const& G, - IN const& in, - RET &out) { - return kruskal(G, - KruskalMapInput(G,in), - out); - } - - /// \brief Wrapper function to kruskal(). - /// Input is from an edge map, output is an STL Sequence. - /// - /// Wrapper function to kruskal(). - /// Input is from an edge map, output is an STL Sequence. - /// - ///\param G The type of the graph the algorithm runs on. - ///\param in An edge map containing the cost of the edges. - ///\par - ///The cost type can be any type satisfying the - ///STL 'LessThan Comparable' - ///concept if it also has an operator+() implemented. (It is necessary for - ///computing the total cost of the tree). - /// - /// \retval out This must be an iteraror of an STL Container with - /// GR::Edge as its value_type. - /// The algorithm copies the elements of the found tree into this sequence. - /// For example, if we know that the spanning tree of the graph \c G has - /// say 53 edges then - /// we can put its edges into a STL vector \c tree with a code like this. - /// \code - /// std::vector tree(53); - /// kruskalEdgeMap_IteratorOut(G,cost,tree.begin()); - /// \endcode - /// Or if we don't know in advance the size of the tree, we can write this. - /// \code - /// std::vector tree; - /// kruskalEdgeMap_IteratorOut(G,cost,std::back_inserter(tree)); - /// \endcode - /// - /// \return The cost of the found tree. - /// - /// \bug its name does not follow the coding style. - - template - inline - typename IN::ValueType - kruskalEdgeMap_IteratorOut(const GR& G, - const IN& in, - RET out) - { - KruskalSequenceOutput _out(out); - return kruskal(G, KruskalMapInput(G, in), _out); - } - - /// @} - -} //namespace hugo - -#endif //HUGO_KRUSKAL_H diff -r 2d6c8075d9d0 -r 818510fa3d99 src/hugo/list_graph.h --- a/src/hugo/list_graph.h Wed Sep 29 14:12:26 2004 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,1106 +0,0 @@ -/* -*- C++ -*- - * src/hugo/list_graph.h - Part of HUGOlib, a generic C++ optimization library - * - * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport - * (Egervary Combinatorial Optimization Research Group, 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 HUGO_LIST_GRAPH_H -#define HUGO_LIST_GRAPH_H - -///\ingroup graphs -///\file -///\brief ListGraph, SymListGraph, NodeSet and EdgeSet classes. - -#include -#include - -#include - -#include -#include - -#include - -#include - - -namespace hugo { - -/// \addtogroup graphs -/// @{ - - ///A list graph class. - - ///This is a simple and fast erasable graph implementation. - /// - ///It conforms to the - ///\ref skeleton::ErasableGraph "ErasableGraph" concept. - ///\sa skeleton::ErasableGraph. - class ListGraph { - - //Nodes are double linked. - //The free nodes are only single linked using the "next" field. - struct NodeT - { - int first_in,first_out; - int prev, next; - }; - //Edges are double linked. - //The free edges are only single linked using the "next_in" field. - struct EdgeT - { - int head, tail; - int prev_in, prev_out; - int next_in, next_out; - }; - - std::vector nodes; - //The first node - int first_node; - //The first free node - int first_free_node; - std::vector edges; - //The first free edge - int first_free_edge; - - public: - - typedef ListGraph Graph; - - class Node; - class Edge; - - - public: - - class NodeIt; - class EdgeIt; - class OutEdgeIt; - class InEdgeIt; - - // Create map registries. - CREATE_MAP_REGISTRIES; - // Create node and edge maps. - CREATE_MAPS(ArrayMap); - - public: - - ListGraph() - : nodes(), first_node(-1), - first_free_node(-1), edges(), first_free_edge(-1) {} - - ListGraph(const ListGraph &_g) - : nodes(_g.nodes), first_node(_g.first_node), - first_free_node(_g.first_free_node), edges(_g.edges), - first_free_edge(_g.first_free_edge) {} - - ///Number of nodes. - int nodeNum() const { return nodes.size(); } - ///Number of edges. - int edgeNum() const { return edges.size(); } - - ///Set the expected maximum number of edges. - - ///With this function, it is possible to set the expected number of edges. - ///The use of this fasten the building of the graph and makes - ///it possible to avoid the superfluous memory allocation. - void reserveEdge(int n) { edges.reserve(n); }; - - /// Maximum node ID. - - /// Maximum node ID. - ///\sa id(Node) - int maxNodeId() const { return nodes.size()-1; } - /// Maximum edge ID. - - /// Maximum edge ID. - ///\sa id(Edge) - int maxEdgeId() const { return edges.size()-1; } - - Node tail(Edge e) const { return edges[e.n].tail; } - Node head(Edge e) const { return edges[e.n].head; } - - NodeIt& first(NodeIt& v) const { - v=NodeIt(*this); return v; } - EdgeIt& first(EdgeIt& e) const { - e=EdgeIt(*this); return e; } - OutEdgeIt& first(OutEdgeIt& e, const Node v) const { - e=OutEdgeIt(*this,v); return e; } - InEdgeIt& first(InEdgeIt& e, const Node v) const { - e=InEdgeIt(*this,v); return e; } - - /// Node ID. - - /// The ID of a valid Node is a nonnegative integer not greater than - /// \ref maxNodeId(). The range of the ID's is not surely continuous - /// and the greatest node ID can be actually less then \ref maxNodeId(). - /// - /// The ID of the \ref INVALID node is -1. - ///\return The ID of the node \c v. - static int id(Node v) { return v.n; } - /// Edge ID. - - /// The ID of a valid Edge is a nonnegative integer not greater than - /// \ref maxEdgeId(). The range of the ID's is not surely continuous - /// and the greatest edge ID can be actually less then \ref maxEdgeId(). - /// - /// The ID of the \ref INVALID edge is -1. - ///\return The ID of the edge \c e. - static int id(Edge e) { return e.n; } - - /// Adds a new node to the graph. - - /// \warning It adds the new node to the front of the list. - /// (i.e. the lastly added node becomes the first.) - Node addNode() { - int n; - - if(first_free_node==-1) - { - n = nodes.size(); - nodes.push_back(NodeT()); - } - else { - n = first_free_node; - first_free_node = nodes[n].next; - } - - nodes[n].next = first_node; - if(first_node != -1) nodes[first_node].prev = n; - first_node = n; - nodes[n].prev = -1; - - nodes[n].first_in = nodes[n].first_out = -1; - - Node nn; nn.n=n; - - //Update dynamic maps - node_maps.add(nn); - - return nn; - } - - Edge addEdge(Node u, Node v) { - int n; - - if(first_free_edge==-1) - { - n = edges.size(); - edges.push_back(EdgeT()); - } - else { - n = first_free_edge; - first_free_edge = edges[n].next_in; - } - - edges[n].tail = u.n; edges[n].head = v.n; - - edges[n].next_out = nodes[u.n].first_out; - if(nodes[u.n].first_out != -1) edges[nodes[u.n].first_out].prev_out = n; - edges[n].next_in = nodes[v.n].first_in; - if(nodes[v.n].first_in != -1) edges[nodes[v.n].first_in].prev_in = n; - edges[n].prev_in = edges[n].prev_out = -1; - - nodes[u.n].first_out = nodes[v.n].first_in = n; - - Edge e; e.n=n; - - //Update dynamic maps - edge_maps.add(e); - - return e; - } - - /// Finds an edge between two nodes. - - /// Finds an edge from node \c u to node \c v. - /// - /// If \c prev is \ref INVALID (this is the default value), then - /// It finds the first edge from \c u to \c v. Otherwise it looks for - /// the next edge from \c u to \c v after \c prev. - /// \return The found edge or INVALID if there is no such an edge. - Edge findEdge(Node u,Node v, Edge prev = INVALID) - { - int e = (prev.n==-1)? nodes[u.n].first_out : edges[prev.n].next_out; - while(e!=-1 && edges[e].tail!=v.n) e = edges[e].next_out; - prev.n=e; - return prev; - } - - private: - void eraseEdge(int n) { - - if(edges[n].next_in!=-1) - edges[edges[n].next_in].prev_in = edges[n].prev_in; - if(edges[n].prev_in!=-1) - edges[edges[n].prev_in].next_in = edges[n].next_in; - else nodes[edges[n].head].first_in = edges[n].next_in; - - if(edges[n].next_out!=-1) - edges[edges[n].next_out].prev_out = edges[n].prev_out; - if(edges[n].prev_out!=-1) - edges[edges[n].prev_out].next_out = edges[n].next_out; - else nodes[edges[n].tail].first_out = edges[n].next_out; - - edges[n].next_in = first_free_edge; - first_free_edge = n; - - //Update dynamic maps - Edge e; e.n=n; - edge_maps.erase(e); - - } - - public: - - void erase(Node nn) { - int n=nn.n; - - int m; - while((m=nodes[n].first_in)!=-1) eraseEdge(m); - while((m=nodes[n].first_out)!=-1) eraseEdge(m); - - if(nodes[n].next != -1) nodes[nodes[n].next].prev = nodes[n].prev; - if(nodes[n].prev != -1) nodes[nodes[n].prev].next = nodes[n].next; - else first_node = nodes[n].next; - - nodes[n].next = first_free_node; - first_free_node = n; - - //Update dynamic maps - node_maps.erase(nn); - - } - - void erase(Edge e) { eraseEdge(e.n); } - - void clear() { - edge_maps.clear(); - edges.clear(); - node_maps.clear(); - nodes.clear(); - first_node=first_free_node=first_free_edge=-1; - } - - class Node { - friend class ListGraph; - template friend class NodeMap; - - friend class Edge; - friend class OutEdgeIt; - friend class InEdgeIt; - friend class SymEdge; - - protected: - int n; - friend int ListGraph::id(Node v); - Node(int nn) {n=nn;} - public: - Node() {} - Node (Invalid) { n=-1; } - bool operator==(const Node i) const {return n==i.n;} - bool operator!=(const Node i) const {return n!=i.n;} - bool operator<(const Node i) const {return nnodes[n].next; - return *this; - } - // ///Validity check - // operator bool() { return Node::operator bool(); } - }; - - class Edge { - friend class ListGraph; - template friend class EdgeMap; - - friend class SymListGraph; - - friend class Node; - friend class NodeIt; - protected: - int n; - friend int ListGraph::id(Edge e); - - public: - /// An Edge with id \c n. - - /// \bug It should be - /// obtained by a member function of the Graph. - Edge(int nn) {n=nn;} - - Edge() { } - Edge (Invalid) { n=-1; } - bool operator==(const Edge i) const {return n==i.n;} - bool operator!=(const Edge i) const {return n!=i.n;} - bool operator<(const Edge i) const {return nedges[n].next_in!=-1) n=G->edges[n].next_in; - else { - int nn; - for(nn=G->nodes[G->edges[n].head].next; - nn!=-1 && G->nodes[nn].first_in == -1; - nn = G->nodes[nn].next) ; - n = (nn==-1)?-1:G->nodes[nn].first_in; - } - return *this; - } - // ///Validity check - // operator bool() { return Edge::operator bool(); } - }; - - class OutEdgeIt : public Edge { - const ListGraph *G; - friend class ListGraph; - public: - OutEdgeIt() : Edge() { } - OutEdgeIt(const ListGraph& _G, Edge e) : Edge(e), G(&_G) { } - OutEdgeIt (Invalid i) : Edge(i) { } - - OutEdgeIt(const ListGraph& _G,const Node v) - : Edge(_G.nodes[v.n].first_out), G(&_G) {} - OutEdgeIt &operator++() { n=G->edges[n].next_out; return *this; } - // ///Validity check - // operator bool() { return Edge::operator bool(); } - }; - - class InEdgeIt : public Edge { - const ListGraph *G; - friend class ListGraph; - public: - InEdgeIt() : Edge() { } - InEdgeIt(const ListGraph& _G, Edge e) : Edge(e), G(&_G) { } - InEdgeIt (Invalid i) : Edge(i) { } - InEdgeIt(const ListGraph& _G,Node v) - : Edge(_G.nodes[v.n].first_in), G(&_G) { } - InEdgeIt &operator++() { n=G->edges[n].next_in; return *this; } - // ///Validity check - // operator bool() { return Edge::operator bool(); } - }; - }; - - ///Graph for bidirectional edges. - - ///The purpose of this graph structure is to handle graphs - ///having bidirectional edges. Here the function \c addEdge(u,v) adds a pair - ///of oppositely directed edges. - ///There is a new edge map type called - ///\ref hugo::SymListGraph::SymEdgeMap "SymEdgeMap" - ///that complements this - ///feature by - ///storing shared values for the edge pairs. The usual - ///\ref hugo::skeleton::StaticGraph::EdgeMap "EdgeMap" - ///can be used - ///as well. - /// - ///The oppositely directed edge can also be obtained easily - ///using \ref hugo::SymListGraph::opposite() "opposite()" member function. - /// - ///Here erase(Edge) deletes a pair of edges. - /// - ///\todo this date structure need some reconsiderations. Maybe it - ///should be implemented independently from ListGraph. - - class SymListGraph : public ListGraph - { - public: - - typedef SymListGraph Graph; - - // Create symmetric map registry. - CREATE_SYM_EDGE_MAP_REGISTRY; - // Create symmetric edge map. - CREATE_SYM_EDGE_MAP(ArrayMap); - - SymListGraph() : ListGraph() { } - SymListGraph(const ListGraph &_g) : ListGraph(_g) { } - ///Adds a pair of oppositely directed edges to the graph. - Edge addEdge(Node u, Node v) - { - Edge e = ListGraph::addEdge(u,v); - Edge f = ListGraph::addEdge(v,u); - sym_edge_maps.add(e); - sym_edge_maps.add(f); - - return e; - } - - void erase(Node n) { ListGraph::erase(n);} - ///The oppositely directed edge. - - ///Returns the oppositely directed - ///pair of the edge \c e. - static Edge opposite(Edge e) - { - Edge f; - f.n = e.n - 2*(e.n%2) + 1; - return f; - } - - ///Removes a pair of oppositely directed edges to the graph. - void erase(Edge e) { - Edge f = opposite(e); - sym_edge_maps.erase(e); - sym_edge_maps.erase(f); - ListGraph::erase(f); - ListGraph::erase(e); - } - }; - - - ///A graph class containing only nodes. - - ///This class implements a graph structure without edges. - ///The most useful application of this class is to be the node set of an - ///\ref EdgeSet class. - /// - ///It conforms to - ///the \ref skeleton::ExtendableGraph "ExtendableGraph" concept - ///with the exception that you cannot - ///add (or delete) edges. The usual edge iterators are exists, but they are - ///always \ref INVALID. - ///\sa skeleton::ExtendableGraph - ///\sa EdgeSet - class NodeSet { - - //Nodes are double linked. - //The free nodes are only single linked using the "next" field. - struct NodeT - { - int first_in,first_out; - int prev, next; - // NodeT() {} - }; - - std::vector nodes; - //The first node - int first_node; - //The first free node - int first_free_node; - - public: - - typedef NodeSet Graph; - - class Node; - class Edge; - - public: - - class NodeIt; - class EdgeIt; - class OutEdgeIt; - class InEdgeIt; - - // Create node map registry. - CREATE_NODE_MAP_REGISTRY; - // Create node maps. - CREATE_NODE_MAP(ArrayMap); - - /// Creating empty map structure for edges. - template - class EdgeMap { - public: - EdgeMap(const Graph&) {} - EdgeMap(const Graph&, const Value&) {} - - EdgeMap(const EdgeMap&) {} - template EdgeMap(const CMap&) {} - - EdgeMap& operator=(const EdgeMap&) {} - template EdgeMap& operator=(const CMap&) {} - - class ConstIterator { - public: - bool operator==(const ConstIterator&) {return true;} - bool operator!=(const ConstIterator&) {return false;} - }; - - typedef ConstIterator Iterator; - - Iterator begin() { return Iterator();} - Iterator end() { return Iterator();} - - ConstIterator begin() const { return ConstIterator();} - ConstIterator end() const { return ConstIterator();} - - }; - - public: - - ///Default constructor - NodeSet() - : nodes(), first_node(-1), first_free_node(-1) {} - ///Copy constructor - NodeSet(const NodeSet &_g) - : nodes(_g.nodes), first_node(_g.first_node), - first_free_node(_g.first_free_node) {} - - ///Number of nodes. - int nodeNum() const { return nodes.size(); } - ///Number of edges. - int edgeNum() const { return 0; } - - /// Maximum node ID. - - /// Maximum node ID. - ///\sa id(Node) - int maxNodeId() const { return nodes.size()-1; } - /// Maximum edge ID. - - /// Maximum edge ID. - ///\sa id(Edge) - int maxEdgeId() const { return 0; } - - Node tail(Edge e) const { return INVALID; } - Node head(Edge e) const { return INVALID; } - - NodeIt& first(NodeIt& v) const { - v=NodeIt(*this); return v; } - EdgeIt& first(EdgeIt& e) const { - e=EdgeIt(*this); return e; } - OutEdgeIt& first(OutEdgeIt& e, const Node v) const { - e=OutEdgeIt(*this,v); return e; } - InEdgeIt& first(InEdgeIt& e, const Node v) const { - e=InEdgeIt(*this,v); return e; } - - /// Node ID. - - /// The ID of a valid Node is a nonnegative integer not greater than - /// \ref maxNodeId(). The range of the ID's is not surely continuous - /// and the greatest node ID can be actually less then \ref maxNodeId(). - /// - /// The ID of the \ref INVALID node is -1. - ///\return The ID of the node \c v. - static int id(Node v) { return v.n; } - /// Edge ID. - - /// The ID of a valid Edge is a nonnegative integer not greater than - /// \ref maxEdgeId(). The range of the ID's is not surely continuous - /// and the greatest edge ID can be actually less then \ref maxEdgeId(). - /// - /// The ID of the \ref INVALID edge is -1. - ///\return The ID of the edge \c e. - static int id(Edge e) { return -1; } - - /// Adds a new node to the graph. - - /// \warning It adds the new node to the front of the list. - /// (i.e. the lastly added node becomes the first.) - Node addNode() { - int n; - - if(first_free_node==-1) - { - n = nodes.size(); - nodes.push_back(NodeT()); - } - else { - n = first_free_node; - first_free_node = nodes[n].next; - } - - nodes[n].next = first_node; - if(first_node != -1) nodes[first_node].prev = n; - first_node = n; - nodes[n].prev = -1; - - nodes[n].first_in = nodes[n].first_out = -1; - - Node nn; nn.n=n; - - //Update dynamic maps - node_maps.add(nn); - - return nn; - } - - void erase(Node nn) { - int n=nn.n; - - if(nodes[n].next != -1) nodes[nodes[n].next].prev = nodes[n].prev; - if(nodes[n].prev != -1) nodes[nodes[n].prev].next = nodes[n].next; - else first_node = nodes[n].next; - - nodes[n].next = first_free_node; - first_free_node = n; - - //Update dynamic maps - node_maps.erase(nn); - } - - - Edge findEdge(Node u,Node v, Edge prev = INVALID) - { - return INVALID; - } - - void clear() { - node_maps.clear(); - nodes.clear(); - first_node = first_free_node = -1; - } - - class Node { - friend class NodeSet; - template friend class NodeMap; - - friend class Edge; - friend class OutEdgeIt; - friend class InEdgeIt; - - protected: - int n; - friend int NodeSet::id(Node v); - Node(int nn) {n=nn;} - public: - Node() {} - Node (Invalid i) { n=-1; } - bool operator==(const Node i) const {return n==i.n;} - bool operator!=(const Node i) const {return n!=i.n;} - bool operator<(const Node i) const {return nnodes[n].next; - return *this; - } - }; - - class Edge { - public: - Edge() { } - Edge (Invalid) { } - bool operator==(const Edge i) const {return true;} - bool operator!=(const Edge i) const {return false;} - bool operator<(const Edge i) const {return false;} - }; - - class EdgeIt : public Edge { - public: - EdgeIt(const NodeSet& G) : Edge() { } - EdgeIt(const NodeSet&, Edge) : Edge() { } - EdgeIt (Invalid i) : Edge(i) { } - EdgeIt() : Edge() { } - EdgeIt operator++() { return INVALID; } - }; - - class OutEdgeIt : public Edge { - friend class NodeSet; - public: - OutEdgeIt() : Edge() { } - OutEdgeIt(const NodeSet&, Edge) : Edge() { } - OutEdgeIt (Invalid i) : Edge(i) { } - OutEdgeIt(const NodeSet& G,const Node v) : Edge() {} - OutEdgeIt operator++() { return INVALID; } - }; - - class InEdgeIt : public Edge { - friend class NodeSet; - public: - InEdgeIt() : Edge() { } - InEdgeIt(const NodeSet&, Edge) : Edge() { } - InEdgeIt (Invalid i) : Edge(i) { } - InEdgeIt(const NodeSet& G,Node v) :Edge() {} - InEdgeIt operator++() { return INVALID; } - }; - - }; - - - - ///Graph structure using a node set of another graph. - - ///This structure can be used to establish another graph over a node set - /// of an existing one. The node iterator will go through the nodes of the - /// original graph, and the NodeMap's of both graphs will convert to - /// each other. - /// - ///\warning Adding or deleting nodes from the graph is not safe if an - ///\ref EdgeSet is currently attached to it! - /// - ///\todo Make it possible to add/delete edges from the base graph - ///(and from \ref EdgeSet, as well) - /// - ///\param GG The type of the graph which shares its node set with this class. - ///Its interface must conform to the - ///\ref skeleton::StaticGraph "StaticGraph" concept. - /// - ///It conforms to the - ///\ref skeleton::ExtendableGraph "ExtendableGraph" concept. - ///\sa skeleton::ExtendableGraph. - ///\sa NodeSet. - template - class EdgeSet { - - typedef GG NodeGraphType; - - NodeGraphType &G; - - public: - - class Node; - class Edge; - class OutEdgeIt; - class InEdgeIt; - class SymEdge; - - typedef EdgeSet Graph; - - int id(Node v) const; - - class Node : public NodeGraphType::Node { - friend class EdgeSet; - - friend class Edge; - friend class OutEdgeIt; - friend class InEdgeIt; - friend class SymEdge; - - public: - friend int EdgeSet::id(Node v) const; - public: - Node() : NodeGraphType::Node() {} - Node (Invalid i) : NodeGraphType::Node(i) {} - Node(const typename NodeGraphType::Node &n) : NodeGraphType::Node(n) {} - }; - - class NodeIt : public NodeGraphType::NodeIt { - friend class EdgeSet; - public: - NodeIt() : NodeGraphType::NodeIt() { } - NodeIt(const EdgeSet& _G,Node n) : NodeGraphType::NodeIt(_G.G,n) { } - NodeIt (Invalid i) : NodeGraphType::NodeIt(i) {} - NodeIt(const EdgeSet& _G) : NodeGraphType::NodeIt(_G.G) { } - NodeIt(const typename NodeGraphType::NodeIt &n) - : NodeGraphType::NodeIt(n) {} - - operator Node() { return Node(*this);} - NodeIt &operator++() - { this->NodeGraphType::NodeIt::operator++(); return *this;} - }; - - private: - //Edges are double linked. - //The free edges are only single linked using the "next_in" field. - struct NodeT - { - int first_in,first_out; - NodeT() : first_in(-1), first_out(-1) { } - }; - - struct EdgeT - { - Node head, tail; - int prev_in, prev_out; - int next_in, next_out; - }; - - - typename NodeGraphType::template NodeMap nodes; - - std::vector edges; - //The first free edge - int first_free_edge; - - public: - - class Node; - class Edge; - - class NodeIt; - class EdgeIt; - class OutEdgeIt; - class InEdgeIt; - - - // Create edge map registry. - CREATE_EDGE_MAP_REGISTRY; - // Create edge maps. - CREATE_EDGE_MAP(ArrayMap); - - // Import node maps from the NodeGraphType. - IMPORT_NODE_MAP(NodeGraphType, graph.G, EdgeSet, graph); - - - public: - - ///Constructor - - ///Construates a new graph based on the nodeset of an existing one. - ///\param _G the base graph. - explicit EdgeSet(NodeGraphType &_G) - : G(_G), nodes(_G), edges(), - first_free_edge(-1) {} - ///Copy constructor - - ///Makes a copy of an EdgeSet. - ///It will be based on the same graph. - explicit EdgeSet(const EdgeSet &_g) - : G(_g.G), nodes(_g.G), edges(_g.edges), - first_free_edge(_g.first_free_edge) {} - - ///Number of nodes. - int nodeNum() const { return G.nodeNum(); } - ///Number of edges. - int edgeNum() const { return edges.size(); } - - /// Maximum node ID. - - /// Maximum node ID. - ///\sa id(Node) - int maxNodeId() const { return G.maxNodeId(); } - /// Maximum edge ID. - - /// Maximum edge ID. - ///\sa id(Edge) - int maxEdgeId() const { return edges.size()-1; } - - Node tail(Edge e) const { return edges[e.n].tail; } - Node head(Edge e) const { return edges[e.n].head; } - - NodeIt& first(NodeIt& v) const { - v=NodeIt(*this); return v; } - EdgeIt& first(EdgeIt& e) const { - e=EdgeIt(*this); return e; } - OutEdgeIt& first(OutEdgeIt& e, const Node v) const { - e=OutEdgeIt(*this,v); return e; } - InEdgeIt& first(InEdgeIt& e, const Node v) const { - e=InEdgeIt(*this,v); return e; } - - /// Node ID. - - /// The ID of a valid Node is a nonnegative integer not greater than - /// \ref maxNodeId(). The range of the ID's is not surely continuous - /// and the greatest node ID can be actually less then \ref maxNodeId(). - /// - /// The ID of the \ref INVALID node is -1. - ///\return The ID of the node \c v. - int id(Node v) { return G.id(v); } - /// Edge ID. - - /// The ID of a valid Edge is a nonnegative integer not greater than - /// \ref maxEdgeId(). The range of the ID's is not surely continuous - /// and the greatest edge ID can be actually less then \ref maxEdgeId(). - /// - /// The ID of the \ref INVALID edge is -1. - ///\return The ID of the edge \c e. - static int id(Edge e) { return e.n; } - - /// Adds a new node to the graph. - Node addNode() { return G.addNode(); } - - Edge addEdge(Node u, Node v) { - int n; - - if(first_free_edge==-1) - { - n = edges.size(); - edges.push_back(EdgeT()); - } - else { - n = first_free_edge; - first_free_edge = edges[n].next_in; - } - - edges[n].tail = u; edges[n].head = v; - - edges[n].next_out = nodes[u].first_out; - if(nodes[u].first_out != -1) edges[nodes[u].first_out].prev_out = n; - edges[n].next_in = nodes[v].first_in; - if(nodes[v].first_in != -1) edges[nodes[v].first_in].prev_in = n; - edges[n].prev_in = edges[n].prev_out = -1; - - nodes[u].first_out = nodes[v].first_in = n; - - Edge e; e.n=n; - - //Update dynamic maps - edge_maps.add(e); - - return e; - } - - /// Finds an edge between two nodes. - - /// Finds an edge from node \c u to node \c v. - /// - /// If \c prev is \ref INVALID (this is the default value), then - /// It finds the first edge from \c u to \c v. Otherwise it looks for - /// the next edge from \c u to \c v after \c prev. - /// \return The found edge or INVALID if there is no such an edge. - Edge findEdge(Node u,Node v, Edge prev = INVALID) - { - int e = (prev.n==-1)? nodes[u].first_out : edges[prev.n].next_out; - while(e!=-1 && edges[e].tail!=v) e = edges[e].next_out; - prev.n=e; - return prev; - } - - private: - void eraseEdge(int n) { - - if(edges[n].next_in!=-1) - edges[edges[n].next_in].prev_in = edges[n].prev_in; - if(edges[n].prev_in!=-1) - edges[edges[n].prev_in].next_in = edges[n].next_in; - else nodes[edges[n].head].first_in = edges[n].next_in; - - if(edges[n].next_out!=-1) - edges[edges[n].next_out].prev_out = edges[n].prev_out; - if(edges[n].prev_out!=-1) - edges[edges[n].prev_out].next_out = edges[n].next_out; - else nodes[edges[n].tail].first_out = edges[n].next_out; - - edges[n].next_in = first_free_edge; - first_free_edge = -1; - - //Update dynamic maps - Edge e; e.n = n; - edge_maps.erase(e); - } - - public: - - void erase(Edge e) { eraseEdge(e.n); } - - ///Clear all edges. (Doesn't clear the nodes!) - void clear() { - edge_maps.clear(); - edges.clear(); - first_free_edge=-1; - } - - - class Edge { - public: - friend class EdgeSet; - template friend class EdgeMap; - - friend class Node; - friend class NodeIt; - protected: - int n; - friend int EdgeSet::id(Edge e) const; - - Edge(int nn) {n=nn;} - public: - Edge() { } - Edge (Invalid) { n=-1; } - bool operator==(const Edge i) const {return n==i.n;} - bool operator!=(const Edge i) const {return n!=i.n;} - bool operator<(const Edge i) const {return n friend class EdgeMap; - - const EdgeSet *G; - public: - EdgeIt(const EdgeSet& _G) : Edge(), G(&_G) { - NodeIt m; - for(G->first(m); - m!=INVALID && G->nodes[m].first_in == -1; ++m); - ///\bug AJJAJ! This is a non sense!!!!!!! - this->n = m!=INVALID?-1:G->nodes[m].first_in; - } - EdgeIt(const EdgeSet& _G, Edge e) : Edge(e), G(&_G) { } - EdgeIt (Invalid i) : Edge(i) { } - EdgeIt() : Edge() { } - ///. - - ///\bug UNIMPLEMENTED!!!!! - // - EdgeIt &operator++() { - return *this; - } - }; - - class OutEdgeIt : public Edge { - const EdgeSet *G; - friend class EdgeSet; - public: - OutEdgeIt() : Edge() { } - OutEdgeIt (Invalid i) : Edge(i) { } - OutEdgeIt(const EdgeSet& _G, Edge e) : Edge(e), G(&_G) { } - - OutEdgeIt(const EdgeSet& _G,const Node v) : - Edge(_G.nodes[v].first_out), G(&_G) { } - OutEdgeIt &operator++() { - Edge::n = G->edges[Edge::n].next_out; - return *this; - } - }; - - class InEdgeIt : public Edge { - const EdgeSet *G; - friend class EdgeSet; - public: - InEdgeIt() : Edge() { } - InEdgeIt (Invalid i) : Edge(i) { } - InEdgeIt(const EdgeSet& _G, Edge e) : Edge(e), G(&_G) { } - InEdgeIt(const EdgeSet& _G,Node v) - : Edge(_G.nodes[v].first_in), G(&_G) { } - InEdgeIt &operator++() { - Edge::n = G->edges[Edge::n].next_in; - return *this; - } - }; - - }; - - template - inline int EdgeSet::id(Node v) const { return G.id(v); } - -/// @} - -} //namespace hugo - -#endif //HUGO_LIST_GRAPH_H diff -r 2d6c8075d9d0 -r 818510fa3d99 src/hugo/map_bits.h --- a/src/hugo/map_bits.h Wed Sep 29 14:12:26 2004 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,67 +0,0 @@ -/* -*- C++ -*- - * src/hugo/map_bits.h - Part of HUGOlib, a generic C++ optimization library - * - * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport - * (Egervary Combinatorial Optimization Research Group, 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 HUGO_MAP_BITS_H -#define HUGO_MAP_BITS_H - -///\ingroup graphmaps -///\file -///\brief Some utils to help implement maps. - -namespace hugo { - - - /// \addtogroup graphmaps - /// @{ - - /// Helper class to get information about the key type. - template - struct KeyInfo {}; - - template - struct KeyInfo { - static int maxId(const Graph& graph) { - return graph.maxNodeId(); - } - static int id(const Graph& graph, const typename Graph::Node& node) { - return graph.id(node); - } - }; - - template - struct KeyInfo { - static int maxId(const Graph& graph) { - return graph.maxEdgeId(); - } - static int id(const Graph& graph, const typename Graph::Edge& edge) { - return graph.id(edge); - } - }; - - template - struct KeyInfo { - static int maxId(const Graph& graph) { - return graph.maxEdgeId() >> 1; - } - static int id(const Graph& graph, const typename Graph::Edge& edge) { - return graph.id(edge) >> 1; - } - }; - - /// @} -} - -#endif diff -r 2d6c8075d9d0 -r 818510fa3d99 src/hugo/map_defines.h --- a/src/hugo/map_defines.h Wed Sep 29 14:12:26 2004 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,228 +0,0 @@ -/* -*- C++ -*- - * src/hugo/map_defines.h - Part of HUGOlib, a generic C++ optimization library - * - * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport - * (Egervary Combinatorial Optimization Research Group, 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 HUGO_MAP_DEFINES_H -#define HUGO_MAP_DEFINES_H - -///\ingroup graphmaps -///\file -///\brief Defines to help creating graph maps. - -/// \addtogroup graphmapfactory -/// @{ - -/** Creates the EdgeMapRegistry type an declare a mutable instance - * named edge_maps. - */ -#define CREATE_EDGE_MAP_REGISTRY \ -typedef MapRegistry EdgeMapRegistry; \ -mutable EdgeMapRegistry edge_maps; - -/** Creates the NodeMapRegistry type an declare a mutable instance - * named node_maps. - */ -#define CREATE_NODE_MAP_REGISTRY \ -typedef MapRegistry NodeMapRegistry; \ -mutable NodeMapRegistry node_maps; - -/** Creates both map registries. - */ -#define CREATE_MAP_REGISTRIES \ -CREATE_NODE_MAP_REGISTRY \ -CREATE_EDGE_MAP_REGISTRY - -/** Creates a map from a template map. The import method is - * an overloading of the map type. - * The reason to use these macro is that the c++ does not support - * the template typedefs. If a future release of the c++ - * supports this feature it should be fixed. - */ -#define CREATE_NODE_MAP(DynMap) \ -template \ -class NodeMap : public DynMap { \ -public: \ -typedef DynMap Parent; \ -NodeMap(const typename Parent::Graph& g) \ - : Parent(g, g.node_maps) {} \ -NodeMap(const typename Parent::Graph& g, const Value& v) \ - : Parent(g, g.node_maps, v) {} \ -NodeMap(const NodeMap& copy) : Parent(static_cast(copy)) {} \ -template \ -NodeMap(const NodeMap& copy) \ - : Parent(static_cast::Parent&>(copy)) {} \ -NodeMap& operator=(const NodeMap& copy) { \ - Parent::operator=(static_cast(copy));\ - return *this; \ -} \ -template \ -NodeMap& operator=(const NodeMap& copy) { \ - Parent::operator=(static_cast::Parent&>(copy));\ - return *this; \ -} \ -}; - -/** Creates a map from a template map. The import method is - * an overloading of the map type. - * The reason to use these macro is that the c++ does not support - * the template typedefs. If a future release of the c++ - * supports this feature it should be fixed. - */ -#define CREATE_EDGE_MAP(DynMap) \ -template \ -class EdgeMap : public DynMap { \ -public: \ -typedef DynMap Parent; \ -\ -EdgeMap(const typename Parent::Graph& g) \ - : Parent(g, g.edge_maps) {} \ -EdgeMap(const typename Parent::Graph& g, const Value& v) \ - : Parent(g, g.edge_maps, v) {} \ -EdgeMap(const EdgeMap& copy) : Parent(static_cast(copy)) {} \ -template \ -EdgeMap(const EdgeMap& copy) \ - : Parent(static_cast::Parent&>(copy)) {} \ -EdgeMap& operator=(const EdgeMap& copy) { \ - Parent::operator=(static_cast(copy));\ - return *this; \ -} \ -template \ -EdgeMap& operator=(const EdgeMap& copy) { \ - Parent::operator=(static_cast::Parent&>(copy));\ - return *this; \ -} \ -}; - -/** This macro creates both maps. - */ -#define CREATE_MAPS(DynMap) \ -CREATE_NODE_MAP(DynMap) \ -CREATE_EDGE_MAP(DynMap) - -/** This macro creates MapRegistry for Symmetric Edge Maps. - */ -#define CREATE_SYM_EDGE_MAP_REGISTRY \ -typedef SymEdgeIt SymEdgeIt; \ -typedef MapRegistry SymEdgeMapRegistry; \ -mutable SymEdgeMapRegistry sym_edge_maps; - - -/** Creates a map from a template map. The import method is - * an overloading of the map type. - * The reason to use these macro is that the c++ does not support - * the template typedefs. If a future release of the c++ - * supports this feature it should be fixed. - */ -#define CREATE_SYM_EDGE_MAP(DynMap) \ -template \ -class SymEdgeMap : public SymMap { \ -public: \ -typedef SymMap Parent; \ -\ -SymEdgeMap(const typename Parent::Graph& g) \ - : Parent(g, g.sym_edge_maps) {} \ -SymEdgeMap(const typename Parent::Graph& g, const Value& v) \ - : Parent(g, g.sym_edge_maps, v) {} \ -SymEdgeMap(const SymEdgeMap& copy) \ - : Parent(static_cast(copy)) {} \ -template \ -SymEdgeMap(const NodeMap& copy) \ - : Parent(static_cast::Parent&>(copy)) {} \ -SymEdgeMap& operator=(const SymEdgeMap& copy) { \ - Parent::operator=(static_cast(copy));\ - return *this; \ -} \ -template \ -SymEdgeMap& operator=(const SymEdgeMap& copy) { \ - Parent::operator=(static_cast::Parent&>(copy));\ - return *this; \ -} \ -}; - -/** This is a macro to import an node map into a graph class. - */ -#define IMPORT_NODE_MAP(From, from, To, to) \ -template \ -class NodeMap : public From::template NodeMap { \ -\ -public: \ -typedef typename From::template NodeMap Parent; \ -\ -NodeMap(const To& to) \ - : Parent(static_cast(from)) { } \ -NodeMap(const To& to, const Value& value) \ - : Parent(static_cast(from), value) { } \ -NodeMap(const NodeMap& copy) \ - : Parent(static_cast(copy)) {} \ -template \ -NodeMap(const NodeMap& copy) \ - : Parent(static_cast::Parent&>(copy)) {} \ -NodeMap& operator=(const NodeMap& copy) { \ - Parent::operator=(static_cast(copy)); \ - return *this; \ -} \ -template \ -NodeMap& operator=(const NodeMap& copy) { \ - Parent::operator=(static_cast::Parent&>(copy));\ - return *this; \ -} \ -}; - -/** This is a macro to import an edge map into a graph class. - */ -#define IMPORT_EDGE_MAP(From, from, To, to) \ -template \ -class EdgeMap : public From::template EdgeMap { \ -\ -public: \ -typedef typename From::template EdgeMap Parent; \ -\ -EdgeMap(const To& to) \ - : Parent(static_cast(from)) { } \ -EdgeMap(const To& to, const Value& value) \ - : Parent(static_cast(from), value) { } \ -EdgeMap(const EdgeMap& copy) \ - : Parent(static_cast(copy)) {} \ -template \ -EdgeMap(const EdgeMap& copy) \ - : Parent(static_cast::Parent&>(copy)) {} \ -EdgeMap& operator=(const EdgeMap& copy) { \ - Parent::operator=(static_cast(copy)); \ - return *this; \ -} \ -template \ -EdgeMap& operator=(const EdgeMap& copy) { \ - Parent::operator=(static_cast::Parent&>(copy));\ - return *this; \ -} \ -}; - -#define KEEP_EDGE_MAP(From, To) \ -IMPORT_EDGE_MAP(From, graph, To, graph) - - -#define KEEP_NODE_MAP(From, To) \ -IMPORT_NODE_MAP(From, graph, To, graph) - -/** This is a macro to keep the node and edge maps for a graph class. - */ -#define KEEP_MAPS(From, To) \ -KEEP_EDGE_MAP(From, To) \ -KEEP_NODE_MAP(From, To) - - -/// @} - -#endif diff -r 2d6c8075d9d0 -r 818510fa3d99 src/hugo/map_iterator.h --- a/src/hugo/map_iterator.h Wed Sep 29 14:12:26 2004 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,692 +0,0 @@ -/* -*- C++ -*- - * src/hugo/map_iterator.h - Part of HUGOlib, a generic C++ optimization library - * - * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport - * (Egervary Combinatorial Optimization Research Group, 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 HUGO_MAP_ITERATOR_H -#define HUGO_MAP_ITERATOR_H - -#include - -#include - -///\ingroup graphmaps -///\file -///\brief Iterators on the maps. - -namespace hugo { - - /// \addtogroup graphmaps - /// @{ - - /** The base class all of the map iterators. - * The class defines the typedefs of the iterators, - * simple step functions and equality operators. - */ - - template - class MapIteratorBase { - - public: - - /// The key type of the iterator. - typedef typename Map::KeyType KeyType; - /// The iterator to iterate on the keys. - typedef typename Map::KeyIt KeyIt; - - /// The value type of the iterator. - typedef typename Map::ValueType ValueType; - /// The reference type of the iterator. - typedef typename Map::ReferenceType ReferenceType; - /// The pointer type of the iterator. - typedef typename Map::PointerType PointerType; - - /// The const value type of the iterator. - typedef typename Map::ConstValueType ConstValueType; - /// The const reference type of the iterator. - typedef typename Map::ConstReferenceType ConstReferenceType; - /// The pointer type of the iterator. - typedef typename Map::ConstPointerType ConstPointerType; - - protected: - - KeyIt it; - - /// Default constructor. - MapIteratorBase() {} - - /// KeyIt initialized MapIteratorBase constructor. - MapIteratorBase(const KeyIt pit) : it(pit) {} - - public: - - /// Stepping forward in the map. - void increment() { - ++it; - } - - /// The equality operator of the map. - bool operator==(const MapIteratorBase& pit) const { - return pit.it == it; - } - - /// The not-equality operator of the map. - bool operator!=(const MapIteratorBase& pit) const { - return !(*this == pit); - } - }; - - template class MapConstIterator; - - /** Compatible iterator with the stl maps' iterators. - * It iterates on pairs of a key and a value. - */ - template - class MapIterator : public MapIteratorBase { - - friend class MapConstIterator; - - - public: - - /// The iterator base class. - typedef MapIteratorBase Base; - - /// The key type of the iterator. - typedef typename Map::KeyType KeyType; - /// The iterator to iterate on the keys. - typedef typename Map::KeyIt KeyIt; - - /// The value type of the iterator. - typedef typename Map::ValueType ValueType; - /// The reference type of the iterator. - typedef typename Map::ReferenceType ReferenceType; - /// The pointer type of the iterator. - typedef typename Map::PointerType PointerType; - - /// The const value type of the iterator. - typedef typename Map::ConstValueType ConstValueType; - /// The const reference type of the iterator. - typedef typename Map::ConstReferenceType ConstReferenceType; - /// The pointer type of the iterator. - typedef typename Map::ConstPointerType ConstPointerType; - - public: - - /// The value type of the iterator. - typedef extended_pair PairValueType; - - /// The reference type of the iterator. - typedef extended_pair PairReferenceType; - - /// Default constructor. - MapIterator() {} - - /// Constructor to initalize the iterators returned - /// by the begin() and end(). - MapIterator(Map& pmap, const KeyIt& pit) : Base(pit), map(&pmap) {} - - /// Dereference operator for the iterator. - PairReferenceType operator*() { - return PairReferenceType(Base::it, (*map)[Base::it]); - } - - /// The pointer type of the iterator. - class PairPointerType { - friend class MapIterator; - private: - PairReferenceType data; - PairPointerType(const KeyType& key, ReferenceType val) - : data(key, val) {} - public: - PairReferenceType* operator->() {return &data;} - }; - - /// Arrow operator for the iterator. - PairPointerType operator->() { - return PairPointerType(Base::it, ((*map)[Base::it])); - } - - /// The pre increment operator of the iterator. - MapIterator& operator++() { - Base::increment(); - return *this; - } - - /// The post increment operator of the iterator. - MapIterator operator++(int) { - MapIterator tmp(*this); - Base::increment(); - return tmp; - } - - private: - Map* map; - - public: - // STL compatibility typedefs. - typedef std::forward_iterator_tag iterator_category; - typedef int difference_type; - typedef PairValueType value_type; - typedef PairReferenceType reference; - typedef PairPointerType pointer; - }; - - /** Compatible iterator with the stl maps' iterators. - * It iterates on pairs of a key and a value. - */ - template - class MapConstIterator : public MapIteratorBase { - - public: - - /// The iterator base class. - typedef MapIteratorBase Base; - - /// The key type of the iterator. - typedef typename Map::KeyType KeyType; - /// The iterator to iterate on the keys. - typedef typename Map::KeyIt KeyIt; - - /// The value type of the iterator. - typedef typename Map::ValueType ValueType; - /// The reference type of the iterator. - typedef typename Map::ReferenceType ReferenceType; - /// The pointer type of the iterator. - typedef typename Map::PointerType PointerType; - - /// The const value type of the iterator. - typedef typename Map::ConstValueType ConstValueType; - /// The const reference type of the iterator. - typedef typename Map::ConstReferenceType ConstReferenceType; - /// The pointer type of the iterator. - typedef typename Map::ConstPointerType ConstPointerType; - - public: - - /// Default constructor. - MapConstIterator() {} - - /// Constructor to initalize the the iterators returned - /// by the begin() and end(). - MapConstIterator(const Map& pmap, const KeyIt& pit) - : Base(pit), map(&pmap) {} - - /// Constructor to create const iterator from a non const. - MapConstIterator(const MapIterator& pit) { - Base::it = pit.Base::it; - map = pit.map; - } - - /// The value type of the iterator. - typedef extended_pair PairValueType; - - /// The reference type of map. - typedef extended_pair PairReferenceType; - - /// Dereference operator for the iterator. - PairReferenceType operator*() { - return PairReferenceType(Base::it, (*map)[Base::it]); - } - - /// The pointer type of the iterator. - class PairPointerType { - friend class MapConstIterator; - private: - PairReferenceType data; - PairPointerType(const KeyType& key, ConstReferenceType val) - : data(key, val) {} - public: - PairReferenceType* operator->() {return &data;} - }; - - /// Arrow operator for the iterator. - PairPointerType operator->() { - return PairPointerType(Base::it, (*map)[Base::it]); - } - - /// The pre increment operator of the iterator. - MapConstIterator& operator++() { - Base::increment(); - return *this; - } - - /// The post increment operator of the iterator. - MapConstIterator operator++(int) { - MapConstIterator tmp(*this); - Base::increment(); - return tmp; - } - - private: - const Map* map; - - public: - // STL compatibility typedefs. - typedef std::input_iterator_tag iterator_category; - typedef int difference_type; - typedef PairValueType value_type; - typedef PairReferenceType reference; - typedef PairPointerType pointer; - }; - - /** The class makes the KeyIt to an stl compatible iterator - * with dereferencing operator. - */ - template - class MapKeyIterator : public MapIteratorBase { - - public: - - /// The iterator base class. - typedef MapIteratorBase Base; - - /// The key type of the iterator. - typedef typename Map::KeyType KeyType; - /// The iterator to iterate on the keys. - typedef typename Map::KeyIt KeyIt; - - public: - - /// Default constructor. - MapKeyIterator() {} - - /// KeyIt initialized iterator. - MapKeyIterator(const KeyIt& pit) : Base(pit) {} - - /// The pre increment operator of the iterator. - MapKeyIterator& operator++() { - Base::increment(); - return *this; - } - - /// The post increment operator of the iterator. - MapKeyIterator operator++(int) { - MapKeyIterator tmp(*this); - Base::increment(); - return tmp; - } - - /// The dereferencing operator of the iterator. - KeyType operator*() const { - return static_cast(Base::it); - } - - public: - // STL compatibility typedefs. - typedef std::input_iterator_tag iterator_category; - typedef int difference_type; - typedef KeyType value_type; - typedef const KeyType& reference; - typedef const KeyType* pointer; - }; - - template class MapConstValueIterator; - - /** MapValueIterator creates an stl compatible iterator - * for the values. - */ - template - class MapValueIterator : public MapIteratorBase { - - friend class MapConstValueIterator; - - public: - - /// The iterator base class. - typedef MapIteratorBase Base; - - /// The key type of the iterator. - typedef typename Map::KeyType KeyType; - /// The iterator to iterate on the keys. - typedef typename Map::KeyIt KeyIt; - - - /// The value type of the iterator. - typedef typename Map::ValueType ValueType; - /// The reference type of the iterator. - typedef typename Map::ReferenceType ReferenceType; - /// The pointer type of the iterator. - typedef typename Map::PointerType PointerType; - - /// The const value type of the iterator. - typedef typename Map::ConstValueType ConstValueType; - /// The const reference type of the iterator. - typedef typename Map::ConstReferenceType ConstReferenceType; - /// The pointer type of the iterator. - typedef typename Map::ConstPointerType ConstPointerType; - - private: - - Map* map; - - public: - - /// Default constructor. - MapValueIterator() {} - - /// Map and KeyIt initialized iterator. - MapValueIterator(Map& pmap, const KeyIt& pit) - : Base(pit), map(&pmap) {} - - - /// The pre increment operator of the iterator. - MapValueIterator& operator++() { - Base::increment(); - return *this; - } - - /// The post increment operator of the iterator. - MapValueIterator operator++(int) { - MapValueIterator tmp(*this); - Base::increment(); - return tmp; - } - - /// The dereferencing operator of the iterator. - ReferenceType operator*() const { - return (*map)[Base::it]; - } - - /// The arrow operator of the iterator. - PointerType operator->() const { - return &(operator*()); - } - - public: - // STL compatibility typedefs. - typedef std::forward_iterator_tag iterator_category; - typedef int difference_type; - typedef ValueType value_type; - typedef ReferenceType reference; - typedef PointerType pointer; - }; - - /** MapValueIterator creates an stl compatible iterator - * for the const values. - */ - - template - class MapConstValueIterator : public MapIteratorBase { - - public: - - /// The iterator base class. - typedef MapIteratorBase Base; - - /// The key type of the iterator. - typedef typename Map::KeyType KeyType; - /// The iterator to iterate on the keys. - typedef typename Map::KeyIt KeyIt; - - /// The value type of the iterator. - typedef typename Map::ValueType ValueType; - /// The reference type of the iterator. - typedef typename Map::ReferenceType ReferenceType; - /// The pointer type of the iterator. - typedef typename Map::PointerType PointerType; - - /// The const value type of the iterator. - typedef typename Map::ConstValueType ConstValueType; - /// The const reference type of the iterator. - typedef typename Map::ConstReferenceType ConstReferenceType; - /// The pointer type of the iterator. - typedef typename Map::ConstPointerType ConstPointerType; - - private: - - const Map* map; - - public: - - /// Default constructor. - MapConstValueIterator() {} - - /// Constructor to create const iterator from a non const. - MapConstValueIterator(const MapValueIterator& pit) { - Base::it = pit.Base::it; - map = pit.map; - } - - /// Map and KeyIt initialized iterator. - MapConstValueIterator(const Map& pmap, const KeyIt& pit) - : Base(pit), map(&pmap) {} - - /// The pre increment operator of the iterator. - MapConstValueIterator& operator++() { - Base::increment(); - return *this; - } - - /// The post increment operator of the iterator. - MapConstValueIterator operator++(int) { - MapConstValueIterator tmp(*this); - Base::increment(); - return tmp; - } - - /// The dereferencing operator of the iterator. - ConstReferenceType operator*() const { - return (*map)[Base::it]; - } - - /// The arrow operator of the iterator. - ConstPointerType operator->() const { - return &(operator*()); - } - - public: - // STL compatibility typedefs. - typedef std::input_iterator_tag iterator_category; - typedef int difference_type; - typedef ValueType value_type; - typedef ConstReferenceType reference; - typedef ConstPointerType pointer; - }; - - - /** This class makes from a map an iteratable set - * which contains all the keys of the map. - */ - template - class MapConstKeySet { - - const Map* map; - - public: - - /// The key type of the iterator. - typedef typename Map::KeyType KeyType; - /// The iterator to iterate on the keys. - typedef typename Map::KeyIt KeyIt; - - - /// The value type of the iterator. - typedef typename Map::ValueType ValueType; - /// The reference type of the iterator. - typedef typename Map::ReferenceType ReferenceType; - /// The pointer type of the iterator. - typedef typename Map::PointerType PointerType; - - /// The const value type of the iterator. - typedef typename Map::ConstValueType ConstValueType; - /// The const reference type of the iterator. - typedef typename Map::ConstReferenceType ConstReferenceType; - /// The pointer type of the iterator. - typedef typename Map::ConstPointerType ConstPointerType; - - /// The map initialized const key set. - MapConstKeySet(const Map& pmap) : map(&pmap) {} - - /// The const iterator of the set. - typedef MapKeyIterator ConstIterator; - - /// It gives back the const iterator pointed to the first element. - ConstIterator begin() const { - return ConstIterator(KeyIt(*map->getGraph())); - } - - /// It gives back the const iterator pointed to the first ivalid element. - ConstIterator end() const { - return ConstIterator(KeyIt(INVALID)); - } - - public: - // STL compatibility typedefs. - typedef ValueType value_type; - typedef ConstIterator const_iterator; - typedef ConstReferenceType const_reference; - typedef ConstPointerType const_pointer; - typedef int difference_type; - }; - - /** This class makes from a map an iteratable set - * which contains all the values of the map. - * The values cannot be modified. - */ - template - class MapConstValueSet { - - const Map* map; - - public: - - /// The key type of the iterator. - typedef typename Map::KeyType KeyType; - /// The iterator to iterate on the keys. - typedef typename Map::KeyIt KeyIt; - - - /// The value type of the iterator. - typedef typename Map::ValueType ValueType; - /// The reference type of the iterator. - typedef typename Map::ReferenceType ReferenceType; - /// The pointer type of the iterator. - typedef typename Map::PointerType PointerType; - - /// The const value type of the iterator. - typedef typename Map::ConstValueType ConstValueType; - /// The const reference type of the iterator. - typedef typename Map::ConstReferenceType ConstReferenceType; - /// The pointer type of the iterator. - typedef typename Map::ConstPointerType ConstPointerType; - - /// The map initialized const value set. - MapConstValueSet(const Map& pmap) : map(&pmap) {} - - /// The const iterator of the set. - typedef MapConstValueIterator ConstIterator; - - /// It gives back the const iterator pointed to the first element. - ConstIterator begin() const { - return ConstIterator(*map, KeyIt(*map->getGraph())); - } - - /// It gives back the const iterator pointed to the first invalid element. - ConstIterator end() const { - return ConstIterator(*map, KeyIt(INVALID)); - } - - public: - // STL compatibility typedefs. - typedef ValueType value_type; - typedef ConstIterator const_iterator; - typedef ConstReferenceType const_reference; - typedef ConstPointerType const_pointer; - typedef int difference_type; - }; - - - /** This class makes from a map an iteratable set - * which contains all the values of the map. - * The values can be modified. - */ - template - class MapValueSet { - - Map* map; - - public: - - /// The key type of the iterator. - typedef typename Map::KeyType KeyType; - /// The iterator to iterate on the keys. - typedef typename Map::KeyIt KeyIt; - - - /// The value type of the iterator. - typedef typename Map::ValueType ValueType; - /// The reference type of the iterator. - typedef typename Map::ReferenceType ReferenceType; - /// The pointer type of the iterator. - typedef typename Map::PointerType PointerType; - - /// The const value type of the iterator. - typedef typename Map::ConstValueType ConstValueType; - /// The const reference type of the iterator. - typedef typename Map::ConstReferenceType ConstReferenceType; - /// The pointer type of the iterator. - typedef typename Map::ConstPointerType ConstPointerType; - - /// The map initialized value set. - MapValueSet(Map& pmap) : map(&pmap) {} - - /// The const iterator of the set. - typedef MapConstValueIterator ConstIterator; - - /// It gives back the const iterator pointed to the first element. - ConstIterator begin() const { - return ConstIterator(*map, KeyIt(*map->getGraph())); - } - - /// It gives back the const iterator pointed to the first invalid element. - ConstIterator end() const { - return ConstIterator(*map, KeyIt(INVALID)); - } - - /// The iterator of the set. - typedef MapValueIterator Iterator; - - /// It gives back the iterator pointed to the first element. - Iterator begin() { - return Iterator(*map, KeyIt(*map->getGraph())); - } - - /// It gives back the iterator pointed to the first invalid element. - Iterator end() { - return Iterator(*map, KeyIt(INVALID)); - } - - public: - // STL compatibility typedefs. - typedef ValueType value_type; - typedef Iterator iterator; - typedef ConstIterator const_iterator; - typedef ReferenceType reference; - typedef ConstReferenceType const_reference; - typedef PointerType pointer; - typedef ConstPointerType const_pointer; - typedef int difference_type; - - }; - - /// @} - -} - -#endif diff -r 2d6c8075d9d0 -r 818510fa3d99 src/hugo/map_registry.h --- a/src/hugo/map_registry.h Wed Sep 29 14:12:26 2004 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,289 +0,0 @@ -/* -*- C++ -*- - * src/hugo/map_registry.h - Part of HUGOlib, a generic C++ optimization library - * - * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport - * (Egervary Combinatorial Optimization Research Group, 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 HUGO_MAP_REGISTRY_H -#define HUGO_MAP_REGISTRY_H - -#include - -///\ingroup graphmapfactory -///\file -///\brief Map registry for graph maps. - -using namespace std; - -namespace hugo { - -/// \addtogroup graphmapfactory -/// @{ - -/** - * Registry class to register edge or node maps into the graph. The - * registry helps you to implement an observer pattern. If you add - * or erase an edge or node you must notify all the maps about the - * event. -*/ - template - class MapRegistry { - public: - typedef G Graph; - typedef K KeyType; - typedef KIt KeyIt; - - /** - * MapBase is the base class of the registered maps. - * It defines the core modification operations on the maps and - * implements some helper functions. - */ - class MapBase { - public: - typedef G Graph; - typedef K KeyType; - typedef KIt KeyIt; - - typedef MapRegistry Registry; - - friend class MapRegistry; - - /** - * Default constructor for MapBase. - */ - - MapBase() : graph(0), registry(0) {} - - /** - * Simple constructor to register into a graph registry. - */ - - MapBase(const Graph& g, Registry& r) : graph(&g), registry(0) { - r.attach(*this); - } - - /** - * Copy constructor to register into the registry. - */ - - MapBase(const MapBase& copy) : graph(copy.graph), registry(0) { - if (copy.registry) { - copy.registry->attach(*this); - } - } - - /** - * Assign operator. - */ - const MapBase& operator=(const MapBase& copy) { - if (registry) { - registry->detach(*this); - } - graph = copy.graph; - if (copy.registry) { - copy.registry->attach(*this); - } - return *this; - } - - - /** - * Destructor. - */ - - virtual ~MapBase() { - if (registry) { - registry->detach(*this); - } - } - - /* - * Returns the graph that the map belongs to. - */ - - const Graph* getGraph() const { return graph; } - - protected: - - const Graph* graph; - Registry* registry; - - int registry_index; - - protected: - - /** - Helper function to implement constructors in the subclasses. - */ - - virtual void init() { - for (KeyIt it(*graph); it != INVALID; ++it) { - add(it); - } - } - - /** - Helper function to implement the destructor in the subclasses. - */ - - virtual void destroy() { - for (KeyIt it(*getGraph()); it != INVALID; ++it) { - erase(it); - } - } - - /** - The add member function should be overloaded in the subclasses. - \e Add extends the map with the new node. - */ - - virtual void add(const KeyType&) = 0; - /** - The erase member function should be overloaded in the subclasses. - \e Erase removes the node from the map. - */ - - virtual void erase(const KeyType&) = 0; - - /** - * The clear member function should be overloaded in the subclasses. - * \e Clear makes empty the data structure. - */ - - virtual void clear() = 0; - - /** - Exception class to throw at unsupported operation. - */ - - class NotSupportedOperationException {}; - - }; - - protected: - - /** - * The container type of the maps. - */ - typedef std::vector Container; - - /** - * The container of the registered maps. - */ - Container container; - - - public: - - /** - * Default Constructor of the MapRegistry. It creates an empty registry. - */ - MapRegistry() {} - - /** - * Copy Constructor of the MapRegistry. The new registry does not steal - * the maps from the right value. The new registry will be an empty. - */ - MapRegistry(const MapRegistry&) {} - - /** - * Assign operator. The left value does not steal the maps - * from the right value. The left value will be an empty registry. - */ - MapRegistry& operator=(const MapRegistry&) { - typename Container::iterator it; - for (it = container.begin(); it != container.end(); ++it) { - (*it)->destroy(); - (*it)->graph = 0; - (*it)->registry = 0; - } - } - - /** - * Destructor of the MapRegistry. - */ - ~MapRegistry() { - typename Container::iterator it; - for (it = container.begin(); it != container.end(); ++it) { - (*it)->destroy(); - (*it)->registry = 0; - (*it)->graph = 0; - } - } - - - public: - - /** - * Attach a map into thr registry. If the map has been attached - * into an other registry it is detached from that automaticly. - */ - void attach(MapBase& map) { - if (map.registry) { - map.registry->detach(map); - } - container.push_back(&map); - map.registry = this; - map.registry_index = container.size()-1; - } - - /** - * Detach the map from the registry. - */ - void detach(MapBase& map) { - container.back()->registry_index = map.registry_index; - container[map.registry_index] = container.back(); - container.pop_back(); - map.registry = 0; - map.graph = 0; - } - - - /** - * Notify all the registered maps about a Key added. - */ - void add(KeyType& key) { - typename Container::iterator it; - for (it = container.begin(); it != container.end(); ++it) { - (*it)->add(key); - } - } - - /** - * Notify all the registered maps about a Key erased. - */ - void erase(KeyType& key) { - typename Container::iterator it; - for (it = container.begin(); it != container.end(); ++it) { - (*it)->erase(key); - } - } - - /** - * Notify all the registered maps about the map should be cleared. - */ - void clear() { - typename Container::iterator it; - for (it = container.begin(); it != container.end(); ++it) { - (*it)->clear(); - } - } - }; - - -/// @} - - -} - -#endif diff -r 2d6c8075d9d0 -r 818510fa3d99 src/hugo/maps.h --- a/src/hugo/maps.h Wed Sep 29 14:12:26 2004 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,176 +0,0 @@ -/* -*- C++ -*- - * src/hugo/maps.h - Part of HUGOlib, a generic C++ optimization library - * - * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport - * (Egervary Combinatorial Optimization Research Group, 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 HUGO_MAPS_H -#define HUGO_MAPS_H - -///\file -///\brief Miscellaneous property maps -/// -///\todo This file has the same name as the concept file in skeletons, -/// and this is not easily detectable in docs... - -#include - -namespace hugo { - - /// Base class of maps. - - /// Base class of maps. - /// It provides the necessary typedefs required by the map concept. - template - class MapBase - { - public: - ///\e - typedef K KeyType; - ///\e - typedef T ValueType; - }; - - /// Null map. (a.k.a. DoNothingMap) - - /// If you have to provide a map only for its type definitions, - /// or if you have to provide a writable map, but - /// data written to it will sent to /dev/null... - template - class NullMap : public MapBase - { - public: - - /// Gives back a default constructed element. - T operator[](const K&) const { return T(); } - /// Absorbs the value. - void set(const K&, const T&) {} - }; - - - /// Constant map. - - /// This is a readable map which assigns a specified value to each key. - /// In other aspects it is equivalent to the \ref NullMap. - /// \todo set could be used to set the value. - template - class ConstMap : public MapBase - { - T v; - public: - - /// Default constructor - - /// The value of the map will be uninitialized. - /// (More exactly it will be default constructed.) - ConstMap() {} - ///\e - - /// \param _v The initial value of the map. - /// - ConstMap(const T &_v) : v(_v) {} - - T operator[](const K&) const { return v; } - void set(const K&, const T&) {} - - template - struct rebind { - typedef ConstMap other; - }; - - template - ConstMap(const ConstMap &, const T &_v) : v(_v) {} - }; - - //to document later - template - struct Const { }; - //to document later - template - class ConstMap > : public MapBase - { - public: - ConstMap() { } - V operator[](const K&) const { return v; } - void set(const K&, const V&) { } - }; - //to document later - typedef Const True; - typedef Const False; - - /// \c std::map wrapper - - /// This is essentially a wrapper for \c std::map. With addition that - /// you can specify a default value different from \c ValueType() . - /// - /// \todo Provide allocator parameter... - template > - class StdMap : public std::map { - typedef std::map parent; - T v; - typedef typename parent::value_type PairType; - - public: - typedef Key KeyType; - typedef T ValueType; - typedef T& ReferenceType; - typedef const T& ConstReferenceType; - - - StdMap() : v() {} - /// Constructor with specified default value - StdMap(const T& _v) : v(_v) {} - - /// \brief Constructs the map from an appropriate std::map. - /// - /// \warning Inefficient: copies the content of \c m ! - StdMap(const parent &m) : parent(m) {} - /// \brief Constructs the map from an appropriate std::map, and explicitly - /// specifies a default value. - /// - /// \warning Inefficient: copies the content of \c m ! - StdMap(const parent &m, const T& _v) : parent(m), v(_v) {} - - template - StdMap(const StdMap &m, const T &_v) { - //FIXME; - } - - ReferenceType operator[](const Key &k) { - return insert(PairType(k,v)).first -> second; - } - ConstReferenceType operator[](const Key &k) const { - typename parent::iterator i = lower_bound(k); - if (i == parent::end() || parent::key_comp()(k, (*i).first)) - return v; - return (*i).second; - } - void set(const Key &k, const T &t) { - parent::operator[](k) = t; - } - - /// Changes the default value of the map. - /// \return Returns the previous default value. - /// - /// \warning The value of some keys (which has already been queried, but - /// the value has been unchanged from the default) may change! - T setDefault(const T &_v) { T old=v; v=_v; return old; } - - template - struct rebind { - typedef StdMap other; - }; - }; - -} -#endif // HUGO_MAPS_H diff -r 2d6c8075d9d0 -r 818510fa3d99 src/hugo/min_cost_flow.h --- a/src/hugo/min_cost_flow.h Wed Sep 29 14:12:26 2004 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,256 +0,0 @@ -/* -*- C++ -*- - * src/hugo/min_cost_flow.h - Part of HUGOlib, a generic C++ optimization library - * - * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport - * (Egervary Combinatorial Optimization Research Group, 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 HUGO_MIN_COST_FLOW_H -#define HUGO_MIN_COST_FLOW_H - -///\ingroup flowalgs -///\file -///\brief An algorithm for finding a flow of value \c k (for small values of \c k) having minimal total cost - - -#include -#include -#include -#include - -namespace hugo { - -/// \addtogroup flowalgs -/// @{ - - ///\brief Implementation of an algorithm for finding a flow of value \c k - ///(for small values of \c k) having minimal total cost between 2 nodes - /// - /// - /// The class \ref hugo::MinCostFlow "MinCostFlow" implements - /// an algorithm for finding a flow of value \c k - /// having minimal total cost - /// from a given source node to a given target node in an - /// edge-weighted directed graph. To this end, - /// the edge-capacities and edge-weitghs have to be nonnegative. - /// The edge-capacities should be integers, but the edge-weights can be - /// integers, reals or of other comparable numeric type. - /// This algorithm is intended to use only for small values of \c k, - /// since it is only polynomial in k, - /// not in the length of k (which is log k). - /// In order to find the minimum cost flow of value \c k it - /// finds the minimum cost flow of value \c i for every - /// \c i between 0 and \c k. - /// - ///\param Graph The directed graph type the algorithm runs on. - ///\param LengthMap The type of the length map. - ///\param CapacityMap The capacity map type. - /// - ///\author Attila Bernath - template - class MinCostFlow { - - typedef typename LengthMap::ValueType Length; - - //Warning: this should be integer type - typedef typename CapacityMap::ValueType Capacity; - - typedef typename Graph::Node Node; - typedef typename Graph::NodeIt NodeIt; - typedef typename Graph::Edge Edge; - typedef typename Graph::OutEdgeIt OutEdgeIt; - typedef typename Graph::template EdgeMap EdgeIntMap; - - - typedef ResGraphWrapper ResGW; - typedef typename ResGW::Edge ResGraphEdge; - - class ModLengthMap { - typedef typename Graph::template NodeMap NodeMap; - const ResGW& G; - const LengthMap &ol; - const NodeMap &pot; - public : - typedef typename LengthMap::KeyType KeyType; - typedef typename LengthMap::ValueType ValueType; - - ValueType operator[](typename ResGW::Edge e) const { - if (G.forward(e)) - return ol[e]-(pot[G.head(e)]-pot[G.tail(e)]); - else - return -ol[e]-(pot[G.head(e)]-pot[G.tail(e)]); - } - - ModLengthMap(const ResGW& _G, - const LengthMap &o, const NodeMap &p) : - G(_G), /*rev(_rev),*/ ol(o), pot(p){}; - };//ModLengthMap - - - protected: - - //Input - const Graph& G; - const LengthMap& length; - const CapacityMap& capacity; - - - //auxiliary variables - - //To store the flow - EdgeIntMap flow; - //To store the potential (dual variables) - typedef typename Graph::template NodeMap PotentialMap; - PotentialMap potential; - - - Length total_length; - - - public : - - /// The constructor of the class. - - ///\param _G The directed graph the algorithm runs on. - ///\param _length The length (weight or cost) of the edges. - ///\param _cap The capacity of the edges. - MinCostFlow(Graph& _G, LengthMap& _length, CapacityMap& _cap) : G(_G), - length(_length), capacity(_cap), flow(_G), potential(_G){ } - - - ///Runs the algorithm. - - ///Runs the algorithm. - ///Returns k if there is a flow of value at least k edge-disjoint - ///from s to t. - ///Otherwise it returns the maximum value of a flow from s to t. - /// - ///\param s The source node. - ///\param t The target node. - ///\param k The value of the flow we are looking for. - /// - ///\todo May be it does make sense to be able to start with a nonzero - /// feasible primal-dual solution pair as well. - int run(Node s, Node t, int k) { - - //Resetting variables from previous runs - total_length = 0; - - for (typename Graph::EdgeIt e(G); e!=INVALID; ++e) flow.set(e, 0); - - //Initialize the potential to zero - for (typename Graph::NodeIt n(G); n!=INVALID; ++n) potential.set(n, 0); - - - //We need a residual graph - ResGW res_graph(G, capacity, flow); - - - ModLengthMap mod_length(res_graph, length, potential); - - Dijkstra dijkstra(res_graph, mod_length); - - int i; - for (i=0; i 0 && fl_e != 0) - return false; - if (mod_pot < 0 && fl_e != capacity[e]) - return false; - } - } - return true; - } - - - }; //class MinCostFlow - - ///@} - -} //namespace hugo - -#endif //HUGO_MIN_COST_FLOW_H diff -r 2d6c8075d9d0 -r 818510fa3d99 src/hugo/path.h --- a/src/hugo/path.h Wed Sep 29 14:12:26 2004 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,709 +0,0 @@ -/* -*- C++ -*- - * src/hugo/path.h - Part of HUGOlib, a generic C++ optimization library - * - * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport - * (Egervary Combinatorial Optimization Research Group, 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. - * - */ - -/** -@defgroup paths Path Structures -@ingroup datas -\brief Path structures implemented in Hugo. - -Hugolib provides flexible data structures -to work with paths. - -All of them have the same interface, especially they can be built or extended -using a standard Builder subclass. This make is easy to have e.g. the Dijkstra -algorithm to store its result in any kind of path structure. - -\sa hugo::skeleton::Path - -*/ - -///\ingroup paths -///\file -///\brief Classes for representing paths in graphs. - -#ifndef HUGO_PATH_H -#define HUGO_PATH_H - -#include -#include -#include - -#include - -namespace hugo { - - /// \addtogroup paths - /// @{ - - - //! \brief A structure for representing directed paths in a graph. - //! - //! A structure for representing directed path in a graph. - //! \param Graph The graph type in which the path is. - //! \param DM DebugMode, defaults to DefaultDebugMode. - //! - //! In a sense, the path can be treated as a graph, for is has \c NodeIt - //! and \c EdgeIt with the same usage. These types converts to the \c Node - //! and \c Edge of the original graph. - //! - //! \todo Thoroughfully check all the range and consistency tests. - template - class DirPath { - public: - /// Edge type of the underlying graph. - typedef typename Graph::Edge GraphEdge; - /// Node type of the underlying graph. - typedef typename Graph::Node GraphNode; - class NodeIt; - class EdgeIt; - - protected: - const Graph *gr; - typedef std::vector Container; - Container edges; - - public: - - /// \param _G The graph in which the path is. - /// - DirPath(const Graph &_G) : gr(&_G) {} - - /// \brief Subpath constructor. - /// - /// Subpath defined by two nodes. - /// \warning It is an error if the two edges are not in order! - DirPath(const DirPath &P, const NodeIt &a, const NodeIt &b) { - gr = P.gr; - edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx); - } - - /// \brief Subpath constructor. - /// - /// Subpath defined by two edges. Contains edges in [a,b) - /// \warning It is an error if the two edges are not in order! - DirPath(const DirPath &P, const EdgeIt &a, const EdgeIt &b) { - gr = P.gr; - edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx); - } - - /// Length of the path. - size_t length() const { return edges.size(); } - /// Returns whether the path is empty. - bool empty() const { return edges.empty(); } - - /// Resets the path to an empty path. - void clear() { edges.clear(); } - - /// \brief Starting point of the path. - /// - /// Starting point of the path. - /// Returns INVALID if the path is empty. - GraphNode tail() const { - return empty() ? INVALID : gr->tail(edges[0]); - } - /// \brief End point of the path. - /// - /// End point of the path. - /// Returns INVALID if the path is empty. - GraphNode head() const { - return empty() ? INVALID : gr->head(edges[length()-1]); - } - - /// \brief Initializes node or edge iterator to point to the first - /// node or edge. - /// - /// \sa nth - template - It& first(It &i) const { return i=It(*this); } - - /// \brief Initializes node iterator to point to the node of a given index. - NodeIt& nth(NodeIt &i, int n) const { - return i=NodeIt(*this, n); - } - - /// \brief Initializes edge iterator to point to the edge of a given index. - EdgeIt& nth(EdgeIt &i, int n) const { - return i=EdgeIt(*this, n); - } - - /// \brief Returns node iterator pointing to the head node of the - /// given edge iterator. - NodeIt head(const EdgeIt& e) const { - return NodeIt(*this, e.idx+1); - } - - /// \brief Returns node iterator pointing to the tail node of the - /// given edge iterator. - NodeIt tail(const EdgeIt& e) const { - return NodeIt(*this, e.idx); - } - - - /* Iterator classes */ - - /** - * \brief Iterator class to iterate on the edges of the paths - * - * \ingroup paths - * This class is used to iterate on the edges of the paths - * - * Of course it converts to Graph::Edge - * - */ - class EdgeIt { - friend class DirPath; - - int idx; - const DirPath *p; - public: - /// Default constructor - EdgeIt() {} - /// Invalid constructor - EdgeIt(Invalid) : idx(-1), p(0) {} - /// Constructor with starting point - EdgeIt(const DirPath &_p, int _idx = 0) : - idx(_idx), p(&_p) { validate(); } - - ///Validity check - bool valid() const { return idx!=-1; } - - ///Conversion to Graph::Edge - operator GraphEdge () const { - return valid() ? p->edges[idx] : INVALID; - } - - /// Next edge - EdgeIt& operator++() { ++idx; validate(); return *this; } - - /// Comparison operator - bool operator==(const EdgeIt& e) const { return idx==e.idx; } - /// Comparison operator - bool operator!=(const EdgeIt& e) const { return idx!=e.idx; } - /// Comparison operator - bool operator<(const EdgeIt& e) const { return idx= p->length() ) idx=-1; } - }; - - /** - * \brief Iterator class to iterate on the nodes of the paths - * - * \ingroup paths - * This class is used to iterate on the nodes of the paths - * - * Of course it converts to Graph::Node - * - */ - class NodeIt { - friend class DirPath; - - int idx; - const DirPath *p; - public: - /// Default constructor - NodeIt() {} - /// Invalid constructor - NodeIt(Invalid) : idx(-1), p(0) {} - /// Constructor with starting point - NodeIt(const DirPath &_p, int _idx = 0) : - idx(_idx), p(&_p) { validate(); } - - ///Validity check - bool valid() const { return idx!=-1; } - - ///Conversion to Graph::Node - operator const GraphNode& () const { - if(idx >= p->length()) - return p->head(); - else if(idx >= 0) - return p->gr->tail(p->edges[idx]); - else - return INVALID; - } - /// Next node - NodeIt& operator++() { ++idx; validate(); return *this; } - - /// Comparison operator - bool operator==(const NodeIt& e) const { return idx==e.idx; } - /// Comparison operator - bool operator!=(const NodeIt& e) const { return idx!=e.idx; } - /// Comparison operator - bool operator<(const NodeIt& e) const { return idx p->length() ) idx=-1; } - }; - - friend class Builder; - - /** - * \brief Class to build paths - * - * \ingroup paths - * This class is used to fill a path with edges. - * - * You can push new edges to the front and to the back of the path in - * arbitrary order then you should commit these changes to the graph. - * - * Fundamentally, for most "Paths" (classes fulfilling the - * PathConcept) while the builder is active (after the first modifying - * operation and until the commit()) the original Path is in a - * "transitional" state (operations on it have undefined result). But - * in the case of DirPath the original path remains unchanged until the - * commit. However we don't recomend that you use this feature. - */ - class Builder { - DirPath &P; - Container front, back; - - public: - ///\param _P the path you want to fill in. - /// - Builder(DirPath &_P) : P(_P) {} - - /// Sets the starting node of the path. - - /// Sets the starting node of the path. Edge added to the path - /// afterwards have to be incident to this node. - /// It should be called if and only if - /// the path is empty and before any call to - /// \ref pushFront() or \ref pushBack() - void setStartNode(const GraphNode &) {} - - ///Push a new edge to the front of the path - - ///Push a new edge to the front of the path. - ///\sa setStartNode - void pushFront(const GraphEdge& e) { - front.push_back(e); - } - - ///Push a new edge to the back of the path - - ///Push a new edge to the back of the path. - ///\sa setStartNode - void pushBack(const GraphEdge& e) { - back.push_back(e); - } - - ///Commit the changes to the path. - void commit() { - if( !front.empty() || !back.empty() ) { - Container tmp; - tmp.reserve(front.size()+back.size()+P.length()); - tmp.insert(tmp.end(), front.rbegin(), front.rend()); - tmp.insert(tmp.end(), P.edges.begin(), P.edges.end()); - tmp.insert(tmp.end(), back.begin(), back.end()); - P.edges.swap(tmp); - front.clear(); - back.clear(); - } - } - - ///Reserve storage for the builder in advance. - - ///If you know a reasonable upper bound of the number of the edges - ///to add to the front, using this function you can speed up the building. - - void reserveFront(size_t r) {front.reserve(r);} - - ///Reserve storage for the builder in advance. - - ///If you know a reasonable upper bound of the number of the edges - ///to add to the back, using this function you can speed up the building. - - void reserveBack(size_t r) {back.reserve(r);} - - private: - bool empty() { - return front.empty() && back.empty() && P.empty(); - } - - GraphNode tail() const { - if( ! front.empty() ) - return P.gr->tail(front[front.size()-1]); - else if( ! P.empty() ) - return P.gr->tail(P.edges[0]); - else if( ! back.empty() ) - return P.gr->tail(back[0]); - else - return INVALID; - } - GraphNode head() const { - if( ! back.empty() ) - return P.gr->head(back[back.size()-1]); - else if( ! P.empty() ) - return P.gr->head(P.edges[P.length()-1]); - else if( ! front.empty() ) - return P.gr->head(front[0]); - else - return INVALID; - } - - }; - - }; - - - - - - - - - - - /**********************************************************************/ - - - //! \brief A structure for representing undirected path in a graph. - //! - //! A structure for representing undirected path in a graph. Ie. this is - //! a path in a \e directed graph but the edges should not be directed - //! forward. - //! - //! \param Graph The graph type in which the path is. - //! \param DM DebugMode, defaults to DefaultDebugMode. - //! - //! In a sense, the path can be treated as a graph, for is has \c NodeIt - //! and \c EdgeIt with the same usage. These types converts to the \c Node - //! and \c Edge of the original graph. - //! - //! \todo Thoroughfully check all the range and consistency tests. - template - class UndirPath { - public: - /// Edge type of the underlying graph. - typedef typename Graph::Edge GraphEdge; - /// Node type of the underlying graph. - typedef typename Graph::Node GraphNode; - class NodeIt; - class EdgeIt; - - protected: - const Graph *gr; - typedef std::vector Container; - Container edges; - - public: - - /// \param _G The graph in which the path is. - /// - UndirPath(const Graph &_G) : gr(&_G) {} - - /// \brief Subpath constructor. - /// - /// Subpath defined by two nodes. - /// \warning It is an error if the two edges are not in order! - UndirPath(const UndirPath &P, const NodeIt &a, const NodeIt &b) { - gr = P.gr; - edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx); - } - - /// \brief Subpath constructor. - /// - /// Subpath defined by two edges. Contains edges in [a,b) - /// \warning It is an error if the two edges are not in order! - UndirPath(const UndirPath &P, const EdgeIt &a, const EdgeIt &b) { - gr = P.gr; - edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx); - } - - /// Length of the path. - size_t length() const { return edges.size(); } - /// Returns whether the path is empty. - bool empty() const { return edges.empty(); } - - /// Resets the path to an empty path. - void clear() { edges.clear(); } - - /// \brief Starting point of the path. - /// - /// Starting point of the path. - /// Returns INVALID if the path is empty. - GraphNode tail() const { - return empty() ? INVALID : gr->tail(edges[0]); - } - /// \brief End point of the path. - /// - /// End point of the path. - /// Returns INVALID if the path is empty. - GraphNode head() const { - return empty() ? INVALID : gr->head(edges[length()-1]); - } - - /// \brief Initializes node or edge iterator to point to the first - /// node or edge. - /// - /// \sa nth - template - It& first(It &i) const { return i=It(*this); } - - /// \brief Initializes node iterator to point to the node of a given index. - NodeIt& nth(NodeIt &i, int n) const { - return i=NodeIt(*this, n); - } - - /// \brief Initializes edge iterator to point to the edge of a given index. - EdgeIt& nth(EdgeIt &i, int n) const { - return i=EdgeIt(*this, n); - } - - /// Checks validity of a node or edge iterator. - template - static - bool valid(const It &i) { return i.valid(); } - - /// Steps the given node or edge iterator. - template - static - It& next(It &e) { - return ++e; - } - - /// \brief Returns node iterator pointing to the head node of the - /// given edge iterator. - NodeIt head(const EdgeIt& e) const { - return NodeIt(*this, e.idx+1); - } - - /// \brief Returns node iterator pointing to the tail node of the - /// given edge iterator. - NodeIt tail(const EdgeIt& e) const { - return NodeIt(*this, e.idx); - } - - - - /** - * \brief Iterator class to iterate on the edges of the paths - * - * \ingroup paths - * This class is used to iterate on the edges of the paths - * - * Of course it converts to Graph::Edge - * - * \todo Its interface differs from the standard edge iterator. - * Yes, it shouldn't. - */ - class EdgeIt { - friend class UndirPath; - - int idx; - const UndirPath *p; - public: - /// Default constructor - EdgeIt() {} - /// Invalid constructor - EdgeIt(Invalid) : idx(-1), p(0) {} - /// Constructor with starting point - EdgeIt(const UndirPath &_p, int _idx = 0) : - idx(_idx), p(&_p) { validate(); } - - ///Validity check - bool valid() const { return idx!=-1; } - - ///Conversion to Graph::Edge - operator GraphEdge () const { - return valid() ? p->edges[idx] : INVALID; - } - /// Next edge - EdgeIt& operator++() { ++idx; validate(); return *this; } - - /// Comparison operator - bool operator==(const EdgeIt& e) const { return idx==e.idx; } - /// Comparison operator - bool operator!=(const EdgeIt& e) const { return idx!=e.idx; } - /// Comparison operator - bool operator<(const EdgeIt& e) const { return idx= p->length() ) idx=-1; } - }; - - /** - * \brief Iterator class to iterate on the nodes of the paths - * - * \ingroup paths - * This class is used to iterate on the nodes of the paths - * - * Of course it converts to Graph::Node - * - * \todo Its interface differs from the standard node iterator. - * Yes, it shouldn't. - */ - class NodeIt { - friend class UndirPath; - - int idx; - const UndirPath *p; - public: - /// Default constructor - NodeIt() {} - /// Invalid constructor - NodeIt(Invalid) : idx(-1), p(0) {} - /// Constructor with starting point - NodeIt(const UndirPath &_p, int _idx = 0) : - idx(_idx), p(&_p) { validate(); } - - ///Validity check - bool valid() const { return idx!=-1; } - - ///Conversion to Graph::Node - operator const GraphNode& () const { - if(idx >= p->length()) - return p->head(); - else if(idx >= 0) - return p->gr->tail(p->edges[idx]); - else - return INVALID; - } - /// Next node - NodeIt& operator++() { ++idx; validate(); return *this; } - - /// Comparison operator - bool operator==(const NodeIt& e) const { return idx==e.idx; } - /// Comparison operator - bool operator!=(const NodeIt& e) const { return idx!=e.idx; } - /// Comparison operator - bool operator<(const NodeIt& e) const { return idx p->length() ) idx=-1; } - }; - - friend class Builder; - - /** - * \brief Class to build paths - * - * \ingroup paths - * This class is used to fill a path with edges. - * - * You can push new edges to the front and to the back of the path in - * arbitrary order then you should commit these changes to the graph. - * - * Fundamentally, for most "Paths" (classes fulfilling the - * PathConcept) while the builder is active (after the first modifying - * operation and until the commit()) the original Path is in a - * "transitional" state (operations ot it have undefined result). But - * in the case of UndirPath the original path is unchanged until the - * commit. However we don't recomend that you use this feature. - */ - class Builder { - UndirPath &P; - Container front, back; - - public: - ///\param _P the path you want to fill in. - /// - Builder(UndirPath &_P) : P(_P) {} - - /// Sets the starting node of the path. - - /// Sets the starting node of the path. Edge added to the path - /// afterwards have to be incident to this node. - /// It should be called if and only if - /// the path is empty and before any call to - /// \ref pushFront() or \ref pushBack() - void setStartNode(const GraphNode &) {} - - ///Push a new edge to the front of the path - - ///Push a new edge to the front of the path. - ///\sa setStartNode - void pushFront(const GraphEdge& e) { - front.push_back(e); - } - - ///Push a new edge to the back of the path - - ///Push a new edge to the back of the path. - ///\sa setStartNode - void pushBack(const GraphEdge& e) { - back.push_back(e); - } - - ///Commit the changes to the path. - void commit() { - if( !(front.empty() && back.empty()) ) { - Container tmp; - tmp.reserve(front.size()+back.size()+P.length()); - tmp.insert(tmp.end(), front.rbegin(), front.rend()); - tmp.insert(tmp.end(), P.edges.begin(), P.edges.end()); - tmp.insert(tmp.end(), back.begin(), back.end()); - P.edges.swap(tmp); - front.clear(); - back.clear(); - } - } - - - ///Reserve storage for the builder in advance. - - ///If you know a reasonable upper bound of the number of the edges - ///to add to the front, using this function you can speed up the building. - - void reserveFront(size_t r) {front.reserve(r);} - - ///Reserve storage for the builder in advance. - - ///If you know a reasonable upper bound of the number of the edges - ///to add to the back, using this function you can speed up the building. - - void reserveBack(size_t r) {back.reserve(r);} - - private: - bool empty() { - return front.empty() && back.empty() && P.empty(); - } - - GraphNode tail() const { - if( ! front.empty() ) - return P.gr->tail(front[front.size()-1]); - else if( ! P.empty() ) - return P.gr->tail(P.edges[0]); - else if( ! back.empty() ) - return P.gr->tail(back[0]); - else - return INVALID; - } - GraphNode head() const { - if( ! back.empty() ) - return P.gr->head(back[back.size()-1]); - else if( ! P.empty() ) - return P.gr->head(P.edges[P.length()-1]); - else if( ! front.empty() ) - return P.gr->head(front[0]); - else - return INVALID; - } - - }; - - }; - - - ///@} - -} // namespace hugo - -#endif // HUGO_PATH_H diff -r 2d6c8075d9d0 -r 818510fa3d99 src/hugo/preflow.h --- a/src/hugo/preflow.h Wed Sep 29 14:12:26 2004 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,819 +0,0 @@ -/* -*- C++ -*- - * src/hugo/preflow.h - Part of HUGOlib, a generic C++ optimization library - * - * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport - * (Egervary Combinatorial Optimization Research Group, 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 HUGO_PREFLOW_H -#define HUGO_PREFLOW_H - -#include -#include - -#include -#include - -/// \file -/// \ingroup flowalgs -/// Implementation of the preflow algorithm. - -namespace hugo { - - /// \addtogroup flowalgs - /// @{ - - ///%Preflow algorithms class. - - ///This class provides an implementation of the \e preflow \e - ///algorithm producing a flow of maximum value in a directed - ///graph. The preflow algorithms are the fastest max flow algorithms - ///up to now. The \e source node, the \e target node, the \e - ///capacity of the edges and the \e starting \e flow value of the - ///edges should be passed to the algorithm through the - ///constructor. It is possible to change these quantities using the - ///functions \ref setSource, \ref setTarget, \ref setCap and \ref - ///setFlow. - /// - ///After running \ref hugo::Preflow::phase1() "phase1()" - ///or \ref hugo::Preflow::run() "run()", the maximal flow - ///value can be obtained by calling \ref flowValue(). The minimum - ///value cut can be written into a bool node map by - ///calling \ref minCut(). (\ref minMinCut() and \ref maxMinCut() writes - ///the inclusionwise minimum and maximum of the minimum value cuts, - ///resp.) - /// - ///\param Graph The directed graph type the algorithm runs on. - ///\param Num The number type of the capacities and the flow values. - ///\param CapMap The capacity map type. - ///\param FlowMap The flow map type. - /// - ///\author Jacint Szabo - template , - typename FlowMap=typename Graph::template EdgeMap > - class Preflow { - protected: - typedef typename Graph::Node Node; - typedef typename Graph::NodeIt NodeIt; - typedef typename Graph::EdgeIt EdgeIt; - typedef typename Graph::OutEdgeIt OutEdgeIt; - typedef typename Graph::InEdgeIt InEdgeIt; - - typedef typename Graph::template NodeMap NNMap; - typedef typename std::vector VecNode; - - const Graph* g; - Node s; - Node t; - const CapMap* capacity; - FlowMap* flow; - int n; //the number of nodes of G - - typename Graph::template NodeMap level; - typename Graph::template NodeMap excess; - - // constants used for heuristics - static const int H0=20; - static const int H1=1; - - public: - - ///Indicates the property of the starting flow map. - - ///Indicates the property of the starting flow map. The meanings are as follows: - ///- \c ZERO_FLOW: constant zero flow - ///- \c GEN_FLOW: any flow, i.e. the sum of the in-flows equals to - ///the sum of the out-flows in every node except the \e source and - ///the \e target. - ///- \c PRE_FLOW: any preflow, i.e. the sum of the in-flows is at - ///least the sum of the out-flows in every node except the \e source. - ///- \c NO_FLOW: indicates an unspecified edge map. \c flow will be - ///set to the constant zero flow in the beginning of - ///the algorithm in this case. - /// - enum FlowEnum{ - NO_FLOW, - ZERO_FLOW, - GEN_FLOW, - PRE_FLOW - }; - - ///Indicates the state of the preflow algorithm. - - ///Indicates the state of the preflow algorithm. The meanings are as follows: - ///- \c AFTER_NOTHING: before running the algorithm or at an unspecified state. - ///- \c AFTER_PREFLOW_PHASE_1: right after running \c phase1 - ///- \c AFTER_PREFLOW_PHASE_2: after running \ref phase2() - /// - enum StatusEnum { - AFTER_NOTHING, - AFTER_PREFLOW_PHASE_1, - AFTER_PREFLOW_PHASE_2 - }; - - protected: - FlowEnum flow_prop; - StatusEnum status; // Do not needle this flag only if necessary. - - public: - ///The constructor of the class. - - ///The constructor of the class. - ///\param _G The directed graph the algorithm runs on. - ///\param _s The source node. - ///\param _t The target node. - ///\param _capacity The capacity of the edges. - ///\param _flow The flow of the edges. - ///Except the graph, all of these parameters can be reset by - ///calling \ref setSource, \ref setTarget, \ref setCap and \ref - ///setFlow, resp. - Preflow(const Graph& _G, Node _s, Node _t, - const CapMap& _capacity, FlowMap& _flow) : - g(&_G), s(_s), t(_t), capacity(&_capacity), - flow(&_flow), n(_G.nodeNum()), level(_G), excess(_G,0), - flow_prop(NO_FLOW), status(AFTER_NOTHING) { } - - - - ///Runs the preflow algorithm. - - ///Runs the preflow algorithm. - /// - void run() { - phase1(flow_prop); - phase2(); - } - - ///Runs the preflow algorithm. - - ///Runs the preflow algorithm. - ///\pre The starting flow map must be - /// - a constant zero flow if \c fp is \c ZERO_FLOW, - /// - an arbitrary flow if \c fp is \c GEN_FLOW, - /// - an arbitrary preflow if \c fp is \c PRE_FLOW, - /// - any map if \c fp is NO_FLOW. - ///If the starting flow map is a flow or a preflow then - ///the algorithm terminates faster. - void run(FlowEnum fp) { - flow_prop=fp; - run(); - } - - ///Runs the first phase of the preflow algorithm. - - ///The preflow algorithm consists of two phases, this method runs - ///the first phase. After the first phase the maximum flow value - ///and a minimum value cut can already be computed, though a - ///maximum flow is not yet obtained. So after calling this method - ///\ref flowValue returns the value of a maximum flow and \ref - ///minCut returns a minimum cut. - ///\warning \ref minMinCut and \ref maxMinCut do not give minimum - ///value cuts unless calling \ref phase2. - ///\pre The starting flow must be - ///- a constant zero flow if \c fp is \c ZERO_FLOW, - ///- an arbitary flow if \c fp is \c GEN_FLOW, - ///- an arbitary preflow if \c fp is \c PRE_FLOW, - ///- any map if \c fp is NO_FLOW. - void phase1(FlowEnum fp) - { - flow_prop=fp; - phase1(); - } - - - ///Runs the first phase of the preflow algorithm. - - ///The preflow algorithm consists of two phases, this method runs - ///the first phase. After the first phase the maximum flow value - ///and a minimum value cut can already be computed, though a - ///maximum flow is not yet obtained. So after calling this method - ///\ref flowValue returns the value of a maximum flow and \ref - ///minCut returns a minimum cut. - ///\warning \ref minCut(), \ref minMinCut() and \ref maxMinCut() do not - ///give minimum value cuts unless calling \ref phase2(). - void phase1() - { - int heur0=(int)(H0*n); //time while running 'bound decrease' - int heur1=(int)(H1*n); //time while running 'highest label' - int heur=heur1; //starting time interval (#of relabels) - int numrelabel=0; - - bool what_heur=1; - //It is 0 in case 'bound decrease' and 1 in case 'highest label' - - bool end=false; - //Needed for 'bound decrease', true means no active - //nodes are above bound b. - - int k=n-2; //bound on the highest level under n containing a node - int b=k; //bound on the highest level under n of an active node - - VecNode first(n, INVALID); - NNMap next(*g, INVALID); - - NNMap left(*g, INVALID); - NNMap right(*g, INVALID); - VecNode level_list(n,INVALID); - //List of the nodes in level i 0 ) { - b=k; - end=true; - } else break; - } - - if ( first[b]==INVALID ) --b; - else { - end=false; - Node w=first[b]; - first[b]=next[w]; - int newlevel=push(w, next, first); - if ( excess[w] > 0 ) relabel(w, newlevel, first, next, level_list, - left, right, b, k, what_heur); - - ++numrelabel; - if ( numrelabel >= heur ) { - numrelabel=0; - if ( what_heur ) { - what_heur=0; - heur=heur0; - end=false; - } else { - what_heur=1; - heur=heur1; - b=k; - } - } - } - } - flow_prop=PRE_FLOW; - status=AFTER_PREFLOW_PHASE_1; - } - // Heuristics: - // 2 phase - // gap - // list 'level_list' on the nodes on level i implemented by hand - // stack 'active' on the active nodes on level i - // runs heuristic 'highest label' for H1*n relabels - // runs heuristic 'bound decrease' for H0*n relabels, starts with 'highest label' - // Parameters H0 and H1 are initialized to 20 and 1. - - - ///Runs the second phase of the preflow algorithm. - - ///The preflow algorithm consists of two phases, this method runs - ///the second phase. After calling \ref phase1 and then \ref - ///phase2, \ref flow contains a maximum flow, \ref flowValue - ///returns the value of a maximum flow, \ref minCut returns a - ///minimum cut, while the methods \ref minMinCut and \ref - ///maxMinCut return the inclusionwise minimum and maximum cuts of - ///minimum value, resp. \pre \ref phase1 must be called before. - void phase2() - { - - int k=n-2; //bound on the highest level under n containing a node - int b=k; //bound on the highest level under n of an active node - - - VecNode first(n, INVALID); - NNMap next(*g, INVALID); - level.set(s,0); - std::queue bfs_queue; - bfs_queue.push(s); - - while ( !bfs_queue.empty() ) { - - Node v=bfs_queue.front(); - bfs_queue.pop(); - int l=level[v]+1; - - for(InEdgeIt e(*g,v); e!=INVALID; ++e) { - if ( (*capacity)[e] <= (*flow)[e] ) continue; - Node u=g->tail(e); - if ( level[u] >= n ) { - bfs_queue.push(u); - level.set(u, l); - if ( excess[u] > 0 ) { - next.set(u,first[l]); - first[l]=u; - } - } - } - - for(OutEdgeIt e(*g,v); e!=INVALID; ++e) { - if ( 0 >= (*flow)[e] ) continue; - Node u=g->head(e); - if ( level[u] >= n ) { - bfs_queue.push(u); - level.set(u, l); - if ( excess[u] > 0 ) { - next.set(u,first[l]); - first[l]=u; - } - } - } - } - b=n-2; - - while ( true ) { - - if ( b == 0 ) break; - if ( first[b]==INVALID ) --b; - else { - Node w=first[b]; - first[b]=next[w]; - int newlevel=push(w,next, first); - - //relabel - if ( excess[w] > 0 ) { - level.set(w,++newlevel); - next.set(w,first[newlevel]); - first[newlevel]=w; - b=newlevel; - } - } - } // while(true) - flow_prop=GEN_FLOW; - status=AFTER_PREFLOW_PHASE_2; - } - - /// Returns the value of the maximum flow. - - /// Returns the value of the maximum flow by returning the excess - /// of the target node \c t. This value equals to the value of - /// the maximum flow already after running \ref phase1. - Num flowValue() const { - return excess[t]; - } - - - ///Returns a minimum value cut. - - ///Sets \c M to the characteristic vector of a minimum value - ///cut. This method can be called both after running \ref - ///phase1 and \ref phase2. It is much faster after - ///\ref phase1. \pre M should be a bool-valued node-map. \pre - ///If \ref minCut() is called after \ref phase2() then M should - ///be initialized to false. - template - void minCut(_CutMap& M) const { - switch ( status ) { - case AFTER_PREFLOW_PHASE_1: - for(NodeIt v(*g); v!=INVALID; ++v) { - if (level[v] < n) { - M.set(v, false); - } else { - M.set(v, true); - } - } - break; - case AFTER_PREFLOW_PHASE_2: - minMinCut(M); - break; - case AFTER_NOTHING: - break; - } - } - - ///Returns the inclusionwise minimum of the minimum value cuts. - - ///Sets \c M to the characteristic vector of the minimum value cut - ///which is inclusionwise minimum. It is computed by processing a - ///bfs from the source node \c s in the residual graph. \pre M - ///should be a node map of bools initialized to false. \pre \ref - ///phase2 should already be run. - template - void minMinCut(_CutMap& M) const { - - std::queue queue; - M.set(s,true); - queue.push(s); - - while (!queue.empty()) { - Node w=queue.front(); - queue.pop(); - - for(OutEdgeIt e(*g,w) ; e!=INVALID; ++e) { - Node v=g->head(e); - if (!M[v] && (*flow)[e] < (*capacity)[e] ) { - queue.push(v); - M.set(v, true); - } - } - - for(InEdgeIt e(*g,w) ; e!=INVALID; ++e) { - Node v=g->tail(e); - if (!M[v] && (*flow)[e] > 0 ) { - queue.push(v); - M.set(v, true); - } - } - } - } - - ///Returns the inclusionwise maximum of the minimum value cuts. - - ///Sets \c M to the characteristic vector of the minimum value cut - ///which is inclusionwise maximum. It is computed by processing a - ///backward bfs from the target node \c t in the residual graph. - ///\pre \ref phase2() or run() should already be run. - template - void maxMinCut(_CutMap& M) const { - - for(NodeIt v(*g) ; v!=INVALID; ++v) M.set(v, true); - - std::queue queue; - - M.set(t,false); - queue.push(t); - - while (!queue.empty()) { - Node w=queue.front(); - queue.pop(); - - for(InEdgeIt e(*g,w) ; e!=INVALID; ++e) { - Node v=g->tail(e); - if (M[v] && (*flow)[e] < (*capacity)[e] ) { - queue.push(v); - M.set(v, false); - } - } - - for(OutEdgeIt e(*g,w) ; e!=INVALID; ++e) { - Node v=g->head(e); - if (M[v] && (*flow)[e] > 0 ) { - queue.push(v); - M.set(v, false); - } - } - } - } - - ///Sets the source node to \c _s. - - ///Sets the source node to \c _s. - /// - void setSource(Node _s) { - s=_s; - if ( flow_prop != ZERO_FLOW ) flow_prop=NO_FLOW; - status=AFTER_NOTHING; - } - - ///Sets the target node to \c _t. - - ///Sets the target node to \c _t. - /// - void setTarget(Node _t) { - t=_t; - if ( flow_prop == GEN_FLOW ) flow_prop=PRE_FLOW; - status=AFTER_NOTHING; - } - - /// Sets the edge map of the capacities to _cap. - - /// Sets the edge map of the capacities to _cap. - /// - void setCap(const CapMap& _cap) { - capacity=&_cap; - status=AFTER_NOTHING; - } - - /// Sets the edge map of the flows to _flow. - - /// Sets the edge map of the flows to _flow. - /// - void setFlow(FlowMap& _flow) { - flow=&_flow; - flow_prop=NO_FLOW; - status=AFTER_NOTHING; - } - - - private: - - int push(Node w, NNMap& next, VecNode& first) { - - int lev=level[w]; - Num exc=excess[w]; - int newlevel=n; //bound on the next level of w - - for(OutEdgeIt e(*g,w) ; e!=INVALID; ++e) { - if ( (*flow)[e] >= (*capacity)[e] ) continue; - Node v=g->head(e); - - if( lev > level[v] ) { //Push is allowed now - - if ( excess[v]<=0 && v!=t && v!=s ) { - next.set(v,first[level[v]]); - first[level[v]]=v; - } - - Num cap=(*capacity)[e]; - Num flo=(*flow)[e]; - Num remcap=cap-flo; - - if ( remcap >= exc ) { //A nonsaturating push. - - flow->set(e, flo+exc); - excess.set(v, excess[v]+exc); - exc=0; - break; - - } else { //A saturating push. - flow->set(e, cap); - excess.set(v, excess[v]+remcap); - exc-=remcap; - } - } else if ( newlevel > level[v] ) newlevel = level[v]; - } //for out edges wv - - if ( exc > 0 ) { - for(InEdgeIt e(*g,w) ; e!=INVALID; ++e) { - - if( (*flow)[e] <= 0 ) continue; - Node v=g->tail(e); - - if( lev > level[v] ) { //Push is allowed now - - if ( excess[v]<=0 && v!=t && v!=s ) { - next.set(v,first[level[v]]); - first[level[v]]=v; - } - - Num flo=(*flow)[e]; - - if ( flo >= exc ) { //A nonsaturating push. - - flow->set(e, flo-exc); - excess.set(v, excess[v]+exc); - exc=0; - break; - } else { //A saturating push. - - excess.set(v, excess[v]+flo); - exc-=flo; - flow->set(e,0); - } - } else if ( newlevel > level[v] ) newlevel = level[v]; - } //for in edges vw - - } // if w still has excess after the out edge for cycle - - excess.set(w, exc); - - return newlevel; - } - - - - void preflowPreproc(VecNode& first, NNMap& next, - VecNode& level_list, NNMap& left, NNMap& right) - { - for(NodeIt v(*g); v!=INVALID; ++v) level.set(v,n); - std::queue bfs_queue; - - if ( flow_prop == GEN_FLOW || flow_prop == PRE_FLOW ) { - //Reverse_bfs from t in the residual graph, - //to find the starting level. - level.set(t,0); - bfs_queue.push(t); - - while ( !bfs_queue.empty() ) { - - Node v=bfs_queue.front(); - bfs_queue.pop(); - int l=level[v]+1; - - for(InEdgeIt e(*g,v) ; e!=INVALID; ++e) { - if ( (*capacity)[e] <= (*flow)[e] ) continue; - Node w=g->tail(e); - if ( level[w] == n && w != s ) { - bfs_queue.push(w); - Node z=level_list[l]; - if ( z!=INVALID ) left.set(z,w); - right.set(w,z); - level_list[l]=w; - level.set(w, l); - } - } - - for(OutEdgeIt e(*g,v) ; e!=INVALID; ++e) { - if ( 0 >= (*flow)[e] ) continue; - Node w=g->head(e); - if ( level[w] == n && w != s ) { - bfs_queue.push(w); - Node z=level_list[l]; - if ( z!=INVALID ) left.set(z,w); - right.set(w,z); - level_list[l]=w; - level.set(w, l); - } - } - } //while - } //if - - - switch (flow_prop) { - case NO_FLOW: - for(EdgeIt e(*g); e!=INVALID; ++e) flow->set(e,0); - case ZERO_FLOW: - for(NodeIt v(*g); v!=INVALID; ++v) excess.set(v,0); - - //Reverse_bfs from t, to find the starting level. - level.set(t,0); - bfs_queue.push(t); - - while ( !bfs_queue.empty() ) { - - Node v=bfs_queue.front(); - bfs_queue.pop(); - int l=level[v]+1; - - for(InEdgeIt e(*g,v) ; e!=INVALID; ++e) { - Node w=g->tail(e); - if ( level[w] == n && w != s ) { - bfs_queue.push(w); - Node z=level_list[l]; - if ( z!=INVALID ) left.set(z,w); - right.set(w,z); - level_list[l]=w; - level.set(w, l); - } - } - } - - //the starting flow - for(OutEdgeIt e(*g,s) ; e!=INVALID; ++e) { - Num c=(*capacity)[e]; - if ( c <= 0 ) continue; - Node w=g->head(e); - if ( level[w] < n ) { - if ( excess[w] <= 0 && w!=t ) { //putting into the stack - next.set(w,first[level[w]]); - first[level[w]]=w; - } - flow->set(e, c); - excess.set(w, excess[w]+c); - } - } - break; - - case GEN_FLOW: - for(NodeIt v(*g); v!=INVALID; ++v) excess.set(v,0); - { - Num exc=0; - for(InEdgeIt e(*g,t) ; e!=INVALID; ++e) exc+=(*flow)[e]; - for(OutEdgeIt e(*g,t) ; e!=INVALID; ++e) exc-=(*flow)[e]; - excess.set(t,exc); - } - - //the starting flow - for(OutEdgeIt e(*g,s); e!=INVALID; ++e) { - Num rem=(*capacity)[e]-(*flow)[e]; - if ( rem <= 0 ) continue; - Node w=g->head(e); - if ( level[w] < n ) { - if ( excess[w] <= 0 && w!=t ) { //putting into the stack - next.set(w,first[level[w]]); - first[level[w]]=w; - } - flow->set(e, (*capacity)[e]); - excess.set(w, excess[w]+rem); - } - } - - for(InEdgeIt e(*g,s); e!=INVALID; ++e) { - if ( (*flow)[e] <= 0 ) continue; - Node w=g->tail(e); - if ( level[w] < n ) { - if ( excess[w] <= 0 && w!=t ) { - next.set(w,first[level[w]]); - first[level[w]]=w; - } - excess.set(w, excess[w]+(*flow)[e]); - flow->set(e, 0); - } - } - break; - - case PRE_FLOW: - //the starting flow - for(OutEdgeIt e(*g,s) ; e!=INVALID; ++e) { - Num rem=(*capacity)[e]-(*flow)[e]; - if ( rem <= 0 ) continue; - Node w=g->head(e); - if ( level[w] < n ) flow->set(e, (*capacity)[e]); - } - - for(InEdgeIt e(*g,s) ; e!=INVALID; ++e) { - if ( (*flow)[e] <= 0 ) continue; - Node w=g->tail(e); - if ( level[w] < n ) flow->set(e, 0); - } - - //computing the excess - for(NodeIt w(*g); w!=INVALID; ++w) { - Num exc=0; - for(InEdgeIt e(*g,w); e!=INVALID; ++e) exc+=(*flow)[e]; - for(OutEdgeIt e(*g,w); e!=INVALID; ++e) exc-=(*flow)[e]; - excess.set(w,exc); - - //putting the active nodes into the stack - int lev=level[w]; - if ( exc > 0 && lev < n && Node(w) != t ) { - next.set(w,first[lev]); - first[lev]=w; - } - } - break; - } //switch - } //preflowPreproc - - - void relabel(Node w, int newlevel, VecNode& first, NNMap& next, - VecNode& level_list, NNMap& left, - NNMap& right, int& b, int& k, bool what_heur ) - { - - int lev=level[w]; - - Node right_n=right[w]; - Node left_n=left[w]; - - //unlacing starts - if ( right_n!=INVALID ) { - if ( left_n!=INVALID ) { - right.set(left_n, right_n); - left.set(right_n, left_n); - } else { - level_list[lev]=right_n; - left.set(right_n, INVALID); - } - } else { - if ( left_n!=INVALID ) { - right.set(left_n, INVALID); - } else { - level_list[lev]=INVALID; - } - } - //unlacing ends - - if ( level_list[lev]==INVALID ) { - - //gapping starts - for (int i=lev; i!=k ; ) { - Node v=level_list[++i]; - while ( v!=INVALID ) { - level.set(v,n); - v=right[v]; - } - level_list[i]=INVALID; - if ( !what_heur ) first[i]=INVALID; - } - - level.set(w,n); - b=lev-1; - k=b; - //gapping ends - - } else { - - if ( newlevel == n ) level.set(w,n); - else { - level.set(w,++newlevel); - next.set(w,first[newlevel]); - first[newlevel]=w; - if ( what_heur ) b=newlevel; - if ( k < newlevel ) ++k; //now k=newlevel - Node z=level_list[newlevel]; - if ( z!=INVALID ) left.set(z,w); - right.set(w,z); - left.set(w,INVALID); - level_list[newlevel]=w; - } - } - } //relabel - - }; -} //namespace hugo - -#endif //HUGO_PREFLOW_H - - - - diff -r 2d6c8075d9d0 -r 818510fa3d99 src/hugo/skeletons/graph.h --- a/src/hugo/skeletons/graph.h Wed Sep 29 14:12:26 2004 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,510 +0,0 @@ -/* -*- C++ -*- - * src/hugo/skeletons/graph.h - Part of HUGOlib, a generic C++ optimization library - * - * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport - * (Egervary Combinatorial Optimization Research Group, 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 HUGO_SKELETON_GRAPH_H -#define HUGO_SKELETON_GRAPH_H - -///\ingroup skeletons -///\file -///\brief Declaration of Graph. - -#include -#include - -namespace hugo { - namespace skeleton { - - /// \addtogroup skeletons - /// @{ - - /// An empty static graph class. - - /// This class provides all the common features of a graph structure, - /// however completely without implementations and real data structures - /// behind the interface. - /// All graph algorithms should compile with this class, but it will not - /// run properly, of course. - /// - /// It can be used for checking the interface compatibility, - /// or it can serve as a skeleton of a new graph structure. - /// - /// Also, you will find here the full documentation of a certain graph - /// feature, the documentation of a real graph imlementation - /// like @ref ListGraph or - /// @ref SmartGraph will just refer to this structure. - class StaticGraph - { - public: - /// Defalult constructor. - - /// Defalult constructor. - /// - StaticGraph() { } - ///Copy consructor. - -// ///\todo It is not clear, what we expect from a copy constructor. -// ///E.g. How to assign the nodes/edges to each other? What about maps? -// StaticGraph(const StaticGraph& g) { } - - /// The base type of node iterators, - /// or in other words, the trivial node iterator. - - /// This is the base type of each node iterator, - /// thus each kind of node iterator converts to this. - /// More precisely each kind of node iterator should be inherited - /// from the trivial node iterator. - class Node { - public: - /// Default constructor - - /// @warning The default constructor sets the iterator - /// to an undefined value. - Node() { } - /// Copy constructor. - - /// Copy constructor. - /// - Node(const Node&) { } - - /// Invalid constructor \& conversion. - - /// This constructor initializes the iterator to be invalid. - /// \sa Invalid for more details. - Node(Invalid) { } - /// Equality operator - - /// Two iterators are equal if and only if they point to the - /// same object or both are invalid. - bool operator==(Node) const { return true; } - - /// Inequality operator - - /// \sa operator==(Node n) - /// - bool operator!=(Node) const { return true; } - - ///Comparison operator. - - ///This is a strict ordering between the nodes. - /// - ///This ordering can be different from the order in which NodeIt - ///goes through the nodes. - ///\todo Possibly we don't need it. - bool operator<(Node) const { return true; } - }; - - /// This iterator goes through each node. - - /// This iterator goes through each node. - /// Its usage is quite simple, for example you can count the number - /// of nodes in graph \c g of type \c Graph like this: - /// \code - /// int count=0; - /// for (Graph::NodeIt n(g); n!=INVALID; ++n) ++count; - /// \endcode - class NodeIt : public Node { - public: - /// Default constructor - - /// @warning The default constructor sets the iterator - /// to an undefined value. - NodeIt() { } - /// Copy constructor. - - /// Copy constructor. - /// - NodeIt(const NodeIt&) { } - /// Invalid constructor \& conversion. - - /// Initialize the iterator to be invalid. - /// \sa Invalid for more details. - NodeIt(Invalid) { } - /// Sets the iterator to the first node. - - /// Sets the iterator to the first node of \c g. - /// - NodeIt(const StaticGraph& g) { } - /// Node -> NodeIt conversion. - - /// Sets the iterator to the node of \c g pointed by the trivial - /// iterator n. - /// This feature necessitates that each time we - /// iterate the edge-set, the iteration order is the same. - NodeIt(const StaticGraph& g, const Node& n) { } - /// Next node. - - /// Assign the iterator to the next node. - /// - NodeIt& operator++() { return *this; } - }; - - - /// The base type of the edge iterators. - - /// The base type of the edge iterators. - /// - class Edge { - public: - /// Default constructor - - /// @warning The default constructor sets the iterator - /// to an undefined value. - Edge() { } - /// Copy constructor. - - /// Copy constructor. - /// - Edge(const Edge&) { } - /// Initialize the iterator to be invalid. - - /// Initialize the iterator to be invalid. - /// - Edge(Invalid) { } - /// Equality operator - - /// Two iterators are equal if and only if they point to the - /// same object or both are invalid. - bool operator==(Edge) const { return true; } - /// Inequality operator - - /// \sa operator==(Node n) - /// - bool operator!=(Edge) const { return true; } - ///Comparison operator. - - ///This is a strict ordering between the nodes. - /// - ///This ordering can be different from the order in which NodeIt - ///goes through the nodes. - ///\todo Possibly we don't need it. - bool operator<(Edge) const { return true; } - }; - - /// This iterator goes trough the outgoing edges of a node. - - /// This iterator goes trough the \e outgoing edges of a certain node - /// of a graph. - /// Its usage is quite simple, for example you can count the number - /// of outgoing edges of a node \c n - /// in graph \c g of type \c Graph as follows. - /// \code - /// int count=0; - /// for (Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) ++count; - /// \endcode - - class OutEdgeIt : public Edge { - public: - /// Default constructor - - /// @warning The default constructor sets the iterator - /// to an undefined value. - OutEdgeIt() { } - /// Copy constructor. - - /// Copy constructor. - /// - OutEdgeIt(const OutEdgeIt&) { } - /// Initialize the iterator to be invalid. - - /// Initialize the iterator to be invalid. - /// - OutEdgeIt(Invalid) { } - /// This constructor sets the iterator to first outgoing edge. - - /// This constructor set the iterator to the first outgoing edge of - /// node - ///@param n the node - ///@param g the graph - OutEdgeIt(const StaticGraph& g, const Node& n) { } - /// Edge -> OutEdgeIt conversion - - /// Sets the iterator to the value of the trivial iterator \c e. - /// This feature necessitates that each time we - /// iterate the edge-set, the iteration order is the same. - OutEdgeIt(const StaticGraph& g, const Edge& e) { } - ///Next outgoing edge - - /// Assign the iterator to the next - /// outgoing edge of the corresponding node. - OutEdgeIt& operator++() { return *this; } - }; - - /// This iterator goes trough the incoming edges of a node. - - /// This iterator goes trough the \e incoming edges of a certain node - /// of a graph. - /// Its usage is quite simple, for example you can count the number - /// of outgoing edges of a node \c n - /// in graph \c g of type \c Graph as follows. - /// \code - /// int count=0; - /// for(Graph::InEdgeIt e(g, n); e!=INVALID; ++e) ++count; - /// \endcode - - class InEdgeIt : public Edge { - public: - /// Default constructor - - /// @warning The default constructor sets the iterator - /// to an undefined value. - InEdgeIt() { } - /// Copy constructor. - - /// Copy constructor. - /// - InEdgeIt(const InEdgeIt&) { } - /// Initialize the iterator to be invalid. - - /// Initialize the iterator to be invalid. - /// - InEdgeIt(Invalid) { } - /// This constructor sets the iterator to first incoming edge. - - /// This constructor set the iterator to the first incoming edge of - /// node - ///@param n the node - ///@param g the graph - InEdgeIt(const StaticGraph& g, const Node& n) { } - /// Edge -> InEdgeIt conversion - - /// Sets the iterator to the value of the trivial iterator \c e. - /// This feature necessitates that each time we - /// iterate the edge-set, the iteration order is the same. - InEdgeIt(const StaticGraph& g, const Edge& n) { } - /// Next incoming edge - - /// Assign the iterator to the next inedge of the corresponding node. - /// - InEdgeIt& operator++() { return *this; } - }; - /// This iterator goes through each edge. - - /// This iterator goes through each edge of a graph. - /// Its usage is quite simple, for example you can count the number - /// of edges in a graph \c g of type \c Graph as follows: - /// \code - /// int count=0; - /// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count; - /// \endcode - class EdgeIt : public Edge { - public: - /// Default constructor - - /// @warning The default constructor sets the iterator - /// to an undefined value. - EdgeIt() { } - /// Copy constructor. - - /// Copy constructor. - /// - EdgeIt(const EdgeIt&) { } - /// Initialize the iterator to be invalid. - - /// Initialize the iterator to be invalid. - /// - EdgeIt(Invalid) { } - /// This constructor sets the iterator to first edge. - - /// This constructor set the iterator to the first edge of - /// node - ///@param g the graph - EdgeIt(const StaticGraph& g) { } - /// Edge -> EdgeIt conversion - - /// Sets the iterator to the value of the trivial iterator \c e. - /// This feature necessitates that each time we - /// iterate the edge-set, the iteration order is the same. - EdgeIt(const StaticGraph&, const Edge&) { } - ///Next edge - - /// Assign the iterator to the next - /// edge of the corresponding node. - EdgeIt& operator++() { return *this; } - }; - - /// First node of the graph. - - /// \retval i the first node. - /// \return the first node. - /// - NodeIt& first(NodeIt& i) const { return i; } - - /// The first incoming edge. - - /// The first incoming edge. - /// - InEdgeIt& first(InEdgeIt &i, Node) const { return i; } - /// The first outgoing edge. - - /// The first outgoing edge. - /// - OutEdgeIt& first(OutEdgeIt& i, Node) const { return i; } - /// The first edge of the Graph. - - /// The first edge of the Graph. - /// - EdgeIt& first(EdgeIt& i) const { return i; } - - ///Gives back the head node of an edge. - - ///Gives back the head node of an edge. - /// - Node head(Edge) const { return INVALID; } - ///Gives back the tail node of an edge. - - ///Gives back the tail node of an edge. - /// - Node tail(Edge) const { return INVALID; } - - ///Gives back the \e id of a node. - - ///\warning Not all graph structures provide this feature. - /// - ///\todo Should each graph provide \c id? - int id(const Node&) const { return 0; } - ///Gives back the \e id of an edge. - - ///\warning Not all graph structures provide this feature. - /// - ///\todo Should each graph provide \c id? - int id(const Edge&) const { return 0; } - - ///\e - - ///\todo Should it be in the concept? - /// - int nodeNum() const { return 0; } - ///\e - - ///\todo Should it be in the concept? - /// - int edgeNum() const { return 0; } - - - ///Reference map of the nodes to type \c T. - - /// \ingroup skeletons - ///Reference map of the nodes to type \c T. - /// \sa Reference - /// \warning Making maps that can handle bool type (NodeMap) - /// needs some extra attention! - template class NodeMap : public ReferenceMap< Node, T > - { - public: - - ///\e - NodeMap(const StaticGraph&) { } - ///\e - NodeMap(const StaticGraph&, T) { } - - ///Copy constructor - template NodeMap(const NodeMap&) { } - ///Assignment operator - template NodeMap& operator=(const NodeMap&) - { return *this; } - }; - - ///Reference map of the edges to type \c T. - - /// \ingroup skeletons - ///Reference map of the edges to type \c T. - /// \sa Reference - /// \warning Making maps that can handle bool type (EdgeMap) - /// needs some extra attention! - template class EdgeMap - : public ReferenceMap - { - public: - - ///\e - EdgeMap(const StaticGraph&) { } - ///\e - EdgeMap(const StaticGraph&, T) { } - - ///Copy constructor - template EdgeMap(const EdgeMap&) { } - ///Assignment operator - template EdgeMap &operator=(const EdgeMap&) - { return *this; } - }; - }; - - - - /// An empty non-static graph class. - - /// This class provides everything that \ref StaticGraph - /// with additional functionality which enables to build a - /// graph from scratch. - class ExtendableGraph : public StaticGraph - { - public: - /// Defalult constructor. - - /// Defalult constructor. - /// - ExtendableGraph() { } - ///Add a new node to the graph. - - /// \return the new node. - /// - Node addNode() { return INVALID; } - ///Add a new edge to the graph. - - ///Add a new edge to the graph with tail node \c t - ///and head node \c h. - ///\return the new edge. - Edge addEdge(Node h, Node t) { return INVALID; } - - /// Resets the graph. - - /// This function deletes all edges and nodes of the graph. - /// It also frees the memory allocated to store them. - /// \todo It might belong to \ref ErasableGraph. - void clear() { } - }; - - /// An empty erasable graph class. - - /// This class is an extension of \ref ExtendableGraph. It also makes it - /// possible to erase edges or nodes. - class ErasableGraph : public ExtendableGraph - { - public: - /// Defalult constructor. - - /// Defalult constructor. - /// - ErasableGraph() { } - /// Deletes a node. - - /// Deletes node \c n node. - /// - void erase(Node n) { } - /// Deletes an edge. - - /// Deletes edge \c e edge. - /// - void erase(Edge e) { } - }; - - // @} - } //namespace skeleton -} //namespace hugo - - - -#endif // HUGO_SKELETON_GRAPH_H diff -r 2d6c8075d9d0 -r 818510fa3d99 src/hugo/skeletons/maps.h --- a/src/hugo/skeletons/maps.h Wed Sep 29 14:12:26 2004 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,120 +0,0 @@ -/* -*- C++ -*- - * src/hugo/skeletons/maps.h - Part of HUGOlib, a generic C++ optimization library - * - * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport - * (Egervary Combinatorial Optimization Research Group, 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 HUGO_MAPSKELETON_H -#define HUGO_MAPSKELETON_H - -///\ingroup skeletons -///\file -///\brief Map concepts checking classes for testing and documenting. - -namespace hugo { - - namespace skeleton { - - /// \addtogroup skeletons - /// @{ - - /// Readable map concept - template - class ReadMap - { - public: - /// Map's key type. - typedef K KeyType; - /// Map's value type. (The type of objects associated with the keys). - typedef T ValueType; - - /// Returns the value associated with a key. - ValueType operator[](const KeyType &k) const {return ValueType();} - - ///Default constructor - ReadMap() {} - }; - - - /// Writable map concept - template - class WriteMap - { - public: - /// Map's key type. - typedef K KeyType; - /// Map's value type. (The type of objects associated with the keys). - typedef T ValueType; - - /// Sets the value associated with a key. - void set(const KeyType &k,const ValueType &t) {} - - ///Default constructor - WriteMap() {} - }; - - ///Read/Writable map concept - template - class ReadWriteMap : public ReadMap, - public WriteMap - { - public: - /// Map's key type. - typedef K KeyType; - /// Map's value type. (The type of objects associated with the keys). - typedef T ValueType; - - /// Returns the value associated with a key. - ValueType operator[](const KeyType &k) const {return ValueType();} - /// Sets the value associated with a key. - void set(const KeyType &k,const ValueType &t) {} - - ///Default constructor - ReadWriteMap() {} - }; - - - ///Dereferable map concept - template - class ReferenceMap : public ReadWriteMap - { - public: - /// Map's key type. - typedef K KeyType; - /// Map's value type. (The type of objects associated with the keys). - typedef T ValueType; - - protected: - ValueType tmp; - public: - typedef ValueType& ReferenceType; - /// Map's const reference type. - typedef const ValueType& ConstReferenceType; - - ///Returns a reference to the value associated to a key. - ReferenceType operator[](const KeyType &i) { return tmp; } - ///Returns a const reference to the value associated to a key. - ConstReferenceType operator[](const KeyType &i) const - { return tmp; } - /// Sets the value associated with a key. - void set(const KeyType &k,const ValueType &t) { operator[](k)=t; } - - ///Default constructor - ReferenceMap() {} - }; - - // @} - - } //namespace skeleton -} //namespace hugo -#endif // HUGO_MAPSKELETON_H diff -r 2d6c8075d9d0 -r 818510fa3d99 src/hugo/skeletons/path.h --- a/src/hugo/skeletons/path.h Wed Sep 29 14:12:26 2004 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,236 +0,0 @@ -/* -*- C++ -*- - * src/hugo/skeletons/path.h - Part of HUGOlib, a generic C++ optimization library - * - * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport - * (Egervary Combinatorial Optimization Research Group, 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. - * - */ - -///\ingroup skeletons -///\file -///\brief Classes for representing paths in graphs. - -#ifndef HUGO_SKELETON_PATH_H -#define HUGO_SKELETON_PATH_H - -#include - -namespace hugo { - namespace skeleton { - /// \addtogroup skeletons - /// @{ - - - //! \brief A skeletom structure for representing directed paths in a graph. - //! - //! A skeleton structure for representing directed paths in a graph. - //! \param GR The graph type in which the path is. - //! - //! In a sense, the path can be treated as a graph, for is has \c NodeIt - //! and \c EdgeIt with the same usage. These types converts to the \c Node - //! and \c Edge of the original graph. - template - class Path { - public: - - /// Type of the underlying graph. - typedef /*typename*/ GR Graph; - /// Edge type of the underlying graph. - typedef typename Graph::Edge GraphEdge; - /// Node type of the underlying graph. - typedef typename Graph::Node GraphNode; - class NodeIt; - class EdgeIt; - - /// \param _G The graph in which the path is. - /// - Path(const Graph &_G) {} - - /// Length of the path. - size_t length() const {return 0;} - /// Returns whether the path is empty. - bool empty() const { return true;} - - /// Resets the path to an empty path. - void clear() {} - - /// \brief Starting point of the path. - /// - /// Starting point of the path. - /// Returns INVALID if the path is empty. - GraphNode/*It*/ head() const {return INVALID;} - /// \brief End point of the path. - /// - /// End point of the path. - /// Returns INVALID if the path is empty. - GraphNode/*It*/ tail() const {return INVALID;} - - /// \brief First NodeIt/EdgeIt. - /// - /// Initializes node or edge iterator to point to the first - /// node or edge. - template - It& first(It &i) const { return i=It(*this); } - - /// \brief The head of an edge. - /// - /// Returns node iterator pointing to the head node of the - /// given edge iterator. - NodeIt head(const EdgeIt& e) const {return INVALID;} - - /// \brief The tail of an edge. - /// - /// Returns node iterator pointing to the tail node of the - /// given edge iterator. - NodeIt tail(const EdgeIt& e) const {return INVALID;} - - - /* Iterator classes */ - - /** - * \brief Iterator class to iterate on the edges of the paths - * - * \ingroup skeletons - * This class is used to iterate on the edges of the paths - * - * Of course it converts to Graph::Edge - * - */ - class EdgeIt { - public: - /// Default constructor - EdgeIt() {} - /// Invalid constructor - EdgeIt(Invalid) {} - /// Constructor with starting point - EdgeIt(const Path &_p) {} - - operator GraphEdge () const {} - - /// Next edge - EdgeIt& operator++() {return *this;} - - /// Comparison operator - bool operator==(const EdgeIt& e) const {return true;} - /// Comparison operator - bool operator!=(const EdgeIt& e) const {return true;} -// /// Comparison operator -// /// \todo It is not clear what is the "natural" ordering. -// bool operator<(const EdgeIt& e) const {} - - }; - - /** - * \brief Iterator class to iterate on the nodes of the paths - * - * \ingroup skeletons - * This class is used to iterate on the nodes of the paths - * - * Of course it converts to Graph::Node. - * - */ - class NodeIt { - public: - /// Default constructor - NodeIt() {} - /// Invalid constructor - NodeIt(Invalid) {} - /// Constructor with starting point - NodeIt(const Path &_p) {} - - ///Conversion to Graph::Node - operator const GraphNode& () const {} - /// Next node - NodeIt& operator++() {return *this;} - - /// Comparison operator - bool operator==(const NodeIt& e) const {return true;} - /// Comparison operator - bool operator!=(const NodeIt& e) const {return true;} -// /// Comparison operator -// /// \todo It is not clear what is the "natural" ordering. -// bool operator<(const NodeIt& e) const {} - - }; - - friend class Builder; - - /** - * \brief Class to build paths - * - * \ingroup skeletons - * This class is used to fill a path with edges. - * - * You can push new edges to the front and to the back of the path in - * arbitrary order then you should commit these changes to the graph. - * - * While the builder is active (after the first modifying - * operation and until the call of \ref commit()) - * the underlining Path is in a - * "transitional" state (operations on it have undefined result). - */ - class Builder { - public: - - Path &P; - - ///\param _P the path you want to fill in. - /// - Builder(Path &_P) : P(_P) {} - - /// Sets the starting node of the path. - - /// Sets the starting node of the path. Edge added to the path - /// afterwards have to be incident to this node. - /// You \em must start building an empry path with this functions. - /// (And you \em must \em not use it later). - /// \sa pushFront() - /// \sa pushBack() - void setStartNode(const GraphNode &) {} - - ///Push a new edge to the front of the path - - ///Push a new edge to the front of the path. - ///If the path is empty, you \em must call \ref setStartNode() before - ///the first use of \ref pushFront(). - void pushFront(const GraphEdge& e) {} - - ///Push a new edge to the back of the path - - ///Push a new edge to the back of the path. - ///If the path is empty, you \em must call \ref setStartNode() before - ///the first use of \ref pushBack(). - void pushBack(const GraphEdge& e) {} - - ///Commit the changes to the path. - void commit() {} - - ///Reserve (front) storage for the builder in advance. - - ///If you know an reasonable upper bound of the number of the edges - ///to add to the front of the path, - ///using this function you may speed up the building. - void reserveFront(size_t r) {} - ///Reserve (back) storage for the builder in advance. - - ///If you know an reasonable upper bound of the number of the edges - ///to add to the back of the path, - ///using this function you may speed up the building. - void reserveBack(size_t r) {} - }; - }; - - ///@} - } - -} // namespace hugo - -#endif // HUGO_SKELETON_PATH_H diff -r 2d6c8075d9d0 -r 818510fa3d99 src/hugo/smart_graph.h --- a/src/hugo/smart_graph.h Wed Sep 29 14:12:26 2004 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,364 +0,0 @@ -/* -*- C++ -*- - * src/hugo/smart_graph.h - Part of HUGOlib, a generic C++ optimization library - * - * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport - * (Egervary Combinatorial Optimization Research Group, 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 HUGO_SMART_GRAPH_H -#define HUGO_SMART_GRAPH_H - -///\ingroup graphs -///\file -///\brief SmartGraph and SymSmartGraph classes. - -#include -#include - -#include - -#include -#include - -#include - -#include - -namespace hugo { - -/// \addtogroup graphs -/// @{ -// class SymSmartGraph; - - ///A smart graph class. - - ///This is a simple and fast graph implementation. - ///It is also quite memory efficient, but at the price - ///that it does not support node and edge deletion. - ///It conforms to - ///the \ref skeleton::ExtendableGraph "ExtendableGraph" concept. - ///\sa skeleton::ExtendableGraph. - /// - ///\todo Some member functions could be \c static. - /// - ///\todo A possibly useful functionality: a function saveState() would - ///give back a data sturcture X and then the function restoreState(X) - ///would remove the nodes and edges added after the call of saveState(). - ///Of course it should be used as a stack. (Maybe X is not necessary.) - /// - ///\author Alpar Juttner - class SmartGraph { - - struct NodeT - { - int first_in,first_out; - NodeT() : first_in(-1), first_out(-1) {} - }; - struct EdgeT - { - int head, tail, next_in, next_out; - //FIXME: is this necessary? - EdgeT() : next_in(-1), next_out(-1) {} - }; - - std::vector nodes; - - std::vector edges; - - - public: - - typedef SmartGraph Graph; - - class Node; - class Edge; - - class NodeIt; - class EdgeIt; - class OutEdgeIt; - class InEdgeIt; - - // Create map registries. - CREATE_MAP_REGISTRIES; - // Create node and edge maps. - CREATE_MAPS(ArrayMap); - - public: - - SmartGraph() : nodes(), edges() { } - SmartGraph(const SmartGraph &_g) : nodes(_g.nodes), edges(_g.edges) { } - - ///Number of nodes. - int nodeNum() const { return nodes.size(); } - ///Number of edges. - int edgeNum() const { return edges.size(); } - - /// Maximum node ID. - - /// Maximum node ID. - ///\sa id(Node) - int maxNodeId() const { return nodes.size()-1; } - /// Maximum edge ID. - - /// Maximum edge ID. - ///\sa id(Edge) - int maxEdgeId() const { return edges.size()-1; } - - Node tail(Edge e) const { return edges[e.n].tail; } - Node head(Edge e) const { return edges[e.n].head; } - - NodeIt& first(NodeIt& v) const { - v=NodeIt(*this); return v; } - EdgeIt& first(EdgeIt& e) const { - e=EdgeIt(*this); return e; } - OutEdgeIt& first(OutEdgeIt& e, const Node v) const { - e=OutEdgeIt(*this,v); return e; } - InEdgeIt& first(InEdgeIt& e, const Node v) const { - e=InEdgeIt(*this,v); return e; } - - /// Node ID. - - /// The ID of a valid Node is a nonnegative integer not greater than - /// \ref maxNodeId(). The range of the ID's is not surely continuous - /// and the greatest node ID can be actually less then \ref maxNodeId(). - /// - /// The ID of the \ref INVALID node is -1. - ///\return The ID of the node \c v. - static int id(Node v) { return v.n; } - /// Edge ID. - - /// The ID of a valid Edge is a nonnegative integer not greater than - /// \ref maxEdgeId(). The range of the ID's is not surely continuous - /// and the greatest edge ID can be actually less then \ref maxEdgeId(). - /// - /// The ID of the \ref INVALID edge is -1. - ///\return The ID of the edge \c e. - static int id(Edge e) { return e.n; } - - Node addNode() { - Node n; n.n=nodes.size(); - nodes.push_back(NodeT()); //FIXME: Hmmm... - - - node_maps.add(n); - return n; - } - - Edge addEdge(Node u, Node v) { - Edge e; e.n=edges.size(); edges.push_back(EdgeT()); //FIXME: Hmmm... - edges[e.n].tail=u.n; edges[e.n].head=v.n; - edges[e.n].next_out=nodes[u.n].first_out; - edges[e.n].next_in=nodes[v.n].first_in; - nodes[u.n].first_out=nodes[v.n].first_in=e.n; - - edge_maps.add(e); - - return e; - } - - /// Finds an edge between two nodes. - - /// Finds an edge from node \c u to node \c v. - /// - /// If \c prev is \ref INVALID (this is the default value), then - /// It finds the first edge from \c u to \c v. Otherwise it looks for - /// the next edge from \c u to \c v after \c prev. - /// \return The found edge or INVALID if there is no such an edge. - Edge findEdge(Node u,Node v, Edge prev = INVALID) - { - int e = (prev.n==-1)? nodes[u.n].first_out : edges[prev.n].next_out; - while(e!=-1 && edges[e].tail!=v.n) e = edges[e].next_out; - prev.n=e; - return prev; - } - - void clear() { - edge_maps.clear(); - edges.clear(); - node_maps.clear(); - nodes.clear(); - } - - class Node { - friend class SmartGraph; - template friend class NodeMap; - - friend class Edge; - friend class OutEdgeIt; - friend class InEdgeIt; - friend class SymEdge; - - protected: - int n; - friend int SmartGraph::id(Node v); - Node(int nn) {n=nn;} - public: - Node() {} - Node (Invalid) { n=-1; } - bool operator==(const Node i) const {return n==i.n;} - bool operator!=(const Node i) const {return n!=i.n;} - bool operator<(const Node i) const {return nnodes.size()+1)-1; - return *this; - } -// ///Validity check -// operator bool() { return Node::operator bool(); } - }; - - class Edge { - friend class SmartGraph; - template friend class EdgeMap; - - friend class SymSmartGraph; - - friend class Node; - friend class NodeIt; - protected: - int n; - friend int SmartGraph::id(Edge e); - Edge(int nn) {n=nn;} - public: - /// An Edge with id \c n. - - Edge() { } - Edge (Invalid) { n=-1; } - bool operator==(const Edge i) const {return n==i.n;} - bool operator!=(const Edge i) const {return n!=i.n;} - bool operator<(const Edge i) const {return nedges[n].next_out; return *this; } -// ///Validity check -// operator bool() { return Edge::operator bool(); } - }; - - class InEdgeIt : public Edge { - const SmartGraph *G; - friend class SmartGraph; - public: - InEdgeIt() : Edge() { } - InEdgeIt(const SmartGraph& _G, Edge e) : Edge(e), G(&_G) { } - InEdgeIt (Invalid i) : Edge(i) { } - InEdgeIt(const SmartGraph& _G,Node v) - : Edge(_G.nodes[v.n].first_in), G(&_G) { } - InEdgeIt &operator++() { n=G->edges[n].next_in; return *this; } -// ///Validity check -// operator bool() { return Edge::operator bool(); } - }; - - }; - - ///Graph for bidirectional edges. - - ///The purpose of this graph structure is to handle graphs - ///having bidirectional edges. Here the function \c addEdge(u,v) adds a pair - ///of oppositely directed edges. - ///There is a new edge map type called - ///\ref SymSmartGraph::SymEdgeMap "SymEdgeMap" - ///that complements this - ///feature by - ///storing shared values for the edge pairs. The usual - ///\ref Graph::EdgeMap "EdgeMap" - ///can be used - ///as well. - /// - ///The oppositely directed edge can also be obtained easily - ///using \ref opposite. - ///\warning It shares the similarity with \ref SmartGraph that - ///it is not possible to delete edges or nodes from the graph. - //\sa SmartGraph. - - class SymSmartGraph : public SmartGraph - { - public: - typedef SymSmartGraph Graph; - - // Create symmetric map registry. - CREATE_SYM_EDGE_MAP_REGISTRY; - // Create symmetric edge map. - CREATE_SYM_EDGE_MAP(ArrayMap); - - - SymSmartGraph() : SmartGraph() { } - SymSmartGraph(const SmartGraph &_g) : SmartGraph(_g) { } - ///Adds a pair of oppositely directed edges to the graph. - Edge addEdge(Node u, Node v) - { - Edge e = SmartGraph::addEdge(u,v); - Edge f = SmartGraph::addEdge(v,u); - sym_edge_maps.add(e); - sym_edge_maps.add(f); - return e; - } - - ///The oppositely directed edge. - - ///Returns the oppositely directed - ///pair of the edge \c e. - static Edge opposite(Edge e) - { - Edge f; - f.n = e.n - 2*(e.n%2) + 1; - return f; - } - - - }; - - /// @} -} //namespace hugo - - - - -#endif //HUGO_SMART_GRAPH_H diff -r 2d6c8075d9d0 -r 818510fa3d99 src/hugo/suurballe.h --- a/src/hugo/suurballe.h Wed Sep 29 14:12:26 2004 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,215 +0,0 @@ -/* -*- C++ -*- - * src/hugo/suurballe.h - Part of HUGOlib, a generic C++ optimization library - * - * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport - * (Egervary Combinatorial Optimization Research Group, 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 HUGO_SUURBALLE_H -#define HUGO_SUURBALLE_H - -///\ingroup flowalgs -///\file -///\brief An algorithm for finding k paths of minimal total length. - - -#include -#include -#include - -namespace hugo { - -/// \addtogroup flowalgs -/// @{ - - ///\brief Implementation of an algorithm for finding k edge-disjoint paths between 2 nodes - /// of minimal total length - /// - /// The class \ref hugo::Suurballe implements - /// an algorithm for finding k edge-disjoint paths - /// from a given source node to a given target node in an - /// edge-weighted directed graph having minimal total weight (length). - /// - ///\warning Length values should be nonnegative. - /// - ///\param Graph The directed graph type the algorithm runs on. - ///\param LengthMap The type of the length map (values should be nonnegative). - /// - ///\note It it questionable if it is correct to call this method after - ///%Suurballe for it is just a special case of Edmond's and Karp's algorithm - ///for finding minimum cost flows. In fact, this implementation is just - ///wraps the MinCostFlow algorithms. The paper of both %Suurballe and - ///Edmonds-Karp published in 1972, therefore it is possibly right to - ///state that they are - ///independent results. Most frequently this special case is referred as - ///%Suurballe method in the literature, especially in communication - ///network context. - ///\author Attila Bernath - template - class Suurballe{ - - - typedef typename LengthMap::ValueType Length; - - typedef typename Graph::Node Node; - typedef typename Graph::NodeIt NodeIt; - typedef typename Graph::Edge Edge; - typedef typename Graph::OutEdgeIt OutEdgeIt; - typedef typename Graph::template EdgeMap EdgeIntMap; - - typedef ConstMap ConstMap; - - //Input - const Graph& G; - - //Auxiliary variables - //This is the capacity map for the mincostflow problem - ConstMap const1map; - //This MinCostFlow instance will actually solve the problem - MinCostFlow mincost_flow; - - //Container to store found paths - std::vector< std::vector > paths; - - public : - - - /// The constructor of the class. - - ///\param _G The directed graph the algorithm runs on. - ///\param _length The length (weight or cost) of the edges. - Suurballe(Graph& _G, LengthMap& _length) : G(_G), - const1map(1), mincost_flow(_G, _length, const1map){} - - ///Runs the algorithm. - - ///Runs the algorithm. - ///Returns k if there are at least k edge-disjoint paths from s to t. - ///Otherwise it returns the number of found edge-disjoint paths from s to t. - /// - ///\param s The source node. - ///\param t The target node. - ///\param k How many paths are we looking for? - /// - int run(Node s, Node t, int k) { - - int i = mincost_flow.run(s,t,k); - - - //Let's find the paths - //We put the paths into stl vectors (as an inner representation). - //In the meantime we lose the information stored in 'reversed'. - //We suppose the lengths to be positive now. - - //We don't want to change the flow of mincost_flow, so we make a copy - //The name here suggests that the flow has only 0/1 values. - EdgeIntMap reversed(G); - - for(typename Graph::EdgeIt e(G); e!=INVALID; ++e) - reversed[e] = mincost_flow.getFlow()[e]; - - paths.clear(); - //total_length=0; - paths.resize(k); - for (int j=0; j - void getPath(Path& p, size_t j){ - - p.clear(); - if (j>paths.size()-1){ - return; - } - typename Path::Builder B(p); - for(typename std::vector::iterator i=paths[j].begin(); - i!=paths[j].end(); ++i ){ - B.pushBack(*i); - } - - B.commit(); - } - - }; //class Suurballe - - ///@} - -} //namespace hugo - -#endif //HUGO_SUURBALLE_H diff -r 2d6c8075d9d0 -r 818510fa3d99 src/hugo/sym_map.h --- a/src/hugo/sym_map.h Wed Sep 29 14:12:26 2004 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,144 +0,0 @@ -/* -*- C++ -*- - * src/hugo/sym_map.h - Part of HUGOlib, a generic C++ optimization library - * - * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport - * (Egervary Combinatorial Optimization Research Group, 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 HUGO_SYM_MAP_H -#define HUGO_SYM_MAP_H - -///\ingroup graphmaps -///\file -///\brief Graph maps that construates and destruates -///their elements dynamically. - -namespace hugo { - -/// \addtogroup graphmaps -/// @{ - - /** The SymEdgeIt is wrapper class for the EdgeIt. It can be used to - * iterate on the symmetric maps when all of the edge - reverse edge pair - * has different parity. - */ - - - template - class SymEdgeIt : public EdgeIt { - public: - - /** Default constructor. - */ - SymEdgeIt() - : EdgeIt() {} - - /** Graph initialized constructor. - */ - SymEdgeIt(const Graph& graph) - : EdgeIt(graph) { - while ( (EdgeIt::n & 1) && EdgeIt::n != -1) { - EdgeIt::operator++(); - } - } - - /** Creating invelid SymEdgeIt. - */ - SymEdgeIt(Invalid invalid) - : EdgeIt(invalid) {} - - /** SymEdgeIt from the given Edge. - */ - SymEdgeIt(const Graph& graph, const Edge& edge) - : EdgeIt(graph, edge) { - while ( (EdgeIt::n & 1) && EdgeIt::n != -1) { - EdgeIt::operator++(); - } - } - - /** Increase operator. - */ - SymEdgeIt& operator++() { - EdgeIt::operator++(); - while ( (EdgeIt::n & 1) && EdgeIt::n != -1) { - EdgeIt::operator++(); - } - return *this; - } - }; - - /** The SymMap template class is graph map structure what - * wraps an other map structure to use as symmetric map structure. - * - * The template parameter is the MapRegistry that the maps - * will belong to and the ValueType. - */ - template