r636:630c4898c548
Wed, 15 Apr 2009 08:13:30
[Not Reviewed]
0 comments (0 inline)
0
5
0
49
10
44
9
21
15
| ... | ... |
@@ -57,43 +57,82 @@ |
| 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); |
| ... | ... |
@@ -70,29 +70,36 @@ |
| 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, |
| ... | ... |
@@ -61,41 +61,76 @@ |
| 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); |
| ... | ... |
@@ -59,50 +59,96 @@ |
| 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 |
| ... | ... |
@@ -83,33 +83,39 @@ |
| 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, |
0 comments (0 inline)