def _get_relevant_vars(self, g):
        """
        Args
        ----
        g : nx.DiGraph
            A graph of variable dependencies.

        Returns
        -------
        dict
            Dictionary that maps a variable name to all other variables in the
            graph that are relevant to it.
        """
        succs = {}
        for nodes in self.inputs:
            for node in nodes:
                succs[node] = set([v for u, v in nx.dfs_edges(g, node)])
                succs[node].add(node)

        relevant = {}
        grev = g.reverse()
        for nodes in self.outputs:
            for node in nodes:
                relevant[node] = set()
                preds = set([v for u, v in nx.dfs_edges(grev, node)])
                preds.add(node)
                for inps in self.inputs:
                    for inp in inps:
                        common = preds.intersection(succs[inp])
                        relevant[node].update(common)
                        relevant.setdefault(inp, set()).update(common)

        return relevant

def belief_propagation(graph, query_node=None):
    """Belief propagation.

    Perform exact inference on tree structured graphs.
    Return the belief of all query_nodes.

    """

    if query_node is None:  # pick random node
        query_node = choice(graph.get_vnodes())

    # Depth First Search to determine edges
    dfs = nx.dfs_edges(graph, query_node)

    # Convert tuple to reversed list
    backward_path = list(dfs)
    forward_path = reversed(backward_path)

    # Messages in forward phase
    for (v, u) in forward_path:  # Edge direction: u -> v
        msg = u.spa(v)
        graph[u][v]['object'].set_message(u, v, msg)

    # Messages in backward phase
    for (u, v) in backward_path:  # Edge direction: u -> v
        msg = u.spa(v)
        graph[u][v]['object'].set_message(u, v, msg)

    # Return marginal distribution
    return query_node.belief()

def depths(dg):
    """Return the depths of nodes in a directed
  graph."""
    depths = defaultdict(int)
    for (u, v) in nx.dfs_edges(dg):
        depths[v] = max(depths[v], depths[u] + 1)
    return depths

def compute_initial_guess(num_nodes, relative_rotations, relative_edges):
	graph = nx.Graph()
	graph.add_nodes_from(range(num_nodes))

	for (ind, edge) in enumerate(relative_edges):
		(n, theta) = so3.matrix_to_axis_angle(relative_rotations[ind])
		graph.add_edge(edge[0], edge[1], weight=theta, index=ind)

	tree = nx.minimum_spanning_tree(graph)

	global_rotation = []

	for i in range(num_nodes):
		global_rotation.append(numpy.identity(3))

	edges = nx.dfs_edges(tree, 0)

	for edge in edges:
		ind = graph[edge[0]][edge[1]]["index"]
		mat = relative_rotations[ind]

		if relative_edges[ind][0] == edge[0] and relative_edges[ind][1] == edge[1]:
			pass
		elif relative_edges[ind][0] == edge[1] and relative_edges[ind][1] == edge[0]:
			mat = mat.transpose()
		else:
			logging.error("GRAPH ERROR")

		global_rotation[edge[1]] = mat.dot(global_rotation[edge[0]])

	return global_rotation

def share_from_user(G, u, fl_dict):
    # compute BFS/DFS-tree with root u
    
#    tree_edges = nx.bfs_edges(G, u)        # use built-in
#    tree_edges = find_bfs_edges(G, u)        # use weighted
    
    tree_edges = nx.dfs_edges(G, u)
    
    
    # (exact) my friend list
    my_list = []
    for v in G.neighbors(u):
        my_list.append((u, v, 1.0))
    fl_dict[u].extend(my_list)

    # init
    list_at_node = [[] for v in G.nodes_iter()]
    
    # propagate
    for (v,w) in tree_edges:
#        print "v,w =", v, w 
        t_level = G.edge[v][w]['t']
        
        if v == u:  # prepare
            a_list = prepare_friend_list(G, u, t_level)
#            print "len(a_list) =", len(a_list)
            list_at_node[w] = a_list
        else:       # forward
            new_list = forward_friend_list(list_at_node[v], t_level)
#            print "len(new_list) =", len(new_list)
            list_at_node[w] = new_list
            
        # add new_list into fl_dict[w]
        fl_dict[w].extend(list_at_node[w])

def get_dependency_rules(graph, root_node=None,
                         node_attrib='label', edge_attrib='label'):
    """
    Given a graph, returns a set of its dependency rules. If root_node is
    given, returns only those rules from the subgraph rooted at that node.
    A dependency rules is represented by a
    (source node label, edge/relation label, target node label) triple, e.g.
    ('woman', 'dt', 'the').
    
    Returns
    -------
    rules : set of (str, str, str) tuples
        each dependency production rule is represented by a
        (source node label, edge/relation label, target node label)
        tuple
    """
    rules = set()

    if not root_node:
        # root node is the first element in a topological sort of the graph
        root_node = nx.topological_sort(graph)[0]

    for source, target in nx.dfs_edges(graph, root_node):
        rules.add( (ensure_utf8(graph.node[source].get(node_attrib, source)),
                    ensure_utf8(graph[source][target].get(edge_attrib, '')),
                    ensure_utf8(graph.node[target].get(node_attrib, target))) )
    return rules

    def _dfs_edges(graph, source, max_steps=None):
        """
        Perform a depth-first search on the given DiGraph, with a limit on maximum steps.

        :param networkx.DiGraph graph:  The graph to traverse.
        :param Any source:              The source to begin traversal.
        :param int max_steps:           Maximum steps of the traversal, or None if not limiting steps.
        :return: An iterator of edges.
        """

        if max_steps is None:
            yield networkx.dfs_edges(graph, source)

        else:
            steps_map = defaultdict(int)
            traversed = { source }
            stack = [ source ]

            while stack:
                src = stack.pop()
                for dst in graph.successors(src):
                    if dst in traversed:
                        continue
                    traversed.add(dst)

                    dst_steps = max(steps_map[src] + 1, steps_map[dst])

                    if dst_steps > max_steps:
                        continue

                    yield src, dst

                    steps_map[dst] = dst_steps
                    stack.append(dst)

    def _get_relevant_systems(self):
        """
        Given the dict that maps relevant vars to each VOI, find the mapping
        of each VOI to the set of systems that need to run.
        """
        relevant_systems = {}
        grev = self._sgraph.reverse()
        for voi, relvars in iteritems(self.relevant):
            rev = True if voi in self._outset else False
            if rev:
                voicomp = self._prom_to_abs[voi][0].rsplit('.', 1)[0]
                gpath = set([voicomp])
                gpath.update([v for u,v in nx.dfs_edges(grev, voicomp)])
            comps = set()
            for relvar in relvars:
                for absvar in self._prom_to_abs[relvar]:
                    parts = absvar.split('.')
                    for i in range(len(parts)-1):
                        cname = '.'.join(parts[:i+1])
                        # in rev mode, need to eliminate irrelevant systems that have shared promoted vars
                        if rev:
                            if cname in gpath:
                                comps.add(cname)
                        else:
                            comps.add(cname)
            relevant_systems[voi] = tuple(comps)

        return relevant_systems

def transitive_reduction(G): 
    TR = nx.DiGraph()
    TR.add_nodes_from(G.nodes())
    for u in G:
        u_edges = set(G[u])
        for v in G[u]:
            u_edges -= {y for x, y in nx.dfs_edges(G, v)}
        TR.add_edges_from((u,v) for v in u_edges)
    return TR    

 def run(self):
     done = []
     for task in nx.dfs_edges(self.execution_graph):
         if not task[0] in done:
             self.__execute__(task[0].label, task[0].executable, task[0].parameters)
         done.append(task[0])
         if not task[1] in done:
             self.__execute__(task[1].label, task[1].executable, task[1].parameters)
         done.append(task[1])

    def _check_graph(self, out_stream=sys.stdout):
        # Cycles in group w/o solver
        cgraph = self.root._relevance._cgraph
        for grp in self.root.subgroups(recurse=True, include_self=True):
            path = [] if not grp.pathname else grp.pathname.split('.')
            graph = cgraph.subgraph([n for n in cgraph if n.startswith(grp.pathname)])
            renames = {}
            for node in graph.nodes_iter():
                renames[node] = '.'.join(node.split('.')[:len(path)+1])
                if renames[node] == node:
                    del renames[node]

            # get the graph of direct children of current group
            nx.relabel_nodes(graph, renames, copy=False)

            # remove self loops created by renaming
            graph.remove_edges_from([(u,v) for u,v in graph.edges()
                                         if u==v])

            strong = [s for s in nx.strongly_connected_components(graph)
                        if len(s)>1]

            if strong and isinstance(grp.nl_solver, RunOnce): # no solver, cycles BAD
                relstrong = []
                for slist in strong:
                    relstrong.append([])
                    for s in slist:
                        relstrong[-1].append(name_relative_to(grp.pathname, s))
                        relstrong[-1] = sorted(relstrong[-1])
                print("Group '%s' has the following cycles: %s" %
                     (grp.pathname, relstrong), file=out_stream)

            # Components/Systems/Groups are not in the right execution order
            subnames = [s.pathname for s in grp.subsystems()]
            while strong:
                # break cycles to check order
                lsys = [s for s in subnames if s in strong[0]]
                for p in graph.predecessors(lsys[0]):
                    if p in lsys:
                        graph.remove_edge(p, lsys[0])
                strong = [s for s in nx.strongly_connected_components(graph)
                            if len(s)>1]

            visited = set()
            out_of_order = set()
            for sub in grp.subsystems():
                visited.add(sub.pathname)
                for u,v in nx.dfs_edges(graph, sub.pathname):
                    if v in visited:
                        out_of_order.add(v)

            if out_of_order:
                print("In group '%s', the following subsystems are out-of-order: %s" %
                      (grp.pathname, sorted([name_relative_to(grp.pathname, n)
                                                for n in out_of_order])), file=out_stream)

    def _get_relevant_vars(self, g):
        """
        Args
        ----
        g : nx.DiGraph
            A graph of variable dependencies.

        Returns
        -------
        dict
            Dictionary that maps a variable name to all other variables in the
            graph that are relevant to it.
        """

        relevant = {}
        succs = {}

        for nodes in self.inputs:
            for node in nodes:
                relevant[node] = set()
                succs[node] = set((node,))
                if node in g:
                    succs[node].update(v for u, v in nx.dfs_edges(g, node))

        grev = g.reverse()
        self._outset = set()
        for nodes in self.outputs:
            self._outset.update(nodes)
            for node in nodes:
                relevant[node] = set()
                if node in g:
                    preds = set(v for u, v in nx.dfs_edges(grev, node))
                    preds.add(node)
                    for inps in self.inputs:
                        for inp in inps:
                            if inp in g:
                                common = preds.intersection(succs[inp])
                                relevant[node].update(common)
                                relevant[inp].update(common)

        return relevant

def depth(dg):
    """Returns the depth of a directed graph.
  A single node has depth 0."""
    depths = defaultdict(int)
    for (u, v) in nx.dfs_edges(dg):
        depths[v] = max(depths[v], depths[u] + 1)
    if len(depths) > 0:
        return max(depths.values())
    elif len(dg.nodes()) == 0:  # No nodes in graph
        return None
    else:  # Nodes but no edges in graph
        return 0

def normalize_step_weight(graph):
    "Changes the edge weights in the graph proportional to the longest path."
    longest_path_len = max(nx.shortest_path_length(graph, "ROOT").values())
    # add normalized path length as weight to edges.
    for category in "ABCEDFGHJKLMNPQRSTUVWXZ":
        # for each category, find out how long the longest path is.
        cat_longest_path_len = max(nx.shortest_path_length(graph, category).values()) + 1
        # normalize the stepsize
        stepsize = float(longest_path_len) / cat_longest_path_len
        # traverse tree for this category and assign stepsize to edges as weight attribute
        for a, b in nx.dfs_edges(graph, category):
            graph[a][b]["weight"] = stepsize

def hierarchy(G, edge_type=EdgeTypes.parent):
    """Produce child nodes in a depth-first order."""
    for root in toplevel(G):
        dq = deque()
        yield G.node[root], len(dq)  # Depth 0
        # Iterate over all children
        dq.append(root)
        for src, dest in nx.dfs_edges(G, source=root):
            while len(dq) > 0 and dq[-1] != src:
                dq.pop()  # Unwind the stack
            if G.edge[src][dest].get('type') == edge_type:
                yield G.node[dest], len(dq)
            dq.append(dest)

def cart_to_internal(molecule):
    """ Converts the coordinates of the molecule from cartesian to internal
    coordinates. """
    # First decide on a starting atom
    source_node = molecule.atoms.nodes()[0]
    # Argh, dictionaries aren't sorted...
    completed_bonds = {source_node: []}
    for edge in nx.dfs_edges(molecule.atoms, source_node):
        completed_bonds[edge[1]] = [edge[0]]
    # completed_bonds[2] += [x for x in completed_bonds[1][1:] if x not in completed_bonds[2]]
    # completed_bonds[3] += [x for x in completed_bonds[2][1:] if x not in completed_bonds[3]]

    for entry in completed_bonds:
        print(entry, completed_bonds[entry])

 def findControllingNode(self, paramName):
     current, parent = self.currentContextName, self.currentContext.parentContext
     var = self.currentContext.parameters[paramName]
     child = None
     if not (parent and var.useParentValue):
         return None
     for child, parent in dfs_edges(self.dependencyGraph, parent):
         try:
             var = self.contextDict[parent].parameters[paramName]
             if not (var.useParentValue and var.hasParent):
                 return child
         except KeyError:
             return child
     return parent

	def get_bad_dest(self, b):
		# pick a random node near b
		count = 0
		ret = None
		for edge in nx.dfs_edges(self.graph, b):
			if count == 1000:
				break
			node = edge[1]
			count += 1
			if count == 1:
				ret = node
			i = randint(0, count - 1)
			if i == count - 1:
				ret = node
		return node

def transitive_reduction(G):
    """ Returns transitive reduction of a directed graph

    The transitive reduction of G = (V,E) is a graph G- = (V,E-) such that
    for all v,w in V there is an edge (v,w) in E- if and only if (v,w) is
    in E and there is no path from v to w in G with length greater than 1.

    Parameters
    ----------
    G : NetworkX DiGraph
        A directed acyclic graph (DAG)

    Returns
    -------
    NetworkX DiGraph
        The transitive reduction of `G`

    Raises
    ------
    NetworkXError
        If `G` is not a directed acyclic graph (DAG) transitive reduction is
        not uniquely defined and a :exc:`NetworkXError` exception is raised.

    References
    ----------
    https://en.wikipedia.org/wiki/Transitive_reduction

    """
    if not is_directed_acyclic_graph(G):
        msg = "Directed Acyclic Graph required for transitive_reduction"
        raise nx.NetworkXError(msg)
    TR = nx.DiGraph()
    TR.add_nodes_from(G.nodes())
    descendants = {}
    # count before removing set stored in descendants
    check_count = dict(G.in_degree)
    for u in G:
        u_nbrs = set(G[u])
        for v in G[u]:
            if v in u_nbrs:
                if v not in descendants:
                    descendants[v] = {y for x, y in nx.dfs_edges(G, v)}
                u_nbrs -= descendants[v]
            check_count[v] -= 1
            if check_count[v] == 0:
                del descendants[v]
        TR.add_edges_from((u, v) for v in u_nbrs)
    return TR

def cluster(g):
    clustered = []
    clusters = {}
    i = 1
    for n in g.nodes():
        c = [n]
        if n in clustered: continue
        edges = list(nx.dfs_edges(g,n))
        for e in edges:
            n1,n2 = e
            clustered+=[n1,n2]
            c+=[n1,n2]
        c = list(set(c))
        clusters[i] = {'num': len(c), 'fams': c[:]}
        i+=1
    return clusters