[Lemon-user] Using Lemon in GraPHedron graph invariant's implementation

[Hadrien Mélot]

Dear Lemon users & developers,

As you maybe know, GraPHedron (www.graphedron.net) is an online system 
to help researchers in graph theory.

More precisely, GraPHedron is a computer-assisted system which helps to 
obtain conjectures about undirected graphs. It uses a polyhedral 
approach to find strongest relations among a set of graph invariants. 
This approach provides a formal framework allowing to identify 
interesting and tight
relations among the selected set of invariants.

The user defines a problem (i.e. selected invariants under interest and 
a class of graphs) and gets a
detailed report about it. This report contains information to derive 
conjectures interactively and, in some cases, GraPHedron is able to give 
fully automated conjectures.

What is new is that now invariants can be implemented using the Lemon 
library. All algorithms which compute a numerical value using a 
ListUGraph object can be used as an invariant.

For instance, the old version of the GraPHedron's implementation of the 
Maximum Matching was very naive and inefficient (recursive exhaustive 
search). Computing all maximum matching sizes of all non-isomorphic 
undirected graphs with 10 nodes (there are 12005168 such graphs) take 
approximately 2 days with this old version. The new version of the 
implementation is now simply:

int GphInvMaxMatching(const ListUGraph& g)
{
    MaxMatching<ListUGraph> maxM(g);
    maxM.run();
   
    return maxM.size();   
}

It takes now only 4 min. 22 sec. of CPU time to compute the 12 millions 
maximum matching sizes (including the adaptation of a "GraPHedron" graph 
to a ListUGraph) !

Don't hesitate to propose invariants which are not yet included in 
GraPHedron via www.graphedron.net and using this great library. All such 
submissions will be noted with a reference to the Lemon library.

Thank to the Lemon Team for this great work!

Hadrien Mélot