LEMON/LEMON-official Changeset - r644:2ca0cdb5f366

Repositories » LEMON » LEMON-official

Summary
Changelog
Files
Switch To
- loading...
Options
- Lightweight changelog
- Search
Pull Requests

Changeset - r644:2ca0cdb5f366

« 643:293551

646:f63e87 »

r644:2ca0cdb5f366

Sat, 18 Apr 2009 21:01:12

[Not Reviewed]

0 comments (0 inline)

deba@inf.elte.hu
deba@inf.elte.hu

Fix in HaoOrlin (#264)

0 2 0

default

2 files changed with 14 insertions and 24 deletions:

lemon/hao_orlin.h

test/hao_orlin_test.cc

↑ Collapse diff ↑

lemon/hao_orlin.h

Show inline comments

@@ -205,48 +205,49 @@
      (*_next)[_last[bucket]] = i;
      (*_next)[i] = INVALID;
      _last[bucket] = i;
    }

    void addItem(const Node& i, int bucket) {
      (*_bucket)[i] = bucket;
      if (_last[bucket] != INVALID) {
        (*_prev)[i] = _last[bucket];
        (*_next)[_last[bucket]] = i;
        (*_next)[i] = INVALID;
        _last[bucket] = i;
      } else {
        (*_prev)[i] = INVALID;
        _first[bucket] = i;
        (*_next)[i] = INVALID;
        _last[bucket] = i;
      }
    }

    void findMinCutOut() {

      for (NodeIt n(_graph); n != INVALID; ++n) {
        (*_excess)[n] = 0;
        (*_source_set)[n] = false;
      }

      for (ArcIt a(_graph); a != INVALID; ++a) {
        (*_flow)[a] = 0;
      }

      int bucket_num = 0;
      std::vector<Node> queue(_node_num);
      int qfirst = 0, qlast = 0, qsep = 0;

      {
        typename Digraph::template NodeMap<bool> reached(_graph, false);

        reached[_source] = true;
        bool first_set = true;

        for (NodeIt t(_graph); t != INVALID; ++t) {
          if (reached[t]) continue;
          _sets.push_front(std::list<int>());

          queue[qlast++] = t;
          reached[t] = true;

          while (qfirst != qlast) {
@@ -504,48 +505,49 @@
              activate(v);
            }
            (*_excess)[v] += rem;
            (*_flow)[a] = 0;
          }

          target = new_target;
          if ((*_active)[target]) {
            deactivate(target);
          }

          _highest = _sets.back().begin();
          while (_highest != _sets.back().end() &&
                 !(*_active)[_first[*_highest]]) {
            ++_highest;
          }
        }
      }
    }

    void findMinCutIn() {

      for (NodeIt n(_graph); n != INVALID; ++n) {
        (*_excess)[n] = 0;
        (*_source_set)[n] = false;
      }

      for (ArcIt a(_graph); a != INVALID; ++a) {
        (*_flow)[a] = 0;
      }

      int bucket_num = 0;
      std::vector<Node> queue(_node_num);
      int qfirst = 0, qlast = 0, qsep = 0;

      {
        typename Digraph::template NodeMap<bool> reached(_graph, false);

        reached[_source] = true;

        bool first_set = true;

        for (NodeIt t(_graph); t != INVALID; ++t) {
          if (reached[t]) continue;
          _sets.push_front(std::list<int>());

          queue[qlast++] = t;
          reached[t] = true;


test/hao_orlin_test.cc

Show inline comments

@@ -90,86 +90,74 @@
 		  for (typename Graph::ArcIt a(graph); a != INVALID; ++a) {
 		    if (cut[graph.source(a)] && !cut[graph.target(a)])
 		      sum += cap[a];
+		  }
 		  return sum;
+		}
 		int main() {
 		  SmartDigraph graph;
 		  SmartDigraph::ArcMap<int> cap1(graph), cap2(graph), cap3(graph);
 		  SmartDigraph::NodeMap<bool> cut(graph);
 		  istringstream input(lgf);
 		  digraphReader(graph, input)
 		    .arcMap("cap1", cap1)
 		    .arcMap("cap2", cap2)
 		    .arcMap("cap3", cap3)
 		    .run();
+		  {
 		    HaoOrlin<SmartDigraph> ho(graph, cap1);
 		    ho.run();
 		    ho.minCutMap(cut);
 		    // BUG: The cut value should be positive
 		    check(ho.minCutValue() == 0, "Wrong cut value");
 		    // BUG: It should work
 		    //check(ho.minCutValue() == cutValue(graph, cap1, cut), "Wrong cut value");
 		    check(ho.minCutValue() == 1, "Wrong cut value");
 		    check(ho.minCutValue() == cutValue(graph, cap1, cut), "Wrong cut value");
+		  }
+		  {
 		    HaoOrlin<SmartDigraph> ho(graph, cap2);
 		    ho.run();
 		    ho.minCutMap(cut);
 		    // BUG: The cut value should be positive
 		    check(ho.minCutValue() == 0, "Wrong cut value");
 		    // BUG: It should work
-		    //check(ho.minCutValue() == cutValue(graph, cap2, cut), "Wrong cut value");
 		    check(ho.minCutValue() == 1, "Wrong cut value");
 		    check(ho.minCutValue() == cutValue(graph, cap2, cut), "Wrong cut value");
+		  }
+		  {
 		    HaoOrlin<SmartDigraph> ho(graph, cap3);
 		    ho.run();
 		    ho.minCutMap(cut);
 		    // BUG: The cut value should be positive
 		    check(ho.minCutValue() == 0, "Wrong cut value");
 		    // BUG: It should work
 		    //check(ho.minCutValue() == cutValue(graph, cap3, cut), "Wrong cut value");
 		    check(ho.minCutValue() == 1, "Wrong cut value");
 		    check(ho.minCutValue() == cutValue(graph, cap3, cut), "Wrong cut value");
+		  }
 		  typedef Undirector<SmartDigraph> UGraph;
 		  UGraph ugraph(graph);
+		  {
 		    HaoOrlin<UGraph, SmartDigraph::ArcMap<int> > ho(ugraph, cap1);
 		    ho.run();
 		    ho.minCutMap(cut);
 		    // BUG: The cut value should be 2
 		    check(ho.minCutValue() == 1, "Wrong cut value");
 		    // BUG: It should work
 		    //check(ho.minCutValue() == cutValue(ugraph, cap1, cut), "Wrong cut value");
 		    check(ho.minCutValue() == 2, "Wrong cut value");
 		    check(ho.minCutValue() == cutValue(ugraph, cap1, cut), "Wrong cut value");
+		  }
+		  {
 		    HaoOrlin<UGraph, SmartDigraph::ArcMap<int> > ho(ugraph, cap2);
 		    ho.run();
 		    ho.minCutMap(cut);
 		    // TODO: Check this cut value
 		    check(ho.minCutValue() == 4, "Wrong cut value");
 		    // BUG: It should work
 		    //check(ho.minCutValue() == cutValue(ugraph, cap2, cut), "Wrong cut value");
 		    check(ho.minCutValue() == 5, "Wrong cut value");
 		    check(ho.minCutValue() == cutValue(ugraph, cap2, cut), "Wrong cut value");
+		  }
+		  {
 		    HaoOrlin<UGraph, SmartDigraph::ArcMap<int> > ho(ugraph, cap3);
 		    ho.run();
 		    ho.minCutMap(cut);
 		    // TODO: Check this cut value
 		    check(ho.minCutValue() == 5, "Wrong cut value");
 		    // BUG: It should work
 		    //check(ho.minCutValue() == cutValue(ugraph, cap3, cut), "Wrong cut value");
 		    check(ho.minCutValue() == cutValue(ugraph, cap3, cut), "Wrong cut value");
+		  }
 		  return 0;
+		}

0 comments (0 inline)

...	...	@@ -205,48 +205,49 @@
205	205	(*_next)[_last[bucket]] = i;
206	206	(*_next)[i] = INVALID;
207	207	_last[bucket] = i;
208	208	}
209	209
210	210	void addItem(const Node& i, int bucket) {
211	211	(*_bucket)[i] = bucket;
212	212	if (_last[bucket] != INVALID) {
213	213	(*_prev)[i] = _last[bucket];
214	214	(*_next)[_last[bucket]] = i;
215	215	(*_next)[i] = INVALID;
216	216	_last[bucket] = i;
217	217	} else {
218	218	(*_prev)[i] = INVALID;
219	219	_first[bucket] = i;
220	220	(*_next)[i] = INVALID;
221	221	_last[bucket] = i;
222	222	}
223	223	}
224	224
225	225	void findMinCutOut() {
226	226
227	227	for (NodeIt n(_graph); n != INVALID; ++n) {
228	228	(*_excess)[n] = 0;
	229	(*_source_set)[n] = false;
229	230	}
230	231
231	232	for (ArcIt a(_graph); a != INVALID; ++a) {
232	233	(*_flow)[a] = 0;
233	234	}
234	235
235	236	int bucket_num = 0;
236	237	std::vector<Node> queue(_node_num);
237	238	int qfirst = 0, qlast = 0, qsep = 0;
238	239
239	240	{
240	241	typename Digraph::template NodeMap<bool> reached(_graph, false);
241	242
242	243	reached[_source] = true;
243	244	bool first_set = true;
244	245
245	246	for (NodeIt t(_graph); t != INVALID; ++t) {
246	247	if (reached[t]) continue;
247	248	_sets.push_front(std::list<int>());
248	249
249	250	queue[qlast++] = t;
250	251	reached[t] = true;
251	252
252	253	while (qfirst != qlast) {
...	...	@@ -504,48 +505,49 @@
504	505	activate(v);
505	506	}
506	507	(*_excess)[v] += rem;
507	508	(*_flow)[a] = 0;
508	509	}
509	510
510	511	target = new_target;
511	512	if ((*_active)[target]) {
512	513	deactivate(target);
513	514	}
514	515
515	516	_highest = _sets.back().begin();
516	517	while (_highest != _sets.back().end() &&
517	518	!(_active)[_first[_highest]]) {
518	519	++_highest;
519	520	}
520	521	}
521	522	}
522	523	}
523	524
524	525	void findMinCutIn() {
525	526
526	527	for (NodeIt n(_graph); n != INVALID; ++n) {
527	528	(*_excess)[n] = 0;
	529	(*_source_set)[n] = false;
528	530	}
529	531
530	532	for (ArcIt a(_graph); a != INVALID; ++a) {
531	533	(*_flow)[a] = 0;
532	534	}
533	535
534	536	int bucket_num = 0;
535	537	std::vector<Node> queue(_node_num);
536	538	int qfirst = 0, qlast = 0, qsep = 0;
537	539
538	540	{
539	541	typename Digraph::template NodeMap<bool> reached(_graph, false);
540	542
541	543	reached[_source] = true;
542	544
543	545	bool first_set = true;
544	546
545	547	for (NodeIt t(_graph); t != INVALID; ++t) {
546	548	if (reached[t]) continue;
547	549	_sets.push_front(std::list<int>());
548	550
549	551	queue[qlast++] = t;
550	552	reached[t] = true;
551	553

RhodeCode

Login to your account