r469:d369e885d196
Fri, 12 Dec 2008 22:00:03
[Not Reviewed]
0 comments (0 inline)
0
1
0
33
20
| ... | ... |
@@ -61,28 +61,28 @@ |
| 61 | 61 |
|
| 62 | 62 |
void next(Node& i) const { _digraph->next(i); }
|
| 63 | 63 |
void next(Arc& i) const { _digraph->next(i); }
|
| 64 | 64 |
void nextIn(Arc& i) const { _digraph->nextIn(i); }
|
| 65 | 65 |
void nextOut(Arc& i) const { _digraph->nextOut(i); }
|
| 66 | 66 |
|
| 67 | 67 |
Node source(const Arc& a) const { return _digraph->source(a); }
|
| 68 | 68 |
Node target(const Arc& a) const { return _digraph->target(a); }
|
| 69 | 69 |
|
| 70 | 70 |
typedef NodeNumTagIndicator<Digraph> NodeNumTag; |
| 71 | 71 |
int nodeNum() const { return _digraph->nodeNum(); }
|
| 72 | 72 |
|
| 73 |
typedef |
|
| 73 |
typedef ArcNumTagIndicator<Digraph> ArcNumTag; |
|
| 74 | 74 |
int arcNum() const { return _digraph->arcNum(); }
|
| 75 | 75 |
|
| 76 |
typedef |
|
| 76 |
typedef FindArcTagIndicator<Digraph> FindArcTag; |
|
| 77 | 77 |
Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) {
|
| 78 | 78 |
return _digraph->findArc(u, v, prev); |
| 79 | 79 |
} |
| 80 | 80 |
|
| 81 | 81 |
Node addNode() { return _digraph->addNode(); }
|
| 82 | 82 |
Arc addArc(const Node& u, const Node& v) { return _digraph->addArc(u, v); }
|
| 83 | 83 |
|
| 84 | 84 |
void erase(const Node& n) const { _digraph->erase(n); }
|
| 85 | 85 |
void erase(const Arc& a) const { _digraph->erase(a); }
|
| 86 | 86 |
|
| 87 | 87 |
void clear() const { _digraph->clear(); }
|
| 88 | 88 |
|
| ... | ... |
@@ -189,32 +189,36 @@ |
| 189 | 189 |
void nextOut(Arc& i) const { _graph->nextOut(i); }
|
| 190 | 190 |
void nextInc(Edge &i, bool &d) const { _graph->nextInc(i, d); }
|
| 191 | 191 |
|
| 192 | 192 |
Node u(const Edge& e) const { return _graph->u(e); }
|
| 193 | 193 |
Node v(const Edge& e) const { return _graph->v(e); }
|
| 194 | 194 |
|
| 195 | 195 |
Node source(const Arc& a) const { return _graph->source(a); }
|
| 196 | 196 |
Node target(const Arc& a) const { return _graph->target(a); }
|
| 197 | 197 |
|
| 198 | 198 |
typedef NodeNumTagIndicator<Graph> NodeNumTag; |
| 199 | 199 |
int nodeNum() const { return _graph->nodeNum(); }
|
| 200 | 200 |
|
| 201 |
typedef ArcNumTagIndicator<Graph> ArcNumTag; |
|
| 202 |
int arcNum() const { return _graph->arcNum(); }
|
|
| 203 |
|
|
| 201 | 204 |
typedef EdgeNumTagIndicator<Graph> EdgeNumTag; |
| 202 |
int arcNum() const { return _graph->arcNum(); }
|
|
| 203 | 205 |
int edgeNum() const { return _graph->edgeNum(); }
|
| 204 | 206 |
|
| 205 |
typedef |
|
| 207 |
typedef FindArcTagIndicator<Graph> FindArcTag; |
|
| 206 | 208 |
Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) {
|
| 207 | 209 |
return _graph->findArc(u, v, prev); |
| 208 | 210 |
} |
| 211 |
|
|
| 212 |
typedef FindEdgeTagIndicator<Graph> FindEdgeTag; |
|
| 209 | 213 |
Edge findEdge(const Node& u, const Node& v, const Edge& prev = INVALID) {
|
| 210 | 214 |
return _graph->findEdge(u, v, prev); |
| 211 | 215 |
} |
| 212 | 216 |
|
| 213 | 217 |
Node addNode() { return _graph->addNode(); }
|
| 214 | 218 |
Edge addEdge(const Node& u, const Node& v) { return _graph->addEdge(u, v); }
|
| 215 | 219 |
|
| 216 | 220 |
void erase(const Node& i) { _graph->erase(i); }
|
| 217 | 221 |
void erase(const Edge& i) { _graph->erase(i); }
|
| 218 | 222 |
|
| 219 | 223 |
void clear() { _graph->clear(); }
|
| 220 | 224 |
|
| ... | ... |
@@ -321,25 +325,25 @@ |
| 321 | 325 |
|
| 322 | 326 |
void firstIn(Arc& a, const Node& n) const { Parent::firstOut(a, n); }
|
| 323 | 327 |
void firstOut(Arc& a, const Node& n ) const { Parent::firstIn(a, n); }
|
| 324 | 328 |
|
| 325 | 329 |
void nextIn(Arc& a) const { Parent::nextOut(a); }
|
| 326 | 330 |
void nextOut(Arc& a) const { Parent::nextIn(a); }
|
| 327 | 331 |
|
| 328 | 332 |
Node source(const Arc& a) const { return Parent::target(a); }
|
| 329 | 333 |
Node target(const Arc& a) const { return Parent::source(a); }
|
| 330 | 334 |
|
| 331 | 335 |
Arc addArc(const Node& u, const Node& v) { return Parent::addArc(v, u); }
|
| 332 | 336 |
|
| 333 |
typedef |
|
| 337 |
typedef FindArcTagIndicator<Digraph> FindArcTag; |
|
| 334 | 338 |
Arc findArc(const Node& u, const Node& v, |
| 335 | 339 |
const Arc& prev = INVALID) {
|
| 336 | 340 |
return Parent::findArc(v, u, prev); |
| 337 | 341 |
} |
| 338 | 342 |
|
| 339 | 343 |
}; |
| 340 | 344 |
|
| 341 | 345 |
/// \ingroup graph_adaptors |
| 342 | 346 |
/// |
| 343 | 347 |
/// \brief A digraph adaptor which reverses the orientation of the arcs. |
| 344 | 348 |
/// |
| 345 | 349 |
/// ReverseDigraph reverses the arcs in the adapted digraph. The |
| ... | ... |
@@ -458,27 +462,27 @@ |
| 458 | 462 |
} |
| 459 | 463 |
|
| 460 | 464 |
void hide(const Node& n) const { _node_filter->set(n, false); }
|
| 461 | 465 |
void hide(const Arc& a) const { _arc_filter->set(a, false); }
|
| 462 | 466 |
|
| 463 | 467 |
void unHide(const Node& n) const { _node_filter->set(n, true); }
|
| 464 | 468 |
void unHide(const Arc& a) const { _arc_filter->set(a, true); }
|
| 465 | 469 |
|
| 466 | 470 |
bool hidden(const Node& n) const { return !(*_node_filter)[n]; }
|
| 467 | 471 |
bool hidden(const Arc& a) const { return !(*_arc_filter)[a]; }
|
| 468 | 472 |
|
| 469 | 473 |
typedef False NodeNumTag; |
| 470 |
typedef False EdgeNumTag; |
|
| 471 |
|
|
| 472 |
typedef |
|
| 474 |
typedef False ArcNumTag; |
|
| 475 |
|
|
| 476 |
typedef FindArcTagIndicator<Digraph> FindArcTag; |
|
| 473 | 477 |
Arc findArc(const Node& source, const Node& target, |
| 474 | 478 |
const Arc& prev = INVALID) {
|
| 475 | 479 |
if (!(*_node_filter)[source] || !(*_node_filter)[target]) {
|
| 476 | 480 |
return INVALID; |
| 477 | 481 |
} |
| 478 | 482 |
Arc arc = Parent::findArc(source, target, prev); |
| 479 | 483 |
while (arc != INVALID && !(*_arc_filter)[arc]) {
|
| 480 | 484 |
arc = Parent::findArc(source, target, arc); |
| 481 | 485 |
} |
| 482 | 486 |
return arc; |
| 483 | 487 |
} |
| 484 | 488 |
|
| ... | ... |
@@ -601,27 +605,27 @@ |
| 601 | 605 |
} |
| 602 | 606 |
|
| 603 | 607 |
void hide(const Node& n) const { _node_filter->set(n, false); }
|
| 604 | 608 |
void hide(const Arc& e) const { _arc_filter->set(e, false); }
|
| 605 | 609 |
|
| 606 | 610 |
void unHide(const Node& n) const { _node_filter->set(n, true); }
|
| 607 | 611 |
void unHide(const Arc& e) const { _arc_filter->set(e, true); }
|
| 608 | 612 |
|
| 609 | 613 |
bool hidden(const Node& n) const { return !(*_node_filter)[n]; }
|
| 610 | 614 |
bool hidden(const Arc& e) const { return !(*_arc_filter)[e]; }
|
| 611 | 615 |
|
| 612 | 616 |
typedef False NodeNumTag; |
| 613 |
typedef False EdgeNumTag; |
|
| 614 |
|
|
| 615 |
typedef |
|
| 617 |
typedef False ArcNumTag; |
|
| 618 |
|
|
| 619 |
typedef FindArcTagIndicator<Digraph> FindArcTag; |
|
| 616 | 620 |
Arc findArc(const Node& source, const Node& target, |
| 617 | 621 |
const Arc& prev = INVALID) {
|
| 618 | 622 |
if (!(*_node_filter)[source] || !(*_node_filter)[target]) {
|
| 619 | 623 |
return INVALID; |
| 620 | 624 |
} |
| 621 | 625 |
Arc arc = Parent::findArc(source, target, prev); |
| 622 | 626 |
while (arc != INVALID && !(*_arc_filter)[arc]) {
|
| 623 | 627 |
arc = Parent::findArc(source, target, arc); |
| 624 | 628 |
} |
| 625 | 629 |
return arc; |
| 626 | 630 |
} |
| 627 | 631 |
|
| ... | ... |
@@ -926,38 +930,41 @@ |
| 926 | 930 |
} |
| 927 | 931 |
|
| 928 | 932 |
void hide(const Node& n) const { _node_filter_map->set(n, false); }
|
| 929 | 933 |
void hide(const Edge& e) const { _edge_filter_map->set(e, false); }
|
| 930 | 934 |
|
| 931 | 935 |
void unHide(const Node& n) const { _node_filter_map->set(n, true); }
|
| 932 | 936 |
void unHide(const Edge& e) const { _edge_filter_map->set(e, true); }
|
| 933 | 937 |
|
| 934 | 938 |
bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; }
|
| 935 | 939 |
bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; }
|
| 936 | 940 |
|
| 937 | 941 |
typedef False NodeNumTag; |
| 942 |
typedef False ArcNumTag; |
|
| 938 | 943 |
typedef False EdgeNumTag; |
| 939 | 944 |
|
| 940 |
typedef |
|
| 945 |
typedef FindArcTagIndicator<Graph> FindArcTag; |
|
| 941 | 946 |
Arc findArc(const Node& u, const Node& v, |
| 942 | 947 |
const Arc& prev = INVALID) {
|
| 943 | 948 |
if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) {
|
| 944 | 949 |
return INVALID; |
| 945 | 950 |
} |
| 946 | 951 |
Arc arc = Parent::findArc(u, v, prev); |
| 947 | 952 |
while (arc != INVALID && !(*_edge_filter_map)[arc]) {
|
| 948 | 953 |
arc = Parent::findArc(u, v, arc); |
| 949 | 954 |
} |
| 950 | 955 |
return arc; |
| 951 | 956 |
} |
| 957 |
|
|
| 958 |
typedef FindEdgeTagIndicator<Graph> FindEdgeTag; |
|
| 952 | 959 |
Edge findEdge(const Node& u, const Node& v, |
| 953 | 960 |
const Edge& prev = INVALID) {
|
| 954 | 961 |
if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) {
|
| 955 | 962 |
return INVALID; |
| 956 | 963 |
} |
| 957 | 964 |
Edge edge = Parent::findEdge(u, v, prev); |
| 958 | 965 |
while (edge != INVALID && !(*_edge_filter_map)[edge]) {
|
| 959 | 966 |
edge = Parent::findEdge(u, v, edge); |
| 960 | 967 |
} |
| 961 | 968 |
return edge; |
| 962 | 969 |
} |
| 963 | 970 |
|
| ... | ... |
@@ -1122,35 +1129,38 @@ |
| 1122 | 1129 |
} |
| 1123 | 1130 |
|
| 1124 | 1131 |
void hide(const Node& n) const { _node_filter_map->set(n, false); }
|
| 1125 | 1132 |
void hide(const Edge& e) const { _edge_filter_map->set(e, false); }
|
| 1126 | 1133 |
|
| 1127 | 1134 |
void unHide(const Node& n) const { _node_filter_map->set(n, true); }
|
| 1128 | 1135 |
void unHide(const Edge& e) const { _edge_filter_map->set(e, true); }
|
| 1129 | 1136 |
|
| 1130 | 1137 |
bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; }
|
| 1131 | 1138 |
bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; }
|
| 1132 | 1139 |
|
| 1133 | 1140 |
typedef False NodeNumTag; |
| 1141 |
typedef False ArcNumTag; |
|
| 1134 | 1142 |
typedef False EdgeNumTag; |
| 1135 | 1143 |
|
| 1136 |
typedef |
|
| 1144 |
typedef FindArcTagIndicator<Graph> FindArcTag; |
|
| 1137 | 1145 |
Arc findArc(const Node& u, const Node& v, |
| 1138 | 1146 |
const Arc& prev = INVALID) {
|
| 1139 | 1147 |
Arc arc = Parent::findArc(u, v, prev); |
| 1140 | 1148 |
while (arc != INVALID && !(*_edge_filter_map)[arc]) {
|
| 1141 | 1149 |
arc = Parent::findArc(u, v, arc); |
| 1142 | 1150 |
} |
| 1143 | 1151 |
return arc; |
| 1144 | 1152 |
} |
| 1153 |
|
|
| 1154 |
typedef FindEdgeTagIndicator<Graph> FindEdgeTag; |
|
| 1145 | 1155 |
Edge findEdge(const Node& u, const Node& v, |
| 1146 | 1156 |
const Edge& prev = INVALID) {
|
| 1147 | 1157 |
Edge edge = Parent::findEdge(u, v, prev); |
| 1148 | 1158 |
while (edge != INVALID && !(*_edge_filter_map)[edge]) {
|
| 1149 | 1159 |
edge = Parent::findEdge(u, v, edge); |
| 1150 | 1160 |
} |
| 1151 | 1161 |
return edge; |
| 1152 | 1162 |
} |
| 1153 | 1163 |
|
| 1154 | 1164 |
template <typename _Value> |
| 1155 | 1165 |
class NodeMap : public SubMapExtender<Adaptor, |
| 1156 | 1166 |
typename Parent::template NodeMap<_Value> > {
|
| ... | ... |
@@ -1837,47 +1847,51 @@ |
| 1837 | 1847 |
Node addNode() { return _digraph->addNode(); }
|
| 1838 | 1848 |
Edge addEdge(const Node& u, const Node& v) {
|
| 1839 | 1849 |
return _digraph->addArc(u, v); |
| 1840 | 1850 |
} |
| 1841 | 1851 |
|
| 1842 | 1852 |
void erase(const Node& i) { _digraph->erase(i); }
|
| 1843 | 1853 |
void erase(const Edge& i) { _digraph->erase(i); }
|
| 1844 | 1854 |
|
| 1845 | 1855 |
void clear() { _digraph->clear(); }
|
| 1846 | 1856 |
|
| 1847 | 1857 |
typedef NodeNumTagIndicator<Digraph> NodeNumTag; |
| 1848 | 1858 |
int nodeNum() const { return 2 * _digraph->arcNum(); }
|
| 1849 |
|
|
| 1859 |
|
|
| 1860 |
typedef ArcNumTagIndicator<Digraph> ArcNumTag; |
|
| 1850 | 1861 |
int arcNum() const { return 2 * _digraph->arcNum(); }
|
| 1862 |
|
|
| 1863 |
typedef ArcNumTag EdgeNumTag; |
|
| 1851 | 1864 |
int edgeNum() const { return _digraph->arcNum(); }
|
| 1852 | 1865 |
|
| 1853 |
typedef |
|
| 1866 |
typedef FindArcTagIndicator<Digraph> FindArcTag; |
|
| 1854 | 1867 |
Arc findArc(Node s, Node t, Arc p = INVALID) const {
|
| 1855 | 1868 |
if (p == INVALID) {
|
| 1856 | 1869 |
Edge arc = _digraph->findArc(s, t); |
| 1857 | 1870 |
if (arc != INVALID) return direct(arc, true); |
| 1858 | 1871 |
arc = _digraph->findArc(t, s); |
| 1859 | 1872 |
if (arc != INVALID) return direct(arc, false); |
| 1860 | 1873 |
} else if (direction(p)) {
|
| 1861 | 1874 |
Edge arc = _digraph->findArc(s, t, p); |
| 1862 | 1875 |
if (arc != INVALID) return direct(arc, true); |
| 1863 | 1876 |
arc = _digraph->findArc(t, s); |
| 1864 | 1877 |
if (arc != INVALID) return direct(arc, false); |
| 1865 | 1878 |
} else {
|
| 1866 | 1879 |
Edge arc = _digraph->findArc(t, s, p); |
| 1867 | 1880 |
if (arc != INVALID) return direct(arc, false); |
| 1868 | 1881 |
} |
| 1869 | 1882 |
return INVALID; |
| 1870 | 1883 |
} |
| 1871 | 1884 |
|
| 1885 |
typedef FindArcTag FindEdgeTag; |
|
| 1872 | 1886 |
Edge findEdge(Node s, Node t, Edge p = INVALID) const {
|
| 1873 | 1887 |
if (s != t) {
|
| 1874 | 1888 |
if (p == INVALID) {
|
| 1875 | 1889 |
Edge arc = _digraph->findArc(s, t); |
| 1876 | 1890 |
if (arc != INVALID) return arc; |
| 1877 | 1891 |
arc = _digraph->findArc(t, s); |
| 1878 | 1892 |
if (arc != INVALID) return arc; |
| 1879 | 1893 |
} else if (_digraph->s(p) == s) {
|
| 1880 | 1894 |
Edge arc = _digraph->findArc(s, t, p); |
| 1881 | 1895 |
if (arc != INVALID) return arc; |
| 1882 | 1896 |
arc = _digraph->findArc(t, s); |
| 1883 | 1897 |
if (arc != INVALID) return arc; |
| ... | ... |
@@ -2215,28 +2229,28 @@ |
| 2215 | 2229 |
} |
| 2216 | 2230 |
|
| 2217 | 2231 |
Node source(const Arc& e) const {
|
| 2218 | 2232 |
return (*_direction)[e] ? _graph->u(e) : _graph->v(e); |
| 2219 | 2233 |
} |
| 2220 | 2234 |
Node target(const Arc& e) const {
|
| 2221 | 2235 |
return (*_direction)[e] ? _graph->v(e) : _graph->u(e); |
| 2222 | 2236 |
} |
| 2223 | 2237 |
|
| 2224 | 2238 |
typedef NodeNumTagIndicator<Graph> NodeNumTag; |
| 2225 | 2239 |
int nodeNum() const { return _graph->nodeNum(); }
|
| 2226 | 2240 |
|
| 2227 |
typedef EdgeNumTagIndicator<Graph> |
|
| 2241 |
typedef EdgeNumTagIndicator<Graph> ArcNumTag; |
|
| 2228 | 2242 |
int arcNum() const { return _graph->edgeNum(); }
|
| 2229 | 2243 |
|
| 2230 |
typedef FindEdgeTagIndicator<Graph> |
|
| 2244 |
typedef FindEdgeTagIndicator<Graph> FindArcTag; |
|
| 2231 | 2245 |
Arc findArc(const Node& u, const Node& v, |
| 2232 | 2246 |
const Arc& prev = INVALID) {
|
| 2233 | 2247 |
Arc arc = prev; |
| 2234 | 2248 |
bool d = arc == INVALID ? true : (*_direction)[arc]; |
| 2235 | 2249 |
if (d) {
|
| 2236 | 2250 |
arc = _graph->findEdge(u, v, arc); |
| 2237 | 2251 |
while (arc != INVALID && !(*_direction)[arc]) {
|
| 2238 | 2252 |
_graph->findEdge(u, v, arc); |
| 2239 | 2253 |
} |
| 2240 | 2254 |
if (arc != INVALID) return arc; |
| 2241 | 2255 |
} |
| 2242 | 2256 |
_graph->findEdge(v, u, arc); |
| ... | ... |
@@ -2875,35 +2889,34 @@ |
| 2875 | 2889 |
return Node(n, false); |
| 2876 | 2890 |
} |
| 2877 | 2891 |
|
| 2878 | 2892 |
static Arc arc(const DigraphNode& n) {
|
| 2879 | 2893 |
return Arc(n); |
| 2880 | 2894 |
} |
| 2881 | 2895 |
|
| 2882 | 2896 |
static Arc arc(const DigraphArc& e) {
|
| 2883 | 2897 |
return Arc(e); |
| 2884 | 2898 |
} |
| 2885 | 2899 |
|
| 2886 | 2900 |
typedef True NodeNumTag; |
| 2887 |
|
|
| 2888 | 2901 |
int nodeNum() const {
|
| 2889 | 2902 |
return 2 * countNodes(*_digraph); |
| 2890 | 2903 |
} |
| 2891 | 2904 |
|
| 2892 |
typedef True |
|
| 2905 |
typedef True ArcNumTag; |
|
| 2893 | 2906 |
int arcNum() const {
|
| 2894 | 2907 |
return countArcs(*_digraph) + countNodes(*_digraph); |
| 2895 | 2908 |
} |
| 2896 | 2909 |
|
| 2897 |
typedef True |
|
| 2910 |
typedef True FindArcTag; |
|
| 2898 | 2911 |
Arc findArc(const Node& u, const Node& v, |
| 2899 | 2912 |
const Arc& prev = INVALID) const {
|
| 2900 | 2913 |
if (inNode(u)) {
|
| 2901 | 2914 |
if (outNode(v)) {
|
| 2902 | 2915 |
if (static_cast<const DigraphNode&>(u) == |
| 2903 | 2916 |
static_cast<const DigraphNode&>(v) && prev == INVALID) {
|
| 2904 | 2917 |
return Arc(u); |
| 2905 | 2918 |
} |
| 2906 | 2919 |
} |
| 2907 | 2920 |
} else {
|
| 2908 | 2921 |
if (inNode(v)) {
|
| 2909 | 2922 |
return Arc(::lemon::findArc(*_digraph, u, v, prev)); |
0 comments (0 inline)