How do we generate paths through the speaker network with the path lengths as a given constraint? Picking random start (ejected) and end (injected) word will not yield a path of size 30 or higher, and in average be much smaller.
Through experimentation, the following algorithm was devised:
- we generate an initial path from the ejected and injected words using the DFS in the "main" MST
- repeat while the currently generated path length is smaller than the desired path length:
- pick a random edge along the current path
- "cut the path" by removing the edge from the set of all edges
- recreate an MST from all vertices minus the vertices already on
the path, with the exception of the two thus determined boundary
- find the path in the new MST for the two vertices, using again DFS
- splice this new path into the path of the previous iteration at the
- finally, if the resulting path becomes longer than the desired path, drop random elements along the last iteration of the path.
The left hand side shows a path of target length 50 thus generated.