COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/graph_utils.h @ 946:c94ef40a22ce

Last change on this file since 946:c94ef40a22ce was 946:c94ef40a22ce, checked in by Mihaly Barasz, 16 years ago

The graph_factory branch (@ 1321) has been merged to trunk.

File size: 4.7 KB
Line 
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
24///\ingroup utils
25///\file
26///\brief Graph utils.
27///
28
29
30namespace lemon {
31
32  // counters in the graph
33  /// \brief Function to count the items in the graph.
34  ///
35  /// This function counts the items in the graph.
36  /// The complexity of the function is O(n) because
37  /// it iterates on all of the items.
38
39  template <typename Graph, typename ItemIt>
40  inline int countItems(const Graph& _g) {
41    int num = 0;
42    for (ItemIt it(_g); it != INVALID; ++it) {
43      ++num;
44    }
45    return num;
46  }
47
48  /// \brief Function to count the nodes in the graph.
49  ///
50  /// This function counts the nodes in the graph.
51  /// The complexity of the function is O(n) but for some
52  /// graph structure it is specialized to O(1).
53
54  template <typename Graph>
55  inline int countNodes(const Graph& _g) {
56    return countItems<Graph, typename Graph::NodeIt>(_g);
57  }
58
59  /// \brief Function to count the edges in the graph.
60  ///
61  /// This function counts the edges in the graph.
62  /// The complexity of the function is O(e) but for some
63  /// graph structure it is specialized to O(1).
64  template <typename Graph>
65  inline int countEdges(const Graph& _g) {
66    return countItems<Graph, typename Graph::EdgeIt>(_g);
67  }
68
69  /// \brief Function to count the symmetric edges in the graph.
70  ///
71  /// This function counts the symmetric edges in the graph.
72  /// The complexity of the function is O(e) but for some
73  /// graph structure it is specialized to O(1).
74  template <typename Graph>
75  inline int countSymEdges(const Graph& _g) {
76    return countItems<Graph, typename Graph::SymEdgeIt>(_g);
77  }
78
79  template <typename Graph, typename DegIt>
80  inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) {
81    int num = 0;
82    for (DegIt it(_g, _n); it != INVALID; ++it) {
83      ++num;
84    }
85    return num;
86  }
87
88  template <typename Graph>
89  inline int countOutEdges(const Graph& _g,  const typename Graph::Node& _n) {
90    return countNodeDegree<Graph, typename Graph::OutEdgeIt>(_g, _n);
91  }
92
93  template <typename Graph>
94  inline int countInEdges(const Graph& _g,  const typename Graph::Node& _n) {
95    return countNodeDegree<Graph, typename Graph::InEdgeIt>(_g, _n);
96  }
97
98  // graph copy
99
100  template <
101    typename DestinationGraph,
102    typename SourceGraph,
103    typename NodeBijection>
104  void copyNodes(DestinationGraph& _d, const SourceGraph& _s,
105                 NodeBijection& _nb) {   
106    for (typename SourceGraph::NodeIt it(_s); it != INVALID; ++it) {
107      _nb[it] = _d.addNode();
108    }
109  }
110
111  template <
112    typename DestinationGraph,
113    typename SourceGraph,
114    typename NodeBijection,
115    typename EdgeBijection>
116  void copyEdges(DestinationGraph& _d, const SourceGraph& _s,
117                 const NodeBijection& _nb, EdgeBijection& _eb) {   
118    for (typename SourceGraph::EdgeIt it(_s); it != INVALID; ++it) {
119      _eb[it] = _d.addEdge(_nb[_s.tail(it)], _nb[_s.head(it)]);
120    }
121  }
122
123  template <
124    typename DestinationGraph,
125    typename SourceGraph,
126    typename NodeBijection,
127    typename EdgeBijection>
128  void copyGraph(DestinationGraph& _d, const SourceGraph& _s,
129                 NodeBijection& _nb, EdgeBijection& _eb) {
130    nodeCopy(_d, _s, _nb);
131    edgeCopy(_d, _s, _nb, _eb);
132  }
133 
134   template <
135    typename _DestinationGraph,
136    typename _SourceGraph,
137    typename _NodeBijection
138    =typename _SourceGraph::template NodeMap<typename _DestinationGraph::Node>,
139    typename _EdgeBijection
140    =typename _SourceGraph::template EdgeMap<typename _DestinationGraph::Edge>
141   >
142   class GraphCopy {
143   public:
144
145     typedef _DestinationGraph DestinationGraph;
146     typedef _SourceGraph SourceGraph;
147
148     typedef _NodeBijection NodeBijection;
149     typedef _EdgeBijection EdgeBijection;
150
151   protected:         
152
153     NodeBijection node_bijection;
154     EdgeBijection edge_bijection;     
155
156   public:
157     
158     GraphCopy(DestinationGraph& _d, const SourceGraph& _s) {
159       copyGraph(_d, _s, node_bijection, edge_bijection);
160     }
161
162     const NodeBijection& getNodeBijection() const {
163       return node_bijection;
164     }
165
166     const EdgeBijection& getEdgeBijection() const {
167       return edge_bijection;
168     }
169     
170   };
171                                                               
172}
173
174#endif
Note: See TracBrowser for help on using the repository browser.