Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Scipy connected_components solution in 3rd party category for New Cities by r_tchaik
import numpy as np
from itertools import chain
from scipy.sparse.csgraph import connected_components
def create_graph(net, crushes):
nodes = {node: idx for idx, node in enumerate(set(chain.from_iterable(net)) - set(crushes))}
net = [edge for edge in net if set(edge).isdisjoint(crushes)]
gridLand = np.zeros([len(nodes)] * 2, dtype=bool)
for edge in net:
x, y = [nodes[node] for node in edge]
gridLand[x, y] = gridLand[y, x] = 1
return gridLand
def subnetworks(net, crushes):
return connected_components(create_graph(net, crushes), directed=False, return_labels=False)
if __name__ == '__main__':
#These "asserts" using only for self-checking and not necessary for auto-testing
assert subnetworks([
['A', 'B'],
['B', 'C'],
['C', 'D']
], ['B']) == 2, "First"
assert subnetworks([
['A', 'B'],
['A', 'C'],
['A', 'D'],
['D', 'F']
], ['A']) == 3, "Second"
assert subnetworks([
['A', 'B'],
['B', 'C'],
['C', 'D']
], ['C', 'D']) == 1, "Third"
print('Done! Check button is waiting for you!')
May 17, 2020
Comments:
