|
1 /* -*- C++ -*- |
|
2 * |
|
3 * This file is a part of LEMON, a generic C++ optimization library |
|
4 * |
|
5 * Copyright (C) 2003-2006 |
|
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
|
7 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
|
8 * |
|
9 * Permission to use, modify and distribute this software is granted |
|
10 * provided that this copyright notice appears in all copies. For |
|
11 * precise terms see the accompanying LICENSE file. |
|
12 * |
|
13 * This software is provided "AS IS" with no warranty of any kind, |
|
14 * express or implied, and with no claim as to its suitability for any |
|
15 * purpose. |
|
16 * |
|
17 */ |
|
18 |
|
19 |
|
20 ///\ingroup paths |
|
21 ///\file |
|
22 ///\brief Classes for representing paths in graphs. |
|
23 /// |
|
24 |
|
25 #ifndef LEMON_PATH_UTILS_H |
|
26 #define LEMON_PATH_UTILS_H |
|
27 |
|
28 #include <lemon/concepts/path.h> |
|
29 |
|
30 namespace lemon { |
|
31 |
|
32 namespace _path_bits { |
|
33 |
|
34 template <typename Path, typename Enable = void> |
|
35 struct RevTagIndicator { |
|
36 static const bool value = false; |
|
37 }; |
|
38 |
|
39 template <typename Graph> |
|
40 struct RevTagIndicator< |
|
41 Graph, |
|
42 typename enable_if<typename Graph::RevTag, void>::type |
|
43 > { |
|
44 static const bool value = true; |
|
45 }; |
|
46 |
|
47 template <typename Target, typename Source, |
|
48 typename BuildEnable = void, typename RevEnable = void> |
|
49 struct PathCopySelector { |
|
50 static void copy(Target& target, const Source& source) { |
|
51 source.clear(); |
|
52 for (typename Source::EdgeIt it(source); it != INVALID; ++it) { |
|
53 target.addBack(it); |
|
54 } |
|
55 } |
|
56 }; |
|
57 |
|
58 template <typename Target, typename Source, typename BuildEnable> |
|
59 struct PathCopySelector< |
|
60 Target, Source, BuildEnable, |
|
61 typename enable_if<typename Source::RevPathTag, void>::type> { |
|
62 static void copy(Target& target, const Source& source) { |
|
63 source.clear(); |
|
64 for (typename Source::RevIt it(source); it != INVALID; ++it) { |
|
65 target.addFront(it); |
|
66 } |
|
67 } |
|
68 }; |
|
69 |
|
70 template <typename Target, typename Source, typename RevEnable> |
|
71 struct PathCopySelector< |
|
72 Target, Source, |
|
73 typename enable_if<typename Target::BuildTag, void>::type, RevEnable> { |
|
74 static void copy(Target& target, const Source& source) { |
|
75 target.clear(); |
|
76 target.build(source); |
|
77 } |
|
78 }; |
|
79 |
|
80 template <typename Target, typename Source> |
|
81 struct PathCopySelector< |
|
82 Target, Source, |
|
83 typename enable_if<typename Target::BuildTag, void>::type, |
|
84 typename enable_if<typename Source::RevPathTag, void>::type> { |
|
85 static void copy(Target& target, const Source& source) { |
|
86 target.clear(); |
|
87 target.buildRev(source); |
|
88 } |
|
89 }; |
|
90 |
|
91 } |
|
92 |
|
93 |
|
94 /// \brief Make of copy of a path. |
|
95 /// |
|
96 /// Make of copy of a path. |
|
97 template <typename Target, typename Source> |
|
98 void copyPath(Target& target, const Source& source) { |
|
99 checkConcept<concepts::PathDumper<typename Source::Graph>, Source>(); |
|
100 _path_bits::PathCopySelector<Target, Source>::copy(target, source); |
|
101 } |
|
102 |
|
103 /// \brief Checks the path's consistency. |
|
104 /// |
|
105 /// Checks that each edge's target is the next's source. |
|
106 /// \Checks the path's consistency. |
|
107 /// |
|
108 /// Checks that each edge's target is the next's source. |
|
109 template <typename Graph, typename Path> |
|
110 bool checkPath(const Graph& graph, const Path& path) { |
|
111 typename Path::EdgeIt it(path); |
|
112 if (it == INVALID) return true; |
|
113 typename Graph::Node node = graph.target(it); |
|
114 ++it; |
|
115 while (it != INVALID) { |
|
116 if (graph.source(it) != node) return false; |
|
117 node = graph.target(it); |
|
118 ++it; |
|
119 } |
|
120 return true; |
|
121 } |
|
122 |
|
123 /// \brief Gives back the source of the path |
|
124 /// |
|
125 /// Gives back the source of the path. |
|
126 template <typename Graph, typename Path> |
|
127 typename Graph::Node pathSource(const Graph& graph, const Path& path) { |
|
128 return graph.source(path.front()); |
|
129 } |
|
130 |
|
131 /// \brief Gives back the target of the path |
|
132 /// |
|
133 /// Gives back the target of the path. |
|
134 template <typename Graph, typename Path> |
|
135 typename Graph::Node pathTarget(const Graph& graph, const Path& path) { |
|
136 return graph.target(path.back()); |
|
137 } |
|
138 } |
|
139 |
|
140 #endif |