BFS from HackerRank

bfsGraph

# 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)