OKlibrary  0.2.1.6
general.hpp File Reference

Plans for Maxima-components for hypergraphs. More...

Go to the source code of this file.


Detailed Description

Plans for Maxima-components for hypergraphs.

Todo:
Place of IndependentSets.mac
  • The question is whether this belongs to module Transversals or not.
  • Yet it is some kind of interface, which could stay at this top level.
Todo:
Write tests
Todo:
Redesign
Todo:
Write docus
  • We should have a list of all available functions.
  • Seems that this list needs to be maintained manually?
Todo:
Statistics
  • Similar to ClauseSets/Statistics.mac we should have Hypergraphs/Statistics.mac.
  • Simplest:
    statistics_hg(G) := statistics_fcs(G)$
       
Todo:
Special properties of hypergraphs
  • Perhaps we have a module "Properties.mac", where basic properties of hypergraphs are tested.
  • Whether a general hypergraph has repeated hyperedges.
  • Whether a hypergraph has subsumed hyperedges.
  • Was a hypergraph is "downward hereditary" or "upward hereditary".
  • What about all forms of stability under set-operations? Likely these special hypergraphs should go to ComputerAlgebra/Sets.
Todo:
Intersecting hypergraphs
Todo:
Helly property
  • In [Chepoi, Creignou, Hermann, Salzer, The {H}elly property and satisfiability of {B}oolean formulas defined on set families, European Journal of Combinatorics, 2010, 31(2):502-516] the Helly property of hypergraphs (every intersecting sub-hypergraph is a star) is applied to signed CNF (the vertices are the possible values, the hyperedges the allowed positive signs).
  • They also discuss two algorithms for deciding the Helly property in polynomial time.
  • We should implement these algorithms. (And, of course, also the other algorithms from the paper.)
Todo:
Hypergraph automorphisms
Todo:
Representing edge and vertex labellings
Todo:
Palindromic versions
  • We have palindromise_vdw_ohg as well as schurtriples_pd_ohg and wschurtriples_pd_ohg.
  • Perhaps a more general framework is possible?

Definition in file general.hpp.