r472:91fcb8ed4cdc
Fri, 12 Dec 2008 22:59:17
[Not Reviewed]
0 comments (0 inline)
0
1
0
71
46
| ... | ... |
@@ -817,11 +817,14 @@ |
| 817 | 817 |
} |
| 818 | 818 |
|
| 819 | 819 |
|
| 820 |
template <typename _Graph, typename NodeFilterMap, |
|
| 821 |
typename EdgeFilterMap, bool _checked = true> |
|
| 820 |
template <typename _Graph, typename _NodeFilterMap, |
|
| 821 |
typename _EdgeFilterMap, bool _checked = true> |
|
| 822 | 822 |
class SubGraphBase : public GraphAdaptorBase<_Graph> {
|
| 823 | 823 |
public: |
| 824 | 824 |
typedef _Graph Graph; |
| 825 |
typedef _NodeFilterMap NodeFilterMap; |
|
| 826 |
typedef _EdgeFilterMap EdgeFilterMap; |
|
| 827 |
|
|
| 825 | 828 |
typedef SubGraphBase Adaptor; |
| 826 | 829 |
typedef GraphAdaptorBase<_Graph> Parent; |
| 827 | 830 |
protected: |
| ... | ... |
@@ -1048,11 +1051,14 @@ |
| 1048 | 1051 |
|
| 1049 | 1052 |
}; |
| 1050 | 1053 |
|
| 1051 |
template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap> |
|
| 1052 |
class SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap, false> |
|
| 1054 |
template <typename _Graph, typename _NodeFilterMap, typename _EdgeFilterMap> |
|
| 1055 |
class SubGraphBase<_Graph, _NodeFilterMap, _EdgeFilterMap, false> |
|
| 1053 | 1056 |
: public GraphAdaptorBase<_Graph> {
|
| 1054 | 1057 |
public: |
| 1055 | 1058 |
typedef _Graph Graph; |
| 1059 |
typedef _NodeFilterMap NodeFilterMap; |
|
| 1060 |
typedef _EdgeFilterMap EdgeFilterMap; |
|
| 1061 |
|
|
| 1056 | 1062 |
typedef SubGraphBase Adaptor; |
| 1057 | 1063 |
typedef GraphAdaptorBase<_Graph> Parent; |
| 1058 | 1064 |
protected: |
| ... | ... |
@@ -1857,7 +1863,7 @@ |
| 1857 | 1863 |
void clear() { _digraph->clear(); }
|
| 1858 | 1864 |
|
| 1859 | 1865 |
typedef NodeNumTagIndicator<Digraph> NodeNumTag; |
| 1860 |
int nodeNum() const { return
|
|
| 1866 |
int nodeNum() const { return _digraph->nodeNum(); }
|
|
| 1861 | 1867 |
|
| 1862 | 1868 |
typedef ArcNumTagIndicator<Digraph> ArcNumTag; |
| 1863 | 1869 |
int arcNum() const { return 2 * _digraph->arcNum(); }
|
| ... | ... |
@@ -1892,7 +1898,7 @@ |
| 1892 | 1898 |
if (arc != INVALID) return arc; |
| 1893 | 1899 |
arc = _digraph->findArc(t, s); |
| 1894 | 1900 |
if (arc != INVALID) return arc; |
| 1895 |
} else if (_digraph-> |
|
| 1901 |
} else if (_digraph->source(p) == s) {
|
|
| 1896 | 1902 |
Edge arc = _digraph->findArc(s, t, p); |
| 1897 | 1903 |
if (arc != INVALID) return arc; |
| 1898 | 1904 |
arc = _digraph->findArc(t, s); |
| ... | ... |
@@ -1921,6 +1927,10 @@ |
| 1921 | 1927 |
|
| 1922 | 1928 |
typedef _Value Value; |
| 1923 | 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 | 1935 |
ArcMapBase(const Adaptor& adaptor) : |
| 1926 | 1936 |
_forward(*adaptor._digraph), _backward(*adaptor._digraph) {}
|
| ... | ... |
@@ -1936,8 +1946,7 @@ |
| 1936 | 1946 |
} |
| 1937 | 1947 |
} |
| 1938 | 1948 |
|
| 1939 |
typename MapTraits<MapImpl>::ConstReturnValue |
|
| 1940 |
operator[](const Arc& a) const {
|
|
| 1949 |
ConstReturnValue operator[](const Arc& a) const {
|
|
| 1941 | 1950 |
if (direction(a)) {
|
| 1942 | 1951 |
return _forward[a]; |
| 1943 | 1952 |
} else {
|
| ... | ... |
@@ -1945,8 +1954,7 @@ |
| 1945 | 1954 |
} |
| 1946 | 1955 |
} |
| 1947 | 1956 |
|
| 1948 |
typename MapTraits<MapImpl>::ReturnValue |
|
| 1949 |
operator[](const Arc& a) {
|
|
| 1957 |
ReturnValue operator[](const Arc& a) {
|
|
| 1950 | 1958 |
if (direction(a)) {
|
| 1951 | 1959 |
return _forward[a]; |
| 1952 | 1960 |
} else {
|
| ... | ... |
@@ -1996,7 +2004,7 @@ |
| 1996 | 2004 |
typedef _Value Value; |
| 1997 | 2005 |
typedef SubMapExtender<Adaptor, ArcMapBase<Value> > Parent; |
| 1998 | 2006 |
|
| 1999 |
ArcMap(const Adaptor& adaptor) |
|
| 2007 |
explicit ArcMap(const Adaptor& adaptor) |
|
| 2000 | 2008 |
: Parent(adaptor) {}
|
| 2001 | 2009 |
|
| 2002 | 2010 |
ArcMap(const Adaptor& adaptor, const Value& value) |
| ... | ... |
@@ -2043,6 +2051,9 @@ |
| 2043 | 2051 |
typedef typename ItemSetTraits<Digraph, Node>::ItemNotifier NodeNotifier; |
| 2044 | 2052 |
NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); }
|
| 2045 | 2053 |
|
| 2054 |
typedef typename ItemSetTraits<Digraph, Edge>::ItemNotifier EdgeNotifier; |
|
| 2055 |
EdgeNotifier& notifier(Edge) const { return _digraph->notifier(Edge()); }
|
|
| 2056 |
|
|
| 2046 | 2057 |
protected: |
| 2047 | 2058 |
|
| 2048 | 2059 |
UndirectorBase() : _digraph(0) {}
|
| ... | ... |
@@ -2100,6 +2111,11 @@ |
| 2100 | 2111 |
typedef typename ForwardMap::Value Value; |
| 2101 | 2112 |
typedef typename Parent::Arc Key; |
| 2102 | 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; |
|
| 2118 |
|
|
| 2103 | 2119 |
/// \brief Constructor |
| 2104 | 2120 |
/// |
| 2105 | 2121 |
/// Constructor |
| ... | ... |
@@ -2121,8 +2137,7 @@ |
| 2121 | 2137 |
/// \brief Returns the value associated with a key. |
| 2122 | 2138 |
/// |
| 2123 | 2139 |
/// Returns the value associated with a key. |
| 2124 |
typename MapTraits<ForwardMap>::ConstReturnValue |
|
| 2125 |
operator[](const Key& e) const {
|
|
| 2140 |
ConstReturnValue operator[](const Key& e) const {
|
|
| 2126 | 2141 |
if (Parent::direction(e)) {
|
| 2127 | 2142 |
return (*_forward)[e]; |
| 2128 | 2143 |
} else {
|
| ... | ... |
@@ -2133,8 +2148,7 @@ |
| 2133 | 2148 |
/// \brief Returns the value associated with a key. |
| 2134 | 2149 |
/// |
| 2135 | 2150 |
/// Returns the value associated with a key. |
| 2136 |
typename MapTraits<ForwardMap>::ReturnValue |
|
| 2137 |
operator[](const Key& e) {
|
|
| 2151 |
ReturnValue operator[](const Key& e) {
|
|
| 2138 | 2152 |
if (Parent::direction(e)) {
|
| 2139 | 2153 |
return (*_forward)[e]; |
| 2140 | 2154 |
} else {
|
| ... | ... |
@@ -2246,18 +2260,9 @@ |
| 2246 | 2260 |
typedef FindEdgeTagIndicator<Graph> FindArcTag; |
| 2247 | 2261 |
Arc findArc(const Node& u, const Node& v, |
| 2248 | 2262 |
const Arc& prev = INVALID) const {
|
| 2249 |
Arc arc = prev; |
|
| 2250 |
bool d = arc == INVALID ? true : (*_direction)[arc]; |
|
| 2251 |
|
|
| 2263 |
Arc arc = _graph->findEdge(u, v, prev); |
|
| 2264 |
while (arc != INVALID && source(arc) != u) {
|
|
| 2252 | 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 | 2267 |
return arc; |
| 2263 | 2268 |
} |
| ... | ... |
@@ -2267,8 +2272,8 @@ |
| 2267 | 2272 |
} |
| 2268 | 2273 |
|
| 2269 | 2274 |
Arc addArc(const Node& u, const Node& v) {
|
| 2270 |
Arc arc = _graph->addArc(u, v); |
|
| 2271 |
_direction->set(arc, _graph->source(arc) == u); |
|
| 2275 |
Arc arc = _graph->addEdge(u, v); |
|
| 2276 |
_direction->set(arc, _graph->u(arc) == u); |
|
| 2272 | 2277 |
return arc; |
| 2273 | 2278 |
} |
| 2274 | 2279 |
|
| ... | ... |
@@ -2912,17 +2917,14 @@ |
| 2912 | 2917 |
typedef True FindArcTag; |
| 2913 | 2918 |
Arc findArc(const Node& u, const Node& v, |
| 2914 | 2919 |
const Arc& prev = INVALID) const {
|
| 2915 |
if (inNode(u)) {
|
|
| 2916 |
if (outNode(v)) {
|
|
| 2917 |
if (static_cast<const DigraphNode&>(u) == |
|
| 2918 |
static_cast<const DigraphNode&>(v) && prev == INVALID) {
|
|
| 2919 |
return Arc(u); |
|
| 2920 |
} |
|
| 2920 |
if (inNode(u) && outNode(v)) {
|
|
| 2921 |
if (static_cast<const DigraphNode&>(u) == |
|
| 2922 |
static_cast<const DigraphNode&>(v) && prev == INVALID) {
|
|
| 2923 |
return Arc(u); |
|
| 2921 | 2924 |
} |
| 2922 |
} else {
|
|
| 2923 |
if (inNode(v)) {
|
|
| 2924 |
return Arc(::lemon::findArc(*_digraph, u, v, prev)); |
|
| 2925 |
} |
|
| 2925 |
} |
|
| 2926 |
else if (outNode(u) && inNode(v)) {
|
|
| 2927 |
return Arc(::lemon::findArc(*_digraph, u, v, prev)); |
|
| 2926 | 2928 |
} |
| 2927 | 2929 |
return INVALID; |
| 2928 | 2930 |
} |
| ... | ... |
@@ -2936,6 +2938,11 @@ |
| 2936 | 2938 |
public: |
| 2937 | 2939 |
typedef Node Key; |
| 2938 | 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 | 2947 |
NodeMapBase(const Adaptor& adaptor) |
| 2941 | 2948 |
: _in_map(*adaptor._digraph), _out_map(*adaptor._digraph) {}
|
| ... | ... |
@@ -2948,14 +2955,12 @@ |
| 2948 | 2955 |
else {_out_map.set(key, val); }
|
| 2949 | 2956 |
} |
| 2950 | 2957 |
|
| 2951 |
typename MapTraits<NodeImpl>::ReturnValue |
|
| 2952 |
operator[](const Node& key) {
|
|
| 2958 |
ReturnValue operator[](const Node& key) {
|
|
| 2953 | 2959 |
if (Adaptor::inNode(key)) { return _in_map[key]; }
|
| 2954 | 2960 |
else { return _out_map[key]; }
|
| 2955 | 2961 |
} |
| 2956 | 2962 |
|
| 2957 |
typename MapTraits<NodeImpl>::ConstReturnValue |
|
| 2958 |
operator[](const Node& key) const {
|
|
| 2963 |
ConstReturnValue operator[](const Node& key) const {
|
|
| 2959 | 2964 |
if (Adaptor::inNode(key)) { return _in_map[key]; }
|
| 2960 | 2965 |
else { return _out_map[key]; }
|
| 2961 | 2966 |
} |
| ... | ... |
@@ -2972,6 +2977,11 @@ |
| 2972 | 2977 |
public: |
| 2973 | 2978 |
typedef Arc Key; |
| 2974 | 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 | 2986 |
ArcMapBase(const Adaptor& adaptor) |
| 2977 | 2987 |
: _arc_map(*adaptor._digraph), _node_map(*adaptor._digraph) {}
|
| ... | ... |
@@ -2987,8 +2997,7 @@ |
| 2987 | 2997 |
} |
| 2988 | 2998 |
} |
| 2989 | 2999 |
|
| 2990 |
typename MapTraits<ArcImpl>::ReturnValue |
|
| 2991 |
operator[](const Arc& key) {
|
|
| 3000 |
ReturnValue operator[](const Arc& key) {
|
|
| 2992 | 3001 |
if (Adaptor::origArc(key)) {
|
| 2993 | 3002 |
return _arc_map[key._item.first()]; |
| 2994 | 3003 |
} else {
|
| ... | ... |
@@ -2996,8 +3005,7 @@ |
| 2996 | 3005 |
} |
| 2997 | 3006 |
} |
| 2998 | 3007 |
|
| 2999 |
typename MapTraits<ArcImpl>::ConstReturnValue |
|
| 3000 |
operator[](const Arc& key) const {
|
|
| 3008 |
ConstReturnValue operator[](const Arc& key) const {
|
|
| 3001 | 3009 |
if (Adaptor::origArc(key)) {
|
| 3002 | 3010 |
return _arc_map[key._item.first()]; |
| 3003 | 3011 |
} else {
|
| ... | ... |
@@ -3184,6 +3192,12 @@ |
| 3184 | 3192 |
typedef Node Key; |
| 3185 | 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 | 3201 |
/// \brief Constructor |
| 3188 | 3202 |
/// |
| 3189 | 3203 |
/// Constructor. |
| ... | ... |
@@ -3270,6 +3284,17 @@ |
| 3270 | 3284 |
typedef Arc Key; |
| 3271 | 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 | 3298 |
/// \brief Constructor |
| 3274 | 3299 |
/// |
| 3275 | 3300 |
/// Constructor. |
0 comments (0 inline)