Given a chordal graph, this package provides functions to update the graph ensuring its chordality. It is based on the first of the two implementations described in
Ibarra, Louis. "Fully dynamic algorithms for chordal graphs and split graphs" ACM Transactions on Algorithms (TALG) (2008).
The add_edge
and update_insertable(v)
operations costs O(n), where n is
the number of nodes in the graph.
You can install the cliquetree package by executing the following command in a terminal.
pip install git+https://github.com/harrymvr/cliquetree#Egg=cliquetree
For instructions on how to use the package, consult its documentation.
To run all the tests for the code, you will need tox -- check its webpage for instructions on how to install it.
Once tox is installed, use your terminal to enter the directory with the local copy of the code (here it's named 'cliquetree') and simply type the following command.
cliquetree $ tox
If everything goes well, you'll receive a congratulatory message.
Note that the code is distributed under the Open Source Initiative (ISC) license. For the exact terms of distribution, see the LICENSE.
Copyright (c) 2016, cliquetree contributors, Charalampos Mavroforakis <[email protected]>