Library for working with problems similar to Defensive Alliance.
Written to help with experiments for my Masters Thesis.
If you use this, please verify the implementations! There may be bugs!
The library is fairly functional in design.
You pass graphs with parameters into solvers, and get an Optional[Alliance]
out.
Based on NetworkX.
The core Alliance classes are based on a VertexSet, which represents a set of nodes in a graph, and extended with constraints that get tested on construction. If an Alliance is constructed that doesn't meet the constraints, an exception is thrown.
Algorithms are split into three categories:
- ILP Solvers - Often the best choice for your problems.
- Z3 based Solvers - SMT based solutions often perform well, but not as good as ILP.
- Direct Approaches - More direct algorithms.
- Heuristics - Experimental heuristics, not bounded (beyond every vertex in a -1-DA being an alliance.)
Some variants require specific solvers to represent.
This isn't overly focused on performance, as these algorithms being implemented are exponential in some cases. (As the focus of my thesis is parameterized complexity.)
Setup a virtual environment, and use poetry to install the dependencies.
There is a makefile setup with some useful tests (type checking, linting,
tests):
Run make to set those up.
Check examples/ for some sample scripts.
MIT