DiGraphillion is a Python software package on search, optimization, and enumeration for a directed graphset, or a set of digraphs.
see also Graphillion.
- Linux/Mac OS
- 64-bit machines
- Python version 3.6 or later
- Python development environment (
Python.h)- It is included with XCode in macOS, while it can be installed by
apt install python-devin Ubuntu.
- It is included with XCode in macOS, while it can be installed by
- GCC or Clang
- To build Graphillion, you need gcc version 5.4.0 or later.
- Clone the Graphillion repository
git clone https://github.com/ComputerAlgorithmsGroupAtKyotoU/digraphillion.git - Change directory to "digraphillion"
- Run python
setup.py buildto build - (optional) Run
python setup.py test -qto execute the tests
pip install -U graphillionbefore testing.
- Run
sudo python setup.py installto install
- see also Graphillion.
| Term | Description | Example |
|---|---|---|
| vertex | any hashable object | 1, 'v1', (x, y) |
| directed edge | tuple of vertices | (1, 2), (2, 1) |
| digraph | list of directed edges | [(1, 2), (2, 1), (1, 3)] |
| set of digraphs | DiGraphSet object | DiGraphSet([[(1, 2), (1, 3)], [(1, 2), (2, 1)]]) |
- the order of vertices is important.
- directed edge
(1, 2)is not equal to(2, 1).
- directed edge
- self-loop edges and multiedges are NOT supported. Incorrect solutions may be obtained.
- You can use
GraphSetwithDiGraphSetin the same program. However,GraphSetandDiGraphSetare incompatible.- see also
digraphillion/test/test_digraphillion.py.
- see also
| Method | Description |
|---|---|
gs.graphs(in_degree_constraints, out_degree_constraints) |
Returns a new DiGraphSet with degree constraints from gs |
gs.directed_cycles() |
Returns a new DiGraphSet with directed single cycles from gs |
gs.directed_hamiltonian_cycles() |
Returns a new DiGraphSet with directed single hamiltonian cycles from gs |
gs.directed_st_paths(s, t, is_hamiltonian) |
Returns a new DiGraphSet with directed st path from gs |
gs.rooted_forests(roots, is_spanning) |
Returns a new DiGraphSet with rooted forests from gs |
gs.rooted_trees(root, is_spanning) |
Returns a new DiGraphSet with rooted trees from gs |