Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
BFS from HackerRank
# ATTN: import Q for BFS traversal
# https://stackoverflow.com/questions/717148/queue-queue-vs-collections-deque
from collections import deque
# ATTN: import simplest DICT for Graph Adjacency list
# https://stackoverflow.com/questions/5900578/how-does-collections-defaultdict-work
from collections import defaultdict
# ATTN: import simplest COUNTER dictionary for Distance accum for EQUAL-weighted OCCURRENCE counts but LESS GENERAL-FLEXIBLE than adding VARIABLE edge weight using DefaultDict!
# https://pymotw.com/2/collections/counter.html
from collections import Counter
from sys import maxsize
# APPROACH:
# ALGO: USES GREEDY-PARALLEL-SPIDER-SEARCH BFS on EQUAL-WEIGHTED EDGES to build SHORTEST-PATH!
# ATTN: NO need to evaluate MIN path among path options; as doing PARALLEL traversal on
# EQUALWEIGHTED segements!
# STEP1: build sparse-friendly adjacency dictionary to represent GRAPH
# ATTN: DICT keyed by SOURCE node to sub-DICT of DESTINATION nodes with EDGE weight
# STEP2: ACCUM weighted-edge DISTANCE count to COUNTER keyed by DESTINATION of edge examined;
# incrementing distance from distance of SOURCE of edge examined
# PLUS EDGE to each of its dest adjacencies
# STEP3: use FIFO Queue for BFS TRAVERSAL
# using Lookup in GRAPH Dictionary to APPEND Adjacent Destination Nodes NEXT Level down
# STEP4: use Unvisited SET to FILTER next nodes to process while avoiding CYCLEs in traversal
# SIMPLIFICATION 1: Node Key or Id is SAME as associated Value, otherwise would have to create separate Vertex class
# SIMPLIFICATION 2: EQUAL weights, so algo only needs to COUNT edges, rather than DECIDE on MIN across possibilities
class Graph:
def __init__(self, numNodes):
# ATTN: node count
self.numNodes = numNodes
# default dict materializes element type given by lambda factory iff new non-existent key used on
# ANY access (so be sure that you WANT entry on ANY access, otherwise first check KEY 'in' prior)
# ATTN: lambda is explicit with default element factory, and (int) is idiomatic type with default val 0
self.edges = defaultdict(lambda: defaultdict(int))
def connect(self,x,y,weight):
self.edges[x][y] = weight
# ATTN:
# - loads Counter/Dict of cumulative shortest path distances KEYed by DESTINATION node from SOURCE node
# - Count 0 returned for items NOT in Dict; but we will update with -1 for ORPHAN items
# not connected
def traverseBFS_AccumEdges(self, origin):
# https://docs.python.org/2/library/collections.html#collections.Counter
# ATTN: ORIGIN to be DELETED as not relevant to path at END
allDistFromS = Counter()
#ATTN: initialize BFS traversal Q with Origin
bfsQ = deque()
bfsQ.append(origin)
# ATTN: initialize UNVISITED SET from list comprehension,
# REMOVING Origin as already-visited
# AND 1-indexed, and INCLUSIVE of LAST node value with +1, and START INDEX of 1
unvisited = set([i for i in xrange(1, self.numNodes + 1)])
unvisited.remove(origin)
# print ("STARTING bfsQ:")
# print bfsQ
# print ("STARTING unvisited:")
# print unvisited
# ATTN: syntax for checking Q still has elements to process
while bfsQ:
# ATTN: FIFO traversal, remove from FRONT of Q
currSourceNode = bfsQ.popleft()
# ATTN: lookup connected edges and ACCUM weights to allDistFromS,
# CAREFUL not to ADD any default entry if no existing connections from currSourceNode
if currSourceNode in self.edges:
adjacents = self.edges[currSourceNode]
for dest in adjacents.keys():
# KEY-TRICK1: Incremental accum of distance CROSSING from Visited to Unvisited
# node sets! ASSURED to be Min Path as Equal-Weighted edges,
# PARALLEL greedy traversal; so just Count edges OK!
# NO need to COMPARE which originating Path is SHORTER as in Dijkstra!
# ATTN: Set accum distance for DESTINATION node based on distance to SOURCe, adding EDGE
# allDistFromS[dest] = allDistFromS[source] + self.edges[currNode][dest]
# ATTN: Counter uses INCREMENTAL summation syntax
# https://pymotw.com/2/collections/counter.html
# KEY-TRICK2: To prevent CYCLE-COUNTs, test membership in unvisited set first!
# ATTN: Origin is never added here; as only DEST node entries are updated
if dest in unvisited:
allDistFromS.update( { dest: allDistFromS[currSourceNode] })
allDistFromS.update( { dest: self.edges[currSourceNode][dest] } )
# ATTN: UPDATE process tracking state for both TRAVERSAL and UNVISITED
# print ("ADDED to BFSQ to traverse: ")
bfsQ.append(dest)
# print bfsQ
# print ("REMOVED from UNVISITED: ")
unvisited.remove(dest)
# print unvisited
# print ("BUILDING CUMULATIVE DISTANCES:")
# print allDistFromS
# ATTN: if NOT connected to ANY edges, then STILL add entry with Count initialized
# to -1
# print "ORPHAN NODEs with NO CONNECTED EDGE FOUND: {0}".format(unvisited)
for orphan in unvisited:
# allDistFromS.update( { orphan: Integer.MAX_VALUE} )
# allDistFromS.update( { orphan: maxsize} )
allDistFromS.update( { orphan: -1 } )
# RETURN results of cumulative paths TO Nodes FROM Origin
return allDistFromS
# ***** ATTN: input-parsing code
def loadGraph(numNodes, numEdges):
# print "***** LOADING NEW GRAPH: "
# print "NumNodes and NumEdges: {0}, {1}".format(numNodes, numEdges)
# ATTN: load Graph for given number of edges
graph = Graph(numNodes)
for i in xrange(numEdges):
x,y = [int(e) for e in raw_input().strip().split()]
# ATTN: formatted print
# print "Edge: {0},{1}".format(x,y)
# ATTN: setting Graph to connect Nodes input translated
# AND assume EQUAL weight of 6!
# ATTN: using MAP, no need to offset values by 0-indexed List structure!
# ATTN: use SYMMETRIC undirected mapping!
graph.connect(x,y,6)
graph.connect(y,x,6)
return graph
# ***** ATTN: MAIN DRIVER CODE!
# int() and strip() for input data-cleaning, typesafety!
# ATTN: loading of each SET of Graph data
t = input()
# print "Number of Graph Input Sets: {0}".format(t)
for i in range(t):
# ATTN: parse to n num nodes, m num edges
n,m = [int(x) for x in raw_input().strip().split()]
# ATTN: loading Graph
aGraph = loadGraph(n, m)
# print ("LOADED GRAPH: ")
# print aGraph.numNodes
# print aGraph.edges
# ATTN: loading origin point
origin = int(raw_input().strip())
# print "SOURCE NODE: {0}".format(origin)
# ATTN: calculating shortest path distances from specified SOURCE to ALL OTHER DESTINATION nodes
allShortestDistFromS = aGraph.traverseBFS_AccumEdges(origin)
# print "RESULT CUMULATIVE SHORTEST PATHs, ALL from Origin"
# print allShortestDistFromS
# TODO: extract keys(), Sort, then access values IN-ORDER for Dict via list comprehension!
# del allShortestDistFromS[origin]
# ATTN: aList.sort() vs sorted(aList); where in-place timesort for list.sort() saves time on copy
# https://stackoverflow.com/questions/1436962/python-sort-method-on-list-vs-builtin-sorted-function
# print "FINAL RESULT VALUES SORTED BY NODE INDEX ( which is same as VALUE here ):"
# https://stackoverflow.com/questions/4642501/how-to-sort-dictionaries-by-keys-in-python
# for k, v in sorted(allShortestDistFromS.items()):
# print k, ':', v
# print [ v for k, v in sorted(allShortestDistFromS.items()) ]
# ATTN: printing string of Items List
sortedAllShortestDistFromS = [ v for k, v in sorted(allShortestDistFromS.items()) ]
print " ".join(str(e) for e in sortedAllShortestDistFromS)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.