gave the membership in the different cycle/path
sets:
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.)
AUTHORS
Petra M. Gleiss, Peter F. Stadler
BUGS
Comments should be sent to xtof@bioinf.uni-leipzig.de