def dls_test_successor(self):
     result = nx.dfs_successors(self.G, source=4, depth_limit=3)
     assert_equal({n: set(v) for n, v in result.items()},
                  {2: {1, 7}, 3: {2}, 4: {3, 5}, 5: {6}})
     result = nx.dfs_successors(self.D, source=7, depth_limit=2)
     assert_equal({n: set(v) for n, v in result.items()},
                  {8: {9}, 2: {3}, 7: {8, 2}})

    def test_make_agent_walk_along_nx_graph(self):
        nx_skeleton = networkx_utils.NxSkeleton()
        coords = np.array([[100, 100, 100], [100, 101, 100],
                           [100, 102, 101], [100, 103, 102], [100, 104, 103], [100, 105, 104]])
        edgelist = [(0, 1), (1, 2), (2, 3), (3, 4), (4, 5)]
        nx_skeleton.initialize_from_edgelist(coords, edgelist)

        nm = neuron_maze.NeuronMaze()
        nm.make_agent_walk_along_nx_graph(nx_skeleton, 0, 5)
        self.assertEqual(nm.hero.visited_positions[1], tuple(coords[1]))
        first_direction = Vector3(0, 1, 0)
        self.assertEqual(nm.directions.index(first_direction), nm.hero.taken_actions[0])


        current_nx_graph = nm.nx_skeletons.nx_graph_dic[1]
        nx_skeleton = networkx_utils.NxSkeleton(nx_graph=current_nx_graph)

        source = networkx_utils.get_nodes_with_a_specific_degree(current_nx_graph,
                                                                  degree_value=1)
        source_node = source[0]
        number_of_steps = 5
        successor_dic = nx.dfs_successors(current_nx_graph, source=source[0])
        for steps in range(number_of_steps):
            source = successor_dic[source[0]]
        target_node = source[0]
        print 'source node', source_node
        print 'target node', target_node
        nm = neuron_maze.NeuronMaze()
        nm.make_agent_walk_along_nx_graph(nx_skeleton, source_node, target_node)

def _get_ancestry_table(g):
    rows = []
    for n in g.nodes():
        for ancestors in nx.dfs_successors(g, n).values():
            for ancestor in ancestors:
                rows.append((ancestor, n))
    return pd.DataFrame(rows, columns=["Ancestor", "Descendant"])

def list_dependencies(G, source_filter_function):
    source_nodes = filter(source_filter_function, G.nodes())

    for n in source_nodes:
        print '\n\n----------------------------------------'
        print 'Dependencies of %s:' % n
        for d in sorted(nx.dfs_successors(G, n)):
            print d

 def prune(self, images):
     ''' Prune not in images '''
     nodes = {}
     for image in images:
         nodes[image] = []
         nodes.update(networkx.dfs_successors(self.graph, source=image))
     nodes = set([item for key, values in nodes.items() for item in [key]+values])
     self.graph.remove_nodes_from(set(self.graph.nodes()) - set(nodes))

	def get_nounPharse_short(self, nounhead):
		npIDs=[]
		if(self.udgraph.node[nounhead]['pos'] in ['NOUN','PROPN']):
			allsuccessors = nx.dfs_successors(self.udgraph,nounhead)

			flag = True
			parents = [nounhead]
			
			while len(parents)>0:
				temp = []
				for parent in parents:
					if parent in allsuccessors.keys():
						for child in allsuccessors[parent]:
							if (parent==nounhead and self.udgraph[parent][child]['relation'] not in ['acl','acl:relcl','cc','conj','appos','punct','amod']):
							#or (parent!=nounhead and self.udgraph[parent][child]['relation'] not in ['acl','acl:relcl','appos','dobj','punct']):
								#if parent!=nounhead or self.udgraph[parent][child]['relation'] not in []:
								npIDs.append(child)
								temp.append(child)
				parents = temp
			
			'''
			for parent,child in allsuccessors.items():
				print(str(parent))
				print(child)
			'''		
			#raw_input(" ")

			#for value in allsuccessors.values():
			#	npIDs.extend(value)
			#print(npIDs)

		npIDs.append(nounhead)
		npTokens =[]
		npIDs.sort()
		#print(npIDs)

		start = 0
		for i in range(0,len(npIDs)):
			if self.udgraph.node[npIDs[i]]['pos']=='ADP':
				start = i+1
		npIDs = npIDs[start:]

		flag = False
		for i in range(1,len(npIDs)):
			if npIDs[i]-npIDs[i-1] != 1:
				flag = True

		if flag == True:
			npIDs = []
			npIDs.append(nounhead)


		for npID in npIDs:
			npTokens.append(self.udgraph.node[npID]['token'])
			
		nounPhrase = (' ').join(npTokens)

		return nounPhrase

 def successors(self):
     ''' Add attribute successors to all nodes '''
     successors = {}
     for image in self.graph.nodes_iter():
         successors[image] = len(set([
             successor
             for values in networkx.dfs_successors(self.graph, source=image).values()
             for successor in values
         ]))
     networkx.set_node_attributes(self.graph, 'successors', successors)

    def test_get_feasible_history(self):

        # This transition matrix is on a 4x4 grid.
        P = _mc0.get_example_transition_matrix()

        # Define a very sparse tree.
        T = nx.Graph()
        T.add_weighted_edges_from([
            (0, 12, 1.0),
            (0, 23, 2.0),
            (0, 33, 1.0),
            ])

        # Define the known states
        node_to_state = {
                12 : 11,
                23 : 14,
                33 : 41}

        # Define a root at a node with a known state,
        # so that we can avoid specifying a distribution at the root.
        root = 12
        T_aug = _sample_mcx.get_feasible_history(T, node_to_state,
                root=root, P_default=P)

        # The unweighted and weighted tree size should be unchanged.
        assert_allclose(
                T.size(weight='weight'), T_aug.size(weight='weight'))

        # Check that for each node in the initial tree,
        # all adjacent edges in the augmented tree have the same state.
        # Furthermore if the state of the node in the initial tree is known,
        # check that the adjacent edges share this known state.
        for a in T:
            states = set()
            for b in T_aug.neighbors(a):
                states.add(T_aug[a][b]['state'])
            assert_equal(len(states), 1)
            state = _util.get_first_element(states)
            if a in node_to_state:
                assert_equal(node_to_state[a], state)

        # Check that every adjacent edge pair is a valid transition.
        successors = nx.dfs_successors(T_aug, root)
        for a, b in nx.bfs_edges(T_aug, root):
            if b in successors:
                for c in successors[b]:
                    ab = T_aug[a][b]['state']
                    bc = T_aug[b][c]['state']
                    assert_(ab in P)
                    assert_(bc in P[ab])
                    assert_(P[ab][bc]['weight'] > 0)

def generate_dep_graph(l,filename, preprocessing=True, colors=True, write_gml=True):
    p=filter(lambda x: x.has_key('package'), l)
    #TODO: handling of install tags
    u=map(lambda x: x.strip(), filter(lambda x: x.has_key('request'), l)[0]['upgrade'].split(','))

    G=nx.DiGraph()
    versions=collect_versions(p)

    #****************************************************************************************
    #ADD DEPENDENCIES
    #****************************************************************************************
    #implicit
    for e in versions:
        if len(versions[e])>1:
            for v in ifilter(lambda x: x is not None, versions[e]):
                G.add_edge(tuple2str(e,None),tuple2str(e,v),property='implict',
                           graphics=gml_edge_graphics('implicit'))
    #explicit
    for r in p:
        v=(r['package'], r['version'])
        for cudf_property in cudf_properties:
            add(G,r,cudf_property,versions)

    if preprocessing:
        #****************************************************************************************
        #COLLECT RELEVANT VERSIONS
        #****************************************************************************************
        relevant_versions=[]
        for e in u:
            e=e.strip()
            if versions[e]:
                #TODO
                #tuple2str(e,reduce(lambda x,y: x if LooseVersion(x)>
                #         LooseVersion(y) else y, versions[e]))
                relevant_versions.append(e)
            else:
                relevant_versions.append(tuple2str(e,versions[e]))

        successors=set()
        for v in relevant_versions:
            ret = []
            for e,k in nx.dfs_successors(G,v).iteritems():
                ret.append(e)
                ret.extend(k)
            successors.update(ret)
        G=G.subgraph(list(successors)).copy()

        if colors:
            color_nodes(G,p,u,successors)
    if write_gml:
        nx.write_gml(G,filename)
    return G

 def getClusterMembers(self):
     '''
     '''
     G = self.G
     topnodes = [node for node in G.pred if not G.pred[node]]
     clusterMembers = defaultdict(list)
     for tnode in topnodes:
         dfs = nx.dfs_successors(G, tnode)
         for node in dfs:
             for mem in dfs[node]:
                 if int(mem.split('_')[0]) == 0:
                     clusterMembers[tnode].append(mem)
     return clusterMembers

def get_history_root_state_and_transitions(T, root=None):
    """

    Parameters
    ----------
    T : undirected weighted networkx tree with edges annotated with states
        A sampled history of states and substitution times on the tree.
    root : integer, optional
        The root of the tree.
        If not specified, an arbitrary root will be used.

    Returns
    -------
    root_state : integer
        The state at the root.
    transition_counts : directed weighted networkx graph
        A networkx graph that tracks the number of times
        each transition type appears in the history.

    """

    # Bookkeeping.
    degrees = T.degree()

    # Pick a root with only one neighbor if no root was specified.
    if root is None:
        root = _util.get_arbitrary_tip(T, degrees)

    # The root must have a well defined state.
    # This means that it cannot be adjacent to edges with differing states.
    root_states = [T[root][b]['state'] for b in T[root]]
    if len(set(root_states)) != 1:
        raise ValueError('the root does not have a well defined state')
    root_state = root_states[0]

    # Count the state transitions.
    transition_counts = nx.DiGraph()
    successors = nx.dfs_successors(T, root)
    for a, b in nx.bfs_edges(T, root):
        if degrees[b] == 2:
            c = _util.get_first_element(successors[b])
            sa = T[a][b]['state']
            sb = T[b][c]['state']
            if sa != sb:
                if transition_counts.has_edge(sa, sb):
                    transition_counts[sa][sb]['weight'] += 1
                else:
                    transition_counts.add_edge(sa, sb, weight=1)

    # Return the statistics.
    return root_state, transition_counts

def print_dependency_tree():
    """
    For each module, print the dependency tree for imported modules
    :return: None
    """
    print('\n=== Module Dependency Trees ===')
    for node_name in G.nodes_iter():
        if G.node[node_name][TAG_ATTR] != UNKNOWN_TAG:
            dg = nx.dfs_successors(G, node_name)
            plist = []
            print(augment_format_string(node_name, '\n%s:') % node_name)
            if len(dg):
                imports = dg[node_name]
                print_dependents(dg, plist, imports)

def rec_dfs_successor(G, node_name):
    """Recursively determines the successors of a node, returns a flat-list of such successors"""
    temp_affected_nodes = nx.dfs_successors(G, node_name).get(node_name, [])
    temp = []
    for temp_node in temp_affected_nodes:
        temp_list = rec_dfs_successor(G, temp_node)
        temp.append(temp_list)
    temp_affected_nodes.append(temp)

    if temp_affected_nodes:
        temp_affected_nodes = flatten_list(temp_affected_nodes)
        return list(set(temp_affected_nodes))
    else:
        return []

def dconn(gDir, path, conds):
	"""Check whether the path d-connects start and end nodes."""
	for idx in range(len(path) - 2):
		p1 = path[idx]
		p2 = path[idx + 1]
		p3 = path[idx + 2]
		if (gDir.has_edge(p1, p2) and gDir.has_edge(p3, p2)): # p1 -> p2 <- p3
			if (p2 not in conds):
				if not (len(set(nx.dfs_successors(gDir, p2)).intersection(conds)) > 0):					
					return False
		else:
			det = gDir.node[p2]["determines"]
			if (p2 in conds) or ((det is not None) and (det <= conds)):
				return False	
	return True

    def build(self):
        ''' Build '''
        queue_out = queue.Queue(maxsize=META['limits']['threads'])
        queue_in = queue.Queue()
        for _ in range(META['limits']['threads']):
            ThreadBuild(queue_out, queue_in).start()

        active = []
        while self.graph:
            degree = self.graph.in_degree()
            images = [image for image in degree if image not in active and degree[image] == 0]
            images = sorted(images, reverse=True,
                            key=lambda image: self.graph.node[image]['successors'])

            for image in images:
                try:
                    queue_out.put(image, block=False)
                except queue.Full:
                    break
                active.append(image)

            build = queue_in.get()
            active.remove(build.name)
            print('\n\033[33m### Build log: {0:s} ###\033[0m'.format(build.name))
            for line in build.log:
                if 'stream' in line:
                    print(line['stream'], end='')
                else:
                    print(line)
            if build.state == 'finished':
                print('\033[32m### Build finished: {0:s} ###\033[0m\n'.format(build.name))
                self.graph.remove_node(build.name)
            elif build.state == 'failed':
                print('\033[31m### Build failed: {0:s} ###\033[0m\n'.format(build.name))
                successors = networkx.dfs_successors(self.graph, source=build.name)
                if not successors:
                    self.graph.remove_node(build.name)
                else:
                    self.graph.remove_nodes_from(set(
                        [image for key, values in successors.items() for image in [key]+values]
                    ))
            else:
                raise RuntimeError('State is unknown: {0:s} {1:s}'.format(build.name, build.state))
            queue_in.task_done()

    def descendant_nodes(self, u):
        """
        Returns a set with all the descendents of u.

        EXAMPLE::
        
            >>> network = PhyloNetwork(eNewick="((,(3,4)#1)2,#1)1;")
            >>> network.nodes()
            ... ['_5', '_4', '_3', '_2', '_1', '#1']
            >>> network.node_by_taxa('2')
            ... '_2'
            >>> network.descendant_nodes('_2')
            ... ['_5', '_4', '#1' '_3', '_2']
            >>> network.strict_descendant_nodes('_2')
            ... ['_3', '_2']
            >>> network.descendant_taxa('_2')
            ... ['4', '3', '2']
            
        """
        return sum(list(dfs_successors(self, u).values()), [])+ [u]

def joins_from_successors(join_subgraph, root):
    """
    Creates a dfs successors tree and use it to create joins with root
    returns all inner joins list
    Example:
       root = 'a'        
       successors = {'a': ['c'], 
                     'c': ['j', 'f'], 
                     'f': ['i'], 
                     'j': ['k']} 
                     
       from a
        inner join c on a.id = c.id
            inner join j on j.id = c.id
                inner join k on k.id = j.id
            inner join f on f.id = c.id
                inner join i on i.id = f.id         
    """    
    successors = nx.dfs_successors(join_subgraph, root)
    return create_joins(successors, root, [])

def directLeafConnection(G, H):
    nodes = H.nodes()
    counter = 0
    while not udah_belom(H):
        if time.time()-waktu1 > 300:
            return H
        for x in nodes:
            counter += 1
            x_neigh = H.neighbors(x)
            if len(x_neigh) > 2:
                for y in x_neigh:
                    dummyGraph = H.copy()
    
                    dummyGraph.node[x]['neighbor_color'].remove(dummyGraph.node[y]['color'])        #remove neighbor color
                    dummyGraph.node[y]['neighbor_color'].remove(dummyGraph.node[x]['color'])        #remove neighbor color
                    dummyGraph.remove_edge(x,y)
    
                    tree = nx.dfs_successors(dummyGraph, x)
                    anak_anak = nx.dfs_predecessors(dummyGraph, x)
                    for anak in anak_anak:
                        if anak not in tree:
                            if validColor(dummyGraph, anak, y):
                                dummyGraph.add_edge(anak,y, weight=G[anak][y]['weight'])
                                addNeighborColor(dummyGraph, y, anak)
                                H = dummyGraph.copy()
                                #drawHraph(H)
                                break
            if counter%100000==0:
                print 'iteration: ', counter, ' in Direct Leaf Connection'
            if counter == 500001:
                #os.system('say "Redo from scratch"')
                mst = kruskal_mst(G)
                H = G.copy()
                H.remove_edges_from(H.edges())
                H.add_edges_from(mst)

                H = directLeafConnection(G, H)
                return H
    return H

        def getAtomByMolIndex(self,index):
                """Returns the Atom by it's index in the molecule where the index is defined as the number of bonds away from the anchor atom 
                (i.e. the atom at index 1 is the atom directly connected to the anchor atom)

                Parameters
                ----------
                index : int
                    The molecular index of the Atom object one wishes to retrieve where the index is defined as the number of bonds away from the anchor atom.

                Returns
                -------
                Atom Object
                    The Atom Object located at the specified index if the index is greater than the number of atoms in the molecule minus one then 
                    the function returns None as this is out of the range of the atom list.
                """
                if(index>(len(self.atoms)-1)):
                    return None
                successor_dict= ntwkx.dfs_successors(self.graph,source=self.anchorAtom.atomID)
                currentID = self.anchorAtom.atomID
                for i in range(index):
                    currentID = successor_dict[currentID][0]
                return self.getAtomByID(currentID)

    def _explore(self):
        """
        Starting from the start_node, explore the entire VFG, and perform the following:
        - Generate def-use chains for all registers and memory addresses using a worklist
        """

        # TODO: The worklist algorithm can definitely use some optimizations. It is a future work.

        # The worklist holds individual VFGNodes that comes from the VFG
        # Initialize the worklist with all nodes in VFG
        worklist = list(self._vfg.graph.nodes())
        # Set up a set of worklist for fast inclusion test
        worklist_set = set(worklist)

        # A dict storing defs set
        # variable -> locations
        live_defs_per_node = { }

        while worklist:
            # Pop out a node
            node = worklist[0]
            worklist_set.remove(node)
            worklist = worklist[ 1 : ]

            # Grab all final states. There are usually more than one (one state for each successor), and we gotta
            # process all of them
            final_states = node.final_states

            if node in live_defs_per_node:
                live_defs = live_defs_per_node[node]
            else:
                live_defs = { }
                live_defs_per_node[node] = live_defs

            successing_nodes = self._vfg.graph.successors(node)
            for state in final_states:
                if state.history.jumpkind == 'Ijk_FakeRet' and len(final_states) > 1:
                    # Skip fakerets if there are other control flow transitions available
                    continue

                # TODO: Match the jumpkind
                # TODO: Support cases where IP is undecidable
                corresponding_successors = [ n for n in successing_nodes if n.addr == state.se.eval(state.ip) ]
                if not corresponding_successors:
                    continue
                successing_node = corresponding_successors[0]

                new_defs = self._track(state, live_defs)

                if successing_node in live_defs_per_node:
                    defs_for_next_node = live_defs_per_node[successing_node]
                else:
                    defs_for_next_node = { }
                    live_defs_per_node[successing_node] = defs_for_next_node

                changed = False
                for var, code_loc_set in new_defs.iteritems():
                    if var not in defs_for_next_node:
                        defs_for_next_node[var] = code_loc_set
                        changed = True

                    else:
                        for code_loc in code_loc_set:
                            if code_loc not in defs_for_next_node[var]:
                                defs_for_next_node[var].add(code_loc)
                                changed = True

                if changed:
                    # Put all reachable successors back to our worklist again
                    if successing_node not in worklist_set:
                        worklist.append(successing_node)
                        worklist_set.add(successing_node)
                    all_successors_dict = networkx.dfs_successors(self._vfg.graph, source=successing_node)
                    for successors in all_successors_dict.values():
                        for s in successors:
                            if s not in worklist_set:
                                worklist.append(s)
                                worklist_set.add(s)