### ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ###
## 308-522 -- Modelling and Simulation
## Fall 2002
## --- ASSIGNMENT 1 ---
##
## Graph.py
##
## last modified: 09/23/02
### ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ###
# Counter for the topological sorting:
_dfsCounter = 1
def topSort(graph):
""" graph : a list of (block) connectors (referred to as nodes here)
Output the list of nodes sorted in topological order.
RECALL that for the dependency graph, the connections of the original model
need to be reversed (a signal on a node depends on the signals upstream).
Hence the depth-first search goes ``against'' the connections in the model.
RECALL that the dependencies between signals on either side of a delay block
do not show up in the dependency graph.
"""
# MARK ALL NODES IN THE GRAPH AS UNVISITED:
for node in graph:
node.orderNumber = 0
for node in graph:
if node.orderNumber == 0:
_dfsLabelling(node)
# Sort the nodes according to their "orderNumber" attribute:
graph.sort( lambda x, y : cmp(x.orderNumber, y.orderNumber) )
return graph
def _dfsLabelling(node):
global _dfsCounter
# If the node has already been visited, the recursion stops here:
if node.orderNumber == 0:
# AVOID INFINITE LOOPS:
# -1 signals the node has been visited, if not numbered.
node.orderNumber = -1
# VISIT ALL NEIGHBOURS FIRST (deep first):
# First find what block is connected to the node. The "assert" statement
# makes sure there is a unique block.
outBlock = node.in_connections_ # List of Blocks
assert len(outBlock) == 1, "Too many blocks connected to node"
outBlock = outBlock[0]
# Find what nodes are connected to the block we found:
# Note that in the case of a delay block (integrator), only the IC
# connection shows up.
if not "block_type" in dir(outBlock):
outNodes = []
elif outBlock.block_type.getValue()[1] in [5, 6]: # integrator block and delay block
outNodes = outBlock.block_IC_port
else:
outNodes = outBlock.in_connections_
for neighbour in outNodes:
_dfsLabelling(neighbour)
# LABEL THE NODE WITH THE COUNTER, AND INCREMENT:
node.orderNumber = _dfsCounter
_dfsCounter += 1
def strongComp(graph):
""" graph : a list of (block) connectors (referred to as nodes here).
Return a list of lists, each sublist a set of strongly connected components.
NOTE that in our implementation, the nodes in "graph" are already sorted in
topological order.
RECALL that to find strongly-connected components, we process the nodes in
reverse topological order. Likewise, the connections are visited in the
normal direction (as opposed to "topSort").
RECALL the dependencies between signals on either side of a delay block
do not show up in the dependency graph.
"""
strongComponents = []
# MARK ALL NODES IN THE GRAPH AS UNVISITED:
for node in graph:
node.visited = 0
# Visit each node in reverse topological order:
i = len(graph)-1
while i >= 0:
node = graph[i]
if node.visited == 0:
strongComponents.append( _dfsCollect(node) )
i -= 1
return strongComponents
def _dfsCollect(node):
# If the node has already been visited, the recursion stops here:
# visited attribute is not available in the Plot
if not "visited" in dir(node) or node.visited != 0: # Plots are not initiated, so their don't have "visited" attributes
return []
else:
# AVOID INFINITE LOOPS:
node.visited = 1
tmp = [node]
# VISIT ALL NEIGHBOURS FIRST (deep first):
# First find what block is connected to the node. The "assert" statement
# makes sure there is a unique block.
outBlock = node.out_connections_ # List of Blocks
assert len(outBlock) == 1, "Too many blocks connected to node"
outBlock = outBlock[0]
# Find what nodes are connected to the block we found:
# Note that in the case of a delay block (integrator), the outgoing
# connection is considered only if the "node" is the IC.
if not "block_type" in dir(outBlock): # Plots do not have a block_type; though SimControl has an in-port, its value does not depend on the input value. So the outNodes of both is empty.
outNodes = []
elif outBlock.block_type.getValue()[1] in [5, 6]: # integrator block and delay block
if node == outBlock.block_IC_port:
outNodes = outBlock.out_connections_
else:
outNodes = []
else:
outNodes = outBlock.out_connections_
for neighbour in outNodes:
tmp += _dfsCollect(neighbour)
return tmp