Debian Codegraph @

doc/mcxerdos.azm

raw ◀ ▶
Source reconstructed at patch state 0 of 1 — not the installed (fully patched) source.
1 Debian patch touch this file
1 \import{mcx.zmm}
2
3 \begin{pud::man}{
4
5 {name}{mcx erdos}
6 {html_title}{The mcx erdos manual}
7 {author}{Stijn van Dongen}
8 {section}{1}
9 {synstyle}{long}
10 {defstyle}{long}
11
12 \man_share
13 }
14
15 \${html}{\"pud::man::maketoc"}
16
17 \sec{name}{NAME}
18 \NAME{mcx erdos}{compute shortest paths in a graph}
19
20 \sec{synopsis}{SYNOPSIS}
21 \par{
22 \mcx{erdos} [options]}
23
24 \disclaim_mcx{erdos}
25
26 \par{
27 \mcx{erdos}
28 \synoptopt{-query}{<fname>}{query input stream}
29 \synoptopt{-abc}{<fname>}{specify label input}
30 \synoptopt{-imx}{<fname>}{specify matrix input}
31 \synoptopt{-tab}{<fname>}{use tab file}
32 \synoptopt{-o}{<fname>}{output file name}
33 \synoptopt{--is-directed}{input graph is directed}
34 \synoptopt{--is-undirected}{input graph is directed}
35 \synoptopt{-write-path}{<fname>}{path matrix file}
36 \synoptopt{-write-step}{<fname>}{step matrix file}
37 \stdsynopt
38 }
39
40 \sec{description}{DESCRIPTION}
41 \par{
42 \mcx{erdos} computes shortest paths in graphs.
43 It can read a graph either in label format with \genopt{-abc}
44 or in native format with \genopt{-imx}.
45 It reads pairs of node indices from an input stream, and for
46 each pair outputs a data structure describing the full
47 set of shortest paths between the two nodes.
48 Edge weights are not taken into account, so an
49 edge always represents a unit step size between two nodes
50 irrespective of its weight. A mode to compute shortest paths while taking into
51 account edge weights will be implemented later as \mcx{dijkstra}.
52 }
53
54 \par{
55 Note that the full set of shortest paths between two nodes in
56 a graph can be described as a directed acyclic graph (DAG),
57 and this is how \mcx{erdos} operates. It is easy to construct
58 graphs and node pairs for which the number of shortest paths
59 between the two nodes becomes exponential in the size of
60 the graph, whereas the lattice description is always
61 garantueed to map to a subset of the graph edge set.
62 }
63
64
65 \par{
66 By default it is assumed that the input graph should be treated as
67 undirected. To this end a transformation step is applied to ensure that the
68 graph in memory is undirected. It is possible to compute shortest
69 paths in directed graphs by using \genopt{--is-directed}, and
70 it is possible to omit the transformation step by using \genopt{--is-undirected}.
71 If the latter is specified while the input graph is in native format and in
72 fact directed, results will be erroneous. This could in theory be mitigated
73 by checking that the input graph is undirected. However, the reason to use
74 \genopt{--is-undirected} is simply to increase speed of operation, whereas
75 such a check would be equally expensive as the transformation step that is
76 omitted with \genopt{--is-undirected}.
77 }
78
79
80 \par{
81 The input graph/matrix, if specified with the \genopt{-imx} option, has to
82 be in mcl matrix/graph format. You can use label input instead by using the
83 \genopt{-abc} option.
84 Refer to \mysib{mcxio} for a description of these two input formats.
85 By default \mcx{erdos} reads from STDIN \it{and expects matrix format}.
86 To specify label input from STDIN use \useopt{-abc}{-}.
87 }
88
89
90 \sec{options}{OPTIONS}
91
92 \begin{itemize}{\mcx_itemopts}
93
94 \item{\defopt{-query}{<fname>}{query input}}
95 \car{
96 The name for the file from which queries are read.
97 A query consists of two white-space separated node indices
98 or two white-space separated labels. Labels can only be used
99 if either \genopt{-abc} or \genopt{-tab} is specified.
100 }
101
102 \item{\defopt{-abc}{<fname>}{label input}}
103 \car{
104 The file name for input that is in label format.}
105
106 \item{\defopt{-imx}{<fname>}{input matrix}}
107 \car{
108 The file name for input that is in mcl native matrix format.}
109
110 \item{\defopt{-o}{<fname>}{output file name}}
111 \car{
112 The name of the file to write output to.
113 }
114
115 \item{\defopt{-tab}{<fname>}{use tab file}}
116 \car{
117 This option causes the output to be printed with the labels
118 found in the tab file.
119 With \genopt{-abc} this option will, additionally, construct
120 a graph only on the labels found in the tab file.
121 If this option is used in conjunction with \genopt{-imx} the
122 tab domain and the matrix domain are required to be identical.
123 }
124
125 \item{\defopt{--is-directed}{compute directed shortest paths}}
126 \car{
127 The input graph is not transformed and assumed to be directed.
128 Shortest paths are computed taking this into account.
129 }
130
131 \item{\defopt{--is-undirected}{skip symmetrification step}}
132 \car{
133 The input graph is not transformed and assumed to be undirected.
134 Shortest paths are computed on the assumption that the input
135 is undirected. Use this option only if you are sure the input
136 is undirected and need to have faster execution.
137 }
138
139 \items{
140 {\defopt{-write-path}{<fname>}{path matrix file}}
141 {\defopt{-write-step}{<fname>}{step matrix file}}
142 }
143 \car{
144 The path matrix enumerates the nodes that take
145 part in all shortest paths. The first list contains
146 those nodes that lie at distance 1 of the source node,
147 the second list contains nodes lying at distance 2,
148 and so on.
149 The step matrix contains all the edges that make up
150 the lattice of shortest paths between the two query nodes.
151 }
152
153 \end{itemize}
154
155
156 \sec{seealso}{SEE ALSO}
157 \par{
158 \mysib{mcxio},
159 and \mysib{mclfamily} for an overview of all the documentation
160 and the utilities in the mcl family.}
161
162 \end{pud::man}
163