Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Break Rings by MaxAlive
import copy
from itertools import combinations
class BrokenRingGraph(object):
def __init__(self, edges):
self.graph = {}
self.fill_graph(edges)
def fill_graph(self,edges):
for x, y in edges:
self.append_graph(x,y)
self.append_graph(y,x)
def append_graph(self,vertex,value):
if vertex not in self.graph:
self.graph[vertex] = [value]
else:
self.graph[vertex].append(value)
def remove_vertex(self, vertex):
for key in self.graph[vertex]:
self.graph[key].remove(vertex)
self.graph.pop(vertex)
def rings_disconnected(self):
for element in self.graph:
if self.graph[element]:
return False
return True
def break_rings(edges):
ring_network = BrokenRingGraph(edges)
vertices = [vertex for vertex in ring_network.graph]
for i in range(1,len(vertices)):
possibilities = list(combinations(vertices,i))
for possibility in possibilities:
copy_network = copy.deepcopy(ring_network)
for j in possibility:
copy_network.remove_vertex(j)
if copy_network.rings_disconnected():
return len(possibility)
if __name__ == '__main__':
# These "asserts" using only for self-checking and not necessary for auto-testing
assert break_rings(({1, 2}, {2, 3}, {3, 4}, {4, 5}, {5, 6}, {4, 6})) == 3, "example"
assert break_rings(({1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4})) == 3, "All to all"
assert break_rings(({5, 6}, {4, 5}, {3, 4}, {3, 2}, {2, 1}, {1, 6})) == 3, "Chain"
assert break_rings(({8, 9}, {1, 9}, {1, 2}, {2, 3}, {3, 4}, {4, 5}, {5, 6}, {6, 7}, {8, 7})) == 5, "Long chain"
July 1, 2015
