COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/graph_utils.h @ 963:5a7556e9e340

Last change on this file since 963:5a7556e9e340 was 947:93e9c45703ea, checked in by Alpar Juttner, 20 years ago

A new doxygen group added for graph utilities.

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