| 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 |
|