Keeping track of time while depth first searching a digraph

Question

I'm trying to do a depth first search of a directed graph, and while doing that I'm also trying to keep track of data about the graph. First, here are the classes I used to construct the digraph.

class Node(object):
   def __init__(self, name):
       self.name = str(name)
   def getName(self):
       return self.name
   def __str__(self):
       return self.name
   def __repr__(self):
      return self.name
   def __eq__(self, other):
      return self.name == other.name
   def __ne__(self, other):
      return not self.__eq__(other)

class Edge(object):
   def __init__(self, src, dest,distance,distance_out):
       self.src = src
       self.dest = dest
       self.distance = distance
       self.distance_out = distance_out
   def getSource(self):
       return self.src
   def getDestination(self):
       return self.dest
   def getDistance(self):
      return self.distance
   def getDistance_Outdoors(self):
      return self.distance_out
   def __str__(self):
       return str(self.src) + '--'+'Total Distance:(' +str(self.distance)+')' + ' '+ 'Outside Distance:('+str(self.distance_out)+')'+'-->' + str(self.dest)


class Digraph(object):
   """
   A directed graph
   """
   def __init__(self):
       self.nodes = set([])
       self.edges = {}
   def addNode(self, node):
       if node in self.nodes:
           raise ValueError('Duplicate node')
       else:
           self.nodes.add(node)
           self.edges[node] = []
   def addEdge(self, edge):
       src = edge.getSource()
       dest = edge.getDestination()
       distance = edge.getDistance()
       distance_out = edge.distance_out
       if not(src in self.nodes and dest in self.nodes):
           raise ValueError('Node not in graph')
       self.edges[src].append([dest,[distance,distance_out]])
   def childrenOf(self, node):
       return self.edges[node]
   def hasNode(self, node):
       return node in self.nodes
   def testDict(self):
      return self.edges
   def __str__(self):
       res = ''
       for k in self.edges:
           for d in self.edges[k]:
               res = res + str(k) + '->' + str(d[0]) + str(d[1])+ '\n' 
       return res[:-1]

The digraph I'm currently working on has 37 nodes and 129 edges.

Here's the code for my search functions.

import string
from graph import Digraph, Edge, Node
def depthFirstSearchVisit(digraph, time, node,discovered, undiscovered ,
                          explored , nodes , hierarchy ):
    time = time + 1 #While vertex has just been discovered
    nodes[node].append(time) ##Mark the discovery time for the node in the nodes dictionary
    discovered.append(node)##Mark the node as discovered
    if node in undiscovered: ## Remove node from undiscovered after it's discovery
        undiscovered.remove(node)
    for adjacent_node in digraph.childrenOf(node):##Explore edge (node, adjacent_node)
        if adjacent_node[0] in undiscovered: ##The adjacent node is a predecessor of the node
            hierarchy[node].append(adjacent_node[0])##Mark it as such in the hierarchy dictionary
            depthFirstSearchVisit(digraph,time,adjacent_node[0],discovered,
                                  undiscovered,explored,nodes,hierarchy)##Then recursively visit that adjacent_node
    explored.append(node) ##After exploring all of the nodes adjacent
    nodes[node].append(time)
    return nodes
def depthFirstSearch(digraph,time, discovered = [], undiscovered = [],
                     explored = [], nodes = {}, hierarchy = {}):

    if len(nodes) == 0: ## If nodes is empty
        for i in digraph.nodes: ##Initialize a dictionary where nodes are the keys and 
            nodes[i] = [] ##An empty list for values, so they can be filled with discovery and exploration times
    for key in nodes: ##For each node in the digraph mark them all as undiscovered.
        undiscovered.append(key)
    for key2 in nodes:##Construct hierarchy dict for later use in DepthFirstSearchVisit
        hierarchy[key2] = []
    ##Time initialized to zero in parameter call
    for node in nodes:
        if node in undiscovered:
            depthFirstSearchVisit(digraph,time,node,discovered, undiscovered, explored,nodes,hierarchy)
    return nodes

Right now I'm testing to see if a dictionary nodes is outputting the correct information. Here is the structure of the nodes dictionary.

{node: [time of discovery, time of exploration]}

The time of discovery is when the DepthFirsTSearchVisit first encounters a node, and the time of exploration is when that node's descendants and so forth all the way down are all discovered.

Here is what I get as output:

{32: [1, 1], 48: [4, 4], 50: [9, 9], 37: [17, 17], 13: [15, 15], 10: [25, 25], 64: [9, 9], 35: [18, 18], 5: [22, 22], 24: [14, 14], 6: [10, 10], 57: [2, 2], 9: [20, 20], 68: [6, 6], 39: [16, 16], 1: [23, 23], 38: [16, 16], 62: [8, 8], 4: [12, 12], 16: [4, 4], 34: [15, 15], 2: [9, 9], 54: [7, 7], 7: [21, 21], 66: [8, 8], 56: [5, 5], 46: [3, 3], 76: [7, 7], 18: [6, 6], 3: [24, 24], 36: [2, 2], 12: [13, 13], 33: [19, 19], 14: [8, 8], 8: [11, 11], 26: [3, 3], 31: [18, 18]}

What output I think I should be getting: The time values shouldn't be the same. There should be a large difference between discovery and exploration.

Thanks in advance for any help.

might the builtin time module come in handy? – Totem Dec 09 '13 at 20:51 — Totem, Dec 09 '13 at 20:51

Corley Brigman · Answer 1 · 2013-12-09T21:06:51.757

you are treating time as if it were pass-by-reference. it isn't - it is pass by value. this is because python ints are immutable. so when you do this:

def depthFirstSearchVisit(digraph, time, node,discovered, undiscovered ,
                          explored , nodes , hierarchy ):
    time = time + 1 #While vertex has just been discovered
    ...

This created a local called time, and it points to the same int as the input time. Then you increment it, and now time points to a new integer local to the function. Then later, when you do this:

depthFirstSearchVisit(digraph,time,adjacent_node[0],discovered,
     undiscovered,explored,nodes,hierarchy)

It looks like are expecting the subfunction to increment time while it's there, and then when it returns back, the time i passed down will be modified. But actually, it won't.

Python variable passing can be a little confusing for programmers from other languages, because it isn't really pass by reference OR value, at least not in the C++ style. You have a name, and it points to an object. When you call a function, the function gets a new local name, but it points to the same object. As long as you don't reassign this name, then it's like pass by reference. But as soon as you reassign it, your local name now points to a new object and is no longer sharing.

As the comment says, you'd be better off just calling time.time() at the top and bottom.

One last addition: If you really want integer time, it's easy to use itertools.count. It has to be a global though:

from itertools import count
gtime = count(0)

#Note: Removed time, as it's useless now
def depthFirstSearchVisit(digraph, node,discovered, undiscovered ,
                          explored , nodes , hierarchy ):
     starttime = gtime.next()
     # Call some functions...
     # ....
     # Those also increment global time
     endtime = gtime.next()

.. and here's a [link](http://stackoverflow.com/questions/7370801/measure-time-elapsed-in-python) on how to do that properly — Milo Wielondek, Dec 09 '13 at 20:57
Other alternatives, retaining the neat integer time steps: `global time`; or explicitly `return time`. — jonrsharpe, Dec 09 '13 at 20:59
added some information on how to use `itertools.count` to do this a little easier... — Corley Brigman, Dec 09 '13 at 21:07
Thanks Corley Brigman, that seems to work. I used the itertools.count. — user2980081, Dec 09 '13 at 21:18

Keeping track of time while depth first searching a digraph

1 Answers1