def next_move(self, who):
     all_paths = nx.all_pairs_shortest_path(who.graph.clear_networkx_graph(self.cannottouch))
     all_paths2 = nx.all_pairs_shortest_path(who.graph.networkx_graph())
     temp = []
     for i in self.graph.graph[who.position]:
         if i in all_paths:
             temp.append(i)
     if not temp == []:
         return random.choice(temp)

def shortest_path_policy(graph1, graph2):
    # Take two graphs as arguments, one with all the switches and one
    # with some removed. For each host, flip a coin to decide if it
    # will be routed using the full or partial graph.
    # Because hosts are single-homed, we can save a lot of computation
    # by computing shortest paths on the subgraph of switches instead
    # the full graph of switches and hosts
    raw = defaultdict(lambda:[])
    sub_graph1 = graph1.copy()
    sub_graph1.remove_nodes_from(sub_graph1.hosts())
    sub_graph2 = graph2.copy()
    sub_graph2.remove_nodes_from(sub_graph2.hosts())
    paths1 = nx.all_pairs_shortest_path(sub_graph1)
    paths2 = nx.all_pairs_shortest_path(sub_graph2)
    hosts = graph1.hosts()
    for src in hosts:
        for dst in hosts:
            if src != dst:
                if hash(src + dst) % 5:
                    paths = paths1
                    graph = graph1
                else:
                    paths = paths2
                    graph = graph2
                # Grab hosts' switches
                try:
                    if len(graph1.neighbors(src)) > 1:
                        log.debug(str(src) + " nbrs: " + str(graph1.neighbors(src)))
                    src_sw = graph1.neighbors(src)[0]
                except IndexError:
                    # log.debug("Index error! src host " + str(src))
                    break
                try:                    
                    dst_sw = graph1.neighbors(dst)[0]
                except IndexError:
                    # log.debug("Index error! dst host " + str(dst))
                    continue
                try:
                    path = [src] + paths[src_sw][dst_sw] + [dst]
                except KeyError:
                    # log.debug("Key error! switches " + str(src_sw) + " and " + str(dst_sw))
                    continue
                last = path.pop(0)
                curr = path.pop(0)
                for next in path:
                    inport = graph1.node[curr]['ports'][last]
                    outport = graph1.node[curr]['ports'][next]
                    pat = { IN_PORT:inport, DL_TYPE:0x800, \
                            NW_SRC:ip(src), NW_DST:ip(dst) }
                    acts = [forward(outport)]
                    raw[curr].append((pat,acts))
                    last = curr
                    curr = next
    return policy_of_dict(raw)

def getPathFrequencies(g, label_name='label'):
	apsp = nx.all_pairs_shortest_path(g)

	l = [v0 for v in apsp.itervalues() for v0 in v.itervalues()]
	l_label = [[g.node[i][label_name] for i in item]  for item in l]


	prepared_l_label0 = [zip(path, ['/' for i in range(len(path))]) for path in l_label]
	prepared_l_label1 = [[el for subsublist in sublist for el in subsublist][:-1] for sublist in prepared_l_label0]

	all_paths = ['//' + ''.join(str_list) for str_list in prepared_l_label1]
	all_paths.sort()


	result = [[all_paths[0], 1]]

	for i in range(1, len(all_paths)):
		if all_paths[i] == all_paths[i-1]:
			result[-1][1] += 1
		else:
			result.append([all_paths[i], 1])

	freq = {}
	for el in result:
		freq[el[0]] = el[1]

	return freq

def initialize_graph(size):
    points_x = []
    points_y = []
    terminals = []
    for i in range(size):
        points_x.append(random.uniform(-100, 100))
        points_y.append(random.uniform(-100, 100))
    for i in range(size):
        if i % 2 == 0:
            terminals.append(i)

    h = nx.erdos_renyi_graph(size, 0.3)
    g = nx.Graph()
    for i in range(size):
        g.add_node(i)

    for i in range(size):
        for j in range(i, size):
            if h.has_edge(i, j):
                g.add_edge(i, j)
                # weight=manhattan_distance((points_x[i], points_y[i]), (points_x[j], points_y[j])))

    length_shortest_paths = nx.all_pairs_dijkstra_path_length(g)
    shortest_paths = nx.all_pairs_shortest_path(g)

    metric_closure = nx.Graph()
    for i in range(size):
        metric_closure.add_node(i)
    for i in range(size):
        for j in range(size):
            metric_closure.add_edge(i, j, weight=length_shortest_paths[i][j])

    print metric_closure
    return (terminals, shortest_paths, metric_closure, points_x, points_y, g)

 def add_switch(self, dpid, stats):
     if not dpid in self.topology.nodes():
         self.topology.add_node(dpid)
         self.topology.node[dpid]['rules'] = {}
         self.topology.node[dpid]['nActives'] = 0
     if not self.__setting_up__: self.paths_dict = nx.all_pairs_shortest_path(self.topology)
     return

 def rem_switch(self, dpid):
     if dpid in self.topology.nodes():
         self.topology.remove_node(dpid)
         for mac in self.switch_to_host[dpid]:
             del host_to_switch[mac]
         del switch_to_host[dpid]
     if not self.__setting_up__: self.paths_dict = nx.all_pairs_shortest_path(self.topology)
     return

def compareToBinary(complexSentencesById, classifications, exampleBuilder, options):
    # Load corpus and make sentence graphs
    print >> sys.stderr, "Calculating performance on binary corpus"
    classificationsBySentence = {}
    for classification in classifications:
        example = classification[0][0]
        sentenceId = example[0].rsplit(".",1)[0]
        sentenceOrigId = complexSentencesById[sentenceId].sentence.attrib["origId"]
        if not classificationsBySentence.has_key(sentenceOrigId):
            classificationsBySentence[sentenceOrigId] = []
        classificationsBySentence[sentenceOrigId].append(classification)
    
    print >> sys.stderr, "Loading Binary corpus"
    binaryCorpusElements = loadCorpus(options.binaryCorpus)
    binaryClassifications = []
    counter = ProgressCounter(len(binaryCorpusElements.sentences), "Build binary classifications")
    for binarySentence in binaryCorpusElements.sentences:
        counter.update(1, "Building binary classifications ("+binarySentence.sentence.attrib["id"]+"): ")
        if(classificationsBySentence.has_key(binarySentence.sentence.attrib["origId"])):
            complexClassificationGraph = NX.XGraph(multiedges = multiedges)
            for token in binarySentence.sentenceGraph.tokens:
                complexClassificationGraph.add_node(token)
            for classification in classificationsBySentence[binarySentence.sentence.attrib["origId"]]:
                if classification[1] > 0:
                    example = classification[0][0]       
                    t1 = example[3]["t1"]
                    t2 = example[3]["t2"]
                    t1Binary = None
                    for token in binarySentence.sentenceGraph.tokens:
                        if token.attrib["charOffset"] == t1.attrib["charOffset"]:
                            t1Binary = token
                    t2Binary = None
                    for token in binarySentence.sentenceGraph.tokens:
                        if token.attrib["charOffset"] == t2.attrib["charOffset"]:
                            t2Binary = token
                    assert(t1Binary != None and t2Binary != None)
                    complexClassificationGraph.add_edge(t1Binary, t2Binary)
            paths = NX.all_pairs_shortest_path(complexClassificationGraph, cutoff=999)
            for pair in binarySentence.pairs:
                t1 = binarySentence.sentenceGraph.entityHeadTokenByEntity[pair.attrib["e1"]]
                t2 = binarySentence.sentenceGraph.entityHeadTokenByEntity[pair.attrib["e2"]]
                assert(pair.attrib["interaction"] == "True" or pair.attrib["interaction"] == "False")
                if pair.attrib["interaction"] == "True":
                    pairClass = 1
                else:
                    pairClass = -1
                extra = {"xtype":"edge","type":"i","t1":t1,"t2":t2}
                if paths.has_key(t1) and paths[t1].has_key(t2):
                    binaryClassifications.append( [[pair.attrib["id"], pairClass, None, extra], 1, "binary"] )
                else:
                    binaryClassifications.append( [[pair.attrib["id"], pairClass, None, extra], -1, "binary"] )
    print >> sys.stderr, "Evaluating binary classifications"
    evaluation = Evaluation(predictions, classSet=exampleBuilder.classSet)
    print >> sys.stderr, evaluation.toStringConcise()
    if options.output != None:
        evaluation.saveCSV(options.output + "/binary_comparison_results.csv")                    

    def buildExamples(self, sentenceGraph):
        self.makeGSEvents(sentenceGraph)

        eventNodes = []
        nameNodes = []
        for entity in sentenceGraph.entities:
            if entity.get("type") == "neg":
                continue
            if entity.get("isName") == "True":
                nameNodes.append(entity)
            else:
                eventNodes.append(entity)
        allNodes = eventNodes + nameNodes

        examples = []
        exampleIndex = 0

        undirected = sentenceGraph.dependencyGraph.to_undirected()
        paths = NX.all_pairs_shortest_path(undirected, cutoff=999)

        for eventNode in eventNodes:
            eventType = eventNode.get("type")
            if eventType in [
                "Gene_expression",
                "Transcription",
                "Protein_catabolism",
                "Localization",
                "Phosphorylation",
            ]:
                for nameNode in nameNodes:
                    if self.isPotentialGeniaInteraction(eventNode, nameNode):
                        examples.append(self.buildExample(exampleIndex, sentenceGraph, paths, eventNode, nameNode))
                        exampleIndex += 1
            elif eventType in ["Regulation", "Positive_regulation", "Negative_regulation"]:
                combinations = combine.combine(allNodes + [None], allNodes + [None])
                for combination in combinations:
                    if combination[0] == combination[1]:
                        continue
                    if combination[0] == eventNode or combination[1] == eventNode:
                        continue
                    if combination[0] != None and not self.isPotentialGeniaInteraction(eventNode, combination[0]):
                        continue
                    if combination[1] != None and not self.isPotentialGeniaInteraction(eventNode, combination[1]):
                        continue
                    examples.append(
                        self.buildExample(exampleIndex, sentenceGraph, paths, eventNode, combination[0], combination[1])
                    )
                    exampleIndex += 1
            elif eventType in ["Binding"]:
                continue
            else:
                assert False, eventType

        self.gsEvents = None
        return examples

    def __init__(self, topology, shortest_path=None):
        """Constructors
        
        Parameters
        ----------
        topology : fnss.Topology
            The topology object
        shortest_path : dict of dict, optional
            The all-pair shortest paths of the network
        """
        # Filter inputs
        if not isinstance(topology, fnss.Topology):
            raise ValueError('The topology argument must be an instance of '
                             'fnss.Topology or any of its subclasses.')
        
        # Shortest paths of the network
        self.shortest_path = shortest_path if shortest_path is not None \
                             else nx.all_pairs_shortest_path(topology)
        
        # Network topology
        self.topology = topology
        
        # Dictionary mapping each content object to its source
        # dict of location of contents keyed by content ID
        self.content_source = {}
        
        # Dictionary of cache sizes keyed by node
        self.cache_size = {}
        
        self.colla_table = {}

        # Dictionary of link types (internal/external)
        self.link_type = nx.get_edge_attributes(topology.to_directed(), 'type')
        
        self.link_delay = fnss.get_delays(topology.to_directed())
        
        policy_name = topology.graph['cache_policy']
        # Initialize attributes
        for node in topology.nodes_iter():
            stack_name, stack_props = fnss.get_stack(topology, node)
            if stack_name == 'cache':
                self.cache_size[node] = stack_props['size']
                self.colla_table[node] = {}
            elif stack_name == 'source':
                contents = stack_props['contents']
                for content in contents:
                    self.content_source[content] = node
        cache_size = dict((node, fnss.get_stack(topology, node)[1]['size'])
                          for node in topology.nodes_iter()
                          if fnss.get_stack(topology, node)[0] == 'cache')
        # The actual cache object storing the content
        self.caches = dict((node, cache_policy_register[policy_name](cache_size[node]))
                            for node in cache_size)

 def test_all_pairs_shortest_path(self):
     p=nx.shortest_path(self.cycle)
     assert_equal(p[0][3],[0,1,2,3])
     assert_equal(p,nx.all_pairs_shortest_path(self.cycle))
     p=nx.shortest_path(self.grid)
     assert_equal(p[1][12],[1, 2, 3, 4, 8, 12])
     # now with weights
     p=nx.shortest_path(self.cycle,weighted=True)
     assert_equal(p[0][3],[0,1,2,3])
     assert_equal(p,nx.all_pairs_dijkstra_path(self.cycle))
     p=nx.shortest_path(self.grid,weighted=True)
     assert_equal(p[1][12],[1, 2, 3, 4, 8, 12])

 def run(self):
      """here we wait for the topology to be "complete", then calculate what is needed and stop the thread"""
      self.__cur__ = self.__init_idle__ = time.time()
      self.__setting_up__ = True
      while (self.__cur__ < self.__init_idle__ + 5):
         self.__cur__ = time.time()
         #print 'Detecting topology, idle for ',self.__cur__ - self.__init_idle__
         time.sleep(0.001)
      print 'Finished detecting topology, creating data...'
      self.paths_dict = nx.all_pairs_shortest_path(self.topology)
      self.__setting_up__ = False
      print 'Finished creating data'

 def test_all_pairs_shortest_path(self):
     p=nx.shortest_path(self.cycle)
     assert_equal(p[0][3],[0,1,2,3])
     assert_equal(p,nx.all_pairs_shortest_path(self.cycle))
     p=nx.shortest_path(self.grid)
     validate_grid_path(4, 4, 1, 12, p[1][12])
     # now with weights
     p=nx.shortest_path(self.cycle,weight='weight')
     assert_equal(p[0][3],[0,1,2,3])
     assert_equal(p,nx.all_pairs_dijkstra_path(self.cycle))
     p=nx.shortest_path(self.grid,weight='weight')
     validate_grid_path(4, 4, 1, 12, p[1][12])

 def transitveReduction(self, digraph):
     paths = dict(NX.all_pairs_shortest_path(digraph))
     def hasPath(node1, node2):
         if node1 == node2:
             return False
         return (node1 in paths and node2 in paths[node1] and
                 len(paths[node1][node2]) > 0)
     for x in digraph.nodes():
         for y in digraph.nodes():
             for z in digraph.nodes():
                 if (x != z and digraph.has_edge(x, z) and hasPath(x, y) and
                     hasPath(y, z)):
                     digraph.remove_edge(x, z)

 def all_pairs_shortest_path(cls,topology):
     location_paths = {}
     switch_paths = nx.all_pairs_shortest_path(topology)
     for s1, paths in switch_paths.items():
         location_paths[s1] = {}
         for s2, path in paths.items():
             location_paths[s1][s2] = []
             cur = s1
             for nxt in path + [s2]:
                 if cur != nxt:
                     link = topology[cur][nxt]
                     loc = Location(cur,link[cur])
                     location_paths[s1][s2].append(loc)
                 cur = nxt
     return location_paths

def main(list_of_filenames):
	"""
	the function that runs all the experiments
	"""
	list_of_param_graphs = read_graphs_params(list_of_filenames[0])
	list_of_coeffs = read_coeff(list_of_filenames[1])

	list_of_setP = []
	list_of_path_dict = []
	list_of_uncovered_edges = []
	list_of_graph_iDs = []

	for param_graphs in list_of_param_graphs: # getting each graph parameters
		list_of_graph_iDs.append(param_graphs[0])
		H = nx.fast_gnp_random_graph(param_graphs[1], param_graphs[2], param_graphs[3], False)
		randSeed = param_graphs[6]

		for (u,v) in H.edges():
			random.seed(randSeed)
			rInt = random.randint(param_graphs[4], param_graphs[5])
			H[u][v]['w'] = rInt
			randSeed += 1

		set_of_paths_P = nx.all_pairs_shortest_path(H)
		setP = gc.remove_duplicate_paths(set_of_paths_P, nx.number_of_nodes(H))
		list_of_setP.append(setP)
		path_dict = create_path_dict(setP)
		list_of_path_dict.append(path_dict)
		uncovered_edges = gc.get_all_edges_from_SOP(setP)
		list_of_uncovered_edges.append(uncovered_edges)


	out_file = ''.join(["./data/csv/",list_of_filenames[2],".csv"])
	file = open(os.path.expanduser(out_file), 'at')
	writer = csv.writer(file)
	for idx in xrange(len(list_of_setP)): #loop through the graphs
		graph_iD = list_of_graph_iDs[idx]
		writer.writerow(('Graph Params: ', list_of_param_graphs[idx]))
		for coeffs in list_of_coeffs:
			for iteration in xrange(1): # change the input to xrange() depending on the number of iterations on a single experiment
				t_path_dict = list_of_path_dict[idx]
				t_uncovered_edges = set(list_of_uncovered_edges[idx])
				t_setP = list_of_setP[idx]
				six_tuple = gf.func_wrapper_greedy_algo(t_path_dict, t_uncovered_edges, coeffs[0])
				writer.writerow((graph_iD, coeffs[0], six_tuple[0], len(t_setP), six_tuple[1], 
					six_tuple[2], six_tuple[3], six_tuple[4], six_tuple[5]))
	file.close()

    def __init__(self, costfun="nocore", tm="2004", tm_factor_name="max-50",
            EPscalingFactor=1, mappingseed=None):
        """ costfun is a string in ["10xcore", "nocore"] """

        logger.info("Initializing a new EnterpriseTopology")
        logger.debug("Traffic matrix: %s" % str(tm))
        logger.debug("Traffic costfun: %s" % str(costfun))

        # Use this to initialize the random seed when a EnterpriseTopology instance
        # is not created using panoptisim.py
        if mappingseed is not None:
            random.seed(mappingseed)

        self.name = "enterprise"
        self.tm = tm
        self.port = OrderedDict()

        endpoint_scaling_factor = EPscalingFactor
        assert EPscalingFactor == int(EPscalingFactor)

        self.trace_duration = trace_durations[tm]
        lbnl = json.load(open("traces/tm"+tm+".json"))

        self.graph = self.__enterprise_to_nx()
        self.leaves = self.__prune_access_switches(endpoint_scaling_factor)
        self.paths = nx.all_pairs_shortest_path(self.graph)

        #Ensure symmetry in the original shortest paths
        for src in self.graph.nodes():
            for dst in self.graph.nodes():
                self.paths[src][dst] = list(reversed(self.paths[dst][src]))

        # Map endpoints and project load over the shortest path topology
        self.__map_end_points(lbnl)
        self.__project_base_load()

        # Scale up the traffic according to the tm_factor_name and re-project
        # new scaled-up traffic load
        self.tm_scaling_factor = self.__calculate_traffic_scaling_factor(tm_factor_name)
        self.__scale_traffic(self.tm_scaling_factor)
        self.__project_base_load()

        #Ensure every link has at any flow traversing it at most once
        for src, dst, e in self.graph.edges(data=True):
            flows_by_srcdst = e['flows']
            for key, value in flows_by_srcdst.iteritems():
                assert value == 1

def approximate(G):
    D = nx.diameter(G)-3
    paths = nx.all_pairs_shortest_path(G,cutoff=D)
    centralityScore= {}
    total = 0.0
    for path in paths.keys():
        for p in paths[path].keys():
            for nodes in paths[path][p]:
                if nodes not in centralityScore:
                    centralityScore[nodes] = 1.0
                    total += 1.0
                else:
                    centralityScore[nodes] += 1.0
                    total += 1.0
    for x in centralityScore.keys():
        centralityScore[x] /= total
    return centralityScore

 def buildExamples(self, sentenceGraph):
     examples = []
     exampleIndex = 0
     
     undirected = sentenceGraph.dependencyGraph.to_undirected()
     #undirected = self.makeUndirected(sentenceGraph.dependencyGraph)
     paths = NX.all_pairs_shortest_path(undirected, cutoff=4)
     #key1 = paths.keys()[0]
     #key2 = paths[key1].keys()[0]
     #print key1
     #print key2
     #print paths[key1][key2]
     #sys.exit(0)
     for i in range(len(sentenceGraph.tokens)-1):
         for j in range(i+1,len(sentenceGraph.tokens)):
             tI = sentenceGraph.tokens[i]
             tJ = sentenceGraph.tokens[j]
             # only consider paths between entities (NOTE! entities, not only named entities)
             if (sentenceGraph.tokenIsEntityHead[tI] == None) or (sentenceGraph.tokenIsEntityHead[tJ] == None):
                 continue
             # find the path
             if paths.has_key(tI) and paths[tI].has_key(tJ):
                 path = paths[tI][tJ]
             elif paths.has_key(tJ) and paths[tJ].has_key(tI):
                 path = paths[tJ][tI]
             else:
                 continue
             if len(path) > 2:
                 # define class
                 if sentenceGraph.interactionGraph.has_edge(path[0], path[-1]):
                     self.buildExample(path, sentenceGraph, 1, examples, exampleIndex)
                     exampleIndex += 1
                 else:
                     self.buildExample(path, sentenceGraph, -1, examples, exampleIndex)
                     exampleIndex += 1
                 if sentenceGraph.interactionGraph.has_edge(path[-1], path[0]):
                     self.buildExample(path[::-1], sentenceGraph, 1, examples, exampleIndex)
                     exampleIndex += 1
                 else:
                     self.buildExample(path[::-1], sentenceGraph, -1, examples, exampleIndex)
                     exampleIndex += 1
     #print "examples:",len(examples)
     #sys.exit(0)
     return examples

def read_test_data():
    points_x = []
    points_y = []
    terminals = []

    f = open("input.txt")
    for i in range(8):
        f.readline()
    number_of_nodes = int((f.readline().split())[1])
    number_of_edges = int((f.readline().split())[1])

    g = nx.Graph()
    for i in range(number_of_nodes):
        g.add_node(i)

    for i in range(number_of_edges):
        temp = f.readline().split()
        g.add_edge(int(temp[1]) - 1, int(temp[2]) - 1, weight=int(temp[3]))
    for i in range(3):
        f.readline()

    number_of_terminals = int(f.readline().split()[1])
    for i in range(number_of_terminals):
        terminals.append(int(f.readline().split()[1]) - 1)
    for i in range(3):
        f.readline()
    for i in range(number_of_nodes):
        temp = f.readline().split()
        points_x.append(int(temp[2]))
        points_y.append(int(temp[3]))

    length_shortest_paths = nx.all_pairs_dijkstra_path_length(g)
    shortest_paths = nx.all_pairs_shortest_path(g)

    metric_closure = nx.Graph()
    for i in range(number_of_nodes):
        metric_closure.add_node(i)
    for i in range(number_of_nodes):
        for j in range(number_of_nodes):
            metric_closure.add_edge(i, j, weight=length_shortest_paths[i][j])

    print metric_closure
    return (terminals, shortest_paths, metric_closure, points_x, points_y, g)

def get_pairwise_distances(npalign, tree_file=None, seq_file=None):

    if seq_file is None:
        fasta_handle = NTF(mode="w")
    else:
        fasta_handle = open("/tmp/tmp.fasta", "w")
    if tree_file is None:
        tree_handle = NTF()
    else:
        tree_handle = open(tree_file, "w")
    seq_names = fasta_write(fasta_handle, npalign)

    fasta_handle.flush()
    os.fsync(fasta_handle.fileno())
    cmd = "muscle -in %(ifile)s -tree2 %(treefile)s -gapopen -2.9"
    cmdlist = shlex.split(cmd % {"ifile": fasta_handle.name, "treefile": tree_handle.name})

    try:
        t = check_output(cmdlist)
        tree = Phylo.read(open(tree_handle.name), "newick")
    except CalledProcessError:
        # print('Could not make tree')
        return None
    except ValueError:
        # print('no tree present')
        return None
    except RuntimeError:
        return None

    seq_names = sorted(tree.get_terminals(), key=lambda x: x.name)
    net = Phylo.to_networkx(tree)
    dmat = networkx.all_pairs_shortest_path(net)
    terminals = tree.get_terminals()
    dists = np.zeros((npalign.shape[0], npalign.shape[0]))
    for t1, t2 in product(terminals, terminals):
        path = dmat[t1][t2]
        dist = sum(c.branch_length for c in path)
        i1 = int(t1.name.split("-")[1])
        i2 = int(t2.name.split("-")[1])
        dists[i1, i2] = dist

    return dists