The 8 flags in
1 ... prototype cycles (paths)
2 ... minimum cycles (paths) bases
3 ... relevant cycles (paths)
4 ... shortest cycles (paths)
5 ... unique shortest cycles (paths)
6 ... essential cycles (paths)
7 ... (empty flag)
8 ... is a path
Of course, all cycles and paths have the third flag set.
example:
1 1 1 3 < 1 1 1 1 1 1 0 0 > 3 1 2 3
(This triangle has the cycle number 1, the prototype number 1 and is contained in the interchangeability class number 1. It is a prototype, in the calculated minimum cycle basis, is a relevant, shortest, unique shortest and essential cycle, but not a path. The triangle contains the nodes 1, 2 and 3.)
Note. cycdeco takes the last argument as graphfile.
OPTIONS
- -l
- graphfile contains a list of of GML-graph files, separated by newline. The calculations are done separately for each file in the list. The output is also given separately for each file
- -U unodefile
- Calculate the cycle and U-path bases. unodefile has to contain the ids of the nodes (just integers) of the graph separated by spaces, e.g.: 1 5 9.
- -m
- Do not calculate all cycle (path) sets, but only a minimum cycle (path) bases.
- -r
- Do not calculate all cycle (path) sets, but only a minimum cycle (path) bases and the set of relevant cycles (paths).
- -u
- Do not calculate the interchangeability classes and essential cycles (paths).
- -q
- All calculations are done, but the cycles and paths are not written to a file. This option is only reasonalbe, if just length distributions are needed and therefore -s is given.
- -s
- Calculate a length distribution of the cycles and paths and write it into a file called "graphfile.cycle_stat", not deleting the file, just appending on the end. In the first line the appearing length are given, then the distributions for a minimum cycle (path) basis, the set of relevant, shortest, unique shortest and essential cycles (paths) are given.
- -h -?
- Display a short help message and exit
REFERENCES
The calculation of the minium cycle bases is based on an algorithm originally developed by J. D. Horton, modified by Ph. Vismara. The algorithm for the prototypes of relevant cycles and relevant cycles is based on work by Ph. Vismara. The calculation of the interchangeability classes and the concept of U-Path bases is based on work by P. M. Gleiss and J. Leydold and P. F. Stadler. If you use this program in your work you might want to cite:P. M. Gleiss and P. F. Stadler. "Relevant cycles in biopolymers and random graphs. Presented at the Fourth Slovene International Conference in Graph Theory, Bled, Slovenia (Santa Fe Institute Preprint 99-07-042, Santa Fe Institute), 1999.
P. M. Gleiss, J. Leydold, and P. F. Stadler "Interchangeability of relevant cycles in graphs" "Elec. J. Comb., 7:R16 [16pages], 2000 (See Electr. J. Comb.)
P. M. Gleiss, J. Leydold, and P. F. Stadler "A note On Minimum Path Bases"
J. D. Horton "A polynomial-time algorithm to find the shortest cycle basis of a graph." SIAM J. Comput., 16:359--366, 1987
P. Vismara "Union of all the minimum cycle bases of a graph" Electr. J. Comb., 4:73--87, 1997 (Paper No. #R9 (15 pages), see Electr. J. Comb.)
