public
Created

  • Download Gist
gistfile1.py
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79
class Graph(object):
def __init__(self):
self.nodes = {}
"""
self.nodes is a mapping between a node and a mapping of nodes that
can be reached with a set of possible source nodes:
self.nodes = {
'fromNodeA': {
'toNodeB': set(['ifComingFromC', 'ifComingFromD', ...]),
'toNodeE': set(['ifComingFromF']),
},
...
}
Each node is represented by a unique string.
"""
 
def addEdge(self, (node1, comingFrom1), (node2, comingFrom2)):
"""
Adds an edge to this graph between node1 and node2. This edge can be
walked in direction node1 -> node2 only if coming from a node in
comingFrom1, and respectively, in direction node2 -> node1 only if
coming from a node in comingFrom2.
Complexity: O(1)
Note: comingFrom1 and comingFrom2 can be any iterable, but only
set/frozenset types allow for the best O complexity in the
following methods.
"""
# Add the nodes for both directions, as the graph is not directed.
self.nodes.setdefault(node1, {})[node2] = comingFrom1
self.nodes.setdefault(node2, {})[node1] = comingFrom2
 
def isEdge(self, comingFrom, passingBy, goingTo):
"""
Returns True if there is an edge between passingBy and goingTo
accessible when coming from comingFrom.
Complexity: O(1)
Note: compelxity may be O(n) where n is the number of directions if
the direction type does not support O(1) lookup.
"""
try:
return comingFrom in self.nodes[passingBy][goingTo]
except KeyError:
# passingBy not in self.nodes
# - or -
# goingTo is not in self.nodes[passingBy]
return False
 
def destinations(self, comingFrom, passingBy):
"""
Returns a set containing all possible destinations (i.e. edges between
passingBy and all other nodes in the graph) when coming from
comingFrom.
Complexity: O(n) where n is the number of edges exiting from passingBy.
"""
dests = set()
try:
for node, directions in self.nodes[passingBy].iteritems():
if comingFrom in directions:
dests.add(node)
except KeyError:
pass
return dests
 
def sources(self, passingBy, goingTo):
"""
Returns a set containing all possible source nodes which allow to
walk the edge between passingBy and goingTo.
Complexity: O(n) where n is the number of edges entering passingBy.
"""
return self.destinations(goingTo, passingBy)

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.