I don't know the proper name for this connected component, yet what I'm looking for is to form paths with all possible combinations of a list of pairs/edges. Given a list:
("A", "B")
("A", "C")
("A", "D")
("C", "D")
("D", "B")
("D", "E")
("E", "F")
I would like my output similar to this:
("A", "B")
("B", "A")
("A", "C")
("C", "A")
("A", "D")
("D", "A")
("C", "D")
("D", "C")
...
("A", "B", "D")
("A", "C", "D")
("A", "D", "B")
("A", "D", "C")
("A", "D", "E")
("B", "A", "C")
("B", "A", "D")
("B", "D", "A")
("B", "D", "C")
("B", "D", "E")
...
("A", "B", "D", "E")
("A", "C", "D", "E")
...
("A", "B", "D", "E", "F")
...
("F", "E", "D", "B", "A")
I will need no more than four to five combinations (depending on how large is the output).
Vaguely related to what I'm looking for, I found in more_itertools.distinct_permutations and networkx.algorithms.clique.enumerate_all_cliques
Your task can be easily solved through regular Depth First Search approach of Graph traversal using Recursive function.
My code below fully implements this approach. Just call all_paths() function with given list of edges and it will return all possible paths up to desired maximal length.
This function has some extra params allow_same_vertices = False, allow_same_edges = False, max_length = 5. First param says if it is allowed to repeat same vertices twice within single path. Second says if it is allowed to repeat same edge twice (sometimes it might be allowed to repeat same vertex but not same edge). Third param says what is allowed maximal length of the path.
How this Depth First Search works: Recursive function starts with some vertex, then it tries to visit all neighbours of this vertex (by following all edges from current vertex), if neighour is present in set of visited vertices then this neighour is skipped, otherwise neighbour is added to visited vertices and added to the path and recursive function is called again with this neighbour as argument. After recursive call is finished, neighbour is removed from path and from visited vertices.
This kind of recursive depth first search traversal of a graph is guaranteed to visit ALL possible paths, it is a well known algorithm.
def all_paths(edges, *, allow_same_vertices = False, allow_same_edges = False, max_length = 5):
neighbours = {None: []}
for a, b in edges:
for i in range(2):
if a not in neighbours[None]:
neighbours[None].append(a)
if a not in neighbours:
neighbours[a] = []
if b not in neighbours[a]:
neighbours[a].append(b)
a, b = b, a
visited_edges = {}
visited_vertices = {}
paths = set()
path = []
def rec(vertex):
if len(path) >= 2:
paths.add(tuple(path))
if len(path) >= max_length:
return
for neighbour in neighbours.get(vertex, []):
if not allow_same_vertices and visited_vertices.get(neighbour, 0) > 0:
continue
if not allow_same_edges and visited_edges.get((vertex, neighbour), 0) > 0:
continue
visited_vertices[neighbour] = visited_vertices.get(neighbour, 0) + 1
visited_edges[(vertex, neighbour)] = visited_edges.get((vertex, neighbour), 0) + 1
path.append(neighbour)
rec(neighbour)
path.pop()
visited_vertices[neighbour] -= 1
visited_edges[(vertex, neighbour)] -= 1
rec(None)
return sorted(paths, key = lambda e: (len(e), e))
def main():
for path in all_paths([
("A", "B"),
("A", "C"),
("A", "D"),
("C", "D"),
("D", "B"),
("D", "E"),
("E", "F"),
], max_length = 4):
print(path)
main()
Input:
("A", "B"),
("A", "C"),
("A", "D"),
("C", "D"),
("D", "B"),
("D", "E"),
("E", "F"),
Output:
('A', 'B')
('A', 'C')
('A', 'D')
('B', 'A')
('B', 'D')
('C', 'A')
('C', 'D')
('D', 'A')
('D', 'B')
('D', 'C')
('D', 'E')
('E', 'D')
('E', 'F')
('F', 'E')
('A', 'B', 'D')
('A', 'C', 'D')
('A', 'D', 'B')
('A', 'D', 'C')
('A', 'D', 'E')
('B', 'A', 'C')
('B', 'A', 'D')
('B', 'D', 'A')
('B', 'D', 'C')
('B', 'D', 'E')
('C', 'A', 'B')
('C', 'A', 'D')
('C', 'D', 'A')
('C', 'D', 'B')
('C', 'D', 'E')
('D', 'A', 'B')
('D', 'A', 'C')
('D', 'B', 'A')
('D', 'C', 'A')
('D', 'E', 'F')
('E', 'D', 'A')
('E', 'D', 'B')
('E', 'D', 'C')
('F', 'E', 'D')
('A', 'B', 'D', 'C')
('A', 'B', 'D', 'E')
('A', 'C', 'D', 'B')
('A', 'C', 'D', 'E')
('A', 'D', 'E', 'F')
('B', 'A', 'C', 'D')
('B', 'A', 'D', 'C')
('B', 'A', 'D', 'E')
('B', 'D', 'A', 'C')
('B', 'D', 'C', 'A')
('B', 'D', 'E', 'F')
('C', 'A', 'B', 'D')
('C', 'A', 'D', 'B')
('C', 'A', 'D', 'E')
('C', 'D', 'A', 'B')
('C', 'D', 'B', 'A')
('C', 'D', 'E', 'F')
('D', 'B', 'A', 'C')
('D', 'C', 'A', 'B')
('E', 'D', 'A', 'B')
('E', 'D', 'A', 'C')
('E', 'D', 'B', 'A')
('E', 'D', 'C', 'A')
('F', 'E', 'D', 'A')
('F', 'E', 'D', 'B')
('F', 'E', 'D', 'C')