def graph_example_1():
    G = nx.convert_node_labels_to_integers(nx.grid_graph([5, 5]),
                                           label_attribute='labels')
    rlabels = nx.get_node_attributes(G, 'labels')
    labels = {v: k for k, v in rlabels.items()}

    for nodes in [(labels[(0, 0)], labels[(1, 0)]),
                  (labels[(0, 4)], labels[(1, 4)]),
                  (labels[(3, 0)], labels[(4, 0)]),
                  (labels[(3, 4)], labels[(4, 4)])]:
        new_node = G.order() + 1
        # Petersen graph is triconnected
        P = nx.petersen_graph()
        G = nx.disjoint_union(G, P)
        # Add two edges between the grid and P
        G.add_edge(new_node + 1, nodes[0])
        G.add_edge(new_node, nodes[1])
        # K5 is 4-connected
        K = nx.complete_graph(5)
        G = nx.disjoint_union(G, K)
        # Add three edges between P and K5
        G.add_edge(new_node + 2, new_node + 11)
        G.add_edge(new_node + 3, new_node + 12)
        G.add_edge(new_node + 4, new_node + 13)
        # Add another K5 sharing a node
        G = nx.disjoint_union(G, K)
        nbrs = G[new_node + 10]
        G.remove_node(new_node + 10)
        for nbr in nbrs:
            G.add_edge(new_node + 17, nbr)
        G.add_edge(new_node + 16, new_node + 5)

    G.name = 'Example graph for connectivity'
    return G

def test_white_harary_paper():
    # Figure 1b white and harary (2001)
    # http://eclectic.ss.uci.edu/~drwhite/sm-w23.PDF
    # A graph with high adhesion (edge connectivity) and low cohesion
    # (node connectivity)
    G = nx.disjoint_union(nx.complete_graph(4), nx.complete_graph(4))
    G.remove_node(7)
    for i in range(4, 7):
        G.add_edge(0, i)
    G = nx.disjoint_union(G, nx.complete_graph(4))
    G.remove_node(G.order() - 1)
    for i in range(7, 10):
        G.add_edge(0, i)
    for flow_func in flow_funcs:
        kwargs = dict(flow_func=flow_func)
        # edge cuts
        edge_cut = nx.minimum_edge_cut(G, **kwargs)
        assert_equal(3, len(edge_cut), msg=msg.format(flow_func.__name__))
        H = G.copy()
        H.remove_edges_from(edge_cut)
        assert_false(nx.is_connected(H), msg=msg.format(flow_func.__name__))
        # node cuts
        node_cut = nx.minimum_node_cut(G, **kwargs)
        assert_equal(set([0]), node_cut, msg=msg.format(flow_func.__name__))
        H = G.copy()
        H.remove_nodes_from(node_cut)
        assert_false(nx.is_connected(H), msg=msg.format(flow_func.__name__))

def atlas6():
    """ Return the atlas of all connected graphs of 6 nodes or less.
        Attempt to check for isomorphisms and remove.
    """

    Atlas = graph_atlas_g()[0:208]  # 208
    # remove isolated nodes, only connected graphs are left
    U = nx.Graph()  # graph for union of all graphs in atlas
    for G in Atlas:
        zerodegree = [n for n in G if G.degree(n) == 0]
        for n in zerodegree:
            G.remove_node(n)
        U = nx.disjoint_union(U, G)

    # list of graphs of all connected components
    C = nx.connected_component_subgraphs(U)

    UU = nx.Graph()
    # do quick isomorphic-like check, not a true isomorphism checker
    nlist = []  # list of nonisomorphic graphs
    for G in C:
        # check against all nonisomorphic graphs so far
        if not iso(G, nlist):
            nlist.append(G)
            UU = nx.disjoint_union(UU, G)  # union the nonisomorphic graphs
    return UU

def test_white_harary1():
    # Figure 1b white and harary (2001)
    # A graph with high adhesion (edge connectivity) and low cohesion
    # (node connectivity)
    G = nx.disjoint_union(nx.complete_graph(4), nx.complete_graph(4))
    G.remove_node(7)
    for i in range(4,7):
        G.add_edge(0,i)
    G = nx.disjoint_union(G, nx.complete_graph(4))
    G.remove_node(G.order()-1)
    for i in range(7,10):
        G.add_edge(0,i)
    assert_equal(1, approx.node_connectivity(G))

def test_white_harary_1():
    # Figure 1b white and harary (2001)
    # # http://eclectic.ss.uci.edu/~drwhite/sm-w23.PDF
    # A graph with high adhesion (edge connectivity) and low cohesion
    # (vertex connectivity)
    G = nx.disjoint_union(nx.complete_graph(4), nx.complete_graph(4))
    G.remove_node(7)
    for i in range(4,7):
        G.add_edge(0,i)
    G = nx.disjoint_union(G, nx.complete_graph(4))
    G.remove_node(G.order()-1)
    for i in range(7,10):
        G.add_edge(0,i)
    assert_equal(1, nx.node_connectivity(G))
    assert_equal(3, nx.edge_connectivity(G))

 def add_community(self, G, community):
     last_community = len(G.nodes())/self._household_size-1
     G=nx.disjoint_union(G, community)
     self.get_node_with_highest_degree(last_community, G)
     for i in range(last_community+1, last_community+len(community.nodes())/self._household_size+1):
         G.add_edge(self.get_random_node(last_community), self.get_random_node(i))
     return G

def patternsets2(MotifG1, MotifG2):
    #enumerate all possible permutations of node labels,
    #minimum is sharing one edge, all the way to max is the smaller number of edges, complexity 2^edgenum_max
    #return a set of possibly isomorphic collapses

    patternset = set()
    edgenum_max = min(MotifG1.number_of_edges(), MotifG2.number_of_edges())

    #select L (two+) edges to overlap
    for L in range(1, edgenum_max + 1):
        print L
        L_subsets = list(itertools.combinations(MotifG1.edges(),L))
        L_subsets2 = list(itertools.combinations(MotifG2.edges(),L))
        for subset1 in L_subsets:
            for subset2 in L_subsets2:
                print "already chose these" +str(L)+" edges in Motif2"
                print subset2
                permutations = list(itertools.permutations(subset1))
                i = 0
                for permutation in permutations:
                    print "this permutation is"
                    print permutation
                    print "in this particular order" + str(i)
                    if MotifG1 == MotifG2:
                        print "waring!!!same motif non-relabled"
                        G = nx.disjoint_union(MotifG1, MotifG2)
                    else:
                        G = nx.union(MotifG1, MotifG2)

                    if len(G) != 0:
                        G2 = nx.Graph()
                        G22 = nx.Graph()
                        Motif2merged_nodes = set()
                        for j in range(0, len(permutation)):
                            edge_1 = permutation[j]
                            edge_2 = subset2[j]
                            print "edge 1"
                            print edge_1
                            print "edge 2"
                            print edge_2

                            if edge_2[0] not in Motif2merged_nodes:
                                G1 = merge_nodes(G, edge_1[0], edge_2[0])
                                Motif2merged_nodes.add(edge_2[0])
                            if edge_2[1] not in Motif2merged_nodes:
                                G2 = merge_nodes(G1, edge_1[1], edge_2[1])
                                Motif2merged_nodes.add(edge_2[1])

                            if edge_2[0] not in Motif2merged_nodes:
                                G11 = merge_nodes(G, edge_1[1], edge_2[0])
                            if edge_2[1] not in Motif2merged_nodes:
                                G22 = merge_nodes(G11, edge_1[0], edge_2[1])

                        patternset.add(G2)
                        patternset.add(G22)
                        print G2.nodes()
                    i += 1


    return patternset

    def CreateInd(self,nbClusters, connectInter, connectIntra, pcExc, pcInh, nbNeuronByCluster, interRatio):
        """
        connectInter est la probabilite de connecter deux clusters entre eux
        connectIntra est une liste de probabilite de connection de neurones suivant leur type (pEE,pEI,pII,pIE)
        pcExc et pcInh sont le pourcentage de chaque type de neurones
        interRatio est le ratio de neurones-interface entre deux clusters (>1)
        """

        nbNeuronsInd = nbClusters * nbNeuronByCluster
        
        numNeuron = 0
        nbExc = int(pcExc * nbNeuronByCluster)
        lstNeuronsType = ([1] * nbExc  + [-1]*(nbNeuronByCluster - nbExc)) * nbClusters 
        lstNeuronToCluster = [y for y in range(nbClusters) for x in range(nbNeuronByCluster)]
        lstClusterToNeuron = [range(y*nbNeuronByCluster,(y+1)*nbNeuronByCluster) for y in range(nbClusters) ]
        lstInterfaceNeuron = [[],[],[],[]]  #Liste des neurones de chaque cluster connectes aux neurones d'autres clusters

        gphInd =  nx.MultiDiGraph()

        #Creation des clusters
        for numCluster in range(nbClusters):
            gphCluster = nx.MultiDiGraph()
            matrix = self.CreateConnectionMatrix(pcExc,pcInh,nbNeuronByCluster,connectIntra)
            #Parcourt de la matrice de connexion du cluster
            for ligne in range(nbNeuronByCluster):
                for col in range(nbNeuronByCluster):
                    gphCluster.add_edge(ligne+numNeuron , col+numNeuron,weight=matrix[ligne,col])

            #Permet la numerotation continue entre les clusters
            numNeuron+=nbNeuronByCluster
            #Rajoute le graphe du cluster (gphCluster) au graphe total (gphInd)
            gphInd=nx.disjoint_union(gphInd,gphCluster)
            gphCluster=nx.create_empty_copy(gphCluster)

        #Creation des connexions inter-cluster
        lstClusterConnection = self.CreateClusterConnection(connectInter,nbClusters)
        for numCluster in range(nbClusters):
            pcInter = int(nbNeuronByCluster /  interRatio)   #Nombre de neurones connectes entre deux clusters
            (preNeurones,postNeurones,weights) = self.CreateInterConnectionMatrix(numCluster,nbNeuronByCluster,lstClusterToNeuron,lstClusterConnection,pcInter,lstNeuronsType)
            for n in range(len(preNeurones)):
                gphInd.add_edge(preNeurones[n] , postNeurones[n] ,weight=weights[n])
                
         #Liste caracterisant les connexions inter-cluster
         #ligne 0 : numero de cluster des neurones pre-synaptiques
         #ligne 1 : numero des neurones pre-synaptiques
         #ligne 2 : numero de cluster des neurones post-synaptiques
         #ligne 3 : numero des neurones post-synaptiques
               
            lstInterfaceNeuron[0].extend([numCluster] * len(preNeurones))
            lstInterfaceNeuron[1].extend(preNeurones)       
            lstInterfaceNeuron[2].extend( [lstNeuronToCluster[x] for x in postNeurones] )   
            lstInterfaceNeuron[3].extend(postNeurones)
            
            
        #Stockage des valeurs de sortie dans des proprietes de la classe    
        self.graph = gphInd
        self.lstNeuronsType = lstNeuronsType
        self.lstNeuronToCluster = lstNeuronToCluster
        self.lstClusterToNeuron = lstClusterToNeuron
        self.lstInterfaceNeuron = lstInterfaceNeuron

def plot_clustered_graph(dist_matrix, labels=None):
    plt.close('all')
    plt.figure(1)
    plt.clf()
    n_clusters = max(labels) + 1
    print('n_clusters = {}'.format(n_clusters))
    g_g = nx.Graph()
    for k in range(0, n_clusters):
        class_members = labels == k
        class_dist = dist_matrix[class_members].T[class_members]
        g = nx.from_numpy_matrix(class_dist)
        g_g = nx.disjoint_union(g_g, g)

    # color nodes the same in each connected subgraph
    for g in nx.connected_component_subgraphs(g_g):
        c = [random.random()] * nx.number_of_nodes(g)  # random color...
        nx.draw(g,

                node_size=40,
                node_color=c,
                vmin=0.0,
                vmax=1.0,
                with_labels=False)
    plt.savefig("atlas.png", dpi=75)
    plt.show()

    def __setup_network_graph(self):
        structure = nx.disjoint_union(
            self.left_region.graph.structure,
            self.right_region.graph.structure
        )

        return sypy.CustomGraph(structure)

def disjoint_union_all(graphs):
    """Return the disjoint union of all graphs.

    This operation forces distinct integer node labels starting with 0
    for the first graph in the list and numbering consecutively.

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

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

    Notes
    -----
    It is recommended that the graphs be either all directed or all undirected.

    Graph, edge, and node attributes are propagated to the union graph.
    If a graph attribute is present in multiple graphs, then the value
    from the last graph in the list with that attribute is used.
    """
    graphs = iter(graphs)
    U = next(graphs)
    for H in graphs:
        U = nx.disjoint_union(U, H)
    return U

def string_to_networkx(header, sequence, **options):
    # defaults
    energy_range = options.get('energy_range', 10)
    max_num = options.get('max_num', 3)
    max_num_subopts = options.get('max_num_subopts', 100)
    split_components = options.get('split_components', False)
    seq_struct_list, energy_list = rnasubopt_wrapper(sequence, energy_range=energy_range, max_num=max_num, max_num_subopts=max_num_subopts)
    if split_components:
        for seq_struct, energy in zip(seq_struct_list, energy_list):
            G = sequence_dotbracket_to_graph(seq_info=sequence, seq_struct=seq_struct)
            G.graph['info'] = 'RNAsubopt energy=%s max_num=%s' % (energy, max_num)
            if G.number_of_nodes() < 2:
                G = seq_to_networkx(header, sequence, **options)
            G.graph['id'] = header
            G.graph['sequence'] = sequence
            G.graph['structure'] = seq_struct
            yield G
    else:
        G_global = nx.Graph()
        G_global.graph['id'] = header
        G_global.graph['info'] = 'RNAsubopt energy_range=%s max_num=%s' % (energy_range, max_num)
        G_global.graph['sequence'] = sequence
        for seq_struct in seq_struct_list:
            G = sequence_dotbracket_to_graph(seq_info=sequence, seq_struct=seq_struct)
            G_global = nx.disjoint_union(G_global, G)
        if G_global.number_of_nodes() < 2:
            G_global = seq_to_networkx(header, sequence, **options)
        yield G_global

    def random_pair_stitch(self, num_edges):
        left_nodes = self.left_region.graph.nodes()
        right_nodes = self.right_region.graph.nodes()

        if num_edges > len(left_nodes) * len(right_nodes):
            raise Exception("Too many edges to stitch")

        stitch = []
        while len(stitch) != num_edges:
            edge = (
                random.choice(left_nodes),
                random.choice(right_nodes)
            )
            if edge in stitch:
                continue
            stitch.append(edge)

        self.graph.structure = nx.disjoint_union(
            self.left_region.graph.structure,
            self.right_region.graph.structure
        )

        for (left_node, right_node) in stitch:
            edge = (left_node,
                len(left_nodes)+right_node
            )
            self.graph.structure.add_edges_from([edge])
            self.attack_edges.append(edge)

        self.known_honests = self.left_region.known_honests
        self.is_stitched = True

    def graph(self, nested=False):
        '''
        generate the graph that will be used for evaluation ( it will be vectorized by eden and then used
        in a machine learning scheme).

        Args:
            nested: bool
                the graph returned here is the union of graph minor and the base graph.
                nested decides wether there edges between nodes in the base graph and their
                representative in the graph minor. these edges have the attribute 'nested'.


        Returns:
            nx.graph
        '''
        g= nx.disjoint_union(self._base_graph, self.abstract_graph())
        node_id= len(g)

        if nested:
            for n,d in g.nodes(data=True):
                if 'contracted' in d and 'edge' not in d:
                    for e in d['contracted']:
                        if 'edge' not in g.node[e]:
                            # we want an edge from n to e
                            g.add_node(node_id,edge=True,label='e')
                            g.add_edge( n, node_id, nesting=True)
                            g.add_edge( node_id, e, nesting=True)
                            #g.add_edge( n, e, nesting=True)
                            node_id+=1

        return g

 def _string_to_networkx(self, header=None, sequence=None, constraint=None):
     seq_struct_list, energy_list = self._rnasubopt_wrapper(sequence)
     if self.split_components:
         for seq_struct, energy in zip(seq_struct_list, energy_list):
             graph = sequence_dotbracket_to_graph(header=header,
                                                  seq_info=sequence,
                                                  seq_struct=seq_struct)
             graph.graph['info'] = 'RNAsubopt energy=%s max_num=%s' % \
                 (energy, self.max_num)
             graph.graph['id'] = header
             graph.graph['sequence'] = sequence
             graph.graph['structure'] = seq_struct
             yield graph
     else:
         graph_global = nx.Graph()
         graph_global.graph['id'] = header
         graph_global.graph['info'] = \
             'RNAsubopt energy_range=%s max_num=%s' % \
             (self.energy_range, self.max_num)
         graph_global.graph['sequence'] = sequence
         for seq_struct in seq_struct_list:
             graph = sequence_dotbracket_to_graph(header=header,
                                                  seq_info=sequence,
                                                  seq_struct=seq_struct)
             graph_global = nx.disjoint_union(graph_global, graph)
         yield graph_global

def instance8_1000():
    """
    Returns a 3-element tuple (G,T,leaves) where G is the graph
    T is the optimal solution and leaves is the number of leaves
    in the optimal solution.
    
    The graph is constructed by creating 4 stars with 90 nodes and
    adding 10 random nodes.
    """
    
    #create a star of 4 stars
    starList = []
    
    for _ in range(0,6):
        starList.append(nx.heawood_graph())
    
    T = nx.Graph()
    for star in starList:
        T = nx.disjoint_union(T,star)
        
    T.add_node(84)
    T.add_edges_from([(84,0),(84,14),(84,28),(84,42),(84,56),(84,70)])
    
    #add 10 more nodes with random edges
    T.add_nodes_from(range(85,100))
    for i in range(85,100):
        x = int(random()*5371)%90
        T.add_edge(i,x)
        
    #count the number of leaves
    leaves = list(T.degree(T.nodes()).values()).count(1)
    
    #randomize the label of nodes
    n = range(100)
    new = range(100)

    r.shuffle(new)

    T = nx.relabel_nodes(T,dict(zip(n,new)))
        
    G = nx.Graph()
    G.add_nodes_from(T.nodes())
    G.add_edges_from(T.edges())

    # add random edges
    for i in range(1000):
        x = int(random()*15897)%100
        y = int(random()*17691)%100
        G.add_edge(G.nodes()[x],G.nodes()[y])

    for e in G.edges():
        if e[0] == e[1]:
            G.remove_edge(e[0],e[1])

    G = G.to_undirected()  
    #T = mlst.one_edge_swap(G)  
    
    T = nx.Graph()
    return (G,T)

def contraction(graphs=None,
                contraction_attribute='label',
                dont_contract_attribute_symbol=None,
                nesting=False,
                contraction_weight_scaling_factor=1,
                modifiers=modifiers,
                **options):
    '''
    modifiers: list of named tuples, each containing the keys: attribute_in, attribute_out and reduction.
    "attribute_in" identifies the node attribute that is extracted from all contracted nodes.
    "attribute_out" identifies the node attribute that is written in the resulting graph.
    "reduction" is one of the following reduction operations:
    1. histogram,
    2. sum,
    3. average,
    4. categorical,
    5. set_categorical.
    "histogram" returns a sparse vector with numerical hashed keys,
    "sum" and "average" cast the values into floats before computing the sum and average respectively,
    "categorical" returns the concatenation string of the lexicographically sorted list of input attributes,
    "set_categorical" returns the concatenation string of the lexicographically sorted set of input
    attributes.
    contraction_weight_scaling_factor: factor to multiply the weights of the contracted part
    '''
    for g in graphs:
        # check for 'position' attribute and add it if not present
        for i, (n, d) in enumerate(g.nodes_iter(data=True)):
            if d.get('position', None) is None:
                g.node[n]['position'] = i
        # compute contraction
        g_contracted = edge_contraction(graph=g, node_attribute=contraction_attribute,
                                        except_symbol=dont_contract_attribute_symbol)
        info = g_contracted.graph.get('info', '')
        g_contracted.graph['info'] = info + '\n' + serialize_modifiers(modifiers)
        for n, d in g_contracted.nodes_iter(data=True):
            # get list of contracted node ids
            contracted = d.get('contracted', None)
            if contracted is None:
                raise Exception('Empty contraction list for: id %d data: %s' % (n, d))
            for modifier in modifiers:
                modifier_func = contraction_modifer_map[modifier.reduction]
                g_contracted.node[n][modifier.attribute_out] = modifier_func(
                    input_attribute=modifier.attribute_in, graph=g, id_nodes=contracted)
                # rescale the weight of the contracted nodes
                if contraction_weight_scaling_factor != 1:
                    w = d.get('weight', 1)
                    w = w * contraction_weight_scaling_factor
                    g_contracted.node[n]['weight'] = w
        if nesting:  # add nesting edges between the constraction graph and the original graph
            g_nested = nx.disjoint_union(g, g_contracted)
            # rewire contracted graph to the original graph
            for n, d in g_nested.nodes_iter(data=True):
                contracted = d.get('contracted', None)
                if contracted:
                    for m in contracted:
                        g_nested.add_edge(n, m, label='.', len=1, nesting=True)
            yield g_nested
        else:
            yield g_contracted

    def test_is_planar_unions(self):
        try:
            from itertools import combinations,product
        except ImportError:
            raise SkipTest('itertools.combinations not found')

        for (G1,G2) in combinations(self.planar,2):
            G=nx.disjoint_union(G1,G2)
            assert_true(planarity.is_planar(G))

        for (G1,G2) in combinations(self.non_planar,2):
            G=nx.disjoint_union(G1,G2)
            assert_false(planarity.is_planar(G))

        for (G1,G2) in product(self.planar,self.non_planar):
            G=nx.disjoint_union(G1,G2)
            assert_false(planarity.is_planar(G))

def original_graph():
    romeos_family = nx.complete_graph(5)
    julias_family = nx.complete_graph(5)
    # The families clash <- aw, not good!
    family_fight = nx.disjoint_union(romeos_family, julias_family)
    # ... but Romeo and Julia make love nevertheless
    family_fight.add_edge(0, 9)
    return family_fight

    def get_json(self):

        # join together all layers in the network
        H = nx.DiGraph()
        for G in self.layergraphs:
            H = nx.disjoint_union(G, H)

        data = json_graph.node_link_data(H)
        return json.dumps(data)