def __remove_random_fermat_point(self, input_graph, fermat_points):
     graph = input_graph.copy()
     points_count = len(fermat_points)
     if points_count > 1:
         point_to_delete = fermat_points[rnd.randint(0, points_count-1)]
         graph.remove_node(point_to_delete)
         if nx.is_connected(graph):
             return nx.minimum_spanning_tree(graph), graph
     return nx.minimum_spanning_tree(input_graph), input_graph

 def test_prim_minimum_spanning_tree_edges_specify_weight(self):
     G = nx.Graph()
     G.add_edge(1, 2, weight=1, color="red", distance=7)
     G.add_edge(1, 3, weight=30, color="blue", distance=1)
     G.add_edge(2, 3, weight=1, color="green", distance=1)
     G.add_node(13, color="purple")
     G.graph["foo"] = "bar"
     T = nx.minimum_spanning_tree(G, algorithm="prim")
     assert_equal(sorted(T.nodes()), [1, 2, 3, 13])
     assert_equal(sorted(T.edges()), [(1, 2), (2, 3)])
     T = nx.minimum_spanning_tree(G, weight="distance", algorithm="prim")
     assert_equal(sorted(T.edges()), [(1, 3), (2, 3)])
     assert_equal(sorted(T.nodes()), [1, 2, 3, 13])

 def test_mst_edges_specify_weight(self):
     G=nx.Graph()
     G.add_edge(1,2,weight=1,color='red',distance=7)
     G.add_edge(1,3,weight=30,color='blue',distance=1)
     G.add_edge(2,3,weight=1,color='green',distance=1)
     G.add_node(13,color='purple')
     G.graph['foo']='bar'
     T=nx.minimum_spanning_tree(G)
     assert_equal(sorted(T.nodes()),[1,2,3,13])
     assert_equal(sorted(T.edges()),[(1,2),(2,3)])
     T=nx.minimum_spanning_tree(G,weight='distance')
     assert_equal(sorted(T.edges()),[(1,3),(2,3)])
     assert_equal(sorted(T.nodes()),[1,2,3,13])

def spanning_trees():
    G = full_grid_nocut()
    H = nx.Graph()
    nodes1 = []
    nodes2 = []
    
    for u in G.nodes():
        H.add_node(u)
        plant = None
        if u[0] < 5:
            nodes1.append(u)
            plant = 1
        else:
            nodes2.append(u)
            plant = 2
        H.node[u]['plant'] = plant
            
    G1 = G.subgraph(nodes1)
    G2 = G.subgraph(nodes2)
    
    S1 = nx.minimum_spanning_tree(G1)
    S2 = nx.minimum_spanning_tree(G2)
    
    for u, v in S1.edges() + S2.edges():
        H.add_edge(u, v)
        H[u][v]['difficulty'] = 1
    
    H.graph['nests'] = G.graph['nests']
    H.graph['name'] = 'span_trees'
    
    '''
    H = partition_plants(H)
    H.graph['name'] = 'span_trees'
    '''
    
    assign_difficulties(H)
    
    for i in xrange(11):
        u, v = (4, i), (5, i)
        H.add_edge(u, v)
        H[u][v]['difficulty'] = 3

    '''
    for i in xrange(10):
        u, v = (i, 5), (i + 1, 5)
        H.add_edge((i, 5), (i + 1, 5))
        H[u][v]['difficulty'] = 1
    '''
    
    return H

def chords (G):
  """Return a new graph that contains the edges that are the chords of G.

      The chords are all the edges that are not in a spanning three of G.

  Parameters
  ----------
  G : graph
     A NetworkX graph.

  Returns
  -------
  C : A new graph with the chords of G.
  T : The spanning tree from which C was calculated.

  """
  if G.is_directed ():
    if G.is_multigraph ():
      T = nx.minimum_spanning_tree (nx.MultiGraph (G))
    else:
      T = nx.minimum_spanning_tree (nx.Graph (G))
  else:
    T = nx.minimum_spanning_tree (G)

  C     = G.copy ()
  edges = T.edges_iter ()

  for e in edges:
    try:
      C.remove_edge (*e)
    except:
      C.remove_edge (*e[::-1])

  #deg = C.degree_iter ();
  #for d in deg:
  #  if d[1] == 0:
  #    C.remove_node (d[0])

  # Recreate T to get the same type as G
  T = G.copy ()
  if G.is_multigraph ():
    edges = C.edges_iter (keys=True)
  else:
    edges = C.edges_iter ()

  for e in edges:
    T.remove_edge (*e)

  return T,C

def plotGraph(g,filename):
    """
    Creates a plot of the graph passed in after transforming
    the full graph into a minimum spanning tree. The MST of a graph
    like this has some significance (but also some locally strange paths)
    and is nice to look add due to the reduced edge density.
    """

    plt.figure(figsize=(15, 10))
    np.random.seed(5)
    mst = nx.minimum_spanning_tree(g, weight='difference')
    pos = nx.spring_layout(mst, iterations=900, k=.008, weight='difference')

    mst_edges = list(nx.minimum_spanning_edges(g, weight='difference'))
    degs = mst.degree()
    nodesize = [degs[v]*80 for v in mst]

    nl = mst.nodes()

    nx.draw_networkx_edges(g, pos, edgelist=mst_edges, alpha=.2)
    nx.draw_networkx_nodes(g, pos, nodelist = nl, node_size=nodesize, node_color=nodesize)

        
    nx.draw_networkx_labels(g, pos, font_color='k', font_size=7)

    plt.title("Artist Network", fontsize=18)
    plt.xticks([])
    plt.yticks([])
    plt.savefig(filename)

def mst_weight(
        taxa,
        patterns,
        matrices,
        characters
        ):
    """
    Calculate minimal weight of unsorted trees.
    """

    G = nx.Graph()
    for i,tA in enumerate(taxa):
        for j,tB in enumerate(taxa):
            if i < j:
                all_scores = []
                for pt,mt,cs in zip(patterns, matrices, characters):
                    ptA = pt[i]
                    ptB = pt[j]
                    scores = []
                    for pA in ptA:
                        idxA = cs.index(pA)
                        for pB in ptB:
                            idxB = cs.index(pB)
                            score = mt[idxA][idxB]
                        scores += [score]
                    all_scores += [min(scores)]
                G.add_edge(tA, tB, weight=sum(all_scores))
    g = nx.minimum_spanning_tree(G)
    
    return sum([w[2]['weight'] for w in g.edges(data=True)]) / 2

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 compute_initial_guess(num_nodes, relative_rotations, relative_edges):
	graph = nx.Graph()
	graph.add_nodes_from(range(num_nodes))

	for (ind, edge) in enumerate(relative_edges):
		(n, theta) = so3.matrix_to_axis_angle(relative_rotations[ind])
		graph.add_edge(edge[0], edge[1], weight=theta, index=ind)

	tree = nx.minimum_spanning_tree(graph)

	global_rotation = []

	for i in range(num_nodes):
		global_rotation.append(numpy.identity(3))

	edges = nx.dfs_edges(tree, 0)

	for edge in edges:
		ind = graph[edge[0]][edge[1]]["index"]
		mat = relative_rotations[ind]

		if relative_edges[ind][0] == edge[0] and relative_edges[ind][1] == edge[1]:
			pass
		elif relative_edges[ind][0] == edge[1] and relative_edges[ind][1] == edge[0]:
			mat = mat.transpose()
		else:
			logging.error("GRAPH ERROR")

		global_rotation[edge[1]] = mat.dot(global_rotation[edge[0]])

	return global_rotation

def minimal_couplers(subgraphs, edges):
    '''Use the fewest possible number of couplers between and within
    subgraphs'''

    N = len(subgraphs)

    # map each subgraph to its minimum spanning tree
    subgraphs = [nx.minimum_spanning_tree(subgraph) for subgraph in subgraphs]

    # for each tree, find a root node and store the shortest path to each
    # node as a cost metric.
    costs = {}
    for tree in subgraphs:
        # identify the root
        path_lengths = nx.shortest_path_length(tree)
        root_weights = {k: sum(path_lengths[k].values()) for k in path_lengths}
        root = sort_dict(root_weights)[0]
        # assign path lengths as node costs
        for node in path_lengths[root]:
            costs[node] = path_lengths[root][node]

    # for each pair of subgraphs, keep the inter-subgraph edge with the
    # minimum total cost of its end nodes
    nodes = sorted(subgraphs.keys())
    for i in xrange(N-1):
        q1 = nodes[i]
        for j in xrange(i+1, N):
            q2 = nodes[j]
            edge_costs = {e: costs[e[0]]+costs[e[1]] for e in edges[(q1, q2)]}
            edges[(q1, q2)] = sort_dict(edge_costs)[0]

    return subgraphs, edges

 def test_prim_minimum_spanning_tree_disconnected(self):
     G = nx.Graph()
     G.add_edge(1, 2)
     G.add_edge(10, 20)
     T = nx.minimum_spanning_tree(G, algorithm='prim')
     assert_equal(sorted(map(sorted, T.edges())), [[1, 2], [10, 20]])
     assert_equal(sorted(T.nodes()), [1, 2, 10, 20])

    def _retrieve_skycoords(V):
        coords_l = []
        # Accessing the borders one by one. At this step, V_subgraphs contains a list of cycles
        # (i.e. one describing the external border of the MOC component and several describing the holes
        # found in the MOC component).
        V_subgraphs = nx.connected_component_subgraphs(V)
        for v in V_subgraphs:
            # Compute the MST for each cycle
            v = nx.convert_node_labels_to_integers(v)
            mst = nx.minimum_spanning_tree(v)
            # Get one end of the span tree by looping over its node and checking if the degree is one
            src = None
            for (node, deg) in mst.degree():
                if deg == 1:
                    src = node
                    break

            # Get the unordered lon and lat
            ra = np.asarray(list(nx.get_node_attributes(v, 'ra').values()))
            dec = np.asarray(list(nx.get_node_attributes(v, 'dec').values()))
            coords = np.vstack((ra, dec)).T
            # Get the ordering from the MST
            ordering = np.asarray(list(nx.dfs_preorder_nodes(mst, src)))
            # Order the coords
            coords = coords[ordering]
            # Get a skycoord containing N coordinates computed from the Nx2 `coords` array
            coords = SkyCoord(coords, unit="deg")
            coords_l.append(coords)

        return coords_l

def chow_liu(data, mi_estimator=discrete_mutual_information):
    arguments = list(data.columns)
    g = nx.Graph()
    g.add_nodes_from(arguments)
    for src, dst in combinations(arguments, 2):
        g.add_edge(src, dst, weight=-mi_estimator(data[[src]], data[[dst]]))
    return DGM(nx.dfs_tree(nx.minimum_spanning_tree(g), arguments[0]))

def visualize_mst(votes):
    min_spanning_tree = nx.minimum_spanning_tree(votes, weight = 'difference')

    #this makes sure draw_spring results are the same at each call
    np.random.seed(1)  

    color = [min_spanning_tree.node[senator]['color'] for senator in min_spanning_tree.nodes()]

    #determine position of each node using a spring layout
    pos = nx.spring_layout(min_spanning_tree, iterations=200)
    plt.figure(figsize=(25,25))


    #plot the edges
    nx.draw_networkx_edges(min_spanning_tree, pos, alpha = .5)

    #plot the nodes
    nx.draw_networkx_nodes(min_spanning_tree, pos, node_color=color)

    #draw the labels
    lbls = nx.draw_networkx_labels(min_spanning_tree, pos, alpha=5, font_size=8)

    #coordinate information is meaningless here, so let's remove it
    plt.xticks([])
    plt.yticks([])
    remove_border(left=False, bottom=False)

def find_min_spanning_tree(A):
	"""
		Input:
			A : Adjecency matrix in scipy.sparse format.
		Output:
			T : Minimum spanning tree.
			run_time : Total runtime to find minimum spanning tree 

	"""
	# Record start time.
	start = time.time()

	# Check if graph is pre-processed, if yes then don't process it again.
	if os.path.exists('../Data/dcg_graph.json'):
		with open('../Data/dcg_graph.json') as data:
			d = json.load(data)
		G = json_graph.node_link_graph(d)

	# If graph is not preprocessed then convert it to a Graph and save it to a JSON file.
	else:
		G = from_scipy_sparse_matrix(A)
		data = json_graph.node_link_data(G)
		with open('../Data/dcg_graph.json', 'w') as outfile:
			json.dump(data, outfile)

	# Find MST.
	T = minimum_spanning_tree(G)

	#Record total Runtime
	run_time = time.time()-start
	return T, run_time

def test_min_edges():

    # run mod_boruvka on graph with high mv max and long edge and make sure
    # that the result is an MST
    # of eachother (otherwise they should be connected)
    g = graph_high_mvmax_long_edge()

    subgraphs = UnionFind()
    rtree = Rtree()

    # build min span forest via mod_boruvka
    msf_g = mod_boruvka(g, subgraphs=subgraphs, rtree=rtree)

    # use networkx to build mst and compare
    coord_list = msf_g.coords.values()
    c = np.array(coord_list)
    all_dists = np.sqrt(((c[np.newaxis, :, :] - c[:, np.newaxis, :]) ** 2).
                    sum(2))

    complete_g = nx.Graph(all_dists)
    mst_g = nx.minimum_spanning_tree(complete_g)

    mst_edge_set = set([frozenset(e) for e in mst_g.edges()])
    msf_edge_set = set([frozenset(e) for e in msf_g.edges()])
    assert msf_edge_set == mst_edge_set

    def verify_solution(self, sol):
        """Verify the solution for MST against NetworkX's built-in MST solver.
           Only works if the solution is unique (=> edges have unique weights.)"""

        nx_sol = set(nx.minimum_spanning_tree(self.graph).edges())

        return nx_sol == sol

def threshold_matrix(M, cost):
    '''
    M is the full association matrix.
    cost is the percentage (0 to 100) at which you'd like to threshold
    
    threshold_matrix first creates a copy of the input matrix, then
    sets all diagonal values to 0. It next calculates the minimum spanning tree,
    and ensures that those edges are *always* included in the thresholded
    matrix.
    
    then sets all values below the 
    appropriate percentile to 0
    '''
    # Make a copy of the matrix
    thr_M = np.copy(M)
    
    # Set all diagonal values to -999    
    thr_M[np.diag_indices_from(thr_M)] = -999
    
    # Calculate minmum spanning tree
    G = nx.from_numpy_matrix(M)
    mst = nx.minimum_spanning_tree(G, weight='weight'*-1)
    
    # Calculate the threshold value
    thr = np.percentile(thr_M[np.triu_indices_from(thr_M, k=1)], cost)
    
    # Set all values that are less than the threshold to 0
    thr_M[thr_M < thr] = 0
       
    # Set all values that are not zero to 1
    thr_M[thr_M != 0] = 1

    return thr_M

 def test_mst_disconnected(self):
     G=nx.Graph()
     G.add_path([1,2])
     G.add_path([10,20])
     T=nx.minimum_spanning_tree(G)
     assert_equal(sorted(T.edges()),[(1, 2), (20, 10)])
     assert_equal(sorted(T.nodes()),[1, 2, 10, 20])

    def create_spanning_tree(self, username="manager", password="ccw"):
        T = nx.minimum_spanning_tree(self.graph)

        used_links = []
        disabled_ports = {}

        for link in self.links:
            used = False
            src, dst = hex(link.src.dpid), hex(link.dst.dpid)
            for edge in T.edges():
                if (src,dst) == edge or (dst,src) == edge:
                    used = True
            if not used:
                if link.src.dpid not in disabled_ports:
                    disabled_ports[link.src.dpid] = []
                disabled_ports[link.src.dpid].append(link.src.port_no)
        for dp in disabled_ports:
            ip = self.dpid_to_ip[hex(dp)]
            print("logging into " + ip)
            s = spawn("ssh %[email protected]%s" %(username, ip))
            s.expect(".*assword")
            s.sendline(password)
            s.expect("Press any key to continue")
            s.sendline("\r")
            s.sendline("config")
            for n in disabled_ports[dp]:
                #print("Enabling port " + `n` + " on " + self.dpid_to_ip[dp])
                s.sendline("interface ethernet " + `n` + " disable")
            s.sendline("save")
            s.sendline("logo")
            s.sendline("y")
        print("CREATED SPANNING TREE")