MCXERDOS(1)

💖 mcx erdos — a manual page, but make it a group chat 💖

okay bestie, so this is the manual page for mcx erdos(1), a USER COMMANDS situation, and we're about to make shortest paths your whole personality. no cap. 🦋

---

✨ NAME ✨

mcx_erdos — compute shortest paths in a graph. that's it. that's the girl. 👑

---

🌸 SYNOPSIS 🌸

mcx erdos [options]

lowkey plot twist incoming: mcxerdos is not in actual fact a program. 😭 this manual page documents the behaviour and options of the mcx program when invoked in mode erdos. so like, it's a mode, not a standalone bestie.

also, the options -h, --apropos, --version, -set, --nop, -progress <num> are accessible in all mcx modes. they're described in the mcx manual page. iykyk. 💅

here's the full vibe, verbatim:

mcx erdos [-query <fname> (query input stream)] [-abc <fname> (specify
label input)] [-imx <fname> (specify matrix input)] [-tab <fname> (use
tab file)] [-o <fname> (output file name)] [--is-directed (input graph is
directed)] [--is-undirected (input graph is directed)] [-write-path
<fname> (path matrix file)] [-write-step <fname> (step matrix file)] [-h
(print synopsis, exit)] [--apropos (print synopsis, exit)] [--version
(print version, exit)]

---

🎀 DESCRIPTION 🎀

okay so mcx erdos computes shortest paths in graphs. it can read a graph either in label format with -abc or in native format with -imx. it reads pairs of node indices from an input stream, and for each pair it outputs a data structure describing the full set of shortest paths between the two nodes. the way that it just… does that. iconic. ✨

🚨 important, bestie: edge weights are not taken into account. an edge always represents a unit step size between two nodes, irrespective of its weight. a mode to compute shortest paths while taking edge weights into account will be implemented later as mcx dijkstra. so hold that thought. 💀

now, note that the full set of shortest paths between two nodes in a graph can be described as a directed acyclic graph (DAG), and this is how mcx erdos operates. it is easy to construct graphs and node pairs for which the number of shortest paths between the two nodes becomes exponential in the size of the graph, whereas the lattice description is always garantueed to map to a subset of the graph edge set. so the lattice is the moment, fr fr. 🌈

by default it is assumed that the input graph should be treated as undirected. to this end a transformation step is applied to ensure that the graph in memory is undirected. it is possible to compute shortest paths in directed graphs by using --is-directed, and it is possible to omit the transformation step by using --is-undirected.

⚠️ if --is-undirected is specified while the input graph is in native format and in fact directed, results will be erroneous. this could in theory be mitigated by checking that the input graph is undirected. however, the reason to use --is-undirected is simply to increase speed of operation, whereas such a check would be equally expensive as the transformation step that is omitted with --is-undirected. so like, no free lunch. 🍓

the input graph/matrix, if specified with the -imx option, has to be in mcl matrix/graph format. you can use label input instead by using the -abc option. refer to mcxio(5) for a description of these two input formats. 📚

by default mcx erdos reads from STDIN and expects matrix format. to specify label input from STDIN use -abc -. 💅

---

💜 OPTIONS 💜

• -query <fname> — (query input) the name for the file from which queries are read. a query consists of two white-space separated node indices or two white-space separated labels. labels can only be used if either -abc or -tab is specified. bestie, that's the whole rule. 🫶
• -abc <fname> — (label input) the file name for input that is in label format. cute and labeled, we love her. 🎀
• -imx <fname> — (input matrix) the file name for input that is in mcl native matrix format. the classic. ✨
• -o <fname> — (output file name) the name of the file to write output to. 📝
• -tab <fname> — (use tab file) this option causes the output to be printed with the labels found in the tab file. with -abc this option will, additionally, construct a graph only on the labels found in the tab file. if this option is used in conjunction with -imx the tab domain and the matrix domain are required to be identical. no negotiating on that one. 💅
• --is-directed — (compute directed shortest paths) the input graph is not transformed and assumed to be directed. shortest paths are computed taking this into account. main character energy for directed graphs. 👑
• --is-undirected — (skip symmetrification step) the input graph is not transformed and assumed to be undirected. shortest paths are computed on the assumption that the input is undirected. use this option only if you are sure the input is undirected and need to have faster execution. speed over caution, but like, know what you're doing. 🔥
• -write-path <fname> — (path matrix file) 🦋
• -write-step <fname> — (step matrix file) 🦋

so these two share a description and it's giving lore drop: the path matrix enumerates the nodes that take part in all shortest paths. the first list contains those nodes that lie at distance 1 of the source node, the second list contains nodes lying at distance 2, and so on. the step matrix contains all the edges that make up the lattice of shortest paths between the two query nodes. obsessed with how structured that is. 💖

---

🌟 SEE ALSO 🌟

mcxio(5), and mclfamily(7) for an overview of all the documentation and the utilities in the mcl family. go read them, bestie, they're family. 🫶

---

and that's the whole page, no notes. this was mcx erdos, version 22-282, dated 9 Oct 2022 — mwah, periodt. 💅✨🎀