summaryrefslogtreecommitdiff
path: root/doc/johnson_cycles.md
diff options
context:
space:
mode:
authorKatolaZ <katolaz@freaknet.org>2017-09-27 15:06:31 +0100
committerKatolaZ <katolaz@freaknet.org>2017-09-27 15:06:31 +0100
commit3aee2fd43e3059a699af2b63c6f2395e5a55e515 (patch)
tree58c95505a0906ed9cfa694f9dbd319403fd8f01d /doc/johnson_cycles.md
First commit on github -- NetBunch 1.0
Diffstat (limited to 'doc/johnson_cycles.md')
-rw-r--r--doc/johnson_cycles.md171
1 files changed, 171 insertions, 0 deletions
diff --git a/doc/johnson_cycles.md b/doc/johnson_cycles.md
new file mode 100644
index 0000000..bf2d92f
--- /dev/null
+++ b/doc/johnson_cycles.md
@@ -0,0 +1,171 @@
+johnson_cycles(1) -- Enumerate the simple cycles of a graph
+======
+
+## SYNOPSIS
+
+`johnson_cycles` <graph_in> [<max_length> [SHOW]]
+
+## DESCRIPTION
+
+`johnson_cycles` enumerates all the simple cycles of the graph given
+on input, and prints the total number of cycles of each length. If
+<max_length> is provided, `johnson_cycles` ignores any cycle whose
+length is larger than <max_length>. If `SHOW` is given as third
+argument, all the found cycles are printed on STDERR as soon as they
+are found.
+
+## PARAMETERS
+
+* <graph_in>:
+ input graph (edge list) if equal to `-` (dash), read the edge list
+ from STDIN.
+
+* <max_length>: The maximum length of cycles to count/print. If not
+ provided, `johnson_cycles` tries to find all the cycles of the
+ graph (see the **WARNING** in the section [OUTPUT][] below).
+
+* SHOW:
+ If the third (optional) parameter is equal to `SHOW`, the program
+ will dump on the standard error all the cycles found.
+
+## OUTPUT
+
+`johnson_cycles` prints on the standard output the number of cycles of
+each length, in the format:
+
+ 2 N_2
+ 3 N_3
+ 4 N_4
+ 5 N_5
+ ...
+
+where 2, 3, 4, 5... is the cycle lengths and N_2, N_3, N_4, N_5... is
+(twice) the number of cycles of that length. If `SHOW` is given, each
+cycle is also printed on STDERR as soon as it is found, in the format:
+
+ node_l node_(l-1) node_(l-2) ... node_0
+
+where `node_l`, `node_(l-1)`, etc. are the labels of the nodes
+belonging to the cycle which starts at node `node_0`.
+
+**WARNING**: If the second parameter <max_length> is not provided,
+ `johnson_cycles` will try to enumerate **all** the cycles of the
+ graph. In general, this might take a time **exponential** in the
+ number of nodes and edges of the graph. As a consequence, specifying
+ a maximum length is **highly recommended** if you are not interested
+ in finding the number of cycles of any length.
+
+
+## EXAMPLES
+
+We can count the cycle of any length in the graph of Florentine
+families using the command:
+
+ $ johnson_cycles florentine.net
+ 2 20
+ 3 6
+ 4 4
+ 5 6
+ 6 10
+ 7 20
+ 8 22
+ 9 8
+ 10 2
+ 11 0
+ 12 0
+ 13 0
+ 14 0
+ 15 0
+ 16 0
+ $
+
+The output means that the graph has 20 cycles of length 2 (edges),
+6/2=3 cycles of length 3, 4/2=2 cycles of length 4, and so on. We
+could otherwise focus on the cycles of length up to 5 and have each
+cycle printed on output:
+
+ $ johnson_cycles florentine.net 5 SHOW
+ 8 0
+ 5 1
+ 8 15 6 1
+ 8 12 15 6 1
+ 6 1
+ 6 15 12 8 1
+ 6 15 8 1
+ 8 1
+ 8 12 14 4 2
+ ....
+ 15 12
+ 2 20
+ 3 6
+ 4 4
+ 5 6
+ $
+
+Apart from the degenerate cycles like "8 0", "5 1", etc.,
+corresponding to the cycles obtained by traversing the same undirected
+edge in the two possible directions, we see in that list some of the
+cycles of length 4 (such as "8 15 6 1") and of length 5 (such as "8 12
+15 6 1").
+
+The enumeration of all the cycles is normally impractical on larger
+graphs, so it is highly recommended to limit the search to short
+sizes. For instance, the command:
+
+ $ johnson_cycles er_1000_5000.net 6
+ 2 5000
+ 3 340
+ 4 2406
+ 5 19416
+ 6 160554
+ $
+
+will require less than one second on a modern desktop computer, but
+the command:
+
+ $ johnson_cycles er_1000_5000.net 7
+ 2 5000
+ 3 340
+ 4 2406
+ 5 19416
+ 6 160554
+ 7 1360104
+ $
+
+will probably take about 15 seconds, while:
+
+ $ johnson_cycles er_1000_5000.net 8
+ 2 5000
+ 3 340
+ 4 2406
+ 5 19416
+ 6 160554
+ 7 1360104
+ 8 11743500
+ $
+
+will run for more than 2 minutes, and larger cycle lengths will
+require exponentially more time.
+
+
+## SEE ALSO
+
+f3m(1), shortest(1)
+
+## REFERENCES
+
+* D\. B. Johnson. "Finding All the Elementary Circuits of a Directed
+ Graph". SIAM J. Comput. 4 (1975), 77-84.
+
+* V\. Latora, V. Nicosia, G. Russo, "Complex Networks: Principles,
+ Methods and Applications", Chapter 8, Cambridge University Press
+ (2017)
+
+* V\. Latora, V. Nicosia, G. Russo, "Complex Networks: Principles,
+ Methods and Applications", Appendix 15, Cambridge University Press
+ (2017)
+
+
+## AUTHORS
+
+(c) Vincenzo 'KatolaZ' Nicosia 2009-2017 `<v.nicosia@qmul.ac.uk>`.