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 test_multi_allocate_and_free(self):
        """Assert that resources allocated by flows are freed"""
        SWITCHES = ['sw1', 'sw2']
        SERVERS = ['s1', 's2']
        graph = self.graph
        max_duration = 10
        durations = range(1, max_duration)
        steps = 100
        a = nx.shortest_path(graph, choice(SERVERS), choice(SWITCHES))
        b = nx.shortest_path(graph, choice(SERVERS), choice(SWITCHES))
        paths = [a, b]
        workload = [(choice(paths), choice(durations)) for t in range(steps)]

        ctrls = [LinkBalancerCtrl(['sw1', 'sw2'])]
        sim = LinkBalancerSim(graph, ctrls)

        metric_before_alloc = sim.rmse_links(graph)

        for now, item in enumerate(workload):
            path, dur = item
            sim.free_resources(now)
            sim.allocate_resources(path, 1, now, dur)

        # Free the (up to max_duration) possibly remaining live flows
        for i in range(len(workload), steps + max_duration):
            sim.free_resources(i)

        metric_after_free = sim.rmse_links(graph)

        self.assertEqual(metric_before_alloc, metric_after_free)
        self.assertEqual(len(sim.active_flows), 0)

def switches_to_remove(version, graph):
    if version == 0:
        return []
    elif len(graph.switches()) < 2:
        return []
    else:
        scratch_graph = graph.copy()
        nodes = []
        hosts = scratch_graph.hosts()[::version * 2]
        for host1 in hosts:
            for host2 in hosts:
                if host1 == host2:
                    continue
                try:
                    path = nx.shortest_path(scratch_graph, host1, host2)
                except nx.exception.NetworkXNoPath:
                    continue
                # Pick a "middle" node
                node = path[len(path)/2]
                tmp_graph = scratch_graph.copy()
                tmp_graph.remove_node(node)
                try:
                    nx.shortest_path(tmp_graph, host1, host2)
                except nx.exception.NetworkXNoPath:
                    continue
                # If path still exists, toss node onto list
                scratch_graph.remove_node(node)
                nodes.append(node)
                
        return nodes

def randomCommodities(random_graph, numCommodities, commodityDistribution = None):
    '''Generates a list of commodities with reachable source and sink
       and numCommodity groups numbers of commodities with the same starting source
    '''

    edgeDict = random_graph.edge
    nodes = set([key for key in edgeDict.iterkeys()])
    commodities = []
    commodityDistribution = commodityDistribution or [1] * numCommodities
    assert len(commodityDistribution) <= len(nodes)
    for xCommodities in commodityDistribution:
        done = False
        while not done:
            randomChoice = random.sample(nodes, 1)[0]
            possSinks = [k for k in nx.shortest_path(random_graph,randomChoice).iterkeys()]
            possSinks.remove(randomChoice)
            if len(possSinks) < xCommodities:
                pass
            else:
                nodes.remove(randomChoice)
                sinks = random.sample(possSinks, xCommodities)
                
                for sink in sinks:
                    commodities.append(Commodity(randomChoice, sink, random.randint(1,50)))
                done = True
    assert len(commodities) == numCommodities
    for commodity in commodities:
        assert(commodity.sink in nx.shortest_path(random_graph, commodity.source))
    return commodities

def main(fName="cppzk.txt"):
    g = nx.Graph()
    for eachLine in open(fName):
        fields = eachLine.split()
        g.add_edge(fields[0], fields[1])
         
#     keyConns = [["ASPA0085", "ARGA0082"], ["ARGA0082", "GLUA0194"]]
    keyConns = [["ASPA0085", "GLUA0194"]]
#     keyConns = [["ASPA0085", "ARGA0082"], ["ARGA0082", "GLUA0194"], ["ASPA0085", "GLUA0194"]]

    keyAtoms = {"ASPA0085":["OD1", "OD2"], "ARGA0082":["NE", "NH1", "NH2"], "GLUA0194":["OE1", "OE2"]}
    
    for eachConn in keyConns:
        sourceRes = eachConn[0]
        targetRes = eachConn[1]
        
        for eachSourceAtom in keyAtoms[sourceRes]:
            sourceAtom = sourceRes + eachSourceAtom
            if sourceAtom not in g.nodes(): continue
            for eachTargetAtom in keyAtoms[targetRes]:
                targetAtom = targetRes + eachTargetAtom
                if targetAtom not in g.nodes(): continue
                
                if nx.has_path(g, sourceAtom, targetAtom):
                    print "Path between %13s%13s" % (sourceAtom, targetAtom),
                    print nx.shortest_path(g, sourceAtom, targetAtom)

    def _generate_path(self, topo, src_mac, dst_mac, src_port,
                       dst_port, src_dpid, dst_dpid):
        """Generate path method."""
        net = nx.DiGraph(data=topo)
        net.add_node(src_mac)
        net.add_node(dst_mac)
        net.add_edge(int(src_dpid), src_mac, {'port': int(src_port)})
        net.add_edge(src_mac, int(src_dpid))
        net.add_edge(int(dst_dpid), dst_mac, {'port': int(dst_port)})
        net.add_edge(dst_mac, int(dst_dpid))

        target_path = None
        try:
            path = nx.shortest_path(net, src_mac, dst_mac)
            path2 = nx.shortest_path(net, src_mac, dst_mac)
            path2.pop()
            path2.pop(0)
            list_load = check_switch_load(path2, data_collection.switch_stat, constant.load_limitation)
            if len(list_load) > 0:
                # print 'lui', list_load
                all_paths = nx.all_simple_paths(net, src_mac, dst_mac)
                path_list = list(all_paths)
                target_path_index, target_path_cost = calculate_least_cost_path(path_list, data_collection.switch_stat, net)
                target_path = path_list[target_path_index]
            else:
                target_path = path
            print 'tarrr', target_path
        except Exception:
            target_path = None
        return target_path

    def getFreePathToTarget(self, bot, current, target):
        ## tmp: get one of the current active paths
        if len(self.botWaypoints) == 0 or (len(self.botWaypoints) == 1 and bot in self.botWaypoints):
            return nx.shortest_path(self.graph, current, target, weight="weight")
        rndKey = random.choice([key for key in self.botWaypoints.keys() if key != bot])
        otherPath = self.botWaypoints[rndKey][0]

        ## Create a dummy graph node and connect it to each nodes of the shortest path.
        u = "startNode"
        self.graph.add_node(u)
        for v in otherPath:
            self.graph.add_edge(u, v, weight=1)

        ## Now calculate the path lengths of all graph nodes to the shortest path nodes.
        distances = nx.single_source_dijkstra_path_length(self.graph, u, weight="weight")
        self.graph.remove_node(u)  # we don't need the dummy graph node any more
        del distances[u]

        ## Create weight heuristics based on path lengths.
        for node_index, length in distances.iteritems():
            self.graph.node[node_index]["weight"] = length
        for u, v in self.graph.edges():
            w = (self.graph.node[u]["weight"] + self.graph.node[v]["weight"]) * 0.5
            self.graph[u][v]["weight"] = 1 / w ** 2

        ## And finally calculate the path to the flanking position.
        return nx.shortest_path(self.graph, current, target, weight="weight")

    def display_path_to(self, node_id):
        if node_id != self.identity.pubkey:
            for edge in self.edges.values():
                edge.neutralize()

            for node in self.nodes.values():
                node.neutralize()

            path = []
            try:
                path = networkx.shortest_path(self.nx_graph, node_id, self.identity.pubkey)
            except (networkx.exception.NetworkXError, networkx.exception.NetworkXNoPath) as e:
                logging.debug(str(e))
                try:
                    path = networkx.shortest_path(self.nx_graph, self.identity.pubkey, node_id)
                except (networkx.exception.NetworkXError, networkx.exception.NetworkXNoPath) as e:
                    logging.debug(str(e))

            for node, next_node in zip(path[:-1], path[1:]):
                if (node, next_node) in self.edges:
                    edge = self.edges[(node, next_node)]
                elif (next_node, node) in self.edges:
                    edge = self.edges[(next_node, node)]
                if edge:
                    edge.highlight()
                    self.nodes[node].highlight()
                    self.nodes[next_node].highlight()
                    logging.debug("Update edge between {0} and {1}".format(node, next_node))

def testSerialRandom():
    """ 50 Random serial test cases
    """

    N = 10
    p = .7
    runs = 0
    while runs < 50:

        # a random graph
        G = nx.fast_gnp_random_graph(N, p)
        try:
            nx.shortest_path(G, source=0, target=N-1)
        except:
            continue
        # convert to plain ndarray
        nw1 = nx2nw(G)

        # copy and join network
        nw2 = serialCopy(nw1)

        # compute effective resistance
        ER1 = ResNetwork(
            nw1, silence_level=3).effective_resistance(0, len(nw1)-1)
        ER2 = ResNetwork(
            nw2, silence_level=3).effective_resistance(0, len(nw2)-1)

        # increment runs
        runs += 1
        # assertion
        print (ER1*2-ER2)
        assert (ER1*2-ER2) < 1E-6

    def _generate_path(self, 
                       frame_from, 
                       frame_to):
        '''
        Generate a path between two frames.
        
        Arguments
        ---------
        frame_from: a frame key, usually a string 
                    example: 'world'
        frame_to:   a frame key, usually a string 
                    example: 'mesh_0'

        Returns
        ----------
        path: (n) list of frame keys
              example: ['mesh_finger', 'mesh_hand', 'world']
        inverted: boolean flag, whether the path is traversing stored
                  matrices forwards or backwards. 
        '''
        try: 
            path = shortest_path(self._transforms, frame_from, frame_to)
            inverted = False
        except NetworkXNoPath:
            path = shortest_path(self._transforms, frame_to, frame_from)
            inverted = True
        self._paths[(frame_from, frame_to)] = (path, inverted)
        return path, inverted

    def __send_to_who(self, sender, deploy_network, civ_information, cap):
        """
        Function to populate list to whom information should be sent

        """
        send_to = []

        if cap == "shelter":
            for i in range(len(deploy_network)):
                if self.rs[deploy_network[i].id].c_shelter is True and self.__check_in_circle(self.rs[deploy_network[i].id].deploy_range, civ_information.position):
                    path = nx.shortest_path(self.G, sender, deploy_network[i].id)
                    send_to.append(path[1])
        elif cap == "medical":
            for i in range(len(deploy_network)):
                if self.rs[deploy_network[i].id].c_medical is True and self.__check_in_circle(self.rs[deploy_network[i].id].deploy_range, civ_information.position):
                    path = nx.shortest_path(self.G, sender, deploy_network[i].id)
                    send_to.append(path[1])
        elif cap == "food":
            for i in range(len(deploy_network)):
                if self.rs[deploy_network[i].id].c_food is True and self.__check_in_circle(self.rs[deploy_network[i].id].deploy_range, civ_information.position):
                    path = nx.shortest_path(self.G, sender, deploy_network[i].id)
                    send_to.append(path[1])
        elif cap == "logistic":
            for i in range(len(deploy_network)):
                if self.rs[deploy_network[i].id].c_logistic is True and self.__check_in_circle(self.rs[deploy_network[i].id].deploy_range, civ_information.position):
                    path = nx.shortest_path(self.G, sender, deploy_network[i].id)
                    send_to.append(path[1])

        return send_to

def calculate_network_measures(net, analyser):
    deg=nx.degree_centrality(net)
    clust=[]

    if(net.is_multigraph()):
        net = analyser.flatGraph(net)

    if(nx.is_directed(net)):
        tmp_net=net.to_undirected()
        clust=nx.clustering(tmp_net)
    else:
        clust=nx.clustering(net)



    if(nx.is_directed(net)):
        tmp_net=net.to_undirected()
        paths=nx.shortest_path(tmp_net, source=None, target=None, weight=None)
    else:
        paths=nx.shortest_path(net, source=None, target=None, weight=None)

    lengths = [map(lambda a: len(a[1]), x[1].items()[1:]) for x in paths.items()]
    all_lengths=[]
    for a in lengths:
        all_lengths.extend(a)
    max_value=max(all_lengths)
    #all_lengths = [x / float(max_value) for x in all_lengths]

    return deg.values(),clust.values(),all_lengths

    def get_influence(self, nodea, nodeb):
        ''' Returns a positive number if "nodea is more dominant than nodeb"; 
            Returns a negative number if "nodeb is more dominant than nodea";
            Returns None if no influence comparison could be performed '''

        try:
            ab = nx.shortest_path(self.G, nodea, nodeb)
        except nx.NetworkXError:
            print "Could not find one of the nodes in the graph"
            return 0.0
        except nx.NetworkXNoPath:
            ab = None 

        try:
            ba = nx.shortest_path(self.G, nodeb, nodea)
        except nx.NetworkXError:
            print "Could not find one of the nodes in the graph"
            return 0.0
        except nx.NetworkXNoPath:
            ba = None 

        if ab != None and ba != None: 
            if len(ab) > len(ba):
                ab = None
            else:
                ba = None

        if ab != None: 
            return 1./(len(ab))
        elif ba != None: 
            return -1./len(ba)
        else:
            return 0.0

def nca(name1, name2):
	G=json_graph.load(open("static/local_instance.json"))	

	frontier1=[get_id(name1)]
	frontier2=[get_id(name2)]
	
	done=False
	while not done:
		#retrieve nodes in next BFS shell
		shell1=list(chain.from_iterable(G.predecessors(each) for each in frontier1))
		shell2=list(chain.from_iterable(G.predecessors(each) for each in frontier2))

		#no new nodes. End of the line
		if not shell1 and not shell2:
			return []
		
		frontier1+=shell1
		frontier2+=shell2
		intersect=set(frontier1)&set(frontier2)
	
		if intersect:
			done=True
			#print intersect

	return [(nx.shortest_path(G,ancestor,get_id(name1)),nx.shortest_path(G,ancestor,get_id(name2))) for ancestor in list(intersect)]

	def get_score(self, player_goal, opponent_goal):
		if not self.is_terminal(player_goal, opponent_goal):
			player_path = nx.shortest_path(self.G, self.player_location, player_goal, weight="weight")
			self.player_score -= self.score_for_path(player_path, self.G) + len(player_path)
			opponent_path = nx.shortest_path(self.G, self.opponent_location, opponent_goal, weight="weight")
			self.opponent_score -= self.score_for_path(opponent_path, self.G) + len(opponent_path)
		return self.player_score+self.opponent_score+1000

def helper(T, U, e1, e2):
	path1 = nx.shortest_path(T, e1[0], e1[1])

	for f1 in zip(path1[0:],path1[1:]):

		U.add_edge(e1[0],e1[1])
		U.remove_edge(f1[0],f1[1])

		path2 = nx.shortest_path(T, e2[0], e2[1])

		for f2 in zip(path2[0:],path2[1:]):

			U.add_edge(e2[0],e2[1])

			if (tuple([f2[0],f2[1]]) in U.edges()):
				U.remove_edge(f2[0],f2[1])

			newDegrees = list(U.degree(U.nodes()).values())

			if newDegrees.count(1) > Degrees.count(1):
				print newDegrees.count(1)
				print i
				T = U.copy()
				Degrees = list(T.degree(T.nodes()).values())

			U.add_edge(f2[0],f2[1]);

		U.add_edge(f1[0],f1[1]);

 def get_shortest_path(self, source, destination):
   G = nx.DiGraph()
   self.update()
   G.add_weighted_edges_from([(link.lastHopIP, link.destinationIP, link.tcEdgeCost) for link in self.linklist])
   if self.is_in_topology(source) and self.is_in_topology(destination):
     return nx.shortest_path(G, source, destination)
   elif self.is_in_topology(source):
     # find the closest gateway
     closestgw = None
     cost = 0
     for gw in self.gatewaylist:
       try:
         splen = nx.shortest_path_length(G, source, gw)
       except nx.NetworkXNoPath:
         return None
       if splen > cost:
         cost = splen
         closestgw = gw
     if closestgw:
       return nx.shortest_path(G, source, closestgw)
     else:
       return None
   elif self.is_in_topology(destination):
     # should this happen?
     res = self.get_shortest_path(destination, source)
     res.reverse()
     return res

 def pre_process(self, source_id, sink_id):
     #create grade values for each node
     try:
         nx.shortest_path(self.graph, source=source_id, target = sink_id)
     except Exception, e:
         #no path in between source and destination, so return false o
         return False

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 path(self, src_ip, dst_ip):
        src_mac = self.get_by_attr('ip', src_ip)
        dst_mac = self.get_by_attr('ip', dst_ip)
        #print "src_mac = %s dst_mac = %s" % (src_mac, dst_mac)
        ofctl_ip = self.get_ip_ofctl()
        if src_mac is None:
            if ofctl_ip == src_ip:
                src_mac = self.get_hw_ofctl()
            else:
                return []
        if dst_mac is None:
            if ofctl_ip == dst_ip:
                dst_mac = self.get_hw_ofctl()
            else:
                dst_mac = self.get_my_crossdomain_sw(dst_ip)
                if dst_mac is not None:
                    try:
                        domain_path = shortest_path(self, src_mac, dst_mac, 'weight')
                    except Exception as e:
                        #log.debug("ERRO ENCONTRAR O PATH - %s", e)
                        return []

                    if len(domain_path) != 0:
                        dst_sw = self.get_dst_crossdomain_sw(dst_ip)
                        domain_path.append(dst_sw)
                    return domain_path
                else:
                    return []
        try:
            domain_path = shortest_path(self, src_mac, dst_mac, 'weight')
        except Exception as e:
            #log.debug("ERRO SYNC ADD EDGE - %s", e)
            return []
        return domain_path