
def topological_sort(start_nodes, dependencies):
    """
    Return a topologically sorted list of :param:`start_nodes` and
    :param:`dependencies`.

    Nodes are checked on identity, not equality.

    Raises a ValueError if no topological sort is possible.

    :param start_nodes: list of nodes of graph with no incoming edges
    :param dependencies: list of dependency edges; ([dependencies], target),
                         dependencies may be of any sequence or be atomic
    :returns: topologically sorted nodes
    :rtype: list of nodes
    """
    seen = set(start_nodes)
    for deps, target in dependencies:
        if deps is None:
            seen.add(target)
    order = list(seen)
    old_dependencies = []
    while True:
        dependencies = [(deps, target) for deps, target in dependencies if target not in seen]
        if not dependencies:
            return order
        if old_dependencies == dependencies:
            raise ValueError("no topological sort possible")

        for deps, target in dependencies:
            # test for sequences
            try:
                deps = iter(deps)
            # atomic object
            except TypeError:
                deps = [deps]
            if all(dep in seen for dep in deps):
                order.append(target)
                seen.add(target)
        # copy dependencies to check progress
        old_dependencies = list(dependencies)


def topological_sort(start_nodes, dependencies):
    """
    Return a topologically sorted list of :param:`start_nodes` and
    :param:`dependencies`.

    Nodes are checked on identity, not equality.

    Raises a ValueError if no topological sort is possible.

    :param start_nodes: sequence of nodes of graph with no incoming edges
    :param dependencies: sequence of dependency edges; ([dependencies], target),
                         dependencies may be of any sequence or be atomic, if
                         there is no dependency it must be ``None``
    :returns: topologically sorted nodes
    :rtype: list of nodes
    """
    seen = set(start_nodes)
    for deps, target in dependencies:
        if deps is None:
            seen.add(target)
    order = list(seen)
    old_dependencies = []
    while True:
        dependencies = [(deps, target) for deps, target in dependencies if target not in seen]
        if not dependencies:
            return order
        if old_dependencies == dependencies:
            raise ValueError("no topological sort possible")

        for deps, target in dependencies:
            # test for sequences
            try:
                deps = iter(deps)
            # atomic object
            except TypeError:
                deps = [deps]
            if all(dep in seen for dep in deps):
                order.append(target)
                seen.add(target)
        # copy dependencies to check progress
        old_dependencies = list(dependencies)

Fix documentation of top sort.
Fix documentation of top sort.

Change wording from list to sequence and include note about how to
specify no dependencies.

Signed-off-by: Michael Markert <5eb998b7ac86da375651a4cd767b88c9dad25896@googlemail.com>

  
  def topological_sort(start_nodes, dependencies):
      """
      Return a topologically sorted list of :param:`start_nodes` and
      :param:`dependencies`.
  
      Nodes are checked on identity, not equality.
  
      Raises a ValueError if no topological sort is possible.
  
-     :param start_nodes: list of nodes of graph with no incoming edges
+     :param start_nodes: sequence of nodes of graph with no incoming edges
-     :param dependencies: list of dependency edges; ([dependencies], target),
+     :param dependencies: sequence of dependency edges; ([dependencies], target),
-                          dependencies may be of any sequence or be atomic
+                          dependencies may be of any sequence or be atomic, if
+                          there is no dependency it must be ``None``
      :returns: topologically sorted nodes
      :rtype: list of nodes
      """
      seen = set(start_nodes)
      for deps, target in dependencies:
          if deps is None:
              seen.add(target)
      order = list(seen)
      old_dependencies = []
      while True:
          dependencies = [(deps, target) for deps, target in dependencies if target not in seen]
          if not dependencies:
              return order
          if old_dependencies == dependencies:
              raise ValueError("no topological sort possible")
  
          for deps, target in dependencies:
              # test for sequences
              try:
                  deps = iter(deps)
              # atomic object
              except TypeError:
                  deps = [deps]
              if all(dep in seen for dep in deps):
                  order.append(target)
                  seen.add(target)
          # copy dependencies to check progress
          old_dependencies = list(dependencies)
  
Fix documentation of top sort.
## Code Before:

def topological_sort(start_nodes, dependencies):
    """
    Return a topologically sorted list of :param:`start_nodes` and
    :param:`dependencies`.

    Nodes are checked on identity, not equality.

    Raises a ValueError if no topological sort is possible.

    :param start_nodes: list of nodes of graph with no incoming edges
    :param dependencies: list of dependency edges; ([dependencies], target),
                         dependencies may be of any sequence or be atomic
    :returns: topologically sorted nodes
    :rtype: list of nodes
    """
    seen = set(start_nodes)
    for deps, target in dependencies:
        if deps is None:
            seen.add(target)
    order = list(seen)
    old_dependencies = []
    while True:
        dependencies = [(deps, target) for deps, target in dependencies if target not in seen]
        if not dependencies:
            return order
        if old_dependencies == dependencies:
            raise ValueError("no topological sort possible")

        for deps, target in dependencies:
            # test for sequences
            try:
                deps = iter(deps)
            # atomic object
            except TypeError:
                deps = [deps]
            if all(dep in seen for dep in deps):
                order.append(target)
                seen.add(target)
        # copy dependencies to check progress
        old_dependencies = list(dependencies)

## Instruction:
Fix documentation of top sort.
## Code After:

def topological_sort(start_nodes, dependencies):
    """
    Return a topologically sorted list of :param:`start_nodes` and
    :param:`dependencies`.

    Nodes are checked on identity, not equality.

    Raises a ValueError if no topological sort is possible.

    :param start_nodes: sequence of nodes of graph with no incoming edges
    :param dependencies: sequence of dependency edges; ([dependencies], target),
                         dependencies may be of any sequence or be atomic, if
                         there is no dependency it must be ``None``
    :returns: topologically sorted nodes
    :rtype: list of nodes
    """
    seen = set(start_nodes)
    for deps, target in dependencies:
        if deps is None:
            seen.add(target)
    order = list(seen)
    old_dependencies = []
    while True:
        dependencies = [(deps, target) for deps, target in dependencies if target not in seen]
        if not dependencies:
            return order
        if old_dependencies == dependencies:
            raise ValueError("no topological sort possible")

        for deps, target in dependencies:
            # test for sequences
            try:
                deps = iter(deps)
            # atomic object
            except TypeError:
                deps = [deps]
            if all(dep in seen for dep in deps):
                order.append(target)
                seen.add(target)
        # copy dependencies to check progress
        old_dependencies = list(dependencies)
