1.1 --- a/lemon/adaptors.h Fri Dec 12 22:18:41 2008 +0100
1.2 +++ b/lemon/adaptors.h Fri Dec 12 22:59:17 2008 +0100
1.3 @@ -817,11 +817,14 @@
1.4 }
1.5
1.6
1.7 - template <typename _Graph, typename NodeFilterMap,
1.8 - typename EdgeFilterMap, bool _checked = true>
1.9 + template <typename _Graph, typename _NodeFilterMap,
1.10 + typename _EdgeFilterMap, bool _checked = true>
1.11 class SubGraphBase : public GraphAdaptorBase<_Graph> {
1.12 public:
1.13 typedef _Graph Graph;
1.14 + typedef _NodeFilterMap NodeFilterMap;
1.15 + typedef _EdgeFilterMap EdgeFilterMap;
1.16 +
1.17 typedef SubGraphBase Adaptor;
1.18 typedef GraphAdaptorBase<_Graph> Parent;
1.19 protected:
1.20 @@ -1048,11 +1051,14 @@
1.21
1.22 };
1.23
1.24 - template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
1.25 - class SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap, false>
1.26 + template <typename _Graph, typename _NodeFilterMap, typename _EdgeFilterMap>
1.27 + class SubGraphBase<_Graph, _NodeFilterMap, _EdgeFilterMap, false>
1.28 : public GraphAdaptorBase<_Graph> {
1.29 public:
1.30 typedef _Graph Graph;
1.31 + typedef _NodeFilterMap NodeFilterMap;
1.32 + typedef _EdgeFilterMap EdgeFilterMap;
1.33 +
1.34 typedef SubGraphBase Adaptor;
1.35 typedef GraphAdaptorBase<_Graph> Parent;
1.36 protected:
1.37 @@ -1857,7 +1863,7 @@
1.38 void clear() { _digraph->clear(); }
1.39
1.40 typedef NodeNumTagIndicator<Digraph> NodeNumTag;
1.41 - int nodeNum() const { return 2 * _digraph->arcNum(); }
1.42 + int nodeNum() const { return _digraph->nodeNum(); }
1.43
1.44 typedef ArcNumTagIndicator<Digraph> ArcNumTag;
1.45 int arcNum() const { return 2 * _digraph->arcNum(); }
1.46 @@ -1892,7 +1898,7 @@
1.47 if (arc != INVALID) return arc;
1.48 arc = _digraph->findArc(t, s);
1.49 if (arc != INVALID) return arc;
1.50 - } else if (_digraph->s(p) == s) {
1.51 + } else if (_digraph->source(p) == s) {
1.52 Edge arc = _digraph->findArc(s, t, p);
1.53 if (arc != INVALID) return arc;
1.54 arc = _digraph->findArc(t, s);
1.55 @@ -1921,6 +1927,10 @@
1.56
1.57 typedef _Value Value;
1.58 typedef Arc Key;
1.59 + typedef typename MapTraits<MapImpl>::ConstReturnValue ConstReturnValue;
1.60 + typedef typename MapTraits<MapImpl>::ReturnValue ReturnValue;
1.61 + typedef typename MapTraits<MapImpl>::ConstReturnValue ConstReference;
1.62 + typedef typename MapTraits<MapImpl>::ReturnValue Reference;
1.63
1.64 ArcMapBase(const Adaptor& adaptor) :
1.65 _forward(*adaptor._digraph), _backward(*adaptor._digraph) {}
1.66 @@ -1936,8 +1946,7 @@
1.67 }
1.68 }
1.69
1.70 - typename MapTraits<MapImpl>::ConstReturnValue
1.71 - operator[](const Arc& a) const {
1.72 + ConstReturnValue operator[](const Arc& a) const {
1.73 if (direction(a)) {
1.74 return _forward[a];
1.75 } else {
1.76 @@ -1945,8 +1954,7 @@
1.77 }
1.78 }
1.79
1.80 - typename MapTraits<MapImpl>::ReturnValue
1.81 - operator[](const Arc& a) {
1.82 + ReturnValue operator[](const Arc& a) {
1.83 if (direction(a)) {
1.84 return _forward[a];
1.85 } else {
1.86 @@ -1996,7 +2004,7 @@
1.87 typedef _Value Value;
1.88 typedef SubMapExtender<Adaptor, ArcMapBase<Value> > Parent;
1.89
1.90 - ArcMap(const Adaptor& adaptor)
1.91 + explicit ArcMap(const Adaptor& adaptor)
1.92 : Parent(adaptor) {}
1.93
1.94 ArcMap(const Adaptor& adaptor, const Value& value)
1.95 @@ -2043,6 +2051,9 @@
1.96 typedef typename ItemSetTraits<Digraph, Node>::ItemNotifier NodeNotifier;
1.97 NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); }
1.98
1.99 + typedef typename ItemSetTraits<Digraph, Edge>::ItemNotifier EdgeNotifier;
1.100 + EdgeNotifier& notifier(Edge) const { return _digraph->notifier(Edge()); }
1.101 +
1.102 protected:
1.103
1.104 UndirectorBase() : _digraph(0) {}
1.105 @@ -2100,6 +2111,11 @@
1.106 typedef typename ForwardMap::Value Value;
1.107 typedef typename Parent::Arc Key;
1.108
1.109 + typedef typename MapTraits<ForwardMap>::ReturnValue ReturnValue;
1.110 + typedef typename MapTraits<ForwardMap>::ConstReturnValue ConstReturnValue;
1.111 + typedef typename MapTraits<ForwardMap>::ReturnValue Reference;
1.112 + typedef typename MapTraits<ForwardMap>::ConstReturnValue ConstReference;
1.113 +
1.114 /// \brief Constructor
1.115 ///
1.116 /// Constructor
1.117 @@ -2121,8 +2137,7 @@
1.118 /// \brief Returns the value associated with a key.
1.119 ///
1.120 /// Returns the value associated with a key.
1.121 - typename MapTraits<ForwardMap>::ConstReturnValue
1.122 - operator[](const Key& e) const {
1.123 + ConstReturnValue operator[](const Key& e) const {
1.124 if (Parent::direction(e)) {
1.125 return (*_forward)[e];
1.126 } else {
1.127 @@ -2133,8 +2148,7 @@
1.128 /// \brief Returns the value associated with a key.
1.129 ///
1.130 /// Returns the value associated with a key.
1.131 - typename MapTraits<ForwardMap>::ReturnValue
1.132 - operator[](const Key& e) {
1.133 + ReturnValue operator[](const Key& e) {
1.134 if (Parent::direction(e)) {
1.135 return (*_forward)[e];
1.136 } else {
1.137 @@ -2246,18 +2260,9 @@
1.138 typedef FindEdgeTagIndicator<Graph> FindArcTag;
1.139 Arc findArc(const Node& u, const Node& v,
1.140 const Arc& prev = INVALID) const {
1.141 - Arc arc = prev;
1.142 - bool d = arc == INVALID ? true : (*_direction)[arc];
1.143 - if (d) {
1.144 + Arc arc = _graph->findEdge(u, v, prev);
1.145 + while (arc != INVALID && source(arc) != u) {
1.146 arc = _graph->findEdge(u, v, arc);
1.147 - while (arc != INVALID && !(*_direction)[arc]) {
1.148 - _graph->findEdge(u, v, arc);
1.149 - }
1.150 - if (arc != INVALID) return arc;
1.151 - }
1.152 - _graph->findEdge(v, u, arc);
1.153 - while (arc != INVALID && (*_direction)[arc]) {
1.154 - _graph->findEdge(u, v, arc);
1.155 }
1.156 return arc;
1.157 }
1.158 @@ -2267,8 +2272,8 @@
1.159 }
1.160
1.161 Arc addArc(const Node& u, const Node& v) {
1.162 - Arc arc = _graph->addArc(u, v);
1.163 - _direction->set(arc, _graph->source(arc) == u);
1.164 + Arc arc = _graph->addEdge(u, v);
1.165 + _direction->set(arc, _graph->u(arc) == u);
1.166 return arc;
1.167 }
1.168
1.169 @@ -2912,17 +2917,14 @@
1.170 typedef True FindArcTag;
1.171 Arc findArc(const Node& u, const Node& v,
1.172 const Arc& prev = INVALID) const {
1.173 - if (inNode(u)) {
1.174 - if (outNode(v)) {
1.175 - if (static_cast<const DigraphNode&>(u) ==
1.176 - static_cast<const DigraphNode&>(v) && prev == INVALID) {
1.177 - return Arc(u);
1.178 - }
1.179 + if (inNode(u) && outNode(v)) {
1.180 + if (static_cast<const DigraphNode&>(u) ==
1.181 + static_cast<const DigraphNode&>(v) && prev == INVALID) {
1.182 + return Arc(u);
1.183 }
1.184 - } else {
1.185 - if (inNode(v)) {
1.186 - return Arc(::lemon::findArc(*_digraph, u, v, prev));
1.187 - }
1.188 + }
1.189 + else if (outNode(u) && inNode(v)) {
1.190 + return Arc(::lemon::findArc(*_digraph, u, v, prev));
1.191 }
1.192 return INVALID;
1.193 }
1.194 @@ -2936,6 +2938,11 @@
1.195 public:
1.196 typedef Node Key;
1.197 typedef _Value Value;
1.198 + typedef typename MapTraits<NodeImpl>::ReferenceMapTag ReferenceMapTag;
1.199 + typedef typename MapTraits<NodeImpl>::ReturnValue ReturnValue;
1.200 + typedef typename MapTraits<NodeImpl>::ConstReturnValue ConstReturnValue;
1.201 + typedef typename MapTraits<NodeImpl>::ReturnValue Reference;
1.202 + typedef typename MapTraits<NodeImpl>::ConstReturnValue ConstReference;
1.203
1.204 NodeMapBase(const Adaptor& adaptor)
1.205 : _in_map(*adaptor._digraph), _out_map(*adaptor._digraph) {}
1.206 @@ -2948,14 +2955,12 @@
1.207 else {_out_map.set(key, val); }
1.208 }
1.209
1.210 - typename MapTraits<NodeImpl>::ReturnValue
1.211 - operator[](const Node& key) {
1.212 + ReturnValue operator[](const Node& key) {
1.213 if (Adaptor::inNode(key)) { return _in_map[key]; }
1.214 else { return _out_map[key]; }
1.215 }
1.216
1.217 - typename MapTraits<NodeImpl>::ConstReturnValue
1.218 - operator[](const Node& key) const {
1.219 + ConstReturnValue operator[](const Node& key) const {
1.220 if (Adaptor::inNode(key)) { return _in_map[key]; }
1.221 else { return _out_map[key]; }
1.222 }
1.223 @@ -2972,6 +2977,11 @@
1.224 public:
1.225 typedef Arc Key;
1.226 typedef _Value Value;
1.227 + typedef typename MapTraits<ArcImpl>::ReferenceMapTag ReferenceMapTag;
1.228 + typedef typename MapTraits<ArcImpl>::ReturnValue ReturnValue;
1.229 + typedef typename MapTraits<ArcImpl>::ConstReturnValue ConstReturnValue;
1.230 + typedef typename MapTraits<ArcImpl>::ReturnValue Reference;
1.231 + typedef typename MapTraits<ArcImpl>::ConstReturnValue ConstReference;
1.232
1.233 ArcMapBase(const Adaptor& adaptor)
1.234 : _arc_map(*adaptor._digraph), _node_map(*adaptor._digraph) {}
1.235 @@ -2987,8 +2997,7 @@
1.236 }
1.237 }
1.238
1.239 - typename MapTraits<ArcImpl>::ReturnValue
1.240 - operator[](const Arc& key) {
1.241 + ReturnValue operator[](const Arc& key) {
1.242 if (Adaptor::origArc(key)) {
1.243 return _arc_map[key._item.first()];
1.244 } else {
1.245 @@ -2996,8 +3005,7 @@
1.246 }
1.247 }
1.248
1.249 - typename MapTraits<ArcImpl>::ConstReturnValue
1.250 - operator[](const Arc& key) const {
1.251 + ConstReturnValue operator[](const Arc& key) const {
1.252 if (Adaptor::origArc(key)) {
1.253 return _arc_map[key._item.first()];
1.254 } else {
1.255 @@ -3184,6 +3192,12 @@
1.256 typedef Node Key;
1.257 typedef typename InNodeMap::Value Value;
1.258
1.259 + typedef typename MapTraits<InNodeMap>::ReferenceMapTag ReferenceMapTag;
1.260 + typedef typename MapTraits<InNodeMap>::ReturnValue ReturnValue;
1.261 + typedef typename MapTraits<InNodeMap>::ConstReturnValue ConstReturnValue;
1.262 + typedef typename MapTraits<InNodeMap>::ReturnValue Reference;
1.263 + typedef typename MapTraits<InNodeMap>::ConstReturnValue ConstReference;
1.264 +
1.265 /// \brief Constructor
1.266 ///
1.267 /// Constructor.
1.268 @@ -3270,6 +3284,17 @@
1.269 typedef Arc Key;
1.270 typedef typename DigraphArcMap::Value Value;
1.271
1.272 + typedef typename MapTraits<DigraphArcMap>::ReferenceMapTag
1.273 + ReferenceMapTag;
1.274 + typedef typename MapTraits<DigraphArcMap>::ReturnValue
1.275 + ReturnValue;
1.276 + typedef typename MapTraits<DigraphArcMap>::ConstReturnValue
1.277 + ConstReturnValue;
1.278 + typedef typename MapTraits<DigraphArcMap>::ReturnValue
1.279 + Reference;
1.280 + typedef typename MapTraits<DigraphArcMap>::ConstReturnValue
1.281 + ConstReference;
1.282 +
1.283 /// \brief Constructor
1.284 ///
1.285 /// Constructor.