def testAlreadyPrioritized(self):
     graph = {1: set([2]),
              2: set()}
     expected = deepcopy(graph)
     topo_prioritize(2, graph)
     self.assertEquals(graph, expected)
     sorted = toposort_flatten(graph)
     self.assertEqual(toposort_flatten(graph), [2, 1])

 def testAvoidCircularReference(self):
     graph = {1: set(),
              2: set([1])}
     expected = deepcopy(graph)
     topo_prioritize(2, graph)
     self.assertEquals(graph, expected)
     sorted = toposort_flatten(graph)
     self.assertEqual(toposort_flatten(graph), [1, 2])

 def testSimple(self):
     graph = {1: set(),
              2: set()}
     expected = deepcopy(graph)
     expected[1].add(2)
     topo_prioritize(2, graph)
     self.assertEquals(graph, expected)
     sorted = toposort_flatten(graph)
     self.assertEqual(toposort_flatten(graph), [2, 1])

 def order_modules(self):
     runorder = None
     try:
         dependencies = self.collect_dependencies()
         runorder = toposort_flatten(dependencies)
         self.compute_reachability(dependencies)
     except ValueError: # cycle, try to break it then
         # if there's still a cycle, we cannot run the first cycle
         logger.info('Cycle in module dependencies, trying to drop optional fields')
         dependencies = self.collect_dependencies(only_required=True)
         runorder = toposort_flatten(dependencies)
         self.compute_reachability(dependencies)
     return runorder

    def expand(self, states):
        seen = set()
        depends = defaultdict(list)
        queue = deque()
        for state in states:
            queue.append(state)
            seen.add(state)
        while len(queue):
            state = queue.popleft()
            for arc in self.get_arcs(state, EPSILON):
                depends[arc[1]].append((arc[0], arc[3]))
                if arc[1] in seen:
                    continue
                queue.append(arc[1])
                seen.add(arc[1])

        depends_for_toposort = {key: {state for state, weight in value}
                                for key, value in depends.items()}
        order = toposort_flatten(depends_for_toposort)

        next_states = states
        for next_state in order:
            next_states[next_state] = self.combine_weights(
                *([next_states.get(next_state)] +
                  [next_states[prev_state] + weight
                   for prev_state, weight in depends[next_state]]))

        return next_states

def get_dependency_map(
  depman: 'DependencyManager', mods: LilacMods,
) -> Dict[str, Set['Dependency']]:
  map: Dict[str, Set['Dependency']] = defaultdict(set)
  shallow_map: Dict[str, Set[str]] = defaultdict(set)
  rmap: Dict[str, Set[str]] = defaultdict(set)

  for name, mod in mods.items():
    depends = getattr(mod, 'repo_depends', ())

    ds = [depman.get(d) for d in depends]
    if ds:
      for d in ds:
        shallow_map[name].add(d.pkgname)
        rmap[d.pkgname].add(name)
      map[name].update(ds)

  dep_order = toposort_flatten(shallow_map)
  for name in dep_order:
    if name in rmap:
      deps = map[name]
      dependers = rmap[name]
      for dd in dependers:
        map[dd].update(deps)

  return map

    def ordered_task_instances_list(self):
        """
        Start from a root task, and read task dependencies recursively.
        """
        # NOTE consider Luiti modifies Luigi, same task instances maybe not unique. TODO Fix it
        def func(dep_dict, _curr_task):
            """ Generate a a dependencies graph. """
            required_task_instances = _curr_task.requires()

            # 1. clean dep normal tasks as a list
            if not isinstance(required_task_instances, list):
                required_task_instances = [required_task_instances]
            dep_dict[_curr_task] = filter(lambda t1: bool(t1) and (not isinstance(t1, RootTask)), required_task_instances)

            # 2. selected undone tasks
            if self.check_output_recursive:
                dep_dict[_curr_task] = filter(lambda t1: not t1.output().exists(), dep_dict[_curr_task])
            dep_dict[_curr_task] = set(dep_dict[_curr_task])

            # 3. recursive
            for t1 in dep_dict[_curr_task]:
                func(dep_dict, t1)

            return dep_dict

        # 1. generate a dep dict
        task_instances_dep_dict = func(dict(), self.curr_task_intance)

        # 2. sort the DAG.
        from toposort import toposort_flatten
        ordered_task_instances_list = toposort_flatten(task_instances_dep_dict)

        return ordered_task_instances_list

    def render_schema(self, **kwargs):
        "return full SQL schema built rendering indexed resources"

        # construct templating environment
        tplEnv = Environment(line_statement_prefix='--#')

        # build resource index
        rsrIdx = self.build_index()

        # iterates resource in 'topological' sorted order
        buf = []
        for rsr in toposort_flatten(rsrIdx):

            # process resource template if any
            if rsr.tplstr:

                # add source informations to tplstr
                tplstr = self._fileHead % (self.get_rpath(rsr), rsr.tplstr)

                # compile template
                tpl = tplEnv.from_string(tplstr)

                # prepare rendering context
                ctx = {}
                ctx.update(rsr.tpldefaults)
                ctx.update(kwargs)

                # render template
                buf.append(tpl.render(ctx))


        return u"\n".join(buf)

    def mount_lowerdirs(self):
        # First, build a dependency graph in order to avoid duplicate entries
        dependencies = {}

        def dependency_path(dep):
            if 'image' in dep:
                return Image.download(dep['image'], dep['version'])
            if ':' in dep['imageName']:  # It's an image
                return Image.download(dep['imageName'])
            else:  # It's a container
                container = self.__class__(dep['imageName'])
                path = dep.get('path', str((container.path / 'overlay.fs').resolve()))
                return os.path.join(dep['imageName'], path)

        pending_deps = set(map(dependency_path, self.dependencies))
        while len(pending_deps) > 0:
            path = pending_deps.pop()
            if isinstance(path, Image):
                path.extract()
                prev_layer = str(path.layers[-1].fs_path)
                dependencies[prev_layer] = set()
                for layer in reversed(path.layers[:-1]):
                    dependencies[prev_layer] = {str(layer.fs_path)}
                    prev_layer = str(layer.fs_path)
            else:
                name = path.split('/')[-2]
                if name not in dependencies:
                    dependencies[path] = set(map(dependency_path, self.__class__(name).dependencies))
                    pending_deps |= dependencies[path]

        # Then sort it topologically. The list is reversed, because overlayfs
        # will check the mounts in order they are given, so the base fs has to
        # be the last one.
        dependencies = reversed(list(toposort_flatten(dependencies)))
        return (os.path.join(self.metadata_dir, dep) for dep in dependencies)

def refresh_provisioning_playbook(arg_vars, project_root):
  cluster_id = arg_vars['cluster_id']
  tpl = util.provisioning_template()
  path = util.machine_profiles_path(project_root, cluster_id)
  profile_files = [f for f in listdir(path) if isfile(join(path, f))]

  services = {}
  service_graph = {}
  profiles = []
  for f in profile_files:
    with open((path + "/"  + f), "r") as handle:
      content = yaml.load(handle)
      profiles.append(content['profile_id'])
      for s in content.get('machine_services', []):
        rets = services.get(s, [])
        rets.append(content['profile_id'])
        services[s] = rets

  for s in services.keys():
    with open((project_root + "/ansible/roles/" + s + "/defaults/main.yml"), "r") as text_file:
      content = yaml.load(text_file)
      service_graph[s] = set(content.get('service_dependencies', {}))

  service_seq = toposort_flatten(service_graph)
  with open(util.provisioning_file(project_root, cluster_id), "w") as text_file:
    text_file.write(tpl.render(cluster_id = cluster_id,
                               services = services,
                               profiles = profiles,
                               service_seq = service_seq,
                               service_graph = service_graph))

def find_joins_for_tables(joins, base_table, required_tables):
    """
    Given a set of tables required for a slicer query, this function finds the joins required for the query and
    sorts them topologically.

    :return:
        A list of joins in the order that they must be joined to the query.
    :raises:
        MissingTableJoinException - If a table is required but there is no join for that table
        CircularJoinsException - If there is a circular dependency between two or more joins
    """
    dependencies = defaultdict(set)
    slicer_joins = {join.table: join
                    for join in joins}

    while required_tables:
        table = required_tables.pop()

        if table not in slicer_joins:
            raise MissingTableJoinException('Could not find a join for table {}'
                                            .format(str(table)))

        join = slicer_joins[table]
        tables_required_for_join = set(join.criterion.tables_) - {base_table, join.table}

        dependencies[join] |= {slicer_joins[table]
                               for table in tables_required_for_join}
        required_tables += tables_required_for_join - {d.table for d in dependencies}

    try:
        return toposort_flatten(dependencies, sort=True)
    except CircularDependencyError as e:
        raise CircularJoinsException(str(e))

def toposort_flatten_checking(d, sort=False):
    '''Essentially just toposort_flatten, but with checking for
       self-referential dependencies and defaulting to sort=False
       to preserves order when possible'''
    for k, v in d.iteritems():
        assert k not in v, 'Self-referencing dependency: {}'.format(k)
    return toposort.toposort_flatten(d, sort=sort)

 def step(self, name, deps, f, *args, **kwargs):
     """
     Function to add a step to the computational graph.
       deps [String]: a list of nodes in the graph that the function depends on
       f [Function]: node to execute
       args [List]: list of arguments to be passed into the function
     """
     # create a new stair for this function
     stair = Stair(name, deps, f,  *args, **kwargs)
     # update our computational graph with this stair
     self.stairs[name] = stair
     # check that we have the dependencies in the, and assume any
     # that aren't are inputs
     for dep in deps:
         # first check that the variable isn't already in the graph
         if dep in self.stairs: continue
         # create an input stair and enter it into our graph
         input_stair = Stair(dep, [], lambda v: v)
         self.stairs[dep] = input_stair
         self.graph[input_stair] = set([])
     # add our dependencie to the graph
     self.graph[stair] = set([self.stairs[dep] for dep in deps])
     # ensure that our new graph compiles
     self.slist = toposort_flatten(self.graph)
     # return self for chaining
     return self

def recreateSequence(darcs):
    from toposort import toposort_flatten
    
    dependFrom={}
    for u,v in darcs:
        dependFrom[v]=set([u])

    return toposort_flatten(dependFrom)

 def resolveDependencies(self):
     import toposort
     #build dependancy graph
                 
     dg = self.dependancyGraph()
     
     #solve the dependency tree        
     return toposort.toposort_flatten(dg)

def process_spec(specs):
    """Builds mapping class -> set of all descendants."""
    tree = dict((name, set(children)) for name, children, _ in specs)
    attr_map = dict((name, attrs) for name, _, attrs in specs)
    for node in toposort_flatten(tree):
        children = tree[node]
        for child in set(children):
            tree[node] |= tree[child]
    return tree, attr_map

    def create_base_query(self, sql_generator):
        self.anchor_table = self.get_data_table(self.PATIENTS).alias(self.BASE_PREFIX + self.PATIENTS)
        anchor_column = self.anchor_table.c.get(QDMConstants.PATIENT_ID_COL).label(self.outer_colname(QDMConstants.PATIENT_ID_COL))
        base_from = self.anchor_table
        base_select_cols = [anchor_column]

        so_list = list(toposort_flatten(self.raw_symbol_table.so_temporal_dependencies))
        self.merge_so_lists(so_list, self.data_criteria_names_used)
        so_done = []
        for var in self.variables.values():
            if not var.is_specific_occurrence_target():
                sel = var.get_selectable(self, correlate=False)
                query = sel.get_selectable()
                sel.set_subquery_table(sql_generator.create_table_from_select(var.get_short_name(), query))
                query = sel.get_selectable()            
                for colname in [QDMConstants.UNIQUE_ID, QDMConstants.STARTTIME, QDMConstants.ENDTIME]:
                    col = sel.get_column(colname)
                    if col is not None:
                        base_select_cols.append(col)
                base_from = base_from.join(query, sel.get_column(QDMConstants.PATIENT_ID_COL) == anchor_column, isouter=True)


        for var in self.specific_occurrence_targets.values():
            sel = var.get_selectable(self, correlate=False)
            query = sel.get_selectable()
            sel.set_subquery_table(sql_generator.create_table_from_select(var.get_short_name(), query))

        processed_sos = dict()            
        for var in self.specific_occurrences.values():                  
            sel = var.get_selectable(self, correlate=False)            
            root = var.get_raw_id().get_root()                        
            join_conds = [sel.get_column(QDMConstants.PATIENT_ID_COL) == anchor_column]
            prior_sos = processed_sos.get(root)
            if prior_sos == None:
                processed_sos[root] = [sel]
            else:
                for prior_so in prior_sos:
                    join_conds.append(sel.get_column(QDMConstants.UNIQUE_ID) !=
                                      prior_so.get_column(QDMConstants.UNIQUE_ID))
                prior_sos.append(sel)
            base_from = base_from.join(sel.get_from(), and_(*join_conds), isouter=True)
            for colname in [QDMConstants.UNIQUE_ID, QDMConstants.STARTTIME, QDMConstants.ENDTIME]:
                col = sel.get_column(colname)
                if col is not None:
                    base_select_cols.append(col.label(var.to_so_colname(col.name)))


#        base_select = select(base_select_cols).select_from(base_from)
#        self.base_select = base_select.alias('patient_base')
#        self.anchor_column = self.base_select.corresponding_column(anchor_column)
        self.base_select = sql_generator.create_table_from_select('patient_base', select(base_select_cols).select_from(base_from))
        for var in self.specific_occurrences.values():
            for colname in [QDMConstants.UNIQUE_ID, QDMConstants.STARTTIME, QDMConstants.ENDTIME]:
                var.get_selectable(self).set_column(colname, self.base_select.c.get(var.to_so_colname(colname)))
        self.anchor_column = self.base_select.c.get(self.outer_colname(QDMConstants.PATIENT_ID_COL))
        self.anchor_table = self.base_select

 def testMiddle(self):
     #
     graph = {1: set(),
              2: set([3]),
              3: set()}
     expected = deepcopy(graph)
     expected[1].add(2)
     topo_prioritize(2, graph)
     self.assertEquals(graph, expected)
     self.assertEqual(toposort_flatten(graph), [3, 2, 1])

 def sortCodes(self):
     """put self.codes in a working evaluation order"""
     codeFromOutput = dict((c.outName, c) for c in self.codes)
     deps = {}
     for c in self.codes:
         outName = c.outName
         inNames = c.possibleVars.intersection(codeFromOutput.keys())
         inNames.discard(outName)
         deps[outName] = inNames
     self.codes = [codeFromOutput[n] for n in toposort.toposort_flatten(deps)]

    def test_sort_flatten(self):
        data = {2: {11},
                9: {11, 8},
                10: {11, 3},
                11: {7, 5},
                8: {7, 3, 8},  # includes something self-referential
                }
        expected = [{3, 5, 7}, {8, 11}, {2, 9, 10}]
        self.assertEqual(list(toposort(data)), expected)

        # now check the sorted results
        results = []
        for item in expected:
            results.extend(sorted(item))
        self.assertEqual(toposort_flatten(data), results)

        # and the unsorted results. break the results up into groups to compare them
        actual = toposort_flatten(data, False)
        results = [{i for i in actual[0:3]}, {i for i in actual[3:5]}, {i for i in actual[5:8]}]
        self.assertEqual(results, expected)