Shortest paths #22
Description
Create a method for hypergraphs that, given two edges, e1 and e2, finds the set of shortest paths from one to the other.
To illustrate, this edge is itself the shortest path between e1 and e2:
(is/P e1 e2)
Or, if only the following two edges exist, they are the shortest path between e1 and e2:
(is/P e1 e3)
(likes/P e3 e2)
Or, there could be multiple shortest paths:
(is/P e1 e3)
(likes/P e3 e4)
(hates/P e3 e4)
(equals/P e4 e2)
And so on.
Notice that naive solutions to this problem lead to combinatorial explosion. Depending also on the topology of the hypergraph in question, the search space could increase exponentially with the length of the shortest path.
Proposals
Several approaches are possible here, to be decided:
- Implement the naive method for now, with a simple heuristic (e.g. maximum number of visited nodes) to give up;
- Implement some non-naive approach that uses optimizations and heuristics to tame the combinatorial explosion, possibly not guaranteeing complete results for large shortest path lengths;
- Implement a meta-solution that can be extended with new approaches in the future. Above approaches (naive, mixed) can be included. This makes sense if we figure that the problem has sufficient depth (e.g. there could be different notions of neighborhood, such as a recursive one).