Consensus.hpp File Reference

Plans regarding implementing the "consensus algorithm" from [XXX] for computing all maximal bicliques. More...

Go to the source code of this file.

Detailed Description

Plans regarding implementing the "consensus algorithm" from [XXX] for computing all maximal bicliques.

Failing test okltest_con_alg2(con_alg2)
  • The assert
      assert(f([[{1,2},{3,4}],[{2,5},{3,6}],[{2,7},{4,8}]],[{1,2,3,4,5,6,7,8},{{1,3},{1,4},{2,3},{2,4},{5,3},{5,6},{2,6},{7,4},{7,8},{2,8}}]) = [[{4},{1,2,7}],[{2},{3,4,6,8}],[{3},{1,2,5}],[{1,2},{3,4}],[{2,5},{3,6}],[{2,7},{4,8}]])
    fails, since the order of the return list is different.
  • The specification of con_alg1/2 is incomplete: In which order are the maximal bicliques output?
  • Either this order can be defined, or, if left unspecified as an implementation detail, then the tests for con_alg1, con_alg2 must be changed to reflect this.
Notions and notations
  • A kind of dictionary is needed.
  • Compare with the functions for resolution.
The basic "consensus" operation
Maximisation functions
  • It appears that the various maximisation functions should better be placed somewhere else.
  • maximal_bc_gl belongs to general biclique functionality.
  • For aux_con_alg1_abs compare max_elements in ComputerAlgebra/Hypergraphs/Lisp/SetSystems.mac.
The consensus iteration
Handling general graphs
  • Can the algorithms be generalised to handle general graphs?
  • Regarding vertex bicliques: the bicliques of a general graph are exactly the bicliques of the underlying graph (with loops).
  • Regarding edge bicliques, we can simply obtain them from the vertex bicliques by using all combinations of underlying edges.
Improving the implementations
  • "con_adj_gl_b1_1_b2_1_p" looks confusing; perhaps all these functions can be captured by a single function.
Compute all maximal bicliques
  • "con_alg1/2" should likely use "consensus".
  • We need also these algorithms without the argument C.
    1. The trivial choice is just to take the edges on their own.
    2. Does the running time depend on C (strongly)?
    3. If yes, then some heuristics is needed.
    4. Likely, we need some reasonable algorithm for finding a biclique cover of small size.
      1. One possibility is to chose some yet uncovered edge, find a maximal biclique (in the original graph) covering this edge, and repeating this process.
    5. Perhaps "C" should be called "LB".

Definition in file Consensus.hpp.