Let’s say I have 5 points in graph, v = [0,1,2,3,4].
The list with all possible combinations would look like this:
[(), (0,), (1,), (2,), (3,), (4,), (0, 1), (0, 2), (0, 3), (0, 4), (1, 2), (1, 3), (1, 4),
(2, 3), (2, 4), (3, 4), (0, 1, 2), (0, 1, 3), (0, 1, 4), (0, 2, 3), (0, 2, 4), (0, 3, 4),
(1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4), (0, 1, 2, 3), (0, 1, 2, 4), (0, 1, 3, 4),
(0, 2, 3, 4), (1, 2, 3, 4), (0, 1, 2, 3, 4)]
Now lets say I have the following edges:
[(0, 3), (1, 2), (2, 3), (2, 4), (3, 4)]
Lets take the (0,3) for example. As you can see that is a edge in the graph so all the combinations with 0 and 3 should be discarded, like (0,3), (0,1,3), etc.
How can I make a code that uses a condition to verify if the possible combination as 2 adjacent vertices?
The code to generate the possible combinations is the following:
list_combinations = list()
for n in range(len(N_vert) + 1):
list_combinations += list(combinations(vert, n))
n_comb = len(list_combinations)
>Solution :
You could check, for each combination, is one edge is a subset of it
vert = [0, 1, 2, 3, 4]
edges = [(0, 3), (1, 2), (2, 3), (2, 4), (3, 4)]
edges = [set(edge) for edge in edges]
list_combinations = []
for n in range(len(vert) + 1): # start loop at 1 to remove the empty tuple
for comb in combinations(vert, n):
if not any(edge.issubset(comb) for edge in edges):
list_combinations.append(comb)
print(list_combinations)
# [(), (0,), (1,), (2,), (3,), (4,), (0, 1), (0, 2), (0, 4), (1, 3), (1, 4), (0, 1, 4)]