def disjoint_union(G,H):
    """ Return the disjoint union of graphs G and H,
    forcing distinct integer node labels.

    Parameters
    ----------
    G,H : graph
       A NetworkX graph

    Returns
    -------
    U : A union graph with the same type as G.

    Notes
    -----
    A new graph is created, of the same class as G.  It is recommended
    that G and H be either both directed or both undirected.

    The nodes of G are relabeled 0 to len(G)-1, and the nodes of H are
    relabeld len(G) to len(G)+len(H)-1.
    """
    R1=nx.convert_node_labels_to_integers(G)
    R2=nx.convert_node_labels_to_integers(H,first_label=len(R1))
    R=union(R1,R2)
    R.name="disjoint_union( %s, %s )"%(G.name,H.name)
    return R

    def setUp(self):
        # G is the example graph in Figure 1 from Batagelj and
        # Zaversnik's paper titled An O(m) Algorithm for Cores
        # Decomposition of Networks, 2003,
        # http://arXiv.org/abs/cs/0310049.  With nodes labeled as
        # shown, the 3-core is given by nodes 1-8, the 2-core by nodes
        # 9-16, the 1-core by nodes 17-20 and node 21 is in the
        # 0-core.
        t1 = nx.convert_node_labels_to_integers(nx.tetrahedral_graph(), 1)
        t2 = nx.convert_node_labels_to_integers(t1, 5)
        G = nx.union(t1, t2)
        G.add_edges_from([(3, 7), (2, 11), (11, 5), (11, 12), (5, 12),
                          (12, 19), (12, 18), (3, 9), (7, 9), (7, 10),
                          (9, 10), (9, 20), (17, 13), (13, 14), (14, 15),
                          (15, 16), (16, 13)])
        G.add_node(21)
        self.G = G

        # Create the graph H resulting from the degree sequence
        # [0, 1, 2, 2, 2, 2, 3] when using the Havel-Hakimi algorithm.

        degseq = [0, 1, 2, 2, 2, 2, 3]
        H = nx.havel_hakimi_graph(degseq)
        mapping = {6: 0, 0: 1, 4: 3, 5: 6, 3: 4, 1: 2, 2: 5}
        self.H = nx.relabel_nodes(H, mapping)

def disjoint_union(G, H):
    """ Return the disjoint union of graphs G and H.

    This algorithm forces distinct integer node labels.

    Parameters
    ----------
    G,H : graph
       A NetworkX graph

    Returns
    -------
    U : A union graph with the same type as G.

    Notes
    -----
    A new graph is created, of the same class as G.  It is recommended
    that G and H be either both directed or both undirected.

    The nodes of G are relabeled 0 to len(G)-1, and the nodes of H are
    relabeled len(G) to len(G)+len(H)-1.

    Graph, edge, and node attributes are propagated from G and H
    to the union graph.  If a graph attribute is present in both
    G and H the value from H is used.
    """
    R1 = nx.convert_node_labels_to_integers(G)
    R2 = nx.convert_node_labels_to_integers(H, first_label=len(R1))
    R = union(R1, R2)
    R.graph.update(G.graph)
    R.graph.update(H.graph)
    return R

def null_model(version):
    net = nx.DiGraph(globals()["TRN"][version])
    flips = globals()["flip_num"]
    nx.convert_node_labels_to_integers(net, ordering="sorted",
            label_attribute="element")
    rewirer = NetworkRewiring()
    (rnd_net, flip_rate) = rewirer.randomise(net, flip=flips, copy=False)
    return (rnd_net, flip_rate)

def TheAlgorithm(G):
    dColor = Dcolor(G)
    partialColoring = list()
     
    #Compute chi(G) (using brute force)
    k = len(dColor.color())
    
    hasStrongStableSet = False
    thisStableSet = FindStrongStableSet(G)
    if thisStableSet != None:
        hasStrongStableSet = True
    while hasStrongStableSet:
        #thisStableSet = FindStrongStableSet(G)
        partialColoring.append(list(thisStableSet))
        #Remove this stable set from the graph
        for thisStableVertex in thisStableSet:
            G.remove_node(thisStableVertex)
            
        thisStableSet = FindStrongStableSet(G)
        if thisStableSet == None:
            hasStrongStableSet = False
              
    #check for induced C7
    graphToTest = convert_node_labels_to_integers(G, 0, ordering='default', label_attribute = None)
    if induced_subgraph(graphToTest, make_cycle(CYCLE_LENGTH)) == None:
        stillHasInducedC7 = False
    else:
        stillHasInducedC7 = True
    graphToTest.clear()
    
    while stillHasInducedC7 == True:
        thisStableSet = FindSimpleStableSet(G)
        partialColoring.append(thisStableSet)
        for thisStableVertex in thisStableSet:
            G.remove_node(thisStableVertex)
            
        graphToTest = convert_node_labels_to_integers(G, 0, ordering='default', label_attribute = None)
        if induced_subgraph(graphToTest, make_cycle(CYCLE_LENGTH)) == None:
            stillHasInducedC7 = False
        graphToTest.clear()
            
    """        
    At this point, there does not exist a strong stable set of size 3, because there is no C7.
    This means that G is now a perfect graph.
    """
    t = chromatic_number(G)
 
    #Find the chromatic number of our partial graph of stable sets
    s = len(partialColoring)
     
    if k == (s + t):
        result = True
    else:
        result = False

    return result

def generate_random_slice(slice_id,num_populations,edgeweight,max_x_coord,max_y_coord):
    """
    Generate a NetworkX graph object with num_populations nodes, located in random places around the coordinate
    represented by the centroid tuple, and cluster spread as variance.  Nodes are wired together in a complete
    graph.  All of the nodes belong to lineage #1 by default.

    :param num_populations:
    :param edgeweight:
    :param centroid_range_tuple:
    :param cluster_spread:
    :return:
    """
    g = nx.empty_graph(num_populations)
    start_node_id = (slice_id - 1) * num_populations
    log.debug("nodes labeled: %s", range(start_node_id, start_node_id + num_populations))
    nx.convert_node_labels_to_integers(g, start_node_id)

    for id in g.nodes():
        xcoord = 0.0
        ycoord = 0.0

        while (True):
            xcoord = np.random.random_integers(0, max_x_coord, size=1).astype(np.int64)[0]
            ycoord = np.random.random_integers(0, max_y_coord, size=1).astype(np.int64)[0]

            location = (int(xcoord), int(ycoord))
            if location not in location_cache:
                location_cache.add(location)
                break

        # log.debug("node %s at %s,%s",id,xcoord,ycoord)
        g.node[id]['xcoord'] = str(xcoord)
        g.node[id]['ycoord'] = str(ycoord)
        lab = "assemblage-"
        lab += str(xcoord)
        lab += "-"
        lab += str(ycoord)
        g.node[id]['label'] = lab
        g.node[id]['level'] = "None"
        g.node[id]['cluster_id'] = 1
        g.node[id]['lineage_id'] = 1
        g.node[id]['appears_in_slice'] = slice_id
        if slice_id == 1:
            g.node[id]['parent_node'] = 'initial'

    # now we wire up the edges in the slice
    assign_distance_weighted_edges_to_slice(g, max_x_coord,max_y_coord)

    assign_uniform_intracluster_weights(g, edgeweight)
    assign_node_distances(g)

    return g

def isomorphic(xmrs1, xmrs2):
    g1 = nx.convert_node_labels_to_integers(
        xmrs1._graph, label_attribute='node_label'
    )
    g2 = nx.convert_node_labels_to_integers(
        xmrs2._graph, label_attribute='node_label'
    )
    return nx.is_isomorphic(
        g1,
        g2,
        node_match=xmrs_node_match,
        edge_match=xmrs_edge_match
    )

    def importGexf(self, url ):

        # TODO once files are stored in a standard upload directory this will need to be changed
        import platform
        if platform.system() == 'Windows':
            PATH = 'c:\\inetpub\\wwwroot\\pydev\\systemshock\\modellingengine\\fincat\\parameters\\'
        else:
            PATH = '/var/lib/geonode/src/GeoNodePy/geonode/modellingengine/fincat/parameters/'

        G = nx.read_gexf(PATH + url)

        # ensure the nodes are labelled with integers starting from 0
        # TODO might need to start from current number of nodes in G
        G = nx.convert_node_labels_to_integers(G, first_label=0)

        for node in G.nodes(data=True):
            nodeid = node[0] #node array index 0 is the node id, index 1 is the attribute list
            attributes = node[1]
            attributes['guid'] = nodeid
            if 'wkt' in attributes:
                attributes['geometry'] = self.WKTtoGeoJSON(attributes['wkt'])

        for edge in G.edges(data=True):
            edgeid = unicode(edge[0]) + '-' + unicode(edge[1])
            attributes = edge[2]
            attributes['guid'] = edgeid

        self.layergraphs.append(G)  # add the new layer graph to the overall network
        return True

def load_shp(shp_path):
    """ loads a shapefile into a networkx based GeoGraph object

    Args:
        shp_path:  string path to a line or point shapefile

    Returns:
        geograph:  GeoGraph

    """

    # NOTE:  if shp_path is unicode io doesn't work for some reason
    shp_path = shp_path.encode('ascii', 'ignore')
    g = nx.read_shp(shp_path)
    coords = dict(enumerate(g.nodes()))

    driver = ogr.GetDriverByName('ESRI Shapefile')
    shp = driver.Open(shp_path)
    layer = shp.GetLayer()

    spatial_ref = layer.GetSpatialRef()
    proj4 = None
    if not spatial_ref:
        if gm.is_in_lon_lat(coords):
            proj4 = gm.PROJ4_LATLONG
        else:
            warnings.warn("Spatial Reference could not be set for {}".
                format(shp_path))

    else:
        proj4 = spatial_ref.ExportToProj4()

    g = nx.convert_node_labels_to_integers(g)

    return GeoGraph(srs=proj4, coords=coords, data=g)

def main(args):
    """
    Entry point.
    """
    if len(args) != 2:
        sys.exit(__doc__ %{"script_name" : args[0].split("/")[-1]})

    # Load the simulation parameters.
    params = json.load((open(args[1], "r")))
    network_params = params["network_params"]

    # Setup the network.
    G = networkx.read_graphml(network_params["args"]["path"])
    G = networkx.convert_node_labels_to_integers(G)

    # Load the attack sequences.
    fname = network_params["args"]["path"].replace(".graphml", ".pkl")
    attack_sequences = pickle.load(open(fname, "rb"))

    # Carry out the requested number of trials of the disease dynamics and 
    # compute basic statistics of the results.
    Sm, Im, Rm = numpy.array([0.0]), numpy.array([0.0]), numpy.array([0.0])
    for t in range(1, params["trials"] + 1):
        S, I, R = single_trial(G, params, attack_sequences)
        Sm, S = extend(Sm, S)
        Im, I = extend(Im, I)
        Rm, R = extend(Rm, R)
        Sm += (S - Sm) / t
        Im += (I - Im) / t
        Rm += (R - Rm) / t

    # Print the averaged results to STDOUT.
    for i in range(len(Sm)):
        print "%.3f\t%.3f\t%.3f" %(Sm[i], Im[i], Rm[i])

    def save_graph(self, graphname, fmt='edgelist'):
        """
        Saves the graph to disk

        **Positional Arguments:**

                graphname:
                    - Filename for the graph

        **Optional Arguments:**

                fmt:
                    - Output graph format
        """
        self.g.graph['ecount'] = nx.number_of_edges(self.g)
        g = nx.convert_node_labels_to_integers(self.g, first_label=1)
        if fmt == 'edgelist':
            nx.write_weighted_edgelist(g, graphname, encoding='utf-8')
        elif fmt == 'gpickle':
            nx.write_gpickle(g, graphname)
        elif fmt == 'graphml':
            nx.write_graphml(g, graphname)
        else:
            raise ValueError('edgelist, gpickle, and graphml currently supported')
        pass

def main(args):
    """
    Entry point.
    """
    if len(args) == 0:
        print "Usage: python disease.py <params file>"
        sys.exit(1)

    # Load the simulation parameters.
    params = json.load((open(args[0], "r")))
    network_params = params["network_params"]

    # Setup the network.
    if network_params["name"] == "read_graphml":
        G = networkx.read_graphml(network_params["args"]["path"])
        G = networkx.convert_node_labels_to_integers(G)
    else:
        G = getattr(networkx, network_params["name"])(**network_params["args"])

    # Carry out the requested number of trials of the disease dynamics and 
    # average the results.
    Sm, Im, Rm, Rv = 0.0, 0.0, 0.0, 0.0
    for t in range(1, params["trials"] + 1):
        S, I, R = single_trial(G, params)
        Rm_prev = Rm
        Sm += (S - Sm) / t
        Im += (I - Im) / t
        Rm += (R - Rm) / t
        Rv += (R - Rm) * (R - Rm_prev)

    # Print the average
    print("%.3f\t%.3f\t%.3f\t%.3f" \
          %(Sm, Im, Rm, (Rv / params["trials"]) ** 0.5))

def mergenodes(a,b):
    global G
    
    #Iterate through haplotypes on second node
    for key, value in G.node[b]['hap'].items():
        #If haplotype exists in dictionary of node a. Add weight to dictionary
        if key in G.node[a]['hap']:
            G.node[a]['hap'][key] += value
        #Otherwise add key and value to dictionary of node a
        else:
            G.node[a]['hap'].update({key:value})

    #Move all incoming edges of b to a
    for i in G.in_edges(b, data=True, keys=True):
        G.add_edge(i[0],a,a=i[3]['a'],weight=i[3]['weight'])
        G.remove_edge(i[0],i[1],key=i[2])

    #Remove node b form G
    G.remove_node(b)
        
    #Remove node from gl
    for i in gl:
        if b <= i:
            gl[gl.index(i)] = gl[gl.index(i)] - 1

    #Relablel nodes so that they are consecutive integers
    G = nx.convert_node_labels_to_integers(G, first_label=1, ordering="sorted")

 def plot_celltype_graph_3d(self, filename="celltypes_graph_3d.png"):
     """Some eyecandi useful for presentations."""
     if not has_mayavi:
         return
     numeric_graph = nx.convert_node_labels_to_integers(self.__celltype_graph)
     pos = nx.spring_layout(numeric_graph, dim=3)
     xyz = numpy.array([pos[v] for v in numeric_graph])
     scalars = [self.__celltype_graph.node[vertex]["count"] for vertex in self.__celltype_graph]
     fig = mlab.figure(1, bgcolor=(0, 0, 0))
     mlab.clf()
     points = mlab.points3d(
         xyz[:, 0],
         xyz[:, 1],
         xyz[:, 2],
         scalars,
         scale_factor=0.1,
         scale_mode="none",
         colormap="summer",
         opacity=0.4,
         transparent=True,
         resolution=20,
     )
     points.mlab_source.dataset.lines = numpy.array(numeric_graph.edges())
     points.mlab_source.update()
     # mlab.pipeline.surface(points, color=(1,1,1),
     #                       representation='wireframe',
     #                       line_width=2,
     #                       name='synapses')
     tube = mlab.pipeline.tube(points, tube_radius=0.01)
     mlab.pipeline.surface(tube, color=(0.8, 0.8, 0.8))
     mlab.savefig(filename, size=(1280, 800), figure=fig)
     print "Mayavi celltype graph saved in", filename
     mlab.show()

def main(args):
    """
    Entry point.
    """
    if len(args) != 2:
        sys.exit(__doc__ %{"script_name" : args[0].split("/")[-1]})

    # Load the simulation parameters.
    params = json.load((open(args[1], "r")))
    network_params = params["network_params"]

    # Setup the network.
    G = networkx.read_graphml(network_params["args"]["path"])
    G = networkx.convert_node_labels_to_integers(G)

    # Load the attack sequences.
    fname = network_params["args"]["path"].replace(".graphml", ".pkl")
    attack_sequences = pickle.load(open(fname, "rb"))
    
    # Carry out the requested number of trials of the disease dynamics and 
    # average the results.
    Sm, Im, Rm, Rv = 0.0, 0.0, 0.0, 0.0
    for t in range(1, params["trials"] + 1):
        S, I, R = single_trial(G, params, attack_sequences)
        Rm_prev = Rm
        Sm += (S - Sm) / t
        Im += (I - Im) / t
        Rm += (R - Rm) / t
        Rv += (R - Rm) * (R - Rm_prev)

    # Print the average
    print("%.3f\t%.3f\t%.3f\t%.3f" \
          %(Sm, Im, Rm, (Rv / params["trials"]) ** 0.5))

def main():
    # First half of the script calculates the partitions, and the metric used
    # to identify good candidate partitions for using in the exploded view; 
    # the ratio of extern tie-internal ties/total network edges
    
    # G=NX.generators.barabasi_albert_graph(550,2)
    G=NX.read_edgelist('test_network.edgelist',create_using=NX.Graph())
    G=NX.convert_node_labels_to_integers(G,first_label=0) # for consistent record keeping
    partitions=generate_network_clusters(G)
    external,internal,ei_ratio=external_internal_ties(G,partitions)
    # Plot E-I ratio and save
    P.plot(ei_ratio.values(),ls='-',marker='.',color='r')
    P.savefig('ei_plot.png')
    #P.show()
    #P.savefig('ei_plot.png',dpi=100)
    # Looking for large jumps in graph, thoes will be candidate partitions
    time.sleep(10)
    # Once the candidate partitions have been identified, we use UbiGraph to 
    # display exploded view
    S=open_ubigraph_server()    # Open connection to XML-RPC UbiGraph Server
    edges=build_ubigraph(G,S)         # Build network in UbiGraph
    time.sleep(20)
    edge_ref,external_edges=exploded_view(G,S,edges,partitions[20],repulsion=0.20738) # Choose partition and display 'exploded view'
    time.sleep(20)
    rebuild(S,edge_ref,external_edges)

def draw_tree(H):  # plots a graph H with it's different spanning trees
    G=NX.convert_node_labels_to_integers(H)
    T1=generate_BFS_spanning_tree(G, 0)
    T2=generate_DFS_spanning_tree(G, 0)
    T3=make_random_spanning_tree(G)
    T4=makeNormalTree(G.size())
    
    global number_of_figs
    figure(number_of_figs)
    number_of_figs += 1
    
    P.subplot(2,3, 1)
    title("The graph")
    NX.draw(G, node_color='y', node_size=100)
    P.subplot(2,3, 2)
    title("BFS")
    NX.draw(T1, node_color='g', node_size=100)
    P.subplot(2,3, 3)
    title("DFS")
    NX.draw(T2, node_color='m', node_size=100)
    P.subplot(2,3, 4)
    title("Random")
    NX.draw(T3, node_color='m', node_size=100)
    P.subplot(2,3, 5)
    title("Normal")
    NX.draw(T4, node_color='y', node_size=150)

def generateGraphFunction(H):
    G = NX.convert_node_labels_to_integers(H)
    func = [0 for i in G.nodes()]
    which_used = 0
    if (generation_mode & __DFS == __DFS):
        which_used += 1
        for i in G.nodes():
            lf = generate_DFS_level_function(G, i)
            for j in range(len(lf)):
                func[j] += lf[j]
                
    if (generation_mode & __BFS == __BFS):
        which_used += 1
        for i in G.nodes():
            lf = generate_BFS_level_function(G, i)
            for j in range(len(lf)):
                func[j] += lf[j]

    if (generation_mode & __RANDOM == __RANDOM):
        which_used += 1
        for i in G.nodes():
            lf = generate_random_level_function(G)
            for j in range(len(lf)):
                func[j] += lf[j]

    if generation_mode == 0:
        ordr = float(which_used*G.order())
    else:
        ordr = float(G.order())
        
    for i in G.nodes():
        func[i] /= ordr

    return func

 def postprocess_transformer_out(graph):
     # 1. the original graph needs to be directed
     ograph = _edge_to_vertex_transform(graph.graph['original'])
     graph.graph['original'] = rna.expanded_rna_graph_to_digraph(ograph)
     # 2. our convention is, that node ids are not overlapping ,, complying by optimistic renaming..
     graph = nx.convert_node_labels_to_integers(graph,first_label=1000)
     return graph

def GenerateAllGraphsWithManyXNoY(xCardinalityUpperBound):

    t = range(1, xCardinalityUpperBound)
    graphConfigSet = set(set(product(set(t),repeat = CYCLE_LENGTH)))

    for thisGraphConfiguration in graphConfigSet:
        myGraph = ConstructBaseGraph()
        for thisSetIndex in range(0,CYCLE_LENGTH):
            if thisGraphConfiguration[thisSetIndex] >= 2:
                myGraph = AddXSet(myGraph, thisGraphConfiguration[thisSetIndex] - 1, False, thisSetIndex)
                       
        if not (GIsHFree(myGraph, FORBIDDEN_SUBGRAPHS)):
            print("ERROR!")
            f = File(DIRECTORY, G = myGraph, logger = MY_LOGGER, base="C5-")
            f.save()
            exit()
            
        result = TheAlgorithm(myGraph)
        
        if(result == True):
            print("Conjecture Holds.")
        else:
            print("Conjecture Fails!")
            G = convert_node_labels_to_integers(G, 0, ordering='default', label_attribute = None)
            f = File(DIRECTORY, G = myGraph, logger = MY_LOGGER, base="C5-")
            f.save()
            
        myGraph.clear()

    return