Where can I get to from each location? (Transitive Closure)
Given an undirected graph (network) \$G\$, construct a new graph in which vertex (node) pair \$(u,v)\$ is an edge (are connected) if and only if a path \$(u,w_1,w_2,...,w_k,v)\$ exists in \$G\$ for some \$k\ge 0\$. This is known as \$G\$'s transitive closure. If this is clear to you, you're ready to get started. Otherwise, just read through the below sections. It is actually a very simple problem.
I/O formats
Take for example the graph (network)
1──2 3──4
│ │
5 6──7──8
We can represent¹ it as an adjacency (connection) matrix:
│1 2 3 4 5 6 7 8
─┼───────────────
1│ ┘
2│
3│ ┘
4│
5│┘
6│ ┘
7│ ┘ ┘
8│
which is:
[[0,1,0,0,0,0,0,0],[0,0,0,0,0,0,0,0],[0,0,0,1,0,0,0,0],[0,0,0,0,0,0,0,0],[1,0,0,0,0,0,0,0],[0,0,0,0,0,0,1,0],[0,0,0,1,0,0,0,1],[0,0,0,0,0,0,0,0]]
Note that here only one of \$(u,v),(v,u)\$ is represented, but we consider both directions as valid edges (connections).
Or as a list of of edges²:
[[1,2],[1,5],[3,4],[5,1],[6,7],[7,3],[7,8]]
Or for each vertex³ (node), the list of its adjacent vertices:
[[2,5],[1],[7,4],[1],[7],[3,8],[8],[]]
Or as a dictionary⁴:
{"1":[2,5],"3":[7,4],"7":[6,3,8]}
Any of these, and any other reasonable input and output formats (you optionally may use one format for input and another for output) are allowed, but you must state what your formats are.
However, it is required that your formats support under-representing (e.g. [3,7]
but not [7,3]
) and over-representing (e.g. both [3,7]
and [7,3]
).
Walk-through
Let's use the representation [[1,2],[1,5],[3,4],[5,1],[6,7],[7,3],[7,8]]
. Since 1 is connected to 2 then 2 is also connected to 1, so we add (it doesn't matter where) this edge (connection):
[[1,2],[1,5],[2,1],[3,4],[5,1],[6,7],[7,3],[7,8]]
It is also possible to travel [1,5]
in reverse, but that pair is already represented further in the list. Now note that it is possible to find a path from 2 to 5, and vice versa, via 1, so we add these two edges:
[[1,2],[1,5],[2,1],[2,5],[5,2],[3,4],[5,1],[6,7],[7,3],[7,8]]
This completes the left side of the graph. Similarly, we process the right side by adding the reversals of [3,4]
, [6,7]
, and [7,3]
:
[[1,2],[1,5],[2,1],[2,5],[5,2],[3,4],[5,1],[6,7],[7,3],[7,8],[4,3],[7,6],[7,3]]
Two-step paths via 3 are possible, so we add [7,4]
and [4,7]
. Similarly, two-step paths via 7 are [6,3]
, [3,6]
, [6,8]
, [8,6]
, [3,8]
, and [8,3]
:
[[1,2],[1,5],[2,1],[2,5],[5,2],[3,4],[5,1],[6,7],[7,3],[7,8],[4,3],[7,6],[7,3],[7,4],[4,7],[6,3],[3,6],[6,8],[8,6],[3,8],[8,3]]
Finally, we add the three-step paths [6,4]
, [4,6]
, [4,8]
, and [8,4]
:
[[1,2],[1,5],[2,1],[2,5],[5,2],[3,4],[5,1],[6,7],[7,3],[7,8],[4,3],[7,6],[7,3],[7,4],[4,7],[6,3],[3,6],[6,8],[8,6],[3,8],[8,3],[6,4],[4,6],[4,8],[8,4]]
And this is our answer. It could of course be in any order.
- Though the connections do not have direction, I've only put in one entry in the table for each connection, and obviously the diagonal is all-true too, as every node is reachable from itself.
- Since the connections in this challenge do not have a direction,
[1,5]
and [5,1]
are the same connection. This serves to illustrate that such may occur in the given data.
- Here, each node must have its own list, as the lists are paired to their points by their position in the data. However, each list need not be exhaustive as long as all connections are represented somewhere.
- Here, we can omit entries that are fully covered by the other entries.
code-golf path-finding graph-theory