def test_multigraph_keys(self):
        """Tests that the minimum spanning edges of a multigraph
        preserves edge keys.

        """
        G = nx.MultiGraph()
        G.add_edge(0, 1, key="a", weight=2)
        G.add_edge(0, 1, key="b", weight=1)
        mst_edges = nx.minimum_spanning_edges(G, algorithm="kruskal", data=False)
        assert_equal([(0, 1, "b")], list(mst_edges))
        mst_edges = nx.minimum_spanning_edges(G, algorithm="prim", data=False)
        assert_equal([(0, 1, "b")], list(mst_edges))

def graph_mst(dist, labels, limit):
    """Обёртка над алгоритмом MST"""

    from collections import deque;
    
    S = nx.Graph(); #исходный граф
    S.add_nodes_from(labels);
    R = S.copy(); #результат кластеризации
    C = nx.Graph(); #читаемый результат

    dq = deque(dist);        
    len_x = len(labels);
    for x in range( len_x-1 ):
        for y in range(x + 1, len_x):
            S.add_edge( labels[x], labels[y], weight=dq.popleft() );

    mst = deque(nx.minimum_spanning_edges(S, data=True));
    del S;

    R.add_edges_from( [edge for edge in mst if( edge[2]['weight'] <= limit)] );

    for num, clust in enumerate(nx.connected_components(R)):
        C.add_node(num, {
                   'size':len(clust),
                   'members': clust
                   });
    del R;

    return 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 get_DT(MI_subset):
    #we use networkx package
    #create a Graph object
    G = nx.Graph()
    G.add_nodes_from(range(len(MI_subset)))
    edge_list = []
    for i in range(len(MI_subset)):
        for j in range(i+1,len(MI_subset)):
            #we negate MI, turning into a MST problem
            edge_list.extend([(i,j,-MI_subset[i][j]),(j,i,-MI_subset[j][i])])
    G.add_weighted_edges_from(edge_list)
    
    min_span_tree = sorted(list(nx.minimum_spanning_edges(G)))
    #rearrange the mst s.t. all 1st axis is parents of 2nd axis
    N = len(min_span_tree)
    #indicates which nodes are added, hence they are not children
    indicator = np.zeros((N+1,1)) #add 1 to compensate for N edges and N+1 nodes
    temp1,temp2,_ = min_span_tree.pop(0)
    rearranged = [[temp1,temp2]]
    indicator[[rearranged[0][0],rearranged[0][1]]] = 1 #default parents
    while min_span_tree:
        for ins in range(len(min_span_tree)):
            if indicator[min_span_tree[ins][0]]==1:
                temp1,temp2,_ = min_span_tree.pop(ins)
                rearranged.append([temp1,temp2])
                indicator[temp2] = 1
                break
            elif indicator[min_span_tree[ins][1]]==1:
                temp1,temp2,_ = min_span_tree.pop(ins)
                rearranged.append([temp2,temp1])
                indicator[temp1] = 1
                break
    return rearranged

 def test_nan_weights(self):
     # Edge weights NaN never appear in the spanning tree. see #2164
     G = self.G
     G.add_edge(0, 12, weight=float('nan'))
     edges = nx.minimum_spanning_edges(G, algorithm=self.algo,
                                       data=False, ignore_nan=True)
     actual = sorted((min(u, v), max(u, v)) for u, v in edges)
     expected = [(u, v) for u, v, d in self.minimum_spanning_edgelist]
     assert_edges_equal(actual, expected)
     # Now test for raising exception
     edges = nx.minimum_spanning_edges(G, algorithm=self.algo,
                                       data=False, ignore_nan=False)
     assert_raises(ValueError, list, edges)
     # test default for ignore_nan as False
     edges = nx.minimum_spanning_edges(G, algorithm=self.algo, data=False)
     assert_raises(ValueError, list, edges)

 def iterativeAlgorithm(self):
     T = nx.Graph()
     for n in T:
         T.node[n]=self.node[n].copy()
     T.graph=self.graph.copy()
     for u, v, d in nx.minimum_spanning_edges(self, data=True):
         T.add_edge(u,v,d)
         yield T

 def test_without_data(self):
     edges = nx.minimum_spanning_edges(self.G, algorithm=self.algo,
                                       data=False)
     # Edges from the spanning edges functions don't come in sorted
     # orientation, so we need to sort each edge individually.
     actual = sorted((min(u, v), max(u, v)) for u, v in edges)
     expected = [(u, v) for u, v, d in self.minimum_spanning_edgelist]
     assert_edges_equal(actual, expected)

    def test_unicode_name(self):
        """Tests that using a Unicode string can correctly indicate
        Borůvka's algorithm.

        """
        edges = nx.minimum_spanning_edges(self.G, algorithm=u'borůvka')
        # Edges from the spanning edges functions don't come in sorted
        # orientation, so we need to sort each edge individually.
        actual = sorted((min(u, v), max(u, v), d) for u, v, d in edges)
        assert_edges_equal(actual, self.minimum_spanning_edgelist)

def euclidean_minimum_spanning_tree(nodes,**kwargs):
    """
    :param nodes: list of (x,y) nodes positions
    :return: :class:`GeoGraph` with minimum spanning tree between nodes

    see https://en.wikipedia.org/wiki/Euclidean_minimum_spanning_tree
    """
    g=GeoGraph(None,**kwargs)
    d=delauney_triangulation(nodes,**kwargs)
    g.add_edges_from(nx.minimum_spanning_edges(d, weight='length'))
    return g

def create_islands(graph):
    # create minimum spanning tree from undirected edges
    mst_edges = sorted(list(nx.minimum_spanning_edges(graph, data=True)))
    islands = nx.Graph()
    for e0, e1, w in mst_edges:
        ring0 = graph.node[e0]["ring"]
        ring1 = graph.node[e1]["ring"]
        local0, local1 = graph.node[e0]["local"], graph.node[e1]["local"]
        if ring0 != ring1:
            islands.add_edge(ring0, ring1, weight=w, connection=[e0, e1, local0, local1])
    return islands

def euclidean_minimum_spanning_tree(nodes, **kwargs):
    """
    :param nodes: list of (x,y) nodes positions
    :return: geograph with minimum spanning tree between  nodes
    see https://en.wikipedia.org/wiki/Euclidean_minimum_spanning_tree
    """
    g = GeoGraph(None, **kwargs)
    d = delauney_triangulation(nodes, **kwargs)
    for edge in nx.minimum_spanning_edges(d, weight="length"):
        g.add_edge(*edge)
    return g

def main():
	# build up a graph
	filename = '../../florentine_families_graph.gpickle'
	G = nx.read_gpickle(filename)

	# Spanning tree
	mst = nx.minimum_spanning_tree(G) 
	out_file = 'florentine_families_graph_minimum_spanning_tree.png'
	PlotGraph.plot_graph(G, filename=out_file, colored_edges=mst.edges())

	edges = nx.minimum_spanning_edges(G, weight='weight', data=True)
	list_edges = list(edges)
	print(list_edges)

def mst_pairs(pairs):
    """Given all pairwise distances, determine the minimal spanning subset.

    Convert pairwise distances to an undirected graph, determine the
    minumum spanning tree, and emit the minimal list of edges to connect all
    nodes.

    Input: iterable of (SeqRecord, SeqRecord, distance)
    Output: iterable of (SeqRecord, SeqRecord)
    """
    G = networkx.Graph()
    for left, right, score in pairs:
        G.add_edge(left, right, weight=1.0/score)
    mst = networkx.minimum_spanning_edges(G, data=False)
    return list(mst)

def minimum_spanning_tree(G, weight="weight"):
    """Return a minimum spanning tree or forest of an undirected 
    weighted graph.

    A minimum spanning tree is a subgraph of the graph (a tree) with
    the minimum sum of edge weights.

    If the graph is not connected a spanning forest is constructed.  A
    spanning forest is a union of the spanning trees for each
    connected component of the graph.

    Parameters
    ----------
    G : NetworkX Graph
    
    weight : string
       Edge data key to use for weight (default 'weight').

    Returns
    -------
    G : NetworkX Graph
       A minimum spanning tree or forest. 
    
    Examples
    --------
    >>> G=nx.cycle_graph(4)
    >>> G.add_edge(0,3,weight=2) # assign weight 2 to edge 0-3
    >>> T=nx.minimum_spanning_tree(G)
    >>> print(sorted(T.edges(data=True)))
    [(0, 1, {}), (1, 2, {}), (2, 3, {})]

    Notes
    -----
    Uses Kruskal's algorithm.

    If the graph edges do not have a weight attribute a default weight of 1
    will be used.
    """
    T = nx.Graph(nx.minimum_spanning_edges(G, weight=weight, data=True))
    # Add isolated nodes
    if len(T) != len(G):
        T.add_nodes_from([n for n, d in G.degree().items() if d == 0])
    # Add node and graph attributes as shallow copy
    for n in T:
        T.node[n] = G.node[n].copy()
    T.graph = G.graph.copy()
    return T

def get_sparsified_MPST_remove_leaves(G, K, directed=False):
    '''
    Sparsify graph using most probable spanning tree.
    If |MPST| < K, then add most probable edges that are not included.
    If |MPST| > K, then remove edges that are adjacent to leaves
    '''
    G_edges = G.edges(data=True)
    if directed:
        # MPST_edges = branchings.minimum_spanning_arborescence(G, attr='weight').edges(data=True)
        pass
    else:
        MPST_edges = list(nx.minimum_spanning_edges(G,weight='weight',data=True))
    edges = [e for e in G_edges if e not in MPST_edges]
    mp_edges = sorted(edges,
                    key = lambda (u,v,d): exp(1)**(-d["weight"]),
                    reverse = True)
    if len(MPST_edges) <= K:
        MPST_edges.extend(mp_edges[:(K - len(MPST_edges))])
    else:
        # remove edges that are adjacent to leaves (keeping connectivity)
        # if ties remove with lowest probability (keeping probability)
        #TODO check why in case of directed MPST it doesn't work
        MPST = nx.Graph(MPST_edges)
        degrees = dict()
        leaves = set()
        for u in MPST:
            degrees[u] = len(MPST[u])
            if degrees[u] == 1:
                v, d = MPST[u].items()[0]
                leaves.add((u,v,d["weight"]))
        for _ in range(len(MPST_edges) - K):
            u,v,d = min(leaves, key = lambda (u,v,d): exp(1)**(-d))
            MPST.remove_edge(u,v)
            leaves.remove((u,v,d))
            v_edges = MPST[v].items()
            if len(v_edges) == 1:
                w, t = v_edges[0]
                leaves.add((v,w,t["weight"]))
            elif len(v_edges) == 0:
                leaves.remove((v,u,d))
        print len(MPST.edges()), K
        MPST_edges = MPST.edges(data=True)
    return MPST_edges

def steiner_tree(G, terminal_nodes, weight='weight'):
    """ Return an approximation to the minimum Steiner tree of a graph.

    Parameters
    ----------
    G : NetworkX graph

    terminal_nodes : list
         A list of terminal nodes for which minimum steiner tree is
         to be found.

    Returns
    -------
    NetworkX graph
        Approximation to the minimum steiner tree of `G` induced by
        `terminal_nodes` .

    Notes
    -----
    Steiner tree can be approximated by computing the minimum spanning
    tree of the subgraph of the metric closure of the graph induced by the
    terminal nodes, where the metric closure of *G* is the complete graph in
    which each edge is weighted by the shortest path distance between the
    nodes in *G* .
    This algorithm produces a tree whose weight is within a (2 - (2 / t))
    factor of the weight of the optimal Steiner tree where *t* is number of
    terminal nodes.

    """
    # M is the subgraph of the metric closure induced by the terminal nodes of
    # G.
    M = metric_closure(G, weight=weight)
    # Use the 'distance' attribute of each edge provided by the metric closure
    # graph.
    H = M.subgraph(terminal_nodes)
    mst_edges = nx.minimum_spanning_edges(H, weight='distance', data=True)
    # Create an iterator over each edge in each shortest path; repeats are okay
    edges = chain.from_iterable(pairwise(d['path']) for u, v, d in mst_edges)
    T = G.edge_subgraph(edges)
    return T

def plotGraph(g,filename):
    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 _min_cycle_basis(comp, weight):
    cb = []
    # We  extract the edges not in this spanning tree
    spanning_tree_edges = list(
        nx.minimum_spanning_edges(comp, weight=None, data=False))
    edges_excl = [
        frozenset(e) for e in comp.edges() if e not in spanning_tree_edges]
    N = len(edges_excl)

    # We maintain a set of vectors orthogonal to sofar found cycles
    set_orth = [set([edge]) for edge in edges_excl]
    for k in xrange(N):
        # kth cycle is "parallel" to kth vector in set_orth
        new_cycle = _min_cycle(comp, set_orth[k], weight=weight)
        cb.append(list(set().union(*new_cycle)))
        # now update set_orth so that k+1,k+2... th elements are
        # orthogonal to the newly found cycle, as per [p. 336, 1]
        base = set_orth[k]
        set_orth[k + 1:] = [orth ^ base if len(orth & new_cycle) % 2\
                            else orth for orth in set_orth[k + 1:]]

    return cb

for e in weighted_edges:
    f = e[0]
    t = e[1]
    w = e[2]
    if w > 20:
        G2.add_edge(f, t, weight=w)

nx.write_graphml(G2, 'topic_graph.graphml')

# minimum spanning tree
T = nx.algorithms.minimum_spanning_tree(G2, weight='weight')
nx.write_graphml(T, "spanning_tree.graphml")

# spanning edges
E = nx.minimum_spanning_edges(G2, weight='weight')
nx.write_graphml(T, "spanning_edges.graphml")

# code -> topic
code_topic = {'0' : 'EU roma külpolitika',
              '1' : 'Roma önkormányzat',
              '2' : 'Magyar Gárda, stb.',
              '3' : 'Lopással kapcsolatos hírek',
              '4' : 'Roma-nem roma társadalmi prolémák, stb.',
              '5' : 'Politikai pártok, politikusok',
              '6' : 'Ingatlanüggyel, lakhatással kapcsolatos problémák, bűntények',
              '7' : 'Máshonnan átvett tartalmak',
              '8' : 'Vidéki települések roma-többségi konfliktusai',
              '9' : 'Egészségügy',
              '10' : 'Közbiztonság, önvédelem, polgárőrség',
              '11' : 'Olvasói történetek',

def minimum_spanning_tree(G,weight='weight'):
    T=nx.Graph(nx.minimum_spanning_edges(G,weight=weight,data=True))
    return T