COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/path_utils.h @ 2347:0aaa7ada5395

Last change on this file since 2347:0aaa7ada5395 was 2335:27aa03cd3121, checked in by Balazs Dezso, 17 years ago

New path concept and path structures

TODO: BellmanFord::negativeCycle()

File size: 4.0 KB
Line 
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
30namespace 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
Note: See TracBrowser for help on using the repository browser.