paths method
Returns a list containing all paths connecting start
and target
.
Implementation
List<List<T>> paths(T start, T target) {
final pathList = <List<T>>[];
// // Retrieve vertex tree.
// final tree = mappedTree(start);
// if (tree.containsKey(target)) {
// for (final branch in tree[target]!) {
// pathList.add(<T>[start, ...branch]);
// }
// }
final tree = <Set<T>>[];
for (final connected in edges(start)) {
if (connected == target) {
// Add to list of paths
pathList.add([start, target]);
} else if (connected == start) {
// Do not follow self-loops.
continue;
} else {
// Store first branches of tree.
tree.add({connected});
}
}
// There is no other path (except for self-loops from `start` to `start`).
if (tree.isNotEmpty) {
var startIndex = 0;
var endIndex = 0;
var length = tree.length;
do {
endIndex = tree.length;
for (var i = startIndex; i < endIndex; ++i) {
final path = tree[i];
for (final vertex in edges(path.last)) {
// Discard walks which reach the same (inner) vertex twice.
// Note: Each path starts with [start] even though it is not
// listed!
if (path.contains(vertex) || path.contains(start)) {
continue;
} else {
if (vertex == target) {
// Store detected path:
pathList.add([start, ...path, vertex]);
} else {
// Continue growing tree.
tree.add({...path, vertex});
length++;
}
}
}
}
startIndex = endIndex;
} while (endIndex < length);
}
return pathList;
}