### ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ###
##                    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 outBlock.block_type.getValue()[1] == 6:  # integrator 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:
  if node.visited != 0:
    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 outBlock.block_type.getValue()[1] == 6:  # integrator 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