Factor graph code out into its own module, rework spack graph.

6 files changed, 509 insertions, 317 deletions

diff --git a/lib/spack/spack/cmd/graph.py b/lib/spack/spack/cmd/graph.py
index 955be51955..13efab5fe5 100644
--- a/lib/spack/spack/cmd/graph.py
+++ b/lib/spack/spack/cmd/graph.py
@@ -23,17 +23,39 @@
 # Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
 ##############################################################################
 from external import argparse
+
 import spack
 import spack.cmd
+from spack.graph import *
 
-description = "Write out inter-package dependencies in dot graph format"
+description = "Generate graphs of package dependency relationships."
 
 def setup_parser(subparser):
+    method = subparser.add_mutually_exclusive_group()
+    method.add_argument(
+        '--ascii', action='store_true',
+        help="Draw graph as ascii to stdout (default).")
+    method.add_argument(
+        '--dot', action='store_true',
+        help="Generate graph in dot format and print to stdout.")
+
+    method.add_argument(
+        '--concretize', action='store_true', help="Concretize specs before graphing.")
+
     subparser.add_argument(
-        'specs', nargs=argparse.REMAINDER,
-        help="specs of packages to graph.  Default is all packages.")
+        'specs', nargs=argparse.REMAINDER, help="specs of packages to graph.")
 
 
 def graph(parser, args):
-    specs = spack.cmd.parse_specs(args.specs)
-    spack.db.graph_dependencies(*specs)
+    specs = spack.cmd.parse_specs(
+        args.specs, normalize=True, concretize=args.concretize)
+
+
+    if args.dot:    # Dot graph only if asked for.
+        graph_dot(*specs)
+
+    elif specs:     # ascii is default: user doesn't need to provide it explicitly
+        graph_ascii(specs[0])
+        for spec in specs[1:]:
+            print # extra line bt/w independent graphs
+            graph_ascii(spec)
diff --git a/lib/spack/spack/cmd/location.py b/lib/spack/spack/cmd/location.py
index 3fc05d471d..509c336b69 100644
--- a/lib/spack/spack/cmd/location.py
+++ b/lib/spack/spack/cmd/location.py
@@ -111,4 +111,3 @@ def location(parser, args):
                     tty.die("Build directory does not exist yet. Run this to create it:",
                             "spack stage " + " ".join(args.spec))
                 print pkg.stage.source_path
-
diff --git a/lib/spack/spack/cmd/spec.py b/lib/spack/spack/cmd/spec.py
index 71bc12d6f5..e2cb5689c0 100644
--- a/lib/spack/spack/cmd/spec.py
+++ b/lib/spack/spack/cmd/spec.py
@@ -27,8 +27,8 @@ import spack.cmd
 
 import llnl.util.tty as tty
 
-import spack.url as url
 import spack
+import spack.url as url
 
 description = "print out abstract and concrete versions of a spec."
 
@@ -44,14 +44,9 @@ def spec(parser, args):
         print "Normalized"
         print "------------------------------"
         spec.normalize()
-        print spec.tree(color=True, indent=2, cover='paths')
+        print spec.tree(color=True, indent=2)
 
         print "Concretized"
         print "------------------------------"
         spec.concretize()
         print spec.tree(color=True, indent=2)
-
-        print "Graph"
-        print "------------------------------"
-        spec.graph()
-        return
diff --git a/lib/spack/spack/graph.py b/lib/spack/spack/graph.py
new file mode 100644
index 0000000000..142c9c5c8f
--- /dev/null
+++ b/lib/spack/spack/graph.py
@@ -0,0 +1,480 @@
+##############################################################################
+# Copyright (c) 2013, Lawrence Livermore National Security, LLC.
+# Produced at the Lawrence Livermore National Laboratory.
+#
+# This file is part of Spack.
+# Written by Todd Gamblin, tgamblin@llnl.gov, All rights reserved.
+# LLNL-CODE-647188
+#
+# For details, see https://scalability-llnl.github.io/spack
+# Please also see the LICENSE file for our notice and the LGPL.
+#
+# This program is free software; you can redistribute it and/or modify
+# it under the terms of the GNU General Public License (as published by
+# the Free Software Foundation) version 2.1 dated February 1999.
+#
+# This program is distributed in the hope that it will be useful, but
+# WITHOUT ANY WARRANTY; without even the IMPLIED WARRANTY OF
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the terms and
+# conditions of the GNU General Public License for more details.
+#
+# You should have received a copy of the GNU Lesser General Public License
+# along with this program; if not, write to the Free Software Foundation,
+# Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+##############################################################################
+"""Functions for graphing DAGs of dependencies.
+
+This file contains code for graphing DAGs of software packages
+(i.e. Spack specs).  There are two main functions you probably care
+about:
+
+graph_ascii() will output a colored graph of a spec in ascii format,
+knd of like the graph git shows with "git log --graph".
+
+graph_dot() will output a graph of a spec (or multiple specs) in dot
+format.
+
+Note that ``graph_ascii`` assumes a single spec while ``graph_dot``
+can take a number of specs as input.
+
+"""
+__all__ = ['topological_sort', 'graph_ascii', 'AsciiGraph', 'graph_dot']
+
+from heapq import *
+
+from llnl.util.lang import *
+from llnl.util.tty.color import *
+
+import spack
+
+
+def topological_sort(spec, **kwargs):
+    """Topological sort for specs.
+
+    Return a list of dependency specs sorted topologically.  The spec
+    argument is not modified in the process.
+
+    """
+    reverse = kwargs.get('reverse', False)
+    if not reverse:
+        parents  = lambda s: s.dependents
+        children = lambda s: s.dependencies
+    else:
+        parents  = lambda s: s.dependencies
+        children = lambda s: s.dependents
+
+    # Work on a copy so this is nondestructive.
+    spec = spec.copy()
+    nodes = spec.index()
+
+    topo_order = []
+    remaining = [name for name in nodes.keys() if not parents(nodes[name])]
+    heapify(remaining)
+
+    while remaining:
+        name = heappop(remaining)
+        topo_order.append(name)
+
+        node = nodes[name]
+        for dep in children(node).values():
+            del parents(dep)[node.name]
+            if not parents(dep):
+                heappush(remaining, dep.name)
+
+    if any(parents(s) for s in spec.traverse()):
+        raise ValueError("Spec has cycles!")
+    else:
+        return topo_order
+
+
+def find(seq, predicate):
+    """Find index in seq for which predicate is True.
+
+    Searches the sequence and returns the index of the element for
+    which the predicate evaluates to True.  Returns -1 if the
+    predicate does not evaluate to True for any element in seq.
+
+    """
+    for i, elt in enumerate(seq):
+        if predicate(elt):
+            return i
+    return -1
+
+
+class AsciiGraph(object):
+    def __init__(self):
+        # These can be set after initialization or after a call to
+        # graph() to change behavior.
+        self.node_character = 'o'
+        self.debug = False
+        self.indent = 0
+
+        # These are colors in the order they'll be used for edges.
+        # See llnl.util.tty.color for details on color characters.
+        self.colors = 'rgbmcyRGBMCY'
+
+        # Internal vars are used in the graph() function and are
+        # properly initialized there.
+        self._name_to_color = None    # Node name to color
+        self._out = None              # Output stream
+        self._frontier = None         # frontier
+        self._nodes = None            # dict from name -> node
+
+
+    def _indent(self):
+        self._out.write(self.indent * ' ')
+
+
+    def _write_edge(self, string, index, sub=0):
+        """Write a colored edge to the output stream."""
+        name = self._frontier[index][sub]
+        edge = "@%s{%s}" % (self._name_to_color[name], string)
+        self._out.write(edge)
+
+
+    def _connect_deps(self, i, deps, collapse, label):
+        """Connect dependencies to existing edges in the frontier.
+
+        ``deps`` are to be inserted at position i in the
+        frontier. This routine determines whether other open edges
+        should be merged with <deps> (if there are other open edges
+        pointing to the same place) or whether they should just be
+        inserted as a completely new open edge.
+
+        Open edges that are not fully expanded (i.e. those that point
+        at multiple places) are left intact.
+
+        Parameters:
+
+        collapse -- whether the frontier is collapsing or staying the
+                    same size.
+
+        label    -- optional debug label for the connection.
+
+        Returns: True if the deps were connected to another edge
+        (i.e. the frontier did not grow) and False if the deps were
+        NOT already in the frontier (i.e. they were inserted and the
+        frontier grew).
+
+        """
+        if len(deps) == 1 and deps in self._frontier:
+            j = self._frontier.index(deps)
+
+            # connect to the left
+            if j < i:
+                if i-j > 1:   # two lines if distance > 1
+                    self._back_edge([], j,  i, True, label)
+                self._back_edge([j], -1, -1, (i-j == 1), label)
+
+            # connect to the right
+            else:
+                if i < j:
+                    self._frontier.pop(j)
+                    self._frontier.insert(i, deps)
+                if j-i > 1:
+                    self._back_edge([], i, j+1, collapse, label)
+                self._back_edge([i], -1,  -1, not (j-i > 1) and collapse, label)
+            return True
+
+        elif deps:
+            self._frontier.insert(i, deps)
+            return False
+
+
+    def _add_deps_to_frontier(self, node, i):
+        """Add dependencies to frontier.
+
+        Adds the dependencies of <node> to the frontier, and connects
+        them to other open edges if they match.  Also deletes parent
+        pointers in the node to mark edges as covered.
+
+        """
+        deps = sorted((d for d in node.dependencies), reverse=True)
+        self._connect_deps(i, deps, True, "add_deps")
+        for d in deps:
+            del self._nodes[d].dependents[node.name]
+
+
+
+    def _back_edge(self, prev_ends, end, start, collapse, label=None):
+        """Write part of a backwards edge in the graph.
+
+        Writes single- or multi-line backward edges in an ascii graph.
+        For example, a single line edge::
+
+            | | | | o |
+            | | | |/ /  <-- single-line edge connects two nodes.
+            | | | o |
+
+        Or a multi-line edge (requires two calls to back_edge)::
+
+            | | | | o |
+            | |_|_|/ /   <-- multi-line edge crosses vertical edges.
+            |/| | | |
+            o | | | |
+
+        Also handles "pipelined" edges, where the same line contains
+        parts of multiple edges::
+
+                      o start
+            | |_|_|_|/|
+            |/| | |_|/| <-- this line has parts of 2 edges.
+            | | |/| | |
+            o   o
+
+        Arguments:
+
+        prev_ends -- indices in frontier of previous edges that need
+                     to be finished on this line.
+
+        end -- end of the current edge on this line.
+
+        start -- start index of the current edge.
+
+        collapse -- whether the graph will be collapsing (i.e. whether
+                    to slant the end of the line or keep it straight)
+
+        label -- optional debug label to print after the line.
+
+        """
+        def advance(to_pos, edges):
+            """Write edges up to <to_pos>."""
+            for i in range(self._pos, to_pos):
+                for e in edges():
+                    self._write_edge(*e)
+                self._pos += 1
+
+        flen = len(self._frontier)
+        self._pos = 0
+        self._indent()
+
+        for p in prev_ends:
+            advance(p,         lambda: [("| ", self._pos)] )
+            advance(p+1,       lambda: [("|/", self._pos)] )
+
+        if end >= 0:
+            advance(end + 1,   lambda: [("| ", self._pos)] )
+            advance(start - 1, lambda: [("|",  self._pos), ("_", end)] )
+        else:
+            advance(start - 1, lambda: [("| ", self._pos)] )
+
+        if start >= 0:
+            advance(start,     lambda: [("|",  self._pos), ("/", end)] )
+
+        if collapse:
+            advance(flen,      lambda: [(" /", self._pos)] )
+        else:
+            advance(flen,      lambda: [("| ", self._pos)] )
+
+        if self.debug:
+            self._out.write(" " * 10)
+            if label:
+                self._out.write(label)
+            self._out.write("%s" % self._frontier)
+
+        self._out.write("\n")
+
+
+    def write(self, spec, **kwargs):
+        """Write out an ascii graph of the provided spec.
+
+        Arguments:
+        spec -- spec to graph.  This only handles one spec at a time.
+
+        Optional arguments:
+
+        out -- file object to write out to (default is sys.stdout)
+
+        color -- whether to write in color.  Default is to autodetect
+                 based on output file.
+
+        """
+        out = kwargs.get('out', None)
+        if not out:
+            out = sys.stdout
+
+        color = kwargs.get('color', None)
+        if not color:
+            color = out.isatty()
+        self._out = ColorStream(sys.stdout, color=color)
+
+        # We'll traverse the spec in topo order as we graph it.
+        topo_order = topological_sort(spec, reverse=True)
+
+        # Work on a copy to be nondestructive
+        spec = spec.copy()
+        self._nodes = spec.index()
+
+        # Colors associated with each node in the DAG.
+        # Edges are colored by the node they point to.
+        self._name_to_color = dict((name, self.colors[i % len(self.colors)])
+                                  for i, name in enumerate(topo_order))
+
+        # This array tracks the open edges at the frontier of the
+        # graph we're writing out.
+        self._frontier = []
+
+        self._add_deps_to_frontier(spec, 0)
+        self._indent()
+        self._out.write('%s  %s\n' % (self.node_character, spec.name))
+        topo_order.pop()
+
+        while self._frontier:
+            # Find an unexpanded part of frontier
+            i = find(self._frontier, lambda f: len(f) > 1)
+
+            # Expand frontier until there are enough columns for all children.
+            if i >= 0:
+                # Figure out how many back connections there are and
+                # sort them so we do them in order
+                back = []
+                for d in self._frontier[i]:
+                    b = find(self._frontier[:i], lambda f: f == [d])
+                    if b != -1: back.append((b, d))
+
+                # Do all back connections in sorted order so we can
+                # pipeline them and save space.
+                if back:
+                    back.sort()
+                    prev_ends = []
+                    for j, (b, d) in enumerate(back):
+                        self._frontier[i].remove(d)
+                        if i-b > 1:
+                            self._back_edge(prev_ends, b, i, False)
+                            del prev_ends[:]
+                        prev_ends.append(b)
+                    self._back_edge(prev_ends, -1, -1, False)
+
+                if not self._frontier[i]:
+                    self._frontier.pop(i)
+
+                elif len(self._frontier[i]) > 1:
+                    # Expand forawrd after doing all back connections
+                    self._indent()
+                    for c in range(i):
+                        self._write_edge("| ", c)
+                    self._write_edge("|", i)
+
+                    if (i+1 < len(self._frontier) and len(self._frontier[i+1]) == 1
+                        and self._frontier[i+1][0] in self._frontier[i]):
+                        # We need to connect to the element to the right.
+                        # Keep lines straight by connecting directly and
+                        # avoiding immediate expand/contract.
+                        name = self._frontier[i+1][0]
+                        self._frontier[i].remove(name)
+
+                        self._write_edge("\\", i+1)
+                        for c in range(i+1, len(self._frontier)):
+                            self._write_edge("| ", c )
+                        self._out.write("\n")
+
+                    else:
+                        # Just allow the expansion here.
+                        name = self._frontier[i].pop(0)
+                        deps = [name]
+                        self._write_edge("\\", i)
+                        for c in range(i+1, len(self._frontier)):
+                            self._write_edge(" \\", c)
+                        self._out.write("\n")
+                        self._connect_deps(i, deps, True, "expansion")
+
+                # Handle any remaining back edges to the right
+                j = i+1
+                while j < len(self._frontier):
+                    deps = self._frontier.pop(j)
+                    if not self._connect_deps(j, deps, True, "rem_back"):
+                        j += 1
+
+            else:
+                name = topo_order.pop()
+                node = self._nodes[name]
+
+                # Find the next node in topo order and remove it from
+                # the frontier. Since specs are single-rooted DAGs,
+                # the node is always there. If the graph had multiple
+                # roots, we'd need to handle that case case of a new root.
+                i = find(self._frontier, lambda f: name in f)
+                self._frontier.pop(i)
+
+                self._indent()
+                for c in range(i):
+                    self._write_edge("| ", c)
+                self._out.write("%s " % self.node_character)
+                for c in range(i, len(self._frontier)):
+                    self._write_edge("| ", c)
+                self._out.write(" %s\n" % name)
+
+                if node.dependencies:
+                    self._add_deps_to_frontier(node, i)
+                elif self._frontier:
+                    self._indent()
+                    for c in range(i):
+                        self._write_edge("| ", c)
+                    for c in range(i, len(self._frontier)):
+                        self._write_edge(" /", c)
+                    self._out.write("\n")
+
+
+def graph_ascii(spec, **kwargs):
+    node_character = kwargs.get('node', 'o')
+    out            = kwargs.pop('out', None)
+    debug          = kwargs.pop('debug', False)
+    indent         = kwargs.pop('indent', 0)
+    color          = kwargs.pop('color', None)
+    check_kwargs(kwargs, graph_ascii)
+
+    graph = AsciiGraph()
+    graph.debug = debug
+    graph.indent = indent
+    graph.node_character = node_character
+
+    graph.write(spec, color=color, out=out)
+
+
+
+def graph_dot(*specs, **kwargs):
+    """Generate a graph in dot format of all provided specs.
+
+    Print out a dot formatted graph of all the dependencies between
+    package.  Output can be passed to graphviz, e.g.:
+
+        spack graph --dot qt | dot -Tpdf > spack-graph.pdf
+
+    """
+    out = kwargs.pop('out', sys.stdout)
+    check_kwargs(kwargs, graph_dot)
+
+    out.write('digraph G {\n')
+    out.write('  label = "Spack Dependencies"\n')
+    out.write('  labelloc = "b"\n')
+    out.write('  rankdir = "LR"\n')
+    out.write('  ranksep = "5"\n')
+    out.write('\n')
+
+    def quote(string):
+        return '"%s"' % string
+
+    if not specs:
+        packages = spack.db.all_packages()
+    else:
+        packages = []
+        for spec in specs:
+            packages.extend(s.package for s in spec.normalized().traverse())
+
+    deps = []
+    for pkg in packages:
+        out.write('  %-30s [label="%s"]\n' % (quote(pkg.name), pkg.name))
+
+        # Add edges for each depends_on in the package.
+        for dep_name, dep in pkg.dependencies.iteritems():
+            deps.append((pkg.name, dep_name))
+
+        # If the package provides something, add an edge for that.
+        for provider in set(p.name for p in pkg.provided):
+            deps.append((provider, pkg.name))
+
+    out.write('\n')
+
+    for pair in deps:
+        out.write('  "%s" -> "%s"\n' % pair)
+    out.write('}\n')
diff --git a/lib/spack/spack/packages.py b/lib/spack/spack/packages.py
index 0aa8090b61..db43d3909a 100644
--- a/lib/spack/spack/packages.py
+++ b/lib/spack/spack/packages.py
@@ -214,48 +214,6 @@ class PackageDB(object):
         return cls
 
 
-    def graph_dependencies(self, *specs, **kwargs):
-        """Print out a graph of all the dependencies between package.
-           Graph is in dot format."""
-        out = kwargs.pop('out', sys.stdout)
-        check_kwargs(kwargs, self.graph_dependencies)
-
-        out.write('digraph G {\n')
-        out.write('  label = "Spack Dependencies"\n')
-        out.write('  labelloc = "b"\n')
-        out.write('  rankdir = "LR"\n')
-        out.write('  ranksep = "5"\n')
-        out.write('\n')
-
-        def quote(string):
-            return '"%s"' % string
-
-        if not specs:
-            packages = self.all_packages()
-        else:
-            packages = []
-            for spec in specs:
-                packages.extend(s.package for s in spec.normalized().traverse())
-
-        deps = []
-        for pkg in packages:
-            out.write('  %-30s [label="%s"]\n' % (quote(pkg.name), pkg.name))
-
-            # Add edges for each depends_on in the package.
-            for dep_name, dep in pkg.dependencies.iteritems():
-                deps.append((pkg.name, dep_name))
-
-            # If the package provides something, add an edge for that.
-            for provider in set(p.name for p in pkg.provided):
-                deps.append((provider, pkg.name))
-
-        out.write('\n')
-
-        for pair in deps:
-            out.write('  "%s" -> "%s"\n' % pair)
-        out.write('}\n')
-
-
 class UnknownPackageError(spack.error.SpackError):
     """Raised when we encounter a package spack doesn't have."""
     def __init__(self, name):
diff --git a/lib/spack/spack/spec.py b/lib/spack/spack/spec.py
index 7aed82e239..2f4fe9ca24 100644
--- a/lib/spack/spack/spec.py
+++ b/lib/spack/spack/spec.py
@@ -93,7 +93,6 @@ expansion when it is the first character in an id typed on the command line.
 import sys
 import itertools
 import hashlib
-from heapq import *
 from StringIO import StringIO
 from operator import attrgetter
 
@@ -1326,267 +1325,6 @@ class Spec(object):
         return out
 
 
-    def graph(self, **kwargs):
-        N      = kwargs.get('node', 'o')        # Node character
-        color  = kwargs.get('color', True)
-        out    = kwargs.get('out', ColorStream(sys.stdout, color=color))
-        debug  = kwargs.get('debug', False)
-        indent = kwargs.get('indent', 0)
-        indent *= ' '
-
-        topo_order = self.topological_sort(reverse=True)
-
-        # Work on a clone so the spec is self contained (no incoming
-        # parent edges), and so we don't destroy this spec.
-        clone = self.copy()
-
-        # Fast access to nodes in the spec.
-        nodes = clone.index()
-
-        # Colors associated with each node in the DAG.
-        # Edges are colored by the node they point to.
-        all_colors = 'rgbmcyRGBMCY'
-        colors = dict((name, all_colors[i % len(all_colors)])
-                      for i, name in enumerate(topo_order))
-        def write_edge(string, index, sub=0):
-            edge = "@%s{%s}" % (colors[frontier[index][sub]], string)
-            out.write(edge)
-
-        frontier = []
-
-        def ordered_deps(node):
-            deps = node.dependencies
-            return sorted((d for d in deps), reverse=True)
-
-
-        def back_edge(prev_ends, end, start, collapse, label=None):
-            # Use prev & next for pipelining -- pipelined edges have
-            # the same start, and they're in sorted order e.g.::
-            #
-            #               start
-            #       | |_|_|_|/|
-            #       |/| | |_|/|
-            #       | | |/| | |  <-- when doing this line.
-            #    prev end
-            #
-            out.write(indent)
-
-            f = len(frontier)
-
-            self._pos = 0
-            def advance(to, fun):
-                for i in range(self._pos, to):
-                    fun()
-                    self._pos += 1
-
-            for p in prev_ends:
-                advance(p,             lambda: write_edge("| ", self._pos))
-                advance(p+1,           lambda: write_edge("|/", self._pos))
-            if end >= 0:
-                advance(end + 1,       lambda: write_edge("| ", self._pos))
-                advance(start - 1,     lambda: (write_edge("|", self._pos) or
-                                                write_edge("_", end)))
-            else:
-                advance(start - 1,     lambda: write_edge("| ", self._pos))
-
-            if start >= 0:
-                advance(start,         lambda: (write_edge("|", self._pos) or
-                                                write_edge("/", end)))
-
-            if collapse:
-                advance(len(frontier), lambda: write_edge(" /", self._pos))
-            else:
-                advance(len(frontier), lambda: write_edge("| ", self._pos))
-
-            if debug:
-                out.write(" " * 10)
-                if label: out.write(label)
-                out.write("%s" % frontier)
-
-            out.write("\n")
-
-
-        def connect_deps(i, deps, collapse, label):
-            """Connect dependencies to frontier at position i."""
-            if len(deps) == 1 and deps in frontier:
-                j = frontier.index(deps)
-
-                # connect to the left
-                if j < i:
-                    if i-j > 1:   # two lines if distance > 1
-                        back_edge([], j,  i, True, label)
-                    back_edge([j], -1, -1, (i-j == 1), label)
-
-                # connect to the right
-                else:
-                    if i < j:
-                        frontier.pop(j)
-                        frontier.insert(i, deps)
-                    if j-i > 1:
-                        back_edge([], i, j+1, collapse, label)
-                    back_edge([i], -1,  -1, not (j-i > 1) and collapse, label)
-                return True
-
-            elif deps:
-                frontier.insert(i, deps)
-                return False
-
-
-        def add_deps_to_frontier(node, i):
-            """Add dependencies to frontier, connecting them if they're fully
-               expanded, and deleting parent pointers."""
-            deps = ordered_deps(node)
-            connect_deps(i, deps, True, "add_deps")
-            for d in deps:
-                del nodes[d].dependents[node.name]
-
-
-        def find(seq, predicate):
-            for i, elt in enumerate(seq):
-                if predicate(elt):
-                    return i
-            return -1
-
-
-        add_deps_to_frontier(self, 0)
-        out.write(indent)
-        out.write('%s  %s\n' % (N, self.name))
-        topo_order.pop()
-
-        while frontier:
-            # Find an unexpanded part of frontier
-            i = find(frontier, lambda f: len(f) > 1)
-
-            # Expand frontier until there are enough columns for all children.
-            if i >= 0:
-                # Figure out how many back connections there are and
-                # sort them so we do them in order
-                back = []
-                for d in frontier[i]:
-                    b = find(frontier[:i], lambda f: f == [d])
-                    if b != -1: back.append((b, d))
-
-                # Do all back connections in sorted order so we can
-                # pipeline them and save space.
-                if back:
-                    back.sort()
-
-                    prev_ends = []
-                    for j, (b, d) in enumerate(back):
-                        frontier[i].remove(d)
-                        if i-b > 1:
-                            back_edge(prev_ends, b, i, False)
-                            del prev_ends[:]
-                        prev_ends.append(b)
-                    back_edge(prev_ends, -1, -1, False)
-
-                if not frontier[i]:
-                    frontier.pop(i)
-
-                elif len(frontier[i]) > 1:
-                    # Expand forawrd after doing all back connections
-                    out.write(indent)
-                    for c in range(i):
-                        write_edge("| ", c)
-                    write_edge("|", i)
-
-                    if (i+1 < len(frontier) and len(frontier[i+1]) == 1
-                        and frontier[i+1][0] in frontier[i]):
-                        # We need to connect to the element to the right.
-                        # Keep lines straight by connecting directly and
-                        # avoiding immediate expand/contract.
-                        name = frontier[i+1][0]
-                        frontier[i].remove(name)
-
-                        write_edge("\\", i+1)
-                        for c in range(i+1, len(frontier)):
-                            write_edge("| ", c )
-                        out.write("\n")
-
-                    else:
-                        # Just allow the expansion here.
-                        name = frontier[i].pop(0)
-                        deps = [name]
-                        write_edge("\\", i)
-                        for c in range(i+1, len(frontier)):
-                            write_edge(" \\", c)
-                        out.write("\n")
-                        connect_deps(i, deps, True, "expansion")
-
-                # Handle any remaining back edges to the right
-                j = i+1
-                while j < len(frontier):
-                    deps = frontier.pop(j)
-                    # TODO: semantics of connect_deps are weird.
-                    # TODO: false return means the popped item was put
-                    # TODO: back & not connected.
-                    if not connect_deps(j, deps, True, "rem_back"):
-                        j += 1
-
-            else:
-                name = topo_order.pop()
-                node = nodes[name]
-
-                # Find the next node in topo order and remove it from
-                # the frontier. Since specs are single-rooted DAGs,
-                # the node is always there. If the graph had multiple
-                # roots, we'd need to handle that case case of a new root.
-                i = find(frontier, lambda f: name in f)
-                frontier.pop(i)
-
-                out.write(indent)
-                for c in range(i):
-                    write_edge("| ", c)
-                out.write("%s " % N)
-                for c in range(i, len(frontier)):
-                    write_edge("| ", c)
-                out.write(" %s\n" % name)
-
-                if node.dependencies:
-                    add_deps_to_frontier(node, i)
-                elif frontier:
-                    out.write(indent)
-                    for c in range(i):
-                        write_edge("| ", c)
-                    for c in range(i, len(frontier)):
-                        write_edge(" /", c)
-                    out.write("\n")
-
-
-    def topological_sort(self, **kwargs):
-        """Return a list of dependency specs sorted topologically.
-           This spec is not modified in the process."""
-        reverse = kwargs.get('reverse', False)
-        if not reverse:
-            parents  = lambda s: s.dependents
-            children = lambda s: s.dependencies
-        else:
-            parents  = lambda s: s.dependencies
-            children = lambda s: s.dependents
-
-        spec = self.copy()
-        nodes = spec.index()
-
-        topo_order = []
-        remaining = [name for name in nodes.keys() if not parents(nodes[name])]
-        heapify(remaining)
-
-        while remaining:
-            name = heappop(remaining)
-            topo_order.append(name)
-
-            node = nodes[name]
-            for dep in children(node).values():
-                del parents(dep)[node.name]
-                if not parents(dep):
-                    heappush(remaining, dep.name)
-
-        if any(parents(s) for s in spec.traverse()):
-            raise ValueError("Spec has cycles!")
-        else:
-            return topo_order
-
-
     def __repr__(self):
         return str(self)