def verify(prog, src_name, dst_name):
    src = prog.subs.find(src_name)
    dst = prog.subs.find(dst_name)
    if src is None or dst is None:
        return None

    graphs = GraphsBuilder()
    graphs.run(prog)
    cg = graphs.callgraph

    if nx.has_path(cg, src.id.number, dst.id.number):
        return ('calls', nx.shortest_path(cg, src.id.number, dst.id.number))

    calls = CallsitesCollector(graphs.callgraph, src.id.number, dst.id.number)

    for sub in prog.subs:
        calls.run(sub)
        cfg = graphs.callgraph.nodes[sub.id.number]['cfg']
        for src in calls.srcs:
            for dst in calls.dsts:
                if src != dst and nx.has_path(cfg, src, dst):
                    return ('sites', nx.shortest_path(cfg, src, dst))
        calls.clear()

    return None

	def get_patterns_a(self):
		leaves = []
		root_name = "%s//%s" %(root, root.data)
		for n in G.nodes():
			if not nx.has_path(G, root_name, n):
				G.remove_node(n)
		# for n in nx.descendants(G, root_name):
			elif G.successors(n) == []:
				leaves.append(n)
		if leaves == []:
			print '\n******No Pattern******\n'
		else:
			print '\n******Patterns******\n'
			print '\nExtracted Pattern <%i>' %len(leaves)

		i = 0
		for n in leaves:
			pattern = []
			if nx.has_path(G, root_name, n):
				for p in nx.dijkstra_path(G, root_name, n):
					if G.node[p].has_key('fontcolor'):
						pattern.append(G.node[p]['label'].split(r'\n')[1])
					elif G.node[p] == {}:
						pass
					else:
						label = G.node[p]['label'].split(r'\n')[:-1]
						pattern.append('<%s>:{%s}' %(label[0].split('(')[0], ', '.join(label[1:])))
			print '%d:' %i, u'//'.join(pattern)
			i += 1

def check_road_path(road_graph, u, v):
    sp = nx.shortest_path(road_graph, u, v)
    if len(sp) >= 20:
        print "path too long"
        return None
    print "shortest path length", len(sp)
    print "shortest path", sp
    for i in xrange(1, len(sp) - 1):
        v1, v2 = sp[i], sp[i + 1]
        print v1, v2
        road_graph.remove_edge(v1, v2)
        if nx.has_path(road_graph, v1, v2):
            fp = nx.shortest_path(road_graph, v1, v2)
            if 3 < len(fp) < 8:
                print "fix path length", len(fp)
                print "fix path", fp
        else:
            pass
        if nx.has_path(road_graph, u, v):
            sp2 = nx.shortest_path(road_graph, u, v)
            if len(sp2) <= 20 and u in sp2 and v in sp2:
               print "new shortest path length", len(sp2)
               print "new shortest path", sp2
        else:
            pass
        road_graph.add_edge(v1, v2)

def _apply_is(is_formulas, core_formulas):
    """
    Given a list of formulas, resolve transitivity by Is relation

    :param formula_nodes:
    :return:
    """
    graph = nx.Graph()
    explicit_sigs = set()
    equal_formulas = []
    for formula_node in is_formulas:
        assert isinstance(formula_node, FormulaNode)
        a_node, b_node = formula_node.children
        a_sig, b_sig = a_node.signature, b_node.signature

        if a_sig.return_type == 'number' or b_sig.return_type == 'number':
            equal_formula = FormulaNode(signatures['Equals'], [a_node, b_node])
            equal_formulas.append(equal_formula)

        if not isinstance(a_sig, VariableSignature) or not isinstance(b_sig, VariableSignature):
            continue

        graph.add_edge(a_sig, b_sig)
        p = re.compile("^([A-Z]+|[a-z])$")
        if p.match(a_sig.name):
            explicit_sigs.add(a_sig)
        if p.match(b_sig.name):
            explicit_sigs.add(b_sig)

    tester = lambda sig: sig in graph and any(nx.has_path(graph, sig, explicit_sig) for explicit_sig in explicit_sigs)
    getter = lambda sig: [explicit_sig for explicit_sig in explicit_sigs if nx.has_path(graph, sig, explicit_sig)][0]
    new_formula_nodes = [formula_node.replace_signature(tester, getter) for formula_node in core_formulas]
    new_formula_nodes = new_formula_nodes + equal_formulas
    return new_formula_nodes

def betweenness(G):
  deltas = {}
  B = {}
  n = len(G.nodes())
  count = 1
  for s in G.nodes():
    print 'On node', count, 'of', n
    count += 1
    sigmas = {}
    delta_s = {}
    preds = {}
    #get sigmas of s for each v:
    for v in G.nodes():
      if nx.has_path(G, s, v):
        pred_set = Set()
        sigmas[v] = get_sigma(G, s, v, pred_set)
        preds[v] = pred_set
      else:
        sigmas[v] = 0
    #get successors for use in finding delta:
    successors = get_successors(preds)

    #get deltas of s for each edge in E:
    for e in G.edges():
      if e not in B:
        B[e] = 0
      if nx.has_path(G, s, e[0]):
        B[e] += get_delta(G, s, e, sigmas, successors)

  return B

def get_contigs_of_mates(node, bamfile, G):
    """ retrieves set of nodes mapped to by read pairs
        having one mate on node; discards isolated nodes
        because they tend to reflect irrelevant alignments
    """
    mate_tigs = set([])
    if node[-1] == "'": node=node[:-1]
    try:    
        for hit in bamfile.fetch(node):
            nref = bamfile.getrname(hit.next_reference_id)
            if nref != node:
                mate_tigs.add(nref)

    except ValueError:
        pass
    source_name = node #re.sub('NODE_','EDGE_', node)

    # print "before removal", mate_tigs
    to_remove = set([])
    for nd in mate_tigs:
        # flip name from "NODE_" prefix back to "EDGE_"
        # differs between contigs set and graph node names
        nd_name = nd #re.sub('NODE_','EDGE_', nd)
        if (G.in_degree(nd_name)==0 and G.out_degree(nd_name)==0) or \
        (not G.has_node(nd_name)):
            to_remove.add(nd)
        # see if nd reachable by node or vice-versa
        # try both flipping to rc and switching source and target    
        elif not any([nx.has_path(G, source_name, nd_name), nx.has_path(G, rc_node(source_name),nd_name), 
          nx.has_path(G, nd_name, source_name), nx.has_path(G, nd_name, rc_node(source_name))]):
            to_remove.add(nd)
    mate_tigs -= to_remove
    # print "after removal", mate_tigs

    return mate_tigs

 def enter_Call(self,jmp):
     callee = direct(jmp.target[0])
     if callee:
         if nx.has_path(self.callgraph, callee.number, self.src):
             self.srcs.append(self.caller)
         if nx.has_path(self.callgraph, callee.number, self.dst):
             self.dsts.append(self.caller)

	def get_patterns_b(self):
		roots = []
		for n in G.nodes():
			if not nx.has_path(G, n, '1'):
				G.remove_node(n)
		# for n in nx.ancestors(G, '1'):
			elif G.predecessors(n) == []:
				roots.append(n)
		if roots == []:
			print '\n******No Pattern******\n'
		else:
			print '\n******Patterns******\n'
			print '\nExtracted Pattern <%i>' %len(roots)
		i = 0
		for n in roots:
			pattern = []
			if nx.has_path(G, n, '1'):
				for p in nx.dijkstra_path(G, n, '1')[:-1]:
					if G.node[p].has_key('fontcolor'):
						pattern.append(G.node[p]['label'].split(r'\n')[1])
					else:
						label = G.node[p]['label'].split(r'\n')[:-1]
						pattern.append('%s:{%s}' %(label[0].split('(')[0], ', '.join(label[1:])))
			print '%d:' %i, u' '.join(pattern)
			i += 1

def er_network(p=0.5):
    G = nx.grid_2d_graph(11, 11)
    for u in G.nodes():
        for v in G.nodes():
            if u == nest and v == target:
                continue
            if v == nest and u == target:
                continue
            if u != v:
                if random() <= p:
                    G.add_edge(u, v)
                else:
                    if G.has_edge(u, v):
                        G.remove_edge(u, v)
    if not nx.has_path(G, nest, target):
        return None
    short_path = nx.shortest_path(G, nest, target)
    if len(short_path) <= 3:
        return None
    #print short_path
    idx = choice(range(1, len(short_path) - 1))
    #print idx
    G.remove_edge(short_path[idx], short_path[idx + 1])
    for i in xrange(idx):
        P.append((short_path[i], short_path[i + 1]))
    for i in xrange(idx + 1, len(short_path) - 1):
        P.append((short_path[i], short_path[i + 1]))
    #print P
        
    if not nx.has_path(G, nest, target):
        return None
    
    for i,u in enumerate(G.nodes_iter()):
        M[i] = u
        Minv[u] = i
        pos[u] = [u[0],u[1]] # position is the same as the label.

        if (u[0] == nest) or (u == target):
            node_size.append(100)
            node_color.append('r')
        else:
            node_size.append(10)
            node_color.append('k') 
        
    for u,v in G.edges_iter():
        G[u][v]['weight'] = MIN_PHEROMONE
        if (u, v) in P or (v, u) in P:
            edge_color.append('g')
            edge_width.append(10)
        else:
            edge_color.append('k')
            edge_width.append(1)
    
    for i, (u,v) in enumerate(G.edges()):
        Ninv[(u, v)] = i
        N[i] = (u, v)        
        Ninv[(v, u)] = i
            
    return G

def road(road_file_path, comments='#'):
    G = nx.read_edgelist(road_file_path, comments=comments, nodetype=int)
    nodes = []
    start_node = random.choice(G.nodes())
    queue = [start_node]
    added_nodes = 1
    seen = set()
    while added_nodes < MAX_ROAD_NODES and len(queue) > 0:
        curr = queue.pop()
        if curr in seen:
            continue
        else:
            nodes.append(curr)
            queue += G.neighbors(curr)
            seen.add(curr)
            added_nodes += 1
    
    G = G.subgraph(nodes)
 
    mapping = {}
    for i, node in enumerate(G.nodes()):
        x = i / 12
        y = i % 12
        mapping[node] = (x, y)
    #nx.relabel_nodes(G, mapping, copy=False)
    
    mapping2 = {}
    for i, node in enumerate(sorted(G.nodes())):
        mapping2[node] = i
    #nx.relabel_nodes(G, mapping2, copy=False)
    
    G.graph['name'] = 'road'
    
    pos = nx.kamada_kawai_layout(G, scale = graphscale)
    for u in G.nodes():
        G.node[u]['pos'] = pos[u]
    
    done = False
    for i in xrange(MAX_ROAD_ATTEMPTS):
        n1, n2 = sample(G.nodes(), 2)
        if not nx.has_path(G, n1, n2):
            continue
        sp = nx.shortest_path(G, n1, n2)
        if len(sp) < 8 or len(sp) > 30:
            continue
        index = random.choice(range(len(sp) / 4, 3 * len(sp) / 4))
        u, v = sp[index], sp[index + 1]
        G.remove_edge(u, v)
        if not nx.has_path(G, u, v):
            G.add_edge(u, v)
            continue
        fp = nx.shortest_path(G, u, v)
        if len(fp) > 8:
            G.add_edge(u, v)
            continue
        #print n1, n2, u, v, sp, fp
        G.add_edge(u, v)
        set_init_road_path(G, n1, n2, u, v)
        return G

def test_TR(DAG, TR):
    missing_edges = []
    for node1 in DAG.nodes():
        for node2 in DAG.nodes(): #iterates over all pairs of nodes in the DAG
            if dl.age_check(DAG, node1, node2): #ensure that there could possibly be a path from node1 to node2
                if nx.has_path(DAG, node1, node2): #tests whether there is a path between these two nodes in the original DAG
                    if not nx.has_path(TR, node1, node2): 
                        missing_edges.append([node1, node2]) #if there is no longer a path between these two pairs of nodes in the transitive reduction...
    return missing_edges #...then these two edges are stored and printed

def four_chain(three_chain_list, DAG_TC): #Uses the transitive completion of the DAG to find all of the three chains in the DAG
    four_chain_list = []
    for three_chain in three_chain_list: #Iterates over every 3 chain
        [node1, node2, node3] = three_chain
        for node in DAG_TC.nodes(): #Iterates over every node in the DAG
            if dl.age_check(DAG_TC, node1, node): #If a node has birthdays between two of the nodes in the 3 chain, it could be possible to find a 4 chain that has this node added in to the 3 chain
                if dl.age_check(DAG_TC, node, node2): 
                    if nx.has_path(DAG_TC, node1, node):
                        if nx.has_path(DAG_TC, node, node2): 
                            four_chain_list.append([node1, node, node2, node3]) #If a three chain can be formed, add it to the list
    return four_chain_list

def three_chain(DAG_TC): #Uses the transitive completion of the DAG to find all of the three chains in the DAG
    three_chain_list = []
    for edge in DAG_TC.edges(): #Iterates over every edge in the TC, which is also every 2 chain
        [node1, node2] = edge
        for node in DAG_TC.nodes():
            if dl.age_check(DAG_TC, node1, node): #If a node has birthdays between each end of the 2 chain, it could be possible to find a 3 chain that has this node inbetween the the ends of the 2 chain
                if dl.age_check(DAG_TC, node, node2):
                    if nx.has_path(DAG_TC, node1, node): #check if there is a path to the middle node from the 1st
                        if nx.has_path(DAG_TC, node, node2): #check if there is a path from the middle node to the 2nd
                            three_chain_list.append([node1, node, node2]) #If a three chain can be formed, add it to the list
    return three_chain_list

    def get_parameterized_intercitation_dag(self,old_node,new_node,dag):
        desc = nx.descendants(dag,old_node)
        desc.add(old_node)
        anc = nx.ancestors(dag,new_node)
        anc.add(new_node)

        # Intersect lineages to get ad tree
        intersect = desc.intersection(anc)

        if (len(intersect) == 0):
            print "No common intercitations between ",old_node," and ",new_node
        else:
          rev_dag = nx.reverse(dag,copy=True)
          # Strength of weighting due to impact (# citations)
          impact_param = 1.0

          #Strength of weighting due to network relevance of paper's citations
          network_relevance_param = 1.0

          #Strength of weighting due to redundancy in citation network
          network_robustness_param = 1.0

          sum_citations = sum([pow(dag.in_degree(w),impact_param) for w in intersect])

          #Store importance score
          importance_dict = {}
          for w in intersect:
            importance_dict[w] = pow(dag.in_degree(w),impact_param)

          #Calculate network relevance
          net_relevance = {}
          for w in intersect:
            cited_reach_cnt = 0
            for cited in dag.neighbors(w):
              #If we can reach old node through cited node add to count
              if (nx.has_path(dag,cited,old_node)):
                cited_reach_cnt += 1
            net_relevance[w] = pow(float(cited_reach_cnt)/dag.out_degree(w),network_relevance_param)


          #Calculate network robustness
          net_robustness = {}
          for w in intersect:
            citer_alt_path = 0
            cited_alt_path = 0
            for citer in rev_dag.neighbors(w):
              #If we can reach old node through citer node (without using that citation as a link)
              if (nx.has_path(dag,citer,old_node)):
                citer_alt_path += 1
            for cited in dag.neighbors(w):
              if (nx.has_path(rev_dag,cited,new_node)):
                cited_alt_path += 1
            net_robustness[w] = pow(float(cited_alt_path + citer_alt_path)/(dag.out_degree(w) + dag.in_degree(w)),network_robustness_param)

def createMinMaxGraphByWeight( **kwargs):
    ## first need to find the pairs with the maximum occurrence, then we work down from there until all of the
    ## nodes are included
    ## the weight

    weight = kwargs.get('weight', "weight")
    input_graph = kwargs.get('input_graph')
    sumDistance = calc_sum_distance(input_graph)

    #first create a graph that is complete
    new_graph = createCompleteGraphByDistance(input_graph=input_graph.copy(), weight='weight')

    output_graph = nx.Graph(is_directed=False)
    output_graph.add_nodes_from(input_graph.nodes(data=True)) ## copy just the nodes

    pairsHash={}

    for e in new_graph.edges_iter():
        d = new_graph.get_edge_data(*e)
        fromAssemblage = e[0]
        toAssemblage = e[1]
        key = fromAssemblage+"*"+toAssemblage
        value = new_graph[fromAssemblage][toAssemblage]['weight']
        pairsHash[key]=value

    for key, value in sorted(pairsHash.iteritems(), key=operator.itemgetter(1), reverse=True ):
        ass1, ass2 = key.split("*")
        edgesToAdd={}
        if nx.has_path(output_graph, ass1, ass2) == False:
            edgesToAdd[key]=value
             ## check to see if any other pairs NOT already represented that have the same value
            for p in pairsHash:
                if pairsHash[p] == value:
                    k1,k2 = p.split("*")
                    if nx.has_path(output_graph, k1,k2) == False:
                        edgesToAdd[p]=pairsHash[p]
            ## now add all of the edges that are the same value if they dont already exist as paths
            for newEdge in edgesToAdd:
                a1,a2 = newEdge.split("*")
                key=a1+"*"+a2
                distance=edgeDistance[key]
                weight=1/distance
                normalized_weight=distance/sumDistance
                if weight in [0,None,False]:
                    weight=0.000000000001 ## use this value so that we never get a 1/0
                output_graph.add_path([a1, a2], normalized_weight=normalized_weight,unnormalized_weight=weight,
                                      distance=distance, weight=weight)
    ## now remove all of the non linked nodes.
    outdeg = output_graph.degree()
    to_remove = [n for n in outdeg if outdeg[n] < 1]
    input_graph.remove_nodes_from(to_remove)

    return output_graph.copy()

 def _path(self, start_obj, end_obj):
     graph = self._graph
     di_graph = self._di_graph
     if( start_obj.fqtn == end_obj.fqtn and
         nx.has_path( di_graph, start_obj.fqtn, end_obj.fqtn ) ):
             path = [start_obj.fqtn]
     elif nx.has_path( di_graph, start_obj.fqtn, end_obj.fqtn ):
         path = nx.shortest_path(
             di_graph, start_obj.fqtn, end_obj.fqtn, 'weight' )
     else:
         path = nx.shortest_path(
             graph, start_obj.fqtn, end_obj.fqtn, 'weight' )
     return path

def interval_size(DAG, start, end):
    
    i = 0
    #print 'checking interval from %s to %s' % (start, end)
    for node in DAG.nodes():        
        if nx.has_path(DAG, start, node):
            if nx.has_path(DAG, node, end):
                i += 1
                #print 'found node %s in interval %s to %s' % (node, start, end)
       
                 
            pass
    return i

def transitive_reduction(G):
    """
    Returns a transitive reduction of a graph.  The original graph
    is not modified.

    A transitive reduction H of G has a path from x to y if and
    only if there was a path from x to y in G.  Deleting any edge
    of H destroys this property.  A transitive reduction is not
    unique in general.  A transitive reduction has the same
    transitive closure as the original graph.

    A transitive reduction of a complete graph is a tree.  A
    transitive reduction of a tree is itself.

    >>> G = nx.DiGraph([(1, 2), (1, 3), (2, 3), (2, 4), (3, 4)])
    >>> H = transitive_reduction(G)
    >>> H.edges()
    [(1, 2), (2, 3), (3, 4)]
    """
    H = G.copy()
    for a, b, w in G.edges_iter(data=True):
        # Try deleting the edge, see if we still have a path
        # between the vertices
        H.remove_edge(a, b)
        if not nx.has_path(H, a, b):  # we shouldn't have deleted it
            H.add_edge(a, b, w)
    return H

 def currentLeader (self, switch):
     for c in sorted(list(self.controllers)):
         if c not in self.graph:
             self.graph.add_node(c)
     for c in sorted(list(self.controllers)):
         if nx.has_path(self.graph, c, switch):
             return c #Find the first connected controller

def find_disconnected_groups(graph):
	
	# create a dictionary of the nodes of the graph with their colour
	node_colours = {}
	for i in graph.nodes():
		node_colours[i] = None

	colour_counter = 0
	groups = {}

	# while all the nodes are uncoloured
	while (None in node_colours.values()):
		for i in graph.nodes():
			# if it is uncoloured, colour it and find
			# all of the nodes connected to it and colour them
			if node_colours[i] == None:
				node_colours[i] = colour_counter
				groups[colour_counter] = [i]
				for j in graph.nodes():
					if nx.has_path(graph, i, j) == True:
						node_colours[j] = node_colours[i]
						if j not in groups[colour_counter]:
							groups[colour_counter].append(j)
				colour_counter += 1
				# print node_colours

	# the number of groups
	n_groups = max(groups.keys()) + 1

	return groups