source: lemon-0.x/lemon/path_utils.h @ 2350:eb371753e814

/* -*- C++ -*-
 *
 * This file is a part of LEMON, a generic C++ optimization library
 *
 * Copyright (C) 2003-2006
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
 *
 * Permission to use, modify and distribute this software is granted
 * provided that this copyright notice appears in all copies. For
 * precise terms see the accompanying LICENSE file.
 *
 * This software is provided "AS IS" with no warranty of any kind,
 * express or implied, and with no claim as to its suitability for any
 * purpose.
 *
 */


///\ingroup paths
///\file
///\brief Classes for representing paths in graphs.
///

#ifndef LEMON_PATH_UTILS_H
#define LEMON_PATH_UTILS_H

#include <lemon/concepts/path.h>

namespace lemon {

  namespace _path_bits {

    template <typename Path, typename Enable = void>
    struct RevTagIndicator {
      static const bool value = false;
    };

    template <typename Graph>
    struct RevTagIndicator<
      Graph, 
      typename enable_if<typename Graph::RevTag, void>::type
    > {
      static const bool value = true;
    };

    template <typename Target, typename Source,
              typename BuildEnable = void, typename RevEnable = void>
    struct PathCopySelector {
      static void copy(Target& target, const Source& source) {
        source.clear();
        for (typename Source::EdgeIt it(source); it != INVALID; ++it) {
          target.addBack(it);
        }
      }
    };

    template <typename Target, typename Source, typename BuildEnable>
    struct PathCopySelector<
      Target, Source, BuildEnable, 
      typename enable_if<typename Source::RevPathTag, void>::type> {
      static void copy(Target& target, const Source& source) {
        source.clear();
        for (typename Source::RevIt it(source); it != INVALID; ++it) {
          target.addFront(it);
        }
      }
    };

    template <typename Target, typename Source, typename RevEnable>
    struct PathCopySelector<
      Target, Source, 
      typename enable_if<typename Target::BuildTag, void>::type, RevEnable> {
      static void copy(Target& target, const Source& source) {
        target.clear();
        target.build(source);
      }
    };

    template <typename Target, typename Source>
    struct PathCopySelector<
      Target, Source, 
      typename enable_if<typename Target::BuildTag, void>::type,
      typename enable_if<typename Source::RevPathTag, void>::type> {
      static void copy(Target& target, const Source& source) {
        target.clear();
        target.buildRev(source);
      }
    };

  }


  /// \brief Make of copy of a path.
  ///
  ///  Make of copy of a path.
  template <typename Target, typename Source>
  void copyPath(Target& target, const Source& source) {
    checkConcept<concepts::PathDumper<typename Source::Graph>, Source>();
    _path_bits::PathCopySelector<Target, Source>::copy(target, source);
  }

  /// \brief Checks the path's consistency.
  ///
  /// Checks that each edge's target is the next's source. 
  /// 
  template <typename Graph, typename Path>
  bool checkPath(const Graph& graph, const Path& path) {
    typename Path::EdgeIt it(path);
    if (it == INVALID) return true;
    typename Graph::Node node = graph.target(it);
    ++it;
    while (it != INVALID) {
      if (graph.source(it) != node) return false;
      node = graph.target(it);
      ++it;
    }
    return true;
  }

  /// \brief Gives back the source of the path
  ///
  /// Gives back the source of the path.
  template <typename Graph, typename Path>
  typename Graph::Node pathSource(const Graph& graph, const Path& path) {
    return graph.source(path.front());
  }

  /// \brief Gives back the target of the path
  ///
  /// Gives back the target of the path.
  template <typename Graph, typename Path>
  typename Graph::Node pathTarget(const Graph& graph, const Path& path) {
    return graph.target(path.back());
  }
}

#endif