def intersection_all(graphs):
    """Return a new graph that contains only the edges that exist in
    all graphs.

    All supplied graphs must have the same node set.

    Parameters
    ----------
    graphs_list : list
       List of NetworkX graphs

    Returns
    -------
    R : A new graph with the same type as the first graph in list

    Notes
    -----
    Attributes from the graph, nodes, and edges are not copied to the new
    graph.
    """
    graphs = iter(graphs)
    R = next(graphs)
    for H in graphs:
        R = nx.intersection(R, H)
    return R

def jaccard(network1, network2, d="directed"):
    """Returns Jaccard similarity coefficient and
    distance of two different networks of the same
    sets of nodes.

    Parameters
    ----------
    network1 : first network edge list
    network2 : second network edge list
    d : directed or undirected
        type of graph

    Returns
    -------
    j : float
        Jaccard similarity coefficient
    jd : float
        Jaccard distance
    """
    if d == "directed":
        g1 = nx.read_weighted_edgelist(network1, create_using=nx.DiGraph())
        g2 = nx.read_weighted_edgelist(network2, create_using=nx.DiGraph())
    elif d == "undirected":
        g1 = nx.read_weighted_edgelist(network1)
        g2 = nx.read_weighted_edgelist(network2)

    union = nx.compose(g1, g2)
    inter = nx.intersection(g1, g2)

    j = float(inter.number_of_edges()) / float(union.number_of_edges())
    jd = 1 - j

    return j, jd

def intersection_all(graphs):
    """Return a new graph that contains only the edges that exist in
    all graphs.

    All supplied graphs must have the same node set.

    Parameters
    ----------
    graphs : list
       List of NetworkX graphs

    Returns
    -------
    R : A new graph with the same type as the first graph in list

    Raises
    ------
    ValueError
       If `graphs` is an empty list.

    Notes
    -----
    Attributes from the graph, nodes, and edges are not copied to the new
    graph.
    """
    if not graphs:
        raise ValueError('cannot apply intersection_all to an empty list')
    graphs = iter(graphs)
    R = next(graphs)
    for H in graphs:
        R = nx.intersection(R, H)
    return R

def test_intersection(testgraph):
    """
    Test the Intersection of the two graphs are same
    """

    a = nx.intersection(testgraph[0], testgraph[1])
    b = sg.digraph_operations.intersection(testgraph[2], testgraph[3])
    digraph_equals(a, b)

def test_intersection():
    G=nx.Graph()
    H=nx.Graph()
    G.add_nodes_from([1,2,3,4])
    G.add_edge(1,2)
    G.add_edge(2,3)
    H.add_nodes_from([1,2,3,4])
    H.add_edge(2,3)
    H.add_edge(3,4)
    I=nx.intersection(G,H)
    assert_equal( set(I.nodes()) , set([1,2,3,4]) )    
    assert_equal( sorted(I.edges()) , [(2,3)] )    

def test_intersection_multigraph_attributes():
    g = nx.MultiGraph()
    g.add_edge(0, 1, key=0)
    g.add_edge(0, 1, key=1)
    g.add_edge(0, 1, key=2)
    h = nx.MultiGraph()
    h.add_edge(0, 1, key=0)
    h.add_edge(0, 1, key=3)
    gh = nx.intersection(g, h)
    assert_equal( set(gh.nodes()) , set(g.nodes()) )
    assert_equal( set(gh.nodes()) , set(h.nodes()) )
    assert_equal( sorted(gh.edges()) , [(0,1)] )
    assert_equal( sorted(gh.edges(keys=True)) , [(0,1,0)] )

def test_intersection_attributes():
    g = nx.Graph()
    g.add_node(0, x=4)
    g.add_node(1, x=5)
    g.add_edge(0, 1, size=5)
    g.graph['name'] = 'g'

    h = g.copy()
    h.graph['name'] = 'h'
    h.graph['attr'] = 'attr'
    h.node[0]['x'] = 7

    gh = nx.intersection(g, h)
    assert_equal( set(gh.nodes()) , set(g.nodes()) )
    assert_equal( set(gh.nodes()) , set(h.nodes()) )
    assert_equal( sorted(gh.edges()) , sorted(g.edges()) )

    h.remove_node(0)
    assert_raises(nx.NetworkXError, nx.intersection, g, h)

def test_intersection_attributes():
    g = nx.Graph()
    g.add_node(0, x=4)
    g.add_node(1, x=5)
    g.add_edge(0, 1, size=5)
    g.graph["name"] = "g"

    h = g.copy()
    h.graph["name"] = "h"
    h.graph["attr"] = "attr"
    h.node[0]["x"] = 7

    gh = nx.intersection(g, h)
    assert_equal(set(gh.nodes()), set(g.nodes()))
    assert_equal(set(gh.nodes()), set(h.nodes()))
    assert_equal(sorted(gh.edges()), sorted(g.edges()))

    h.remove_node(0)
    assert_raises(nx.NetworkXError, nx.intersection, g, h)

def crossover(t1, t2, graph):
    # here we get from |V-1| edges (when two graphs are identical) 
    # to minimum 1 common edge
    edges = nx.compose(t1,t2).edges()
    shuffle(edges)
    # we select the largest resulting subgraph

    g = nx.Graph()
    g.add_nodes_from(t1.nodes())
    for edge in edges:
        if g.size()  == t1.order() - 1:
            break
        if not nx.has_path(g, edge[0], edge[1]):
            g.add_edge(edge[0], edge[1])
    
    if uniform(0,1) <= 0.25:        
        if nx.intersection(t1,t2).size() ==  t1.size():
            mutation(g, graph)

    return g

def intersection_all(graphs):
    """Return a new graph that contains only the edges that exist in
    all graphs.

    All supplied graphs must have the same node set.

    Parameters
    ----------
    graphs_list : list
       Multiple NetworkX graphs.  Graphs must have the same node sets.

    Returns
    -------
    R : A new graph with the same type as the first graph

    Notes
    -----
    Attributes from the graph, nodes, and edges are not copied to the new
    graph.
    """
    R = graphs.pop(0)
    for H in graphs:
        R = nx.intersection(R, H)
    return R

#[(1, 'c'), (3, 'c'), (1, 'b'), (3, 'b'), (2, 'a'), (3, 'a'), (4, 'd'), (1, 'd'), (2, 'b'), (4, 'b'), (2, 'c'), (4, 'c'), (1, 'a'), (4, 'a'), (2, 'd'), (3, 'd')]
GH3.edges()
#[((1, 'c'), (1, 'd')), ((1, 'c'), (1, 'b')), ((1, 'c'), (2, 'c')), ((3, 'c'), (4, 'c')), ((3, 'c'), (2, 'c')), ((3, 'c'), (3, 'b')), ((3, 'c'), (3, 'd')), ((1,'b'), (1, 'a')), ((1, 'b'), (2, 'b')), ((3, 'b'), (3, 'a')), ((3, 'b'), (2, 'b')), ((3, 'b'), (4, 'b')), ((2, 'a'), (3, 'a')), ((2, 'a'), (1, 'a')), ((2, 'a'),(2, 'b')), ((3, 'a'), (4, 'a')), ((4, 'd'), (4, 'c')), ((4, 'd'), (3, 'd')), ((1, 'd'), (2, 'd')), ((2, 'b'), (2, 'c')), ((4, 'b'), (4, 'c')), ((4, 'b'), (4, 'a')), ((2, 'c'), (2, 'd')), ((2, 'd'), (3, 'd'))]

""" Complement """
#Graphe complementaire
G1=nx.complement(G)
G1.nodes()
G1.edges()

""" Intersection de graphes """
# Les noeuds de H et G doivent etre les memes
H.clear()
H.add_nodes_from([1,2,3,4])
H.add_edge(1,2)
GH4=nx.intersection(G,H)
GH4.nodes()
#[1,2,3,4]
GH4.edges()
#[(1,2)]

""" Difference de graphes """
# Les noeuds de H et G doivent etre les memes
GH5=nx.difference(G,H)
GH5.nodes()
# [1,2,3,4]
GH5.edges()
# [((2,3),(3,4)]
# Retourne un graphe avec des aretes qui existent dans G mais pas dans H

""" Difference symetrique de graphes """

def test_mixed_type_intersection():
    G = nx.Graph()
    H = nx.MultiGraph()
    U = nx.intersection(G,H)

def similarityoftwograph(A,B):
	inter=nx.intersection(A,B)
	union=nx.union(A,B)
	return nx.number_of_nodes(inter)/nx.number_of_nodes(union)