tools/android/loading/dag.py

# Copyright 2015 The Chromium Authors. All rights reserved.
# Use of this source code is governed by a BSD-style license that can be
# found in the LICENSE file.

"""Support for directed acyclic graphs.

Used in the ResourceGraph model for chrome loading.
"""

class Node(object):
  """A node in a DAG.

  We do not enforce at a node level that a graph is a DAG. Methods like
  TopologicalSort will assume a DAG and may fail if that's not the case.

  Nodes are identified with an index that must be unique for a particular graph
  (it is used for hashing and equality). A graph is represented as a list of
  nodes, for example in the TopologicalSort class method. By convention a node's
  index is its position in this list, making it easy to store auxillary
  information.
  """
  def __init__(self, index):
    """Create a new node.

    Args:
      index: index of the node. We assume these indicies uniquely identify a
        node (and so use it for hashing and equality).
    """
    self._predecessors = set()
    self._successors = set()
    self._index = index

  def Predecessors(self):
    return self._predecessors

  def Successors(self):
    return self._successors

  def AddSuccessor(self, s):
    """Add a successor.

    Updates appropriate links. Any existing parents of s are unchanged; to move
    a node you must do a combination of RemoveSuccessor and AddSuccessor.

    Args:
      s: the node to add as a successor.
    """
    self._successors.add(s)
    s._predecessors.add(self)

  def RemoveSuccessor(self, s):
    """Removes a successor.

    Updates appropriate links.

    Args:
      s: the node to remove as a successor. Will raise a set exception if s is
         not an existing successor.
    """
    self._successors.remove(s)
    s._predecessors.remove(self)

  def SortedSuccessors(self):
    children = [c for c in self.Successors()]
    children.sort(key=lambda c: c.Index())
    return children

  def Index(self):
    return self._index

  def __eq__(self, o):
    return self.Index() == o.Index()

  def __hash__(self):
    return hash(self.Index())


def TopologicalSort(nodes, node_filter=None):
  """Topological sort.

  We use a BFS-like walk which ensures that sibling are always grouped
  together in the output. This is more convenient for some later analyses.

  Args:
    nodes: [Node, ...] Nodes to sort.
    node_filter: a filter Node->boolean to restrict the graph. A node passes the
      filter on a return value of True. Only the subgraph reachable from a root
      passing the filter is considered.

  Returns:
    A list of Nodes in topological order. Note that node indicies are
    unchanged; the original list nodes is not modified.
  """
  if node_filter is None:
    node_filter = lambda _: True
  sorted_nodes = []
  sources = []
  remaining_in_edges = {}
  for n in nodes:
    if n.Predecessors():
      remaining_in_edges[n] = len(n.Predecessors())
    elif node_filter(n):
      sources.append(n)
  while sources:
    n = sources.pop(0)
    assert node_filter(n)
    sorted_nodes.append(n)
    # We sort by index to get consistent sorts across runs/machines.
    for c in n.SortedSuccessors():
      assert remaining_in_edges[c] > 0
      if not node_filter(c):
        continue
      remaining_in_edges[c] -= 1
      if not remaining_in_edges[c]:
        sources.append(c)
  return sorted_nodes