Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
FULLY COMMENTED AND EXPLAINED: Expressing graph as a numpy array solution in 3rd party category for Node Disconnected Users by Keisuki
import numpy
def disconnected_users(net, users, source, crushes):
#To solve this problem, we first need to know which nodes can be reached from which nodes.
#We will store this data in the form of a numpy matrix, where the matrix entry at row i and column j
# is 1 if there is a valid path from node i to node j. For example, if the network is given by:
#
# [['A', 'B'],
# ['A', 'C'],
# ['A', 'D'],
# ['A', 'E'],
# ['A', 'F']]
#
#Then any node can be reached from anywhere else, so our matrix is given by:
#
# A B C D E F
# A 1 1 1 1 1 1
# B 1 1 1 1 1 1
# C 1 1 1 1 1 1
# D 1 1 1 1 1 1
# E 1 1 1 1 1 1
# F 1 1 1 1 1 1
#
#If we have a network split into separate connected groups of nodes, such as:
#
# [['A', 'B'],
# ['B', 'C'],
# ['D', 'E'],
# ['E', 'F']]
#
#Then the matrix for this network is:
#
# A B C D E F
# A 1 1 1 0 0 0
# B 1 1 1 0 0 0
# C 1 1 1 0 0 0
# D 0 0 0 1 1 1
# E 0 0 0 1 1 1
# F 0 0 0 1 1 1
#
#To construct such a matrix, we start by plotting the network connections we've been given.
# We start with a diagonal matrix of 1s, as any node is connected with itself.
# If we're given that there's a connection, ['A', 'B'], then we put a 1 in row A column B,
# and the same in row B column A.
#
#The network,
#
# [['A', 'B'],
# ['B', 'C'],
# ['D', 'E'],
# ['E', 'F']]
#
#Would give us:
#
# A B C D E F
# A 1 1 0 0 0 0
# B 1 1 1 0 0 0
# C 0 1 1 0 0 0
# D 0 0 0 1 1 0
# E 0 0 0 1 1 1
# F 0 0 0 0 1 1
#
#Then, we can notice things like:
#
# A is connected to B and B is connected to C, therefore: A is connected to C
# D is connected to E and E is connected to F, therefore: D is connected to F
#
#We continue looking for connections like this until no more can be found, then our matrix
# is complete.
#
#To compute the matrix of connections for a network with some nodes removed, we simply
# ignore any connections to and from the removed nodes.
#First, we create a matrix of 0s
dimension = len(users)
connections = numpy.zeros((dimension, dimension), dtype=numpy.int8)
#Next, we fill the diagonal with 1s
for i in range(dimension):
connections[i,i] = 1
#We assign a row and column number to each node, sequentially, and store that information
# in a dictionary.
node_number = {}
i = 0
for node in users:
node_number[node] = i
i += 1
#Next, we plot each connection from net into the matrix, ignoring ones to and from crushed
# nodes
for connection in net:
if connection[0] in crushes or connection[1] in crushes:
continue
#To plot the connection, we look up the row/column number for the connected nodes from
# our node_number dictionary.
connections[node_number[connection[0]], node_number[connection[1]]] = 1
connections[node_number[connection[1]], node_number[connection[0]]] = 1
#Now we just need to use a loop, to look for nodes which are connected via other nodes.
# To do this, we use a variable to keep track of whether new connections are still being
# found. This way, we can stop when no new connections remain.
found_new_connections = True
while found_new_connections:
found_new_connections = False
for i in range(dimension):
for j in range(dimension):
#We look for 2 connected nodes
if connections[i,j] != 1:
continue
#And then we look for a third node which is connected to the first.
for k in range(dimension):
if connections[i,k] != 1:
continue
#If so, then i and j are connected, and i and k are connected,
# so j and k must be connected.
if connections[j,k] != 1:
#So if they aren't already marked as connected, we do so, and set our
# flag for new connections being found to True
connections[j,k] = 1
found_new_connections = True
#Once we get to this point, we've left the loop of adding new connections, and our matrix is
# complete. We simply need to go through each node, and see if it's connected to the
# node sending emails. If it isn't, then we add its users to the total number of users requiring
# pigeon delivery. In addition, crushed nodes should always require pigeons, even if they
# are the ones sending the email.
source_number = node_number[source]
pigeons = 0
for node in users:
if node in crushes or connections[source_number, node_number[node]] == 0:
pigeons += users[node]
return pigeons
if __name__ == '__main__':
#These "asserts" using only for self-checking and not necessary for auto-testing
assert disconnected_users([
['A', 'B'],
['B', 'C'],
['C', 'D']
], {
'A': 10,
'B': 20,
'C': 30,
'D': 40
},
'A', ['C']) == 70, "First"
assert disconnected_users([
['A', 'B'],
['B', 'D'],
['A', 'C'],
['C', 'D']
], {
'A': 10,
'B': 0,
'C': 0,
'D': 40
},
'A', ['B']) == 0, "Second"
assert disconnected_users([
['A', 'B'],
['A', 'C'],
['A', 'D'],
['A', 'E'],
['A', 'F']
], {
'A': 10,
'B': 10,
'C': 10,
'D': 10,
'E': 10,
'F': 10
},
'C', ['A']) == 50, "Third"
print('Done. Try to check now. There are a lot of other tests')
July 22, 2018
