Generating all possible 3-connected graphs
There is a conjecture by Tutte and Thomassen (Planarity and duality of finite and infinite graphs, 1979) saying this
A 3-connected graph can be obtained from a wheel by succestively adding an edge and splitting a vertex into two adjacent vertices of degree at least three such that the edge joining them is not contained in a 3-cycle. If we apply a more general splitting operation (i.e., we allow the edge joining the two new vertices to be contained in a 3-cycle) then we can start out with K_4, and we need only the splitting operation in order to generate all 3-connected graphs.
I am trying to implement the last stated operation using iGraph with Python.
I want to define a function splitVertex(g,v), taking a graph g and a vertex v, and then have it split v in all the possible ways as the operation defines. Then I want a list of all these new graphs, and I will do some further work on them.
At this point, I have the following function creating two new vertices x and y, which would be the newly created vertices after the split.
def splitVertex(g,v):
numver = g.vcount()
g.add_vertices(2)
x = numv开发者_Python百科er
y = numver+1
g.add_edges([(x,y)])
Can somebody please help me out with a nice way to implement this? I know this will generate a massive amount of data, but that is alright, I have plenty of time ;)
Edit: Of course this have to be controlled in some way since the number of 3-connected graphs is infinite, but that is not what this question concerns.
Your splitting operation should be a bit more involved. You need to modify all the edges that used to connect to v
to connect to x
or y
instead.
def splitVertex(g,v):
numver = g.vcount()
g.add_vertices(2)
x = numver
y = numver+1
g.add_edges([(x,y)])
neighbors = g.neighbors(v)
g.delete_vertices([v])
new_graphs = []
for (neighbors_of_x, neighbors_of_y) in set_split(neighbors):
if len(neighbors_of_x) < 2: continue
if len(neighbors_of_y) < 2: continue
g2 = g.copy()
g2.add_edges(map(lambda neighbor_of_x: [neighbor_of_x, x], neighbors_of_x))
g2.add_edges(map(lambda neighbor_of_y: [neighbor_of_y, y], neighbors_of_y))
new_graphs.add(g2)
return new_graphs
Where set_split
should generate all possible ways of splitting neighbors
into two sets.
You then need to generate all possible choices for v
and apply them to each graph.
You will likely get lots of isomorphic graphs. I imagine there is a better way to do all of this, can't think of it off the top of my head.
Based on Keith's solution. This is totally untested, but I guess the general idea is OK. This version generates the splits instead of returning all of them at once.
from itertools import chain, combinations
def powerset(iterable):
"Returns all the possible subsets of the elements in a given iterable"
s = list(iterable)
return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))
def partition(iterable):
"Returns all the possible ways to partition a set into two subsets"
s = set(iterable)
for s1 in powerset(s):
yield s1, s-s1
def split_vertex(graph, v1):
# Note that you only need one extra vertex, you can use v for the other
v2 = graph.vcount()
graph.add_vertices(1)
# Find the neighbors of v1
neis = set(graph.neighbors(v1))
# Delete all the edges incident on v1 - some of them will be re-added
g.delete_edges(g.incident(v1))
# Iterate over the powerset of neis to find all possible splits
for set1, set2 in partition(neis):
if len(set1) < 2 or len(set2) < 2:
continue
# Copy the original graph
g2 = g.copy()
# Add edges between v1 and members of set1
g2.add_edges([(v1, v3) for v3 in set1])
# Add edges between v2 and members of set2
g2.add_edges([(v2, v3) for v3 in set2])
# Return the result
yield g2
精彩评论