[Lemon-user] problem with using HaoOrlin

[Pierre Nancel-Penard]

Hi,

I ve tried to use  HaoOrlin Algorithm lemon implementation for a 
SmartDigraph. I use the calculateOut() method.
and I am facing a problem. As I didn't manage to register (I had the 
"Environment not found" error message)  to be able to post a ticket, I 
post it here.
I use lemon-1.2.3 on ubuntu 10.04.4 and gcc to compile.

first here is a test of use that works good. Its a graph with 5 nodes: 0 
is the source, 4 is the sink.
It finds the min cut 2 that correspond to the nodes 0 and 2. All is good!

Here are the results of the compiled c++ attached files:

$ ./test_that_work
@nodes
label
0
1
2
3
4
@arcs
         label    capacity
0    1    0    2
0    2    1    3
1    2    2    1000
1    3    3    1000
3    4    4    4
mincut=2
2
0

Then,

$ ./test_that_dont_work
@nodes
label
0
1
2
3
4
5
@arcs
         label    capacity
0    1    0    2
0    2    1    3
1    2    2    1000
1    3    3    1000
3    5    4    4
4    5    5    4
mincut=0
5
3
2
1
0

This is same graph as before but now 5 is sink, and there is other node 
4 that is only connected to sink.
As this node is only connected to sink, it don't change the min cut. but 
it did and find 0 and all nodes!
I have same problem if the node 4 is not connected to sink.
So if there are unconnected nodes or nodes only connected to sink, the 
method calculateOut() seems to not give the min cut I want to obtain.
So I want to know if its due to an error from my use or understanding of 
calculateOut() method.
Because putting off all the only sink connected nodes and unconnected 
nodes is too much time consumming for larger problem instance,

Any help will be greatly apreciated!

Best regards,

Pierre Nancel-Penard
PostDoc in Advanced Mining Technology Center
Universidad de Chile
-------------- next part --------------
#include <lemon/smart_graph.h>
#include <lemon/hao_orlin.h>
#include <lemon/lgf_writer.h>

using namespace std;
using namespace lemon;
typedef unsigned int BlockIndexType;
typedef SmartDigraph::Node Node;
typedef SmartDigraph::NodeMap<bool> CutMap;

main(){
	SmartDigraph _graph;
	Node* _nodes=new Node[5];
	SmartDigraph::ArcMap<float> _capacities(_graph);
	
	for(BlockIndexType i = 0; i <= 5; ++i){ 
		_nodes[i]=_graph.addNode();
	}
	SmartDigraphBase::Arc myarc=_graph.addArc(_nodes[0],_nodes[1]);
	_capacities[myarc]=2;
	myarc=_graph.addArc(_nodes[0],_nodes[2]);
	_capacities[myarc]=3;
	myarc=_graph.addArc(_nodes[1],_nodes[2]);
	_capacities[myarc]=1000;
	myarc=_graph.addArc(_nodes[1],_nodes[3]);
	_capacities[myarc]=1000;
	myarc=_graph.addArc(_nodes[3],_nodes[5]);
	_capacities[myarc]=4;
	myarc=_graph.addArc(_nodes[4],_nodes[5]);
	_capacities[myarc]=4;
	DigraphWriter<SmartDigraph> writer(_graph, std::cout);
    writer.arcMap("capacity", _capacities);
    writer.run();
	
	HaoOrlin<SmartDigraph,SmartDigraph::ArcMap<float> > myhao(_graph, _capacities);
	myhao.init(_nodes[0]);
	myhao.calculateOut();
	cerr<< "mincut="<<myhao.minCutValue()<<endl;
	BlockIndexType mynode=0;
	CutMap mycutMap(_graph);
	myhao.minCutMap(mycutMap);
	for (SmartDigraph::NodeMap<bool>::MapIt it(mycutMap); it != INVALID; ++it){
		mynode=_graph.id(it);
		if(*it) {
			cerr << mynode <<endl;
		}
	}
}
-------------- next part --------------
#include <lemon/smart_graph.h>
#include <lemon/hao_orlin.h>
#include <lemon/lgf_writer.h>

using namespace std;
using namespace lemon;
typedef unsigned int BlockIndexType;
typedef SmartDigraph::Node Node;
typedef SmartDigraph::NodeMap<bool> CutMap;

main(){
	SmartDigraph _graph;
	Node* _nodes=new Node[5];
	SmartDigraph::ArcMap<float> _capacities(_graph);
	
	for(BlockIndexType i = 0; i <= 4; ++i){ 
		_nodes[i]=_graph.addNode();
	}
	SmartDigraphBase::Arc myarc=_graph.addArc(_nodes[0],_nodes[1]);
	_capacities[myarc]=2;
	myarc=_graph.addArc(_nodes[0],_nodes[2]);
	_capacities[myarc]=3;
	myarc=_graph.addArc(_nodes[1],_nodes[2]);
	_capacities[myarc]=1000;
	myarc=_graph.addArc(_nodes[1],_nodes[3]);
	_capacities[myarc]=1000;
	myarc=_graph.addArc(_nodes[3],_nodes[4]);
	_capacities[myarc]=4;
	DigraphWriter<SmartDigraph> writer(_graph, std::cout);
    writer.arcMap("capacity", _capacities);
    writer.run();
	
	HaoOrlin<SmartDigraph,SmartDigraph::ArcMap<float> > myhao(_graph, _capacities);
	myhao.init(_nodes[0]);
	myhao.calculateOut();
	cerr<< "mincut="<<myhao.minCutValue()<<endl;
	BlockIndexType mynode=0;
	CutMap mycutMap(_graph);
	myhao.minCutMap(mycutMap);
	for (SmartDigraph::NodeMap<bool>::MapIt it(mycutMap); it != INVALID; ++it){
		mynode=_graph.id(it);
		if(*it) {	
			cerr << mynode <<endl;
		}
	}
}