Welcome to the cycle-bases toolkit for the study of graph cycle bases. This project aims to calculate minimal cycle bases for a given graph. Originally initiated by Prof. Dr. Peter Stadler and Dr. Christian Höner zu Siederdissen, this project was developed as part of the course "Advanced Methods of Bioinformatics." The toolkit includes several algorithms and functions, including horton, edge-short-cycles, gauss, dijkstra, and de-pina. Graph operations within the toolkit are generalized over all finite fields (prime fields). For more in-depth information, please refer to the project's wiki.
Authors: Simon Johanning and Camill Kaipf
To use the cycle-bases toolkit, follow these steps:
-
Install Stack, a Haskell build tool.
-
Read the
test/Spec.hsfile, which includes the test execution details. -
Run the tests using Stack:
stack test
The toolkit assumes graphs in a specific format:
- Graphs are imported from an adjacency list.
- Each entry in the adjacency list contains a 4-tuple
(tail, head, edge, weight). - The edge label (integer) corresponds to the unnested adjacency list, with enumeration starting from 1.
- All graphs are treated as directed graphs with unique edges.
Check the test/ directory for example input files.
The cycle-bases toolkit provides several algorithms and functions:
- horton: Implementation of the Horton's algorithm.
- edge-short-cycles: Algorithm for detecting short cycles based on edges.
- gauss: Gauss elimination algorithm for cycle detection.
- dijkstra: Dijkstra's algorithm for cycle detection.
- de-pina: De Pina's algorithm for finding fundamental cycles in planar graphs.
Graph operations within the toolkit are generalized over all finite fields, specifically prime fields.
For more detailed information about individual algorithms, usage examples, and further details, please refer to the project's wiki.