This is the code accompanying my phd thesis, which I used for the chapter concerning edge partitions of complete geometric graphs. See also our paper Edge Partitions of Complete Geometric Graphs.
Given a set
ATTENTION: The main purpose of this code is proving that there exist point sets which do not admit a partition into plane spanning trees. Hence, in order to save a huge amount of constraints in our ILP formulation, we implemented only part of the constraints enforcing the properties of a spanning tree. More precisely, when partitioning into plane spanning trees we enforce the following constraints:
- Edges of the same color do not cross (this is always enforced),
- Every color class has precisely
$n-1$ edges, - No color class contains a cycle of length 3 (cycles of length 4 can also be set to be forbidden).
An input that cannot even satisfy these constraints, can in particular not be partitioned into plane spanning trees. Conversely, if the program reports a solution, there is no guarantee that the color classes indeed form spanning trees (the program can check this).
If you find this repository useful, please cite the following reference
@InProceedings{aichholzer_et_al:LIPIcs.SoCG.2022.6,
author = {Aichholzer, Oswin and Obenaus, Johannes and Orthaber, Joachim and Paul, Rosna and Schnider, Patrick and Steiner, Raphael and Taubner, Tim and Vogtenhuber, Birgit},
title = {{Edge Partitions of Complete Geometric Graphs}},
booktitle = {38th International Symposium on Computational Geometry (SoCG 2022)},
pages = {6:1--6:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-227-3},
ISSN = {1868-8969},
year = {2022},
volume = {224},
editor = {Goaoc, Xavier and Kerber, Michael},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16014},
URN = {urn:nbn:de:0030-drops-160141},
doi = {10.4230/LIPIcs.SoCG.2022.6},
annote = {Keywords: edge partition, complete geometric graph, plane spanning tree, wheel set}
}
Python 3 and a Gurobi license (for solving the ILP) are required.
Make sure you have Python 3.9 installed.
python3 -m venv venv
source venv/bin/activate
pip install -r requirements.txt
conda create -n edge_partitions python=3.9
conda activate edge_partitions
pip install -r requirements.txt
Setup the Gurobi license as described here.
python main.py
As described in the above mentioned paper, bumpy wheel
python main.py --pset bw --k 3 --l 5 --n1_constraints True --forbidden_cycles 3
- point set configurations:
--pset
specifies the type of the underlying point set ('bw' (bumpy wheel), 'gw' (generalized wheel), 'convex', 'random', 'random_wheel', 'two_convex_layers').
--n
specifies the total number of points of the point set (mandatory for all except bw and gw); should usually be an even integer.
--k
and --l
specify the group sizes if pset is bw.
--group_sizes
specifies the sizes of the groups if pset is gw.
- ILP constraints and parameters:
--n1_constraints
enforces
--forbidden_cycles
forbids cycles of certain lengths in any color class (lengths 3 and 4 are possible).
--cover_all_vertices
enforces that there are no isolated vertices in any color class (may help the ILP to find a solution faster).
--timelimit
sets a timelimit for the ILP.
-
$k$ -planar partitions
--k_planar
allows edges to cross at most
- Plotting:
--plot
show plot (true/false).
--draw_labels
draw labels of edges and vertices (true/false).
- Saving data:
--save_data
saves basic data concerning the configurations used, also saves the figure if a solution was found.
--save_data_overview
only saves an overview of the results (useful when running --rand_exp_pst
or --rand_exp_subgraphs
).
--res_dir
specifies the directory for the results (default is "results/").
--no_save
if set to true, the program does not save anything.
- Miscellanious:
--n_colors
specifies the number of available colors (default is
--check_pst
double checks whether partition is really a partition into plane spanning trees and prints a warning to the terminal if not.
- Master commands that overrule certain other commands:
--partition_pst
sets all commands to aim for a partition into spanning trees.
--partition_subgraphs
sets all commands to aim for a partition into subgraphs.
--rand_exp_pst
runs experiment on random point sets for --n_iterations
iterations; aiming to partition into spanning trees.
--rand_exp_subgraphs
runs experiment on random point sets for --n_iterations
iterations; aiming to partition into subgraphs.
- Testing some command line arguments for simple bumpy wheels:
python main.py --pset bw --k 3 --l 3 --partition_pst True --no_save True
python main.py --pset bw --k 3 --l 3 --partition_pst True --no_save True --draw_labels True
python main.py --pset bw --k 3 --l 3 --partition_pst True --no_save True --plot False
python main.py --pset bw --k 5 --l 3 --partition_pst True
- Bumpy
$BW_{3,5}$ cannot be partitioned into plane spanning trees but admits a partition into plane subgraphs (takes 1min to compute):
python main.py --pset bw --k 3 --l 5 --n1_constraints True --forbidden_cycles 3
python main.py --pset bw --k 3 --l 5 --partition_subgraphs True
- Some examples on point sets other than bumpy wheels (note that for
random
andtwo_convex_layers
the partition is likely to not be a partition into spanning trees):
python main.py --pset convex --n 16 --partition_pst True --no_save True
python main.py --pset random --n 14 --partition_pst True
python main.py --pset random_wheel --n 14 --partition_pst True
python main.py --pset two_convex_layers --n 14 --partition_pst True
- Generalized wheels.
python main.py --pset gw --group_sizes 2 3 3 4 5 --n1_constraints True --forbidden_cycles 3 4
Changing the order of the groups allows a partition (1min to compute):
python main.py --pset gw --group_sizes 2 3 4 3 5 --partition_pst True
Also slightly changing
python main.py --pset gw --group_sizes 4 5 6 --partition_pst True
Another example that cannot be partitioned into plane spanning trees, which conforms to Theorem 2.3 (4min to compute):
python main.py --pset gw --group_sizes 5 6 6 --n1_constraints True --forbidden_cycles 3
-
$k$ -plane partitions (cf. Theorem 2.5):
python main.py --pset convex --n 15 --k_planar 1 --n_colors 5 --partition_subgraphs True
python main.py --pset convex --n 15 --k_planar 1 --n_colors 4 --partition_subgraphs True
- Some random experiments:
python main.py --rand_exp_pst True --pset random --n 12 --n_iterations 5
python main.py --rand_exp_pst True --pset random_wheel --n 14 --n_iterations 10
python main.py --rand_exp_subgraphs True --pset random --n 16 --n_iterations 10
python main.py --rand_exp_subgraphs True --pset random --n 18 --n_iterations 20