1.1 --- a/demo/graph_to_eps_demo.cc Tue Jul 15 18:43:41 2008 +0100
1.2 +++ b/demo/graph_to_eps_demo.cc Tue Jul 15 18:49:30 2008 +0100
1.3 @@ -31,7 +31,6 @@
1.4 /// \include graph_to_eps_demo.cc
1.5
1.6 #include<lemon/list_graph.h>
1.7 -#include<lemon/graph_utils.h>
1.8 #include<lemon/graph_to_eps.h>
1.9 #include<lemon/math.h>
1.10
2.1 --- a/lemon/Makefile.am Tue Jul 15 18:43:41 2008 +0100
2.2 +++ b/lemon/Makefile.am Tue Jul 15 18:49:30 2008 +0100
2.3 @@ -24,12 +24,12 @@
2.4 lemon/color.h \
2.5 lemon/concept_check.h \
2.6 lemon/counter.h \
2.7 + lemon/core.h \
2.8 lemon/dfs.h \
2.9 lemon/dijkstra.h \
2.10 lemon/dim2.h \
2.11 lemon/error.h \
2.12 lemon/graph_to_eps.h \
2.13 - lemon/graph_utils.h \
2.14 lemon/kruskal.h \
2.15 lemon/lgf_reader.h \
2.16 lemon/lgf_writer.h \
2.17 @@ -49,12 +49,11 @@
2.18 lemon/bits/base_extender.h \
2.19 lemon/bits/bezier.h \
2.20 lemon/bits/default_map.h \
2.21 + lemon/bits/enable_if.h \
2.22 lemon/bits/graph_extender.h \
2.23 - lemon/bits/invalid.h \
2.24 lemon/bits/map_extender.h \
2.25 lemon/bits/path_dump.h \
2.26 lemon/bits/traits.h \
2.27 - lemon/bits/utility.h \
2.28 lemon/bits/vector_map.h
2.29
2.30 concept_HEADERS += \
3.1 --- a/lemon/base.cc Tue Jul 15 18:43:41 2008 +0100
3.2 +++ b/lemon/base.cc Tue Jul 15 18:49:30 2008 +0100
3.3 @@ -20,7 +20,7 @@
3.4 ///\brief Some basic non-inline functions and static global data.
3.5
3.6 #include<lemon/tolerance.h>
3.7 -#include<lemon/bits/invalid.h>
3.8 +#include<lemon/core.h>
3.9 namespace lemon {
3.10
3.11 float Tolerance<float>::def_epsilon = 1e-4;
4.1 --- a/lemon/bfs.h Tue Jul 15 18:43:41 2008 +0100
4.2 +++ b/lemon/bfs.h Tue Jul 15 18:49:30 2008 +0100
4.3 @@ -24,9 +24,8 @@
4.4 ///\brief Bfs algorithm.
4.5
4.6 #include <lemon/list_graph.h>
4.7 -#include <lemon/graph_utils.h>
4.8 #include <lemon/bits/path_dump.h>
4.9 -#include <lemon/bits/invalid.h>
4.10 +#include <lemon/core.h>
4.11 #include <lemon/error.h>
4.12 #include <lemon/maps.h>
4.13
5.1 --- a/lemon/bits/alteration_notifier.h Tue Jul 15 18:43:41 2008 +0100
5.2 +++ b/lemon/bits/alteration_notifier.h Tue Jul 15 18:49:30 2008 +0100
5.3 @@ -22,7 +22,7 @@
5.4 #include <vector>
5.5 #include <list>
5.6
5.7 -#include <lemon/bits/utility.h>
5.8 +#include <lemon/core.h>
5.9
5.10 ///\ingroup graphbits
5.11 ///\file
6.1 --- a/lemon/bits/base_extender.h Tue Jul 15 18:43:41 2008 +0100
6.2 +++ b/lemon/bits/base_extender.h Tue Jul 15 18:49:30 2008 +0100
6.3 @@ -19,7 +19,7 @@
6.4 #ifndef LEMON_BITS_BASE_EXTENDER_H
6.5 #define LEMON_BITS_BASE_EXTENDER_H
6.6
6.7 -#include <lemon/bits/invalid.h>
6.8 +#include <lemon/core.h>
6.9 #include <lemon/error.h>
6.10
6.11 #include <lemon/bits/map_extender.h>
7.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
7.2 +++ b/lemon/bits/enable_if.h Tue Jul 15 18:49:30 2008 +0100
7.3 @@ -0,0 +1,131 @@
7.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
7.5 + *
7.6 + * This file is a part of LEMON, a generic C++ optimization library.
7.7 + *
7.8 + * Copyright (C) 2003-2008
7.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
7.11 + *
7.12 + * Permission to use, modify and distribute this software is granted
7.13 + * provided that this copyright notice appears in all copies. For
7.14 + * precise terms see the accompanying LICENSE file.
7.15 + *
7.16 + * This software is provided "AS IS" with no warranty of any kind,
7.17 + * express or implied, and with no claim as to its suitability for any
7.18 + * purpose.
7.19 + *
7.20 + */
7.21 +
7.22 +// This file contains a modified version of the enable_if library from BOOST.
7.23 +// See the appropriate copyright notice below.
7.24 +
7.25 +// Boost enable_if library
7.26 +
7.27 +// Copyright 2003 (c) The Trustees of Indiana University.
7.28 +
7.29 +// Use, modification, and distribution is subject to the Boost Software
7.30 +// License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
7.31 +// http://www.boost.org/LICENSE_1_0.txt)
7.32 +
7.33 +// Authors: Jaakko Jarvi (jajarvi at osl.iu.edu)
7.34 +// Jeremiah Willcock (jewillco at osl.iu.edu)
7.35 +// Andrew Lumsdaine (lums at osl.iu.edu)
7.36 +
7.37 +
7.38 +#ifndef LEMON_BITS_ENABLE_IF_H
7.39 +#define LEMON_BITS_ENABLE_IF_H
7.40 +
7.41 +///\file
7.42 +///\brief Miscellaneous basic utilities
7.43 +
7.44 +namespace lemon
7.45 +{
7.46 +
7.47 + /// Basic type for defining "tags". A "YES" condition for \c enable_if.
7.48 +
7.49 + /// Basic type for defining "tags". A "YES" condition for \c enable_if.
7.50 + ///
7.51 + ///\sa False
7.52 + struct True {
7.53 + ///\e
7.54 + static const bool value = true;
7.55 + };
7.56 +
7.57 + /// Basic type for defining "tags". A "NO" condition for \c enable_if.
7.58 +
7.59 + /// Basic type for defining "tags". A "NO" condition for \c enable_if.
7.60 + ///
7.61 + ///\sa True
7.62 + struct False {
7.63 + ///\e
7.64 + static const bool value = false;
7.65 + };
7.66 +
7.67 +
7.68 +
7.69 + template <typename T>
7.70 + struct Wrap {
7.71 + const T &value;
7.72 + Wrap(const T &t) : value(t) {}
7.73 + };
7.74 +
7.75 + /**************** dummy class to avoid ambiguity ****************/
7.76 +
7.77 + template<int T> struct dummy { dummy(int) {} };
7.78 +
7.79 + /**************** enable_if from BOOST ****************/
7.80 +
7.81 + template <typename Type, typename T = void>
7.82 + struct exists {
7.83 + typedef T type;
7.84 + };
7.85 +
7.86 +
7.87 + template <bool B, class T = void>
7.88 + struct enable_if_c {
7.89 + typedef T type;
7.90 + };
7.91 +
7.92 + template <class T>
7.93 + struct enable_if_c<false, T> {};
7.94 +
7.95 + template <class Cond, class T = void>
7.96 + struct enable_if : public enable_if_c<Cond::value, T> {};
7.97 +
7.98 + template <bool B, class T>
7.99 + struct lazy_enable_if_c {
7.100 + typedef typename T::type type;
7.101 + };
7.102 +
7.103 + template <class T>
7.104 + struct lazy_enable_if_c<false, T> {};
7.105 +
7.106 + template <class Cond, class T>
7.107 + struct lazy_enable_if : public lazy_enable_if_c<Cond::value, T> {};
7.108 +
7.109 +
7.110 + template <bool B, class T = void>
7.111 + struct disable_if_c {
7.112 + typedef T type;
7.113 + };
7.114 +
7.115 + template <class T>
7.116 + struct disable_if_c<true, T> {};
7.117 +
7.118 + template <class Cond, class T = void>
7.119 + struct disable_if : public disable_if_c<Cond::value, T> {};
7.120 +
7.121 + template <bool B, class T>
7.122 + struct lazy_disable_if_c {
7.123 + typedef typename T::type type;
7.124 + };
7.125 +
7.126 + template <class T>
7.127 + struct lazy_disable_if_c<true, T> {};
7.128 +
7.129 + template <class Cond, class T>
7.130 + struct lazy_disable_if : public lazy_disable_if_c<Cond::value, T> {};
7.131 +
7.132 +} // namespace lemon
7.133 +
7.134 +#endif
8.1 --- a/lemon/bits/graph_extender.h Tue Jul 15 18:43:41 2008 +0100
8.2 +++ b/lemon/bits/graph_extender.h Tue Jul 15 18:49:30 2008 +0100
8.3 @@ -19,8 +19,7 @@
8.4 #ifndef LEMON_BITS_GRAPH_EXTENDER_H
8.5 #define LEMON_BITS_GRAPH_EXTENDER_H
8.6
8.7 -#include <lemon/bits/invalid.h>
8.8 -#include <lemon/bits/utility.h>
8.9 +#include <lemon/core.h>
8.10
8.11 #include <lemon/bits/map_extender.h>
8.12 #include <lemon/bits/default_map.h>
9.1 --- a/lemon/bits/invalid.h Tue Jul 15 18:43:41 2008 +0100
9.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
9.3 @@ -1,55 +0,0 @@
9.4 -/* -*- mode: C++; indent-tabs-mode: nil; -*-
9.5 - *
9.6 - * This file is a part of LEMON, a generic C++ optimization library.
9.7 - *
9.8 - * Copyright (C) 2003-2008
9.9 - * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
9.10 - * (Egervary Research Group on Combinatorial Optimization, EGRES).
9.11 - *
9.12 - * Permission to use, modify and distribute this software is granted
9.13 - * provided that this copyright notice appears in all copies. For
9.14 - * precise terms see the accompanying LICENSE file.
9.15 - *
9.16 - * This software is provided "AS IS" with no warranty of any kind,
9.17 - * express or implied, and with no claim as to its suitability for any
9.18 - * purpose.
9.19 - *
9.20 - */
9.21 -
9.22 -#ifndef LEMON_BITS_INVALID_H
9.23 -#define LEMON_BITS_INVALID_H
9.24 -
9.25 -///\file
9.26 -///\brief Definition of INVALID.
9.27 -
9.28 -namespace lemon {
9.29 -
9.30 - /// \brief Dummy type to make it easier to create invalid iterators.
9.31 - ///
9.32 - /// Dummy type to make it easier to create invalid iterators.
9.33 - /// See \ref INVALID for the usage.
9.34 - struct Invalid {
9.35 - public:
9.36 - bool operator==(Invalid) { return true; }
9.37 - bool operator!=(Invalid) { return false; }
9.38 - bool operator< (Invalid) { return false; }
9.39 - };
9.40 -
9.41 - /// \brief Invalid iterators.
9.42 - ///
9.43 - /// \ref Invalid is a global type that converts to each iterator
9.44 - /// in such a way that the value of the target iterator will be invalid.
9.45 -
9.46 - //Some people didn't like this:
9.47 - //const Invalid &INVALID = *(Invalid *)0;
9.48 -
9.49 -#ifdef LEMON_ONLY_TEMPLATES
9.50 - const Invalid INVALID = Invalid();
9.51 -#else
9.52 - extern const Invalid INVALID;
9.53 -#endif
9.54 -
9.55 -} //namespace lemon
9.56 -
9.57 -#endif
9.58 -
10.1 --- a/lemon/bits/traits.h Tue Jul 15 18:43:41 2008 +0100
10.2 +++ b/lemon/bits/traits.h Tue Jul 15 18:49:30 2008 +0100
10.3 @@ -19,13 +19,16 @@
10.4 #ifndef LEMON_BITS_TRAITS_H
10.5 #define LEMON_BITS_TRAITS_H
10.6
10.7 -#include <lemon/bits/utility.h>
10.8 -
10.9 ///\file
10.10 ///\brief Traits for graphs and maps
10.11 ///
10.12
10.13 +#include <lemon/bits/enable_if.h>
10.14 +
10.15 namespace lemon {
10.16 +
10.17 + struct InvalidType {};
10.18 +
10.19 template <typename _Graph, typename _Item>
10.20 class ItemSetTraits {};
10.21
11.1 --- a/lemon/bits/utility.h Tue Jul 15 18:43:41 2008 +0100
11.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
11.3 @@ -1,140 +0,0 @@
11.4 -/* -*- mode: C++; indent-tabs-mode: nil; -*-
11.5 - *
11.6 - * This file is a part of LEMON, a generic C++ optimization library.
11.7 - *
11.8 - * Copyright (C) 2003-2008
11.9 - * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
11.10 - * (Egervary Research Group on Combinatorial Optimization, EGRES).
11.11 - *
11.12 - * Permission to use, modify and distribute this software is granted
11.13 - * provided that this copyright notice appears in all copies. For
11.14 - * precise terms see the accompanying LICENSE file.
11.15 - *
11.16 - * This software is provided "AS IS" with no warranty of any kind,
11.17 - * express or implied, and with no claim as to its suitability for any
11.18 - * purpose.
11.19 - *
11.20 - */
11.21 -
11.22 -// This file contains a modified version of the enable_if library from BOOST.
11.23 -// See the appropriate copyright notice below.
11.24 -
11.25 -// Boost enable_if library
11.26 -
11.27 -// Copyright 2003 (c) The Trustees of Indiana University.
11.28 -
11.29 -// Use, modification, and distribution is subject to the Boost Software
11.30 -// License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
11.31 -// http://www.boost.org/LICENSE_1_0.txt)
11.32 -
11.33 -// Authors: Jaakko Jarvi (jajarvi at osl.iu.edu)
11.34 -// Jeremiah Willcock (jewillco at osl.iu.edu)
11.35 -// Andrew Lumsdaine (lums at osl.iu.edu)
11.36 -
11.37 -
11.38 -#ifndef LEMON_BITS_UTILITY_H
11.39 -#define LEMON_BITS_UTILITY_H
11.40 -
11.41 -///\file
11.42 -///\brief Miscellaneous basic utilities
11.43 -///
11.44 -///\todo Please rethink the organisation of the basic files like this.
11.45 -///E.g. this file might be merged with invalid.h.
11.46 -
11.47 -
11.48 -namespace lemon
11.49 -{
11.50 -
11.51 - /// Basic type for defining "tags". A "YES" condition for \c enable_if.
11.52 -
11.53 - /// Basic type for defining "tags". A "YES" condition for \c enable_if.
11.54 - ///
11.55 - ///\sa False
11.56 - ///
11.57 - /// \todo This should go to a separate "basic_types.h" (or something)
11.58 - /// file.
11.59 - struct True {
11.60 - ///\e
11.61 - static const bool value = true;
11.62 - };
11.63 -
11.64 - /// Basic type for defining "tags". A "NO" condition for \c enable_if.
11.65 -
11.66 - /// Basic type for defining "tags". A "NO" condition for \c enable_if.
11.67 - ///
11.68 - ///\sa True
11.69 - struct False {
11.70 - ///\e
11.71 - static const bool value = false;
11.72 - };
11.73 -
11.74 -
11.75 - struct InvalidType {
11.76 - };
11.77 -
11.78 - template <typename T>
11.79 - struct Wrap {
11.80 - const T &value;
11.81 - Wrap(const T &t) : value(t) {}
11.82 - };
11.83 -
11.84 - /**************** dummy class to avoid ambiguity ****************/
11.85 -
11.86 - template<int T> struct dummy { dummy(int) {} };
11.87 -
11.88 - /**************** enable_if from BOOST ****************/
11.89 -
11.90 - template <typename Type, typename T = void>
11.91 - struct exists {
11.92 - typedef T type;
11.93 - };
11.94 -
11.95 -
11.96 - template <bool B, class T = void>
11.97 - struct enable_if_c {
11.98 - typedef T type;
11.99 - };
11.100 -
11.101 - template <class T>
11.102 - struct enable_if_c<false, T> {};
11.103 -
11.104 - template <class Cond, class T = void>
11.105 - struct enable_if : public enable_if_c<Cond::value, T> {};
11.106 -
11.107 - template <bool B, class T>
11.108 - struct lazy_enable_if_c {
11.109 - typedef typename T::type type;
11.110 - };
11.111 -
11.112 - template <class T>
11.113 - struct lazy_enable_if_c<false, T> {};
11.114 -
11.115 - template <class Cond, class T>
11.116 - struct lazy_enable_if : public lazy_enable_if_c<Cond::value, T> {};
11.117 -
11.118 -
11.119 - template <bool B, class T = void>
11.120 - struct disable_if_c {
11.121 - typedef T type;
11.122 - };
11.123 -
11.124 - template <class T>
11.125 - struct disable_if_c<true, T> {};
11.126 -
11.127 - template <class Cond, class T = void>
11.128 - struct disable_if : public disable_if_c<Cond::value, T> {};
11.129 -
11.130 - template <bool B, class T>
11.131 - struct lazy_disable_if_c {
11.132 - typedef typename T::type type;
11.133 - };
11.134 -
11.135 - template <class T>
11.136 - struct lazy_disable_if_c<true, T> {};
11.137 -
11.138 - template <class Cond, class T>
11.139 - struct lazy_disable_if : public lazy_disable_if_c<Cond::value, T> {};
11.140 -
11.141 -} // namespace lemon
11.142 -
11.143 -#endif
12.1 --- a/lemon/bits/vector_map.h Tue Jul 15 18:43:41 2008 +0100
12.2 +++ b/lemon/bits/vector_map.h Tue Jul 15 18:49:30 2008 +0100
12.3 @@ -22,9 +22,7 @@
12.4 #include <vector>
12.5 #include <algorithm>
12.6
12.7 -#include <lemon/bits/traits.h>
12.8 -#include <lemon/bits/utility.h>
12.9 -
12.10 +#include <lemon/core.h>
12.11 #include <lemon/bits/alteration_notifier.h>
12.12
12.13 #include <lemon/concept_check.h>
13.1 --- a/lemon/concepts/digraph.h Tue Jul 15 18:43:41 2008 +0100
13.2 +++ b/lemon/concepts/digraph.h Tue Jul 15 18:49:30 2008 +0100
13.3 @@ -23,8 +23,7 @@
13.4 ///\file
13.5 ///\brief The concept of directed graphs.
13.6
13.7 -#include <lemon/bits/invalid.h>
13.8 -#include <lemon/bits/utility.h>
13.9 +#include <lemon/core.h>
13.10 #include <lemon/concepts/maps.h>
13.11 #include <lemon/concept_check.h>
13.12 #include <lemon/concepts/graph_components.h>
14.1 --- a/lemon/concepts/graph.h Tue Jul 15 18:43:41 2008 +0100
14.2 +++ b/lemon/concepts/graph.h Tue Jul 15 18:49:30 2008 +0100
14.3 @@ -25,7 +25,7 @@
14.4
14.5 #include <lemon/concepts/graph_components.h>
14.6 #include <lemon/concepts/graph.h>
14.7 -#include <lemon/bits/utility.h>
14.8 +#include <lemon/core.h>
14.9
14.10 namespace lemon {
14.11 namespace concepts {
15.1 --- a/lemon/concepts/graph_components.h Tue Jul 15 18:43:41 2008 +0100
15.2 +++ b/lemon/concepts/graph_components.h Tue Jul 15 18:49:30 2008 +0100
15.3 @@ -24,7 +24,7 @@
15.4 #ifndef LEMON_CONCEPT_GRAPH_COMPONENTS_H
15.5 #define LEMON_CONCEPT_GRAPH_COMPONENTS_H
15.6
15.7 -#include <lemon/bits/invalid.h>
15.8 +#include <lemon/core.h>
15.9 #include <lemon/concepts/maps.h>
15.10
15.11 #include <lemon/bits/alteration_notifier.h>
16.1 --- a/lemon/concepts/heap.h Tue Jul 15 18:43:41 2008 +0100
16.2 +++ b/lemon/concepts/heap.h Tue Jul 15 18:49:30 2008 +0100
16.3 @@ -23,7 +23,7 @@
16.4 #ifndef LEMON_CONCEPT_HEAP_H
16.5 #define LEMON_CONCEPT_HEAP_H
16.6
16.7 -#include <lemon/bits/invalid.h>
16.8 +#include <lemon/core.h>
16.9
16.10 namespace lemon {
16.11
17.1 --- a/lemon/concepts/maps.h Tue Jul 15 18:43:41 2008 +0100
17.2 +++ b/lemon/concepts/maps.h Tue Jul 15 18:49:30 2008 +0100
17.3 @@ -19,7 +19,7 @@
17.4 #ifndef LEMON_CONCEPT_MAPS_H
17.5 #define LEMON_CONCEPT_MAPS_H
17.6
17.7 -#include <lemon/bits/utility.h>
17.8 +#include <lemon/core.h>
17.9 #include <lemon/concept_check.h>
17.10
17.11 ///\ingroup concept
18.1 --- a/lemon/concepts/path.h Tue Jul 15 18:43:41 2008 +0100
18.2 +++ b/lemon/concepts/path.h Tue Jul 15 18:49:30 2008 +0100
18.3 @@ -25,8 +25,7 @@
18.4 #ifndef LEMON_CONCEPT_PATH_H
18.5 #define LEMON_CONCEPT_PATH_H
18.6
18.7 -#include <lemon/bits/invalid.h>
18.8 -#include <lemon/bits/utility.h>
18.9 +#include <lemon/core.h>
18.10 #include <lemon/concept_check.h>
18.11
18.12 namespace lemon {
19.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
19.2 +++ b/lemon/core.h Tue Jul 15 18:49:30 2008 +0100
19.3 @@ -0,0 +1,1851 @@
19.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
19.5 + *
19.6 + * This file is a part of LEMON, a generic C++ optimization library.
19.7 + *
19.8 + * Copyright (C) 2003-2008
19.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
19.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
19.11 + *
19.12 + * Permission to use, modify and distribute this software is granted
19.13 + * provided that this copyright notice appears in all copies. For
19.14 + * precise terms see the accompanying LICENSE file.
19.15 + *
19.16 + * This software is provided "AS IS" with no warranty of any kind,
19.17 + * express or implied, and with no claim as to its suitability for any
19.18 + * purpose.
19.19 + *
19.20 + */
19.21 +
19.22 +#ifndef LEMON_CORE_H
19.23 +#define LEMON_CORE_H
19.24 +
19.25 +#include <vector>
19.26 +#include <algorithm>
19.27 +
19.28 +#include <lemon/bits/enable_if.h>
19.29 +#include <lemon/bits/traits.h>
19.30 +
19.31 +///\file
19.32 +///\brief LEMON core utilities.
19.33 +
19.34 +namespace lemon {
19.35 +
19.36 + /// \brief Dummy type to make it easier to create invalid iterators.
19.37 + ///
19.38 + /// Dummy type to make it easier to create invalid iterators.
19.39 + /// See \ref INVALID for the usage.
19.40 + struct Invalid {
19.41 + public:
19.42 + bool operator==(Invalid) { return true; }
19.43 + bool operator!=(Invalid) { return false; }
19.44 + bool operator< (Invalid) { return false; }
19.45 + };
19.46 +
19.47 + /// \brief Invalid iterators.
19.48 + ///
19.49 + /// \ref Invalid is a global type that converts to each iterator
19.50 + /// in such a way that the value of the target iterator will be invalid.
19.51 +#ifdef LEMON_ONLY_TEMPLATES
19.52 + const Invalid INVALID = Invalid();
19.53 +#else
19.54 + extern const Invalid INVALID;
19.55 +#endif
19.56 +
19.57 + /// \addtogroup gutils
19.58 + /// @{
19.59 +
19.60 + ///Creates convenience typedefs for the digraph types and iterators
19.61 +
19.62 + ///This \c \#define creates convenience typedefs for the following types
19.63 + ///of \c Digraph: \c Node, \c NodeIt, \c Arc, \c ArcIt, \c InArcIt,
19.64 + ///\c OutArcIt, \c BoolNodeMap, \c IntNodeMap, \c DoubleNodeMap,
19.65 + ///\c BoolArcMap, \c IntArcMap, \c DoubleArcMap.
19.66 + ///
19.67 + ///\note If the graph type is a dependent type, ie. the graph type depend
19.68 + ///on a template parameter, then use \c TEMPLATE_DIGRAPH_TYPEDEFS()
19.69 + ///macro.
19.70 +#define DIGRAPH_TYPEDEFS(Digraph) \
19.71 + typedef Digraph::Node Node; \
19.72 + typedef Digraph::NodeIt NodeIt; \
19.73 + typedef Digraph::Arc Arc; \
19.74 + typedef Digraph::ArcIt ArcIt; \
19.75 + typedef Digraph::InArcIt InArcIt; \
19.76 + typedef Digraph::OutArcIt OutArcIt; \
19.77 + typedef Digraph::NodeMap<bool> BoolNodeMap; \
19.78 + typedef Digraph::NodeMap<int> IntNodeMap; \
19.79 + typedef Digraph::NodeMap<double> DoubleNodeMap; \
19.80 + typedef Digraph::ArcMap<bool> BoolArcMap; \
19.81 + typedef Digraph::ArcMap<int> IntArcMap; \
19.82 + typedef Digraph::ArcMap<double> DoubleArcMap
19.83 +
19.84 + ///Creates convenience typedefs for the digraph types and iterators
19.85 +
19.86 + ///\see DIGRAPH_TYPEDEFS
19.87 + ///
19.88 + ///\note Use this macro, if the graph type is a dependent type,
19.89 + ///ie. the graph type depend on a template parameter.
19.90 +#define TEMPLATE_DIGRAPH_TYPEDEFS(Digraph) \
19.91 + typedef typename Digraph::Node Node; \
19.92 + typedef typename Digraph::NodeIt NodeIt; \
19.93 + typedef typename Digraph::Arc Arc; \
19.94 + typedef typename Digraph::ArcIt ArcIt; \
19.95 + typedef typename Digraph::InArcIt InArcIt; \
19.96 + typedef typename Digraph::OutArcIt OutArcIt; \
19.97 + typedef typename Digraph::template NodeMap<bool> BoolNodeMap; \
19.98 + typedef typename Digraph::template NodeMap<int> IntNodeMap; \
19.99 + typedef typename Digraph::template NodeMap<double> DoubleNodeMap; \
19.100 + typedef typename Digraph::template ArcMap<bool> BoolArcMap; \
19.101 + typedef typename Digraph::template ArcMap<int> IntArcMap; \
19.102 + typedef typename Digraph::template ArcMap<double> DoubleArcMap
19.103 +
19.104 + ///Creates convenience typedefs for the graph types and iterators
19.105 +
19.106 + ///This \c \#define creates the same convenience typedefs as defined
19.107 + ///by \ref DIGRAPH_TYPEDEFS(Graph) and six more, namely it creates
19.108 + ///\c Edge, \c EdgeIt, \c IncEdgeIt, \c BoolEdgeMap, \c IntEdgeMap,
19.109 + ///\c DoubleEdgeMap.
19.110 + ///
19.111 + ///\note If the graph type is a dependent type, ie. the graph type depend
19.112 + ///on a template parameter, then use \c TEMPLATE_DIGRAPH_TYPEDEFS()
19.113 + ///macro.
19.114 +#define GRAPH_TYPEDEFS(Graph) \
19.115 + DIGRAPH_TYPEDEFS(Graph); \
19.116 + typedef Graph::Edge Edge; \
19.117 + typedef Graph::EdgeIt EdgeIt; \
19.118 + typedef Graph::IncEdgeIt IncEdgeIt; \
19.119 + typedef Graph::EdgeMap<bool> BoolEdgeMap; \
19.120 + typedef Graph::EdgeMap<int> IntEdgeMap; \
19.121 + typedef Graph::EdgeMap<double> DoubleEdgeMap
19.122 +
19.123 + ///Creates convenience typedefs for the graph types and iterators
19.124 +
19.125 + ///\see GRAPH_TYPEDEFS
19.126 + ///
19.127 + ///\note Use this macro, if the graph type is a dependent type,
19.128 + ///ie. the graph type depend on a template parameter.
19.129 +#define TEMPLATE_GRAPH_TYPEDEFS(Graph) \
19.130 + TEMPLATE_DIGRAPH_TYPEDEFS(Graph); \
19.131 + typedef typename Graph::Edge Edge; \
19.132 + typedef typename Graph::EdgeIt EdgeIt; \
19.133 + typedef typename Graph::IncEdgeIt IncEdgeIt; \
19.134 + typedef typename Graph::template EdgeMap<bool> BoolEdgeMap; \
19.135 + typedef typename Graph::template EdgeMap<int> IntEdgeMap; \
19.136 + typedef typename Graph::template EdgeMap<double> DoubleEdgeMap
19.137 +
19.138 + /// \brief Function to count the items in the graph.
19.139 + ///
19.140 + /// This function counts the items (nodes, arcs etc) in the graph.
19.141 + /// The complexity of the function is O(n) because
19.142 + /// it iterates on all of the items.
19.143 + template <typename Graph, typename Item>
19.144 + inline int countItems(const Graph& g) {
19.145 + typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;
19.146 + int num = 0;
19.147 + for (ItemIt it(g); it != INVALID; ++it) {
19.148 + ++num;
19.149 + }
19.150 + return num;
19.151 + }
19.152 +
19.153 + // Node counting:
19.154 +
19.155 + namespace _core_bits {
19.156 +
19.157 + template <typename Graph, typename Enable = void>
19.158 + struct CountNodesSelector {
19.159 + static int count(const Graph &g) {
19.160 + return countItems<Graph, typename Graph::Node>(g);
19.161 + }
19.162 + };
19.163 +
19.164 + template <typename Graph>
19.165 + struct CountNodesSelector<
19.166 + Graph, typename
19.167 + enable_if<typename Graph::NodeNumTag, void>::type>
19.168 + {
19.169 + static int count(const Graph &g) {
19.170 + return g.nodeNum();
19.171 + }
19.172 + };
19.173 + }
19.174 +
19.175 + /// \brief Function to count the nodes in the graph.
19.176 + ///
19.177 + /// This function counts the nodes in the graph.
19.178 + /// The complexity of the function is O(n) but for some
19.179 + /// graph structures it is specialized to run in O(1).
19.180 + ///
19.181 + /// If the graph contains a \e nodeNum() member function and a
19.182 + /// \e NodeNumTag tag then this function calls directly the member
19.183 + /// function to query the cardinality of the node set.
19.184 + template <typename Graph>
19.185 + inline int countNodes(const Graph& g) {
19.186 + return _core_bits::CountNodesSelector<Graph>::count(g);
19.187 + }
19.188 +
19.189 + // Arc counting:
19.190 +
19.191 + namespace _core_bits {
19.192 +
19.193 + template <typename Graph, typename Enable = void>
19.194 + struct CountArcsSelector {
19.195 + static int count(const Graph &g) {
19.196 + return countItems<Graph, typename Graph::Arc>(g);
19.197 + }
19.198 + };
19.199 +
19.200 + template <typename Graph>
19.201 + struct CountArcsSelector<
19.202 + Graph,
19.203 + typename enable_if<typename Graph::ArcNumTag, void>::type>
19.204 + {
19.205 + static int count(const Graph &g) {
19.206 + return g.arcNum();
19.207 + }
19.208 + };
19.209 + }
19.210 +
19.211 + /// \brief Function to count the arcs in the graph.
19.212 + ///
19.213 + /// This function counts the arcs in the graph.
19.214 + /// The complexity of the function is O(e) but for some
19.215 + /// graph structures it is specialized to run in O(1).
19.216 + ///
19.217 + /// If the graph contains a \e arcNum() member function and a
19.218 + /// \e EdgeNumTag tag then this function calls directly the member
19.219 + /// function to query the cardinality of the arc set.
19.220 + template <typename Graph>
19.221 + inline int countArcs(const Graph& g) {
19.222 + return _core_bits::CountArcsSelector<Graph>::count(g);
19.223 + }
19.224 +
19.225 + // Edge counting:
19.226 + namespace _core_bits {
19.227 +
19.228 + template <typename Graph, typename Enable = void>
19.229 + struct CountEdgesSelector {
19.230 + static int count(const Graph &g) {
19.231 + return countItems<Graph, typename Graph::Edge>(g);
19.232 + }
19.233 + };
19.234 +
19.235 + template <typename Graph>
19.236 + struct CountEdgesSelector<
19.237 + Graph,
19.238 + typename enable_if<typename Graph::EdgeNumTag, void>::type>
19.239 + {
19.240 + static int count(const Graph &g) {
19.241 + return g.edgeNum();
19.242 + }
19.243 + };
19.244 + }
19.245 +
19.246 + /// \brief Function to count the edges in the graph.
19.247 + ///
19.248 + /// This function counts the edges in the graph.
19.249 + /// The complexity of the function is O(m) but for some
19.250 + /// graph structures it is specialized to run in O(1).
19.251 + ///
19.252 + /// If the graph contains a \e edgeNum() member function and a
19.253 + /// \e EdgeNumTag tag then this function calls directly the member
19.254 + /// function to query the cardinality of the edge set.
19.255 + template <typename Graph>
19.256 + inline int countEdges(const Graph& g) {
19.257 + return _core_bits::CountEdgesSelector<Graph>::count(g);
19.258 +
19.259 + }
19.260 +
19.261 +
19.262 + template <typename Graph, typename DegIt>
19.263 + inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) {
19.264 + int num = 0;
19.265 + for (DegIt it(_g, _n); it != INVALID; ++it) {
19.266 + ++num;
19.267 + }
19.268 + return num;
19.269 + }
19.270 +
19.271 + /// \brief Function to count the number of the out-arcs from node \c n.
19.272 + ///
19.273 + /// This function counts the number of the out-arcs from node \c n
19.274 + /// in the graph.
19.275 + template <typename Graph>
19.276 + inline int countOutArcs(const Graph& _g, const typename Graph::Node& _n) {
19.277 + return countNodeDegree<Graph, typename Graph::OutArcIt>(_g, _n);
19.278 + }
19.279 +
19.280 + /// \brief Function to count the number of the in-arcs to node \c n.
19.281 + ///
19.282 + /// This function counts the number of the in-arcs to node \c n
19.283 + /// in the graph.
19.284 + template <typename Graph>
19.285 + inline int countInArcs(const Graph& _g, const typename Graph::Node& _n) {
19.286 + return countNodeDegree<Graph, typename Graph::InArcIt>(_g, _n);
19.287 + }
19.288 +
19.289 + /// \brief Function to count the number of the inc-edges to node \c n.
19.290 + ///
19.291 + /// This function counts the number of the inc-edges to node \c n
19.292 + /// in the graph.
19.293 + template <typename Graph>
19.294 + inline int countIncEdges(const Graph& _g, const typename Graph::Node& _n) {
19.295 + return countNodeDegree<Graph, typename Graph::IncEdgeIt>(_g, _n);
19.296 + }
19.297 +
19.298 + namespace _core_bits {
19.299 +
19.300 + template <typename Digraph, typename Item, typename RefMap>
19.301 + class MapCopyBase {
19.302 + public:
19.303 + virtual void copy(const Digraph& from, const RefMap& refMap) = 0;
19.304 +
19.305 + virtual ~MapCopyBase() {}
19.306 + };
19.307 +
19.308 + template <typename Digraph, typename Item, typename RefMap,
19.309 + typename ToMap, typename FromMap>
19.310 + class MapCopy : public MapCopyBase<Digraph, Item, RefMap> {
19.311 + public:
19.312 +
19.313 + MapCopy(ToMap& tmap, const FromMap& map)
19.314 + : _tmap(tmap), _map(map) {}
19.315 +
19.316 + virtual void copy(const Digraph& digraph, const RefMap& refMap) {
19.317 + typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
19.318 + for (ItemIt it(digraph); it != INVALID; ++it) {
19.319 + _tmap.set(refMap[it], _map[it]);
19.320 + }
19.321 + }
19.322 +
19.323 + private:
19.324 + ToMap& _tmap;
19.325 + const FromMap& _map;
19.326 + };
19.327 +
19.328 + template <typename Digraph, typename Item, typename RefMap, typename It>
19.329 + class ItemCopy : public MapCopyBase<Digraph, Item, RefMap> {
19.330 + public:
19.331 +
19.332 + ItemCopy(It& it, const Item& item) : _it(it), _item(item) {}
19.333 +
19.334 + virtual void copy(const Digraph&, const RefMap& refMap) {
19.335 + _it = refMap[_item];
19.336 + }
19.337 +
19.338 + private:
19.339 + It& _it;
19.340 + Item _item;
19.341 + };
19.342 +
19.343 + template <typename Digraph, typename Item, typename RefMap, typename Ref>
19.344 + class RefCopy : public MapCopyBase<Digraph, Item, RefMap> {
19.345 + public:
19.346 +
19.347 + RefCopy(Ref& map) : _map(map) {}
19.348 +
19.349 + virtual void copy(const Digraph& digraph, const RefMap& refMap) {
19.350 + typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
19.351 + for (ItemIt it(digraph); it != INVALID; ++it) {
19.352 + _map.set(it, refMap[it]);
19.353 + }
19.354 + }
19.355 +
19.356 + private:
19.357 + Ref& _map;
19.358 + };
19.359 +
19.360 + template <typename Digraph, typename Item, typename RefMap,
19.361 + typename CrossRef>
19.362 + class CrossRefCopy : public MapCopyBase<Digraph, Item, RefMap> {
19.363 + public:
19.364 +
19.365 + CrossRefCopy(CrossRef& cmap) : _cmap(cmap) {}
19.366 +
19.367 + virtual void copy(const Digraph& digraph, const RefMap& refMap) {
19.368 + typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
19.369 + for (ItemIt it(digraph); it != INVALID; ++it) {
19.370 + _cmap.set(refMap[it], it);
19.371 + }
19.372 + }
19.373 +
19.374 + private:
19.375 + CrossRef& _cmap;
19.376 + };
19.377 +
19.378 + template <typename Digraph, typename Enable = void>
19.379 + struct DigraphCopySelector {
19.380 + template <typename From, typename NodeRefMap, typename ArcRefMap>
19.381 + static void copy(Digraph &to, const From& from,
19.382 + NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) {
19.383 + for (typename From::NodeIt it(from); it != INVALID; ++it) {
19.384 + nodeRefMap[it] = to.addNode();
19.385 + }
19.386 + for (typename From::ArcIt it(from); it != INVALID; ++it) {
19.387 + arcRefMap[it] = to.addArc(nodeRefMap[from.source(it)],
19.388 + nodeRefMap[from.target(it)]);
19.389 + }
19.390 + }
19.391 + };
19.392 +
19.393 + template <typename Digraph>
19.394 + struct DigraphCopySelector<
19.395 + Digraph,
19.396 + typename enable_if<typename Digraph::BuildTag, void>::type>
19.397 + {
19.398 + template <typename From, typename NodeRefMap, typename ArcRefMap>
19.399 + static void copy(Digraph &to, const From& from,
19.400 + NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) {
19.401 + to.build(from, nodeRefMap, arcRefMap);
19.402 + }
19.403 + };
19.404 +
19.405 + template <typename Graph, typename Enable = void>
19.406 + struct GraphCopySelector {
19.407 + template <typename From, typename NodeRefMap, typename EdgeRefMap>
19.408 + static void copy(Graph &to, const From& from,
19.409 + NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
19.410 + for (typename From::NodeIt it(from); it != INVALID; ++it) {
19.411 + nodeRefMap[it] = to.addNode();
19.412 + }
19.413 + for (typename From::EdgeIt it(from); it != INVALID; ++it) {
19.414 + edgeRefMap[it] = to.addEdge(nodeRefMap[from.u(it)],
19.415 + nodeRefMap[from.v(it)]);
19.416 + }
19.417 + }
19.418 + };
19.419 +
19.420 + template <typename Graph>
19.421 + struct GraphCopySelector<
19.422 + Graph,
19.423 + typename enable_if<typename Graph::BuildTag, void>::type>
19.424 + {
19.425 + template <typename From, typename NodeRefMap, typename EdgeRefMap>
19.426 + static void copy(Graph &to, const From& from,
19.427 + NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
19.428 + to.build(from, nodeRefMap, edgeRefMap);
19.429 + }
19.430 + };
19.431 +
19.432 + }
19.433 +
19.434 + /// \brief Class to copy a digraph.
19.435 + ///
19.436 + /// Class to copy a digraph to another digraph (duplicate a digraph). The
19.437 + /// simplest way of using it is through the \c copyDigraph() function.
19.438 + ///
19.439 + /// This class not just make a copy of a graph, but it can create
19.440 + /// references and cross references between the nodes and arcs of
19.441 + /// the two graphs, it can copy maps for use with the newly created
19.442 + /// graph and copy nodes and arcs.
19.443 + ///
19.444 + /// To make a copy from a graph, first an instance of DigraphCopy
19.445 + /// should be created, then the data belongs to the graph should
19.446 + /// assigned to copy. In the end, the \c run() member should be
19.447 + /// called.
19.448 + ///
19.449 + /// The next code copies a graph with several data:
19.450 + ///\code
19.451 + /// DigraphCopy<NewGraph, OrigGraph> dc(new_graph, orig_graph);
19.452 + /// // create a reference for the nodes
19.453 + /// OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph);
19.454 + /// dc.nodeRef(nr);
19.455 + /// // create a cross reference (inverse) for the arcs
19.456 + /// NewGraph::ArcMap<OrigGraph::Arc> acr(new_graph);
19.457 + /// dc.arcCrossRef(acr);
19.458 + /// // copy an arc map
19.459 + /// OrigGraph::ArcMap<double> oamap(orig_graph);
19.460 + /// NewGraph::ArcMap<double> namap(new_graph);
19.461 + /// dc.arcMap(namap, oamap);
19.462 + /// // copy a node
19.463 + /// OrigGraph::Node on;
19.464 + /// NewGraph::Node nn;
19.465 + /// dc.node(nn, on);
19.466 + /// // Executions of copy
19.467 + /// dc.run();
19.468 + ///\endcode
19.469 + template <typename To, typename From>
19.470 + class DigraphCopy {
19.471 + private:
19.472 +
19.473 + typedef typename From::Node Node;
19.474 + typedef typename From::NodeIt NodeIt;
19.475 + typedef typename From::Arc Arc;
19.476 + typedef typename From::ArcIt ArcIt;
19.477 +
19.478 + typedef typename To::Node TNode;
19.479 + typedef typename To::Arc TArc;
19.480 +
19.481 + typedef typename From::template NodeMap<TNode> NodeRefMap;
19.482 + typedef typename From::template ArcMap<TArc> ArcRefMap;
19.483 +
19.484 +
19.485 + public:
19.486 +
19.487 +
19.488 + /// \brief Constructor for the DigraphCopy.
19.489 + ///
19.490 + /// It copies the content of the \c _from digraph into the
19.491 + /// \c _to digraph.
19.492 + DigraphCopy(To& to, const From& from)
19.493 + : _from(from), _to(to) {}
19.494 +
19.495 + /// \brief Destructor of the DigraphCopy
19.496 + ///
19.497 + /// Destructor of the DigraphCopy
19.498 + ~DigraphCopy() {
19.499 + for (int i = 0; i < int(_node_maps.size()); ++i) {
19.500 + delete _node_maps[i];
19.501 + }
19.502 + for (int i = 0; i < int(_arc_maps.size()); ++i) {
19.503 + delete _arc_maps[i];
19.504 + }
19.505 +
19.506 + }
19.507 +
19.508 + /// \brief Copies the node references into the given map.
19.509 + ///
19.510 + /// Copies the node references into the given map. The parameter
19.511 + /// should be a map, which key type is the Node type of the source
19.512 + /// graph, while the value type is the Node type of the
19.513 + /// destination graph.
19.514 + template <typename NodeRef>
19.515 + DigraphCopy& nodeRef(NodeRef& map) {
19.516 + _node_maps.push_back(new _core_bits::RefCopy<From, Node,
19.517 + NodeRefMap, NodeRef>(map));
19.518 + return *this;
19.519 + }
19.520 +
19.521 + /// \brief Copies the node cross references into the given map.
19.522 + ///
19.523 + /// Copies the node cross references (reverse references) into
19.524 + /// the given map. The parameter should be a map, which key type
19.525 + /// is the Node type of the destination graph, while the value type is
19.526 + /// the Node type of the source graph.
19.527 + template <typename NodeCrossRef>
19.528 + DigraphCopy& nodeCrossRef(NodeCrossRef& map) {
19.529 + _node_maps.push_back(new _core_bits::CrossRefCopy<From, Node,
19.530 + NodeRefMap, NodeCrossRef>(map));
19.531 + return *this;
19.532 + }
19.533 +
19.534 + /// \brief Make copy of the given map.
19.535 + ///
19.536 + /// Makes copy of the given map for the newly created digraph.
19.537 + /// The new map's key type is the destination graph's node type,
19.538 + /// and the copied map's key type is the source graph's node type.
19.539 + template <typename ToMap, typename FromMap>
19.540 + DigraphCopy& nodeMap(ToMap& tmap, const FromMap& map) {
19.541 + _node_maps.push_back(new _core_bits::MapCopy<From, Node,
19.542 + NodeRefMap, ToMap, FromMap>(tmap, map));
19.543 + return *this;
19.544 + }
19.545 +
19.546 + /// \brief Make a copy of the given node.
19.547 + ///
19.548 + /// Make a copy of the given node.
19.549 + DigraphCopy& node(TNode& tnode, const Node& snode) {
19.550 + _node_maps.push_back(new _core_bits::ItemCopy<From, Node,
19.551 + NodeRefMap, TNode>(tnode, snode));
19.552 + return *this;
19.553 + }
19.554 +
19.555 + /// \brief Copies the arc references into the given map.
19.556 + ///
19.557 + /// Copies the arc references into the given map.
19.558 + template <typename ArcRef>
19.559 + DigraphCopy& arcRef(ArcRef& map) {
19.560 + _arc_maps.push_back(new _core_bits::RefCopy<From, Arc,
19.561 + ArcRefMap, ArcRef>(map));
19.562 + return *this;
19.563 + }
19.564 +
19.565 + /// \brief Copies the arc cross references into the given map.
19.566 + ///
19.567 + /// Copies the arc cross references (reverse references) into
19.568 + /// the given map.
19.569 + template <typename ArcCrossRef>
19.570 + DigraphCopy& arcCrossRef(ArcCrossRef& map) {
19.571 + _arc_maps.push_back(new _core_bits::CrossRefCopy<From, Arc,
19.572 + ArcRefMap, ArcCrossRef>(map));
19.573 + return *this;
19.574 + }
19.575 +
19.576 + /// \brief Make copy of the given map.
19.577 + ///
19.578 + /// Makes copy of the given map for the newly created digraph.
19.579 + /// The new map's key type is the to digraph's arc type,
19.580 + /// and the copied map's key type is the from digraph's arc
19.581 + /// type.
19.582 + template <typename ToMap, typename FromMap>
19.583 + DigraphCopy& arcMap(ToMap& tmap, const FromMap& map) {
19.584 + _arc_maps.push_back(new _core_bits::MapCopy<From, Arc,
19.585 + ArcRefMap, ToMap, FromMap>(tmap, map));
19.586 + return *this;
19.587 + }
19.588 +
19.589 + /// \brief Make a copy of the given arc.
19.590 + ///
19.591 + /// Make a copy of the given arc.
19.592 + DigraphCopy& arc(TArc& tarc, const Arc& sarc) {
19.593 + _arc_maps.push_back(new _core_bits::ItemCopy<From, Arc,
19.594 + ArcRefMap, TArc>(tarc, sarc));
19.595 + return *this;
19.596 + }
19.597 +
19.598 + /// \brief Executes the copies.
19.599 + ///
19.600 + /// Executes the copies.
19.601 + void run() {
19.602 + NodeRefMap nodeRefMap(_from);
19.603 + ArcRefMap arcRefMap(_from);
19.604 + _core_bits::DigraphCopySelector<To>::
19.605 + copy(_to, _from, nodeRefMap, arcRefMap);
19.606 + for (int i = 0; i < int(_node_maps.size()); ++i) {
19.607 + _node_maps[i]->copy(_from, nodeRefMap);
19.608 + }
19.609 + for (int i = 0; i < int(_arc_maps.size()); ++i) {
19.610 + _arc_maps[i]->copy(_from, arcRefMap);
19.611 + }
19.612 + }
19.613 +
19.614 + protected:
19.615 +
19.616 +
19.617 + const From& _from;
19.618 + To& _to;
19.619 +
19.620 + std::vector<_core_bits::MapCopyBase<From, Node, NodeRefMap>* >
19.621 + _node_maps;
19.622 +
19.623 + std::vector<_core_bits::MapCopyBase<From, Arc, ArcRefMap>* >
19.624 + _arc_maps;
19.625 +
19.626 + };
19.627 +
19.628 + /// \brief Copy a digraph to another digraph.
19.629 + ///
19.630 + /// Copy a digraph to another digraph. The complete usage of the
19.631 + /// function is detailed in the DigraphCopy class, but a short
19.632 + /// example shows a basic work:
19.633 + ///\code
19.634 + /// copyDigraph(trg, src).nodeRef(nr).arcCrossRef(ecr).run();
19.635 + ///\endcode
19.636 + ///
19.637 + /// After the copy the \c nr map will contain the mapping from the
19.638 + /// nodes of the \c from digraph to the nodes of the \c to digraph and
19.639 + /// \c ecr will contain the mapping from the arcs of the \c to digraph
19.640 + /// to the arcs of the \c from digraph.
19.641 + ///
19.642 + /// \see DigraphCopy
19.643 + template <typename To, typename From>
19.644 + DigraphCopy<To, From> copyDigraph(To& to, const From& from) {
19.645 + return DigraphCopy<To, From>(to, from);
19.646 + }
19.647 +
19.648 + /// \brief Class to copy a graph.
19.649 + ///
19.650 + /// Class to copy a graph to another graph (duplicate a graph). The
19.651 + /// simplest way of using it is through the \c copyGraph() function.
19.652 + ///
19.653 + /// This class not just make a copy of a graph, but it can create
19.654 + /// references and cross references between the nodes, edges and arcs of
19.655 + /// the two graphs, it can copy maps for use with the newly created
19.656 + /// graph and copy nodes, edges and arcs.
19.657 + ///
19.658 + /// To make a copy from a graph, first an instance of GraphCopy
19.659 + /// should be created, then the data belongs to the graph should
19.660 + /// assigned to copy. In the end, the \c run() member should be
19.661 + /// called.
19.662 + ///
19.663 + /// The next code copies a graph with several data:
19.664 + ///\code
19.665 + /// GraphCopy<NewGraph, OrigGraph> dc(new_graph, orig_graph);
19.666 + /// // create a reference for the nodes
19.667 + /// OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph);
19.668 + /// dc.nodeRef(nr);
19.669 + /// // create a cross reference (inverse) for the edges
19.670 + /// NewGraph::EdgeMap<OrigGraph::Arc> ecr(new_graph);
19.671 + /// dc.edgeCrossRef(ecr);
19.672 + /// // copy an arc map
19.673 + /// OrigGraph::ArcMap<double> oamap(orig_graph);
19.674 + /// NewGraph::ArcMap<double> namap(new_graph);
19.675 + /// dc.arcMap(namap, oamap);
19.676 + /// // copy a node
19.677 + /// OrigGraph::Node on;
19.678 + /// NewGraph::Node nn;
19.679 + /// dc.node(nn, on);
19.680 + /// // Executions of copy
19.681 + /// dc.run();
19.682 + ///\endcode
19.683 + template <typename To, typename From>
19.684 + class GraphCopy {
19.685 + private:
19.686 +
19.687 + typedef typename From::Node Node;
19.688 + typedef typename From::NodeIt NodeIt;
19.689 + typedef typename From::Arc Arc;
19.690 + typedef typename From::ArcIt ArcIt;
19.691 + typedef typename From::Edge Edge;
19.692 + typedef typename From::EdgeIt EdgeIt;
19.693 +
19.694 + typedef typename To::Node TNode;
19.695 + typedef typename To::Arc TArc;
19.696 + typedef typename To::Edge TEdge;
19.697 +
19.698 + typedef typename From::template NodeMap<TNode> NodeRefMap;
19.699 + typedef typename From::template EdgeMap<TEdge> EdgeRefMap;
19.700 +
19.701 + struct ArcRefMap {
19.702 + ArcRefMap(const To& to, const From& from,
19.703 + const EdgeRefMap& edge_ref, const NodeRefMap& node_ref)
19.704 + : _to(to), _from(from),
19.705 + _edge_ref(edge_ref), _node_ref(node_ref) {}
19.706 +
19.707 + typedef typename From::Arc Key;
19.708 + typedef typename To::Arc Value;
19.709 +
19.710 + Value operator[](const Key& key) const {
19.711 + bool forward = _from.u(key) != _from.v(key) ?
19.712 + _node_ref[_from.source(key)] ==
19.713 + _to.source(_to.direct(_edge_ref[key], true)) :
19.714 + _from.direction(key);
19.715 + return _to.direct(_edge_ref[key], forward);
19.716 + }
19.717 +
19.718 + const To& _to;
19.719 + const From& _from;
19.720 + const EdgeRefMap& _edge_ref;
19.721 + const NodeRefMap& _node_ref;
19.722 + };
19.723 +
19.724 +
19.725 + public:
19.726 +
19.727 +
19.728 + /// \brief Constructor for the GraphCopy.
19.729 + ///
19.730 + /// It copies the content of the \c _from graph into the
19.731 + /// \c _to graph.
19.732 + GraphCopy(To& to, const From& from)
19.733 + : _from(from), _to(to) {}
19.734 +
19.735 + /// \brief Destructor of the GraphCopy
19.736 + ///
19.737 + /// Destructor of the GraphCopy
19.738 + ~GraphCopy() {
19.739 + for (int i = 0; i < int(_node_maps.size()); ++i) {
19.740 + delete _node_maps[i];
19.741 + }
19.742 + for (int i = 0; i < int(_arc_maps.size()); ++i) {
19.743 + delete _arc_maps[i];
19.744 + }
19.745 + for (int i = 0; i < int(_edge_maps.size()); ++i) {
19.746 + delete _edge_maps[i];
19.747 + }
19.748 +
19.749 + }
19.750 +
19.751 + /// \brief Copies the node references into the given map.
19.752 + ///
19.753 + /// Copies the node references into the given map.
19.754 + template <typename NodeRef>
19.755 + GraphCopy& nodeRef(NodeRef& map) {
19.756 + _node_maps.push_back(new _core_bits::RefCopy<From, Node,
19.757 + NodeRefMap, NodeRef>(map));
19.758 + return *this;
19.759 + }
19.760 +
19.761 + /// \brief Copies the node cross references into the given map.
19.762 + ///
19.763 + /// Copies the node cross references (reverse references) into
19.764 + /// the given map.
19.765 + template <typename NodeCrossRef>
19.766 + GraphCopy& nodeCrossRef(NodeCrossRef& map) {
19.767 + _node_maps.push_back(new _core_bits::CrossRefCopy<From, Node,
19.768 + NodeRefMap, NodeCrossRef>(map));
19.769 + return *this;
19.770 + }
19.771 +
19.772 + /// \brief Make copy of the given map.
19.773 + ///
19.774 + /// Makes copy of the given map for the newly created graph.
19.775 + /// The new map's key type is the to graph's node type,
19.776 + /// and the copied map's key type is the from graph's node
19.777 + /// type.
19.778 + template <typename ToMap, typename FromMap>
19.779 + GraphCopy& nodeMap(ToMap& tmap, const FromMap& map) {
19.780 + _node_maps.push_back(new _core_bits::MapCopy<From, Node,
19.781 + NodeRefMap, ToMap, FromMap>(tmap, map));
19.782 + return *this;
19.783 + }
19.784 +
19.785 + /// \brief Make a copy of the given node.
19.786 + ///
19.787 + /// Make a copy of the given node.
19.788 + GraphCopy& node(TNode& tnode, const Node& snode) {
19.789 + _node_maps.push_back(new _core_bits::ItemCopy<From, Node,
19.790 + NodeRefMap, TNode>(tnode, snode));
19.791 + return *this;
19.792 + }
19.793 +
19.794 + /// \brief Copies the arc references into the given map.
19.795 + ///
19.796 + /// Copies the arc references into the given map.
19.797 + template <typename ArcRef>
19.798 + GraphCopy& arcRef(ArcRef& map) {
19.799 + _arc_maps.push_back(new _core_bits::RefCopy<From, Arc,
19.800 + ArcRefMap, ArcRef>(map));
19.801 + return *this;
19.802 + }
19.803 +
19.804 + /// \brief Copies the arc cross references into the given map.
19.805 + ///
19.806 + /// Copies the arc cross references (reverse references) into
19.807 + /// the given map.
19.808 + template <typename ArcCrossRef>
19.809 + GraphCopy& arcCrossRef(ArcCrossRef& map) {
19.810 + _arc_maps.push_back(new _core_bits::CrossRefCopy<From, Arc,
19.811 + ArcRefMap, ArcCrossRef>(map));
19.812 + return *this;
19.813 + }
19.814 +
19.815 + /// \brief Make copy of the given map.
19.816 + ///
19.817 + /// Makes copy of the given map for the newly created graph.
19.818 + /// The new map's key type is the to graph's arc type,
19.819 + /// and the copied map's key type is the from graph's arc
19.820 + /// type.
19.821 + template <typename ToMap, typename FromMap>
19.822 + GraphCopy& arcMap(ToMap& tmap, const FromMap& map) {
19.823 + _arc_maps.push_back(new _core_bits::MapCopy<From, Arc,
19.824 + ArcRefMap, ToMap, FromMap>(tmap, map));
19.825 + return *this;
19.826 + }
19.827 +
19.828 + /// \brief Make a copy of the given arc.
19.829 + ///
19.830 + /// Make a copy of the given arc.
19.831 + GraphCopy& arc(TArc& tarc, const Arc& sarc) {
19.832 + _arc_maps.push_back(new _core_bits::ItemCopy<From, Arc,
19.833 + ArcRefMap, TArc>(tarc, sarc));
19.834 + return *this;
19.835 + }
19.836 +
19.837 + /// \brief Copies the edge references into the given map.
19.838 + ///
19.839 + /// Copies the edge references into the given map.
19.840 + template <typename EdgeRef>
19.841 + GraphCopy& edgeRef(EdgeRef& map) {
19.842 + _edge_maps.push_back(new _core_bits::RefCopy<From, Edge,
19.843 + EdgeRefMap, EdgeRef>(map));
19.844 + return *this;
19.845 + }
19.846 +
19.847 + /// \brief Copies the edge cross references into the given map.
19.848 + ///
19.849 + /// Copies the edge cross references (reverse
19.850 + /// references) into the given map.
19.851 + template <typename EdgeCrossRef>
19.852 + GraphCopy& edgeCrossRef(EdgeCrossRef& map) {
19.853 + _edge_maps.push_back(new _core_bits::CrossRefCopy<From,
19.854 + Edge, EdgeRefMap, EdgeCrossRef>(map));
19.855 + return *this;
19.856 + }
19.857 +
19.858 + /// \brief Make copy of the given map.
19.859 + ///
19.860 + /// Makes copy of the given map for the newly created graph.
19.861 + /// The new map's key type is the to graph's edge type,
19.862 + /// and the copied map's key type is the from graph's edge
19.863 + /// type.
19.864 + template <typename ToMap, typename FromMap>
19.865 + GraphCopy& edgeMap(ToMap& tmap, const FromMap& map) {
19.866 + _edge_maps.push_back(new _core_bits::MapCopy<From, Edge,
19.867 + EdgeRefMap, ToMap, FromMap>(tmap, map));
19.868 + return *this;
19.869 + }
19.870 +
19.871 + /// \brief Make a copy of the given edge.
19.872 + ///
19.873 + /// Make a copy of the given edge.
19.874 + GraphCopy& edge(TEdge& tedge, const Edge& sedge) {
19.875 + _edge_maps.push_back(new _core_bits::ItemCopy<From, Edge,
19.876 + EdgeRefMap, TEdge>(tedge, sedge));
19.877 + return *this;
19.878 + }
19.879 +
19.880 + /// \brief Executes the copies.
19.881 + ///
19.882 + /// Executes the copies.
19.883 + void run() {
19.884 + NodeRefMap nodeRefMap(_from);
19.885 + EdgeRefMap edgeRefMap(_from);
19.886 + ArcRefMap arcRefMap(_to, _from, edgeRefMap, nodeRefMap);
19.887 + _core_bits::GraphCopySelector<To>::
19.888 + copy(_to, _from, nodeRefMap, edgeRefMap);
19.889 + for (int i = 0; i < int(_node_maps.size()); ++i) {
19.890 + _node_maps[i]->copy(_from, nodeRefMap);
19.891 + }
19.892 + for (int i = 0; i < int(_edge_maps.size()); ++i) {
19.893 + _edge_maps[i]->copy(_from, edgeRefMap);
19.894 + }
19.895 + for (int i = 0; i < int(_arc_maps.size()); ++i) {
19.896 + _arc_maps[i]->copy(_from, arcRefMap);
19.897 + }
19.898 + }
19.899 +
19.900 + private:
19.901 +
19.902 + const From& _from;
19.903 + To& _to;
19.904 +
19.905 + std::vector<_core_bits::MapCopyBase<From, Node, NodeRefMap>* >
19.906 + _node_maps;
19.907 +
19.908 + std::vector<_core_bits::MapCopyBase<From, Arc, ArcRefMap>* >
19.909 + _arc_maps;
19.910 +
19.911 + std::vector<_core_bits::MapCopyBase<From, Edge, EdgeRefMap>* >
19.912 + _edge_maps;
19.913 +
19.914 + };
19.915 +
19.916 + /// \brief Copy a graph to another graph.
19.917 + ///
19.918 + /// Copy a graph to another graph. The complete usage of the
19.919 + /// function is detailed in the GraphCopy class, but a short
19.920 + /// example shows a basic work:
19.921 + ///\code
19.922 + /// copyGraph(trg, src).nodeRef(nr).arcCrossRef(ecr).run();
19.923 + ///\endcode
19.924 + ///
19.925 + /// After the copy the \c nr map will contain the mapping from the
19.926 + /// nodes of the \c from graph to the nodes of the \c to graph and
19.927 + /// \c ecr will contain the mapping from the arcs of the \c to graph
19.928 + /// to the arcs of the \c from graph.
19.929 + ///
19.930 + /// \see GraphCopy
19.931 + template <typename To, typename From>
19.932 + GraphCopy<To, From>
19.933 + copyGraph(To& to, const From& from) {
19.934 + return GraphCopy<To, From>(to, from);
19.935 + }
19.936 +
19.937 + namespace _core_bits {
19.938 +
19.939 + template <typename Graph, typename Enable = void>
19.940 + struct FindArcSelector {
19.941 + typedef typename Graph::Node Node;
19.942 + typedef typename Graph::Arc Arc;
19.943 + static Arc find(const Graph &g, Node u, Node v, Arc e) {
19.944 + if (e == INVALID) {
19.945 + g.firstOut(e, u);
19.946 + } else {
19.947 + g.nextOut(e);
19.948 + }
19.949 + while (e != INVALID && g.target(e) != v) {
19.950 + g.nextOut(e);
19.951 + }
19.952 + return e;
19.953 + }
19.954 + };
19.955 +
19.956 + template <typename Graph>
19.957 + struct FindArcSelector<
19.958 + Graph,
19.959 + typename enable_if<typename Graph::FindEdgeTag, void>::type>
19.960 + {
19.961 + typedef typename Graph::Node Node;
19.962 + typedef typename Graph::Arc Arc;
19.963 + static Arc find(const Graph &g, Node u, Node v, Arc prev) {
19.964 + return g.findArc(u, v, prev);
19.965 + }
19.966 + };
19.967 + }
19.968 +
19.969 + /// \brief Finds an arc between two nodes of a graph.
19.970 + ///
19.971 + /// Finds an arc from node \c u to node \c v in graph \c g.
19.972 + ///
19.973 + /// If \c prev is \ref INVALID (this is the default value), then
19.974 + /// it finds the first arc from \c u to \c v. Otherwise it looks for
19.975 + /// the next arc from \c u to \c v after \c prev.
19.976 + /// \return The found arc or \ref INVALID if there is no such an arc.
19.977 + ///
19.978 + /// Thus you can iterate through each arc from \c u to \c v as it follows.
19.979 + ///\code
19.980 + /// for(Arc e=findArc(g,u,v);e!=INVALID;e=findArc(g,u,v,e)) {
19.981 + /// ...
19.982 + /// }
19.983 + ///\endcode
19.984 + ///
19.985 + ///\sa ArcLookUp
19.986 + ///\sa AllArcLookUp
19.987 + ///\sa DynArcLookUp
19.988 + ///\sa ConArcIt
19.989 + template <typename Graph>
19.990 + inline typename Graph::Arc
19.991 + findArc(const Graph &g, typename Graph::Node u, typename Graph::Node v,
19.992 + typename Graph::Arc prev = INVALID) {
19.993 + return _core_bits::FindArcSelector<Graph>::find(g, u, v, prev);
19.994 + }
19.995 +
19.996 + /// \brief Iterator for iterating on arcs connected the same nodes.
19.997 + ///
19.998 + /// Iterator for iterating on arcs connected the same nodes. It is
19.999 + /// higher level interface for the findArc() function. You can
19.1000 + /// use it the following way:
19.1001 + ///\code
19.1002 + /// for (ConArcIt<Graph> it(g, src, trg); it != INVALID; ++it) {
19.1003 + /// ...
19.1004 + /// }
19.1005 + ///\endcode
19.1006 + ///
19.1007 + ///\sa findArc()
19.1008 + ///\sa ArcLookUp
19.1009 + ///\sa AllArcLookUp
19.1010 + ///\sa DynArcLookUp
19.1011 + template <typename _Graph>
19.1012 + class ConArcIt : public _Graph::Arc {
19.1013 + public:
19.1014 +
19.1015 + typedef _Graph Graph;
19.1016 + typedef typename Graph::Arc Parent;
19.1017 +
19.1018 + typedef typename Graph::Arc Arc;
19.1019 + typedef typename Graph::Node Node;
19.1020 +
19.1021 + /// \brief Constructor.
19.1022 + ///
19.1023 + /// Construct a new ConArcIt iterating on the arcs which
19.1024 + /// connects the \c u and \c v node.
19.1025 + ConArcIt(const Graph& g, Node u, Node v) : _graph(g) {
19.1026 + Parent::operator=(findArc(_graph, u, v));
19.1027 + }
19.1028 +
19.1029 + /// \brief Constructor.
19.1030 + ///
19.1031 + /// Construct a new ConArcIt which continues the iterating from
19.1032 + /// the \c e arc.
19.1033 + ConArcIt(const Graph& g, Arc a) : Parent(a), _graph(g) {}
19.1034 +
19.1035 + /// \brief Increment operator.
19.1036 + ///
19.1037 + /// It increments the iterator and gives back the next arc.
19.1038 + ConArcIt& operator++() {
19.1039 + Parent::operator=(findArc(_graph, _graph.source(*this),
19.1040 + _graph.target(*this), *this));
19.1041 + return *this;
19.1042 + }
19.1043 + private:
19.1044 + const Graph& _graph;
19.1045 + };
19.1046 +
19.1047 + namespace _core_bits {
19.1048 +
19.1049 + template <typename Graph, typename Enable = void>
19.1050 + struct FindEdgeSelector {
19.1051 + typedef typename Graph::Node Node;
19.1052 + typedef typename Graph::Edge Edge;
19.1053 + static Edge find(const Graph &g, Node u, Node v, Edge e) {
19.1054 + bool b;
19.1055 + if (u != v) {
19.1056 + if (e == INVALID) {
19.1057 + g.firstInc(e, b, u);
19.1058 + } else {
19.1059 + b = g.u(e) == u;
19.1060 + g.nextInc(e, b);
19.1061 + }
19.1062 + while (e != INVALID && (b ? g.v(e) : g.u(e)) != v) {
19.1063 + g.nextInc(e, b);
19.1064 + }
19.1065 + } else {
19.1066 + if (e == INVALID) {
19.1067 + g.firstInc(e, b, u);
19.1068 + } else {
19.1069 + b = true;
19.1070 + g.nextInc(e, b);
19.1071 + }
19.1072 + while (e != INVALID && (!b || g.v(e) != v)) {
19.1073 + g.nextInc(e, b);
19.1074 + }
19.1075 + }
19.1076 + return e;
19.1077 + }
19.1078 + };
19.1079 +
19.1080 + template <typename Graph>
19.1081 + struct FindEdgeSelector<
19.1082 + Graph,
19.1083 + typename enable_if<typename Graph::FindEdgeTag, void>::type>
19.1084 + {
19.1085 + typedef typename Graph::Node Node;
19.1086 + typedef typename Graph::Edge Edge;
19.1087 + static Edge find(const Graph &g, Node u, Node v, Edge prev) {
19.1088 + return g.findEdge(u, v, prev);
19.1089 + }
19.1090 + };
19.1091 + }
19.1092 +
19.1093 + /// \brief Finds an edge between two nodes of a graph.
19.1094 + ///
19.1095 + /// Finds an edge from node \c u to node \c v in graph \c g.
19.1096 + /// If the node \c u and node \c v is equal then each loop edge
19.1097 + /// will be enumerated once.
19.1098 + ///
19.1099 + /// If \c prev is \ref INVALID (this is the default value), then
19.1100 + /// it finds the first arc from \c u to \c v. Otherwise it looks for
19.1101 + /// the next arc from \c u to \c v after \c prev.
19.1102 + /// \return The found arc or \ref INVALID if there is no such an arc.
19.1103 + ///
19.1104 + /// Thus you can iterate through each arc from \c u to \c v as it follows.
19.1105 + ///\code
19.1106 + /// for(Edge e = findEdge(g,u,v); e != INVALID;
19.1107 + /// e = findEdge(g,u,v,e)) {
19.1108 + /// ...
19.1109 + /// }
19.1110 + ///\endcode
19.1111 + ///
19.1112 + ///\sa ConEdgeIt
19.1113 +
19.1114 + template <typename Graph>
19.1115 + inline typename Graph::Edge
19.1116 + findEdge(const Graph &g, typename Graph::Node u, typename Graph::Node v,
19.1117 + typename Graph::Edge p = INVALID) {
19.1118 + return _core_bits::FindEdgeSelector<Graph>::find(g, u, v, p);
19.1119 + }
19.1120 +
19.1121 + /// \brief Iterator for iterating on edges connected the same nodes.
19.1122 + ///
19.1123 + /// Iterator for iterating on edges connected the same nodes. It is
19.1124 + /// higher level interface for the findEdge() function. You can
19.1125 + /// use it the following way:
19.1126 + ///\code
19.1127 + /// for (ConEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) {
19.1128 + /// ...
19.1129 + /// }
19.1130 + ///\endcode
19.1131 + ///
19.1132 + ///\sa findEdge()
19.1133 + template <typename _Graph>
19.1134 + class ConEdgeIt : public _Graph::Edge {
19.1135 + public:
19.1136 +
19.1137 + typedef _Graph Graph;
19.1138 + typedef typename Graph::Edge Parent;
19.1139 +
19.1140 + typedef typename Graph::Edge Edge;
19.1141 + typedef typename Graph::Node Node;
19.1142 +
19.1143 + /// \brief Constructor.
19.1144 + ///
19.1145 + /// Construct a new ConEdgeIt iterating on the edges which
19.1146 + /// connects the \c u and \c v node.
19.1147 + ConEdgeIt(const Graph& g, Node u, Node v) : _graph(g) {
19.1148 + Parent::operator=(findEdge(_graph, u, v));
19.1149 + }
19.1150 +
19.1151 + /// \brief Constructor.
19.1152 + ///
19.1153 + /// Construct a new ConEdgeIt which continues the iterating from
19.1154 + /// the \c e edge.
19.1155 + ConEdgeIt(const Graph& g, Edge e) : Parent(e), _graph(g) {}
19.1156 +
19.1157 + /// \brief Increment operator.
19.1158 + ///
19.1159 + /// It increments the iterator and gives back the next edge.
19.1160 + ConEdgeIt& operator++() {
19.1161 + Parent::operator=(findEdge(_graph, _graph.u(*this),
19.1162 + _graph.v(*this), *this));
19.1163 + return *this;
19.1164 + }
19.1165 + private:
19.1166 + const Graph& _graph;
19.1167 + };
19.1168 +
19.1169 +
19.1170 + ///Dynamic arc look up between given endpoints.
19.1171 +
19.1172 + ///Using this class, you can find an arc in a digraph from a given
19.1173 + ///source to a given target in amortized time <em>O(log d)</em>,
19.1174 + ///where <em>d</em> is the out-degree of the source node.
19.1175 + ///
19.1176 + ///It is possible to find \e all parallel arcs between two nodes with
19.1177 + ///the \c findFirst() and \c findNext() members.
19.1178 + ///
19.1179 + ///See the \ref ArcLookUp and \ref AllArcLookUp classes if your
19.1180 + ///digraph is not changed so frequently.
19.1181 + ///
19.1182 + ///This class uses a self-adjusting binary search tree, Sleator's
19.1183 + ///and Tarjan's Splay tree for guarantee the logarithmic amortized
19.1184 + ///time bound for arc lookups. This class also guarantees the
19.1185 + ///optimal time bound in a constant factor for any distribution of
19.1186 + ///queries.
19.1187 + ///
19.1188 + ///\tparam G The type of the underlying digraph.
19.1189 + ///
19.1190 + ///\sa ArcLookUp
19.1191 + ///\sa AllArcLookUp
19.1192 + template<class G>
19.1193 + class DynArcLookUp
19.1194 + : protected ItemSetTraits<G, typename G::Arc>::ItemNotifier::ObserverBase
19.1195 + {
19.1196 + public:
19.1197 + typedef typename ItemSetTraits<G, typename G::Arc>
19.1198 + ::ItemNotifier::ObserverBase Parent;
19.1199 +
19.1200 + TEMPLATE_DIGRAPH_TYPEDEFS(G);
19.1201 + typedef G Digraph;
19.1202 +
19.1203 + protected:
19.1204 +
19.1205 + class AutoNodeMap : public ItemSetTraits<G, Node>::template Map<Arc>::Type {
19.1206 + public:
19.1207 +
19.1208 + typedef typename ItemSetTraits<G, Node>::template Map<Arc>::Type Parent;
19.1209 +
19.1210 + AutoNodeMap(const G& digraph) : Parent(digraph, INVALID) {}
19.1211 +
19.1212 + virtual void add(const Node& node) {
19.1213 + Parent::add(node);
19.1214 + Parent::set(node, INVALID);
19.1215 + }
19.1216 +
19.1217 + virtual void add(const std::vector<Node>& nodes) {
19.1218 + Parent::add(nodes);
19.1219 + for (int i = 0; i < int(nodes.size()); ++i) {
19.1220 + Parent::set(nodes[i], INVALID);
19.1221 + }
19.1222 + }
19.1223 +
19.1224 + virtual void build() {
19.1225 + Parent::build();
19.1226 + Node it;
19.1227 + typename Parent::Notifier* nf = Parent::notifier();
19.1228 + for (nf->first(it); it != INVALID; nf->next(it)) {
19.1229 + Parent::set(it, INVALID);
19.1230 + }
19.1231 + }
19.1232 + };
19.1233 +
19.1234 + const Digraph &_g;
19.1235 + AutoNodeMap _head;
19.1236 + typename Digraph::template ArcMap<Arc> _parent;
19.1237 + typename Digraph::template ArcMap<Arc> _left;
19.1238 + typename Digraph::template ArcMap<Arc> _right;
19.1239 +
19.1240 + class ArcLess {
19.1241 + const Digraph &g;
19.1242 + public:
19.1243 + ArcLess(const Digraph &_g) : g(_g) {}
19.1244 + bool operator()(Arc a,Arc b) const
19.1245 + {
19.1246 + return g.target(a)<g.target(b);
19.1247 + }
19.1248 + };
19.1249 +
19.1250 + public:
19.1251 +
19.1252 + ///Constructor
19.1253 +
19.1254 + ///Constructor.
19.1255 + ///
19.1256 + ///It builds up the search database.
19.1257 + DynArcLookUp(const Digraph &g)
19.1258 + : _g(g),_head(g),_parent(g),_left(g),_right(g)
19.1259 + {
19.1260 + Parent::attach(_g.notifier(typename Digraph::Arc()));
19.1261 + refresh();
19.1262 + }
19.1263 +
19.1264 + protected:
19.1265 +
19.1266 + virtual void add(const Arc& arc) {
19.1267 + insert(arc);
19.1268 + }
19.1269 +
19.1270 + virtual void add(const std::vector<Arc>& arcs) {
19.1271 + for (int i = 0; i < int(arcs.size()); ++i) {
19.1272 + insert(arcs[i]);
19.1273 + }
19.1274 + }
19.1275 +
19.1276 + virtual void erase(const Arc& arc) {
19.1277 + remove(arc);
19.1278 + }
19.1279 +
19.1280 + virtual void erase(const std::vector<Arc>& arcs) {
19.1281 + for (int i = 0; i < int(arcs.size()); ++i) {
19.1282 + remove(arcs[i]);
19.1283 + }
19.1284 + }
19.1285 +
19.1286 + virtual void build() {
19.1287 + refresh();
19.1288 + }
19.1289 +
19.1290 + virtual void clear() {
19.1291 + for(NodeIt n(_g);n!=INVALID;++n) {
19.1292 + _head.set(n, INVALID);
19.1293 + }
19.1294 + }
19.1295 +
19.1296 + void insert(Arc arc) {
19.1297 + Node s = _g.source(arc);
19.1298 + Node t = _g.target(arc);
19.1299 + _left.set(arc, INVALID);
19.1300 + _right.set(arc, INVALID);
19.1301 +
19.1302 + Arc e = _head[s];
19.1303 + if (e == INVALID) {
19.1304 + _head.set(s, arc);
19.1305 + _parent.set(arc, INVALID);
19.1306 + return;
19.1307 + }
19.1308 + while (true) {
19.1309 + if (t < _g.target(e)) {
19.1310 + if (_left[e] == INVALID) {
19.1311 + _left.set(e, arc);
19.1312 + _parent.set(arc, e);
19.1313 + splay(arc);
19.1314 + return;
19.1315 + } else {
19.1316 + e = _left[e];
19.1317 + }
19.1318 + } else {
19.1319 + if (_right[e] == INVALID) {
19.1320 + _right.set(e, arc);
19.1321 + _parent.set(arc, e);
19.1322 + splay(arc);
19.1323 + return;
19.1324 + } else {
19.1325 + e = _right[e];
19.1326 + }
19.1327 + }
19.1328 + }
19.1329 + }
19.1330 +
19.1331 + void remove(Arc arc) {
19.1332 + if (_left[arc] == INVALID) {
19.1333 + if (_right[arc] != INVALID) {
19.1334 + _parent.set(_right[arc], _parent[arc]);
19.1335 + }
19.1336 + if (_parent[arc] != INVALID) {
19.1337 + if (_left[_parent[arc]] == arc) {
19.1338 + _left.set(_parent[arc], _right[arc]);
19.1339 + } else {
19.1340 + _right.set(_parent[arc], _right[arc]);
19.1341 + }
19.1342 + } else {
19.1343 + _head.set(_g.source(arc), _right[arc]);
19.1344 + }
19.1345 + } else if (_right[arc] == INVALID) {
19.1346 + _parent.set(_left[arc], _parent[arc]);
19.1347 + if (_parent[arc] != INVALID) {
19.1348 + if (_left[_parent[arc]] == arc) {
19.1349 + _left.set(_parent[arc], _left[arc]);
19.1350 + } else {
19.1351 + _right.set(_parent[arc], _left[arc]);
19.1352 + }
19.1353 + } else {
19.1354 + _head.set(_g.source(arc), _left[arc]);
19.1355 + }
19.1356 + } else {
19.1357 + Arc e = _left[arc];
19.1358 + if (_right[e] != INVALID) {
19.1359 + e = _right[e];
19.1360 + while (_right[e] != INVALID) {
19.1361 + e = _right[e];
19.1362 + }
19.1363 + Arc s = _parent[e];
19.1364 + _right.set(_parent[e], _left[e]);
19.1365 + if (_left[e] != INVALID) {
19.1366 + _parent.set(_left[e], _parent[e]);
19.1367 + }
19.1368 +
19.1369 + _left.set(e, _left[arc]);
19.1370 + _parent.set(_left[arc], e);
19.1371 + _right.set(e, _right[arc]);
19.1372 + _parent.set(_right[arc], e);
19.1373 +
19.1374 + _parent.set(e, _parent[arc]);
19.1375 + if (_parent[arc] != INVALID) {
19.1376 + if (_left[_parent[arc]] == arc) {
19.1377 + _left.set(_parent[arc], e);
19.1378 + } else {
19.1379 + _right.set(_parent[arc], e);
19.1380 + }
19.1381 + }
19.1382 + splay(s);
19.1383 + } else {
19.1384 + _right.set(e, _right[arc]);
19.1385 + _parent.set(_right[arc], e);
19.1386 +
19.1387 + if (_parent[arc] != INVALID) {
19.1388 + if (_left[_parent[arc]] == arc) {
19.1389 + _left.set(_parent[arc], e);
19.1390 + } else {
19.1391 + _right.set(_parent[arc], e);
19.1392 + }
19.1393 + } else {
19.1394 + _head.set(_g.source(arc), e);
19.1395 + }
19.1396 + }
19.1397 + }
19.1398 + }
19.1399 +
19.1400 + Arc refreshRec(std::vector<Arc> &v,int a,int b)
19.1401 + {
19.1402 + int m=(a+b)/2;
19.1403 + Arc me=v[m];
19.1404 + if (a < m) {
19.1405 + Arc left = refreshRec(v,a,m-1);
19.1406 + _left.set(me, left);
19.1407 + _parent.set(left, me);
19.1408 + } else {
19.1409 + _left.set(me, INVALID);
19.1410 + }
19.1411 + if (m < b) {
19.1412 + Arc right = refreshRec(v,m+1,b);
19.1413 + _right.set(me, right);
19.1414 + _parent.set(right, me);
19.1415 + } else {
19.1416 + _right.set(me, INVALID);
19.1417 + }
19.1418 + return me;
19.1419 + }
19.1420 +
19.1421 + void refresh() {
19.1422 + for(NodeIt n(_g);n!=INVALID;++n) {
19.1423 + std::vector<Arc> v;
19.1424 + for(OutArcIt e(_g,n);e!=INVALID;++e) v.push_back(e);
19.1425 + if(v.size()) {
19.1426 + std::sort(v.begin(),v.end(),ArcLess(_g));
19.1427 + Arc head = refreshRec(v,0,v.size()-1);
19.1428 + _head.set(n, head);
19.1429 + _parent.set(head, INVALID);
19.1430 + }
19.1431 + else _head.set(n, INVALID);
19.1432 + }
19.1433 + }
19.1434 +
19.1435 + void zig(Arc v) {
19.1436 + Arc w = _parent[v];
19.1437 + _parent.set(v, _parent[w]);
19.1438 + _parent.set(w, v);
19.1439 + _left.set(w, _right[v]);
19.1440 + _right.set(v, w);
19.1441 + if (_parent[v] != INVALID) {
19.1442 + if (_right[_parent[v]] == w) {
19.1443 + _right.set(_parent[v], v);
19.1444 + } else {
19.1445 + _left.set(_parent[v], v);
19.1446 + }
19.1447 + }
19.1448 + if (_left[w] != INVALID){
19.1449 + _parent.set(_left[w], w);
19.1450 + }
19.1451 + }
19.1452 +
19.1453 + void zag(Arc v) {
19.1454 + Arc w = _parent[v];
19.1455 + _parent.set(v, _parent[w]);
19.1456 + _parent.set(w, v);
19.1457 + _right.set(w, _left[v]);
19.1458 + _left.set(v, w);
19.1459 + if (_parent[v] != INVALID){
19.1460 + if (_left[_parent[v]] == w) {
19.1461 + _left.set(_parent[v], v);
19.1462 + } else {
19.1463 + _right.set(_parent[v], v);
19.1464 + }
19.1465 + }
19.1466 + if (_right[w] != INVALID){
19.1467 + _parent.set(_right[w], w);
19.1468 + }
19.1469 + }
19.1470 +
19.1471 + void splay(Arc v) {
19.1472 + while (_parent[v] != INVALID) {
19.1473 + if (v == _left[_parent[v]]) {
19.1474 + if (_parent[_parent[v]] == INVALID) {
19.1475 + zig(v);
19.1476 + } else {
19.1477 + if (_parent[v] == _left[_parent[_parent[v]]]) {
19.1478 + zig(_parent[v]);
19.1479 + zig(v);
19.1480 + } else {
19.1481 + zig(v);
19.1482 + zag(v);
19.1483 + }
19.1484 + }
19.1485 + } else {
19.1486 + if (_parent[_parent[v]] == INVALID) {
19.1487 + zag(v);
19.1488 + } else {
19.1489 + if (_parent[v] == _left[_parent[_parent[v]]]) {
19.1490 + zag(v);
19.1491 + zig(v);
19.1492 + } else {
19.1493 + zag(_parent[v]);
19.1494 + zag(v);
19.1495 + }
19.1496 + }
19.1497 + }
19.1498 + }
19.1499 + _head[_g.source(v)] = v;
19.1500 + }
19.1501 +
19.1502 +
19.1503 + public:
19.1504 +
19.1505 + ///Find an arc between two nodes.
19.1506 +
19.1507 + ///Find an arc between two nodes in time <em>O(</em>log<em>d)</em>, where
19.1508 + /// <em>d</em> is the number of outgoing arcs of \c s.
19.1509 + ///\param s The source node
19.1510 + ///\param t The target node
19.1511 + ///\return An arc from \c s to \c t if there exists,
19.1512 + ///\ref INVALID otherwise.
19.1513 + Arc operator()(Node s, Node t) const
19.1514 + {
19.1515 + Arc a = _head[s];
19.1516 + while (true) {
19.1517 + if (_g.target(a) == t) {
19.1518 + const_cast<DynArcLookUp&>(*this).splay(a);
19.1519 + return a;
19.1520 + } else if (t < _g.target(a)) {
19.1521 + if (_left[a] == INVALID) {
19.1522 + const_cast<DynArcLookUp&>(*this).splay(a);
19.1523 + return INVALID;
19.1524 + } else {
19.1525 + a = _left[a];
19.1526 + }
19.1527 + } else {
19.1528 + if (_right[a] == INVALID) {
19.1529 + const_cast<DynArcLookUp&>(*this).splay(a);
19.1530 + return INVALID;
19.1531 + } else {
19.1532 + a = _right[a];
19.1533 + }
19.1534 + }
19.1535 + }
19.1536 + }
19.1537 +
19.1538 + ///Find the first arc between two nodes.
19.1539 +
19.1540 + ///Find the first arc between two nodes in time
19.1541 + /// <em>O(</em>log<em>d)</em>, where <em>d</em> is the number of
19.1542 + /// outgoing arcs of \c s.
19.1543 + ///\param s The source node
19.1544 + ///\param t The target node
19.1545 + ///\return An arc from \c s to \c t if there exists, \ref INVALID
19.1546 + /// otherwise.
19.1547 + Arc findFirst(Node s, Node t) const
19.1548 + {
19.1549 + Arc a = _head[s];
19.1550 + Arc r = INVALID;
19.1551 + while (true) {
19.1552 + if (_g.target(a) < t) {
19.1553 + if (_right[a] == INVALID) {
19.1554 + const_cast<DynArcLookUp&>(*this).splay(a);
19.1555 + return r;
19.1556 + } else {
19.1557 + a = _right[a];
19.1558 + }
19.1559 + } else {
19.1560 + if (_g.target(a) == t) {
19.1561 + r = a;
19.1562 + }
19.1563 + if (_left[a] == INVALID) {
19.1564 + const_cast<DynArcLookUp&>(*this).splay(a);
19.1565 + return r;
19.1566 + } else {
19.1567 + a = _left[a];
19.1568 + }
19.1569 + }
19.1570 + }
19.1571 + }
19.1572 +
19.1573 + ///Find the next arc between two nodes.
19.1574 +
19.1575 + ///Find the next arc between two nodes in time
19.1576 + /// <em>O(</em>log<em>d)</em>, where <em>d</em> is the number of
19.1577 + /// outgoing arcs of \c s.
19.1578 + ///\param s The source node
19.1579 + ///\param t The target node
19.1580 + ///\return An arc from \c s to \c t if there exists, \ref INVALID
19.1581 + /// otherwise.
19.1582 +
19.1583 + ///\note If \c e is not the result of the previous \c findFirst()
19.1584 + ///operation then the amorized time bound can not be guaranteed.
19.1585 +#ifdef DOXYGEN
19.1586 + Arc findNext(Node s, Node t, Arc a) const
19.1587 +#else
19.1588 + Arc findNext(Node, Node t, Arc a) const
19.1589 +#endif
19.1590 + {
19.1591 + if (_right[a] != INVALID) {
19.1592 + a = _right[a];
19.1593 + while (_left[a] != INVALID) {
19.1594 + a = _left[a];
19.1595 + }
19.1596 + const_cast<DynArcLookUp&>(*this).splay(a);
19.1597 + } else {
19.1598 + while (_parent[a] != INVALID && _right[_parent[a]] == a) {
19.1599 + a = _parent[a];
19.1600 + }
19.1601 + if (_parent[a] == INVALID) {
19.1602 + return INVALID;
19.1603 + } else {
19.1604 + a = _parent[a];
19.1605 + const_cast<DynArcLookUp&>(*this).splay(a);
19.1606 + }
19.1607 + }
19.1608 + if (_g.target(a) == t) return a;
19.1609 + else return INVALID;
19.1610 + }
19.1611 +
19.1612 + };
19.1613 +
19.1614 + ///Fast arc look up between given endpoints.
19.1615 +
19.1616 + ///Using this class, you can find an arc in a digraph from a given
19.1617 + ///source to a given target in time <em>O(log d)</em>,
19.1618 + ///where <em>d</em> is the out-degree of the source node.
19.1619 + ///
19.1620 + ///It is not possible to find \e all parallel arcs between two nodes.
19.1621 + ///Use \ref AllArcLookUp for this purpose.
19.1622 + ///
19.1623 + ///\warning This class is static, so you should refresh() (or at least
19.1624 + ///refresh(Node)) this data structure
19.1625 + ///whenever the digraph changes. This is a time consuming (superlinearly
19.1626 + ///proportional (<em>O(m</em>log<em>m)</em>) to the number of arcs).
19.1627 + ///
19.1628 + ///\tparam G The type of the underlying digraph.
19.1629 + ///
19.1630 + ///\sa DynArcLookUp
19.1631 + ///\sa AllArcLookUp
19.1632 + template<class G>
19.1633 + class ArcLookUp
19.1634 + {
19.1635 + public:
19.1636 + TEMPLATE_DIGRAPH_TYPEDEFS(G);
19.1637 + typedef G Digraph;
19.1638 +
19.1639 + protected:
19.1640 + const Digraph &_g;
19.1641 + typename Digraph::template NodeMap<Arc> _head;
19.1642 + typename Digraph::template ArcMap<Arc> _left;
19.1643 + typename Digraph::template ArcMap<Arc> _right;
19.1644 +
19.1645 + class ArcLess {
19.1646 + const Digraph &g;
19.1647 + public:
19.1648 + ArcLess(const Digraph &_g) : g(_g) {}
19.1649 + bool operator()(Arc a,Arc b) const
19.1650 + {
19.1651 + return g.target(a)<g.target(b);
19.1652 + }
19.1653 + };
19.1654 +
19.1655 + public:
19.1656 +
19.1657 + ///Constructor
19.1658 +
19.1659 + ///Constructor.
19.1660 + ///
19.1661 + ///It builds up the search database, which remains valid until the digraph
19.1662 + ///changes.
19.1663 + ArcLookUp(const Digraph &g) :_g(g),_head(g),_left(g),_right(g) {refresh();}
19.1664 +
19.1665 + private:
19.1666 + Arc refreshRec(std::vector<Arc> &v,int a,int b)
19.1667 + {
19.1668 + int m=(a+b)/2;
19.1669 + Arc me=v[m];
19.1670 + _left[me] = a<m?refreshRec(v,a,m-1):INVALID;
19.1671 + _right[me] = m<b?refreshRec(v,m+1,b):INVALID;
19.1672 + return me;
19.1673 + }
19.1674 + public:
19.1675 + ///Refresh the data structure at a node.
19.1676 +
19.1677 + ///Build up the search database of node \c n.
19.1678 + ///
19.1679 + ///It runs in time <em>O(d</em>log<em>d)</em>, where <em>d</em> is
19.1680 + ///the number of the outgoing arcs of \c n.
19.1681 + void refresh(Node n)
19.1682 + {
19.1683 + std::vector<Arc> v;
19.1684 + for(OutArcIt e(_g,n);e!=INVALID;++e) v.push_back(e);
19.1685 + if(v.size()) {
19.1686 + std::sort(v.begin(),v.end(),ArcLess(_g));
19.1687 + _head[n]=refreshRec(v,0,v.size()-1);
19.1688 + }
19.1689 + else _head[n]=INVALID;
19.1690 + }
19.1691 + ///Refresh the full data structure.
19.1692 +
19.1693 + ///Build up the full search database. In fact, it simply calls
19.1694 + ///\ref refresh(Node) "refresh(n)" for each node \c n.
19.1695 + ///
19.1696 + ///It runs in time <em>O(m</em>log<em>D)</em>, where <em>m</em> is
19.1697 + ///the number of the arcs of \c n and <em>D</em> is the maximum
19.1698 + ///out-degree of the digraph.
19.1699 +
19.1700 + void refresh()
19.1701 + {
19.1702 + for(NodeIt n(_g);n!=INVALID;++n) refresh(n);
19.1703 + }
19.1704 +
19.1705 + ///Find an arc between two nodes.
19.1706 +
19.1707 + ///Find an arc between two nodes in time <em>O(</em>log<em>d)</em>, where
19.1708 + /// <em>d</em> is the number of outgoing arcs of \c s.
19.1709 + ///\param s The source node
19.1710 + ///\param t The target node
19.1711 + ///\return An arc from \c s to \c t if there exists,
19.1712 + ///\ref INVALID otherwise.
19.1713 + ///
19.1714 + ///\warning If you change the digraph, refresh() must be called before using
19.1715 + ///this operator. If you change the outgoing arcs of
19.1716 + ///a single node \c n, then
19.1717 + ///\ref refresh(Node) "refresh(n)" is enough.
19.1718 + ///
19.1719 + Arc operator()(Node s, Node t) const
19.1720 + {
19.1721 + Arc e;
19.1722 + for(e=_head[s];
19.1723 + e!=INVALID&&_g.target(e)!=t;
19.1724 + e = t < _g.target(e)?_left[e]:_right[e]) ;
19.1725 + return e;
19.1726 + }
19.1727 +
19.1728 + };
19.1729 +
19.1730 + ///Fast look up of all arcs between given endpoints.
19.1731 +
19.1732 + ///This class is the same as \ref ArcLookUp, with the addition
19.1733 + ///that it makes it possible to find all arcs between given endpoints.
19.1734 + ///
19.1735 + ///\warning This class is static, so you should refresh() (or at least
19.1736 + ///refresh(Node)) this data structure
19.1737 + ///whenever the digraph changes. This is a time consuming (superlinearly
19.1738 + ///proportional (<em>O(m</em>log<em>m)</em>) to the number of arcs).
19.1739 + ///
19.1740 + ///\tparam G The type of the underlying digraph.
19.1741 + ///
19.1742 + ///\sa DynArcLookUp
19.1743 + ///\sa ArcLookUp
19.1744 + template<class G>
19.1745 + class AllArcLookUp : public ArcLookUp<G>
19.1746 + {
19.1747 + using ArcLookUp<G>::_g;
19.1748 + using ArcLookUp<G>::_right;
19.1749 + using ArcLookUp<G>::_left;
19.1750 + using ArcLookUp<G>::_head;
19.1751 +
19.1752 + TEMPLATE_DIGRAPH_TYPEDEFS(G);
19.1753 + typedef G Digraph;
19.1754 +
19.1755 + typename Digraph::template ArcMap<Arc> _next;
19.1756 +
19.1757 + Arc refreshNext(Arc head,Arc next=INVALID)
19.1758 + {
19.1759 + if(head==INVALID) return next;
19.1760 + else {
19.1761 + next=refreshNext(_right[head],next);
19.1762 +// _next[head]=next;
19.1763 + _next[head]=( next!=INVALID && _g.target(next)==_g.target(head))
19.1764 + ? next : INVALID;
19.1765 + return refreshNext(_left[head],head);
19.1766 + }
19.1767 + }
19.1768 +
19.1769 + void refreshNext()
19.1770 + {
19.1771 + for(NodeIt n(_g);n!=INVALID;++n) refreshNext(_head[n]);
19.1772 + }
19.1773 +
19.1774 + public:
19.1775 + ///Constructor
19.1776 +
19.1777 + ///Constructor.
19.1778 + ///
19.1779 + ///It builds up the search database, which remains valid until the digraph
19.1780 + ///changes.
19.1781 + AllArcLookUp(const Digraph &g) : ArcLookUp<G>(g), _next(g) {refreshNext();}
19.1782 +
19.1783 + ///Refresh the data structure at a node.
19.1784 +
19.1785 + ///Build up the search database of node \c n.
19.1786 + ///
19.1787 + ///It runs in time <em>O(d</em>log<em>d)</em>, where <em>d</em> is
19.1788 + ///the number of the outgoing arcs of \c n.
19.1789 +
19.1790 + void refresh(Node n)
19.1791 + {
19.1792 + ArcLookUp<G>::refresh(n);
19.1793 + refreshNext(_head[n]);
19.1794 + }
19.1795 +
19.1796 + ///Refresh the full data structure.
19.1797 +
19.1798 + ///Build up the full search database. In fact, it simply calls
19.1799 + ///\ref refresh(Node) "refresh(n)" for each node \c n.
19.1800 + ///
19.1801 + ///It runs in time <em>O(m</em>log<em>D)</em>, where <em>m</em> is
19.1802 + ///the number of the arcs of \c n and <em>D</em> is the maximum
19.1803 + ///out-degree of the digraph.
19.1804 +
19.1805 + void refresh()
19.1806 + {
19.1807 + for(NodeIt n(_g);n!=INVALID;++n) refresh(_head[n]);
19.1808 + }
19.1809 +
19.1810 + ///Find an arc between two nodes.
19.1811 +
19.1812 + ///Find an arc between two nodes.
19.1813 + ///\param s The source node
19.1814 + ///\param t The target node
19.1815 + ///\param prev The previous arc between \c s and \c t. It it is INVALID or
19.1816 + ///not given, the operator finds the first appropriate arc.
19.1817 + ///\return An arc from \c s to \c t after \c prev or
19.1818 + ///\ref INVALID if there is no more.
19.1819 + ///
19.1820 + ///For example, you can count the number of arcs from \c u to \c v in the
19.1821 + ///following way.
19.1822 + ///\code
19.1823 + ///AllArcLookUp<ListDigraph> ae(g);
19.1824 + ///...
19.1825 + ///int n=0;
19.1826 + ///for(Arc e=ae(u,v);e!=INVALID;e=ae(u,v,e)) n++;
19.1827 + ///\endcode
19.1828 + ///
19.1829 + ///Finding the first arc take <em>O(</em>log<em>d)</em> time, where
19.1830 + /// <em>d</em> is the number of outgoing arcs of \c s. Then, the
19.1831 + ///consecutive arcs are found in constant time.
19.1832 + ///
19.1833 + ///\warning If you change the digraph, refresh() must be called before using
19.1834 + ///this operator. If you change the outgoing arcs of
19.1835 + ///a single node \c n, then
19.1836 + ///\ref refresh(Node) "refresh(n)" is enough.
19.1837 + ///
19.1838 +#ifdef DOXYGEN
19.1839 + Arc operator()(Node s, Node t, Arc prev=INVALID) const {}
19.1840 +#else
19.1841 + using ArcLookUp<G>::operator() ;
19.1842 + Arc operator()(Node s, Node t, Arc prev) const
19.1843 + {
19.1844 + return prev==INVALID?(*this)(s,t):_next[prev];
19.1845 + }
19.1846 +#endif
19.1847 +
19.1848 + };
19.1849 +
19.1850 + /// @}
19.1851 +
19.1852 +} //namespace lemon
19.1853 +
19.1854 +#endif
20.1 --- a/lemon/dfs.h Tue Jul 15 18:43:41 2008 +0100
20.2 +++ b/lemon/dfs.h Tue Jul 15 18:49:30 2008 +0100
20.3 @@ -24,9 +24,8 @@
20.4 ///\brief Dfs algorithm.
20.5
20.6 #include <lemon/list_graph.h>
20.7 -#include <lemon/graph_utils.h>
20.8 #include <lemon/bits/path_dump.h>
20.9 -#include <lemon/bits/invalid.h>
20.10 +#include <lemon/core.h>
20.11 #include <lemon/error.h>
20.12 #include <lemon/maps.h>
20.13
21.1 --- a/lemon/dijkstra.h Tue Jul 15 18:43:41 2008 +0100
21.2 +++ b/lemon/dijkstra.h Tue Jul 15 18:49:30 2008 +0100
21.3 @@ -27,7 +27,7 @@
21.4 #include <lemon/list_graph.h>
21.5 #include <lemon/bin_heap.h>
21.6 #include <lemon/bits/path_dump.h>
21.7 -#include <lemon/bits/invalid.h>
21.8 +#include <lemon/core.h>
21.9 #include <lemon/error.h>
21.10 #include <lemon/maps.h>
21.11
22.1 --- a/lemon/dim2.h Tue Jul 15 18:43:41 2008 +0100
22.2 +++ b/lemon/dim2.h Tue Jul 15 18:49:30 2008 +0100
22.3 @@ -20,7 +20,7 @@
22.4 #define LEMON_DIM2_H
22.5
22.6 #include <iostream>
22.7 -#include <lemon/bits/utility.h>
22.8 +#include <lemon/core.h>
22.9
22.10 ///\ingroup misc
22.11 ///\file
23.1 --- a/lemon/graph_to_eps.h Tue Jul 15 18:43:41 2008 +0100
23.2 +++ b/lemon/graph_to_eps.h Tue Jul 15 18:49:30 2008 +0100
23.3 @@ -35,7 +35,7 @@
23.4 #endif
23.5
23.6 #include<lemon/math.h>
23.7 -#include<lemon/bits/invalid.h>
23.8 +#include<lemon/core.h>
23.9 #include<lemon/dim2.h>
23.10 #include<lemon/maps.h>
23.11 #include<lemon/color.h>
24.1 --- a/lemon/graph_utils.h Tue Jul 15 18:43:41 2008 +0100
24.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
24.3 @@ -1,2760 +0,0 @@
24.4 -/* -*- mode: C++; indent-tabs-mode: nil; -*-
24.5 - *
24.6 - * This file is a part of LEMON, a generic C++ optimization library.
24.7 - *
24.8 - * Copyright (C) 2003-2008
24.9 - * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
24.10 - * (Egervary Research Group on Combinatorial Optimization, EGRES).
24.11 - *
24.12 - * Permission to use, modify and distribute this software is granted
24.13 - * provided that this copyright notice appears in all copies. For
24.14 - * precise terms see the accompanying LICENSE file.
24.15 - *
24.16 - * This software is provided "AS IS" with no warranty of any kind,
24.17 - * express or implied, and with no claim as to its suitability for any
24.18 - * purpose.
24.19 - *
24.20 - */
24.21 -
24.22 -#ifndef LEMON_GRAPH_UTILS_H
24.23 -#define LEMON_GRAPH_UTILS_H
24.24 -
24.25 -#include <iterator>
24.26 -#include <vector>
24.27 -#include <map>
24.28 -#include <cmath>
24.29 -#include <algorithm>
24.30 -
24.31 -#include <lemon/bits/invalid.h>
24.32 -#include <lemon/bits/utility.h>
24.33 -#include <lemon/maps.h>
24.34 -#include <lemon/bits/traits.h>
24.35 -
24.36 -#include <lemon/bits/alteration_notifier.h>
24.37 -#include <lemon/bits/default_map.h>
24.38 -
24.39 -///\ingroup gutils
24.40 -///\file
24.41 -///\brief Graph utilities.
24.42 -
24.43 -namespace lemon {
24.44 -
24.45 - /// \addtogroup gutils
24.46 - /// @{
24.47 -
24.48 - ///Creates convenience typedefs for the digraph types and iterators
24.49 -
24.50 - ///This \c \#define creates convenience typedefs for the following types
24.51 - ///of \c Digraph: \c Node, \c NodeIt, \c Arc, \c ArcIt, \c InArcIt,
24.52 - ///\c OutArcIt, \c BoolNodeMap, \c IntNodeMap, \c DoubleNodeMap,
24.53 - ///\c BoolArcMap, \c IntArcMap, \c DoubleArcMap.
24.54 - ///
24.55 - ///\note If the graph type is a dependent type, ie. the graph type depend
24.56 - ///on a template parameter, then use \c TEMPLATE_DIGRAPH_TYPEDEFS()
24.57 - ///macro.
24.58 -#define DIGRAPH_TYPEDEFS(Digraph) \
24.59 - typedef Digraph::Node Node; \
24.60 - typedef Digraph::NodeIt NodeIt; \
24.61 - typedef Digraph::Arc Arc; \
24.62 - typedef Digraph::ArcIt ArcIt; \
24.63 - typedef Digraph::InArcIt InArcIt; \
24.64 - typedef Digraph::OutArcIt OutArcIt; \
24.65 - typedef Digraph::NodeMap<bool> BoolNodeMap; \
24.66 - typedef Digraph::NodeMap<int> IntNodeMap; \
24.67 - typedef Digraph::NodeMap<double> DoubleNodeMap; \
24.68 - typedef Digraph::ArcMap<bool> BoolArcMap; \
24.69 - typedef Digraph::ArcMap<int> IntArcMap; \
24.70 - typedef Digraph::ArcMap<double> DoubleArcMap
24.71 -
24.72 - ///Creates convenience typedefs for the digraph types and iterators
24.73 -
24.74 - ///\see DIGRAPH_TYPEDEFS
24.75 - ///
24.76 - ///\note Use this macro, if the graph type is a dependent type,
24.77 - ///ie. the graph type depend on a template parameter.
24.78 -#define TEMPLATE_DIGRAPH_TYPEDEFS(Digraph) \
24.79 - typedef typename Digraph::Node Node; \
24.80 - typedef typename Digraph::NodeIt NodeIt; \
24.81 - typedef typename Digraph::Arc Arc; \
24.82 - typedef typename Digraph::ArcIt ArcIt; \
24.83 - typedef typename Digraph::InArcIt InArcIt; \
24.84 - typedef typename Digraph::OutArcIt OutArcIt; \
24.85 - typedef typename Digraph::template NodeMap<bool> BoolNodeMap; \
24.86 - typedef typename Digraph::template NodeMap<int> IntNodeMap; \
24.87 - typedef typename Digraph::template NodeMap<double> DoubleNodeMap; \
24.88 - typedef typename Digraph::template ArcMap<bool> BoolArcMap; \
24.89 - typedef typename Digraph::template ArcMap<int> IntArcMap; \
24.90 - typedef typename Digraph::template ArcMap<double> DoubleArcMap
24.91 -
24.92 - ///Creates convenience typedefs for the graph types and iterators
24.93 -
24.94 - ///This \c \#define creates the same convenience typedefs as defined
24.95 - ///by \ref DIGRAPH_TYPEDEFS(Graph) and six more, namely it creates
24.96 - ///\c Edge, \c EdgeIt, \c IncEdgeIt, \c BoolEdgeMap, \c IntEdgeMap,
24.97 - ///\c DoubleEdgeMap.
24.98 - ///
24.99 - ///\note If the graph type is a dependent type, ie. the graph type depend
24.100 - ///on a template parameter, then use \c TEMPLATE_DIGRAPH_TYPEDEFS()
24.101 - ///macro.
24.102 -#define GRAPH_TYPEDEFS(Graph) \
24.103 - DIGRAPH_TYPEDEFS(Graph); \
24.104 - typedef Graph::Edge Edge; \
24.105 - typedef Graph::EdgeIt EdgeIt; \
24.106 - typedef Graph::IncEdgeIt IncEdgeIt; \
24.107 - typedef Graph::EdgeMap<bool> BoolEdgeMap; \
24.108 - typedef Graph::EdgeMap<int> IntEdgeMap; \
24.109 - typedef Graph::EdgeMap<double> DoubleEdgeMap
24.110 -
24.111 - ///Creates convenience typedefs for the graph types and iterators
24.112 -
24.113 - ///\see GRAPH_TYPEDEFS
24.114 - ///
24.115 - ///\note Use this macro, if the graph type is a dependent type,
24.116 - ///ie. the graph type depend on a template parameter.
24.117 -#define TEMPLATE_GRAPH_TYPEDEFS(Graph) \
24.118 - TEMPLATE_DIGRAPH_TYPEDEFS(Graph); \
24.119 - typedef typename Graph::Edge Edge; \
24.120 - typedef typename Graph::EdgeIt EdgeIt; \
24.121 - typedef typename Graph::IncEdgeIt IncEdgeIt; \
24.122 - typedef typename Graph::template EdgeMap<bool> BoolEdgeMap; \
24.123 - typedef typename Graph::template EdgeMap<int> IntEdgeMap; \
24.124 - typedef typename Graph::template EdgeMap<double> DoubleEdgeMap
24.125 -
24.126 - /// \brief Function to count the items in the graph.
24.127 - ///
24.128 - /// This function counts the items (nodes, arcs etc) in the graph.
24.129 - /// The complexity of the function is O(n) because
24.130 - /// it iterates on all of the items.
24.131 - template <typename Graph, typename Item>
24.132 - inline int countItems(const Graph& g) {
24.133 - typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;
24.134 - int num = 0;
24.135 - for (ItemIt it(g); it != INVALID; ++it) {
24.136 - ++num;
24.137 - }
24.138 - return num;
24.139 - }
24.140 -
24.141 - // Node counting:
24.142 -
24.143 - namespace _graph_utils_bits {
24.144 -
24.145 - template <typename Graph, typename Enable = void>
24.146 - struct CountNodesSelector {
24.147 - static int count(const Graph &g) {
24.148 - return countItems<Graph, typename Graph::Node>(g);
24.149 - }
24.150 - };
24.151 -
24.152 - template <typename Graph>
24.153 - struct CountNodesSelector<
24.154 - Graph, typename
24.155 - enable_if<typename Graph::NodeNumTag, void>::type>
24.156 - {
24.157 - static int count(const Graph &g) {
24.158 - return g.nodeNum();
24.159 - }
24.160 - };
24.161 - }
24.162 -
24.163 - /// \brief Function to count the nodes in the graph.
24.164 - ///
24.165 - /// This function counts the nodes in the graph.
24.166 - /// The complexity of the function is O(n) but for some
24.167 - /// graph structures it is specialized to run in O(1).
24.168 - ///
24.169 - /// If the graph contains a \e nodeNum() member function and a
24.170 - /// \e NodeNumTag tag then this function calls directly the member
24.171 - /// function to query the cardinality of the node set.
24.172 - template <typename Graph>
24.173 - inline int countNodes(const Graph& g) {
24.174 - return _graph_utils_bits::CountNodesSelector<Graph>::count(g);
24.175 - }
24.176 -
24.177 - // Arc counting:
24.178 -
24.179 - namespace _graph_utils_bits {
24.180 -
24.181 - template <typename Graph, typename Enable = void>
24.182 - struct CountArcsSelector {
24.183 - static int count(const Graph &g) {
24.184 - return countItems<Graph, typename Graph::Arc>(g);
24.185 - }
24.186 - };
24.187 -
24.188 - template <typename Graph>
24.189 - struct CountArcsSelector<
24.190 - Graph,
24.191 - typename enable_if<typename Graph::ArcNumTag, void>::type>
24.192 - {
24.193 - static int count(const Graph &g) {
24.194 - return g.arcNum();
24.195 - }
24.196 - };
24.197 - }
24.198 -
24.199 - /// \brief Function to count the arcs in the graph.
24.200 - ///
24.201 - /// This function counts the arcs in the graph.
24.202 - /// The complexity of the function is O(e) but for some
24.203 - /// graph structures it is specialized to run in O(1).
24.204 - ///
24.205 - /// If the graph contains a \e arcNum() member function and a
24.206 - /// \e EdgeNumTag tag then this function calls directly the member
24.207 - /// function to query the cardinality of the arc set.
24.208 - template <typename Graph>
24.209 - inline int countArcs(const Graph& g) {
24.210 - return _graph_utils_bits::CountArcsSelector<Graph>::count(g);
24.211 - }
24.212 -
24.213 - // Edge counting:
24.214 - namespace _graph_utils_bits {
24.215 -
24.216 - template <typename Graph, typename Enable = void>
24.217 - struct CountEdgesSelector {
24.218 - static int count(const Graph &g) {
24.219 - return countItems<Graph, typename Graph::Edge>(g);
24.220 - }
24.221 - };
24.222 -
24.223 - template <typename Graph>
24.224 - struct CountEdgesSelector<
24.225 - Graph,
24.226 - typename enable_if<typename Graph::EdgeNumTag, void>::type>
24.227 - {
24.228 - static int count(const Graph &g) {
24.229 - return g.edgeNum();
24.230 - }
24.231 - };
24.232 - }
24.233 -
24.234 - /// \brief Function to count the edges in the graph.
24.235 - ///
24.236 - /// This function counts the edges in the graph.
24.237 - /// The complexity of the function is O(m) but for some
24.238 - /// graph structures it is specialized to run in O(1).
24.239 - ///
24.240 - /// If the graph contains a \e edgeNum() member function and a
24.241 - /// \e EdgeNumTag tag then this function calls directly the member
24.242 - /// function to query the cardinality of the edge set.
24.243 - template <typename Graph>
24.244 - inline int countEdges(const Graph& g) {
24.245 - return _graph_utils_bits::CountEdgesSelector<Graph>::count(g);
24.246 -
24.247 - }
24.248 -
24.249 -
24.250 - template <typename Graph, typename DegIt>
24.251 - inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) {
24.252 - int num = 0;
24.253 - for (DegIt it(_g, _n); it != INVALID; ++it) {
24.254 - ++num;
24.255 - }
24.256 - return num;
24.257 - }
24.258 -
24.259 - /// \brief Function to count the number of the out-arcs from node \c n.
24.260 - ///
24.261 - /// This function counts the number of the out-arcs from node \c n
24.262 - /// in the graph.
24.263 - template <typename Graph>
24.264 - inline int countOutArcs(const Graph& _g, const typename Graph::Node& _n) {
24.265 - return countNodeDegree<Graph, typename Graph::OutArcIt>(_g, _n);
24.266 - }
24.267 -
24.268 - /// \brief Function to count the number of the in-arcs to node \c n.
24.269 - ///
24.270 - /// This function counts the number of the in-arcs to node \c n
24.271 - /// in the graph.
24.272 - template <typename Graph>
24.273 - inline int countInArcs(const Graph& _g, const typename Graph::Node& _n) {
24.274 - return countNodeDegree<Graph, typename Graph::InArcIt>(_g, _n);
24.275 - }
24.276 -
24.277 - /// \brief Function to count the number of the inc-edges to node \c n.
24.278 - ///
24.279 - /// This function counts the number of the inc-edges to node \c n
24.280 - /// in the graph.
24.281 - template <typename Graph>
24.282 - inline int countIncEdges(const Graph& _g, const typename Graph::Node& _n) {
24.283 - return countNodeDegree<Graph, typename Graph::IncEdgeIt>(_g, _n);
24.284 - }
24.285 -
24.286 - namespace _graph_utils_bits {
24.287 -
24.288 - template <typename Graph, typename Enable = void>
24.289 - struct FindArcSelector {
24.290 - typedef typename Graph::Node Node;
24.291 - typedef typename Graph::Arc Arc;
24.292 - static Arc find(const Graph &g, Node u, Node v, Arc e) {
24.293 - if (e == INVALID) {
24.294 - g.firstOut(e, u);
24.295 - } else {
24.296 - g.nextOut(e);
24.297 - }
24.298 - while (e != INVALID && g.target(e) != v) {
24.299 - g.nextOut(e);
24.300 - }
24.301 - return e;
24.302 - }
24.303 - };
24.304 -
24.305 - template <typename Graph>
24.306 - struct FindArcSelector<
24.307 - Graph,
24.308 - typename enable_if<typename Graph::FindEdgeTag, void>::type>
24.309 - {
24.310 - typedef typename Graph::Node Node;
24.311 - typedef typename Graph::Arc Arc;
24.312 - static Arc find(const Graph &g, Node u, Node v, Arc prev) {
24.313 - return g.findArc(u, v, prev);
24.314 - }
24.315 - };
24.316 - }
24.317 -
24.318 - /// \brief Finds an arc between two nodes of a graph.
24.319 - ///
24.320 - /// Finds an arc from node \c u to node \c v in graph \c g.
24.321 - ///
24.322 - /// If \c prev is \ref INVALID (this is the default value), then
24.323 - /// it finds the first arc from \c u to \c v. Otherwise it looks for
24.324 - /// the next arc from \c u to \c v after \c prev.
24.325 - /// \return The found arc or \ref INVALID if there is no such an arc.
24.326 - ///
24.327 - /// Thus you can iterate through each arc from \c u to \c v as it follows.
24.328 - ///\code
24.329 - /// for(Arc e=findArc(g,u,v);e!=INVALID;e=findArc(g,u,v,e)) {
24.330 - /// ...
24.331 - /// }
24.332 - ///\endcode
24.333 - ///
24.334 - ///\sa ArcLookUp
24.335 - ///\sa AllArcLookUp
24.336 - ///\sa DynArcLookUp
24.337 - ///\sa ConArcIt
24.338 - template <typename Graph>
24.339 - inline typename Graph::Arc
24.340 - findArc(const Graph &g, typename Graph::Node u, typename Graph::Node v,
24.341 - typename Graph::Arc prev = INVALID) {
24.342 - return _graph_utils_bits::FindArcSelector<Graph>::find(g, u, v, prev);
24.343 - }
24.344 -
24.345 - /// \brief Iterator for iterating on arcs connected the same nodes.
24.346 - ///
24.347 - /// Iterator for iterating on arcs connected the same nodes. It is
24.348 - /// higher level interface for the findArc() function. You can
24.349 - /// use it the following way:
24.350 - ///\code
24.351 - /// for (ConArcIt<Graph> it(g, src, trg); it != INVALID; ++it) {
24.352 - /// ...
24.353 - /// }
24.354 - ///\endcode
24.355 - ///
24.356 - ///\sa findArc()
24.357 - ///\sa ArcLookUp
24.358 - ///\sa AllArcLookUp
24.359 - ///\sa DynArcLookUp
24.360 - template <typename _Graph>
24.361 - class ConArcIt : public _Graph::Arc {
24.362 - public:
24.363 -
24.364 - typedef _Graph Graph;
24.365 - typedef typename Graph::Arc Parent;
24.366 -
24.367 - typedef typename Graph::Arc Arc;
24.368 - typedef typename Graph::Node Node;
24.369 -
24.370 - /// \brief Constructor.
24.371 - ///
24.372 - /// Construct a new ConArcIt iterating on the arcs which
24.373 - /// connects the \c u and \c v node.
24.374 - ConArcIt(const Graph& g, Node u, Node v) : _graph(g) {
24.375 - Parent::operator=(findArc(_graph, u, v));
24.376 - }
24.377 -
24.378 - /// \brief Constructor.
24.379 - ///
24.380 - /// Construct a new ConArcIt which continues the iterating from
24.381 - /// the \c e arc.
24.382 - ConArcIt(const Graph& g, Arc a) : Parent(a), _graph(g) {}
24.383 -
24.384 - /// \brief Increment operator.
24.385 - ///
24.386 - /// It increments the iterator and gives back the next arc.
24.387 - ConArcIt& operator++() {
24.388 - Parent::operator=(findArc(_graph, _graph.source(*this),
24.389 - _graph.target(*this), *this));
24.390 - return *this;
24.391 - }
24.392 - private:
24.393 - const Graph& _graph;
24.394 - };
24.395 -
24.396 - namespace _graph_utils_bits {
24.397 -
24.398 - template <typename Graph, typename Enable = void>
24.399 - struct FindEdgeSelector {
24.400 - typedef typename Graph::Node Node;
24.401 - typedef typename Graph::Edge Edge;
24.402 - static Edge find(const Graph &g, Node u, Node v, Edge e) {
24.403 - bool b;
24.404 - if (u != v) {
24.405 - if (e == INVALID) {
24.406 - g.firstInc(e, b, u);
24.407 - } else {
24.408 - b = g.u(e) == u;
24.409 - g.nextInc(e, b);
24.410 - }
24.411 - while (e != INVALID && (b ? g.v(e) : g.u(e)) != v) {
24.412 - g.nextInc(e, b);
24.413 - }
24.414 - } else {
24.415 - if (e == INVALID) {
24.416 - g.firstInc(e, b, u);
24.417 - } else {
24.418 - b = true;
24.419 - g.nextInc(e, b);
24.420 - }
24.421 - while (e != INVALID && (!b || g.v(e) != v)) {
24.422 - g.nextInc(e, b);
24.423 - }
24.424 - }
24.425 - return e;
24.426 - }
24.427 - };
24.428 -
24.429 - template <typename Graph>
24.430 - struct FindEdgeSelector<
24.431 - Graph,
24.432 - typename enable_if<typename Graph::FindEdgeTag, void>::type>
24.433 - {
24.434 - typedef typename Graph::Node Node;
24.435 - typedef typename Graph::Edge Edge;
24.436 - static Edge find(const Graph &g, Node u, Node v, Edge prev) {
24.437 - return g.findEdge(u, v, prev);
24.438 - }
24.439 - };
24.440 - }
24.441 -
24.442 - /// \brief Finds an edge between two nodes of a graph.
24.443 - ///
24.444 - /// Finds an edge from node \c u to node \c v in graph \c g.
24.445 - /// If the node \c u and node \c v is equal then each loop edge
24.446 - /// will be enumerated once.
24.447 - ///
24.448 - /// If \c prev is \ref INVALID (this is the default value), then
24.449 - /// it finds the first arc from \c u to \c v. Otherwise it looks for
24.450 - /// the next arc from \c u to \c v after \c prev.
24.451 - /// \return The found arc or \ref INVALID if there is no such an arc.
24.452 - ///
24.453 - /// Thus you can iterate through each arc from \c u to \c v as it follows.
24.454 - ///\code
24.455 - /// for(Edge e = findEdge(g,u,v); e != INVALID;
24.456 - /// e = findEdge(g,u,v,e)) {
24.457 - /// ...
24.458 - /// }
24.459 - ///\endcode
24.460 - ///
24.461 - ///\sa ConEdgeIt
24.462 -
24.463 - template <typename Graph>
24.464 - inline typename Graph::Edge
24.465 - findEdge(const Graph &g, typename Graph::Node u, typename Graph::Node v,
24.466 - typename Graph::Edge p = INVALID) {
24.467 - return _graph_utils_bits::FindEdgeSelector<Graph>::find(g, u, v, p);
24.468 - }
24.469 -
24.470 - /// \brief Iterator for iterating on edges connected the same nodes.
24.471 - ///
24.472 - /// Iterator for iterating on edges connected the same nodes. It is
24.473 - /// higher level interface for the findEdge() function. You can
24.474 - /// use it the following way:
24.475 - ///\code
24.476 - /// for (ConEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) {
24.477 - /// ...
24.478 - /// }
24.479 - ///\endcode
24.480 - ///
24.481 - ///\sa findEdge()
24.482 - template <typename _Graph>
24.483 - class ConEdgeIt : public _Graph::Edge {
24.484 - public:
24.485 -
24.486 - typedef _Graph Graph;
24.487 - typedef typename Graph::Edge Parent;
24.488 -
24.489 - typedef typename Graph::Edge Edge;
24.490 - typedef typename Graph::Node Node;
24.491 -
24.492 - /// \brief Constructor.
24.493 - ///
24.494 - /// Construct a new ConEdgeIt iterating on the edges which
24.495 - /// connects the \c u and \c v node.
24.496 - ConEdgeIt(const Graph& g, Node u, Node v) : _graph(g) {
24.497 - Parent::operator=(findEdge(_graph, u, v));
24.498 - }
24.499 -
24.500 - /// \brief Constructor.
24.501 - ///
24.502 - /// Construct a new ConEdgeIt which continues the iterating from
24.503 - /// the \c e edge.
24.504 - ConEdgeIt(const Graph& g, Edge e) : Parent(e), _graph(g) {}
24.505 -
24.506 - /// \brief Increment operator.
24.507 - ///
24.508 - /// It increments the iterator and gives back the next edge.
24.509 - ConEdgeIt& operator++() {
24.510 - Parent::operator=(findEdge(_graph, _graph.u(*this),
24.511 - _graph.v(*this), *this));
24.512 - return *this;
24.513 - }
24.514 - private:
24.515 - const Graph& _graph;
24.516 - };
24.517 -
24.518 - namespace _graph_utils_bits {
24.519 -
24.520 - template <typename Digraph, typename Item, typename RefMap>
24.521 - class MapCopyBase {
24.522 - public:
24.523 - virtual void copy(const Digraph& from, const RefMap& refMap) = 0;
24.524 -
24.525 - virtual ~MapCopyBase() {}
24.526 - };
24.527 -
24.528 - template <typename Digraph, typename Item, typename RefMap,
24.529 - typename ToMap, typename FromMap>
24.530 - class MapCopy : public MapCopyBase<Digraph, Item, RefMap> {
24.531 - public:
24.532 -
24.533 - MapCopy(ToMap& tmap, const FromMap& map)
24.534 - : _tmap(tmap), _map(map) {}
24.535 -
24.536 - virtual void copy(const Digraph& digraph, const RefMap& refMap) {
24.537 - typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
24.538 - for (ItemIt it(digraph); it != INVALID; ++it) {
24.539 - _tmap.set(refMap[it], _map[it]);
24.540 - }
24.541 - }
24.542 -
24.543 - private:
24.544 - ToMap& _tmap;
24.545 - const FromMap& _map;
24.546 - };
24.547 -
24.548 - template <typename Digraph, typename Item, typename RefMap, typename It>
24.549 - class ItemCopy : public MapCopyBase<Digraph, Item, RefMap> {
24.550 - public:
24.551 -
24.552 - ItemCopy(It& it, const Item& item) : _it(it), _item(item) {}
24.553 -
24.554 - virtual void copy(const Digraph&, const RefMap& refMap) {
24.555 - _it = refMap[_item];
24.556 - }
24.557 -
24.558 - private:
24.559 - It& _it;
24.560 - Item _item;
24.561 - };
24.562 -
24.563 - template <typename Digraph, typename Item, typename RefMap, typename Ref>
24.564 - class RefCopy : public MapCopyBase<Digraph, Item, RefMap> {
24.565 - public:
24.566 -
24.567 - RefCopy(Ref& map) : _map(map) {}
24.568 -
24.569 - virtual void copy(const Digraph& digraph, const RefMap& refMap) {
24.570 - typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
24.571 - for (ItemIt it(digraph); it != INVALID; ++it) {
24.572 - _map.set(it, refMap[it]);
24.573 - }
24.574 - }
24.575 -
24.576 - private:
24.577 - Ref& _map;
24.578 - };
24.579 -
24.580 - template <typename Digraph, typename Item, typename RefMap,
24.581 - typename CrossRef>
24.582 - class CrossRefCopy : public MapCopyBase<Digraph, Item, RefMap> {
24.583 - public:
24.584 -
24.585 - CrossRefCopy(CrossRef& cmap) : _cmap(cmap) {}
24.586 -
24.587 - virtual void copy(const Digraph& digraph, const RefMap& refMap) {
24.588 - typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
24.589 - for (ItemIt it(digraph); it != INVALID; ++it) {
24.590 - _cmap.set(refMap[it], it);
24.591 - }
24.592 - }
24.593 -
24.594 - private:
24.595 - CrossRef& _cmap;
24.596 - };
24.597 -
24.598 - template <typename Digraph, typename Enable = void>
24.599 - struct DigraphCopySelector {
24.600 - template <typename From, typename NodeRefMap, typename ArcRefMap>
24.601 - static void copy(Digraph &to, const From& from,
24.602 - NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) {
24.603 - for (typename From::NodeIt it(from); it != INVALID; ++it) {
24.604 - nodeRefMap[it] = to.addNode();
24.605 - }
24.606 - for (typename From::ArcIt it(from); it != INVALID; ++it) {
24.607 - arcRefMap[it] = to.addArc(nodeRefMap[from.source(it)],
24.608 - nodeRefMap[from.target(it)]);
24.609 - }
24.610 - }
24.611 - };
24.612 -
24.613 - template <typename Digraph>
24.614 - struct DigraphCopySelector<
24.615 - Digraph,
24.616 - typename enable_if<typename Digraph::BuildTag, void>::type>
24.617 - {
24.618 - template <typename From, typename NodeRefMap, typename ArcRefMap>
24.619 - static void copy(Digraph &to, const From& from,
24.620 - NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) {
24.621 - to.build(from, nodeRefMap, arcRefMap);
24.622 - }
24.623 - };
24.624 -
24.625 - template <typename Graph, typename Enable = void>
24.626 - struct GraphCopySelector {
24.627 - template <typename From, typename NodeRefMap, typename EdgeRefMap>
24.628 - static void copy(Graph &to, const From& from,
24.629 - NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
24.630 - for (typename From::NodeIt it(from); it != INVALID; ++it) {
24.631 - nodeRefMap[it] = to.addNode();
24.632 - }
24.633 - for (typename From::EdgeIt it(from); it != INVALID; ++it) {
24.634 - edgeRefMap[it] = to.addEdge(nodeRefMap[from.u(it)],
24.635 - nodeRefMap[from.v(it)]);
24.636 - }
24.637 - }
24.638 - };
24.639 -
24.640 - template <typename Graph>
24.641 - struct GraphCopySelector<
24.642 - Graph,
24.643 - typename enable_if<typename Graph::BuildTag, void>::type>
24.644 - {
24.645 - template <typename From, typename NodeRefMap, typename EdgeRefMap>
24.646 - static void copy(Graph &to, const From& from,
24.647 - NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
24.648 - to.build(from, nodeRefMap, edgeRefMap);
24.649 - }
24.650 - };
24.651 -
24.652 - }
24.653 -
24.654 - /// \brief Class to copy a digraph.
24.655 - ///
24.656 - /// Class to copy a digraph to another digraph (duplicate a digraph). The
24.657 - /// simplest way of using it is through the \c copyDigraph() function.
24.658 - ///
24.659 - /// This class not just make a copy of a graph, but it can create
24.660 - /// references and cross references between the nodes and arcs of
24.661 - /// the two graphs, it can copy maps for use with the newly created
24.662 - /// graph and copy nodes and arcs.
24.663 - ///
24.664 - /// To make a copy from a graph, first an instance of DigraphCopy
24.665 - /// should be created, then the data belongs to the graph should
24.666 - /// assigned to copy. In the end, the \c run() member should be
24.667 - /// called.
24.668 - ///
24.669 - /// The next code copies a graph with several data:
24.670 - ///\code
24.671 - /// DigraphCopy<NewGraph, OrigGraph> dc(new_graph, orig_graph);
24.672 - /// // create a reference for the nodes
24.673 - /// OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph);
24.674 - /// dc.nodeRef(nr);
24.675 - /// // create a cross reference (inverse) for the arcs
24.676 - /// NewGraph::ArcMap<OrigGraph::Arc> acr(new_graph);
24.677 - /// dc.arcCrossRef(acr);
24.678 - /// // copy an arc map
24.679 - /// OrigGraph::ArcMap<double> oamap(orig_graph);
24.680 - /// NewGraph::ArcMap<double> namap(new_graph);
24.681 - /// dc.arcMap(namap, oamap);
24.682 - /// // copy a node
24.683 - /// OrigGraph::Node on;
24.684 - /// NewGraph::Node nn;
24.685 - /// dc.node(nn, on);
24.686 - /// // Executions of copy
24.687 - /// dc.run();
24.688 - ///\endcode
24.689 - template <typename To, typename From>
24.690 - class DigraphCopy {
24.691 - private:
24.692 -
24.693 - typedef typename From::Node Node;
24.694 - typedef typename From::NodeIt NodeIt;
24.695 - typedef typename From::Arc Arc;
24.696 - typedef typename From::ArcIt ArcIt;
24.697 -
24.698 - typedef typename To::Node TNode;
24.699 - typedef typename To::Arc TArc;
24.700 -
24.701 - typedef typename From::template NodeMap<TNode> NodeRefMap;
24.702 - typedef typename From::template ArcMap<TArc> ArcRefMap;
24.703 -
24.704 -
24.705 - public:
24.706 -
24.707 -
24.708 - /// \brief Constructor for the DigraphCopy.
24.709 - ///
24.710 - /// It copies the content of the \c _from digraph into the
24.711 - /// \c _to digraph.
24.712 - DigraphCopy(To& to, const From& from)
24.713 - : _from(from), _to(to) {}
24.714 -
24.715 - /// \brief Destructor of the DigraphCopy
24.716 - ///
24.717 - /// Destructor of the DigraphCopy
24.718 - ~DigraphCopy() {
24.719 - for (int i = 0; i < int(_node_maps.size()); ++i) {
24.720 - delete _node_maps[i];
24.721 - }
24.722 - for (int i = 0; i < int(_arc_maps.size()); ++i) {
24.723 - delete _arc_maps[i];
24.724 - }
24.725 -
24.726 - }
24.727 -
24.728 - /// \brief Copies the node references into the given map.
24.729 - ///
24.730 - /// Copies the node references into the given map. The parameter
24.731 - /// should be a map, which key type is the Node type of the source
24.732 - /// graph, while the value type is the Node type of the
24.733 - /// destination graph.
24.734 - template <typename NodeRef>
24.735 - DigraphCopy& nodeRef(NodeRef& map) {
24.736 - _node_maps.push_back(new _graph_utils_bits::RefCopy<From, Node,
24.737 - NodeRefMap, NodeRef>(map));
24.738 - return *this;
24.739 - }
24.740 -
24.741 - /// \brief Copies the node cross references into the given map.
24.742 - ///
24.743 - /// Copies the node cross references (reverse references) into
24.744 - /// the given map. The parameter should be a map, which key type
24.745 - /// is the Node type of the destination graph, while the value type is
24.746 - /// the Node type of the source graph.
24.747 - template <typename NodeCrossRef>
24.748 - DigraphCopy& nodeCrossRef(NodeCrossRef& map) {
24.749 - _node_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Node,
24.750 - NodeRefMap, NodeCrossRef>(map));
24.751 - return *this;
24.752 - }
24.753 -
24.754 - /// \brief Make copy of the given map.
24.755 - ///
24.756 - /// Makes copy of the given map for the newly created digraph.
24.757 - /// The new map's key type is the destination graph's node type,
24.758 - /// and the copied map's key type is the source graph's node type.
24.759 - template <typename ToMap, typename FromMap>
24.760 - DigraphCopy& nodeMap(ToMap& tmap, const FromMap& map) {
24.761 - _node_maps.push_back(new _graph_utils_bits::MapCopy<From, Node,
24.762 - NodeRefMap, ToMap, FromMap>(tmap, map));
24.763 - return *this;
24.764 - }
24.765 -
24.766 - /// \brief Make a copy of the given node.
24.767 - ///
24.768 - /// Make a copy of the given node.
24.769 - DigraphCopy& node(TNode& tnode, const Node& snode) {
24.770 - _node_maps.push_back(new _graph_utils_bits::ItemCopy<From, Node,
24.771 - NodeRefMap, TNode>(tnode, snode));
24.772 - return *this;
24.773 - }
24.774 -
24.775 - /// \brief Copies the arc references into the given map.
24.776 - ///
24.777 - /// Copies the arc references into the given map.
24.778 - template <typename ArcRef>
24.779 - DigraphCopy& arcRef(ArcRef& map) {
24.780 - _arc_maps.push_back(new _graph_utils_bits::RefCopy<From, Arc,
24.781 - ArcRefMap, ArcRef>(map));
24.782 - return *this;
24.783 - }
24.784 -
24.785 - /// \brief Copies the arc cross references into the given map.
24.786 - ///
24.787 - /// Copies the arc cross references (reverse references) into
24.788 - /// the given map.
24.789 - template <typename ArcCrossRef>
24.790 - DigraphCopy& arcCrossRef(ArcCrossRef& map) {
24.791 - _arc_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Arc,
24.792 - ArcRefMap, ArcCrossRef>(map));
24.793 - return *this;
24.794 - }
24.795 -
24.796 - /// \brief Make copy of the given map.
24.797 - ///
24.798 - /// Makes copy of the given map for the newly created digraph.
24.799 - /// The new map's key type is the to digraph's arc type,
24.800 - /// and the copied map's key type is the from digraph's arc
24.801 - /// type.
24.802 - template <typename ToMap, typename FromMap>
24.803 - DigraphCopy& arcMap(ToMap& tmap, const FromMap& map) {
24.804 - _arc_maps.push_back(new _graph_utils_bits::MapCopy<From, Arc,
24.805 - ArcRefMap, ToMap, FromMap>(tmap, map));
24.806 - return *this;
24.807 - }
24.808 -
24.809 - /// \brief Make a copy of the given arc.
24.810 - ///
24.811 - /// Make a copy of the given arc.
24.812 - DigraphCopy& arc(TArc& tarc, const Arc& sarc) {
24.813 - _arc_maps.push_back(new _graph_utils_bits::ItemCopy<From, Arc,
24.814 - ArcRefMap, TArc>(tarc, sarc));
24.815 - return *this;
24.816 - }
24.817 -
24.818 - /// \brief Executes the copies.
24.819 - ///
24.820 - /// Executes the copies.
24.821 - void run() {
24.822 - NodeRefMap nodeRefMap(_from);
24.823 - ArcRefMap arcRefMap(_from);
24.824 - _graph_utils_bits::DigraphCopySelector<To>::
24.825 - copy(_to, _from, nodeRefMap, arcRefMap);
24.826 - for (int i = 0; i < int(_node_maps.size()); ++i) {
24.827 - _node_maps[i]->copy(_from, nodeRefMap);
24.828 - }
24.829 - for (int i = 0; i < int(_arc_maps.size()); ++i) {
24.830 - _arc_maps[i]->copy(_from, arcRefMap);
24.831 - }
24.832 - }
24.833 -
24.834 - protected:
24.835 -
24.836 -
24.837 - const From& _from;
24.838 - To& _to;
24.839 -
24.840 - std::vector<_graph_utils_bits::MapCopyBase<From, Node, NodeRefMap>* >
24.841 - _node_maps;
24.842 -
24.843 - std::vector<_graph_utils_bits::MapCopyBase<From, Arc, ArcRefMap>* >
24.844 - _arc_maps;
24.845 -
24.846 - };
24.847 -
24.848 - /// \brief Copy a digraph to another digraph.
24.849 - ///
24.850 - /// Copy a digraph to another digraph. The complete usage of the
24.851 - /// function is detailed in the DigraphCopy class, but a short
24.852 - /// example shows a basic work:
24.853 - ///\code
24.854 - /// copyDigraph(trg, src).nodeRef(nr).arcCrossRef(ecr).run();
24.855 - ///\endcode
24.856 - ///
24.857 - /// After the copy the \c nr map will contain the mapping from the
24.858 - /// nodes of the \c from digraph to the nodes of the \c to digraph and
24.859 - /// \c ecr will contain the mapping from the arcs of the \c to digraph
24.860 - /// to the arcs of the \c from digraph.
24.861 - ///
24.862 - /// \see DigraphCopy
24.863 - template <typename To, typename From>
24.864 - DigraphCopy<To, From> copyDigraph(To& to, const From& from) {
24.865 - return DigraphCopy<To, From>(to, from);
24.866 - }
24.867 -
24.868 - /// \brief Class to copy a graph.
24.869 - ///
24.870 - /// Class to copy a graph to another graph (duplicate a graph). The
24.871 - /// simplest way of using it is through the \c copyGraph() function.
24.872 - ///
24.873 - /// This class not just make a copy of a graph, but it can create
24.874 - /// references and cross references between the nodes, edges and arcs of
24.875 - /// the two graphs, it can copy maps for use with the newly created
24.876 - /// graph and copy nodes, edges and arcs.
24.877 - ///
24.878 - /// To make a copy from a graph, first an instance of GraphCopy
24.879 - /// should be created, then the data belongs to the graph should
24.880 - /// assigned to copy. In the end, the \c run() member should be
24.881 - /// called.
24.882 - ///
24.883 - /// The next code copies a graph with several data:
24.884 - ///\code
24.885 - /// GraphCopy<NewGraph, OrigGraph> dc(new_graph, orig_graph);
24.886 - /// // create a reference for the nodes
24.887 - /// OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph);
24.888 - /// dc.nodeRef(nr);
24.889 - /// // create a cross reference (inverse) for the edges
24.890 - /// NewGraph::EdgeMap<OrigGraph::Arc> ecr(new_graph);
24.891 - /// dc.edgeCrossRef(ecr);
24.892 - /// // copy an arc map
24.893 - /// OrigGraph::ArcMap<double> oamap(orig_graph);
24.894 - /// NewGraph::ArcMap<double> namap(new_graph);
24.895 - /// dc.arcMap(namap, oamap);
24.896 - /// // copy a node
24.897 - /// OrigGraph::Node on;
24.898 - /// NewGraph::Node nn;
24.899 - /// dc.node(nn, on);
24.900 - /// // Executions of copy
24.901 - /// dc.run();
24.902 - ///\endcode
24.903 - template <typename To, typename From>
24.904 - class GraphCopy {
24.905 - private:
24.906 -
24.907 - typedef typename From::Node Node;
24.908 - typedef typename From::NodeIt NodeIt;
24.909 - typedef typename From::Arc Arc;
24.910 - typedef typename From::ArcIt ArcIt;
24.911 - typedef typename From::Edge Edge;
24.912 - typedef typename From::EdgeIt EdgeIt;
24.913 -
24.914 - typedef typename To::Node TNode;
24.915 - typedef typename To::Arc TArc;
24.916 - typedef typename To::Edge TEdge;
24.917 -
24.918 - typedef typename From::template NodeMap<TNode> NodeRefMap;
24.919 - typedef typename From::template EdgeMap<TEdge> EdgeRefMap;
24.920 -
24.921 - struct ArcRefMap {
24.922 - ArcRefMap(const To& to, const From& from,
24.923 - const EdgeRefMap& edge_ref, const NodeRefMap& node_ref)
24.924 - : _to(to), _from(from),
24.925 - _edge_ref(edge_ref), _node_ref(node_ref) {}
24.926 -
24.927 - typedef typename From::Arc Key;
24.928 - typedef typename To::Arc Value;
24.929 -
24.930 - Value operator[](const Key& key) const {
24.931 - bool forward = _from.u(key) != _from.v(key) ?
24.932 - _node_ref[_from.source(key)] ==
24.933 - _to.source(_to.direct(_edge_ref[key], true)) :
24.934 - _from.direction(key);
24.935 - return _to.direct(_edge_ref[key], forward);
24.936 - }
24.937 -
24.938 - const To& _to;
24.939 - const From& _from;
24.940 - const EdgeRefMap& _edge_ref;
24.941 - const NodeRefMap& _node_ref;
24.942 - };
24.943 -
24.944 -
24.945 - public:
24.946 -
24.947 -
24.948 - /// \brief Constructor for the GraphCopy.
24.949 - ///
24.950 - /// It copies the content of the \c _from graph into the
24.951 - /// \c _to graph.
24.952 - GraphCopy(To& to, const From& from)
24.953 - : _from(from), _to(to) {}
24.954 -
24.955 - /// \brief Destructor of the GraphCopy
24.956 - ///
24.957 - /// Destructor of the GraphCopy
24.958 - ~GraphCopy() {
24.959 - for (int i = 0; i < int(_node_maps.size()); ++i) {
24.960 - delete _node_maps[i];
24.961 - }
24.962 - for (int i = 0; i < int(_arc_maps.size()); ++i) {
24.963 - delete _arc_maps[i];
24.964 - }
24.965 - for (int i = 0; i < int(_edge_maps.size()); ++i) {
24.966 - delete _edge_maps[i];
24.967 - }
24.968 -
24.969 - }
24.970 -
24.971 - /// \brief Copies the node references into the given map.
24.972 - ///
24.973 - /// Copies the node references into the given map.
24.974 - template <typename NodeRef>
24.975 - GraphCopy& nodeRef(NodeRef& map) {
24.976 - _node_maps.push_back(new _graph_utils_bits::RefCopy<From, Node,
24.977 - NodeRefMap, NodeRef>(map));
24.978 - return *this;
24.979 - }
24.980 -
24.981 - /// \brief Copies the node cross references into the given map.
24.982 - ///
24.983 - /// Copies the node cross references (reverse references) into
24.984 - /// the given map.
24.985 - template <typename NodeCrossRef>
24.986 - GraphCopy& nodeCrossRef(NodeCrossRef& map) {
24.987 - _node_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Node,
24.988 - NodeRefMap, NodeCrossRef>(map));
24.989 - return *this;
24.990 - }
24.991 -
24.992 - /// \brief Make copy of the given map.
24.993 - ///
24.994 - /// Makes copy of the given map for the newly created graph.
24.995 - /// The new map's key type is the to graph's node type,
24.996 - /// and the copied map's key type is the from graph's node
24.997 - /// type.
24.998 - template <typename ToMap, typename FromMap>
24.999 - GraphCopy& nodeMap(ToMap& tmap, const FromMap& map) {
24.1000 - _node_maps.push_back(new _graph_utils_bits::MapCopy<From, Node,
24.1001 - NodeRefMap, ToMap, FromMap>(tmap, map));
24.1002 - return *this;
24.1003 - }
24.1004 -
24.1005 - /// \brief Make a copy of the given node.
24.1006 - ///
24.1007 - /// Make a copy of the given node.
24.1008 - GraphCopy& node(TNode& tnode, const Node& snode) {
24.1009 - _node_maps.push_back(new _graph_utils_bits::ItemCopy<From, Node,
24.1010 - NodeRefMap, TNode>(tnode, snode));
24.1011 - return *this;
24.1012 - }
24.1013 -
24.1014 - /// \brief Copies the arc references into the given map.
24.1015 - ///
24.1016 - /// Copies the arc references into the given map.
24.1017 - template <typename ArcRef>
24.1018 - GraphCopy& arcRef(ArcRef& map) {
24.1019 - _arc_maps.push_back(new _graph_utils_bits::RefCopy<From, Arc,
24.1020 - ArcRefMap, ArcRef>(map));
24.1021 - return *this;
24.1022 - }
24.1023 -
24.1024 - /// \brief Copies the arc cross references into the given map.
24.1025 - ///
24.1026 - /// Copies the arc cross references (reverse references) into
24.1027 - /// the given map.
24.1028 - template <typename ArcCrossRef>
24.1029 - GraphCopy& arcCrossRef(ArcCrossRef& map) {
24.1030 - _arc_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Arc,
24.1031 - ArcRefMap, ArcCrossRef>(map));
24.1032 - return *this;
24.1033 - }
24.1034 -
24.1035 - /// \brief Make copy of the given map.
24.1036 - ///
24.1037 - /// Makes copy of the given map for the newly created graph.
24.1038 - /// The new map's key type is the to graph's arc type,
24.1039 - /// and the copied map's key type is the from graph's arc
24.1040 - /// type.
24.1041 - template <typename ToMap, typename FromMap>
24.1042 - GraphCopy& arcMap(ToMap& tmap, const FromMap& map) {
24.1043 - _arc_maps.push_back(new _graph_utils_bits::MapCopy<From, Arc,
24.1044 - ArcRefMap, ToMap, FromMap>(tmap, map));
24.1045 - return *this;
24.1046 - }
24.1047 -
24.1048 - /// \brief Make a copy of the given arc.
24.1049 - ///
24.1050 - /// Make a copy of the given arc.
24.1051 - GraphCopy& arc(TArc& tarc, const Arc& sarc) {
24.1052 - _arc_maps.push_back(new _graph_utils_bits::ItemCopy<From, Arc,
24.1053 - ArcRefMap, TArc>(tarc, sarc));
24.1054 - return *this;
24.1055 - }
24.1056 -
24.1057 - /// \brief Copies the edge references into the given map.
24.1058 - ///
24.1059 - /// Copies the edge references into the given map.
24.1060 - template <typename EdgeRef>
24.1061 - GraphCopy& edgeRef(EdgeRef& map) {
24.1062 - _edge_maps.push_back(new _graph_utils_bits::RefCopy<From, Edge,
24.1063 - EdgeRefMap, EdgeRef>(map));
24.1064 - return *this;
24.1065 - }
24.1066 -
24.1067 - /// \brief Copies the edge cross references into the given map.
24.1068 - ///
24.1069 - /// Copies the edge cross references (reverse
24.1070 - /// references) into the given map.
24.1071 - template <typename EdgeCrossRef>
24.1072 - GraphCopy& edgeCrossRef(EdgeCrossRef& map) {
24.1073 - _edge_maps.push_back(new _graph_utils_bits::CrossRefCopy<From,
24.1074 - Edge, EdgeRefMap, EdgeCrossRef>(map));
24.1075 - return *this;
24.1076 - }
24.1077 -
24.1078 - /// \brief Make copy of the given map.
24.1079 - ///
24.1080 - /// Makes copy of the given map for the newly created graph.
24.1081 - /// The new map's key type is the to graph's edge type,
24.1082 - /// and the copied map's key type is the from graph's edge
24.1083 - /// type.
24.1084 - template <typename ToMap, typename FromMap>
24.1085 - GraphCopy& edgeMap(ToMap& tmap, const FromMap& map) {
24.1086 - _edge_maps.push_back(new _graph_utils_bits::MapCopy<From, Edge,
24.1087 - EdgeRefMap, ToMap, FromMap>(tmap, map));
24.1088 - return *this;
24.1089 - }
24.1090 -
24.1091 - /// \brief Make a copy of the given edge.
24.1092 - ///
24.1093 - /// Make a copy of the given edge.
24.1094 - GraphCopy& edge(TEdge& tedge, const Edge& sedge) {
24.1095 - _edge_maps.push_back(new _graph_utils_bits::ItemCopy<From, Edge,
24.1096 - EdgeRefMap, TEdge>(tedge, sedge));
24.1097 - return *this;
24.1098 - }
24.1099 -
24.1100 - /// \brief Executes the copies.
24.1101 - ///
24.1102 - /// Executes the copies.
24.1103 - void run() {
24.1104 - NodeRefMap nodeRefMap(_from);
24.1105 - EdgeRefMap edgeRefMap(_from);
24.1106 - ArcRefMap arcRefMap(_to, _from, edgeRefMap, nodeRefMap);
24.1107 - _graph_utils_bits::GraphCopySelector<To>::
24.1108 - copy(_to, _from, nodeRefMap, edgeRefMap);
24.1109 - for (int i = 0; i < int(_node_maps.size()); ++i) {
24.1110 - _node_maps[i]->copy(_from, nodeRefMap);
24.1111 - }
24.1112 - for (int i = 0; i < int(_edge_maps.size()); ++i) {
24.1113 - _edge_maps[i]->copy(_from, edgeRefMap);
24.1114 - }
24.1115 - for (int i = 0; i < int(_arc_maps.size()); ++i) {
24.1116 - _arc_maps[i]->copy(_from, arcRefMap);
24.1117 - }
24.1118 - }
24.1119 -
24.1120 - private:
24.1121 -
24.1122 - const From& _from;
24.1123 - To& _to;
24.1124 -
24.1125 - std::vector<_graph_utils_bits::MapCopyBase<From, Node, NodeRefMap>* >
24.1126 - _node_maps;
24.1127 -
24.1128 - std::vector<_graph_utils_bits::MapCopyBase<From, Arc, ArcRefMap>* >
24.1129 - _arc_maps;
24.1130 -
24.1131 - std::vector<_graph_utils_bits::MapCopyBase<From, Edge, EdgeRefMap>* >
24.1132 - _edge_maps;
24.1133 -
24.1134 - };
24.1135 -
24.1136 - /// \brief Copy a graph to another graph.
24.1137 - ///
24.1138 - /// Copy a graph to another graph. The complete usage of the
24.1139 - /// function is detailed in the GraphCopy class, but a short
24.1140 - /// example shows a basic work:
24.1141 - ///\code
24.1142 - /// copyGraph(trg, src).nodeRef(nr).arcCrossRef(ecr).run();
24.1143 - ///\endcode
24.1144 - ///
24.1145 - /// After the copy the \c nr map will contain the mapping from the
24.1146 - /// nodes of the \c from graph to the nodes of the \c to graph and
24.1147 - /// \c ecr will contain the mapping from the arcs of the \c to graph
24.1148 - /// to the arcs of the \c from graph.
24.1149 - ///
24.1150 - /// \see GraphCopy
24.1151 - template <typename To, typename From>
24.1152 - GraphCopy<To, From>
24.1153 - copyGraph(To& to, const From& from) {
24.1154 - return GraphCopy<To, From>(to, from);
24.1155 - }
24.1156 -
24.1157 - /// @}
24.1158 -
24.1159 - /// \addtogroup graph_maps
24.1160 - /// @{
24.1161 -
24.1162 - /// Provides an immutable and unique id for each item in the graph.
24.1163 -
24.1164 - /// The IdMap class provides a unique and immutable id for each item of the
24.1165 - /// same type (e.g. node) in the graph. This id is <ul><li>\b unique:
24.1166 - /// different items (nodes) get different ids <li>\b immutable: the id of an
24.1167 - /// item (node) does not change (even if you delete other nodes). </ul>
24.1168 - /// Through this map you get access (i.e. can read) the inner id values of
24.1169 - /// the items stored in the graph. This map can be inverted with its member
24.1170 - /// class \c InverseMap or with the \c operator() member.
24.1171 - ///
24.1172 - template <typename _Graph, typename _Item>
24.1173 - class IdMap {
24.1174 - public:
24.1175 - typedef _Graph Graph;
24.1176 - typedef int Value;
24.1177 - typedef _Item Item;
24.1178 - typedef _Item Key;
24.1179 -
24.1180 - /// \brief Constructor.
24.1181 - ///
24.1182 - /// Constructor of the map.
24.1183 - explicit IdMap(const Graph& graph) : _graph(&graph) {}
24.1184 -
24.1185 - /// \brief Gives back the \e id of the item.
24.1186 - ///
24.1187 - /// Gives back the immutable and unique \e id of the item.
24.1188 - int operator[](const Item& item) const { return _graph->id(item);}
24.1189 -
24.1190 - /// \brief Gives back the item by its id.
24.1191 - ///
24.1192 - /// Gives back the item by its id.
24.1193 - Item operator()(int id) { return _graph->fromId(id, Item()); }
24.1194 -
24.1195 - private:
24.1196 - const Graph* _graph;
24.1197 -
24.1198 - public:
24.1199 -
24.1200 - /// \brief The class represents the inverse of its owner (IdMap).
24.1201 - ///
24.1202 - /// The class represents the inverse of its owner (IdMap).
24.1203 - /// \see inverse()
24.1204 - class InverseMap {
24.1205 - public:
24.1206 -
24.1207 - /// \brief Constructor.
24.1208 - ///
24.1209 - /// Constructor for creating an id-to-item map.
24.1210 - explicit InverseMap(const Graph& graph) : _graph(&graph) {}
24.1211 -
24.1212 - /// \brief Constructor.
24.1213 - ///
24.1214 - /// Constructor for creating an id-to-item map.
24.1215 - explicit InverseMap(const IdMap& map) : _graph(map._graph) {}
24.1216 -
24.1217 - /// \brief Gives back the given item from its id.
24.1218 - ///
24.1219 - /// Gives back the given item from its id.
24.1220 - ///
24.1221 - Item operator[](int id) const { return _graph->fromId(id, Item());}
24.1222 -
24.1223 - private:
24.1224 - const Graph* _graph;
24.1225 - };
24.1226 -
24.1227 - /// \brief Gives back the inverse of the map.
24.1228 - ///
24.1229 - /// Gives back the inverse of the IdMap.
24.1230 - InverseMap inverse() const { return InverseMap(*_graph);}
24.1231 -
24.1232 - };
24.1233 -
24.1234 -
24.1235 - /// \brief General invertable graph-map type.
24.1236 -
24.1237 - /// This type provides simple invertable graph-maps.
24.1238 - /// The InvertableMap wraps an arbitrary ReadWriteMap
24.1239 - /// and if a key is set to a new value then store it
24.1240 - /// in the inverse map.
24.1241 - ///
24.1242 - /// The values of the map can be accessed
24.1243 - /// with stl compatible forward iterator.
24.1244 - ///
24.1245 - /// \tparam _Graph The graph type.
24.1246 - /// \tparam _Item The item type of the graph.
24.1247 - /// \tparam _Value The value type of the map.
24.1248 - ///
24.1249 - /// \see IterableValueMap
24.1250 - template <typename _Graph, typename _Item, typename _Value>
24.1251 - class InvertableMap : protected DefaultMap<_Graph, _Item, _Value> {
24.1252 - private:
24.1253 -
24.1254 - typedef DefaultMap<_Graph, _Item, _Value> Map;
24.1255 - typedef _Graph Graph;
24.1256 -
24.1257 - typedef std::map<_Value, _Item> Container;
24.1258 - Container _inv_map;
24.1259 -
24.1260 - public:
24.1261 -
24.1262 - /// The key type of InvertableMap (Node, Arc, Edge).
24.1263 - typedef typename Map::Key Key;
24.1264 - /// The value type of the InvertableMap.
24.1265 - typedef typename Map::Value Value;
24.1266 -
24.1267 -
24.1268 -
24.1269 - /// \brief Constructor.
24.1270 - ///
24.1271 - /// Construct a new InvertableMap for the graph.
24.1272 - ///
24.1273 - explicit InvertableMap(const Graph& graph) : Map(graph) {}
24.1274 -
24.1275 - /// \brief Forward iterator for values.
24.1276 - ///
24.1277 - /// This iterator is an stl compatible forward
24.1278 - /// iterator on the values of the map. The values can
24.1279 - /// be accessed in the [beginValue, endValue) range.
24.1280 - ///
24.1281 - class ValueIterator
24.1282 - : public std::iterator<std::forward_iterator_tag, Value> {
24.1283 - friend class InvertableMap;
24.1284 - private:
24.1285 - ValueIterator(typename Container::const_iterator _it)
24.1286 - : it(_it) {}
24.1287 - public:
24.1288 -
24.1289 - ValueIterator() {}
24.1290 -
24.1291 - ValueIterator& operator++() { ++it; return *this; }
24.1292 - ValueIterator operator++(int) {
24.1293 - ValueIterator tmp(*this);
24.1294 - operator++();
24.1295 - return tmp;
24.1296 - }
24.1297 -
24.1298 - const Value& operator*() const { return it->first; }
24.1299 - const Value* operator->() const { return &(it->first); }
24.1300 -
24.1301 - bool operator==(ValueIterator jt) const { return it == jt.it; }
24.1302 - bool operator!=(ValueIterator jt) const { return it != jt.it; }
24.1303 -
24.1304 - private:
24.1305 - typename Container::const_iterator it;
24.1306 - };
24.1307 -
24.1308 - /// \brief Returns an iterator to the first value.
24.1309 - ///
24.1310 - /// Returns an stl compatible iterator to the
24.1311 - /// first value of the map. The values of the
24.1312 - /// map can be accessed in the [beginValue, endValue)
24.1313 - /// range.
24.1314 - ValueIterator beginValue() const {
24.1315 - return ValueIterator(_inv_map.begin());
24.1316 - }
24.1317 -
24.1318 - /// \brief Returns an iterator after the last value.
24.1319 - ///
24.1320 - /// Returns an stl compatible iterator after the
24.1321 - /// last value of the map. The values of the
24.1322 - /// map can be accessed in the [beginValue, endValue)
24.1323 - /// range.
24.1324 - ValueIterator endValue() const {
24.1325 - return ValueIterator(_inv_map.end());
24.1326 - }
24.1327 -
24.1328 - /// \brief The setter function of the map.
24.1329 - ///
24.1330 - /// Sets the mapped value.
24.1331 - void set(const Key& key, const Value& val) {
24.1332 - Value oldval = Map::operator[](key);
24.1333 - typename Container::iterator it = _inv_map.find(oldval);
24.1334 - if (it != _inv_map.end() && it->second == key) {
24.1335 - _inv_map.erase(it);
24.1336 - }
24.1337 - _inv_map.insert(make_pair(val, key));
24.1338 - Map::set(key, val);
24.1339 - }
24.1340 -
24.1341 - /// \brief The getter function of the map.
24.1342 - ///
24.1343 - /// It gives back the value associated with the key.
24.1344 - typename MapTraits<Map>::ConstReturnValue
24.1345 - operator[](const Key& key) const {
24.1346 - return Map::operator[](key);
24.1347 - }
24.1348 -
24.1349 - /// \brief Gives back the item by its value.
24.1350 - ///
24.1351 - /// Gives back the item by its value.
24.1352 - Key operator()(const Value& key) const {
24.1353 - typename Container::const_iterator it = _inv_map.find(key);
24.1354 - return it != _inv_map.end() ? it->second : INVALID;
24.1355 - }
24.1356 -
24.1357 - protected:
24.1358 -
24.1359 - /// \brief Erase the key from the map.
24.1360 - ///
24.1361 - /// Erase the key to the map. It is called by the
24.1362 - /// \c AlterationNotifier.
24.1363 - virtual void erase(const Key& key) {
24.1364 - Value val = Map::operator[](key);
24.1365 - typename Container::iterator it = _inv_map.find(val);
24.1366 - if (it != _inv_map.end() && it->second == key) {
24.1367 - _inv_map.erase(it);
24.1368 - }
24.1369 - Map::erase(key);
24.1370 - }
24.1371 -
24.1372 - /// \brief Erase more keys from the map.
24.1373 - ///
24.1374 - /// Erase more keys from the map. It is called by the
24.1375 - /// \c AlterationNotifier.
24.1376 - virtual void erase(const std::vector<Key>& keys) {
24.1377 - for (int i = 0; i < int(keys.size()); ++i) {
24.1378 - Value val = Map::operator[](keys[i]);
24.1379 - typename Container::iterator it = _inv_map.find(val);
24.1380 - if (it != _inv_map.end() && it->second == keys[i]) {
24.1381 - _inv_map.erase(it);
24.1382 - }
24.1383 - }
24.1384 - Map::erase(keys);
24.1385 - }
24.1386 -
24.1387 - /// \brief Clear the keys from the map and inverse map.
24.1388 - ///
24.1389 - /// Clear the keys from the map and inverse map. It is called by the
24.1390 - /// \c AlterationNotifier.
24.1391 - virtual void clear() {
24.1392 - _inv_map.clear();
24.1393 - Map::clear();
24.1394 - }
24.1395 -
24.1396 - public:
24.1397 -
24.1398 - /// \brief The inverse map type.
24.1399 - ///
24.1400 - /// The inverse of this map. The subscript operator of the map
24.1401 - /// gives back always the item what was last assigned to the value.
24.1402 - class InverseMap {
24.1403 - public:
24.1404 - /// \brief Constructor of the InverseMap.
24.1405 - ///
24.1406 - /// Constructor of the InverseMap.
24.1407 - explicit InverseMap(const InvertableMap& inverted)
24.1408 - : _inverted(inverted) {}
24.1409 -
24.1410 - /// The value type of the InverseMap.
24.1411 - typedef typename InvertableMap::Key Value;
24.1412 - /// The key type of the InverseMap.
24.1413 - typedef typename InvertableMap::Value Key;
24.1414 -
24.1415 - /// \brief Subscript operator.
24.1416 - ///
24.1417 - /// Subscript operator. It gives back always the item
24.1418 - /// what was last assigned to the value.
24.1419 - Value operator[](const Key& key) const {
24.1420 - return _inverted(key);
24.1421 - }
24.1422 -
24.1423 - private:
24.1424 - const InvertableMap& _inverted;
24.1425 - };
24.1426 -
24.1427 - /// \brief It gives back the just readable inverse map.
24.1428 - ///
24.1429 - /// It gives back the just readable inverse map.
24.1430 - InverseMap inverse() const {
24.1431 - return InverseMap(*this);
24.1432 - }
24.1433 -
24.1434 -
24.1435 -
24.1436 - };
24.1437 -
24.1438 - /// \brief Provides a mutable, continuous and unique descriptor for each
24.1439 - /// item in the graph.
24.1440 - ///
24.1441 - /// The DescriptorMap class provides a unique and continuous (but mutable)
24.1442 - /// descriptor (id) for each item of the same type (e.g. node) in the
24.1443 - /// graph. This id is <ul><li>\b unique: different items (nodes) get
24.1444 - /// different ids <li>\b continuous: the range of the ids is the set of
24.1445 - /// integers between 0 and \c n-1, where \c n is the number of the items of
24.1446 - /// this type (e.g. nodes) (so the id of a node can change if you delete an
24.1447 - /// other node, i.e. this id is mutable). </ul> This map can be inverted
24.1448 - /// with its member class \c InverseMap, or with the \c operator() member.
24.1449 - ///
24.1450 - /// \tparam _Graph The graph class the \c DescriptorMap belongs to.
24.1451 - /// \tparam _Item The Item is the Key of the Map. It may be Node, Arc or
24.1452 - /// Edge.
24.1453 - template <typename _Graph, typename _Item>
24.1454 - class DescriptorMap : protected DefaultMap<_Graph, _Item, int> {
24.1455 -
24.1456 - typedef _Item Item;
24.1457 - typedef DefaultMap<_Graph, _Item, int> Map;
24.1458 -
24.1459 - public:
24.1460 - /// The graph class of DescriptorMap.
24.1461 - typedef _Graph Graph;
24.1462 -
24.1463 - /// The key type of DescriptorMap (Node, Arc, Edge).
24.1464 - typedef typename Map::Key Key;
24.1465 - /// The value type of DescriptorMap.
24.1466 - typedef typename Map::Value Value;
24.1467 -
24.1468 - /// \brief Constructor.
24.1469 - ///
24.1470 - /// Constructor for descriptor map.
24.1471 - explicit DescriptorMap(const Graph& _graph) : Map(_graph) {
24.1472 - Item it;
24.1473 - const typename Map::Notifier* nf = Map::notifier();
24.1474 - for (nf->first(it); it != INVALID; nf->next(it)) {
24.1475 - Map::set(it, _inv_map.size());
24.1476 - _inv_map.push_back(it);
24.1477 - }
24.1478 - }
24.1479 -
24.1480 - protected:
24.1481 -
24.1482 - /// \brief Add a new key to the map.
24.1483 - ///
24.1484 - /// Add a new key to the map. It is called by the
24.1485 - /// \c AlterationNotifier.
24.1486 - virtual void add(const Item& item) {
24.1487 - Map::add(item);
24.1488 - Map::set(item, _inv_map.size());
24.1489 - _inv_map.push_back(item);
24.1490 - }
24.1491 -
24.1492 - /// \brief Add more new keys to the map.
24.1493 - ///
24.1494 - /// Add more new keys to the map. It is called by the
24.1495 - /// \c AlterationNotifier.
24.1496 - virtual void add(const std::vector<Item>& items) {
24.1497 - Map::add(items);
24.1498 - for (int i = 0; i < int(items.size()); ++i) {
24.1499 - Map::set(items[i], _inv_map.size());
24.1500 - _inv_map.push_back(items[i]);
24.1501 - }
24.1502 - }
24.1503 -
24.1504 - /// \brief Erase the key from the map.
24.1505 - ///
24.1506 - /// Erase the key from the map. It is called by the
24.1507 - /// \c AlterationNotifier.
24.1508 - virtual void erase(const Item& item) {
24.1509 - Map::set(_inv_map.back(), Map::operator[](item));
24.1510 - _inv_map[Map::operator[](item)] = _inv_map.back();
24.1511 - _inv_map.pop_back();
24.1512 - Map::erase(item);
24.1513 - }
24.1514 -
24.1515 - /// \brief Erase more keys from the map.
24.1516 - ///
24.1517 - /// Erase more keys from the map. It is called by the
24.1518 - /// \c AlterationNotifier.
24.1519 - virtual void erase(const std::vector<Item>& items) {
24.1520 - for (int i = 0; i < int(items.size()); ++i) {
24.1521 - Map::set(_inv_map.back(), Map::operator[](items[i]));
24.1522 - _inv_map[Map::operator[](items[i])] = _inv_map.back();
24.1523 - _inv_map.pop_back();
24.1524 - }
24.1525 - Map::erase(items);
24.1526 - }
24.1527 -
24.1528 - /// \brief Build the unique map.
24.1529 - ///
24.1530 - /// Build the unique map. It is called by the
24.1531 - /// \c AlterationNotifier.
24.1532 - virtual void build() {
24.1533 - Map::build();
24.1534 - Item it;
24.1535 - const typename Map::Notifier* nf = Map::notifier();
24.1536 - for (nf->first(it); it != INVALID; nf->next(it)) {
24.1537 - Map::set(it, _inv_map.size());
24.1538 - _inv_map.push_back(it);
24.1539 - }
24.1540 - }
24.1541 -
24.1542 - /// \brief Clear the keys from the map.
24.1543 - ///
24.1544 - /// Clear the keys from the map. It is called by the
24.1545 - /// \c AlterationNotifier.
24.1546 - virtual void clear() {
24.1547 - _inv_map.clear();
24.1548 - Map::clear();
24.1549 - }
24.1550 -
24.1551 - public:
24.1552 -
24.1553 - /// \brief Returns the maximal value plus one.
24.1554 - ///
24.1555 - /// Returns the maximal value plus one in the map.
24.1556 - unsigned int size() const {
24.1557 - return _inv_map.size();
24.1558 - }
24.1559 -
24.1560 - /// \brief Swaps the position of the two items in the map.
24.1561 - ///
24.1562 - /// Swaps the position of the two items in the map.
24.1563 - void swap(const Item& p, const Item& q) {
24.1564 - int pi = Map::operator[](p);
24.1565 - int qi = Map::operator[](q);
24.1566 - Map::set(p, qi);
24.1567 - _inv_map[qi] = p;
24.1568 - Map::set(q, pi);
24.1569 - _inv_map[pi] = q;
24.1570 - }
24.1571 -
24.1572 - /// \brief Gives back the \e descriptor of the item.
24.1573 - ///
24.1574 - /// Gives back the mutable and unique \e descriptor of the map.
24.1575 - int operator[](const Item& item) const {
24.1576 - return Map::operator[](item);
24.1577 - }
24.1578 -
24.1579 - /// \brief Gives back the item by its descriptor.
24.1580 - ///
24.1581 - /// Gives back th item by its descriptor.
24.1582 - Item operator()(int id) const {
24.1583 - return _inv_map[id];
24.1584 - }
24.1585 -
24.1586 - private:
24.1587 -
24.1588 - typedef std::vector<Item> Container;
24.1589 - Container _inv_map;
24.1590 -
24.1591 - public:
24.1592 - /// \brief The inverse map type of DescriptorMap.
24.1593 - ///
24.1594 - /// The inverse map type of DescriptorMap.
24.1595 - class InverseMap {
24.1596 - public:
24.1597 - /// \brief Constructor of the InverseMap.
24.1598 - ///
24.1599 - /// Constructor of the InverseMap.
24.1600 - explicit InverseMap(const DescriptorMap& inverted)
24.1601 - : _inverted(inverted) {}
24.1602 -
24.1603 -
24.1604 - /// The value type of the InverseMap.
24.1605 - typedef typename DescriptorMap::Key Value;
24.1606 - /// The key type of the InverseMap.
24.1607 - typedef typename DescriptorMap::Value Key;
24.1608 -
24.1609 - /// \brief Subscript operator.
24.1610 - ///
24.1611 - /// Subscript operator. It gives back the item
24.1612 - /// that the descriptor belongs to currently.
24.1613 - Value operator[](const Key& key) const {
24.1614 - return _inverted(key);
24.1615 - }
24.1616 -
24.1617 - /// \brief Size of the map.
24.1618 - ///
24.1619 - /// Returns the size of the map.
24.1620 - unsigned int size() const {
24.1621 - return _inverted.size();
24.1622 - }
24.1623 -
24.1624 - private:
24.1625 - const DescriptorMap& _inverted;
24.1626 - };
24.1627 -
24.1628 - /// \brief Gives back the inverse of the map.
24.1629 - ///
24.1630 - /// Gives back the inverse of the map.
24.1631 - const InverseMap inverse() const {
24.1632 - return InverseMap(*this);
24.1633 - }
24.1634 - };
24.1635 -
24.1636 - /// \brief Returns the source of the given arc.
24.1637 - ///
24.1638 - /// The SourceMap gives back the source Node of the given arc.
24.1639 - /// \see TargetMap
24.1640 - template <typename Digraph>
24.1641 - class SourceMap {
24.1642 - public:
24.1643 -
24.1644 - typedef typename Digraph::Node Value;
24.1645 - typedef typename Digraph::Arc Key;
24.1646 -
24.1647 - /// \brief Constructor
24.1648 - ///
24.1649 - /// Constructor
24.1650 - /// \param _digraph The digraph that the map belongs to.
24.1651 - explicit SourceMap(const Digraph& digraph) : _digraph(digraph) {}
24.1652 -
24.1653 - /// \brief The subscript operator.
24.1654 - ///
24.1655 - /// The subscript operator.
24.1656 - /// \param arc The arc
24.1657 - /// \return The source of the arc
24.1658 - Value operator[](const Key& arc) const {
24.1659 - return _digraph.source(arc);
24.1660 - }
24.1661 -
24.1662 - private:
24.1663 - const Digraph& _digraph;
24.1664 - };
24.1665 -
24.1666 - /// \brief Returns a \ref SourceMap class.
24.1667 - ///
24.1668 - /// This function just returns an \ref SourceMap class.
24.1669 - /// \relates SourceMap
24.1670 - template <typename Digraph>
24.1671 - inline SourceMap<Digraph> sourceMap(const Digraph& digraph) {
24.1672 - return SourceMap<Digraph>(digraph);
24.1673 - }
24.1674 -
24.1675 - /// \brief Returns the target of the given arc.
24.1676 - ///
24.1677 - /// The TargetMap gives back the target Node of the given arc.
24.1678 - /// \see SourceMap
24.1679 - template <typename Digraph>
24.1680 - class TargetMap {
24.1681 - public:
24.1682 -
24.1683 - typedef typename Digraph::Node Value;
24.1684 - typedef typename Digraph::Arc Key;
24.1685 -
24.1686 - /// \brief Constructor
24.1687 - ///
24.1688 - /// Constructor
24.1689 - /// \param _digraph The digraph that the map belongs to.
24.1690 - explicit TargetMap(const Digraph& digraph) : _digraph(digraph) {}
24.1691 -
24.1692 - /// \brief The subscript operator.
24.1693 - ///
24.1694 - /// The subscript operator.
24.1695 - /// \param e The arc
24.1696 - /// \return The target of the arc
24.1697 - Value operator[](const Key& e) const {
24.1698 - return _digraph.target(e);
24.1699 - }
24.1700 -
24.1701 - private:
24.1702 - const Digraph& _digraph;
24.1703 - };
24.1704 -
24.1705 - /// \brief Returns a \ref TargetMap class.
24.1706 - ///
24.1707 - /// This function just returns a \ref TargetMap class.
24.1708 - /// \relates TargetMap
24.1709 - template <typename Digraph>
24.1710 - inline TargetMap<Digraph> targetMap(const Digraph& digraph) {
24.1711 - return TargetMap<Digraph>(digraph);
24.1712 - }
24.1713 -
24.1714 - /// \brief Returns the "forward" directed arc view of an edge.
24.1715 - ///
24.1716 - /// Returns the "forward" directed arc view of an edge.
24.1717 - /// \see BackwardMap
24.1718 - template <typename Graph>
24.1719 - class ForwardMap {
24.1720 - public:
24.1721 -
24.1722 - typedef typename Graph::Arc Value;
24.1723 - typedef typename Graph::Edge Key;
24.1724 -
24.1725 - /// \brief Constructor
24.1726 - ///
24.1727 - /// Constructor
24.1728 - /// \param _graph The graph that the map belongs to.
24.1729 - explicit ForwardMap(const Graph& graph) : _graph(graph) {}
24.1730 -
24.1731 - /// \brief The subscript operator.
24.1732 - ///
24.1733 - /// The subscript operator.
24.1734 - /// \param key An edge
24.1735 - /// \return The "forward" directed arc view of edge
24.1736 - Value operator[](const Key& key) const {
24.1737 - return _graph.direct(key, true);
24.1738 - }
24.1739 -
24.1740 - private:
24.1741 - const Graph& _graph;
24.1742 - };
24.1743 -
24.1744 - /// \brief Returns a \ref ForwardMap class.
24.1745 - ///
24.1746 - /// This function just returns an \ref ForwardMap class.
24.1747 - /// \relates ForwardMap
24.1748 - template <typename Graph>
24.1749 - inline ForwardMap<Graph> forwardMap(const Graph& graph) {
24.1750 - return ForwardMap<Graph>(graph);
24.1751 - }
24.1752 -
24.1753 - /// \brief Returns the "backward" directed arc view of an edge.
24.1754 - ///
24.1755 - /// Returns the "backward" directed arc view of an edge.
24.1756 - /// \see ForwardMap
24.1757 - template <typename Graph>
24.1758 - class BackwardMap {
24.1759 - public:
24.1760 -
24.1761 - typedef typename Graph::Arc Value;
24.1762 - typedef typename Graph::Edge Key;
24.1763 -
24.1764 - /// \brief Constructor
24.1765 - ///
24.1766 - /// Constructor
24.1767 - /// \param _graph The graph that the map belongs to.
24.1768 - explicit BackwardMap(const Graph& graph) : _graph(graph) {}
24.1769 -
24.1770 - /// \brief The subscript operator.
24.1771 - ///
24.1772 - /// The subscript operator.
24.1773 - /// \param key An edge
24.1774 - /// \return The "backward" directed arc view of edge
24.1775 - Value operator[](const Key& key) const {
24.1776 - return _graph.direct(key, false);
24.1777 - }
24.1778 -
24.1779 - private:
24.1780 - const Graph& _graph;
24.1781 - };
24.1782 -
24.1783 - /// \brief Returns a \ref BackwardMap class
24.1784 -
24.1785 - /// This function just returns a \ref BackwardMap class.
24.1786 - /// \relates BackwardMap
24.1787 - template <typename Graph>
24.1788 - inline BackwardMap<Graph> backwardMap(const Graph& graph) {
24.1789 - return BackwardMap<Graph>(graph);
24.1790 - }
24.1791 -
24.1792 - /// \brief Potential difference map
24.1793 - ///
24.1794 - /// If there is an potential map on the nodes then we
24.1795 - /// can get an arc map as we get the substraction of the
24.1796 - /// values of the target and source.
24.1797 - template <typename Digraph, typename NodeMap>
24.1798 - class PotentialDifferenceMap {
24.1799 - public:
24.1800 - typedef typename Digraph::Arc Key;
24.1801 - typedef typename NodeMap::Value Value;
24.1802 -
24.1803 - /// \brief Constructor
24.1804 - ///
24.1805 - /// Contructor of the map
24.1806 - explicit PotentialDifferenceMap(const Digraph& digraph,
24.1807 - const NodeMap& potential)
24.1808 - : _digraph(digraph), _potential(potential) {}
24.1809 -
24.1810 - /// \brief Const subscription operator
24.1811 - ///
24.1812 - /// Const subscription operator
24.1813 - Value operator[](const Key& arc) const {
24.1814 - return _potential[_digraph.target(arc)] -
24.1815 - _potential[_digraph.source(arc)];
24.1816 - }
24.1817 -
24.1818 - private:
24.1819 - const Digraph& _digraph;
24.1820 - const NodeMap& _potential;
24.1821 - };
24.1822 -
24.1823 - /// \brief Returns a PotentialDifferenceMap.
24.1824 - ///
24.1825 - /// This function just returns a PotentialDifferenceMap.
24.1826 - /// \relates PotentialDifferenceMap
24.1827 - template <typename Digraph, typename NodeMap>
24.1828 - PotentialDifferenceMap<Digraph, NodeMap>
24.1829 - potentialDifferenceMap(const Digraph& digraph, const NodeMap& potential) {
24.1830 - return PotentialDifferenceMap<Digraph, NodeMap>(digraph, potential);
24.1831 - }
24.1832 -
24.1833 - /// \brief Map of the node in-degrees.
24.1834 - ///
24.1835 - /// This map returns the in-degree of a node. Once it is constructed,
24.1836 - /// the degrees are stored in a standard NodeMap, so each query is done
24.1837 - /// in constant time. On the other hand, the values are updated automatically
24.1838 - /// whenever the digraph changes.
24.1839 - ///
24.1840 - /// \warning Besides addNode() and addArc(), a digraph structure may provide
24.1841 - /// alternative ways to modify the digraph. The correct behavior of InDegMap
24.1842 - /// is not guarantied if these additional features are used. For example
24.1843 - /// the functions \ref ListDigraph::changeSource() "changeSource()",
24.1844 - /// \ref ListDigraph::changeTarget() "changeTarget()" and
24.1845 - /// \ref ListDigraph::reverseArc() "reverseArc()"
24.1846 - /// of \ref ListDigraph will \e not update the degree values correctly.
24.1847 - ///
24.1848 - /// \sa OutDegMap
24.1849 -
24.1850 - template <typename _Digraph>
24.1851 - class InDegMap
24.1852 - : protected ItemSetTraits<_Digraph, typename _Digraph::Arc>
24.1853 - ::ItemNotifier::ObserverBase {
24.1854 -
24.1855 - public:
24.1856 -
24.1857 - typedef _Digraph Digraph;
24.1858 - typedef int Value;
24.1859 - typedef typename Digraph::Node Key;
24.1860 -
24.1861 - typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
24.1862 - ::ItemNotifier::ObserverBase Parent;
24.1863 -
24.1864 - private:
24.1865 -
24.1866 - class AutoNodeMap : public DefaultMap<Digraph, Key, int> {
24.1867 - public:
24.1868 -
24.1869 - typedef DefaultMap<Digraph, Key, int> Parent;
24.1870 -
24.1871 - AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {}
24.1872 -
24.1873 - virtual void add(const Key& key) {
24.1874 - Parent::add(key);
24.1875 - Parent::set(key, 0);
24.1876 - }
24.1877 -
24.1878 - virtual void add(const std::vector<Key>& keys) {
24.1879 - Parent::add(keys);
24.1880 - for (int i = 0; i < int(keys.size()); ++i) {
24.1881 - Parent::set(keys[i], 0);
24.1882 - }
24.1883 - }
24.1884 -
24.1885 - virtual void build() {
24.1886 - Parent::build();
24.1887 - Key it;
24.1888 - typename Parent::Notifier* nf = Parent::notifier();
24.1889 - for (nf->first(it); it != INVALID; nf->next(it)) {
24.1890 - Parent::set(it, 0);
24.1891 - }
24.1892 - }
24.1893 - };
24.1894 -
24.1895 - public:
24.1896 -
24.1897 - /// \brief Constructor.
24.1898 - ///
24.1899 - /// Constructor for creating in-degree map.
24.1900 - explicit InDegMap(const Digraph& digraph)
24.1901 - : _digraph(digraph), _deg(digraph) {
24.1902 - Parent::attach(_digraph.notifier(typename Digraph::Arc()));
24.1903 -
24.1904 - for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
24.1905 - _deg[it] = countInArcs(_digraph, it);
24.1906 - }
24.1907 - }
24.1908 -
24.1909 - /// Gives back the in-degree of a Node.
24.1910 - int operator[](const Key& key) const {
24.1911 - return _deg[key];
24.1912 - }
24.1913 -
24.1914 - protected:
24.1915 -
24.1916 - typedef typename Digraph::Arc Arc;
24.1917 -
24.1918 - virtual void add(const Arc& arc) {
24.1919 - ++_deg[_digraph.target(arc)];
24.1920 - }
24.1921 -
24.1922 - virtual void add(const std::vector<Arc>& arcs) {
24.1923 - for (int i = 0; i < int(arcs.size()); ++i) {
24.1924 - ++_deg[_digraph.target(arcs[i])];
24.1925 - }
24.1926 - }
24.1927 -
24.1928 - virtual void erase(const Arc& arc) {
24.1929 - --_deg[_digraph.target(arc)];
24.1930 - }
24.1931 -
24.1932 - virtual void erase(const std::vector<Arc>& arcs) {
24.1933 - for (int i = 0; i < int(arcs.size()); ++i) {
24.1934 - --_deg[_digraph.target(arcs[i])];
24.1935 - }
24.1936 - }
24.1937 -
24.1938 - virtual void build() {
24.1939 - for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
24.1940 - _deg[it] = countInArcs(_digraph, it);
24.1941 - }
24.1942 - }
24.1943 -
24.1944 - virtual void clear() {
24.1945 - for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
24.1946 - _deg[it] = 0;
24.1947 - }
24.1948 - }
24.1949 - private:
24.1950 -
24.1951 - const Digraph& _digraph;
24.1952 - AutoNodeMap _deg;
24.1953 - };
24.1954 -
24.1955 - /// \brief Map of the node out-degrees.
24.1956 - ///
24.1957 - /// This map returns the out-degree of a node. Once it is constructed,
24.1958 - /// the degrees are stored in a standard NodeMap, so each query is done
24.1959 - /// in constant time. On the other hand, the values are updated automatically
24.1960 - /// whenever the digraph changes.
24.1961 - ///
24.1962 - /// \warning Besides addNode() and addArc(), a digraph structure may provide
24.1963 - /// alternative ways to modify the digraph. The correct behavior of OutDegMap
24.1964 - /// is not guarantied if these additional features are used. For example
24.1965 - /// the functions \ref ListDigraph::changeSource() "changeSource()",
24.1966 - /// \ref ListDigraph::changeTarget() "changeTarget()" and
24.1967 - /// \ref ListDigraph::reverseArc() "reverseArc()"
24.1968 - /// of \ref ListDigraph will \e not update the degree values correctly.
24.1969 - ///
24.1970 - /// \sa InDegMap
24.1971 -
24.1972 - template <typename _Digraph>
24.1973 - class OutDegMap
24.1974 - : protected ItemSetTraits<_Digraph, typename _Digraph::Arc>
24.1975 - ::ItemNotifier::ObserverBase {
24.1976 -
24.1977 - public:
24.1978 -
24.1979 - typedef _Digraph Digraph;
24.1980 - typedef int Value;
24.1981 - typedef typename Digraph::Node Key;
24.1982 -
24.1983 - typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
24.1984 - ::ItemNotifier::ObserverBase Parent;
24.1985 -
24.1986 - private:
24.1987 -
24.1988 - class AutoNodeMap : public DefaultMap<Digraph, Key, int> {
24.1989 - public:
24.1990 -
24.1991 - typedef DefaultMap<Digraph, Key, int> Parent;
24.1992 -
24.1993 - AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {}
24.1994 -
24.1995 - virtual void add(const Key& key) {
24.1996 - Parent::add(key);
24.1997 - Parent::set(key, 0);
24.1998 - }
24.1999 - virtual void add(const std::vector<Key>& keys) {
24.2000 - Parent::add(keys);
24.2001 - for (int i = 0; i < int(keys.size()); ++i) {
24.2002 - Parent::set(keys[i], 0);
24.2003 - }
24.2004 - }
24.2005 - virtual void build() {
24.2006 - Parent::build();
24.2007 - Key it;
24.2008 - typename Parent::Notifier* nf = Parent::notifier();
24.2009 - for (nf->first(it); it != INVALID; nf->next(it)) {
24.2010 - Parent::set(it, 0);
24.2011 - }
24.2012 - }
24.2013 - };
24.2014 -
24.2015 - public:
24.2016 -
24.2017 - /// \brief Constructor.
24.2018 - ///
24.2019 - /// Constructor for creating out-degree map.
24.2020 - explicit OutDegMap(const Digraph& digraph)
24.2021 - : _digraph(digraph), _deg(digraph) {
24.2022 - Parent::attach(_digraph.notifier(typename Digraph::Arc()));
24.2023 -
24.2024 - for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
24.2025 - _deg[it] = countOutArcs(_digraph, it);
24.2026 - }
24.2027 - }
24.2028 -
24.2029 - /// Gives back the out-degree of a Node.
24.2030 - int operator[](const Key& key) const {
24.2031 - return _deg[key];
24.2032 - }
24.2033 -
24.2034 - protected:
24.2035 -
24.2036 - typedef typename Digraph::Arc Arc;
24.2037 -
24.2038 - virtual void add(const Arc& arc) {
24.2039 - ++_deg[_digraph.source(arc)];
24.2040 - }
24.2041 -
24.2042 - virtual void add(const std::vector<Arc>& arcs) {
24.2043 - for (int i = 0; i < int(arcs.size()); ++i) {
24.2044 - ++_deg[_digraph.source(arcs[i])];
24.2045 - }
24.2046 - }
24.2047 -
24.2048 - virtual void erase(const Arc& arc) {
24.2049 - --_deg[_digraph.source(arc)];
24.2050 - }
24.2051 -
24.2052 - virtual void erase(const std::vector<Arc>& arcs) {
24.2053 - for (int i = 0; i < int(arcs.size()); ++i) {
24.2054 - --_deg[_digraph.source(arcs[i])];
24.2055 - }
24.2056 - }
24.2057 -
24.2058 - virtual void build() {
24.2059 - for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
24.2060 - _deg[it] = countOutArcs(_digraph, it);
24.2061 - }
24.2062 - }
24.2063 -
24.2064 - virtual void clear() {
24.2065 - for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
24.2066 - _deg[it] = 0;
24.2067 - }
24.2068 - }
24.2069 - private:
24.2070 -
24.2071 - const Digraph& _digraph;
24.2072 - AutoNodeMap _deg;
24.2073 - };
24.2074 -
24.2075 -
24.2076 - ///Dynamic arc look up between given endpoints.
24.2077 -
24.2078 - ///\ingroup gutils
24.2079 - ///Using this class, you can find an arc in a digraph from a given
24.2080 - ///source to a given target in amortized time <em>O(log d)</em>,
24.2081 - ///where <em>d</em> is the out-degree of the source node.
24.2082 - ///
24.2083 - ///It is possible to find \e all parallel arcs between two nodes with
24.2084 - ///the \c findFirst() and \c findNext() members.
24.2085 - ///
24.2086 - ///See the \ref ArcLookUp and \ref AllArcLookUp classes if your
24.2087 - ///digraph is not changed so frequently.
24.2088 - ///
24.2089 - ///This class uses a self-adjusting binary search tree, Sleator's
24.2090 - ///and Tarjan's Splay tree for guarantee the logarithmic amortized
24.2091 - ///time bound for arc lookups. This class also guarantees the
24.2092 - ///optimal time bound in a constant factor for any distribution of
24.2093 - ///queries.
24.2094 - ///
24.2095 - ///\tparam G The type of the underlying digraph.
24.2096 - ///
24.2097 - ///\sa ArcLookUp
24.2098 - ///\sa AllArcLookUp
24.2099 - template<class G>
24.2100 - class DynArcLookUp
24.2101 - : protected ItemSetTraits<G, typename G::Arc>::ItemNotifier::ObserverBase
24.2102 - {
24.2103 - public:
24.2104 - typedef typename ItemSetTraits<G, typename G::Arc>
24.2105 - ::ItemNotifier::ObserverBase Parent;
24.2106 -
24.2107 - TEMPLATE_DIGRAPH_TYPEDEFS(G);
24.2108 - typedef G Digraph;
24.2109 -
24.2110 - protected:
24.2111 -
24.2112 - class AutoNodeMap : public DefaultMap<G, Node, Arc> {
24.2113 - public:
24.2114 -
24.2115 - typedef DefaultMap<G, Node, Arc> Parent;
24.2116 -
24.2117 - AutoNodeMap(const G& digraph) : Parent(digraph, INVALID) {}
24.2118 -
24.2119 - virtual void add(const Node& node) {
24.2120 - Parent::add(node);
24.2121 - Parent::set(node, INVALID);
24.2122 - }
24.2123 -
24.2124 - virtual void add(const std::vector<Node>& nodes) {
24.2125 - Parent::add(nodes);
24.2126 - for (int i = 0; i < int(nodes.size()); ++i) {
24.2127 - Parent::set(nodes[i], INVALID);
24.2128 - }
24.2129 - }
24.2130 -
24.2131 - virtual void build() {
24.2132 - Parent::build();
24.2133 - Node it;
24.2134 - typename Parent::Notifier* nf = Parent::notifier();
24.2135 - for (nf->first(it); it != INVALID; nf->next(it)) {
24.2136 - Parent::set(it, INVALID);
24.2137 - }
24.2138 - }
24.2139 - };
24.2140 -
24.2141 - const Digraph &_g;
24.2142 - AutoNodeMap _head;
24.2143 - typename Digraph::template ArcMap<Arc> _parent;
24.2144 - typename Digraph::template ArcMap<Arc> _left;
24.2145 - typename Digraph::template ArcMap<Arc> _right;
24.2146 -
24.2147 - class ArcLess {
24.2148 - const Digraph &g;
24.2149 - public:
24.2150 - ArcLess(const Digraph &_g) : g(_g) {}
24.2151 - bool operator()(Arc a,Arc b) const
24.2152 - {
24.2153 - return g.target(a)<g.target(b);
24.2154 - }
24.2155 - };
24.2156 -
24.2157 - public:
24.2158 -
24.2159 - ///Constructor
24.2160 -
24.2161 - ///Constructor.
24.2162 - ///
24.2163 - ///It builds up the search database.
24.2164 - DynArcLookUp(const Digraph &g)
24.2165 - : _g(g),_head(g),_parent(g),_left(g),_right(g)
24.2166 - {
24.2167 - Parent::attach(_g.notifier(typename Digraph::Arc()));
24.2168 - refresh();
24.2169 - }
24.2170 -
24.2171 - protected:
24.2172 -
24.2173 - virtual void add(const Arc& arc) {
24.2174 - insert(arc);
24.2175 - }
24.2176 -
24.2177 - virtual void add(const std::vector<Arc>& arcs) {
24.2178 - for (int i = 0; i < int(arcs.size()); ++i) {
24.2179 - insert(arcs[i]);
24.2180 - }
24.2181 - }
24.2182 -
24.2183 - virtual void erase(const Arc& arc) {
24.2184 - remove(arc);
24.2185 - }
24.2186 -
24.2187 - virtual void erase(const std::vector<Arc>& arcs) {
24.2188 - for (int i = 0; i < int(arcs.size()); ++i) {
24.2189 - remove(arcs[i]);
24.2190 - }
24.2191 - }
24.2192 -
24.2193 - virtual void build() {
24.2194 - refresh();
24.2195 - }
24.2196 -
24.2197 - virtual void clear() {
24.2198 - for(NodeIt n(_g);n!=INVALID;++n) {
24.2199 - _head.set(n, INVALID);
24.2200 - }
24.2201 - }
24.2202 -
24.2203 - void insert(Arc arc) {
24.2204 - Node s = _g.source(arc);
24.2205 - Node t = _g.target(arc);
24.2206 - _left.set(arc, INVALID);
24.2207 - _right.set(arc, INVALID);
24.2208 -
24.2209 - Arc e = _head[s];
24.2210 - if (e == INVALID) {
24.2211 - _head.set(s, arc);
24.2212 - _parent.set(arc, INVALID);
24.2213 - return;
24.2214 - }
24.2215 - while (true) {
24.2216 - if (t < _g.target(e)) {
24.2217 - if (_left[e] == INVALID) {
24.2218 - _left.set(e, arc);
24.2219 - _parent.set(arc, e);
24.2220 - splay(arc);
24.2221 - return;
24.2222 - } else {
24.2223 - e = _left[e];
24.2224 - }
24.2225 - } else {
24.2226 - if (_right[e] == INVALID) {
24.2227 - _right.set(e, arc);
24.2228 - _parent.set(arc, e);
24.2229 - splay(arc);
24.2230 - return;
24.2231 - } else {
24.2232 - e = _right[e];
24.2233 - }
24.2234 - }
24.2235 - }
24.2236 - }
24.2237 -
24.2238 - void remove(Arc arc) {
24.2239 - if (_left[arc] == INVALID) {
24.2240 - if (_right[arc] != INVALID) {
24.2241 - _parent.set(_right[arc], _parent[arc]);
24.2242 - }
24.2243 - if (_parent[arc] != INVALID) {
24.2244 - if (_left[_parent[arc]] == arc) {
24.2245 - _left.set(_parent[arc], _right[arc]);
24.2246 - } else {
24.2247 - _right.set(_parent[arc], _right[arc]);
24.2248 - }
24.2249 - } else {
24.2250 - _head.set(_g.source(arc), _right[arc]);
24.2251 - }
24.2252 - } else if (_right[arc] == INVALID) {
24.2253 - _parent.set(_left[arc], _parent[arc]);
24.2254 - if (_parent[arc] != INVALID) {
24.2255 - if (_left[_parent[arc]] == arc) {
24.2256 - _left.set(_parent[arc], _left[arc]);
24.2257 - } else {
24.2258 - _right.set(_parent[arc], _left[arc]);
24.2259 - }
24.2260 - } else {
24.2261 - _head.set(_g.source(arc), _left[arc]);
24.2262 - }
24.2263 - } else {
24.2264 - Arc e = _left[arc];
24.2265 - if (_right[e] != INVALID) {
24.2266 - e = _right[e];
24.2267 - while (_right[e] != INVALID) {
24.2268 - e = _right[e];
24.2269 - }
24.2270 - Arc s = _parent[e];
24.2271 - _right.set(_parent[e], _left[e]);
24.2272 - if (_left[e] != INVALID) {
24.2273 - _parent.set(_left[e], _parent[e]);
24.2274 - }
24.2275 -
24.2276 - _left.set(e, _left[arc]);
24.2277 - _parent.set(_left[arc], e);
24.2278 - _right.set(e, _right[arc]);
24.2279 - _parent.set(_right[arc], e);
24.2280 -
24.2281 - _parent.set(e, _parent[arc]);
24.2282 - if (_parent[arc] != INVALID) {
24.2283 - if (_left[_parent[arc]] == arc) {
24.2284 - _left.set(_parent[arc], e);
24.2285 - } else {
24.2286 - _right.set(_parent[arc], e);
24.2287 - }
24.2288 - }
24.2289 - splay(s);
24.2290 - } else {
24.2291 - _right.set(e, _right[arc]);
24.2292 - _parent.set(_right[arc], e);
24.2293 -
24.2294 - if (_parent[arc] != INVALID) {
24.2295 - if (_left[_parent[arc]] == arc) {
24.2296 - _left.set(_parent[arc], e);
24.2297 - } else {
24.2298 - _right.set(_parent[arc], e);
24.2299 - }
24.2300 - } else {
24.2301 - _head.set(_g.source(arc), e);
24.2302 - }
24.2303 - }
24.2304 - }
24.2305 - }
24.2306 -
24.2307 - Arc refreshRec(std::vector<Arc> &v,int a,int b)
24.2308 - {
24.2309 - int m=(a+b)/2;
24.2310 - Arc me=v[m];
24.2311 - if (a < m) {
24.2312 - Arc left = refreshRec(v,a,m-1);
24.2313 - _left.set(me, left);
24.2314 - _parent.set(left, me);
24.2315 - } else {
24.2316 - _left.set(me, INVALID);
24.2317 - }
24.2318 - if (m < b) {
24.2319 - Arc right = refreshRec(v,m+1,b);
24.2320 - _right.set(me, right);
24.2321 - _parent.set(right, me);
24.2322 - } else {
24.2323 - _right.set(me, INVALID);
24.2324 - }
24.2325 - return me;
24.2326 - }
24.2327 -
24.2328 - void refresh() {
24.2329 - for(NodeIt n(_g);n!=INVALID;++n) {
24.2330 - std::vector<Arc> v;
24.2331 - for(OutArcIt e(_g,n);e!=INVALID;++e) v.push_back(e);
24.2332 - if(v.size()) {
24.2333 - std::sort(v.begin(),v.end(),ArcLess(_g));
24.2334 - Arc head = refreshRec(v,0,v.size()-1);
24.2335 - _head.set(n, head);
24.2336 - _parent.set(head, INVALID);
24.2337 - }
24.2338 - else _head.set(n, INVALID);
24.2339 - }
24.2340 - }
24.2341 -
24.2342 - void zig(Arc v) {
24.2343 - Arc w = _parent[v];
24.2344 - _parent.set(v, _parent[w]);
24.2345 - _parent.set(w, v);
24.2346 - _left.set(w, _right[v]);
24.2347 - _right.set(v, w);
24.2348 - if (_parent[v] != INVALID) {
24.2349 - if (_right[_parent[v]] == w) {
24.2350 - _right.set(_parent[v], v);
24.2351 - } else {
24.2352 - _left.set(_parent[v], v);
24.2353 - }
24.2354 - }
24.2355 - if (_left[w] != INVALID){
24.2356 - _parent.set(_left[w], w);
24.2357 - }
24.2358 - }
24.2359 -
24.2360 - void zag(Arc v) {
24.2361 - Arc w = _parent[v];
24.2362 - _parent.set(v, _parent[w]);
24.2363 - _parent.set(w, v);
24.2364 - _right.set(w, _left[v]);
24.2365 - _left.set(v, w);
24.2366 - if (_parent[v] != INVALID){
24.2367 - if (_left[_parent[v]] == w) {
24.2368 - _left.set(_parent[v], v);
24.2369 - } else {
24.2370 - _right.set(_parent[v], v);
24.2371 - }
24.2372 - }
24.2373 - if (_right[w] != INVALID){
24.2374 - _parent.set(_right[w], w);
24.2375 - }
24.2376 - }
24.2377 -
24.2378 - void splay(Arc v) {
24.2379 - while (_parent[v] != INVALID) {
24.2380 - if (v == _left[_parent[v]]) {
24.2381 - if (_parent[_parent[v]] == INVALID) {
24.2382 - zig(v);
24.2383 - } else {
24.2384 - if (_parent[v] == _left[_parent[_parent[v]]]) {
24.2385 - zig(_parent[v]);
24.2386 - zig(v);
24.2387 - } else {
24.2388 - zig(v);
24.2389 - zag(v);
24.2390 - }
24.2391 - }
24.2392 - } else {
24.2393 - if (_parent[_parent[v]] == INVALID) {
24.2394 - zag(v);
24.2395 - } else {
24.2396 - if (_parent[v] == _left[_parent[_parent[v]]]) {
24.2397 - zag(v);
24.2398 - zig(v);
24.2399 - } else {
24.2400 - zag(_parent[v]);
24.2401 - zag(v);
24.2402 - }
24.2403 - }
24.2404 - }
24.2405 - }
24.2406 - _head[_g.source(v)] = v;
24.2407 - }
24.2408 -
24.2409 -
24.2410 - public:
24.2411 -
24.2412 - ///Find an arc between two nodes.
24.2413 -
24.2414 - ///Find an arc between two nodes in time <em>O(</em>log<em>d)</em>, where
24.2415 - /// <em>d</em> is the number of outgoing arcs of \c s.
24.2416 - ///\param s The source node
24.2417 - ///\param t The target node
24.2418 - ///\return An arc from \c s to \c t if there exists,
24.2419 - ///\ref INVALID otherwise.
24.2420 - Arc operator()(Node s, Node t) const
24.2421 - {
24.2422 - Arc a = _head[s];
24.2423 - while (true) {
24.2424 - if (_g.target(a) == t) {
24.2425 - const_cast<DynArcLookUp&>(*this).splay(a);
24.2426 - return a;
24.2427 - } else if (t < _g.target(a)) {
24.2428 - if (_left[a] == INVALID) {
24.2429 - const_cast<DynArcLookUp&>(*this).splay(a);
24.2430 - return INVALID;
24.2431 - } else {
24.2432 - a = _left[a];
24.2433 - }
24.2434 - } else {
24.2435 - if (_right[a] == INVALID) {
24.2436 - const_cast<DynArcLookUp&>(*this).splay(a);
24.2437 - return INVALID;
24.2438 - } else {
24.2439 - a = _right[a];
24.2440 - }
24.2441 - }
24.2442 - }
24.2443 - }
24.2444 -
24.2445 - ///Find the first arc between two nodes.
24.2446 -
24.2447 - ///Find the first arc between two nodes in time
24.2448 - /// <em>O(</em>log<em>d)</em>, where <em>d</em> is the number of
24.2449 - /// outgoing arcs of \c s.
24.2450 - ///\param s The source node
24.2451 - ///\param t The target node
24.2452 - ///\return An arc from \c s to \c t if there exists, \ref INVALID
24.2453 - /// otherwise.
24.2454 - Arc findFirst(Node s, Node t) const
24.2455 - {
24.2456 - Arc a = _head[s];
24.2457 - Arc r = INVALID;
24.2458 - while (true) {
24.2459 - if (_g.target(a) < t) {
24.2460 - if (_right[a] == INVALID) {
24.2461 - const_cast<DynArcLookUp&>(*this).splay(a);
24.2462 - return r;
24.2463 - } else {
24.2464 - a = _right[a];
24.2465 - }
24.2466 - } else {
24.2467 - if (_g.target(a) == t) {
24.2468 - r = a;
24.2469 - }
24.2470 - if (_left[a] == INVALID) {
24.2471 - const_cast<DynArcLookUp&>(*this).splay(a);
24.2472 - return r;
24.2473 - } else {
24.2474 - a = _left[a];
24.2475 - }
24.2476 - }
24.2477 - }
24.2478 - }
24.2479 -
24.2480 - ///Find the next arc between two nodes.
24.2481 -
24.2482 - ///Find the next arc between two nodes in time
24.2483 - /// <em>O(</em>log<em>d)</em>, where <em>d</em> is the number of
24.2484 - /// outgoing arcs of \c s.
24.2485 - ///\param s The source node
24.2486 - ///\param t The target node
24.2487 - ///\return An arc from \c s to \c t if there exists, \ref INVALID
24.2488 - /// otherwise.
24.2489 -
24.2490 - ///\note If \c e is not the result of the previous \c findFirst()
24.2491 - ///operation then the amorized time bound can not be guaranteed.
24.2492 -#ifdef DOXYGEN
24.2493 - Arc findNext(Node s, Node t, Arc a) const
24.2494 -#else
24.2495 - Arc findNext(Node, Node t, Arc a) const
24.2496 -#endif
24.2497 - {
24.2498 - if (_right[a] != INVALID) {
24.2499 - a = _right[a];
24.2500 - while (_left[a] != INVALID) {
24.2501 - a = _left[a];
24.2502 - }
24.2503 - const_cast<DynArcLookUp&>(*this).splay(a);
24.2504 - } else {
24.2505 - while (_parent[a] != INVALID && _right[_parent[a]] == a) {
24.2506 - a = _parent[a];
24.2507 - }
24.2508 - if (_parent[a] == INVALID) {
24.2509 - return INVALID;
24.2510 - } else {
24.2511 - a = _parent[a];
24.2512 - const_cast<DynArcLookUp&>(*this).splay(a);
24.2513 - }
24.2514 - }
24.2515 - if (_g.target(a) == t) return a;
24.2516 - else return INVALID;
24.2517 - }
24.2518 -
24.2519 - };
24.2520 -
24.2521 - ///Fast arc look up between given endpoints.
24.2522 -
24.2523 - ///\ingroup gutils
24.2524 - ///Using this class, you can find an arc in a digraph from a given
24.2525 - ///source to a given target in time <em>O(log d)</em>,
24.2526 - ///where <em>d</em> is the out-degree of the source node.
24.2527 - ///
24.2528 - ///It is not possible to find \e all parallel arcs between two nodes.
24.2529 - ///Use \ref AllArcLookUp for this purpose.
24.2530 - ///
24.2531 - ///\warning This class is static, so you should refresh() (or at least
24.2532 - ///refresh(Node)) this data structure
24.2533 - ///whenever the digraph changes. This is a time consuming (superlinearly
24.2534 - ///proportional (<em>O(m</em>log<em>m)</em>) to the number of arcs).
24.2535 - ///
24.2536 - ///\tparam G The type of the underlying digraph.
24.2537 - ///
24.2538 - ///\sa DynArcLookUp
24.2539 - ///\sa AllArcLookUp
24.2540 - template<class G>
24.2541 - class ArcLookUp
24.2542 - {
24.2543 - public:
24.2544 - TEMPLATE_DIGRAPH_TYPEDEFS(G);
24.2545 - typedef G Digraph;
24.2546 -
24.2547 - protected:
24.2548 - const Digraph &_g;
24.2549 - typename Digraph::template NodeMap<Arc> _head;
24.2550 - typename Digraph::template ArcMap<Arc> _left;
24.2551 - typename Digraph::template ArcMap<Arc> _right;
24.2552 -
24.2553 - class ArcLess {
24.2554 - const Digraph &g;
24.2555 - public:
24.2556 - ArcLess(const Digraph &_g) : g(_g) {}
24.2557 - bool operator()(Arc a,Arc b) const
24.2558 - {
24.2559 - return g.target(a)<g.target(b);
24.2560 - }
24.2561 - };
24.2562 -
24.2563 - public:
24.2564 -
24.2565 - ///Constructor
24.2566 -
24.2567 - ///Constructor.
24.2568 - ///
24.2569 - ///It builds up the search database, which remains valid until the digraph
24.2570 - ///changes.
24.2571 - ArcLookUp(const Digraph &g) :_g(g),_head(g),_left(g),_right(g) {refresh();}
24.2572 -
24.2573 - private:
24.2574 - Arc refreshRec(std::vector<Arc> &v,int a,int b)
24.2575 - {
24.2576 - int m=(a+b)/2;
24.2577 - Arc me=v[m];
24.2578 - _left[me] = a<m?refreshRec(v,a,m-1):INVALID;
24.2579 - _right[me] = m<b?refreshRec(v,m+1,b):INVALID;
24.2580 - return me;
24.2581 - }
24.2582 - public:
24.2583 - ///Refresh the data structure at a node.
24.2584 -
24.2585 - ///Build up the search database of node \c n.
24.2586 - ///
24.2587 - ///It runs in time <em>O(d</em>log<em>d)</em>, where <em>d</em> is
24.2588 - ///the number of the outgoing arcs of \c n.
24.2589 - void refresh(Node n)
24.2590 - {
24.2591 - std::vector<Arc> v;
24.2592 - for(OutArcIt e(_g,n);e!=INVALID;++e) v.push_back(e);
24.2593 - if(v.size()) {
24.2594 - std::sort(v.begin(),v.end(),ArcLess(_g));
24.2595 - _head[n]=refreshRec(v,0,v.size()-1);
24.2596 - }
24.2597 - else _head[n]=INVALID;
24.2598 - }
24.2599 - ///Refresh the full data structure.
24.2600 -
24.2601 - ///Build up the full search database. In fact, it simply calls
24.2602 - ///\ref refresh(Node) "refresh(n)" for each node \c n.
24.2603 - ///
24.2604 - ///It runs in time <em>O(m</em>log<em>D)</em>, where <em>m</em> is
24.2605 - ///the number of the arcs of \c n and <em>D</em> is the maximum
24.2606 - ///out-degree of the digraph.
24.2607 -
24.2608 - void refresh()
24.2609 - {
24.2610 - for(NodeIt n(_g);n!=INVALID;++n) refresh(n);
24.2611 - }
24.2612 -
24.2613 - ///Find an arc between two nodes.
24.2614 -
24.2615 - ///Find an arc between two nodes in time <em>O(</em>log<em>d)</em>, where
24.2616 - /// <em>d</em> is the number of outgoing arcs of \c s.
24.2617 - ///\param s The source node
24.2618 - ///\param t The target node
24.2619 - ///\return An arc from \c s to \c t if there exists,
24.2620 - ///\ref INVALID otherwise.
24.2621 - ///
24.2622 - ///\warning If you change the digraph, refresh() must be called before using
24.2623 - ///this operator. If you change the outgoing arcs of
24.2624 - ///a single node \c n, then
24.2625 - ///\ref refresh(Node) "refresh(n)" is enough.
24.2626 - ///
24.2627 - Arc operator()(Node s, Node t) const
24.2628 - {
24.2629 - Arc e;
24.2630 - for(e=_head[s];
24.2631 - e!=INVALID&&_g.target(e)!=t;
24.2632 - e = t < _g.target(e)?_left[e]:_right[e]) ;
24.2633 - return e;
24.2634 - }
24.2635 -
24.2636 - };
24.2637 -
24.2638 - ///Fast look up of all arcs between given endpoints.
24.2639 -
24.2640 - ///\ingroup gutils
24.2641 - ///This class is the same as \ref ArcLookUp, with the addition
24.2642 - ///that it makes it possible to find all arcs between given endpoints.
24.2643 - ///
24.2644 - ///\warning This class is static, so you should refresh() (or at least
24.2645 - ///refresh(Node)) this data structure
24.2646 - ///whenever the digraph changes. This is a time consuming (superlinearly
24.2647 - ///proportional (<em>O(m</em>log<em>m)</em>) to the number of arcs).
24.2648 - ///
24.2649 - ///\tparam G The type of the underlying digraph.
24.2650 - ///
24.2651 - ///\sa DynArcLookUp
24.2652 - ///\sa ArcLookUp
24.2653 - template<class G>
24.2654 - class AllArcLookUp : public ArcLookUp<G>
24.2655 - {
24.2656 - using ArcLookUp<G>::_g;
24.2657 - using ArcLookUp<G>::_right;
24.2658 - using ArcLookUp<G>::_left;
24.2659 - using ArcLookUp<G>::_head;
24.2660 -
24.2661 - TEMPLATE_DIGRAPH_TYPEDEFS(G);
24.2662 - typedef G Digraph;
24.2663 -
24.2664 - typename Digraph::template ArcMap<Arc> _next;
24.2665 -
24.2666 - Arc refreshNext(Arc head,Arc next=INVALID)
24.2667 - {
24.2668 - if(head==INVALID) return next;
24.2669 - else {
24.2670 - next=refreshNext(_right[head],next);
24.2671 -// _next[head]=next;
24.2672 - _next[head]=( next!=INVALID && _g.target(next)==_g.target(head))
24.2673 - ? next : INVALID;
24.2674 - return refreshNext(_left[head],head);
24.2675 - }
24.2676 - }
24.2677 -
24.2678 - void refreshNext()
24.2679 - {
24.2680 - for(NodeIt n(_g);n!=INVALID;++n) refreshNext(_head[n]);
24.2681 - }
24.2682 -
24.2683 - public:
24.2684 - ///Constructor
24.2685 -
24.2686 - ///Constructor.
24.2687 - ///
24.2688 - ///It builds up the search database, which remains valid until the digraph
24.2689 - ///changes.
24.2690 - AllArcLookUp(const Digraph &g) : ArcLookUp<G>(g), _next(g) {refreshNext();}
24.2691 -
24.2692 - ///Refresh the data structure at a node.
24.2693 -
24.2694 - ///Build up the search database of node \c n.
24.2695 - ///
24.2696 - ///It runs in time <em>O(d</em>log<em>d)</em>, where <em>d</em> is
24.2697 - ///the number of the outgoing arcs of \c n.
24.2698 -
24.2699 - void refresh(Node n)
24.2700 - {
24.2701 - ArcLookUp<G>::refresh(n);
24.2702 - refreshNext(_head[n]);
24.2703 - }
24.2704 -
24.2705 - ///Refresh the full data structure.
24.2706 -
24.2707 - ///Build up the full search database. In fact, it simply calls
24.2708 - ///\ref refresh(Node) "refresh(n)" for each node \c n.
24.2709 - ///
24.2710 - ///It runs in time <em>O(m</em>log<em>D)</em>, where <em>m</em> is
24.2711 - ///the number of the arcs of \c n and <em>D</em> is the maximum
24.2712 - ///out-degree of the digraph.
24.2713 -
24.2714 - void refresh()
24.2715 - {
24.2716 - for(NodeIt n(_g);n!=INVALID;++n) refresh(_head[n]);
24.2717 - }
24.2718 -
24.2719 - ///Find an arc between two nodes.
24.2720 -
24.2721 - ///Find an arc between two nodes.
24.2722 - ///\param s The source node
24.2723 - ///\param t The target node
24.2724 - ///\param prev The previous arc between \c s and \c t. It it is INVALID or
24.2725 - ///not given, the operator finds the first appropriate arc.
24.2726 - ///\return An arc from \c s to \c t after \c prev or
24.2727 - ///\ref INVALID if there is no more.
24.2728 - ///
24.2729 - ///For example, you can count the number of arcs from \c u to \c v in the
24.2730 - ///following way.
24.2731 - ///\code
24.2732 - ///AllArcLookUp<ListDigraph> ae(g);
24.2733 - ///...
24.2734 - ///int n=0;
24.2735 - ///for(Arc e=ae(u,v);e!=INVALID;e=ae(u,v,e)) n++;
24.2736 - ///\endcode
24.2737 - ///
24.2738 - ///Finding the first arc take <em>O(</em>log<em>d)</em> time, where
24.2739 - /// <em>d</em> is the number of outgoing arcs of \c s. Then, the
24.2740 - ///consecutive arcs are found in constant time.
24.2741 - ///
24.2742 - ///\warning If you change the digraph, refresh() must be called before using
24.2743 - ///this operator. If you change the outgoing arcs of
24.2744 - ///a single node \c n, then
24.2745 - ///\ref refresh(Node) "refresh(n)" is enough.
24.2746 - ///
24.2747 -#ifdef DOXYGEN
24.2748 - Arc operator()(Node s, Node t, Arc prev=INVALID) const {}
24.2749 -#else
24.2750 - using ArcLookUp<G>::operator() ;
24.2751 - Arc operator()(Node s, Node t, Arc prev) const
24.2752 - {
24.2753 - return prev==INVALID?(*this)(s,t):_next[prev];
24.2754 - }
24.2755 -#endif
24.2756 -
24.2757 - };
24.2758 -
24.2759 - /// @}
24.2760 -
24.2761 -} //END OF NAMESPACE LEMON
24.2762 -
24.2763 -#endif
25.1 --- a/lemon/kruskal.h Tue Jul 15 18:43:41 2008 +0100
25.2 +++ b/lemon/kruskal.h Tue Jul 15 18:49:30 2008 +0100
25.3 @@ -22,12 +22,9 @@
25.4 #include <algorithm>
25.5 #include <vector>
25.6 #include <lemon/unionfind.h>
25.7 -// #include <lemon/graph_utils.h>
25.8 #include <lemon/maps.h>
25.9
25.10 -// #include <lemon/radix_sort.h>
25.11 -
25.12 -#include <lemon/bits/utility.h>
25.13 +#include <lemon/core.h>
25.14 #include <lemon/bits/traits.h>
25.15
25.16 ///\ingroup spantree
25.17 @@ -300,7 +297,7 @@
25.18 ///
25.19 /// \return The total cost of the found spanning tree.
25.20 ///
25.21 - /// \note If the input graph is not (weakly) connected, a spanning
25.22 + /// \note If the input graph is not (weakly) connected, a spanning
25.23 /// forest is calculated instead of a spanning tree.
25.24
25.25 #ifdef DOXYGEN
26.1 --- a/lemon/lgf_reader.h Tue Jul 15 18:43:41 2008 +0100
26.2 +++ b/lemon/lgf_reader.h Tue Jul 15 18:49:30 2008 +0100
26.3 @@ -32,7 +32,7 @@
26.4 #include <map>
26.5
26.6 #include <lemon/assert.h>
26.7 -#include <lemon/graph_utils.h>
26.8 +#include <lemon/core.h>
26.9
26.10 #include <lemon/lgf_writer.h>
26.11
27.1 --- a/lemon/lgf_writer.h Tue Jul 15 18:43:41 2008 +0100
27.2 +++ b/lemon/lgf_writer.h Tue Jul 15 18:49:30 2008 +0100
27.3 @@ -34,7 +34,8 @@
27.4 #include <functional>
27.5
27.6 #include <lemon/assert.h>
27.7 -#include <lemon/graph_utils.h>
27.8 +#include <lemon/core.h>
27.9 +#include <lemon/maps.h>
27.10
27.11 namespace lemon {
27.12
28.1 --- a/lemon/list_graph.h Tue Jul 15 18:43:41 2008 +0100
28.2 +++ b/lemon/list_graph.h Tue Jul 15 18:49:30 2008 +0100
28.3 @@ -23,6 +23,8 @@
28.4 ///\file
28.5 ///\brief ListDigraph, ListGraph classes.
28.6
28.7 +#include <lemon/core.h>
28.8 +#include <lemon/error.h>
28.9 #include <lemon/bits/graph_extender.h>
28.10
28.11 #include <vector>
29.1 --- a/lemon/maps.h Tue Jul 15 18:43:41 2008 +0100
29.2 +++ b/lemon/maps.h Tue Jul 15 18:49:30 2008 +0100
29.3 @@ -23,8 +23,7 @@
29.4 #include <functional>
29.5 #include <vector>
29.6
29.7 -#include <lemon/bits/utility.h>
29.8 -#include <lemon/bits/traits.h>
29.9 +#include <lemon/core.h>
29.10
29.11 ///\file
29.12 ///\ingroup maps
29.13 @@ -1780,6 +1779,926 @@
29.14 return LoggerBoolMap<Iterator>(it);
29.15 }
29.16
29.17 + /// Provides an immutable and unique id for each item in the graph.
29.18 +
29.19 + /// The IdMap class provides a unique and immutable id for each item of the
29.20 + /// same type (e.g. node) in the graph. This id is <ul><li>\b unique:
29.21 + /// different items (nodes) get different ids <li>\b immutable: the id of an
29.22 + /// item (node) does not change (even if you delete other nodes). </ul>
29.23 + /// Through this map you get access (i.e. can read) the inner id values of
29.24 + /// the items stored in the graph. This map can be inverted with its member
29.25 + /// class \c InverseMap or with the \c operator() member.
29.26 + ///
29.27 + template <typename _Graph, typename _Item>
29.28 + class IdMap {
29.29 + public:
29.30 + typedef _Graph Graph;
29.31 + typedef int Value;
29.32 + typedef _Item Item;
29.33 + typedef _Item Key;
29.34 +
29.35 + /// \brief Constructor.
29.36 + ///
29.37 + /// Constructor of the map.
29.38 + explicit IdMap(const Graph& graph) : _graph(&graph) {}
29.39 +
29.40 + /// \brief Gives back the \e id of the item.
29.41 + ///
29.42 + /// Gives back the immutable and unique \e id of the item.
29.43 + int operator[](const Item& item) const { return _graph->id(item);}
29.44 +
29.45 + /// \brief Gives back the item by its id.
29.46 + ///
29.47 + /// Gives back the item by its id.
29.48 + Item operator()(int id) { return _graph->fromId(id, Item()); }
29.49 +
29.50 + private:
29.51 + const Graph* _graph;
29.52 +
29.53 + public:
29.54 +
29.55 + /// \brief The class represents the inverse of its owner (IdMap).
29.56 + ///
29.57 + /// The class represents the inverse of its owner (IdMap).
29.58 + /// \see inverse()
29.59 + class InverseMap {
29.60 + public:
29.61 +
29.62 + /// \brief Constructor.
29.63 + ///
29.64 + /// Constructor for creating an id-to-item map.
29.65 + explicit InverseMap(const Graph& graph) : _graph(&graph) {}
29.66 +
29.67 + /// \brief Constructor.
29.68 + ///
29.69 + /// Constructor for creating an id-to-item map.
29.70 + explicit InverseMap(const IdMap& map) : _graph(map._graph) {}
29.71 +
29.72 + /// \brief Gives back the given item from its id.
29.73 + ///
29.74 + /// Gives back the given item from its id.
29.75 + ///
29.76 + Item operator[](int id) const { return _graph->fromId(id, Item());}
29.77 +
29.78 + private:
29.79 + const Graph* _graph;
29.80 + };
29.81 +
29.82 + /// \brief Gives back the inverse of the map.
29.83 + ///
29.84 + /// Gives back the inverse of the IdMap.
29.85 + InverseMap inverse() const { return InverseMap(*_graph);}
29.86 +
29.87 + };
29.88 +
29.89 +
29.90 + /// \brief General invertable graph-map type.
29.91 +
29.92 + /// This type provides simple invertable graph-maps.
29.93 + /// The InvertableMap wraps an arbitrary ReadWriteMap
29.94 + /// and if a key is set to a new value then store it
29.95 + /// in the inverse map.
29.96 + ///
29.97 + /// The values of the map can be accessed
29.98 + /// with stl compatible forward iterator.
29.99 + ///
29.100 + /// \tparam _Graph The graph type.
29.101 + /// \tparam _Item The item type of the graph.
29.102 + /// \tparam _Value The value type of the map.
29.103 + ///
29.104 + /// \see IterableValueMap
29.105 + template <typename _Graph, typename _Item, typename _Value>
29.106 + class InvertableMap
29.107 + : protected ItemSetTraits<_Graph, _Item>::template Map<_Value>::Type {
29.108 + private:
29.109 +
29.110 + typedef typename ItemSetTraits<_Graph, _Item>::
29.111 + template Map<_Value>::Type Map;
29.112 + typedef _Graph Graph;
29.113 +
29.114 + typedef std::map<_Value, _Item> Container;
29.115 + Container _inv_map;
29.116 +
29.117 + public:
29.118 +
29.119 + /// The key type of InvertableMap (Node, Arc, Edge).
29.120 + typedef typename Map::Key Key;
29.121 + /// The value type of the InvertableMap.
29.122 + typedef typename Map::Value Value;
29.123 +
29.124 +
29.125 +
29.126 + /// \brief Constructor.
29.127 + ///
29.128 + /// Construct a new InvertableMap for the graph.
29.129 + ///
29.130 + explicit InvertableMap(const Graph& graph) : Map(graph) {}
29.131 +
29.132 + /// \brief Forward iterator for values.
29.133 + ///
29.134 + /// This iterator is an stl compatible forward
29.135 + /// iterator on the values of the map. The values can
29.136 + /// be accessed in the [beginValue, endValue) range.
29.137 + ///
29.138 + class ValueIterator
29.139 + : public std::iterator<std::forward_iterator_tag, Value> {
29.140 + friend class InvertableMap;
29.141 + private:
29.142 + ValueIterator(typename Container::const_iterator _it)
29.143 + : it(_it) {}
29.144 + public:
29.145 +
29.146 + ValueIterator() {}
29.147 +
29.148 + ValueIterator& operator++() { ++it; return *this; }
29.149 + ValueIterator operator++(int) {
29.150 + ValueIterator tmp(*this);
29.151 + operator++();
29.152 + return tmp;
29.153 + }
29.154 +
29.155 + const Value& operator*() const { return it->first; }
29.156 + const Value* operator->() const { return &(it->first); }
29.157 +
29.158 + bool operator==(ValueIterator jt) const { return it == jt.it; }
29.159 + bool operator!=(ValueIterator jt) const { return it != jt.it; }
29.160 +
29.161 + private:
29.162 + typename Container::const_iterator it;
29.163 + };
29.164 +
29.165 + /// \brief Returns an iterator to the first value.
29.166 + ///
29.167 + /// Returns an stl compatible iterator to the
29.168 + /// first value of the map. The values of the
29.169 + /// map can be accessed in the [beginValue, endValue)
29.170 + /// range.
29.171 + ValueIterator beginValue() const {
29.172 + return ValueIterator(_inv_map.begin());
29.173 + }
29.174 +
29.175 + /// \brief Returns an iterator after the last value.
29.176 + ///
29.177 + /// Returns an stl compatible iterator after the
29.178 + /// last value of the map. The values of the
29.179 + /// map can be accessed in the [beginValue, endValue)
29.180 + /// range.
29.181 + ValueIterator endValue() const {
29.182 + return ValueIterator(_inv_map.end());
29.183 + }
29.184 +
29.185 + /// \brief The setter function of the map.
29.186 + ///
29.187 + /// Sets the mapped value.
29.188 + void set(const Key& key, const Value& val) {
29.189 + Value oldval = Map::operator[](key);
29.190 + typename Container::iterator it = _inv_map.find(oldval);
29.191 + if (it != _inv_map.end() && it->second == key) {
29.192 + _inv_map.erase(it);
29.193 + }
29.194 + _inv_map.insert(make_pair(val, key));
29.195 + Map::set(key, val);
29.196 + }
29.197 +
29.198 + /// \brief The getter function of the map.
29.199 + ///
29.200 + /// It gives back the value associated with the key.
29.201 + typename MapTraits<Map>::ConstReturnValue
29.202 + operator[](const Key& key) const {
29.203 + return Map::operator[](key);
29.204 + }
29.205 +
29.206 + /// \brief Gives back the item by its value.
29.207 + ///
29.208 + /// Gives back the item by its value.
29.209 + Key operator()(const Value& key) const {
29.210 + typename Container::const_iterator it = _inv_map.find(key);
29.211 + return it != _inv_map.end() ? it->second : INVALID;
29.212 + }
29.213 +
29.214 + protected:
29.215 +
29.216 + /// \brief Erase the key from the map.
29.217 + ///
29.218 + /// Erase the key to the map. It is called by the
29.219 + /// \c AlterationNotifier.
29.220 + virtual void erase(const Key& key) {
29.221 + Value val = Map::operator[](key);
29.222 + typename Container::iterator it = _inv_map.find(val);
29.223 + if (it != _inv_map.end() && it->second == key) {
29.224 + _inv_map.erase(it);
29.225 + }
29.226 + Map::erase(key);
29.227 + }
29.228 +
29.229 + /// \brief Erase more keys from the map.
29.230 + ///
29.231 + /// Erase more keys from the map. It is called by the
29.232 + /// \c AlterationNotifier.
29.233 + virtual void erase(const std::vector<Key>& keys) {
29.234 + for (int i = 0; i < int(keys.size()); ++i) {
29.235 + Value val = Map::operator[](keys[i]);
29.236 + typename Container::iterator it = _inv_map.find(val);
29.237 + if (it != _inv_map.end() && it->second == keys[i]) {
29.238 + _inv_map.erase(it);
29.239 + }
29.240 + }
29.241 + Map::erase(keys);
29.242 + }
29.243 +
29.244 + /// \brief Clear the keys from the map and inverse map.
29.245 + ///
29.246 + /// Clear the keys from the map and inverse map. It is called by the
29.247 + /// \c AlterationNotifier.
29.248 + virtual void clear() {
29.249 + _inv_map.clear();
29.250 + Map::clear();
29.251 + }
29.252 +
29.253 + public:
29.254 +
29.255 + /// \brief The inverse map type.
29.256 + ///
29.257 + /// The inverse of this map. The subscript operator of the map
29.258 + /// gives back always the item what was last assigned to the value.
29.259 + class InverseMap {
29.260 + public:
29.261 + /// \brief Constructor of the InverseMap.
29.262 + ///
29.263 + /// Constructor of the InverseMap.
29.264 + explicit InverseMap(const InvertableMap& inverted)
29.265 + : _inverted(inverted) {}
29.266 +
29.267 + /// The value type of the InverseMap.
29.268 + typedef typename InvertableMap::Key Value;
29.269 + /// The key type of the InverseMap.
29.270 + typedef typename InvertableMap::Value Key;
29.271 +
29.272 + /// \brief Subscript operator.
29.273 + ///
29.274 + /// Subscript operator. It gives back always the item
29.275 + /// what was last assigned to the value.
29.276 + Value operator[](const Key& key) const {
29.277 + return _inverted(key);
29.278 + }
29.279 +
29.280 + private:
29.281 + const InvertableMap& _inverted;
29.282 + };
29.283 +
29.284 + /// \brief It gives back the just readable inverse map.
29.285 + ///
29.286 + /// It gives back the just readable inverse map.
29.287 + InverseMap inverse() const {
29.288 + return InverseMap(*this);
29.289 + }
29.290 +
29.291 +
29.292 +
29.293 + };
29.294 +
29.295 + /// \brief Provides a mutable, continuous and unique descriptor for each
29.296 + /// item in the graph.
29.297 + ///
29.298 + /// The DescriptorMap class provides a unique and continuous (but mutable)
29.299 + /// descriptor (id) for each item of the same type (e.g. node) in the
29.300 + /// graph. This id is <ul><li>\b unique: different items (nodes) get
29.301 + /// different ids <li>\b continuous: the range of the ids is the set of
29.302 + /// integers between 0 and \c n-1, where \c n is the number of the items of
29.303 + /// this type (e.g. nodes) (so the id of a node can change if you delete an
29.304 + /// other node, i.e. this id is mutable). </ul> This map can be inverted
29.305 + /// with its member class \c InverseMap, or with the \c operator() member.
29.306 + ///
29.307 + /// \tparam _Graph The graph class the \c DescriptorMap belongs to.
29.308 + /// \tparam _Item The Item is the Key of the Map. It may be Node, Arc or
29.309 + /// Edge.
29.310 + template <typename _Graph, typename _Item>
29.311 + class DescriptorMap
29.312 + : protected ItemSetTraits<_Graph, _Item>::template Map<int>::Type {
29.313 +
29.314 + typedef _Item Item;
29.315 + typedef typename ItemSetTraits<_Graph, _Item>::template Map<int>::Type Map;
29.316 +
29.317 + public:
29.318 + /// The graph class of DescriptorMap.
29.319 + typedef _Graph Graph;
29.320 +
29.321 + /// The key type of DescriptorMap (Node, Arc, Edge).
29.322 + typedef typename Map::Key Key;
29.323 + /// The value type of DescriptorMap.
29.324 + typedef typename Map::Value Value;
29.325 +
29.326 + /// \brief Constructor.
29.327 + ///
29.328 + /// Constructor for descriptor map.
29.329 + explicit DescriptorMap(const Graph& _graph) : Map(_graph) {
29.330 + Item it;
29.331 + const typename Map::Notifier* nf = Map::notifier();
29.332 + for (nf->first(it); it != INVALID; nf->next(it)) {
29.333 + Map::set(it, _inv_map.size());
29.334 + _inv_map.push_back(it);
29.335 + }
29.336 + }
29.337 +
29.338 + protected:
29.339 +
29.340 + /// \brief Add a new key to the map.
29.341 + ///
29.342 + /// Add a new key to the map. It is called by the
29.343 + /// \c AlterationNotifier.
29.344 + virtual void add(const Item& item) {
29.345 + Map::add(item);
29.346 + Map::set(item, _inv_map.size());
29.347 + _inv_map.push_back(item);
29.348 + }
29.349 +
29.350 + /// \brief Add more new keys to the map.
29.351 + ///
29.352 + /// Add more new keys to the map. It is called by the
29.353 + /// \c AlterationNotifier.
29.354 + virtual void add(const std::vector<Item>& items) {
29.355 + Map::add(items);
29.356 + for (int i = 0; i < int(items.size()); ++i) {
29.357 + Map::set(items[i], _inv_map.size());
29.358 + _inv_map.push_back(items[i]);
29.359 + }
29.360 + }
29.361 +
29.362 + /// \brief Erase the key from the map.
29.363 + ///
29.364 + /// Erase the key from the map. It is called by the
29.365 + /// \c AlterationNotifier.
29.366 + virtual void erase(const Item& item) {
29.367 + Map::set(_inv_map.back(), Map::operator[](item));
29.368 + _inv_map[Map::operator[](item)] = _inv_map.back();
29.369 + _inv_map.pop_back();
29.370 + Map::erase(item);
29.371 + }
29.372 +
29.373 + /// \brief Erase more keys from the map.
29.374 + ///
29.375 + /// Erase more keys from the map. It is called by the
29.376 + /// \c AlterationNotifier.
29.377 + virtual void erase(const std::vector<Item>& items) {
29.378 + for (int i = 0; i < int(items.size()); ++i) {
29.379 + Map::set(_inv_map.back(), Map::operator[](items[i]));
29.380 + _inv_map[Map::operator[](items[i])] = _inv_map.back();
29.381 + _inv_map.pop_back();
29.382 + }
29.383 + Map::erase(items);
29.384 + }
29.385 +
29.386 + /// \brief Build the unique map.
29.387 + ///
29.388 + /// Build the unique map. It is called by the
29.389 + /// \c AlterationNotifier.
29.390 + virtual void build() {
29.391 + Map::build();
29.392 + Item it;
29.393 + const typename Map::Notifier* nf = Map::notifier();
29.394 + for (nf->first(it); it != INVALID; nf->next(it)) {
29.395 + Map::set(it, _inv_map.size());
29.396 + _inv_map.push_back(it);
29.397 + }
29.398 + }
29.399 +
29.400 + /// \brief Clear the keys from the map.
29.401 + ///
29.402 + /// Clear the keys from the map. It is called by the
29.403 + /// \c AlterationNotifier.
29.404 + virtual void clear() {
29.405 + _inv_map.clear();
29.406 + Map::clear();
29.407 + }
29.408 +
29.409 + public:
29.410 +
29.411 + /// \brief Returns the maximal value plus one.
29.412 + ///
29.413 + /// Returns the maximal value plus one in the map.
29.414 + unsigned int size() const {
29.415 + return _inv_map.size();
29.416 + }
29.417 +
29.418 + /// \brief Swaps the position of the two items in the map.
29.419 + ///
29.420 + /// Swaps the position of the two items in the map.
29.421 + void swap(const Item& p, const Item& q) {
29.422 + int pi = Map::operator[](p);
29.423 + int qi = Map::operator[](q);
29.424 + Map::set(p, qi);
29.425 + _inv_map[qi] = p;
29.426 + Map::set(q, pi);
29.427 + _inv_map[pi] = q;
29.428 + }
29.429 +
29.430 + /// \brief Gives back the \e descriptor of the item.
29.431 + ///
29.432 + /// Gives back the mutable and unique \e descriptor of the map.
29.433 + int operator[](const Item& item) const {
29.434 + return Map::operator[](item);
29.435 + }
29.436 +
29.437 + /// \brief Gives back the item by its descriptor.
29.438 + ///
29.439 + /// Gives back th item by its descriptor.
29.440 + Item operator()(int id) const {
29.441 + return _inv_map[id];
29.442 + }
29.443 +
29.444 + private:
29.445 +
29.446 + typedef std::vector<Item> Container;
29.447 + Container _inv_map;
29.448 +
29.449 + public:
29.450 + /// \brief The inverse map type of DescriptorMap.
29.451 + ///
29.452 + /// The inverse map type of DescriptorMap.
29.453 + class InverseMap {
29.454 + public:
29.455 + /// \brief Constructor of the InverseMap.
29.456 + ///
29.457 + /// Constructor of the InverseMap.
29.458 + explicit InverseMap(const DescriptorMap& inverted)
29.459 + : _inverted(inverted) {}
29.460 +
29.461 +
29.462 + /// The value type of the InverseMap.
29.463 + typedef typename DescriptorMap::Key Value;
29.464 + /// The key type of the InverseMap.
29.465 + typedef typename DescriptorMap::Value Key;
29.466 +
29.467 + /// \brief Subscript operator.
29.468 + ///
29.469 + /// Subscript operator. It gives back the item
29.470 + /// that the descriptor belongs to currently.
29.471 + Value operator[](const Key& key) const {
29.472 + return _inverted(key);
29.473 + }
29.474 +
29.475 + /// \brief Size of the map.
29.476 + ///
29.477 + /// Returns the size of the map.
29.478 + unsigned int size() const {
29.479 + return _inverted.size();
29.480 + }
29.481 +
29.482 + private:
29.483 + const DescriptorMap& _inverted;
29.484 + };
29.485 +
29.486 + /// \brief Gives back the inverse of the map.
29.487 + ///
29.488 + /// Gives back the inverse of the map.
29.489 + const InverseMap inverse() const {
29.490 + return InverseMap(*this);
29.491 + }
29.492 + };
29.493 +
29.494 + /// \brief Returns the source of the given arc.
29.495 + ///
29.496 + /// The SourceMap gives back the source Node of the given arc.
29.497 + /// \see TargetMap
29.498 + template <typename Digraph>
29.499 + class SourceMap {
29.500 + public:
29.501 +
29.502 + typedef typename Digraph::Node Value;
29.503 + typedef typename Digraph::Arc Key;
29.504 +
29.505 + /// \brief Constructor
29.506 + ///
29.507 + /// Constructor
29.508 + /// \param _digraph The digraph that the map belongs to.
29.509 + explicit SourceMap(const Digraph& digraph) : _digraph(digraph) {}
29.510 +
29.511 + /// \brief The subscript operator.
29.512 + ///
29.513 + /// The subscript operator.
29.514 + /// \param arc The arc
29.515 + /// \return The source of the arc
29.516 + Value operator[](const Key& arc) const {
29.517 + return _digraph.source(arc);
29.518 + }
29.519 +
29.520 + private:
29.521 + const Digraph& _digraph;
29.522 + };
29.523 +
29.524 + /// \brief Returns a \ref SourceMap class.
29.525 + ///
29.526 + /// This function just returns an \ref SourceMap class.
29.527 + /// \relates SourceMap
29.528 + template <typename Digraph>
29.529 + inline SourceMap<Digraph> sourceMap(const Digraph& digraph) {
29.530 + return SourceMap<Digraph>(digraph);
29.531 + }
29.532 +
29.533 + /// \brief Returns the target of the given arc.
29.534 + ///
29.535 + /// The TargetMap gives back the target Node of the given arc.
29.536 + /// \see SourceMap
29.537 + template <typename Digraph>
29.538 + class TargetMap {
29.539 + public:
29.540 +
29.541 + typedef typename Digraph::Node Value;
29.542 + typedef typename Digraph::Arc Key;
29.543 +
29.544 + /// \brief Constructor
29.545 + ///
29.546 + /// Constructor
29.547 + /// \param _digraph The digraph that the map belongs to.
29.548 + explicit TargetMap(const Digraph& digraph) : _digraph(digraph) {}
29.549 +
29.550 + /// \brief The subscript operator.
29.551 + ///
29.552 + /// The subscript operator.
29.553 + /// \param e The arc
29.554 + /// \return The target of the arc
29.555 + Value operator[](const Key& e) const {
29.556 + return _digraph.target(e);
29.557 + }
29.558 +
29.559 + private:
29.560 + const Digraph& _digraph;
29.561 + };
29.562 +
29.563 + /// \brief Returns a \ref TargetMap class.
29.564 + ///
29.565 + /// This function just returns a \ref TargetMap class.
29.566 + /// \relates TargetMap
29.567 + template <typename Digraph>
29.568 + inline TargetMap<Digraph> targetMap(const Digraph& digraph) {
29.569 + return TargetMap<Digraph>(digraph);
29.570 + }
29.571 +
29.572 + /// \brief Returns the "forward" directed arc view of an edge.
29.573 + ///
29.574 + /// Returns the "forward" directed arc view of an edge.
29.575 + /// \see BackwardMap
29.576 + template <typename Graph>
29.577 + class ForwardMap {
29.578 + public:
29.579 +
29.580 + typedef typename Graph::Arc Value;
29.581 + typedef typename Graph::Edge Key;
29.582 +
29.583 + /// \brief Constructor
29.584 + ///
29.585 + /// Constructor
29.586 + /// \param _graph The graph that the map belongs to.
29.587 + explicit ForwardMap(const Graph& graph) : _graph(graph) {}
29.588 +
29.589 + /// \brief The subscript operator.
29.590 + ///
29.591 + /// The subscript operator.
29.592 + /// \param key An edge
29.593 + /// \return The "forward" directed arc view of edge
29.594 + Value operator[](const Key& key) const {
29.595 + return _graph.direct(key, true);
29.596 + }
29.597 +
29.598 + private:
29.599 + const Graph& _graph;
29.600 + };
29.601 +
29.602 + /// \brief Returns a \ref ForwardMap class.
29.603 + ///
29.604 + /// This function just returns an \ref ForwardMap class.
29.605 + /// \relates ForwardMap
29.606 + template <typename Graph>
29.607 + inline ForwardMap<Graph> forwardMap(const Graph& graph) {
29.608 + return ForwardMap<Graph>(graph);
29.609 + }
29.610 +
29.611 + /// \brief Returns the "backward" directed arc view of an edge.
29.612 + ///
29.613 + /// Returns the "backward" directed arc view of an edge.
29.614 + /// \see ForwardMap
29.615 + template <typename Graph>
29.616 + class BackwardMap {
29.617 + public:
29.618 +
29.619 + typedef typename Graph::Arc Value;
29.620 + typedef typename Graph::Edge Key;
29.621 +
29.622 + /// \brief Constructor
29.623 + ///
29.624 + /// Constructor
29.625 + /// \param _graph The graph that the map belongs to.
29.626 + explicit BackwardMap(const Graph& graph) : _graph(graph) {}
29.627 +
29.628 + /// \brief The subscript operator.
29.629 + ///
29.630 + /// The subscript operator.
29.631 + /// \param key An edge
29.632 + /// \return The "backward" directed arc view of edge
29.633 + Value operator[](const Key& key) const {
29.634 + return _graph.direct(key, false);
29.635 + }
29.636 +
29.637 + private:
29.638 + const Graph& _graph;
29.639 + };
29.640 +
29.641 + /// \brief Returns a \ref BackwardMap class
29.642 +
29.643 + /// This function just returns a \ref BackwardMap class.
29.644 + /// \relates BackwardMap
29.645 + template <typename Graph>
29.646 + inline BackwardMap<Graph> backwardMap(const Graph& graph) {
29.647 + return BackwardMap<Graph>(graph);
29.648 + }
29.649 +
29.650 + /// \brief Potential difference map
29.651 + ///
29.652 + /// If there is an potential map on the nodes then we
29.653 + /// can get an arc map as we get the substraction of the
29.654 + /// values of the target and source.
29.655 + template <typename Digraph, typename NodeMap>
29.656 + class PotentialDifferenceMap {
29.657 + public:
29.658 + typedef typename Digraph::Arc Key;
29.659 + typedef typename NodeMap::Value Value;
29.660 +
29.661 + /// \brief Constructor
29.662 + ///
29.663 + /// Contructor of the map
29.664 + explicit PotentialDifferenceMap(const Digraph& digraph,
29.665 + const NodeMap& potential)
29.666 + : _digraph(digraph), _potential(potential) {}
29.667 +
29.668 + /// \brief Const subscription operator
29.669 + ///
29.670 + /// Const subscription operator
29.671 + Value operator[](const Key& arc) const {
29.672 + return _potential[_digraph.target(arc)] -
29.673 + _potential[_digraph.source(arc)];
29.674 + }
29.675 +
29.676 + private:
29.677 + const Digraph& _digraph;
29.678 + const NodeMap& _potential;
29.679 + };
29.680 +
29.681 + /// \brief Returns a PotentialDifferenceMap.
29.682 + ///
29.683 + /// This function just returns a PotentialDifferenceMap.
29.684 + /// \relates PotentialDifferenceMap
29.685 + template <typename Digraph, typename NodeMap>
29.686 + PotentialDifferenceMap<Digraph, NodeMap>
29.687 + potentialDifferenceMap(const Digraph& digraph, const NodeMap& potential) {
29.688 + return PotentialDifferenceMap<Digraph, NodeMap>(digraph, potential);
29.689 + }
29.690 +
29.691 + /// \brief Map of the node in-degrees.
29.692 + ///
29.693 + /// This map returns the in-degree of a node. Once it is constructed,
29.694 + /// the degrees are stored in a standard NodeMap, so each query is done
29.695 + /// in constant time. On the other hand, the values are updated automatically
29.696 + /// whenever the digraph changes.
29.697 + ///
29.698 + /// \warning Besides addNode() and addArc(), a digraph structure may provide
29.699 + /// alternative ways to modify the digraph. The correct behavior of InDegMap
29.700 + /// is not guarantied if these additional features are used. For example
29.701 + /// the functions \ref ListDigraph::changeSource() "changeSource()",
29.702 + /// \ref ListDigraph::changeTarget() "changeTarget()" and
29.703 + /// \ref ListDigraph::reverseArc() "reverseArc()"
29.704 + /// of \ref ListDigraph will \e not update the degree values correctly.
29.705 + ///
29.706 + /// \sa OutDegMap
29.707 +
29.708 + template <typename _Digraph>
29.709 + class InDegMap
29.710 + : protected ItemSetTraits<_Digraph, typename _Digraph::Arc>
29.711 + ::ItemNotifier::ObserverBase {
29.712 +
29.713 + public:
29.714 +
29.715 + typedef _Digraph Digraph;
29.716 + typedef int Value;
29.717 + typedef typename Digraph::Node Key;
29.718 +
29.719 + typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
29.720 + ::ItemNotifier::ObserverBase Parent;
29.721 +
29.722 + private:
29.723 +
29.724 + class AutoNodeMap
29.725 + : public ItemSetTraits<Digraph, Key>::template Map<int>::Type {
29.726 + public:
29.727 +
29.728 + typedef typename ItemSetTraits<Digraph, Key>::
29.729 + template Map<int>::Type Parent;
29.730 +
29.731 + AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {}
29.732 +
29.733 + virtual void add(const Key& key) {
29.734 + Parent::add(key);
29.735 + Parent::set(key, 0);
29.736 + }
29.737 +
29.738 + virtual void add(const std::vector<Key>& keys) {
29.739 + Parent::add(keys);
29.740 + for (int i = 0; i < int(keys.size()); ++i) {
29.741 + Parent::set(keys[i], 0);
29.742 + }
29.743 + }
29.744 +
29.745 + virtual void build() {
29.746 + Parent::build();
29.747 + Key it;
29.748 + typename Parent::Notifier* nf = Parent::notifier();
29.749 + for (nf->first(it); it != INVALID; nf->next(it)) {
29.750 + Parent::set(it, 0);
29.751 + }
29.752 + }
29.753 + };
29.754 +
29.755 + public:
29.756 +
29.757 + /// \brief Constructor.
29.758 + ///
29.759 + /// Constructor for creating in-degree map.
29.760 + explicit InDegMap(const Digraph& digraph)
29.761 + : _digraph(digraph), _deg(digraph) {
29.762 + Parent::attach(_digraph.notifier(typename Digraph::Arc()));
29.763 +
29.764 + for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
29.765 + _deg[it] = countInArcs(_digraph, it);
29.766 + }
29.767 + }
29.768 +
29.769 + /// Gives back the in-degree of a Node.
29.770 + int operator[](const Key& key) const {
29.771 + return _deg[key];
29.772 + }
29.773 +
29.774 + protected:
29.775 +
29.776 + typedef typename Digraph::Arc Arc;
29.777 +
29.778 + virtual void add(const Arc& arc) {
29.779 + ++_deg[_digraph.target(arc)];
29.780 + }
29.781 +
29.782 + virtual void add(const std::vector<Arc>& arcs) {
29.783 + for (int i = 0; i < int(arcs.size()); ++i) {
29.784 + ++_deg[_digraph.target(arcs[i])];
29.785 + }
29.786 + }
29.787 +
29.788 + virtual void erase(const Arc& arc) {
29.789 + --_deg[_digraph.target(arc)];
29.790 + }
29.791 +
29.792 + virtual void erase(const std::vector<Arc>& arcs) {
29.793 + for (int i = 0; i < int(arcs.size()); ++i) {
29.794 + --_deg[_digraph.target(arcs[i])];
29.795 + }
29.796 + }
29.797 +
29.798 + virtual void build() {
29.799 + for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
29.800 + _deg[it] = countInArcs(_digraph, it);
29.801 + }
29.802 + }
29.803 +
29.804 + virtual void clear() {
29.805 + for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
29.806 + _deg[it] = 0;
29.807 + }
29.808 + }
29.809 + private:
29.810 +
29.811 + const Digraph& _digraph;
29.812 + AutoNodeMap _deg;
29.813 + };
29.814 +
29.815 + /// \brief Map of the node out-degrees.
29.816 + ///
29.817 + /// This map returns the out-degree of a node. Once it is constructed,
29.818 + /// the degrees are stored in a standard NodeMap, so each query is done
29.819 + /// in constant time. On the other hand, the values are updated automatically
29.820 + /// whenever the digraph changes.
29.821 + ///
29.822 + /// \warning Besides addNode() and addArc(), a digraph structure may provide
29.823 + /// alternative ways to modify the digraph. The correct behavior of OutDegMap
29.824 + /// is not guarantied if these additional features are used. For example
29.825 + /// the functions \ref ListDigraph::changeSource() "changeSource()",
29.826 + /// \ref ListDigraph::changeTarget() "changeTarget()" and
29.827 + /// \ref ListDigraph::reverseArc() "reverseArc()"
29.828 + /// of \ref ListDigraph will \e not update the degree values correctly.
29.829 + ///
29.830 + /// \sa InDegMap
29.831 +
29.832 + template <typename _Digraph>
29.833 + class OutDegMap
29.834 + : protected ItemSetTraits<_Digraph, typename _Digraph::Arc>
29.835 + ::ItemNotifier::ObserverBase {
29.836 +
29.837 + public:
29.838 +
29.839 + typedef _Digraph Digraph;
29.840 + typedef int Value;
29.841 + typedef typename Digraph::Node Key;
29.842 +
29.843 + typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
29.844 + ::ItemNotifier::ObserverBase Parent;
29.845 +
29.846 + private:
29.847 +
29.848 + class AutoNodeMap
29.849 + : public ItemSetTraits<Digraph, Key>::template Map<int>::Type {
29.850 + public:
29.851 +
29.852 + typedef typename ItemSetTraits<Digraph, Key>::
29.853 + template Map<int>::Type Parent;
29.854 +
29.855 + AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {}
29.856 +
29.857 + virtual void add(const Key& key) {
29.858 + Parent::add(key);
29.859 + Parent::set(key, 0);
29.860 + }
29.861 + virtual void add(const std::vector<Key>& keys) {
29.862 + Parent::add(keys);
29.863 + for (int i = 0; i < int(keys.size()); ++i) {
29.864 + Parent::set(keys[i], 0);
29.865 + }
29.866 + }
29.867 + virtual void build() {
29.868 + Parent::build();
29.869 + Key it;
29.870 + typename Parent::Notifier* nf = Parent::notifier();
29.871 + for (nf->first(it); it != INVALID; nf->next(it)) {
29.872 + Parent::set(it, 0);
29.873 + }
29.874 + }
29.875 + };
29.876 +
29.877 + public:
29.878 +
29.879 + /// \brief Constructor.
29.880 + ///
29.881 + /// Constructor for creating out-degree map.
29.882 + explicit OutDegMap(const Digraph& digraph)
29.883 + : _digraph(digraph), _deg(digraph) {
29.884 + Parent::attach(_digraph.notifier(typename Digraph::Arc()));
29.885 +
29.886 + for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
29.887 + _deg[it] = countOutArcs(_digraph, it);
29.888 + }
29.889 + }
29.890 +
29.891 + /// Gives back the out-degree of a Node.
29.892 + int operator[](const Key& key) const {
29.893 + return _deg[key];
29.894 + }
29.895 +
29.896 + protected:
29.897 +
29.898 + typedef typename Digraph::Arc Arc;
29.899 +
29.900 + virtual void add(const Arc& arc) {
29.901 + ++_deg[_digraph.source(arc)];
29.902 + }
29.903 +
29.904 + virtual void add(const std::vector<Arc>& arcs) {
29.905 + for (int i = 0; i < int(arcs.size()); ++i) {
29.906 + ++_deg[_digraph.source(arcs[i])];
29.907 + }
29.908 + }
29.909 +
29.910 + virtual void erase(const Arc& arc) {
29.911 + --_deg[_digraph.source(arc)];
29.912 + }
29.913 +
29.914 + virtual void erase(const std::vector<Arc>& arcs) {
29.915 + for (int i = 0; i < int(arcs.size()); ++i) {
29.916 + --_deg[_digraph.source(arcs[i])];
29.917 + }
29.918 + }
29.919 +
29.920 + virtual void build() {
29.921 + for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
29.922 + _deg[it] = countOutArcs(_digraph, it);
29.923 + }
29.924 + }
29.925 +
29.926 + virtual void clear() {
29.927 + for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
29.928 + _deg[it] = 0;
29.929 + }
29.930 + }
29.931 + private:
29.932 +
29.933 + const Digraph& _digraph;
29.934 + AutoNodeMap _deg;
29.935 + };
29.936 +
29.937 /// @}
29.938 }
29.939
30.1 --- a/lemon/path.h Tue Jul 15 18:43:41 2008 +0100
30.2 +++ b/lemon/path.h Tue Jul 15 18:49:30 2008 +0100
30.3 @@ -28,7 +28,7 @@
30.4 #include <algorithm>
30.5
30.6 #include <lemon/error.h>
30.7 -#include <lemon/bits/invalid.h>
30.8 +#include <lemon/core.h>
30.9 #include <lemon/concepts/path.h>
30.10
30.11 namespace lemon {
31.1 --- a/lemon/smart_graph.h Tue Jul 15 18:43:41 2008 +0100
31.2 +++ b/lemon/smart_graph.h Tue Jul 15 18:49:30 2008 +0100
31.3 @@ -25,14 +25,8 @@
31.4
31.5 #include <vector>
31.6
31.7 -#include <lemon/bits/invalid.h>
31.8 -
31.9 -#include <lemon/bits/base_extender.h>
31.10 -#include <lemon/bits/graph_extender.h>
31.11 -
31.12 -#include <lemon/bits/utility.h>
31.13 +#include <lemon/core.h>
31.14 #include <lemon/error.h>
31.15 -
31.16 #include <lemon/bits/graph_extender.h>
31.17
31.18 namespace lemon {
32.1 --- a/lemon/unionfind.h Tue Jul 15 18:43:41 2008 +0100
32.2 +++ b/lemon/unionfind.h Tue Jul 15 18:49:30 2008 +0100
32.3 @@ -30,7 +30,7 @@
32.4 #include <algorithm>
32.5 #include <functional>
32.6
32.7 -#include <lemon/bits/invalid.h>
32.8 +#include <lemon/core.h>
32.9
32.10 namespace lemon {
32.11
33.1 --- a/test/dijkstra_test.cc Tue Jul 15 18:43:41 2008 +0100
33.2 +++ b/test/dijkstra_test.cc Tue Jul 15 18:49:30 2008 +0100
33.3 @@ -19,7 +19,6 @@
33.4 #include <lemon/concepts/digraph.h>
33.5 #include <lemon/smart_graph.h>
33.6 #include <lemon/list_graph.h>
33.7 -#include <lemon/graph_utils.h>
33.8 #include <lemon/dijkstra.h>
33.9 #include <lemon/path.h>
33.10
34.1 --- a/test/graph_copy_test.cc Tue Jul 15 18:43:41 2008 +0100
34.2 +++ b/test/graph_copy_test.cc Tue Jul 15 18:49:30 2008 +0100
34.3 @@ -19,7 +19,6 @@
34.4 #include <lemon/smart_graph.h>
34.5 #include <lemon/list_graph.h>
34.6 #include <lemon/lgf_reader.h>
34.7 -#include <lemon/graph_utils.h>
34.8 #include <lemon/error.h>
34.9
34.10 #include "test_tools.h"
35.1 --- a/test/graph_test.h Tue Jul 15 18:43:41 2008 +0100
35.2 +++ b/test/graph_test.h Tue Jul 15 18:49:30 2008 +0100
35.3 @@ -19,7 +19,7 @@
35.4 #ifndef LEMON_TEST_GRAPH_TEST_H
35.5 #define LEMON_TEST_GRAPH_TEST_H
35.6
35.7 -#include <lemon/graph_utils.h>
35.8 +#include <lemon/core.h>
35.9 #include "test_tools.h"
35.10
35.11 namespace lemon {
36.1 --- a/test/graph_utils_test.cc Tue Jul 15 18:43:41 2008 +0100
36.2 +++ b/test/graph_utils_test.cc Tue Jul 15 18:49:30 2008 +0100
36.3 @@ -20,9 +20,9 @@
36.4 #include <ctime>
36.5
36.6 #include <lemon/random.h>
36.7 -#include <lemon/graph_utils.h>
36.8 #include <lemon/list_graph.h>
36.9 #include <lemon/smart_graph.h>
36.10 +#include <lemon/maps.h>
36.11
36.12 #include "graph_test.h"
36.13 #include "test_tools.h"