1.1 --- a/lemon/concept/ugraph.h Wed Feb 22 18:26:56 2006 +0000
1.2 +++ b/lemon/concept/ugraph.h Thu Feb 23 08:55:54 2006 +0000
1.3 @@ -864,6 +864,10 @@
1.4 void nextIn(Edge&) const {}
1.5
1.6
1.7 + void firstInc(UEdge &, bool &, const Node &) const {}
1.8 +
1.9 + void nextInc(UEdge &, bool &) const {}
1.10 +
1.11 /// \brief Base node of the iterator
1.12 ///
1.13 /// Returns the base node (the source in this case) of the iterator
2.1 --- a/lemon/graph_adaptor.h Wed Feb 22 18:26:56 2006 +0000
2.2 +++ b/lemon/graph_adaptor.h Thu Feb 23 08:55:54 2006 +0000
2.3 @@ -698,13 +698,13 @@
2.4 };
2.5
2.6 template <typename _Graph>
2.7 - class UndirectGraphAdaptorBase :
2.8 + class UndirGraphAdaptorBase :
2.9 public UGraphBaseExtender<GraphAdaptorBase<_Graph> > {
2.10 public:
2.11 typedef _Graph Graph;
2.12 typedef UGraphBaseExtender<GraphAdaptorBase<_Graph> > Parent;
2.13 protected:
2.14 - UndirectGraphAdaptorBase() : Parent() { }
2.15 + UndirGraphAdaptorBase() : Parent() { }
2.16 public:
2.17 typedef typename Parent::UEdge UEdge;
2.18 typedef typename Parent::Edge Edge;
2.19 @@ -712,17 +712,17 @@
2.20 template <typename T>
2.21 class EdgeMap {
2.22 protected:
2.23 - const UndirectGraphAdaptorBase<_Graph>* g;
2.24 + const UndirGraphAdaptorBase<_Graph>* g;
2.25 template <typename TT> friend class EdgeMap;
2.26 typename _Graph::template EdgeMap<T> forward_map, backward_map;
2.27 public:
2.28 typedef T Value;
2.29 typedef Edge Key;
2.30
2.31 - EdgeMap(const UndirectGraphAdaptorBase<_Graph>& _g) : g(&_g),
2.32 + EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g) : g(&_g),
2.33 forward_map(*(g->graph)), backward_map(*(g->graph)) { }
2.34
2.35 - EdgeMap(const UndirectGraphAdaptorBase<_Graph>& _g, T a) : g(&_g),
2.36 + EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g, T a) : g(&_g),
2.37 forward_map(*(g->graph), a), backward_map(*(g->graph), a) { }
2.38
2.39 void set(Edge e, T a) {
2.40 @@ -748,10 +748,10 @@
2.41 typedef T Value;
2.42 typedef UEdge Key;
2.43
2.44 - UEdgeMap(const UndirectGraphAdaptorBase<_Graph>& g) :
2.45 + UEdgeMap(const UndirGraphAdaptorBase<_Graph>& g) :
2.46 map(*(g.graph)) { }
2.47
2.48 - UEdgeMap(const UndirectGraphAdaptorBase<_Graph>& g, T a) :
2.49 + UEdgeMap(const UndirGraphAdaptorBase<_Graph>& g, T a) :
2.50 map(*(g.graph), a) { }
2.51
2.52 void set(UEdge e, T a) {
2.53 @@ -773,17 +773,17 @@
2.54 ///
2.55 /// \author Marton Makai
2.56 template<typename _Graph>
2.57 - class UndirectGraphAdaptor :
2.58 + class UndirGraphAdaptor :
2.59 public UGraphAdaptorExtender<
2.60 - UndirectGraphAdaptorBase<_Graph> > {
2.61 + UndirGraphAdaptorBase<_Graph> > {
2.62 public:
2.63 typedef _Graph Graph;
2.64 typedef UGraphAdaptorExtender<
2.65 - UndirectGraphAdaptorBase<_Graph> > Parent;
2.66 + UndirGraphAdaptorBase<_Graph> > Parent;
2.67 protected:
2.68 - UndirectGraphAdaptor() { }
2.69 + UndirGraphAdaptor() { }
2.70 public:
2.71 - UndirectGraphAdaptor(_Graph& _graph) {
2.72 + UndirGraphAdaptor(_Graph& _graph) {
2.73 setGraph(_graph);
2.74 }
2.75 };
3.1 --- a/lemon/ugraph_adaptor.h Wed Feb 22 18:26:56 2006 +0000
3.2 +++ b/lemon/ugraph_adaptor.h Thu Feb 23 08:55:54 2006 +0000
3.3 @@ -511,9 +511,6 @@
3.4 /// \brief A graph adaptor for hiding nodes and edges from an undirected
3.5 /// graph.
3.6 ///
3.7 - /// \warning Graph adaptors are in even more experimental state than the
3.8 - /// other parts of the lib. Use them at you own risk.
3.9 - ///
3.10 /// SubUGraphAdaptor shows the undirected graph with filtered node-set and
3.11 /// edge-set. If the \c checked parameter is true then it filters the edgeset
3.12 /// to do not get invalid edges without source or target.
3.13 @@ -528,11 +525,6 @@
3.14 /// Note that \c n is of type \c SubGA::NodeIt, but it can be converted to
3.15 /// \c Graph::Node that is why \c g.id(n) can be applied.
3.16 ///
3.17 - /// For examples see also the documentation of NodeSubUGraphAdaptor and
3.18 - /// EdgeSubUGraphAdaptor.
3.19 - ///
3.20 - /// \author Marton Makai
3.21 -
3.22 template<typename _UGraph, typename NodeFilterMap,
3.23 typename UEdgeFilterMap, bool checked = true>
3.24 class SubUGraphAdaptor :
3.25 @@ -553,13 +545,42 @@
3.26 }
3.27 };
3.28
3.29 + template<typename UGraph, typename NodeFilterMap, typename EdgeFilterMap>
3.30 + SubUGraphAdaptor<const UGraph, NodeFilterMap, EdgeFilterMap>
3.31 + subUGraphAdaptor(const UGraph& graph,
3.32 + NodeFilterMap& nfm, EdgeFilterMap& efm) {
3.33 + return SubUGraphAdaptor<const UGraph, NodeFilterMap, EdgeFilterMap>
3.34 + (graph, nfm, efm);
3.35 + }
3.36 +
3.37 + template<typename UGraph, typename NodeFilterMap, typename EdgeFilterMap>
3.38 + SubUGraphAdaptor<const UGraph, const NodeFilterMap, EdgeFilterMap>
3.39 + subUGraphAdaptor(const UGraph& graph,
3.40 + NodeFilterMap& nfm, EdgeFilterMap& efm) {
3.41 + return SubUGraphAdaptor<const UGraph, const NodeFilterMap, EdgeFilterMap>
3.42 + (graph, nfm, efm);
3.43 + }
3.44 +
3.45 + template<typename UGraph, typename NodeFilterMap, typename EdgeFilterMap>
3.46 + SubUGraphAdaptor<const UGraph, NodeFilterMap, const EdgeFilterMap>
3.47 + subUGraphAdaptor(const UGraph& graph,
3.48 + NodeFilterMap& nfm, EdgeFilterMap& efm) {
3.49 + return SubUGraphAdaptor<const UGraph, NodeFilterMap, const EdgeFilterMap>
3.50 + (graph, nfm, efm);
3.51 + }
3.52 +
3.53 + template<typename UGraph, typename NodeFilterMap, typename EdgeFilterMap>
3.54 + SubUGraphAdaptor<const UGraph, const NodeFilterMap, const EdgeFilterMap>
3.55 + subUGraphAdaptor(const UGraph& graph,
3.56 + NodeFilterMap& nfm, EdgeFilterMap& efm) {
3.57 + return SubUGraphAdaptor<const UGraph, const NodeFilterMap,
3.58 + const EdgeFilterMap>(graph, nfm, efm);
3.59 + }
3.60 +
3.61 /// \ingroup graph_adaptors
3.62 ///
3.63 - /// \brief An adaptor for hiding nodes from an undorected graph.
3.64 + /// \brief An adaptor for hiding nodes from an undirected graph.
3.65 ///
3.66 - /// \warning Graph adaptors are in even more experimental state
3.67 - /// than the other
3.68 - /// parts of the lib. Use them at you own risk.
3.69 ///
3.70 /// An adaptor for hiding nodes from an undirected graph.
3.71 /// This adaptor specializes SubUGraphAdaptor in the way that only
3.72 @@ -567,7 +588,6 @@
3.73 /// can be filtered. In usual case the checked parameter is true, we get the
3.74 /// induced subgraph. But if the checked parameter is false then we can only
3.75 /// filter only isolated nodes.
3.76 - /// \author Marton Makai
3.77 template<typename _UGraph, typename NodeFilterMap, bool checked = true>
3.78 class NodeSubUGraphAdaptor :
3.79 public SubUGraphAdaptor<_UGraph, NodeFilterMap,
3.80 @@ -609,8 +629,6 @@
3.81 /// This adaptor specializes SubUGraphAdaptor in the way that
3.82 /// only the edge-set
3.83 /// can be filtered.
3.84 - ///
3.85 - ///\author Marton Makai
3.86 template<typename _UGraph, typename UEdgeFilterMap>
3.87 class EdgeSubUGraphAdaptor :
3.88 public SubUGraphAdaptor<_UGraph, ConstMap<typename _UGraph::Node,bool>,
3.89 @@ -643,7 +661,7 @@
3.90 }
3.91
3.92 template <typename _UGraph, typename _DirectionMap>
3.93 - class DirectUGraphAdaptorBase {
3.94 + class DirUGraphAdaptorBase {
3.95 public:
3.96
3.97 typedef _UGraph Graph;
3.98 @@ -736,19 +754,19 @@
3.99 class NodeMap : public _UGraph::template NodeMap<_Value> {
3.100 public:
3.101 typedef typename _UGraph::template NodeMap<_Value> Parent;
3.102 - explicit NodeMap(const DirectUGraphAdaptorBase& ga)
3.103 + explicit NodeMap(const DirUGraphAdaptorBase& ga)
3.104 : Parent(*ga.graph) { }
3.105 - NodeMap(const DirectUGraphAdaptorBase& ga, const _Value& value)
3.106 + NodeMap(const DirUGraphAdaptorBase& ga, const _Value& value)
3.107 : Parent(*ga.graph, value) { }
3.108 };
3.109
3.110 template <typename _Value>
3.111 class EdgeMap : public _UGraph::template UEdgeMap<_Value> {
3.112 public:
3.113 - typedef typename _UGraph::template EdgeMap<_Value> Parent;
3.114 - explicit EdgeMap(const DirectUGraphAdaptorBase& ga)
3.115 + typedef typename _UGraph::template UEdgeMap<_Value> Parent;
3.116 + explicit EdgeMap(const DirUGraphAdaptorBase& ga)
3.117 : Parent(*ga.graph) { }
3.118 - EdgeMap(const DirectUGraphAdaptorBase& ga, const _Value& value)
3.119 + EdgeMap(const DirUGraphAdaptorBase& ga, const _Value& value)
3.120 : Parent(*ga.graph, value) { }
3.121 };
3.122
3.123 @@ -769,33 +787,43 @@
3.124 };
3.125
3.126
3.127 - template<typename _Graph, typename DirectionMap>
3.128 - class DirectUGraphAdaptor :
3.129 + /// \ingroup graph_adaptors
3.130 + /// \brief A directed graph is made from a undirected graph by an adaptor
3.131 + ///
3.132 + /// This adaptor gives a direction for each uedge in the undirected graph.
3.133 + /// The direction of the edges stored in the DirectionMap. This map is
3.134 + /// a bool map on the undirected edges. If the uedge is mapped to true
3.135 + /// then the direction of the directed edge will be the same as the
3.136 + /// default direction of the uedge. The edges can be easily reverted
3.137 + /// by the reverseEdge member in the adaptor.
3.138 + template<typename _Graph,
3.139 + typename DirectionMap = typename _Graph::template UEdgeMap<bool> >
3.140 + class DirUGraphAdaptor :
3.141 public GraphAdaptorExtender<
3.142 - DirectUGraphAdaptorBase<_Graph, DirectionMap> > {
3.143 + DirUGraphAdaptorBase<_Graph, DirectionMap> > {
3.144 public:
3.145 typedef _Graph Graph;
3.146 typedef GraphAdaptorExtender<
3.147 - DirectUGraphAdaptorBase<_Graph, DirectionMap> > Parent;
3.148 + DirUGraphAdaptorBase<_Graph, DirectionMap> > Parent;
3.149 protected:
3.150 - DirectUGraphAdaptor() { }
3.151 + DirUGraphAdaptor() { }
3.152 public:
3.153 - DirectUGraphAdaptor(_Graph& _graph, DirectionMap& _direction_map) {
3.154 + DirUGraphAdaptor(_Graph& _graph, DirectionMap& _direction_map) {
3.155 setGraph(_graph);
3.156 setDirectionMap(_direction_map);
3.157 }
3.158 };
3.159
3.160 template<typename UGraph, typename DirectionMap>
3.161 - DirectUGraphAdaptor<const UGraph, DirectionMap>
3.162 - directUGraphAdaptor(const UGraph& graph, DirectionMap& dm) {
3.163 - return DirectUGraphAdaptor<const UGraph, DirectionMap>(graph, dm);
3.164 + DirUGraphAdaptor<const UGraph, DirectionMap>
3.165 + dirUGraphAdaptor(const UGraph& graph, DirectionMap& dm) {
3.166 + return DirUGraphAdaptor<const UGraph, DirectionMap>(graph, dm);
3.167 }
3.168
3.169 template<typename UGraph, typename DirectionMap>
3.170 - DirectUGraphAdaptor<const UGraph, const DirectionMap>
3.171 - directUGraphAdaptor(const UGraph& graph, const DirectionMap& dm) {
3.172 - return DirectUGraphAdaptor<const UGraph, const DirectionMap>(graph, dm);
3.173 + DirUGraphAdaptor<const UGraph, const DirectionMap>
3.174 + dirUGraphAdaptor(const UGraph& graph, const DirectionMap& dm) {
3.175 + return DirUGraphAdaptor<const UGraph, const DirectionMap>(graph, dm);
3.176 }
3.177
3.178 }
4.1 --- a/test/graph_adaptor_test.cc Wed Feb 22 18:26:56 2006 +0000
4.2 +++ b/test/graph_adaptor_test.cc Thu Feb 23 08:55:54 2006 +0000
4.3 @@ -26,6 +26,7 @@
4.4 #include<lemon/list_graph.h>
4.5 #include<lemon/full_graph.h>
4.6 #include<lemon/graph_adaptor.h>
4.7 +#include<lemon/ugraph_adaptor.h>
4.8
4.9 #include"test/test_tools.h"
4.10 #include"test/graph_test.h"
4.11 @@ -66,8 +67,17 @@
4.12 checkConcept<StaticGraph, ErasingFirstGraphAdaptor<Graph,
4.13 Graph::NodeMap<Graph::Edge> > >();
4.14
4.15 - /// \bug why does not compile with StaticGraph
4.16 - checkConcept<UGraph, UndirectGraphAdaptor<ListGraph> >();
4.17 + checkConcept<UGraph, UndirGraphAdaptor<Graph> >();
4.18 +
4.19 + checkConcept<UGraph, SubUGraphAdaptor<UGraph,
4.20 + UGraph::NodeMap<bool> , UGraph::UEdgeMap<bool> > >();
4.21 + checkConcept<UGraph, NodeSubUGraphAdaptor<UGraph,
4.22 + UGraph::NodeMap<bool> > >();
4.23 + checkConcept<UGraph, EdgeSubUGraphAdaptor<UGraph,
4.24 + UGraph::UEdgeMap<bool> > >();
4.25 +
4.26 + checkConcept<StaticGraph, DirUGraphAdaptor<UGraph,
4.27 + UGraph::UEdgeMap<bool> > >();
4.28 }
4.29 std::cout << __FILE__ ": All tests passed.\n";
4.30