def test_single_source_shortest_path(self):
     p = nx.single_source_shortest_path(self.directed_cycle, 3)
     assert_equal(p[0], [3, 4, 5, 6, 0])
     p = nx.single_source_shortest_path(self.cycle, 0)
     assert_equal(p[3], [0, 1, 2, 3])
     p = nx.single_source_shortest_path(self.cycle, 0, cutoff=0)
     assert_equal(p, {0: [0]})

def gen_bonded_tuples(g, num, bond_pair):
    """Generates tuples of different size, based on the graph and input edge.

    Args:
        g: The networkx Graph object.
        num: The length of the tuple.
        bond_pair: The edge which has to be included in all tuples.

    Returns:
        The set of all tuples of defined length from graph `g`.
    """
    b0, b1 = bond_pair
    paths = []
    if num > 3:
        for nb0 in g[b0]:
            paths.extend(nx.single_source_shortest_path(g, nb0, num-1).values())
        for nb1 in g[b1]:
            paths.extend(nx.single_source_shortest_path(g, nb1, num-1).values())

    paths.extend(nx.single_source_shortest_path(g, b0, num-1).values())
    paths.extend(nx.single_source_shortest_path(g, b1, num-1).values())
    output = set()
    for b in paths:
        if len(b) == num and b0 in b and b1 in b:
            if tuple(reversed(b)) not in output:
                output.add(tuple(b))
    return output

 def get_upstream_reaches(self, outlet_reach, broken_at_gages=True):
     """Returns the comIDs of the upstream reaches for a given reach.  
     If no comID is specified, then all reaches in the network are 
     returned."""
     if broken_at_gages == True:
         return single_source_shortest_path(self._g_rev, outlet_reach)
     else:
         return single_source_shortest_path(self._g_unbroken_reverse, outlet_reach)

def neighbor_overlap_orderK(G,node1,node2,k):
    nei1=nx.single_source_shortest_path(G,node1,cutoff=k).keys()
    nei2=nx.single_source_shortest_path(G,node2,cutoff=k).keys()

    # return (x1, x2)
    # where x1 = the number of overlapped neighboring nodes
    # and   x2 = the number of overlapped neighboring nodes / the number of union(two neighborhood nodes)

    shared_neighbor=set(nei1).intersection(set(nei2))
    unioned_neighbor=set(nei1).union(set(nei2))

    return (len(shared_neighbor),float(len(shared_neighbor))/float(len(unioned_neighbor)))

def SampledDiameter(g):
  ns=g.nodes()
  pathLengths=[]
  for n in ns:
    paths=nx.single_source_shortest_path(g, n)
    pathLengths.extend([len(paths[n]) for n in paths.keys()])
  return max(pathLengths)

    def calc_star_uptime(self, n, link_fail):
        '''Calc star uptime.

        NOTE: n is the number of nodes.'''
        # Correct for NetworkX, which adds one to n.
        g = nx.star_graph(n - 1)
        # Node 0 is the center of the star.
        edges = g.number_of_edges()
        nodes = g.number_of_nodes()
        paths = nx.single_source_shortest_path(g, g.nodes()[1])
        used = flatten(paths)
        sssp_edges = used.number_of_edges()
        if sssp_edges != g.number_of_edges():
            raise Exception("edge not on sssp for star graph")

        # consider those times when a link failed:
        # first, consider failure on outside of graph
        exp_uptime_outer = link_fail * edges * ((float(edges - 1) / edges) * float(edges) / nodes + \
                                                (float(1) / edges) * float(1) / nodes)
        exp_uptime_outer += (1.0 - (link_fail * sssp_edges)) * 1.0

        # consider only the hub as a controller:
        exp_uptime_inner = link_fail * edges * ((float(edges) / edges) * float(edges) / nodes)
        exp_uptime_inner += (1.0 - (link_fail * edges)) * 1.0

        # merge:
        exp_uptime_weighted = float(edges * exp_uptime_outer + 1 * exp_uptime_inner) / nodes
        return exp_uptime_weighted

def chiral_order(atoms, chiral_atom, depth=6):
  # Create a list of ordered atoms to be passed back
  ordered = []
  # Do a quick check whether there are multiple hydrogens
  neighbors = atoms.neighbors(chiral_atom)
  hydrogens = [atom for atom in neighbors if atom.element == "H"]
  if len(hydrogens) < 2:
    tree = nx.bfs_tree(atoms, chiral_atom)
    # Generate the list of shortest paths in the molecule, neglecting the trivial path [chiral_atom]
    paths = sorted(nx.single_source_shortest_path(tree, chiral_atom, depth).values(), reverse = True)[:-1]
    while paths:
      # Pop the first element (highest priority path) from the list of paths and remove any duplicates.
      path = paths.pop(0)
      paths_no_dups = [unpruned for unpruned in paths if unpruned != path]
      # If there are any duplicates, the paths list will be smaller and we can't resolve a highest priority yet.
      if len(paths_no_dups) != len(paths):
        paths = paths_no_dups
      # Otherwise, the path is higher priority than all the other paths, so its second atom is the neighbour with
      # highest priority.
      else:
        ranked_atom = path[1]
        ordered.append(ranked_atom)
        # Drop all the paths containing our ranked atom.
        paths = [unpruned for unpruned in paths if unpruned[1] is not ranked_atom]
  return ordered

def get_forwarding_policy(topo, link_port_map):
    #rules = []

    pol = None
    base_ip = "10.0.%d.1"

    edge_nodes = [n for n in topo.nodes() if topo.node[n]["isHost"]]
    core_nodes = [n for n in topo.nodes() if topo.node[n]["isHost"] == False]

    # print "start"
    for u in edge_nodes: 
        dst_ip = base_ip % (u - 1)       
        
        paths = nx.single_source_shortest_path(topo, u)
        for v in edge_nodes:
            if u != v:
                pass
                # print u, v, paths[v]
        for s in core_nodes:
            next_hop = paths[s][-2]
            #m = match(switch = s, dstip = dst_ip).compile().rules[0].match 
            #act = fwd(link_port_map[s][next_hop]).compile().rules[0].actions
            if pol:
                pol += match(switch = s, dstip = dst_ip) >> fwd(link_port_map[s][next_hop])
            else:
                pol = match(switch = s, dstip = dst_ip) >> fwd(link_port_map[s][next_hop])

            #rules.append(Rule(m, act))
    return pol

    def to_rule_cpd(self):
        """
        Returns a RuleCPD object which represents the TreeCPD

        Examples
        --------
        >>> from pgmpy.factors import TreeCPD, Factor
        >>> tree = TreeCPD([('B', factors(['A'], [2], [0.8, 0.2]), '0'),
        ...                 ('B', 'C', '1'),
        ...                 ('C', factors(['A'], [2], [0.1, 0.9]), '0'),
        ...                 ('C', 'D', '1'),
        ...                 ('D', factors(['A'], [2], [0.9, 0.1]), '0'),
        ...                 ('D', factors(['A'], [2], [0.4, 0.6]), '1')])
        >>> tree.to_rule_cpd()

        """
        # TODO: This method assumes that factors class has a get_variable method. Check this after merging navin's PR.
        root = [node for node, in_degree in self.in_degree().items() if in_degree == 0][0]
        paths_root_to_factors = {target: path for target, path in nx.single_source_shortest_path(self, root).items() if
                                 isinstance(target, Factor)}
        for node in self.nodes_iter():
            if isinstance(node, Factor):
                rule_cpd = RuleCPD(node.scope()[0])

        for factor, path in paths_root_to_factors.items():
            rule_key = []
            for node_index in range(len(path) - 1):
                rule_key.append(path[node_index] + '_' + self.edge[path[node_index]][path[node_index + 1]]['label'])
            for value_index in range(len(factor.values)):
                rule_key.append(factor.get_variables()[0] + '_' + str(value_index))
                rule_cpd.add_rules({tuple(sorted(rule_key)): factor.values[value_index]})
        return rule_cpd

    def analyzeGraph(self, jsonFile, level=10):
        data = []
        nxg = json_graph.load(open(jsonFile))
        for n in nxg.nodes(data=True):
            if nxg.in_degree(n[0]) == 0:
                rootNode = n
                break 
        paths = nx.single_source_shortest_path(nxg,rootNode[0],level)
        nodes = {} # Dictionary to keep track of nodes at length x from root node
        for k,v in paths.items():
            if k == rootNode[0]: continue # exclude root node
            if not nodes.has_key(len(v) - 1):
                nodes[len(v) - 1] = []
            nodes[len(v) - 1].append(k)
                                     
#        cTotal = 0 # cumulative total

        for k in sorted(nodes.keys()):
            bunch = [rootNode[0]]
            for i in range(1,k + 1):
                bunch.extend(nodes[i])
            subgraph = nxg.subgraph(bunch)
            data.append({'name' : rootNode[1]['name'],
                         'level' : k,
                         'node_cnt' : subgraph.number_of_nodes(),
                         'edge_cnt' : subgraph.number_of_edges()})
        return data

    def get_permission_details(self, name):
        """ Get a permission and what groups it's assigned to. """

        with self.lock:
            data = {
                "groups": {},
            }

            # Get all mapped versions of the permission. This is only direct relationships.
            direct_groups = set()
            for groupname, permissions in self.permission_metadata.iteritems():
                for permission in permissions:
                    if permission.permission == name:
                        data["groups"][groupname] = self.get_group_details(
                            groupname, show_permission=name)
                        direct_groups.add(groupname)

            # Now find all members of these groups going down the tree.
            checked_groups = set()
            for groupname in direct_groups:
                group = ("Group", groupname)
                paths = single_source_shortest_path(self._graph, group, None)
                for member, path in paths.iteritems():
                    if member == group:
                        continue
                    member_type, member_name = member
                    if member_type != 'Group':
                        continue
                    if member_name in checked_groups:
                        continue
                    checked_groups.add(member_name)
                    data["groups"][member_name] = self.get_group_details(
                        member_name, show_permission=name)

            return data

def connect_shortest_v3(weigthed_graph,nodes,weighted=True,cutoff=None,verbose=False):
	STARTTIME=time.time()
	if verbose:
		print "Starting SHOV3 construction"
		sys.stdout.flush()

	STARTTIME=time.time()

	res=nx.Graph()
	for i in range(len(nodes)):
		src=nodes[i]
		if src not in weigthed_graph:
			continue
		if weighted:
			costs,spaths=nx.single_source_dijkstra(weigthed_graph, src, weight='weight',cutoff=cutoff)
		else:
			spaths=nx.single_source_shortest_path(weigthed_graph, src,cutoff=cutoff)
		for j in range(i+1, len(nodes)):
			t=nodes[j]
			if t not in spaths:
				continue
			if cutoff and (len(spaths[t])>cutoff):
				continue
			res.add_path(spaths[t])
		if verbose:
			print "Done",src,"to go:",len(nodes)-i
			sys.stdout.flush()			
	if verbose:
		print "Computed SHOV3,",time.time() - STARTTIME,"seconds"
		STARTTIME=time.time()
		sys.stdout.flush()	
	return res

def mst_of_g(g,terminals,verbose=False,weighted=True,cutoff=7,return_gL=False,bidir=False):
	STARTTIME=time.time()
	if verbose:
		logger.info("Starting MST construction")
		sys.stdout.flush()

	STARTTIME=time.time()
	gLedges=[]
	shortest_network=model.AnnotatedGraph()

	for i in range(len(terminals)):
		src=terminals[i]
		if src not in g:
			if verbose:
				logger.info("Node %s not in g"%(src))
			continue
		if weighted:
			costs,paths=nx.single_source_dijkstra(g, src, weight='weight',cutoff=cutoff)
		else:
			paths=nx.single_source_shortest_path(g,src,cutoff=cutoff)
			costs=dict([(k,len(v)) for k,v in paths.items()])

		if bidir:
			span=range(len(terminals))
		else:
			span=range(i+1,len(terminals))
		for j in span:
			if j==i:
				continue
			tgt=terminals[j]
			if tgt not in paths:
				if verbose:
					logger.info("no paths between %s and %s"%(src,tgt))
				continue
			shortest_network.add_path(paths[tgt])
			gLedges.append((src,tgt,{'weight':costs[tgt],'path':paths[tgt]}))
		if verbose:
			logger.info("Done %s. Still %d to go"%(src,len(terminals)-i))
			sys.stdout.flush()			
	if verbose:
		logger.info("Computed Metric closure in %f seconds"%(time.time() - STARTTIME))
		STARTTIME=time.time()
		sys.stdout.flush()			
	gL=nx.Graph()
	gL.add_edges_from(gLedges)
	# Min spanning Tree
	tL=nx.minimum_spanning_tree(gL)
	if verbose:
		logger.info("Computed Min spanning tree in %f seconds"%(time.time() - STARTTIME))
		STARTTIME=time.time()
		sys.stdout.flush()	

	mst=model.AnnotatedGraph()
	for e in tL.edges(data=True):
		mst.add_path(e[2]["path"])
	copy_attributes_from_g(mst,g)
	if return_gL:
		return mst,gL,shortest_network
	else:
		return mst

    def make_graph_from(self, minima, cutoff=1):
        """rebuild the graph using only the passed minima and those in self.from_minima"""
#        cutoff += 1
        self.from_minima.update(minima)
        minima = self.from_minima
        nodes = set()
        # make a graph from the minima in self.minima and nearest neighbors
        outer_layer = set()
        for m in minima:
            nodesdir = nx.single_source_shortest_path(self.full_graph, m, cutoff=cutoff)
            for n, path in nodesdir.iteritems():
                d = len(path) - 1
                if d < cutoff:
                    # n is close to m, remove it from outer layer
                    outer_layer.discard(n)
                elif d == cutoff:
                    if n not in nodes:
                        # n is in the outer layer of m and not near any other nodes.
                        outer_layer.add(n)
            nodes.update(nodesdir)

        self.boundary_nodes = outer_layer
        self.graph = self.full_graph.subgraph(nodes)

        # remove nodes not in the graph from the dictionary positions
        difference = set(self.positions.viewkeys())
        difference.difference_update(self.graph.nodes())
        for m in difference:
            self.positions.pop(m)

        print "boundary nodes", len(self.boundary_nodes), self.graph.number_of_nodes()

 def neighbors_genotyped_selective(self, node, depth=1):
     '''Return all neighbors of a node in the entire pedigree (if genotyped = False) or
     all genotyped neighbors (if genotyped = True) of depth <= depth. Selects only neighbors
     that have genotyped neighbors on the path between the neighbor and node.'''
     return list(reduce(set.union,
                        (v for (k, v) in 
                         nx.single_source_shortest_path(self._graph_undirected, node, cutoff=depth).iteritems() 
                         if self.is_genotyped(k)), set([])))

 def neighbors(self, node, depth=1, genotyped=False, add_parents=False):
     '''Return all neighbors of a node in the entire pedigree (if genotyped = False) or
     all genotyped neighbors (if genotyped = True) of depth <= depth.
     If add_parents=False, adds all parents of all neighbors to complete the pedigree.'''
     nbhrs = [x for x in nx.single_source_shortest_path(self._graph_undirected, node, cutoff=depth).iterkeys() 
              if (self.is_genotyped(x) if genotyped else True)]
     if add_parents: nbhrs = list(set(nbhrs + [parent for x in nbhrs for parent in self.parents(x).itervalues()])) 
     return nbhrs

def get_bw_cost(g, source, hops):
    counter = 0
    paths = nx.single_source_shortest_path(g, source, hops)
    no_friends = len(paths) - 1
    for k, v in paths.iteritems():
      if (len(v) <= hops):
          counter += g.degree(k)
    return no_friends, counter - no_friends

def edge_parent_finder(abstract, graph):
    '''
    moved this here since i think that it is forgi specific
    '''
    # find out to which abstract node the edges belong
    # finding out where the edge-nodes belong, because the contractor cant possibly do this
    #draw.graphlearn_draw([abstract,graph],size=10, contract=False,vertex_label='id')

    getabstr = {contra: node for node, d in abstract.nodes(data=True) for contra in d.get('contracted', [])}
    # print getabstr
    for n, d in graph.nodes(data=True):
        if 'edge' in d:
            # if we have found an edge node...

            # lets see whos left and right of it:
            # if len is 2 then we hit a basepair, in that case we already have both neighbors
            zomg = graph.neighbors(n)
            if len(zomg)==1:
                zomg+=graph.predecessors(n)

            n1, n2 = zomg


            # case1: ok those belong to the same gang so we most likely also belong there.
            if getabstr[n1] == getabstr[n2]:
                abstract.node[getabstr[n1]]['contracted'].add(n)

            # case2: neighbors belong to different gangs...
            else:
                abstract_intersect = set(abstract.neighbors(getabstr[n1])) & set(abstract.neighbors(getabstr[n2]))

                # case 3: abstract intersect in radius 1 failed, so lets try radius 2
                if not abstract_intersect:
                    abstract_intersect = set(nx.single_source_shortest_path(abstract, getabstr[n1], 2)) & set(
                        nx.single_source_shortest_path(abstract, getabstr[n2], 2))
                    if len(abstract_intersect) > 1:
                        print "weired abs intersect..."

                for ai_node in abstract_intersect:
                    if 'contracted' in abstract.node[ai_node]:
                        abstract.node[ai_node]['contracted'].add(n)
                    else:
                        abstract.node[ai_node]['contracted'] = set([n])

    return abstract

def get_shortest_paths(topo):
    edge_nodes = [n for n in topo.nodes() if topo.node[n]["isHost"]]
    shortest_paths = []
    for u in edge_nodes:
        paths = nx.single_source_shortest_path(topo, u)
        for v in edge_nodes:
            if u != v:
                shortest_paths.append(paths[v])
    return shortest_paths

 def _solve_graph(self):
     sols = []
     j = self.state.to_json()
     d = hashlib.md5(j).hexdigest()
     for a,p in nx.single_source_shortest_path(self.gr,d).items():
         if a in self.gr.graph['finals']:
             sols.append(p)
     sols = sorted(sols, key=lambda sol: len(sol))
     return sols