source: lemon-0.x/src/lemon/graph_utils.h @ 1079:81addddaf3d3

/* -*- C++ -*-
 * src/lemon/graph_utils.h - Part of LEMON, a generic C++ optimization library
 *
 * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 * (Egervary Combinatorial Optimization Research Group, 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.
 *
 */

#ifndef LEMON_GRAPH_UTILS_H
#define LEMON_GRAPH_UTILS_H

#include <iterator>

#include <lemon/invalid.h>
#include <lemon/utility.h>

///\ingroup gutils
///\file
///\brief Graph utilities.
///
///\todo Please
///revise the documentation.
///


namespace lemon {

/// \addtogroup gutils
/// @{

  /// \brief Function to count the items in the graph.
  ///
  /// This function counts the items in the graph.
  /// The complexity of the function is O(n) because
  /// it iterates on all of the items.

  template <typename Graph, typename ItemIt>
  inline int countItems(const Graph& g) {
    int num = 0;
    for (ItemIt it(g); it != INVALID; ++it) {
      ++num;
    }
    return num;
  }

  // Node counting:

  template <typename Graph>
  inline
  typename enable_if<typename Graph::NodeNumTag, int>::type
  _countNodes(const Graph &g) {
    return g.nodeNum();
  }

  template <typename Graph>
  inline int _countNodes(Wrap<Graph> w) {
    return countItems<Graph, typename Graph::NodeIt>(w.value);
  }

  /// \brief Function to count the nodes in the graph.
  ///
  /// This function counts the nodes in the graph.
  /// The complexity of the function is O(n) but for some
  /// graph structure it is specialized to run in O(1).
  ///
  /// \todo refer how to specialize it

  template <typename Graph>
  inline int countNodes(const Graph& g) {
    return _countNodes<Graph>(g);
  }

  // Edge counting:

  template <typename Graph>
  inline
  typename enable_if<typename Graph::EdgeNumTag, int>::type
  _countEdges(const Graph &g) {
    return g.edgeNum();
  }

  template <typename Graph>
  inline int _countEdges(Wrap<Graph> w) {
    return countItems<Graph, typename Graph::EdgeIt>(w.value);
  }

  /// \brief Function to count the edges in the graph.
  ///
  /// This function counts the edges in the graph.
  /// The complexity of the function is O(e) but for some
  /// graph structure it is specialized to run in O(1).

  template <typename Graph>
  inline int countEdges(const Graph& g) {
    return _countEdges<Graph>(g);
  }

  // Undirected edge counting:

  template <typename Graph>
  inline
  typename enable_if<typename Graph::EdgeNumTag, int>::type
  _countUndirEdges(const Graph &g) {
    return g.undirEdgeNum();
  }

  template <typename Graph>
  inline int _countUndirEdges(Wrap<Graph> w) {
    return countItems<Graph, typename Graph::UndirEdgeIt>(w.value);
  }

  /// \brief Function to count the edges in the graph.
  ///
  /// This function counts the edges in the graph.
  /// The complexity of the function is O(e) but for some
  /// graph structure it is specialized to run in O(1).

  template <typename Graph>
  inline int countUndirEdges(const Graph& g) {
    return _countUndirEdges<Graph>(g);
  }



  template <typename Graph, typename DegIt>
  inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) {
    int num = 0;
    for (DegIt it(_g, _n); it != INVALID; ++it) {
      ++num;
    }
    return num;
  }

  /// Finds an edge between two nodes of a graph.

  /// Finds an edge from node \c u to node \c v in graph \c g.
  ///
  /// If \c prev is \ref INVALID (this is the default value), then
  /// it finds the first edge from \c u to \c v. Otherwise it looks for
  /// the next edge from \c u to \c v after \c prev.
  /// \return The found edge or \ref INVALID if there is no such an edge.
  ///
  /// Thus you can iterate through each edge from \c u to \c v as it follows.
  /// \code
  /// for(Edge e=findEdge(g,u,v);e!=INVALID;e=findEdge(g,u,v,e)) {
  ///   ...
  /// }
  /// \endcode
  /// \todo We may want to use the \ref concept::GraphBase "GraphBase"
  /// interface here...
  /// \bug Untested ...
  template <typename Graph>
  typename Graph::Edge findEdge(const Graph &g,
                typename Graph::Node u, typename Graph::Node v,
                typename Graph::Edge prev = INVALID) 
  {
    typename Graph::OutEdgeIt e(g,prev);
    //    if(prev==INVALID) g.first(e,u);
    if(prev==INVALID) e=typename Graph::OutEdgeIt(g,u);
    else ++e;
    while(e!=INVALID && g.target(e)!=v) ++e;
    return e;
  }
  
  ///\e

  ///\todo Please document.
  ///
  template <typename Graph>
  inline int countOutEdges(const Graph& _g,  const typename Graph::Node& _n) {
    return countNodeDegree<Graph, typename Graph::OutEdgeIt>(_g, _n);
  }

  ///\e

  ///\todo Please document.
  ///
  template <typename Graph>
  inline int countInEdges(const Graph& _g,  const typename Graph::Node& _n) {
    return countNodeDegree<Graph, typename Graph::InEdgeIt>(_g, _n);
  }

  // graph copy

  template <
    typename DestinationGraph, 
    typename SourceGraph, 
    typename NodeBijection>
  void copyNodes(DestinationGraph& _d, const SourceGraph& _s, 
                 NodeBijection& _nb) {    
    for (typename SourceGraph::NodeIt it(_s); it != INVALID; ++it) {
      _nb[it] = _d.addNode();
    }
  }

  template <
    typename DestinationGraph, 
    typename SourceGraph, 
    typename NodeBijection,
    typename EdgeBijection>
  void copyEdges(DestinationGraph& _d, const SourceGraph& _s,
                 const NodeBijection& _nb, EdgeBijection& _eb) {    
    for (typename SourceGraph::EdgeIt it(_s); it != INVALID; ++it) {
      _eb[it] = _d.addEdge(_nb[_s.source(it)], _nb[_s.target(it)]);
    }
  }

  template <
    typename DestinationGraph, 
    typename SourceGraph, 
    typename NodeBijection,
    typename EdgeBijection>
  void copyGraph(DestinationGraph& _d, const SourceGraph& _s, 
                 NodeBijection& _nb, EdgeBijection& _eb) {
    nodeCopy(_d, _s, _nb);
    edgeCopy(_d, _s, _nb, _eb);
  }
 
   template <
    typename _DestinationGraph, 
    typename _SourceGraph, 
    typename _NodeBijection 
    =typename _SourceGraph::template NodeMap<typename _DestinationGraph::Node>,
    typename _EdgeBijection 
    =typename _SourceGraph::template EdgeMap<typename _DestinationGraph::Edge>
   >
   class GraphCopy {
   public:

     typedef _DestinationGraph DestinationGraph;
     typedef _SourceGraph SourceGraph;

     typedef _NodeBijection NodeBijection;
     typedef _EdgeBijection EdgeBijection;

   protected:          

     NodeBijection node_bijection;
     EdgeBijection edge_bijection;     

   public:
     
     GraphCopy(DestinationGraph& _d, const SourceGraph& _s) {
       copyGraph(_d, _s, node_bijection, edge_bijection);
     }

     const NodeBijection& getNodeBijection() const {
       return node_bijection;
     }

     const EdgeBijection& getEdgeBijection() const {
       return edge_bijection;
     }
     
   };

/// @}
  
} //END OF NAMESPACE LEMON

#endif