1.1 --- a/lemon/graph_utils.h Thu Jan 26 06:44:22 2006 +0000
1.2 +++ b/lemon/graph_utils.h Thu Jan 26 15:42:13 2006 +0000
1.3 @@ -71,8 +71,8 @@
1.4
1.5 ///This \c \#define creates the same convenience typedefs as defined by
1.6 ///\ref GRAPH_TYPEDEFS(Graph) and three more, namely it creates
1.7 - ///\c UndirEdge, \c UndirEdgeIt, \c IncEdgeIt,
1.8 - ///\c BoolUndirEdgeMap, \c IntUndirEdgeMap, \c DoubleUndirEdgeMap.
1.9 + ///\c UEdge, \c UEdgeIt, \c IncEdgeIt,
1.10 + ///\c BoolUEdgeMap, \c IntUEdgeMap, \c DoubleUEdgeMap.
1.11 ///
1.12 ///\note If \c G it a template parameter, it should be used in this way.
1.13 ///\code
1.14 @@ -83,12 +83,12 @@
1.15 ///template typedefs in C++.
1.16 #define UNDIRGRAPH_TYPEDEFS(Graph) \
1.17 GRAPH_TYPEDEFS(Graph) \
1.18 - typedef Graph:: UndirEdge UndirEdge; \
1.19 - typedef Graph:: UndirEdgeIt UndirEdgeIt; \
1.20 + typedef Graph:: UEdge UEdge; \
1.21 + typedef Graph:: UEdgeIt UEdgeIt; \
1.22 typedef Graph:: IncEdgeIt IncEdgeIt;
1.23 -// typedef Graph::template UndirEdgeMap<bool> BoolUndirEdgeMap;
1.24 -// typedef Graph::template UndirEdgeMap<int> IntUndirEdgeMap;
1.25 -// typedef Graph::template UndirEdgeMap<double> DoubleUndirEdgeMap;
1.26 +// typedef Graph::template UEdgeMap<bool> BoolUEdgeMap;
1.27 +// typedef Graph::template UEdgeMap<int> IntUEdgeMap;
1.28 +// typedef Graph::template UEdgeMap<double> DoubleUEdgeMap;
1.29
1.30
1.31
1.32 @@ -162,13 +162,13 @@
1.33 template <typename Graph>
1.34 inline
1.35 typename enable_if<typename Graph::EdgeNumTag, int>::type
1.36 - _countUndirEdges(const Graph &g) {
1.37 - return g.undirEdgeNum();
1.38 + _countUEdges(const Graph &g) {
1.39 + return g.uEdgeNum();
1.40 }
1.41
1.42 template <typename Graph>
1.43 - inline int _countUndirEdges(Wrap<Graph> w) {
1.44 - return countItems<Graph, typename Graph::UndirEdgeIt>(w.value);
1.45 + inline int _countUEdges(Wrap<Graph> w) {
1.46 + return countItems<Graph, typename Graph::UEdgeIt>(w.value);
1.47 }
1.48
1.49 /// \brief Function to count the undirected edges in the graph.
1.50 @@ -178,8 +178,8 @@
1.51 /// graph structures it is specialized to run in O(1).
1.52
1.53 template <typename Graph>
1.54 - inline int countUndirEdges(const Graph& g) {
1.55 - return _countUndirEdges<Graph>(g);
1.56 + inline int countUEdges(const Graph& g) {
1.57 + return _countUEdges<Graph>(g);
1.58 }
1.59
1.60
1.61 @@ -325,19 +325,19 @@
1.62 inline
1.63 typename enable_if<
1.64 typename Graph::FindEdgeTag,
1.65 - typename Graph::UndirEdge>::type
1.66 - _findUndirEdge(const Graph &g,
1.67 + typename Graph::UEdge>::type
1.68 + _findUEdge(const Graph &g,
1.69 typename Graph::Node u, typename Graph::Node v,
1.70 - typename Graph::UndirEdge prev = INVALID) {
1.71 - return g.findUndirEdge(u, v, prev);
1.72 + typename Graph::UEdge prev = INVALID) {
1.73 + return g.findUEdge(u, v, prev);
1.74 }
1.75
1.76 template <typename Graph>
1.77 - inline typename Graph::UndirEdge
1.78 - _findUndirEdge(Wrap<Graph> w,
1.79 + inline typename Graph::UEdge
1.80 + _findUEdge(Wrap<Graph> w,
1.81 typename Graph::Node u,
1.82 typename Graph::Node v,
1.83 - typename Graph::UndirEdge prev = INVALID) {
1.84 + typename Graph::UEdge prev = INVALID) {
1.85 const Graph& g = w.value;
1.86 if (prev == INVALID) {
1.87 typename Graph::OutEdgeIt e(g, u);
1.88 @@ -350,9 +350,9 @@
1.89 }
1.90 }
1.91
1.92 - /// \brief Finds an undir edge between two nodes of a graph.
1.93 + /// \brief Finds an uedge between two nodes of a graph.
1.94 ///
1.95 - /// Finds an undir edge from node \c u to node \c v in graph \c g.
1.96 + /// Finds an uedge from node \c u to node \c v in graph \c g.
1.97 ///
1.98 /// If \c prev is \ref INVALID (this is the default value), then
1.99 /// it finds the first edge from \c u to \c v. Otherwise it looks for
1.100 @@ -361,63 +361,63 @@
1.101 ///
1.102 /// Thus you can iterate through each edge from \c u to \c v as it follows.
1.103 /// \code
1.104 - /// for(UndirEdge e = findUndirEdge(g,u,v); e != INVALID;
1.105 - /// e = findUndirEdge(g,u,v,e)) {
1.106 + /// for(UEdge e = findUEdge(g,u,v); e != INVALID;
1.107 + /// e = findUEdge(g,u,v,e)) {
1.108 /// ...
1.109 /// }
1.110 /// \endcode
1.111 // /// \todo We may want to use the "GraphBase"
1.112 // /// interface here...
1.113 template <typename Graph>
1.114 - inline typename Graph::UndirEdge
1.115 - findUndirEdge(const Graph &g,
1.116 + inline typename Graph::UEdge
1.117 + findUEdge(const Graph &g,
1.118 typename Graph::Node u,
1.119 typename Graph::Node v,
1.120 - typename Graph::UndirEdge prev = INVALID) {
1.121 - return _findUndirEdge<Graph>(g, u, v, prev);
1.122 + typename Graph::UEdge prev = INVALID) {
1.123 + return _findUEdge<Graph>(g, u, v, prev);
1.124 }
1.125
1.126 - /// \brief Iterator for iterating on undir edges connected the same nodes.
1.127 + /// \brief Iterator for iterating on uedges connected the same nodes.
1.128 ///
1.129 - /// Iterator for iterating on undir edges connected the same nodes. It is
1.130 - /// higher level interface for the findUndirEdge() function. You can
1.131 + /// Iterator for iterating on uedges connected the same nodes. It is
1.132 + /// higher level interface for the findUEdge() function. You can
1.133 /// use it the following way:
1.134 /// \code
1.135 - /// for (ConUndirEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) {
1.136 + /// for (ConUEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) {
1.137 /// ...
1.138 /// }
1.139 /// \endcode
1.140 ///
1.141 /// \author Balazs Dezso
1.142 template <typename _Graph>
1.143 - class ConUndirEdgeIt : public _Graph::UndirEdge {
1.144 + class ConUEdgeIt : public _Graph::UEdge {
1.145 public:
1.146
1.147 typedef _Graph Graph;
1.148 - typedef typename Graph::UndirEdge Parent;
1.149 + typedef typename Graph::UEdge Parent;
1.150
1.151 - typedef typename Graph::UndirEdge UndirEdge;
1.152 + typedef typename Graph::UEdge UEdge;
1.153 typedef typename Graph::Node Node;
1.154
1.155 /// \brief Constructor.
1.156 ///
1.157 - /// Construct a new ConUndirEdgeIt iterating on the edges which
1.158 + /// Construct a new ConUEdgeIt iterating on the edges which
1.159 /// connects the \c u and \c v node.
1.160 - ConUndirEdgeIt(const Graph& g, Node u, Node v) : graph(g) {
1.161 - Parent::operator=(findUndirEdge(graph, u, v));
1.162 + ConUEdgeIt(const Graph& g, Node u, Node v) : graph(g) {
1.163 + Parent::operator=(findUEdge(graph, u, v));
1.164 }
1.165
1.166 /// \brief Constructor.
1.167 ///
1.168 - /// Construct a new ConUndirEdgeIt which continues the iterating from
1.169 + /// Construct a new ConUEdgeIt which continues the iterating from
1.170 /// the \c e edge.
1.171 - ConUndirEdgeIt(const Graph& g, UndirEdge e) : Parent(e), graph(g) {}
1.172 + ConUEdgeIt(const Graph& g, UEdge e) : Parent(e), graph(g) {}
1.173
1.174 /// \brief Increment operator.
1.175 ///
1.176 /// It increments the iterator and gives back the next edge.
1.177 - ConUndirEdgeIt& operator++() {
1.178 - Parent::operator=(findUndirEdge(graph, graph.source(*this),
1.179 + ConUEdgeIt& operator++() {
1.180 + Parent::operator=(findUEdge(graph, graph.source(*this),
1.181 graph.target(*this), *this));
1.182 return *this;
1.183 }
1.184 @@ -596,53 +596,53 @@
1.185 /// \brief Class to copy an undirected graph.
1.186 ///
1.187 /// Class to copy an undirected graph to an other graph (duplicate a graph).
1.188 - /// The simplest way of using it is through the \c copyUndirGraph() function.
1.189 + /// The simplest way of using it is through the \c copyUGraph() function.
1.190 template <typename Target, typename Source>
1.191 - class UndirGraphCopy {
1.192 + class UGraphCopy {
1.193 public:
1.194 typedef typename Source::Node Node;
1.195 typedef typename Source::NodeIt NodeIt;
1.196 typedef typename Source::Edge Edge;
1.197 typedef typename Source::EdgeIt EdgeIt;
1.198 - typedef typename Source::UndirEdge UndirEdge;
1.199 - typedef typename Source::UndirEdgeIt UndirEdgeIt;
1.200 + typedef typename Source::UEdge UEdge;
1.201 + typedef typename Source::UEdgeIt UEdgeIt;
1.202
1.203 typedef typename Source::
1.204 template NodeMap<typename Target::Node> NodeRefMap;
1.205
1.206 typedef typename Source::
1.207 - template UndirEdgeMap<typename Target::UndirEdge> UndirEdgeRefMap;
1.208 + template UEdgeMap<typename Target::UEdge> UEdgeRefMap;
1.209
1.210 private:
1.211
1.212 struct EdgeRefMap {
1.213 - EdgeRefMap(UndirGraphCopy& _gc) : gc(_gc) {}
1.214 + EdgeRefMap(UGraphCopy& _gc) : gc(_gc) {}
1.215 typedef typename Source::Edge Key;
1.216 typedef typename Target::Edge Value;
1.217
1.218 Value operator[](const Key& key) {
1.219 - return gc.target.direct(gc.undirEdgeRef[key],
1.220 + return gc.target.direct(gc.uEdgeRef[key],
1.221 gc.target.direction(key));
1.222 }
1.223
1.224 - UndirGraphCopy& gc;
1.225 + UGraphCopy& gc;
1.226 };
1.227
1.228 public:
1.229
1.230 - /// \brief Constructor for the UndirGraphCopy.
1.231 + /// \brief Constructor for the UGraphCopy.
1.232 ///
1.233 /// It copies the content of the \c _source graph into the
1.234 /// \c _target graph. It creates also two references, one beetween
1.235 /// the two nodeset and one beetween the two edgesets.
1.236 - UndirGraphCopy(Target& _target, const Source& _source)
1.237 + UGraphCopy(Target& _target, const Source& _source)
1.238 : source(_source), target(_target),
1.239 - nodeRefMap(_source), edgeRefMap(*this), undirEdgeRefMap(_source) {
1.240 + nodeRefMap(_source), edgeRefMap(*this), uEdgeRefMap(_source) {
1.241 for (NodeIt it(source); it != INVALID; ++it) {
1.242 nodeRefMap[it] = target.addNode();
1.243 }
1.244 - for (UndirEdgeIt it(source); it != INVALID; ++it) {
1.245 - undirEdgeRefMap[it] = target.addEdge(nodeRefMap[source.source(it)],
1.246 + for (UEdgeIt it(source); it != INVALID; ++it) {
1.247 + uEdgeRefMap[it] = target.addEdge(nodeRefMap[source.source(it)],
1.248 nodeRefMap[source.target(it)]);
1.249 }
1.250 }
1.251 @@ -651,7 +651,7 @@
1.252 ///
1.253 /// Copies the node references into the given map.
1.254 template <typename NodeRef>
1.255 - const UndirGraphCopy& nodeRef(NodeRef& map) const {
1.256 + const UGraphCopy& nodeRef(NodeRef& map) const {
1.257 for (NodeIt it(source); it != INVALID; ++it) {
1.258 map.set(it, nodeRefMap[it]);
1.259 }
1.260 @@ -662,7 +662,7 @@
1.261 ///
1.262 /// Reverse and copies the node references into the given map.
1.263 template <typename NodeRef>
1.264 - const UndirGraphCopy& nodeCrossRef(NodeRef& map) const {
1.265 + const UGraphCopy& nodeCrossRef(NodeRef& map) const {
1.266 for (NodeIt it(source); it != INVALID; ++it) {
1.267 map.set(nodeRefMap[it], it);
1.268 }
1.269 @@ -673,7 +673,7 @@
1.270 ///
1.271 /// Copies the edge references into the given map.
1.272 template <typename EdgeRef>
1.273 - const UndirGraphCopy& edgeRef(EdgeRef& map) const {
1.274 + const UGraphCopy& edgeRef(EdgeRef& map) const {
1.275 for (EdgeIt it(source); it != INVALID; ++it) {
1.276 map.set(edgeRefMap[it], it);
1.277 }
1.278 @@ -685,7 +685,7 @@
1.279 ///
1.280 /// Reverse and copies the undirected edge references into the given map.
1.281 template <typename EdgeRef>
1.282 - const UndirGraphCopy& edgeCrossRef(EdgeRef& map) const {
1.283 + const UGraphCopy& edgeCrossRef(EdgeRef& map) const {
1.284 for (EdgeIt it(source); it != INVALID; ++it) {
1.285 map.set(it, edgeRefMap[it]);
1.286 }
1.287 @@ -696,9 +696,9 @@
1.288 ///
1.289 /// Copies the undirected edge references into the given map.
1.290 template <typename EdgeRef>
1.291 - const UndirGraphCopy& undirEdgeRef(EdgeRef& map) const {
1.292 - for (UndirEdgeIt it(source); it != INVALID; ++it) {
1.293 - map.set(it, undirEdgeRefMap[it]);
1.294 + const UGraphCopy& uEdgeRef(EdgeRef& map) const {
1.295 + for (UEdgeIt it(source); it != INVALID; ++it) {
1.296 + map.set(it, uEdgeRefMap[it]);
1.297 }
1.298 return *this;
1.299 }
1.300 @@ -708,9 +708,9 @@
1.301 ///
1.302 /// Reverse and copies the undirected edge references into the given map.
1.303 template <typename EdgeRef>
1.304 - const UndirGraphCopy& undirEdgeCrossRef(EdgeRef& map) const {
1.305 - for (UndirEdgeIt it(source); it != INVALID; ++it) {
1.306 - map.set(undirEdgeRefMap[it], it);
1.307 + const UGraphCopy& uEdgeCrossRef(EdgeRef& map) const {
1.308 + for (UEdgeIt it(source); it != INVALID; ++it) {
1.309 + map.set(uEdgeRefMap[it], it);
1.310 }
1.311 return *this;
1.312 }
1.313 @@ -722,7 +722,7 @@
1.314 /// and the copied map's key type is the source graph's node
1.315 /// type.
1.316 template <typename TargetMap, typename SourceMap>
1.317 - const UndirGraphCopy& nodeMap(TargetMap& tMap,
1.318 + const UGraphCopy& nodeMap(TargetMap& tMap,
1.319 const SourceMap& sMap) const {
1.320 copyMap(tMap, sMap, NodeIt(source), nodeRefMap);
1.321 return *this;
1.322 @@ -735,7 +735,7 @@
1.323 /// and the copied map's key type is the source graph's edge
1.324 /// type.
1.325 template <typename TargetMap, typename SourceMap>
1.326 - const UndirGraphCopy& edgeMap(TargetMap& tMap,
1.327 + const UGraphCopy& edgeMap(TargetMap& tMap,
1.328 const SourceMap& sMap) const {
1.329 copyMap(tMap, sMap, EdgeIt(source), edgeRefMap);
1.330 return *this;
1.331 @@ -748,9 +748,9 @@
1.332 /// and the copied map's key type is the source graph's edge
1.333 /// type.
1.334 template <typename TargetMap, typename SourceMap>
1.335 - const UndirGraphCopy& undirEdgeMap(TargetMap& tMap,
1.336 + const UGraphCopy& uEdgeMap(TargetMap& tMap,
1.337 const SourceMap& sMap) const {
1.338 - copyMap(tMap, sMap, UndirEdgeIt(source), undirEdgeRefMap);
1.339 + copyMap(tMap, sMap, UEdgeIt(source), uEdgeRefMap);
1.340 return *this;
1.341 }
1.342
1.343 @@ -768,11 +768,11 @@
1.344 return edgeRefMap;
1.345 }
1.346
1.347 - /// \brief Gives back the stored undir edge references.
1.348 + /// \brief Gives back the stored uedge references.
1.349 ///
1.350 - /// Gives back the stored undir edge references.
1.351 - const UndirEdgeRefMap& undirEdgeRef() const {
1.352 - return undirEdgeRefMap;
1.353 + /// Gives back the stored uedge references.
1.354 + const UEdgeRefMap& uEdgeRef() const {
1.355 + return uEdgeRefMap;
1.356 }
1.357
1.358 void run() {}
1.359 @@ -784,7 +784,7 @@
1.360
1.361 NodeRefMap nodeRefMap;
1.362 EdgeRefMap edgeRefMap;
1.363 - UndirEdgeRefMap undirEdgeRefMap;
1.364 + UEdgeRefMap uEdgeRefMap;
1.365 };
1.366
1.367 /// \brief Copy a graph to an other graph.
1.368 @@ -801,9 +801,9 @@
1.369 /// contain the mapping from the target graph's edges to the source's
1.370 /// edges.
1.371 template <typename Target, typename Source>
1.372 - UndirGraphCopy<Target, Source>
1.373 - copyUndirGraph(Target& target, const Source& source) {
1.374 - return UndirGraphCopy<Target, Source>(target, source);
1.375 + UGraphCopy<Target, Source>
1.376 + copyUGraph(Target& target, const Source& source) {
1.377 + return UGraphCopy<Target, Source>(target, source);
1.378 }
1.379
1.380
1.381 @@ -905,7 +905,7 @@
1.382 typedef _Map Map;
1.383 typedef _Graph Graph;
1.384
1.385 - /// The key type of InvertableMap (Node, Edge, UndirEdge).
1.386 + /// The key type of InvertableMap (Node, Edge, UEdge).
1.387 typedef typename _Map::Key Key;
1.388 /// The value type of the InvertableMap.
1.389 typedef typename _Map::Value Value;
1.390 @@ -1036,7 +1036,7 @@
1.391 ///
1.392 /// \param _Graph The graph class the \c DescriptorMap belongs to.
1.393 /// \param _Item The Item is the Key of the Map. It may be Node, Edge or
1.394 - /// UndirEdge.
1.395 + /// UEdge.
1.396 #ifndef DOXYGEN
1.397 /// \param _Map A ReadWriteMap mapping from the item type to integer.
1.398 template <
1.399 @@ -1055,7 +1055,7 @@
1.400 /// The graph class of DescriptorMap.
1.401 typedef _Graph Graph;
1.402
1.403 - /// The key type of DescriptorMap (Node, Edge, UndirEdge).
1.404 + /// The key type of DescriptorMap (Node, Edge, UEdge).
1.405 typedef typename _Map::Key Key;
1.406 /// The value type of DescriptorMap.
1.407 typedef typename _Map::Value Value;
1.408 @@ -1296,7 +1296,7 @@
1.409 public:
1.410
1.411 typedef typename Graph::Edge Value;
1.412 - typedef typename Graph::UndirEdge Key;
1.413 + typedef typename Graph::UEdge Key;
1.414
1.415 /// \brief Constructor
1.416 ///
1.417 @@ -1335,7 +1335,7 @@
1.418 public:
1.419
1.420 typedef typename Graph::Edge Value;
1.421 - typedef typename Graph::UndirEdge Key;
1.422 + typedef typename Graph::UEdge Key;
1.423
1.424 /// \brief Constructor
1.425 ///