815 return SubDigraph<const Digraph, const NodeFilterMap, |
815 return SubDigraph<const Digraph, const NodeFilterMap, |
816 const ArcFilterMap>(digraph, nfm, afm); |
816 const ArcFilterMap>(digraph, nfm, afm); |
817 } |
817 } |
818 |
818 |
819 |
819 |
820 template <typename _Graph, typename NodeFilterMap, |
820 template <typename _Graph, typename _NodeFilterMap, |
821 typename EdgeFilterMap, bool _checked = true> |
821 typename _EdgeFilterMap, bool _checked = true> |
822 class SubGraphBase : public GraphAdaptorBase<_Graph> { |
822 class SubGraphBase : public GraphAdaptorBase<_Graph> { |
823 public: |
823 public: |
824 typedef _Graph Graph; |
824 typedef _Graph Graph; |
|
825 typedef _NodeFilterMap NodeFilterMap; |
|
826 typedef _EdgeFilterMap EdgeFilterMap; |
|
827 |
825 typedef SubGraphBase Adaptor; |
828 typedef SubGraphBase Adaptor; |
826 typedef GraphAdaptorBase<_Graph> Parent; |
829 typedef GraphAdaptorBase<_Graph> Parent; |
827 protected: |
830 protected: |
828 |
831 |
829 NodeFilterMap* _node_filter_map; |
832 NodeFilterMap* _node_filter_map; |
1046 } |
1049 } |
1047 }; |
1050 }; |
1048 |
1051 |
1049 }; |
1052 }; |
1050 |
1053 |
1051 template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap> |
1054 template <typename _Graph, typename _NodeFilterMap, typename _EdgeFilterMap> |
1052 class SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap, false> |
1055 class SubGraphBase<_Graph, _NodeFilterMap, _EdgeFilterMap, false> |
1053 : public GraphAdaptorBase<_Graph> { |
1056 : public GraphAdaptorBase<_Graph> { |
1054 public: |
1057 public: |
1055 typedef _Graph Graph; |
1058 typedef _Graph Graph; |
|
1059 typedef _NodeFilterMap NodeFilterMap; |
|
1060 typedef _EdgeFilterMap EdgeFilterMap; |
|
1061 |
1056 typedef SubGraphBase Adaptor; |
1062 typedef SubGraphBase Adaptor; |
1057 typedef GraphAdaptorBase<_Graph> Parent; |
1063 typedef GraphAdaptorBase<_Graph> Parent; |
1058 protected: |
1064 protected: |
1059 NodeFilterMap* _node_filter_map; |
1065 NodeFilterMap* _node_filter_map; |
1060 EdgeFilterMap* _edge_filter_map; |
1066 EdgeFilterMap* _edge_filter_map; |
1855 void erase(const Edge& i) { _digraph->erase(i); } |
1861 void erase(const Edge& i) { _digraph->erase(i); } |
1856 |
1862 |
1857 void clear() { _digraph->clear(); } |
1863 void clear() { _digraph->clear(); } |
1858 |
1864 |
1859 typedef NodeNumTagIndicator<Digraph> NodeNumTag; |
1865 typedef NodeNumTagIndicator<Digraph> NodeNumTag; |
1860 int nodeNum() const { return 2 * _digraph->arcNum(); } |
1866 int nodeNum() const { return _digraph->nodeNum(); } |
1861 |
1867 |
1862 typedef ArcNumTagIndicator<Digraph> ArcNumTag; |
1868 typedef ArcNumTagIndicator<Digraph> ArcNumTag; |
1863 int arcNum() const { return 2 * _digraph->arcNum(); } |
1869 int arcNum() const { return 2 * _digraph->arcNum(); } |
1864 |
1870 |
1865 typedef ArcNumTag EdgeNumTag; |
1871 typedef ArcNumTag EdgeNumTag; |
1890 if (p == INVALID) { |
1896 if (p == INVALID) { |
1891 Edge arc = _digraph->findArc(s, t); |
1897 Edge arc = _digraph->findArc(s, t); |
1892 if (arc != INVALID) return arc; |
1898 if (arc != INVALID) return arc; |
1893 arc = _digraph->findArc(t, s); |
1899 arc = _digraph->findArc(t, s); |
1894 if (arc != INVALID) return arc; |
1900 if (arc != INVALID) return arc; |
1895 } else if (_digraph->s(p) == s) { |
1901 } else if (_digraph->source(p) == s) { |
1896 Edge arc = _digraph->findArc(s, t, p); |
1902 Edge arc = _digraph->findArc(s, t, p); |
1897 if (arc != INVALID) return arc; |
1903 if (arc != INVALID) return arc; |
1898 arc = _digraph->findArc(t, s); |
1904 arc = _digraph->findArc(t, s); |
1899 if (arc != INVALID) return arc; |
1905 if (arc != INVALID) return arc; |
1900 } else { |
1906 } else { |
1919 |
1925 |
1920 typedef typename MapTraits<MapImpl>::ReferenceMapTag ReferenceMapTag; |
1926 typedef typename MapTraits<MapImpl>::ReferenceMapTag ReferenceMapTag; |
1921 |
1927 |
1922 typedef _Value Value; |
1928 typedef _Value Value; |
1923 typedef Arc Key; |
1929 typedef Arc Key; |
|
1930 typedef typename MapTraits<MapImpl>::ConstReturnValue ConstReturnValue; |
|
1931 typedef typename MapTraits<MapImpl>::ReturnValue ReturnValue; |
|
1932 typedef typename MapTraits<MapImpl>::ConstReturnValue ConstReference; |
|
1933 typedef typename MapTraits<MapImpl>::ReturnValue Reference; |
1924 |
1934 |
1925 ArcMapBase(const Adaptor& adaptor) : |
1935 ArcMapBase(const Adaptor& adaptor) : |
1926 _forward(*adaptor._digraph), _backward(*adaptor._digraph) {} |
1936 _forward(*adaptor._digraph), _backward(*adaptor._digraph) {} |
1927 |
1937 |
1928 ArcMapBase(const Adaptor& adaptor, const Value& v) |
1938 ArcMapBase(const Adaptor& adaptor, const Value& v) |
1934 } else { |
1944 } else { |
1935 _backward.set(a, v); |
1945 _backward.set(a, v); |
1936 } |
1946 } |
1937 } |
1947 } |
1938 |
1948 |
1939 typename MapTraits<MapImpl>::ConstReturnValue |
1949 ConstReturnValue operator[](const Arc& a) const { |
1940 operator[](const Arc& a) const { |
|
1941 if (direction(a)) { |
1950 if (direction(a)) { |
1942 return _forward[a]; |
1951 return _forward[a]; |
1943 } else { |
1952 } else { |
1944 return _backward[a]; |
1953 return _backward[a]; |
1945 } |
1954 } |
1946 } |
1955 } |
1947 |
1956 |
1948 typename MapTraits<MapImpl>::ReturnValue |
1957 ReturnValue operator[](const Arc& a) { |
1949 operator[](const Arc& a) { |
|
1950 if (direction(a)) { |
1958 if (direction(a)) { |
1951 return _forward[a]; |
1959 return _forward[a]; |
1952 } else { |
1960 } else { |
1953 return _backward[a]; |
1961 return _backward[a]; |
1954 } |
1962 } |
1994 { |
2002 { |
1995 public: |
2003 public: |
1996 typedef _Value Value; |
2004 typedef _Value Value; |
1997 typedef SubMapExtender<Adaptor, ArcMapBase<Value> > Parent; |
2005 typedef SubMapExtender<Adaptor, ArcMapBase<Value> > Parent; |
1998 |
2006 |
1999 ArcMap(const Adaptor& adaptor) |
2007 explicit ArcMap(const Adaptor& adaptor) |
2000 : Parent(adaptor) {} |
2008 : Parent(adaptor) {} |
2001 |
2009 |
2002 ArcMap(const Adaptor& adaptor, const Value& value) |
2010 ArcMap(const Adaptor& adaptor, const Value& value) |
2003 : Parent(adaptor, value) {} |
2011 : Parent(adaptor, value) {} |
2004 |
2012 |
2040 |
2048 |
2041 }; |
2049 }; |
2042 |
2050 |
2043 typedef typename ItemSetTraits<Digraph, Node>::ItemNotifier NodeNotifier; |
2051 typedef typename ItemSetTraits<Digraph, Node>::ItemNotifier NodeNotifier; |
2044 NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); } |
2052 NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); } |
|
2053 |
|
2054 typedef typename ItemSetTraits<Digraph, Edge>::ItemNotifier EdgeNotifier; |
|
2055 EdgeNotifier& notifier(Edge) const { return _digraph->notifier(Edge()); } |
2045 |
2056 |
2046 protected: |
2057 protected: |
2047 |
2058 |
2048 UndirectorBase() : _digraph(0) {} |
2059 UndirectorBase() : _digraph(0) {} |
2049 |
2060 |
2097 |
2108 |
2098 typedef typename MapTraits<ForwardMap>::ReferenceMapTag ReferenceMapTag; |
2109 typedef typename MapTraits<ForwardMap>::ReferenceMapTag ReferenceMapTag; |
2099 |
2110 |
2100 typedef typename ForwardMap::Value Value; |
2111 typedef typename ForwardMap::Value Value; |
2101 typedef typename Parent::Arc Key; |
2112 typedef typename Parent::Arc Key; |
|
2113 |
|
2114 typedef typename MapTraits<ForwardMap>::ReturnValue ReturnValue; |
|
2115 typedef typename MapTraits<ForwardMap>::ConstReturnValue ConstReturnValue; |
|
2116 typedef typename MapTraits<ForwardMap>::ReturnValue Reference; |
|
2117 typedef typename MapTraits<ForwardMap>::ConstReturnValue ConstReference; |
2102 |
2118 |
2103 /// \brief Constructor |
2119 /// \brief Constructor |
2104 /// |
2120 /// |
2105 /// Constructor |
2121 /// Constructor |
2106 CombinedArcMap(ForwardMap& forward, BackwardMap& backward) |
2122 CombinedArcMap(ForwardMap& forward, BackwardMap& backward) |
2119 } |
2135 } |
2120 |
2136 |
2121 /// \brief Returns the value associated with a key. |
2137 /// \brief Returns the value associated with a key. |
2122 /// |
2138 /// |
2123 /// Returns the value associated with a key. |
2139 /// Returns the value associated with a key. |
2124 typename MapTraits<ForwardMap>::ConstReturnValue |
2140 ConstReturnValue operator[](const Key& e) const { |
2125 operator[](const Key& e) const { |
|
2126 if (Parent::direction(e)) { |
2141 if (Parent::direction(e)) { |
2127 return (*_forward)[e]; |
2142 return (*_forward)[e]; |
2128 } else { |
2143 } else { |
2129 return (*_backward)[e]; |
2144 return (*_backward)[e]; |
2130 } |
2145 } |
2131 } |
2146 } |
2132 |
2147 |
2133 /// \brief Returns the value associated with a key. |
2148 /// \brief Returns the value associated with a key. |
2134 /// |
2149 /// |
2135 /// Returns the value associated with a key. |
2150 /// Returns the value associated with a key. |
2136 typename MapTraits<ForwardMap>::ReturnValue |
2151 ReturnValue operator[](const Key& e) { |
2137 operator[](const Key& e) { |
|
2138 if (Parent::direction(e)) { |
2152 if (Parent::direction(e)) { |
2139 return (*_forward)[e]; |
2153 return (*_forward)[e]; |
2140 } else { |
2154 } else { |
2141 return (*_backward)[e]; |
2155 return (*_backward)[e]; |
2142 } |
2156 } |
2244 int arcNum() const { return _graph->edgeNum(); } |
2258 int arcNum() const { return _graph->edgeNum(); } |
2245 |
2259 |
2246 typedef FindEdgeTagIndicator<Graph> FindArcTag; |
2260 typedef FindEdgeTagIndicator<Graph> FindArcTag; |
2247 Arc findArc(const Node& u, const Node& v, |
2261 Arc findArc(const Node& u, const Node& v, |
2248 const Arc& prev = INVALID) const { |
2262 const Arc& prev = INVALID) const { |
2249 Arc arc = prev; |
2263 Arc arc = _graph->findEdge(u, v, prev); |
2250 bool d = arc == INVALID ? true : (*_direction)[arc]; |
2264 while (arc != INVALID && source(arc) != u) { |
2251 if (d) { |
|
2252 arc = _graph->findEdge(u, v, arc); |
2265 arc = _graph->findEdge(u, v, arc); |
2253 while (arc != INVALID && !(*_direction)[arc]) { |
|
2254 _graph->findEdge(u, v, arc); |
|
2255 } |
|
2256 if (arc != INVALID) return arc; |
|
2257 } |
|
2258 _graph->findEdge(v, u, arc); |
|
2259 while (arc != INVALID && (*_direction)[arc]) { |
|
2260 _graph->findEdge(u, v, arc); |
|
2261 } |
2266 } |
2262 return arc; |
2267 return arc; |
2263 } |
2268 } |
2264 |
2269 |
2265 Node addNode() { |
2270 Node addNode() { |
2266 return Node(_graph->addNode()); |
2271 return Node(_graph->addNode()); |
2267 } |
2272 } |
2268 |
2273 |
2269 Arc addArc(const Node& u, const Node& v) { |
2274 Arc addArc(const Node& u, const Node& v) { |
2270 Arc arc = _graph->addArc(u, v); |
2275 Arc arc = _graph->addEdge(u, v); |
2271 _direction->set(arc, _graph->source(arc) == u); |
2276 _direction->set(arc, _graph->u(arc) == u); |
2272 return arc; |
2277 return arc; |
2273 } |
2278 } |
2274 |
2279 |
2275 void erase(const Node& i) { _graph->erase(i); } |
2280 void erase(const Node& i) { _graph->erase(i); } |
2276 void erase(const Arc& i) { _graph->erase(i); } |
2281 void erase(const Arc& i) { _graph->erase(i); } |
2910 } |
2915 } |
2911 |
2916 |
2912 typedef True FindArcTag; |
2917 typedef True FindArcTag; |
2913 Arc findArc(const Node& u, const Node& v, |
2918 Arc findArc(const Node& u, const Node& v, |
2914 const Arc& prev = INVALID) const { |
2919 const Arc& prev = INVALID) const { |
2915 if (inNode(u)) { |
2920 if (inNode(u) && outNode(v)) { |
2916 if (outNode(v)) { |
2921 if (static_cast<const DigraphNode&>(u) == |
2917 if (static_cast<const DigraphNode&>(u) == |
2922 static_cast<const DigraphNode&>(v) && prev == INVALID) { |
2918 static_cast<const DigraphNode&>(v) && prev == INVALID) { |
2923 return Arc(u); |
2919 return Arc(u); |
|
2920 } |
|
2921 } |
2924 } |
2922 } else { |
2925 } |
2923 if (inNode(v)) { |
2926 else if (outNode(u) && inNode(v)) { |
2924 return Arc(::lemon::findArc(*_digraph, u, v, prev)); |
2927 return Arc(::lemon::findArc(*_digraph, u, v, prev)); |
2925 } |
|
2926 } |
2928 } |
2927 return INVALID; |
2929 return INVALID; |
2928 } |
2930 } |
2929 |
2931 |
2930 private: |
2932 private: |
2934 : public MapTraits<typename Parent::template NodeMap<_Value> > { |
2936 : public MapTraits<typename Parent::template NodeMap<_Value> > { |
2935 typedef typename Parent::template NodeMap<_Value> NodeImpl; |
2937 typedef typename Parent::template NodeMap<_Value> NodeImpl; |
2936 public: |
2938 public: |
2937 typedef Node Key; |
2939 typedef Node Key; |
2938 typedef _Value Value; |
2940 typedef _Value Value; |
|
2941 typedef typename MapTraits<NodeImpl>::ReferenceMapTag ReferenceMapTag; |
|
2942 typedef typename MapTraits<NodeImpl>::ReturnValue ReturnValue; |
|
2943 typedef typename MapTraits<NodeImpl>::ConstReturnValue ConstReturnValue; |
|
2944 typedef typename MapTraits<NodeImpl>::ReturnValue Reference; |
|
2945 typedef typename MapTraits<NodeImpl>::ConstReturnValue ConstReference; |
2939 |
2946 |
2940 NodeMapBase(const Adaptor& adaptor) |
2947 NodeMapBase(const Adaptor& adaptor) |
2941 : _in_map(*adaptor._digraph), _out_map(*adaptor._digraph) {} |
2948 : _in_map(*adaptor._digraph), _out_map(*adaptor._digraph) {} |
2942 NodeMapBase(const Adaptor& adaptor, const Value& value) |
2949 NodeMapBase(const Adaptor& adaptor, const Value& value) |
2943 : _in_map(*adaptor._digraph, value), |
2950 : _in_map(*adaptor._digraph, value), |
2946 void set(const Node& key, const Value& val) { |
2953 void set(const Node& key, const Value& val) { |
2947 if (Adaptor::inNode(key)) { _in_map.set(key, val); } |
2954 if (Adaptor::inNode(key)) { _in_map.set(key, val); } |
2948 else {_out_map.set(key, val); } |
2955 else {_out_map.set(key, val); } |
2949 } |
2956 } |
2950 |
2957 |
2951 typename MapTraits<NodeImpl>::ReturnValue |
2958 ReturnValue operator[](const Node& key) { |
2952 operator[](const Node& key) { |
|
2953 if (Adaptor::inNode(key)) { return _in_map[key]; } |
2959 if (Adaptor::inNode(key)) { return _in_map[key]; } |
2954 else { return _out_map[key]; } |
2960 else { return _out_map[key]; } |
2955 } |
2961 } |
2956 |
2962 |
2957 typename MapTraits<NodeImpl>::ConstReturnValue |
2963 ConstReturnValue operator[](const Node& key) const { |
2958 operator[](const Node& key) const { |
|
2959 if (Adaptor::inNode(key)) { return _in_map[key]; } |
2964 if (Adaptor::inNode(key)) { return _in_map[key]; } |
2960 else { return _out_map[key]; } |
2965 else { return _out_map[key]; } |
2961 } |
2966 } |
2962 |
2967 |
2963 private: |
2968 private: |
2970 typedef typename Parent::template ArcMap<_Value> ArcImpl; |
2975 typedef typename Parent::template ArcMap<_Value> ArcImpl; |
2971 typedef typename Parent::template NodeMap<_Value> NodeImpl; |
2976 typedef typename Parent::template NodeMap<_Value> NodeImpl; |
2972 public: |
2977 public: |
2973 typedef Arc Key; |
2978 typedef Arc Key; |
2974 typedef _Value Value; |
2979 typedef _Value Value; |
|
2980 typedef typename MapTraits<ArcImpl>::ReferenceMapTag ReferenceMapTag; |
|
2981 typedef typename MapTraits<ArcImpl>::ReturnValue ReturnValue; |
|
2982 typedef typename MapTraits<ArcImpl>::ConstReturnValue ConstReturnValue; |
|
2983 typedef typename MapTraits<ArcImpl>::ReturnValue Reference; |
|
2984 typedef typename MapTraits<ArcImpl>::ConstReturnValue ConstReference; |
2975 |
2985 |
2976 ArcMapBase(const Adaptor& adaptor) |
2986 ArcMapBase(const Adaptor& adaptor) |
2977 : _arc_map(*adaptor._digraph), _node_map(*adaptor._digraph) {} |
2987 : _arc_map(*adaptor._digraph), _node_map(*adaptor._digraph) {} |
2978 ArcMapBase(const Adaptor& adaptor, const Value& value) |
2988 ArcMapBase(const Adaptor& adaptor, const Value& value) |
2979 : _arc_map(*adaptor._digraph, value), |
2989 : _arc_map(*adaptor._digraph, value), |
2985 } else { |
2995 } else { |
2986 _node_map.set(key._item.second(), val); |
2996 _node_map.set(key._item.second(), val); |
2987 } |
2997 } |
2988 } |
2998 } |
2989 |
2999 |
2990 typename MapTraits<ArcImpl>::ReturnValue |
3000 ReturnValue operator[](const Arc& key) { |
2991 operator[](const Arc& key) { |
|
2992 if (Adaptor::origArc(key)) { |
3001 if (Adaptor::origArc(key)) { |
2993 return _arc_map[key._item.first()]; |
3002 return _arc_map[key._item.first()]; |
2994 } else { |
3003 } else { |
2995 return _node_map[key._item.second()]; |
3004 return _node_map[key._item.second()]; |
2996 } |
3005 } |
2997 } |
3006 } |
2998 |
3007 |
2999 typename MapTraits<ArcImpl>::ConstReturnValue |
3008 ConstReturnValue operator[](const Arc& key) const { |
3000 operator[](const Arc& key) const { |
|
3001 if (Adaptor::origArc(key)) { |
3009 if (Adaptor::origArc(key)) { |
3002 return _arc_map[key._item.first()]; |
3010 return _arc_map[key._item.first()]; |
3003 } else { |
3011 } else { |
3004 return _node_map[key._item.second()]; |
3012 return _node_map[key._item.second()]; |
3005 } |
3013 } |
3182 public: |
3190 public: |
3183 |
3191 |
3184 typedef Node Key; |
3192 typedef Node Key; |
3185 typedef typename InNodeMap::Value Value; |
3193 typedef typename InNodeMap::Value Value; |
3186 |
3194 |
|
3195 typedef typename MapTraits<InNodeMap>::ReferenceMapTag ReferenceMapTag; |
|
3196 typedef typename MapTraits<InNodeMap>::ReturnValue ReturnValue; |
|
3197 typedef typename MapTraits<InNodeMap>::ConstReturnValue ConstReturnValue; |
|
3198 typedef typename MapTraits<InNodeMap>::ReturnValue Reference; |
|
3199 typedef typename MapTraits<InNodeMap>::ConstReturnValue ConstReference; |
|
3200 |
3187 /// \brief Constructor |
3201 /// \brief Constructor |
3188 /// |
3202 /// |
3189 /// Constructor. |
3203 /// Constructor. |
3190 CombinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map) |
3204 CombinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map) |
3191 : _in_map(in_map), _out_map(out_map) {} |
3205 : _in_map(in_map), _out_map(out_map) {} |
3268 public: |
3282 public: |
3269 |
3283 |
3270 typedef Arc Key; |
3284 typedef Arc Key; |
3271 typedef typename DigraphArcMap::Value Value; |
3285 typedef typename DigraphArcMap::Value Value; |
3272 |
3286 |
|
3287 typedef typename MapTraits<DigraphArcMap>::ReferenceMapTag |
|
3288 ReferenceMapTag; |
|
3289 typedef typename MapTraits<DigraphArcMap>::ReturnValue |
|
3290 ReturnValue; |
|
3291 typedef typename MapTraits<DigraphArcMap>::ConstReturnValue |
|
3292 ConstReturnValue; |
|
3293 typedef typename MapTraits<DigraphArcMap>::ReturnValue |
|
3294 Reference; |
|
3295 typedef typename MapTraits<DigraphArcMap>::ConstReturnValue |
|
3296 ConstReference; |
|
3297 |
3273 /// \brief Constructor |
3298 /// \brief Constructor |
3274 /// |
3299 /// |
3275 /// Constructor. |
3300 /// Constructor. |
3276 CombinedArcMap(DigraphArcMap& arc_map, DigraphNodeMap& node_map) |
3301 CombinedArcMap(DigraphArcMap& arc_map, DigraphNodeMap& node_map) |
3277 : _arc_map(arc_map), _node_map(node_map) {} |
3302 : _arc_map(arc_map), _node_map(node_map) {} |