def test_simple(self):
        self.assertEqual(list(toposort({2: {11},
                                        9: {11, 8},
                                        10: {11, 3},
                                        11: {7, 5},
                                        8: {7, 3},
                                        })),
                         [{3, 5, 7},
                          {8, 11},
                          {2, 9, 10},
                          ])

        # make sure self dependencies are ignored
        self.assertEqual(list(toposort({2: {2, 11},
                                        9: {11, 8},
                                        10: {10, 11, 3},
                                        11: {7, 5},
                                        8: {7, 3},
                                        })),
                         [{3, 5, 7},
                          {8, 11},
                          {2, 9, 10},
                          ])

        self.assertEqual(list(toposort({1: set()})),
                         [{1}])
        self.assertEqual(list(toposort({1: {1}})),
                         [{1}])

    def test_cycle(self):
        # a simple, 2 element cycle
        self.assertRaises(ValueError, list, toposort({1: {2},
                                                      2: {1}
                                                      }))

        # an indirect cycle
        self.assertRaises(ValueError, list, toposort({1: {2},
                                                      2: {3},
                                                      3: {1},
                                                      }))

    def test_no_dependencies(self):
        self.assertEqual(list(toposort({1: {2},
                                        3: {4},
                                        5: {6},
                                        })),
                         [{2, 4, 6}, {1, 3, 5}])

        self.assertEqual(list(toposort({1: set(),
                                        3: set(),
                                        5: set(),
                                        })),
                         [{1, 3, 5}])

def arrangeNodes(dg):
    ts = list(toposort.toposort(dg))
    xc = 0
    ips = {}
    for st in ts:
        yps = [];
        st = list(st)
        for si in st:
            if si in dg.keys():
                ri = list(dg[si])
                yp = np.mean([ips[rr][1] for rr in ri])
            else:
                yp = 0
            
            while yp in yps:
               yp += 1
               
            yps.append(yp)
                
        #ysi = np.argsort(yps) 
        #ys = (np.arange(len(ysi)) - ysi.mean())
        ysi = np.arange(len(yps))
        ys = yps
        for i, yi in zip(ysi, ys):
            ips[st[i]] = (xc, yi)
        
        xc += 1
        
    return ips

    def _sort_tasks(task_list):
        """
        Take the list of tasks in any order and sort them topologically
        so the resulting list and be executed correctly.
        :param task_list: List of LocalTask objects
        :return: Sorted list of LocalTask objects
        """

        # Create a list of
        tasks_w_deps = {}
        for task in task_list:
            deps = []
            for port_name in task.inputs.portnames:
                port = task.inputs.__getattribute__(port_name)
                if isinstance(port.value, local_task.Directory):
                    if port.value.parent not in task_list:
                        raise LocalWorkflowError('Task %s is missing from workflow' % port.value.parent.type)
                    deps.append(port.value.parent)
            tasks_w_deps[task] = set(deps)

        sorted_list =[]
        for x in toposort(tasks_w_deps):
            sorted_list += list(x)

        return sorted_list

def split_dags(forest):
  parents = defaultdict(set)
  def find_parents(expr):
    for child in expr.children:
      parents[child].add(expr)
      find_parents(child)

  for expr in forest:
    find_parents(expr)

  def contains(tree, expr):
    if tree == expr:
      return True
    else:
      return any(contains(child, expr) for child in tree.children)

  exprs = forest + [expr for expr in parents if len(parents[expr]) > 1]

  # TODO: This is O(n^3)
  deps = {expr: set() for expr in exprs}
  for i in xrange(len(exprs)):
    for j in xrange(len(exprs)):
      if i == j:
        continue

      if contains(exprs[i], exprs[j]):
        deps[exprs[i]].add(exprs[j])
  return list(toposort(deps))

def test_toposort():
  tf.reset_default_graph()
  nodes = util.make_caterpillar_graph(length=2)
  graph = linearize_lib.get_graph()
  initial = list(toposort(graph))[0]
  assert len(initial) == 1
  assert list(initial)[0].name == 'merge2'

def main():
    args = parse_args()
    logging.basicConfig(level=args.loglevel)

    if has_path is False or has_toposort is False:
        LOG.error('Your python environment is missing required modules')
        sys.exit(1)

    dirs = {}

    for item in (Path(dir) for dir in args.dirs):
        if item.name.startswith('.'):
            continue

        if not item.is_dir():
            LOG.warn('skipping %s (not a directory)', item)
            continue

        dirs[item] = {
            'requires': [],
            'required_by': [],
            'provides': [],
        }

        this = dirs[item]

        for reqtype in this.keys():
            LOG.debug('check %s %s', item.name, reqtype)
            try:
                with (item / '.deps' / reqtype).open() as fd:
                    LOG.debug('reading %s deps for %s', reqtype, item.name)
                    this[reqtype] = fd.read().splitlines()
            except IOError:
                continue

    # generated provided_by dictionary
    provided_by = {}
    for k, v in dirs.items():
        provided_by[k.name] = k
        for provide in v['provides']:
            provided_by[provide] = k

    order = {}
    for k, v in dirs.items():
        order.setdefault(k, set())
        for req in v['requires']:
            LOG.debug('%s requires %s (provided by %s)',
                      k, req, provided_by[req])
            order[k].add(provided_by[req])

        for req in v['required_by']:
            LOG.debug('%s is required by %s (via %s)',
                      k, provided_by[req], req)
            order.setdefault(provided_by[req], set()).add(k)

    order = [item for stage in toposort.toposort(order)
             for item in stage]

    print ' '.join(str(x) for x in order)

 def test_input_not_modified_when_cycle_error(self):
     data = {1: {2},
             2: {1},
             3: {4},
             }
     orig = data.copy()
     self.assertRaises(ValueError, list, toposort(data))
     self.assertEqual(data, orig)

def number_of_strongly_connected_components(adj, rev_adj):
    visited = set()
    cc = 0
    order = toposort(rev_adj)
    for v in order:
        if v not in visited:
            explore(v, adj, visited, cc)
            cc += 1
    return cc

 def test_input_not_modified(self):
     data = {2: {11},
             9: {11, 8},
             10: {11, 3},
             11: {7, 5},
             8: {7, 3, 8},  # includes something self-referential
             }
     orig = data.copy()
     results = list(toposort(data))
     self.assertEqual(data, orig)

 def calculate_dependencies():
     """Calculate test dependencies
     First do a topological sorting based on the dependencies.
     Then sort the different dependency groups based on priorities.
     """
     order = []
     for g in toposort(merge_dicts(dependencies, soft_dependencies)):
         for t in sorted(g, key=lambda x: (priorities[x], x)):
             order.append(t)
     return order

 def test_strings(self):
     self.assertEqual(list(toposort({'2': {'11'},
                                     '9': {'11', '8'},
                                     '10': {'11', '3'},
                                     '11': {'7', '5'},
                                     '8': {'7', '3'},
                                     })),
                      [{'3', '5', '7'},
                       {'8', '11'},
                       {'2', '9', '10'},
                       ])

    def calculate_dependencies():
        """Calculate test dependencies
        First do a topological sorting based on the dependencies.
        Then sort the different dependency groups based on priorities.
        """
        order = []
        for group in toposort(dependencies):
            priority_sorted_group = sorted(group, key=lambda x: (priorities[x], x))
            order.extend(priority_sorted_group)

        return order

def ops_in_toposorted_order(ops):
  """Produces ops in deterministic order such that children are executed
  after parents"""

  graph_dict = tf_ops_to_graph(ops)
  toposorted = toposort.toposort(graph_dict)
  ops = []
  # toposort assumes children are dependencies, reverse order
  for op_set in reversed(list(toposorted)):
    ops.extend(sorted(op_set, key=lambda op: op.name))
  return ops

def main():
    CARS = 10
    START_PTS = []
    END_PTS = []
    for i in xrange(CARS):
        START_PTS += [(100+i*30, 500, -math.pi/2)]
        START_PTS += [(100+i*30, 400, -math.pi/2)]
        END_PTS += [(370-i*30, 100, -math.pi/2)]
        END_PTS += [(370-i*30, 200, -math.pi/2)]
    
    dist_matrix = []
    for start_pt in START_PTS:
        dist_vec = []
        for end_pt in END_PTS:
            dist_vec.append(dubins.path_length(start_pt, end_pt, settings.TURNING_RADIUS))
        print dist_vec
        dist_matrix.append(dist_vec)        
    
    m = munkres.Munkres()
    indices = m.compute(dist_matrix)
    
    d_pt_match = {}
    for start_pt_ind, end_pt_ind in indices:
        d_pt_match[start_pt_ind] = end_pt_ind
    
    cars = []
    for i in xrange(CARS):
        cars.append((START_PTS[i], END_PTS[d_pt_match[i]]))
        print cars[-1]    
    
    COLLISION_DIST = 5
    d_collisions = {}    
    for i, (start_pt, end_pt) in enumerate(cars):
        d_collisions[i] = set()
        path, t = dubins.path_sample(start_pt, end_pt, settings.TURNING_RADIUS, 0.1)
        for j, (temp_start_pt, temp_end_pt) in enumerate(cars):
            if j == i:
                continue
            for pt in path:
                if norm(sub_vecs(pt, temp_end_pt)) < COLLISION_DIST:
                    d_collisions[i].add(j)

    print d_collisions
    cars_order = list(toposort.toposort(d_collisions))
            
    for car_set in cars_order[::-1]:
        print "Creating cars", car_set
        for car_ind in car_set:
            thread.start_new_thread(main_loop, ((cars[car_ind][0][0], cars[car_ind][0][1]), cars[car_ind][0][2],
                                                (cars[car_ind][1][0], cars[car_ind][1][1]), cars[car_ind][1][2]))
        time.sleep(10)

def ranks2order(ranks, majority = False):
    big = pd.DataFrame([[(ranks[j] > ranks[i]).sum() 
                         for i in ranks.columns] 
                        for j in ranks.columns])
    big.columns = ranks.columns
    big.index = ranks.columns
    if not majority:
        majority = big.max().max()
    graph = sorted(big[big >= majority].stack().index.tolist())
    big_dict = dict([(x, set(a[1] for a in y)) for (x, y) 
                     in itertools.groupby(graph, key=lambda x: x[0])])
    true_order = list(toposort.toposort(big_dict))
    print("Majority:", majority / len(ranks))
    return true_order

    def find_sync_groups(containers):
        deps = dict()
        name2container = dict()
        for container in containers:
            name2container[container.name] = container
            deps[container.name] = container.dependency_names()

        synch_groups = []
        for synch_group_names in toposort.toposort(deps):
            synch_group = set()
            for container_name in synch_group_names:
                synch_group.add(name2container[container_name])
            synch_groups.append(synch_group)

        return synch_groups

 def build_groups(self):
     """Return topological sort of dependency groups, i.e,
        list of sets of containers which can be built in groups."""
     result = []
     for t in list(toposort.toposort(self.build_depends())):
         if t == set(['']): # We don't have to build the null dependency
             continue
         group = []
         for tag in t:
             container_name = self.container_name_from_tag(tag)
             container = self.get_container(container_name)
             if container.buildable:
                 group.append(container_name)
         result.append(group)
     return result

 def _sort_modules(self):
     modules = {}
     for instance in self._instances:
         if not self._instances[instance]._disabled:
             _deps = self._instances[instance]._depends
             _afters = self._instances[instance]._after
             modules[instance] = _deps.union(_afters)
     try:
         return [m for m in toposort(modules) if m in self._instances]
     except ValueError as e:
         circular = findall('.*?\(\'?(\S+?)\'?,', e.args[0])
         for instance in circular:
             self._instances[instance]._disabled = True
         debug(_('Circular dependencies found, disabled modules: %s')
               % ', '.join(circular))
         return self._sort_modules()