[Lemon-devel] Check function and algorithm interface

[Kovács Péter]

Hi,

I agree, it would be important to have uniform interface for checking functions.

> checkMaxFlow(maxFlowAlg);
> checkMaxFlow(digraph, capacity, s, t, flow, cut);

Both one would have to be called after run(), am I right?

Where should we put these checker functions? To the test directory, or to the lemon directory? I think it would be better to have public checker functions. E.g. they could be placed in a common file, e.g. checker.h, and each checker function should be placed into the corresponding doxygen group in the doc.

> The other topic is the interface of the algorithm. I think we should 
> provide similar interface for similar algorithms. 

This is also important. For the problems that are similar to shortest paths, Bfs, Dijkstra would be the sample, they are just fine, I think. For flow-type problems currently we have Preflow and Circulation. I suggest to clarify and unify the interface of them, and provide checker functions according to it, and after that Preflow would be the sample for the others. Btw. I like the current interface of it.
  
  void run()
  void runMinCut()
  
  Value flowValue() const
  Value flow(const Arc &arc) const
  const FlowMap& flowMap() const
  bool minCut(const Node &node) const
  template<typename CutMap> void minCutMap(CutMap &cutMap) const

It is the same as you wrote except for the following one.

> typename <template FlowMap> void flowMap(FlowMap&);

The flow algorithms use a flow map during running, so it seems to be a better solution to have the current interface, to avoid map copying.
Similarly in the min. cost flow algorithms it is better to have
  const FlowMap& flowMap() const
  const PotentialMap& potentialMap() const
than having template functions, since they are using these maps during running.

Maybe the only questionable names in the Preflow interface are minCut() and minCutMap(). For the flow values flow() and flowMap() is used, not maxFlow() and maxFlowMap(), which is much better (e.g. it is similar to min. cost flows), so maybe we should use cut() and cutMap(). What do you think? On the other hand, if an algorithm considers a cut, than it is usually minimum cut in a sense.

The interface of Suurballe is an intresting question, since it is related to shortest path problems, but its interface should be rather similar to the interface of min. cost flow algorithms. I think the only question is to use "length" or "cost". Now length is used in Suurballe, but cost is used in min. cost flows (in the svn repository). What do you think, should it be unifrom? Should we rename length to cost in Suurballe?

Regards,
Peter

Balazs Dezso írta:
> Dear Developers,
> 
> The algorithm checking is important issue, therefore I think we should use 
> uniform interface for it. For example it can be made efficiently for several 
> algorithms: shortest paths, max flows, min cost flows, circulations, matchings, 
> etc. I think separate functions would the most efficient solution for this 
> purpose, one which uses the uniform interface of the algorithm, and another 
> one which uses the maps used or set by algorithm.
> 
> checkMaxFlow(maxFlowAlg);
> checkMaxFlow(digraph, capacity, s, t, flow, cut);
> 
> Currently just in the Circulation are there checking functions, but those are 
> member functions. In the tests directory we use similar checks for shortest 
> paths, max flows, matchings.
> 
> The other topic is the interface of the algorithm. I think we should provide 
> similar interface for similar algorithms. The flow problems, the matchings and 
> similar duality based algorithms can follow common approach. For example for a 
> max flow problem:

> Value flow(Arc);
> typename <template FlowMap> void flowMap(FlowMap&);

> Value flowValue();
> bool minCut(Node);
> typename <typename CutMap> void minCutMap(CutMap&);
> Value minCutValue();
> 
> I think, we should decide a good policy for naming this kind of member 
> functions.
> 
> Best, Balazs