COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/path_utils.h @ 2391:14a343be7a5a

Last change on this file since 2391:14a343be7a5a was 2391:14a343be7a5a, checked in by Alpar Juttner, 12 years ago

Happy New Year to all source files!

File size: 3.9 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2007
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///\ingroup paths
20///\file
21///\brief Classes for representing paths in graphs.
22///
23
24#ifndef LEMON_PATH_UTILS_H
25#define LEMON_PATH_UTILS_H
26
27#include <lemon/concepts/path.h>
28
29namespace lemon {
30
31  namespace _path_bits {
32
33    template <typename Path, typename Enable = void>
34    struct RevTagIndicator {
35      static const bool value = false;
36    };
37
38    template <typename Graph>
39    struct RevTagIndicator<
40      Graph,
41      typename enable_if<typename Graph::RevTag, void>::type
42    > {
43      static const bool value = true;
44    };
45
46    template <typename Target, typename Source,
47              typename BuildEnable = void, typename RevEnable = void>
48    struct PathCopySelector {
49      static void copy(Target& target, const Source& source) {
50        target.clear();
51        for (typename Source::EdgeIt it(source); it != INVALID; ++it) {
52          target.addBack(it);
53        }
54      }
55    };
56
57    template <typename Target, typename Source, typename BuildEnable>
58    struct PathCopySelector<
59      Target, Source, BuildEnable,
60      typename enable_if<typename Source::RevPathTag, void>::type> {
61      static void copy(Target& target, const Source& source) {
62        target.clear();
63        for (typename Source::RevEdgeIt it(source); it != INVALID; ++it) {
64          target.addFront(it);
65        }
66      }
67    };
68
69    template <typename Target, typename Source, typename RevEnable>
70    struct PathCopySelector<
71      Target, Source,
72      typename enable_if<typename Target::BuildTag, void>::type, RevEnable> {
73      static void copy(Target& target, const Source& source) {
74        target.clear();
75        target.build(source);
76      }
77    };
78
79    template <typename Target, typename Source>
80    struct PathCopySelector<
81      Target, Source,
82      typename enable_if<typename Target::BuildTag, void>::type,
83      typename enable_if<typename Source::RevPathTag, void>::type> {
84      static void copy(Target& target, const Source& source) {
85        target.clear();
86        target.buildRev(source);
87      }
88    };
89
90  }
91
92
93  /// \brief Make of copy of a path.
94  ///
95  ///  Make of copy of a path.
96  template <typename Target, typename Source>
97  void copyPath(Target& target, const Source& source) {
98    checkConcept<concepts::PathDumper<typename Source::Graph>, Source>();
99    _path_bits::PathCopySelector<Target, Source>::copy(target, source);
100  }
101
102  /// \brief Checks the path's consistency.
103  ///
104  /// Checks that each edge's target is the next's source.
105  ///
106  template <typename Graph, typename Path>
107  bool checkPath(const Graph& graph, const Path& path) {
108    typename Path::EdgeIt it(path);
109    if (it == INVALID) return true;
110    typename Graph::Node node = graph.target(it);
111    ++it;
112    while (it != INVALID) {
113      if (graph.source(it) != node) return false;
114      node = graph.target(it);
115      ++it;
116    }
117    return true;
118  }
119
120  /// \brief Gives back the source of the path
121  ///
122  /// Gives back the source of the path.
123  template <typename Graph, typename Path>
124  typename Graph::Node pathSource(const Graph& graph, const Path& path) {
125    return graph.source(path.front());
126  }
127
128  /// \brief Gives back the target of the path
129  ///
130  /// Gives back the target of the path.
131  template <typename Graph, typename Path>
132  typename Graph::Node pathTarget(const Graph& graph, const Path& path) {
133    return graph.target(path.back());
134  }
135}
136
137#endif
Note: See TracBrowser for help on using the repository browser.