r632:65fbcf2f978a
Wed, 15 Apr 2009 03:26:45
[Not Reviewed]
0 comments (0 inline)
0
5
0
49
10
44
9
17
11
| ... | ... |
@@ -53,52 +53,91 @@ |
| 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); |
| 92 | 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); |
|
| 118 |
|
|
| 93 | 119 |
bfs_test.run(s); |
| 94 | 120 |
bfs_test.run(s,t); |
| 95 | 121 |
bfs_test.run(); |
| 96 | 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); |
|
| 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 |
| ... | ... |
@@ -66,37 +66,44 @@ |
| 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> |
|
| 77 |
typedef Circulation<Digraph, CapMap, CapMap, DeltaMap> |
|
| 76 | 78 |
::SetFlowMap<FlowMap> |
| 77 | 79 |
::SetElevator<Elev> |
| 78 | 80 |
::SetStandardElevator<LinkedElev> |
| 79 |
::Create |
|
| 81 |
::Create CirculationType; |
|
| 82 |
CirculationType circ_test(g, lcap, ucap, delta); |
|
| 83 |
const CirculationType& const_circ_test = circ_test; |
|
| 80 | 84 |
|
| 81 |
circ_test.lowerCapMap(lcap); |
|
| 82 |
circ_test.upperCapMap(ucap); |
|
| 83 |
circ_test.deltaMap(delta); |
|
| 84 |
flow = circ_test.flowMap(); |
|
| 85 |
circ_test |
|
| 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(); |
| ... | ... |
@@ -57,49 +57,84 @@ |
| 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 |
} |
| ... | ... |
@@ -55,58 +55,104 @@ |
| 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; |
| ... | ... |
@@ -79,41 +79,47 @@ |
| 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> |
|
| 90 |
typedef Preflow<Digraph, CapMap> |
|
| 89 | 91 |
::SetFlowMap<FlowMap> |
| 90 | 92 |
::SetElevator<Elev> |
| 91 | 93 |
::SetStandardElevator<LinkedElev> |
| 92 |
::Create |
|
| 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 |
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); |
|
| 111 | 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) {
|
0 comments (0 inline)