src/lemon/graph_utils.h
author alpar
Tue, 11 Jan 2005 09:15:25 +0000
changeset 1073 bedab8bd915f
parent 986 e997802b855c
child 1079 81addddaf3d3
permissions -rw-r--r--
graph_to_eps mission accomplished.
- lemon/graph_to_eps.h header created
- lemon/bezier.h: Tools to compute with bezier curves (unclean and undocumented
interface, used internally by graph_to_eps.h)
- demo/graph_to_eps_demo.cc: a simple demo for lemon/graph_to_eps.h
     1 /* -*- C++ -*-
     2  * src/lemon/graph_utils.h - Part of LEMON, a generic C++ optimization library
     3  *
     4  * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     5  * (Egervary Combinatorial Optimization Research Group, EGRES).
     6  *
     7  * Permission to use, modify and distribute this software is granted
     8  * provided that this copyright notice appears in all copies. For
     9  * precise terms see the accompanying LICENSE file.
    10  *
    11  * This software is provided "AS IS" with no warranty of any kind,
    12  * express or implied, and with no claim as to its suitability for any
    13  * purpose.
    14  *
    15  */
    16 
    17 #ifndef LEMON_GRAPH_UTILS_H
    18 #define LEMON_GRAPH_UTILS_H
    19 
    20 #include <iterator>
    21 
    22 #include <lemon/invalid.h>
    23 #include <lemon/utility.h>
    24 
    25 ///\ingroup gutils
    26 ///\file
    27 ///\brief Graph utilities.
    28 ///
    29 ///\todo Please
    30 ///revise the documentation.
    31 ///
    32 
    33 
    34 namespace lemon {
    35 
    36 /// \addtogroup gutils
    37 /// @{
    38 
    39   /// \brief Function to count the items in the graph.
    40   ///
    41   /// This function counts the items in the graph.
    42   /// The complexity of the function is O(n) because
    43   /// it iterates on all of the items.
    44 
    45   template <typename Graph, typename ItemIt>
    46   inline int countItems(const Graph& g) {
    47     int num = 0;
    48     for (ItemIt it(g); it != INVALID; ++it) {
    49       ++num;
    50     }
    51     return num;
    52   }
    53 
    54   // Node counting:
    55 
    56   template <typename Graph>
    57   inline
    58   typename enable_if<typename Graph::NodeNumTag, int>::type
    59   _countNodes(const Graph &g) {
    60     return g.nodeNum();
    61   }
    62 
    63   template <typename Graph>
    64   inline int _countNodes(Wrap<Graph> w) {
    65     return countItems<Graph, typename Graph::NodeIt>(w.value);
    66   }
    67 
    68   /// \brief Function to count the nodes in the graph.
    69   ///
    70   /// This function counts the nodes in the graph.
    71   /// The complexity of the function is O(n) but for some
    72   /// graph structure it is specialized to run in O(1).
    73   ///
    74   /// \todo refer how to specialize it
    75 
    76   template <typename Graph>
    77   inline int countNodes(const Graph& g) {
    78     return _countNodes<Graph>(g);
    79   }
    80 
    81   // Edge counting:
    82 
    83   template <typename Graph>
    84   inline
    85   typename enable_if<typename Graph::EdgeNumTag, int>::type
    86   _countEdges(const Graph &g) {
    87     return g.edgeNum();
    88   }
    89 
    90   template <typename Graph>
    91   inline int _countEdges(Wrap<Graph> w) {
    92     return countItems<Graph, typename Graph::EdgeIt>(w.value);
    93   }
    94 
    95   /// \brief Function to count the edges in the graph.
    96   ///
    97   /// This function counts the edges in the graph.
    98   /// The complexity of the function is O(e) but for some
    99   /// graph structure it is specialized to run in O(1).
   100 
   101   template <typename Graph>
   102   inline int countEdges(const Graph& g) {
   103     return _countEdges<Graph>(g);
   104   }
   105 
   106   // Undirected edge counting:
   107 
   108   template <typename Graph>
   109   inline
   110   typename enable_if<typename Graph::EdgeNumTag, int>::type
   111   _countUndirEdges(const Graph &g) {
   112     return g.undirEdgeNum();
   113   }
   114 
   115   template <typename Graph>
   116   inline int _countUndirEdges(Wrap<Graph> w) {
   117     return countItems<Graph, typename Graph::UndirEdgeIt>(w.value);
   118   }
   119 
   120   /// \brief Function to count the edges in the graph.
   121   ///
   122   /// This function counts the edges in the graph.
   123   /// The complexity of the function is O(e) but for some
   124   /// graph structure it is specialized to run in O(1).
   125 
   126   template <typename Graph>
   127   inline int countUndirEdges(const Graph& g) {
   128     return _countUndirEdges<Graph>(g);
   129   }
   130 
   131 
   132 
   133   template <typename Graph, typename DegIt>
   134   inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) {
   135     int num = 0;
   136     for (DegIt it(_g, _n); it != INVALID; ++it) {
   137       ++num;
   138     }
   139     return num;
   140   }
   141 
   142   /// Finds an edge between two nodes of a graph.
   143 
   144   /// Finds an edge from node \c u to node \c v in graph \c g.
   145   ///
   146   /// If \c prev is \ref INVALID (this is the default value), then
   147   /// it finds the first edge from \c u to \c v. Otherwise it looks for
   148   /// the next edge from \c u to \c v after \c prev.
   149   /// \return The found edge or \ref INVALID if there is no such an edge.
   150   ///
   151   /// Thus you can iterate through each edge from \c u to \c v as it follows.
   152   /// \code
   153   /// for(Edge e=findEdge(g,u,v);e!=INVALID;e=findEdge(g,u,v,e)) {
   154   ///   ...
   155   /// }
   156   /// \endcode
   157   /// \todo We may want to use the \ref concept::GraphBase "GraphBase"
   158   /// interface here...
   159   /// \bug Untested ...
   160   template <typename Graph>
   161   typename Graph::Edge findEdge(const Graph &g,
   162 		typename Graph::Node u, typename Graph::Node v,
   163 		typename Graph::Edge prev = INVALID) 
   164   {
   165     typename Graph::OutEdgeIt e(g,prev);
   166     if(prev==INVALID) g.first(e,u);
   167     else ++e;
   168     while(e!=INVALID && g.source(e)!=v) ++e;
   169     return e;
   170   }
   171   
   172   ///\e
   173 
   174   ///\todo Please document.
   175   ///
   176   template <typename Graph>
   177   inline int countOutEdges(const Graph& _g,  const typename Graph::Node& _n) {
   178     return countNodeDegree<Graph, typename Graph::OutEdgeIt>(_g, _n);
   179   }
   180 
   181   ///\e
   182 
   183   ///\todo Please document.
   184   ///
   185   template <typename Graph>
   186   inline int countInEdges(const Graph& _g,  const typename Graph::Node& _n) {
   187     return countNodeDegree<Graph, typename Graph::InEdgeIt>(_g, _n);
   188   }
   189 
   190   // graph copy
   191 
   192   template <
   193     typename DestinationGraph, 
   194     typename SourceGraph, 
   195     typename NodeBijection>
   196   void copyNodes(DestinationGraph& _d, const SourceGraph& _s, 
   197 		 NodeBijection& _nb) {    
   198     for (typename SourceGraph::NodeIt it(_s); it != INVALID; ++it) {
   199       _nb[it] = _d.addNode();
   200     }
   201   }
   202 
   203   template <
   204     typename DestinationGraph, 
   205     typename SourceGraph, 
   206     typename NodeBijection,
   207     typename EdgeBijection>
   208   void copyEdges(DestinationGraph& _d, const SourceGraph& _s,
   209 		 const NodeBijection& _nb, EdgeBijection& _eb) {    
   210     for (typename SourceGraph::EdgeIt it(_s); it != INVALID; ++it) {
   211       _eb[it] = _d.addEdge(_nb[_s.source(it)], _nb[_s.target(it)]);
   212     }
   213   }
   214 
   215   template <
   216     typename DestinationGraph, 
   217     typename SourceGraph, 
   218     typename NodeBijection,
   219     typename EdgeBijection>
   220   void copyGraph(DestinationGraph& _d, const SourceGraph& _s, 
   221 		 NodeBijection& _nb, EdgeBijection& _eb) {
   222     nodeCopy(_d, _s, _nb);
   223     edgeCopy(_d, _s, _nb, _eb);
   224   }
   225  
   226    template <
   227     typename _DestinationGraph, 
   228     typename _SourceGraph, 
   229     typename _NodeBijection 
   230     =typename _SourceGraph::template NodeMap<typename _DestinationGraph::Node>,
   231     typename _EdgeBijection 
   232     =typename _SourceGraph::template EdgeMap<typename _DestinationGraph::Edge>
   233    >
   234    class GraphCopy {
   235    public:
   236 
   237      typedef _DestinationGraph DestinationGraph;
   238      typedef _SourceGraph SourceGraph;
   239 
   240      typedef _NodeBijection NodeBijection;
   241      typedef _EdgeBijection EdgeBijection;
   242 
   243    protected:          
   244 
   245      NodeBijection node_bijection;
   246      EdgeBijection edge_bijection;     
   247 
   248    public:
   249      
   250      GraphCopy(DestinationGraph& _d, const SourceGraph& _s) {
   251        copyGraph(_d, _s, node_bijection, edge_bijection);
   252      }
   253 
   254      const NodeBijection& getNodeBijection() const {
   255        return node_bijection;
   256      }
   257 
   258      const EdgeBijection& getEdgeBijection() const {
   259        return edge_bijection;
   260      }
   261      
   262    };
   263 
   264 /// @}
   265   
   266 } //END OF NAMESPACE LEMON
   267 
   268 #endif