graph-vcdim

Description

A library for computing the VC dimension of the closed neighborhoods of an undirected graph.

Authors

• David Coudert
• Mónika Csikós
• Guillaume Ducoffe
• Laurent Viennot

License

This code is released under the GNU General Public License, version 3, or any later version as published by the Free Software Foundation.

Compile

Requires C++17 and Cmake:

make

produces the main executable _build/main.

VC-dimension computation

Compute the VC-dimension of a graph in file g.txt (the file format is described below) with:

_build/main vcdim g.txt

Test it with:

_build/main vcdim unit_data/BIOGRID-SYSTEM-Dosage_Rescue-3.4.145.bcc.edgelist

For testing only the search of lower bounds :

_build/main vcdim-lb unit_data/com-dblp.ungraph.txt 64

Graph format

One edge per line with two space separated numbers. Lines beginning with a # are considered as comments. For example:

# 4 node graph
1 2
2 3
1 3
1 4

Get usage help

_build/main -h

More graphs

Graph repository

Experiments

Download the above repository and make a bunch of experiments with the following command (requires rust, python3, numpy, panda, plotly, kaleido):

make -j 16 -f experiments.mk world

The above computation takes roughly two days on a 16 cores machine (use the -j option according to the number of cores on your computer).

Thanks

We use code stubs provided by mogproject/modular-decomposition