r632:65fbcf2f978a
Wed, 15 Apr 2009 03:26:45
[Not Reviewed]
0 comments (0 inline)
0
5
0
49
10
44
9
21
15
| ... | ... |
@@ -29,99 +29,138 @@ |
| 29 | 29 |
using namespace lemon; |
| 30 | 30 |
|
| 31 | 31 |
char test_lgf[] = |
| 32 | 32 |
"@nodes\n" |
| 33 | 33 |
"label\n" |
| 34 | 34 |
"0\n" |
| 35 | 35 |
"1\n" |
| 36 | 36 |
"2\n" |
| 37 | 37 |
"3\n" |
| 38 | 38 |
"4\n" |
| 39 | 39 |
"5\n" |
| 40 | 40 |
"@arcs\n" |
| 41 | 41 |
" label\n" |
| 42 | 42 |
"0 1 0\n" |
| 43 | 43 |
"1 2 1\n" |
| 44 | 44 |
"2 3 2\n" |
| 45 | 45 |
"3 4 3\n" |
| 46 | 46 |
"0 3 4\n" |
| 47 | 47 |
"0 3 5\n" |
| 48 | 48 |
"5 2 6\n" |
| 49 | 49 |
"@attributes\n" |
| 50 | 50 |
"source 0\n" |
| 51 | 51 |
"target 4\n"; |
| 52 | 52 |
|
| 53 | 53 |
void checkBfsCompile() |
| 54 | 54 |
{
|
| 55 | 55 |
typedef concepts::Digraph Digraph; |
| 56 | 56 |
typedef Bfs<Digraph> BType; |
| 57 | 57 |
typedef Digraph::Node Node; |
| 58 | 58 |
typedef Digraph::Arc Arc; |
| 59 | 59 |
|
| 60 | 60 |
Digraph G; |
| 61 |
Node s, t; |
|
| 61 |
Node s, t, n; |
|
| 62 | 62 |
Arc e; |
| 63 |
int l; |
|
| 63 |
int l, i; |
|
| 64 | 64 |
bool b; |
| 65 | 65 |
BType::DistMap d(G); |
| 66 | 66 |
BType::PredMap p(G); |
| 67 | 67 |
Path<Digraph> pp; |
| 68 |
concepts::ReadMap<Node,bool> nm; |
|
| 68 | 69 |
|
| 69 | 70 |
{
|
| 70 | 71 |
BType bfs_test(G); |
| 72 |
const BType& const_bfs_test = bfs_test; |
|
| 71 | 73 |
|
| 72 | 74 |
bfs_test.run(s); |
| 73 | 75 |
bfs_test.run(s,t); |
| 74 | 76 |
bfs_test.run(); |
| 75 | 77 |
|
| 76 |
l = bfs_test.dist(t); |
|
| 77 |
e = bfs_test.predArc(t); |
|
| 78 |
s = bfs_test.predNode(t); |
|
| 79 |
b = bfs_test.reached(t); |
|
| 80 |
d = bfs_test.distMap(); |
|
| 81 |
p = bfs_test.predMap(); |
|
| 82 |
|
|
| 78 |
bfs_test.init(); |
|
| 79 |
bfs_test.addSource(s); |
|
| 80 |
n = bfs_test.processNextNode(); |
|
| 81 |
n = bfs_test.processNextNode(t, b); |
|
| 82 |
n = bfs_test.processNextNode(nm, n); |
|
| 83 |
n = const_bfs_test.nextNode(); |
|
| 84 |
b = const_bfs_test.emptyQueue(); |
|
| 85 |
i = const_bfs_test.queueSize(); |
|
| 86 |
|
|
| 87 |
bfs_test.start(); |
|
| 88 |
bfs_test.start(t); |
|
| 89 |
bfs_test.start(nm); |
|
| 90 |
|
|
| 91 |
l = const_bfs_test.dist(t); |
|
| 92 |
e = const_bfs_test.predArc(t); |
|
| 93 |
s = const_bfs_test.predNode(t); |
|
| 94 |
b = const_bfs_test.reached(t); |
|
| 95 |
d = const_bfs_test.distMap(); |
|
| 96 |
p = const_bfs_test.predMap(); |
|
| 97 |
pp = const_bfs_test.path(t); |
|
| 83 | 98 |
} |
| 84 | 99 |
{
|
| 85 | 100 |
BType |
| 86 | 101 |
::SetPredMap<concepts::ReadWriteMap<Node,Arc> > |
| 87 | 102 |
::SetDistMap<concepts::ReadWriteMap<Node,int> > |
| 88 | 103 |
::SetReachedMap<concepts::ReadWriteMap<Node,bool> > |
| 104 |
::SetStandardProcessedMap |
|
| 89 | 105 |
::SetProcessedMap<concepts::WriteMap<Node,bool> > |
| 90 |
::SetStandardProcessedMap |
|
| 91 | 106 |
::Create bfs_test(G); |
| 107 |
|
|
| 108 |
concepts::ReadWriteMap<Node,Arc> pred_map; |
|
| 109 |
concepts::ReadWriteMap<Node,int> dist_map; |
|
| 110 |
concepts::ReadWriteMap<Node,bool> reached_map; |
|
| 111 |
concepts::WriteMap<Node,bool> processed_map; |
|
| 112 |
|
|
| 113 |
bfs_test |
|
| 114 |
.predMap(pred_map) |
|
| 115 |
.distMap(dist_map) |
|
| 116 |
.reachedMap(reached_map) |
|
| 117 |
.processedMap(processed_map); |
|
| 92 | 118 |
|
| 93 | 119 |
bfs_test.run(s); |
| 94 | 120 |
bfs_test.run(s,t); |
| 95 | 121 |
bfs_test.run(); |
| 122 |
|
|
| 123 |
bfs_test.init(); |
|
| 124 |
bfs_test.addSource(s); |
|
| 125 |
n = bfs_test.processNextNode(); |
|
| 126 |
n = bfs_test.processNextNode(t, b); |
|
| 127 |
n = bfs_test.processNextNode(nm, n); |
|
| 128 |
n = bfs_test.nextNode(); |
|
| 129 |
b = bfs_test.emptyQueue(); |
|
| 130 |
i = bfs_test.queueSize(); |
|
| 131 |
|
|
| 132 |
bfs_test.start(); |
|
| 133 |
bfs_test.start(t); |
|
| 134 |
bfs_test.start(nm); |
|
| 96 | 135 |
|
| 97 | 136 |
l = bfs_test.dist(t); |
| 98 | 137 |
e = bfs_test.predArc(t); |
| 99 | 138 |
s = bfs_test.predNode(t); |
| 100 | 139 |
b = bfs_test.reached(t); |
| 101 | 140 |
pp = bfs_test.path(t); |
| 102 | 141 |
} |
| 103 | 142 |
} |
| 104 | 143 |
|
| 105 | 144 |
void checkBfsFunctionCompile() |
| 106 | 145 |
{
|
| 107 | 146 |
typedef int VType; |
| 108 | 147 |
typedef concepts::Digraph Digraph; |
| 109 | 148 |
typedef Digraph::Arc Arc; |
| 110 | 149 |
typedef Digraph::Node Node; |
| 111 | 150 |
|
| 112 | 151 |
Digraph g; |
| 113 | 152 |
bool b; |
| 114 | 153 |
bfs(g).run(Node()); |
| 115 | 154 |
b=bfs(g).run(Node(),Node()); |
| 116 | 155 |
bfs(g).run(); |
| 117 | 156 |
bfs(g) |
| 118 | 157 |
.predMap(concepts::ReadWriteMap<Node,Arc>()) |
| 119 | 158 |
.distMap(concepts::ReadWriteMap<Node,VType>()) |
| 120 | 159 |
.reachedMap(concepts::ReadWriteMap<Node,bool>()) |
| 121 | 160 |
.processedMap(concepts::WriteMap<Node,bool>()) |
| 122 | 161 |
.run(Node()); |
| 123 | 162 |
b=bfs(g) |
| 124 | 163 |
.predMap(concepts::ReadWriteMap<Node,Arc>()) |
| 125 | 164 |
.distMap(concepts::ReadWriteMap<Node,VType>()) |
| 126 | 165 |
.reachedMap(concepts::ReadWriteMap<Node,bool>()) |
| 127 | 166 |
.processedMap(concepts::WriteMap<Node,bool>()) |
| ... | ... |
@@ -42,85 +42,92 @@ |
| 42 | 42 |
"0 2 2 6\n" |
| 43 | 43 |
"1 3 4 7\n" |
| 44 | 44 |
"1 4 0 5\n" |
| 45 | 45 |
"2 4 1 3\n" |
| 46 | 46 |
"3 5 3 8\n" |
| 47 | 47 |
"4 5 3 7\n" |
| 48 | 48 |
"@attributes\n" |
| 49 | 49 |
"source 0\n" |
| 50 | 50 |
"sink 5\n"; |
| 51 | 51 |
|
| 52 | 52 |
void checkCirculationCompile() |
| 53 | 53 |
{
|
| 54 | 54 |
typedef int VType; |
| 55 | 55 |
typedef concepts::Digraph Digraph; |
| 56 | 56 |
|
| 57 | 57 |
typedef Digraph::Node Node; |
| 58 | 58 |
typedef Digraph::Arc Arc; |
| 59 | 59 |
typedef concepts::ReadMap<Arc,VType> CapMap; |
| 60 | 60 |
typedef concepts::ReadMap<Node,VType> DeltaMap; |
| 61 | 61 |
typedef concepts::ReadWriteMap<Arc,VType> FlowMap; |
| 62 | 62 |
typedef concepts::WriteMap<Node,bool> BarrierMap; |
| 63 | 63 |
|
| 64 | 64 |
typedef Elevator<Digraph, Digraph::Node> Elev; |
| 65 | 65 |
typedef LinkedElevator<Digraph, Digraph::Node> LinkedElev; |
| 66 | 66 |
|
| 67 | 67 |
Digraph g; |
| 68 | 68 |
Node n; |
| 69 | 69 |
Arc a; |
| 70 | 70 |
CapMap lcap, ucap; |
| 71 | 71 |
DeltaMap delta; |
| 72 | 72 |
FlowMap flow; |
| 73 | 73 |
BarrierMap bar; |
| 74 |
VType v; |
|
| 75 |
bool b; |
|
| 74 | 76 |
|
| 75 |
Circulation<Digraph, CapMap, CapMap, DeltaMap> |
|
| 76 |
::SetFlowMap<FlowMap> |
|
| 77 |
::SetElevator<Elev> |
|
| 78 |
::SetStandardElevator<LinkedElev> |
|
| 79 |
::Create circ_test(g,lcap,ucap,delta); |
|
| 80 |
|
|
| 81 |
circ_test.lowerCapMap(lcap); |
|
| 82 |
circ_test.upperCapMap(ucap); |
|
| 83 |
circ_test.deltaMap(delta); |
|
| 84 |
flow = circ_test.flowMap(); |
|
| 85 |
|
|
| 77 |
typedef Circulation<Digraph, CapMap, CapMap, DeltaMap> |
|
| 78 |
::SetFlowMap<FlowMap> |
|
| 79 |
::SetElevator<Elev> |
|
| 80 |
::SetStandardElevator<LinkedElev> |
|
| 81 |
::Create CirculationType; |
|
| 82 |
CirculationType circ_test(g, lcap, ucap, delta); |
|
| 83 |
const CirculationType& const_circ_test = circ_test; |
|
| 84 |
|
|
| 85 |
circ_test |
|
| 86 |
.lowerCapMap(lcap) |
|
| 87 |
.upperCapMap(ucap) |
|
| 88 |
.deltaMap(delta) |
|
| 89 |
.flowMap(flow); |
|
| 86 | 90 |
|
| 87 | 91 |
circ_test.init(); |
| 88 | 92 |
circ_test.greedyInit(); |
| 89 | 93 |
circ_test.start(); |
| 90 | 94 |
circ_test.run(); |
| 91 | 95 |
|
| 92 |
circ_test.barrier(n); |
|
| 93 |
circ_test.barrierMap(bar); |
|
| 94 |
|
|
| 96 |
v = const_circ_test.flow(a); |
|
| 97 |
const FlowMap& fm = const_circ_test.flowMap(); |
|
| 98 |
b = const_circ_test.barrier(n); |
|
| 99 |
const_circ_test.barrierMap(bar); |
|
| 100 |
|
|
| 101 |
ignore_unused_variable_warning(fm); |
|
| 95 | 102 |
} |
| 96 | 103 |
|
| 97 | 104 |
template <class G, class LM, class UM, class DM> |
| 98 | 105 |
void checkCirculation(const G& g, const LM& lm, const UM& um, |
| 99 | 106 |
const DM& dm, bool find) |
| 100 | 107 |
{
|
| 101 | 108 |
Circulation<G, LM, UM, DM> circ(g, lm, um, dm); |
| 102 | 109 |
bool ret = circ.run(); |
| 103 | 110 |
if (find) {
|
| 104 | 111 |
check(ret, "A feasible solution should have been found."); |
| 105 | 112 |
check(circ.checkFlow(), "The found flow is corrupt."); |
| 106 | 113 |
check(!circ.checkBarrier(), "A barrier should not have been found."); |
| 107 | 114 |
} else {
|
| 108 | 115 |
check(!ret, "A feasible solution should not have been found."); |
| 109 | 116 |
check(circ.checkBarrier(), "The found barrier is corrupt."); |
| 110 | 117 |
} |
| 111 | 118 |
} |
| 112 | 119 |
|
| 113 | 120 |
int main (int, char*[]) |
| 114 | 121 |
{
|
| 115 | 122 |
typedef ListDigraph Digraph; |
| 116 | 123 |
DIGRAPH_TYPEDEFS(Digraph); |
| 117 | 124 |
|
| 118 | 125 |
Digraph g; |
| 119 | 126 |
IntArcMap lo(g), up(g); |
| 120 | 127 |
IntNodeMap delta(g, 0); |
| 121 | 128 |
Node s, t; |
| 122 | 129 |
|
| 123 | 130 |
std::istringstream input(test_lgf); |
| 124 | 131 |
DigraphReader<Digraph>(g,input). |
| 125 | 132 |
arcMap("lcap", lo).
|
| 126 | 133 |
arcMap("ucap", up).
|
| ... | ... |
@@ -33,97 +33,132 @@ |
| 33 | 33 |
"label\n" |
| 34 | 34 |
"0\n" |
| 35 | 35 |
"1\n" |
| 36 | 36 |
"2\n" |
| 37 | 37 |
"3\n" |
| 38 | 38 |
"4\n" |
| 39 | 39 |
"5\n" |
| 40 | 40 |
"6\n" |
| 41 | 41 |
"@arcs\n" |
| 42 | 42 |
" label\n" |
| 43 | 43 |
"0 1 0\n" |
| 44 | 44 |
"1 2 1\n" |
| 45 | 45 |
"2 3 2\n" |
| 46 | 46 |
"1 4 3\n" |
| 47 | 47 |
"4 2 4\n" |
| 48 | 48 |
"4 5 5\n" |
| 49 | 49 |
"5 0 6\n" |
| 50 | 50 |
"6 3 7\n" |
| 51 | 51 |
"@attributes\n" |
| 52 | 52 |
"source 0\n" |
| 53 | 53 |
"target 5\n"; |
| 54 | 54 |
|
| 55 | 55 |
void checkDfsCompile() |
| 56 | 56 |
{
|
| 57 | 57 |
typedef concepts::Digraph Digraph; |
| 58 | 58 |
typedef Dfs<Digraph> DType; |
| 59 | 59 |
typedef Digraph::Node Node; |
| 60 | 60 |
typedef Digraph::Arc Arc; |
| 61 | 61 |
|
| 62 | 62 |
Digraph G; |
| 63 | 63 |
Node s, t; |
| 64 | 64 |
Arc e; |
| 65 |
int l; |
|
| 65 |
int l, i; |
|
| 66 | 66 |
bool b; |
| 67 | 67 |
DType::DistMap d(G); |
| 68 | 68 |
DType::PredMap p(G); |
| 69 | 69 |
Path<Digraph> pp; |
| 70 |
concepts::ReadMap<Arc,bool> am; |
|
| 70 | 71 |
|
| 71 | 72 |
{
|
| 72 | 73 |
DType dfs_test(G); |
| 74 |
const DType& const_dfs_test = dfs_test; |
|
| 73 | 75 |
|
| 74 | 76 |
dfs_test.run(s); |
| 75 | 77 |
dfs_test.run(s,t); |
| 76 | 78 |
dfs_test.run(); |
| 77 | 79 |
|
| 78 |
l = dfs_test.dist(t); |
|
| 79 |
e = dfs_test.predArc(t); |
|
| 80 |
s = dfs_test.predNode(t); |
|
| 81 |
b = dfs_test.reached(t); |
|
| 82 |
d = dfs_test.distMap(); |
|
| 83 |
p = dfs_test.predMap(); |
|
| 84 |
|
|
| 80 |
dfs_test.init(); |
|
| 81 |
dfs_test.addSource(s); |
|
| 82 |
e = dfs_test.processNextArc(); |
|
| 83 |
e = const_dfs_test.nextArc(); |
|
| 84 |
b = const_dfs_test.emptyQueue(); |
|
| 85 |
i = const_dfs_test.queueSize(); |
|
| 86 |
|
|
| 87 |
dfs_test.start(); |
|
| 88 |
dfs_test.start(t); |
|
| 89 |
dfs_test.start(am); |
|
| 90 |
|
|
| 91 |
l = const_dfs_test.dist(t); |
|
| 92 |
e = const_dfs_test.predArc(t); |
|
| 93 |
s = const_dfs_test.predNode(t); |
|
| 94 |
b = const_dfs_test.reached(t); |
|
| 95 |
d = const_dfs_test.distMap(); |
|
| 96 |
p = const_dfs_test.predMap(); |
|
| 97 |
pp = const_dfs_test.path(t); |
|
| 85 | 98 |
} |
| 86 | 99 |
{
|
| 87 | 100 |
DType |
| 88 | 101 |
::SetPredMap<concepts::ReadWriteMap<Node,Arc> > |
| 89 | 102 |
::SetDistMap<concepts::ReadWriteMap<Node,int> > |
| 90 | 103 |
::SetReachedMap<concepts::ReadWriteMap<Node,bool> > |
| 104 |
::SetStandardProcessedMap |
|
| 91 | 105 |
::SetProcessedMap<concepts::WriteMap<Node,bool> > |
| 92 |
::SetStandardProcessedMap |
|
| 93 | 106 |
::Create dfs_test(G); |
| 94 | 107 |
|
| 108 |
concepts::ReadWriteMap<Node,Arc> pred_map; |
|
| 109 |
concepts::ReadWriteMap<Node,int> dist_map; |
|
| 110 |
concepts::ReadWriteMap<Node,bool> reached_map; |
|
| 111 |
concepts::WriteMap<Node,bool> processed_map; |
|
| 112 |
|
|
| 113 |
dfs_test |
|
| 114 |
.predMap(pred_map) |
|
| 115 |
.distMap(dist_map) |
|
| 116 |
.reachedMap(reached_map) |
|
| 117 |
.processedMap(processed_map); |
|
| 118 |
|
|
| 95 | 119 |
dfs_test.run(s); |
| 96 | 120 |
dfs_test.run(s,t); |
| 97 | 121 |
dfs_test.run(); |
| 122 |
dfs_test.init(); |
|
| 123 |
|
|
| 124 |
dfs_test.addSource(s); |
|
| 125 |
e = dfs_test.processNextArc(); |
|
| 126 |
e = dfs_test.nextArc(); |
|
| 127 |
b = dfs_test.emptyQueue(); |
|
| 128 |
i = dfs_test.queueSize(); |
|
| 129 |
|
|
| 130 |
dfs_test.start(); |
|
| 131 |
dfs_test.start(t); |
|
| 132 |
dfs_test.start(am); |
|
| 98 | 133 |
|
| 99 | 134 |
l = dfs_test.dist(t); |
| 100 | 135 |
e = dfs_test.predArc(t); |
| 101 | 136 |
s = dfs_test.predNode(t); |
| 102 | 137 |
b = dfs_test.reached(t); |
| 103 | 138 |
pp = dfs_test.path(t); |
| 104 | 139 |
} |
| 105 | 140 |
} |
| 106 | 141 |
|
| 107 | 142 |
void checkDfsFunctionCompile() |
| 108 | 143 |
{
|
| 109 | 144 |
typedef int VType; |
| 110 | 145 |
typedef concepts::Digraph Digraph; |
| 111 | 146 |
typedef Digraph::Arc Arc; |
| 112 | 147 |
typedef Digraph::Node Node; |
| 113 | 148 |
|
| 114 | 149 |
Digraph g; |
| 115 | 150 |
bool b; |
| 116 | 151 |
dfs(g).run(Node()); |
| 117 | 152 |
b=dfs(g).run(Node(),Node()); |
| 118 | 153 |
dfs(g).run(); |
| 119 | 154 |
dfs(g) |
| 120 | 155 |
.predMap(concepts::ReadWriteMap<Node,Arc>()) |
| 121 | 156 |
.distMap(concepts::ReadWriteMap<Node,VType>()) |
| 122 | 157 |
.reachedMap(concepts::ReadWriteMap<Node,bool>()) |
| 123 | 158 |
.processedMap(concepts::WriteMap<Node,bool>()) |
| 124 | 159 |
.run(Node()); |
| 125 | 160 |
b=dfs(g) |
| 126 | 161 |
.predMap(concepts::ReadWriteMap<Node,Arc>()) |
| 127 | 162 |
.distMap(concepts::ReadWriteMap<Node,VType>()) |
| 128 | 163 |
.reachedMap(concepts::ReadWriteMap<Node,bool>()) |
| 129 | 164 |
.processedMap(concepts::WriteMap<Node,bool>()) |
| ... | ... |
@@ -31,106 +31,152 @@ |
| 31 | 31 |
|
| 32 | 32 |
char test_lgf[] = |
| 33 | 33 |
"@nodes\n" |
| 34 | 34 |
"label\n" |
| 35 | 35 |
"0\n" |
| 36 | 36 |
"1\n" |
| 37 | 37 |
"2\n" |
| 38 | 38 |
"3\n" |
| 39 | 39 |
"4\n" |
| 40 | 40 |
"@arcs\n" |
| 41 | 41 |
" label length\n" |
| 42 | 42 |
"0 1 0 1\n" |
| 43 | 43 |
"1 2 1 1\n" |
| 44 | 44 |
"2 3 2 1\n" |
| 45 | 45 |
"0 3 4 5\n" |
| 46 | 46 |
"0 3 5 10\n" |
| 47 | 47 |
"0 3 6 7\n" |
| 48 | 48 |
"4 2 7 1\n" |
| 49 | 49 |
"@attributes\n" |
| 50 | 50 |
"source 0\n" |
| 51 | 51 |
"target 3\n"; |
| 52 | 52 |
|
| 53 | 53 |
void checkDijkstraCompile() |
| 54 | 54 |
{
|
| 55 | 55 |
typedef int VType; |
| 56 | 56 |
typedef concepts::Digraph Digraph; |
| 57 | 57 |
typedef concepts::ReadMap<Digraph::Arc,VType> LengthMap; |
| 58 | 58 |
typedef Dijkstra<Digraph, LengthMap> DType; |
| 59 | 59 |
typedef Digraph::Node Node; |
| 60 | 60 |
typedef Digraph::Arc Arc; |
| 61 | 61 |
|
| 62 | 62 |
Digraph G; |
| 63 |
Node s, t; |
|
| 63 |
Node s, t, n; |
|
| 64 | 64 |
Arc e; |
| 65 | 65 |
VType l; |
| 66 |
int i; |
|
| 66 | 67 |
bool b; |
| 67 | 68 |
DType::DistMap d(G); |
| 68 | 69 |
DType::PredMap p(G); |
| 69 | 70 |
LengthMap length; |
| 70 | 71 |
Path<Digraph> pp; |
| 72 |
concepts::ReadMap<Node,bool> nm; |
|
| 71 | 73 |
|
| 72 | 74 |
{
|
| 73 | 75 |
DType dijkstra_test(G,length); |
| 76 |
const DType& const_dijkstra_test = dijkstra_test; |
|
| 74 | 77 |
|
| 75 | 78 |
dijkstra_test.run(s); |
| 76 | 79 |
dijkstra_test.run(s,t); |
| 77 | 80 |
|
| 81 |
dijkstra_test.init(); |
|
| 82 |
dijkstra_test.addSource(s); |
|
| 83 |
dijkstra_test.addSource(s, 1); |
|
| 84 |
n = dijkstra_test.processNextNode(); |
|
| 85 |
n = const_dijkstra_test.nextNode(); |
|
| 86 |
b = const_dijkstra_test.emptyQueue(); |
|
| 87 |
i = const_dijkstra_test.queueSize(); |
|
| 88 |
|
|
| 89 |
dijkstra_test.start(); |
|
| 90 |
dijkstra_test.start(t); |
|
| 91 |
dijkstra_test.start(nm); |
|
| 92 |
|
|
| 93 |
l = const_dijkstra_test.dist(t); |
|
| 94 |
e = const_dijkstra_test.predArc(t); |
|
| 95 |
s = const_dijkstra_test.predNode(t); |
|
| 96 |
b = const_dijkstra_test.reached(t); |
|
| 97 |
b = const_dijkstra_test.processed(t); |
|
| 98 |
d = const_dijkstra_test.distMap(); |
|
| 99 |
p = const_dijkstra_test.predMap(); |
|
| 100 |
pp = const_dijkstra_test.path(t); |
|
| 101 |
l = const_dijkstra_test.currentDist(t); |
|
| 102 |
} |
|
| 103 |
{
|
|
| 104 |
DType |
|
| 105 |
::SetPredMap<concepts::ReadWriteMap<Node,Arc> > |
|
| 106 |
::SetDistMap<concepts::ReadWriteMap<Node,VType> > |
|
| 107 |
::SetStandardProcessedMap |
|
| 108 |
::SetProcessedMap<concepts::WriteMap<Node,bool> > |
|
| 109 |
::SetOperationTraits<DijkstraDefaultOperationTraits<VType> > |
|
| 110 |
::SetHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> > > |
|
| 111 |
::SetStandardHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> > > |
|
| 112 |
::SetHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> >, |
|
| 113 |
concepts::ReadWriteMap<Node,int> > |
|
| 114 |
::Create dijkstra_test(G,length); |
|
| 115 |
|
|
| 116 |
LengthMap length_map; |
|
| 117 |
concepts::ReadWriteMap<Node,Arc> pred_map; |
|
| 118 |
concepts::ReadWriteMap<Node,VType> dist_map; |
|
| 119 |
concepts::WriteMap<Node,bool> processed_map; |
|
| 120 |
concepts::ReadWriteMap<Node,int> heap_cross_ref; |
|
| 121 |
BinHeap<VType, concepts::ReadWriteMap<Node,int> > heap(heap_cross_ref); |
|
| 122 |
|
|
| 123 |
dijkstra_test |
|
| 124 |
.lengthMap(length_map) |
|
| 125 |
.predMap(pred_map) |
|
| 126 |
.distMap(dist_map) |
|
| 127 |
.processedMap(processed_map) |
|
| 128 |
.heap(heap, heap_cross_ref); |
|
| 129 |
|
|
| 130 |
dijkstra_test.run(s); |
|
| 131 |
dijkstra_test.run(s,t); |
|
| 132 |
|
|
| 133 |
dijkstra_test.addSource(s); |
|
| 134 |
dijkstra_test.addSource(s, 1); |
|
| 135 |
n = dijkstra_test.processNextNode(); |
|
| 136 |
n = dijkstra_test.nextNode(); |
|
| 137 |
b = dijkstra_test.emptyQueue(); |
|
| 138 |
i = dijkstra_test.queueSize(); |
|
| 139 |
|
|
| 140 |
dijkstra_test.start(); |
|
| 141 |
dijkstra_test.start(t); |
|
| 142 |
dijkstra_test.start(nm); |
|
| 143 |
|
|
| 78 | 144 |
l = dijkstra_test.dist(t); |
| 79 | 145 |
e = dijkstra_test.predArc(t); |
| 80 | 146 |
s = dijkstra_test.predNode(t); |
| 81 | 147 |
b = dijkstra_test.reached(t); |
| 82 |
d = dijkstra_test.distMap(); |
|
| 83 |
p = dijkstra_test.predMap(); |
|
| 148 |
b = dijkstra_test.processed(t); |
|
| 84 | 149 |
pp = dijkstra_test.path(t); |
| 85 |
} |
|
| 86 |
{
|
|
| 87 |
DType |
|
| 88 |
::SetPredMap<concepts::ReadWriteMap<Node,Arc> > |
|
| 89 |
::SetDistMap<concepts::ReadWriteMap<Node,VType> > |
|
| 90 |
::SetProcessedMap<concepts::WriteMap<Node,bool> > |
|
| 91 |
::SetStandardProcessedMap |
|
| 92 |
::SetOperationTraits<DijkstraDefaultOperationTraits<VType> > |
|
| 93 |
::SetHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> > > |
|
| 94 |
::SetStandardHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> > > |
|
| 95 |
::Create dijkstra_test(G,length); |
|
| 96 |
|
|
| 97 |
dijkstra_test.run(s); |
|
| 98 |
dijkstra_test.run(s,t); |
|
| 99 |
|
|
| 100 |
l = dijkstra_test.dist(t); |
|
| 101 |
e = dijkstra_test.predArc(t); |
|
| 102 |
s = dijkstra_test.predNode(t); |
|
| 103 |
b = dijkstra_test.reached(t); |
|
| 104 |
pp = dijkstra_test.path(t); |
|
| 150 |
l = dijkstra_test.currentDist(t); |
|
| 105 | 151 |
} |
| 106 | 152 |
|
| 107 | 153 |
} |
| 108 | 154 |
|
| 109 | 155 |
void checkDijkstraFunctionCompile() |
| 110 | 156 |
{
|
| 111 | 157 |
typedef int VType; |
| 112 | 158 |
typedef concepts::Digraph Digraph; |
| 113 | 159 |
typedef Digraph::Arc Arc; |
| 114 | 160 |
typedef Digraph::Node Node; |
| 115 | 161 |
typedef concepts::ReadMap<Digraph::Arc,VType> LengthMap; |
| 116 | 162 |
|
| 117 | 163 |
Digraph g; |
| 118 | 164 |
bool b; |
| 119 | 165 |
dijkstra(g,LengthMap()).run(Node()); |
| 120 | 166 |
b=dijkstra(g,LengthMap()).run(Node(),Node()); |
| 121 | 167 |
dijkstra(g,LengthMap()) |
| 122 | 168 |
.predMap(concepts::ReadWriteMap<Node,Arc>()) |
| 123 | 169 |
.distMap(concepts::ReadWriteMap<Node,VType>()) |
| 124 | 170 |
.processedMap(concepts::WriteMap<Node,bool>()) |
| 125 | 171 |
.run(Node()); |
| 126 | 172 |
b=dijkstra(g,LengthMap()) |
| 127 | 173 |
.predMap(concepts::ReadWriteMap<Node,Arc>()) |
| 128 | 174 |
.distMap(concepts::ReadWriteMap<Node,VType>()) |
| 129 | 175 |
.processedMap(concepts::WriteMap<Node,bool>()) |
| 130 | 176 |
.path(concepts::Path<Digraph>()) |
| 131 | 177 |
.dist(VType()) |
| 132 | 178 |
.run(Node(),Node()); |
| 133 | 179 |
} |
| 134 | 180 |
|
| 135 | 181 |
template <class Digraph> |
| 136 | 182 |
void checkDijkstra() {
|
| ... | ... |
@@ -55,89 +55,95 @@ |
| 55 | 55 |
"4 3 9 3\n" |
| 56 | 56 |
"5 7 10 3\n" |
| 57 | 57 |
"5 6 11 10\n" |
| 58 | 58 |
"5 8 12 10\n" |
| 59 | 59 |
"6 8 13 8\n" |
| 60 | 60 |
"8 9 14 20\n" |
| 61 | 61 |
"8 1 15 5\n" |
| 62 | 62 |
"9 5 16 5\n" |
| 63 | 63 |
"@attributes\n" |
| 64 | 64 |
"source 1\n" |
| 65 | 65 |
"target 8\n"; |
| 66 | 66 |
|
| 67 | 67 |
void checkPreflowCompile() |
| 68 | 68 |
{
|
| 69 | 69 |
typedef int VType; |
| 70 | 70 |
typedef concepts::Digraph Digraph; |
| 71 | 71 |
|
| 72 | 72 |
typedef Digraph::Node Node; |
| 73 | 73 |
typedef Digraph::Arc Arc; |
| 74 | 74 |
typedef concepts::ReadMap<Arc,VType> CapMap; |
| 75 | 75 |
typedef concepts::ReadWriteMap<Arc,VType> FlowMap; |
| 76 | 76 |
typedef concepts::WriteMap<Node,bool> CutMap; |
| 77 | 77 |
|
| 78 | 78 |
typedef Elevator<Digraph, Digraph::Node> Elev; |
| 79 | 79 |
typedef LinkedElevator<Digraph, Digraph::Node> LinkedElev; |
| 80 | 80 |
|
| 81 | 81 |
Digraph g; |
| 82 | 82 |
Node n; |
| 83 | 83 |
Arc e; |
| 84 | 84 |
CapMap cap; |
| 85 | 85 |
FlowMap flow; |
| 86 | 86 |
CutMap cut; |
| 87 |
VType v; |
|
| 88 |
bool b; |
|
| 87 | 89 |
|
| 88 |
Preflow<Digraph, CapMap> |
|
| 89 |
::SetFlowMap<FlowMap> |
|
| 90 |
::SetElevator<Elev> |
|
| 91 |
::SetStandardElevator<LinkedElev> |
|
| 92 |
|
|
| 90 |
typedef Preflow<Digraph, CapMap> |
|
| 91 |
::SetFlowMap<FlowMap> |
|
| 92 |
::SetElevator<Elev> |
|
| 93 |
::SetStandardElevator<LinkedElev> |
|
| 94 |
::Create PreflowType; |
|
| 95 |
PreflowType preflow_test(g, cap, n, n); |
|
| 96 |
const PreflowType& const_preflow_test = preflow_test; |
|
| 93 | 97 |
|
| 94 |
preflow_test.capacityMap(cap); |
|
| 95 |
flow = preflow_test.flowMap(); |
|
| 96 |
preflow_test.flowMap(flow); |
|
| 97 |
preflow_test.source(n); |
|
| 98 |
preflow_test |
|
| 98 |
preflow_test |
|
| 99 |
.capacityMap(cap) |
|
| 100 |
.flowMap(flow) |
|
| 101 |
.source(n) |
|
| 102 |
.target(n); |
|
| 99 | 103 |
|
| 100 | 104 |
preflow_test.init(); |
| 101 | 105 |
preflow_test.init(cap); |
| 102 | 106 |
preflow_test.startFirstPhase(); |
| 103 | 107 |
preflow_test.startSecondPhase(); |
| 104 | 108 |
preflow_test.run(); |
| 105 | 109 |
preflow_test.runMinCut(); |
| 106 | 110 |
|
| 107 |
preflow_test.flowValue(); |
|
| 108 |
preflow_test.minCut(n); |
|
| 109 |
preflow_test.minCutMap(cut); |
|
| 110 |
preflow_test.flow(e); |
|
| 111 |
|
|
| 111 |
v = const_preflow_test.flowValue(); |
|
| 112 |
v = const_preflow_test.flow(e); |
|
| 113 |
const FlowMap& fm = const_preflow_test.flowMap(); |
|
| 114 |
b = const_preflow_test.minCut(n); |
|
| 115 |
const_preflow_test.minCutMap(cut); |
|
| 116 |
|
|
| 117 |
ignore_unused_variable_warning(fm); |
|
| 112 | 118 |
} |
| 113 | 119 |
|
| 114 | 120 |
int cutValue (const SmartDigraph& g, |
| 115 | 121 |
const SmartDigraph::NodeMap<bool>& cut, |
| 116 | 122 |
const SmartDigraph::ArcMap<int>& cap) {
|
| 117 | 123 |
|
| 118 | 124 |
int c=0; |
| 119 | 125 |
for(SmartDigraph::ArcIt e(g); e!=INVALID; ++e) {
|
| 120 | 126 |
if (cut[g.source(e)] && !cut[g.target(e)]) c+=cap[e]; |
| 121 | 127 |
} |
| 122 | 128 |
return c; |
| 123 | 129 |
} |
| 124 | 130 |
|
| 125 | 131 |
bool checkFlow(const SmartDigraph& g, |
| 126 | 132 |
const SmartDigraph::ArcMap<int>& flow, |
| 127 | 133 |
const SmartDigraph::ArcMap<int>& cap, |
| 128 | 134 |
SmartDigraph::Node s, SmartDigraph::Node t) {
|
| 129 | 135 |
|
| 130 | 136 |
for (SmartDigraph::ArcIt e(g); e != INVALID; ++e) {
|
| 131 | 137 |
if (flow[e] < 0 || flow[e] > cap[e]) return false; |
| 132 | 138 |
} |
| 133 | 139 |
|
| 134 | 140 |
for (SmartDigraph::NodeIt n(g); n != INVALID; ++n) {
|
| 135 | 141 |
if (n == s || n == t) continue; |
| 136 | 142 |
int sum = 0; |
| 137 | 143 |
for (SmartDigraph::OutArcIt e(g, n); e != INVALID; ++e) {
|
| 138 | 144 |
sum += flow[e]; |
| 139 | 145 |
} |
| 140 | 146 |
for (SmartDigraph::InArcIt e(g, n); e != INVALID; ++e) {
|
| 141 | 147 |
sum -= flow[e]; |
| 142 | 148 |
} |
| 143 | 149 |
if (sum != 0) return false; |
0 comments (0 inline)