Skip to content

Instantly share code, notes, and snippets.

@rburing
Last active March 3, 2021 15:25
Show Gist options
  • Save rburing/8854254 to your computer and use it in GitHub Desktop.
Save rburing/8854254 to your computer and use it in GitHub Desktop.
import networkx as nx
def contract_edges(G,nodes, new_node, attr_dict=None, **attr):
'''Contracts the edges of the nodes in the set "nodes" '''
#Add the node with its attributes
G.add_node(new_node, attr_dict, **attr)
#Create the set of the edges that are to be contracted
cntr_edge_set = G.edges(nodes, data = True)
#Add edges from new_node to all target nodes in the set of edges that are to be contracted
#Possibly also checking that edge attributes are preserved and not overwritten,
#especially in the case of an undirected G (Most lazy approach here would be to return a
#multigraph so that multiple edges and their data are preserved)
G.add_edges_from(map(lambda x: (new_node,x[1],x[2]), cntr_edge_set))
#Remove the edges contained in the set of edges that are to be contracted, concluding the contraction operation
G.remove_edges_from(cntr_edge_set)
#Remove the nodes as well
G.remove_nodes_from(nodes)
#Return the graph
return G
def all_moves(G):
for node in G.nodes():
for color in ['R','G','B']:
if not node[0] == color:
yield (node, color)
def fill(G, node, color):
samecolor = [n for n in G.nodes() if n[0] == color]
newnode = color + (str(max([int(n[1:]) for n in samecolor]) + 1) if samecolor else '1')
oldnodes = [node]
oldnodes.extend([n for n in G.neighbors(node) if n[0] == color])
contract_edges(G, oldnodes, newnode)
#print node, color, G.size()
#print [e for e in G.edges() if newnode in e]
return G
def solve(G, max_moves=None, moves=[]):
for (node, color) in all_moves(G):
H = G.copy()
fill(H, node, color)
if H.size() < G.size():
#print '-'*len(moves), node, color
if H.size() == 0:
moves.append((node, color))
print 'solved in %d moves:' % len(moves), moves
moves.pop()
elif not max_moves or len(moves) < max_moves - 1:
moves.append((node, color))
solve(H, max_moves=max_moves, moves=moves)
moves.pop()
G = nx.Graph()
G.add_edges_from([('G1', 'R1'), ('G1', 'B3'), ('G1', 'B2'), ('R1', 'B2'), ('R1', 'B1'), ('R2', 'B1'), ('B1', 'G3'), ('B2', 'G2'), ('R2', 'G2'), ('R2', 'G3'), ('G3', 'R3'), ('G2', 'R3'), ('B3', 'R3'), ('B3', 'G2')])
solve(G, max_moves = 4)
#manual solution:
#fill(G, 'B1', 'R')
#fill(G, 'R4', 'G')
#fill(G, 'G4', 'B')
#fill(G, 'R3', 'B')
#G = nx.Graph()
#G.add_edges_from([('B1', 'R1')])
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment