def setUp(self):

        self.T1 = self.graph()

        self.T2 = self.graph()
        self.T2.add_node(1)

        self.T3 = self.graph()
        self.T3.add_nodes_from(range(5))
        edges = [(i,i+1) for i in range(4)]
        self.T3.add_edges_from(edges)

        self.T5 = self.multigraph()
        self.T5.add_nodes_from(range(5))
        edges = [(i,i+1) for i in range(4)]
        self.T5.add_edges_from(edges)

        self.T6 = self.graph()
        self.T6.add_nodes_from([6,7])
        self.T6.add_edge(6,7)

        self.F1 = nx.compose(self.T6, self.T3)

        self.N4 = self.graph()
        self.N4.add_node(1)
        self.N4.add_edge(1,1)

        self.N5 = self.graph()
        self.N5.add_nodes_from(range(5))

        self.N6 = self.graph()
        self.N6.add_nodes_from(range(3))
        self.N6.add_edges_from([(0,1),(1,2),(2,0)])

        self.NF1 = nx.compose(self.T6,self.N6)

def load_semantic_network():
	# load several files into a single nx graph
	S = load_file_to_graph("../ontologies/stuff_ontology.txt")
	A = load_file_to_graph("../ontologies/attribute_ontology.txt")
	C = load_file_to_graph("../ontologies/context_knowledge.txt")
	X = load_file_to_graph("../ontologies/activity_ontology.txt")
	
	G = nx.compose(S,A)
	G = nx.compose(G,C)
	G = nx.compose(G,X)
	return G

def load_semantic_network():
	# load several files into a single nx graph
	filePath = os.path.dirname(os.path.abspath(__file__))
	S = load_file_to_graph(filePath +"/ontologies/stuff_ontology.txt")
	A = load_file_to_graph(filePath + "/ontologies/attribute_ontology.txt")
	C = load_file_to_graph(filePath + "/ontologies/context_knowledge.txt")
	X = load_file_to_graph(filePath + "/ontologies/activity_ontology.txt")
	
	G = nx.compose(S,A)
	G = nx.compose(G,C)
	G = nx.compose(G,X)
	return G

    def outputGraph(self, filename, _filter=None):
        if filename not in self._graphTime:
            self._graphTime[filename] = 0

        if (time.time() - self._graphTime[filename]) > 10:
            # print 'pre-Update Graph: %s' % filename
            G = nx.DiGraph()
            plt.clf()
            for edge in self._edges:
                if _filter is None:
                    G.add_edge(edge[0], edge[1])
                elif _filter(edge[0]) or _filter(edge[1]):
                    G.add_edge(edge[0], edge[1])

            try:
                G1 = dfs_tree(G, u"0015")
                G2 = dfs_tree(G, u"0013")
                G3 = nx.compose(G1, G2)
                G4 = dfs_tree(G, u"0017")
                G = nx.compose(G3, G4)
            except:
                pass

            relabel = {}
            newToOld = {}
            for n in G.nodes():
                if n in self._berths and self._berths[n] is not None:
                    relabel[n] = self._berths[n]
                    newToOld[self._berths[n]] = n
            nx.relabel_nodes(G, relabel, False)

            colours = []
            for n in G.nodes():
                if n in newToOld:
                    n = newToOld[n]
                if n in self._berths and self._berths[n] is not None:
                    colours.append("r")
                else:
                    colours.append("g")

            pos = nx.graphviz_layout(G, prog="dot")

            nx.draw_networkx_nodes(G, pos, node_color=colours, node_shape="s", node_size=900)
            nx.draw_networkx_edges(G, pos)
            nx.draw_networkx_labels(G, pos)

            fig = matplotlib.pyplot.gcf()
            fig.set_size_inches(16.0, 25.0)
            plt.axis("off")

            self.outputFile(plt, filename)

            self._graphTime[filename] = time.time()

def snowball_round(G,seeds,myspace=False):
    """Function takes a base graph, and a list of seeds
    and builds out the network data by accessing the
    Google SocialGraph API."""
    t0=time()
    if myspace:
        seeds=get_myspace_url(seeds)
    sb_data=[]
    for s in range(0,len(seeds)):
        s_sg=get_sg(seeds[s])
        new_ego,pen=create_egonet(s_sg) # Create ego net of seed
        # Compose new network data into old abse graph
        for p in pen:
                sb_data.append(p)
        if s<1:
            sb_net=nx.compose(G,new_ego)
        else:
            sb_net=nx.compose(new_ego,sb_net)
        del new_ego
        if s==round(len(seeds)*0.2):
        # Simple progress output, useful for long jobs
            sb_net.name='20% complete'
            nx.info(sb_net)
            print 'AT: '+strftime('%m/%d/%Y, %H:%M:%S', gmtime())
            print ''
        if s==round(len(seeds)*0.4):
            sb_net.name='40% complete'
            nx.info(sb_net)
            print 'AT: '+strftime('%m/%d/%Y, %H:%M:%S', gmtime())
            print ''
        if s==round(len(seeds)*0.6):
            sb_net.name='60% complete'
            nx.info(sb_net)
            print 'AT: '+strftime('%m/%d/%Y, %H:%M:%S', gmtime())
            print ''
        if s==round(len(seeds)*0.8):
            sb_net.name='80% complete'
            nx.info(sb_net)
            print 'AT: '+strftime('%m/%d/%Y, %H:%M:%S', gmtime())
            print ''
        if s==len(seeds)-1:
            print 'NEW NETWORK COMPLETE!'
            print 'AT: '+strftime('%m/%d/%Y, %H:%M:%S', gmtime())
            sb_net.name=G.name+'--> '
    # Return newly discovered seeds
    sb_data=array(sb_data)
    sb_data.flatten()
    sb_data=unique(sb_data)
    nx.info(sb_net)
    return sb_net,sb_data

def main():
    '''
    This is the main function
    http://networkx.lanl.gov/reference/algorithms.operators.html
    '''    
    # Get distance matrices
    walking_times = read_weights_from_file(walking_time_filename)  
    shuttle_times = read_weights_from_file(shuttle_time_filename)
    shuttle_connection_times = read_weights_from_file(shuttle_connection_time_filename)
    outdoorness_matrix = read_weights_from_file(outdoorness_filename)
    #print outdoorness_matrix
    
    # Add penalties
    shuttle_connection_times = apply_penalty(shuttle_connection_times, shuttle_penalty/2, 'add') # /2 because we get in and out the shuttle, so we don't want to have a double penalty
    walking_times = apply_penalty(walking_times, walking_penalty , 'multiply') 
    walking_times = apply_outdoor_penalty(walking_times, outdoorness_matrix, outdoorness_penalty)
    
    # Create subgraphs
    walking_graph = nx.DiGraph(data=walking_times)
    #print G.edges(data=True)
    walking_graph = nx.relabel_nodes(walking_graph,convert_list_to_dict(read_node_labels(walking_time_filename)))    
    print 'walking_graph', walking_graph.edges(data=True)
    
    shuttle_graph = nx.DiGraph(data=shuttle_times)
    shuttle_graph = nx.relabel_nodes(shuttle_graph,convert_list_to_dict(read_node_labels(shuttle_time_filename)))
    print 'shuttle_graph', shuttle_graph.edges(data=True)
    
    shuttle_connection_graph = nx.DiGraph(data=shuttle_connection_times)
    shuttle_connection_graph = nx.relabel_nodes(shuttle_connection_graph,convert_list_to_dict(read_node_labels(shuttle_connection_time_filename)))
    print 'shuttle_connection_graph', shuttle_connection_graph.edges(data=True)
    
    # Create main graph
    main_graph = nx.compose(walking_graph, shuttle_graph)
    print 'main_graph', main_graph.edges(data=True)    
    main_graph = nx.compose(main_graph, shuttle_connection_graph)
    print 'main_graph', main_graph.edges(data=True)
    
    # Compute the shortest paths and path lengths between nodes in the graph.
    # http://networkx.lanl.gov/reference/algorithms.shortest_paths.html
    compute_shortest_path(main_graph, '32', 'NW86')
    compute_shortest_path(main_graph, 'W7', 'W20')
    compute_shortest_path(main_graph, '50', '35')
    #print nx.dijkstra_predecessor_and_distance(main_graph, 'NW86')
    
    # Compute shortest paths and lengths in a weighted graph G. TODO: Return farthest region.
    print nx.single_source_dijkstra(main_graph, '32', 'NW86')
    
    # Compute KSP (k-shortest paths) using https://github.com/Pent00/YenKSP
    yenksp_digraph = convert_nx_digraph_into_yenksp_digraph(main_graph)
    print ksp_yen(yenksp_digraph, 'NW86', '32', 2)

def test_compose_multigraph():
    G = nx.MultiGraph()
    G.add_edge(1, 2, key=0)
    G.add_edge(1, 2, key=1)
    H = nx.MultiGraph()
    H.add_edge(3, 4, key=0)
    H.add_edge(3, 4, key=1)
    GH = nx.compose(G, H)
    assert_equal(set(GH), set(G) | set(H))
    assert_equal(set(GH.edges(keys=True)), set(G.edges(keys=True)) | set(H.edges(keys=True)))
    H.add_edge(1, 2, key=2)
    GH = nx.compose(G, H)
    assert_equal(set(GH), set(G) | set(H))
    assert_equal(set(GH.edges(keys=True)), set(G.edges(keys=True)) | set(H.edges(keys=True)))

    def graph(self):
        graph = nx.DiGraph()
        # Link all antecedents to me by decomposing
        #  FuzzyVariableTermAggregate down to just FuzzyVariableTerms
        for t in self.antecedent_terms:
            assert isinstance(t, FuzzyVariableTerm)
            graph.add_path([t, self])
            graph = nx.compose(graph, t.parent_variable.graph)

        # Link all consequents from me
        for c in self.consequent:
            assert isinstance(c, WeightedConsequent)
            graph.add_path([self, c.term])
            graph = nx.compose(graph, c.term.parent_variable.graph)
        return graph

 def search(self,concept):
     global G, mentioned_concepts
     new_subgraph = nx.DiGraph()
     # ('ConceptuallyRelatedTo',1), ('AtLocation',2), ('DerivedFrom', 1)
     for relation, lim in [('IsA',3), ('PartOf', 2),('HasContext', 2)]:
         for node in mentioned_concepts:
             json_document = json.dumps(cnet.search(rel=relation, start=node, end=concept, limit=lim))
             decoder = json.JSONDecoder()
             json_obj = decoder.decode(json_document)
             new_subgraph = nx.compose(new_subgraph,self.parse_json_to_graph(json_obj, start=node, end=concept))
             json_document = json.dumps(cnet.search(rel=relation,start=concept, end=node, limit=lim))
             decoder = json.JSONDecoder()
             json_obj = decoder.decode(json_document)
             new_subgraph = nx.compose(new_subgraph, self.parse_json_to_graph(json_obj, start=concept, end=node))
     G = nx.compose(G,new_subgraph)    

def graph_from_set(df):
    """
    The co-ocurrence graph for a set of tweets is the composition of the individual
    complete k-graphs, for each tweet. In other words, each tweet in the set forms
    a k-clique of the composed graph, and cliques are connected when distinct tweets
    have at least one hashtag in common.

    Each already existing node/hashtag that is seen in a new tweet will take on the
    timestamp of the new tweet containing it.

    Parameters
    ----------
    df : Pandas DataFrame
        to extract tweet info from, usually within a time window.

    Return
    ------
    G : NetworkX Graph
        composition graph on all tweets' hashtags in df
    """

    G = nx.Graph(time=df.time.max())  # initialize empty graph with latest timestamp

    for i in df.itertuples():
        tw_no, tags, time = i

        if len(tags) < 2:  # skip tweets with no hashtag co-occurrence
            continue
        H = graph_from_tweet(df, tw_no)  # current tweet's complete k-graph
        G = nx.compose(G, H)  # add new edges and nodes found in H not already in G
    return G

def combine_graph(Gs, opts):
    # combine the graphs in the list Gs
    G = Gs[0]
    for i in range(1,len(Gs)):
        G = nx.compose(G, Gs[i])

    # position of each nodes
    pos = nx.spring_layout(G) # Fruchterman-Reingold force-directed algorithm.

    # plot nodes and edges separately
    for i in range(len(Gs)):
        nodes = Gs[i].nodes()
        edges = Gs[i].edges()
        opt = opts[i]
        nx.draw_networkx_nodes(G, pos, nodelist = nodes, 
                               node_color = opt['node_color'], 
                               alpha = float(opt['node_alpha']), 
                               node_size = int(opt['node_size']))
        nx.draw_networkx_edges(G, pos, edgelist = edges, 
                               edge_color = opt['edge_color'], 
                               alpha = float(opt['edge_alpha']), 
                               width = int(opt['edge_width']))
    # label the nodes
    nx.draw_networkx_labels(G, pos)
    plt.show()

    def update_graph(self, list_solutions):
        
        ''' update__graph
            Parameters:
            list_solutions: A list of paths returned by different ants
            A path is a list of NODES (not node indexes)
            Given a list of solutions (list of paths), updates the global graph.
            
            Return:
            Returns a list of graphs of the solutions
        '''
        list_graphs_return = list()
        
        for solution in list_solutions:
            # [[(1080243414620259090, {'node': <aconode.ACONode instance at 0x2c713b0>, 'initial': True, 'solution': False}), (16212338162585125650L, {'node': <aconode.ACONode instance at 0x2c71368>}), (17225648078743487250L, {'node': <aconode.ACONode instance at 0x2c71878>}), (17270683387822424850L, {'node': <aconode.ACONode instance at 0x2c718c0>}), (17270672049108763410L, {'node': <aconode.ACONode instance at 0x2c71908>}), (16189824631214261010L, {'node': <aconode.ACONode instance at 0x2c71950>}), (1057729883249394450, {'node': <aconode.ACONode instance at 0x2c71998>}), (14892576832299025170L, {'node': <aconode.ACONode instance at 0x2c719e0>}), (14892717567639896850L, {'node': <aconode.ACONode instance at 0x2c71a28>}), (14892717569401504530L, {'node': <aconode.ACONode instance at 0x2c71a70>}), (14892717569451835410L, {'node': <aconode.ACONode instance at 0x2c71ab8>}), (14892717569451820050L, {'node': <aconode.ACONode instance at 0x2c71b00>}), (14892717567572800530L, {'node': <aconode.ACONode instance at 0x2c71b48>}), (14892717568327775250L, {'node': <aconode.ACONode instance at 0x2c71b90>}), (14892717568422147090L, {'node': <aconode.ACONode instance at 0x2c71bd8>}), (14892716812519437330L, {'node': <aconode.ACONode instance at 0x2c71c20>}), (14847681503440499730L, {'node': <aconode.ACONode instance at 0x2c71c68>}), (13901925581692695570L, {'node': <aconode.ACONode instance at 0x2c71cb0>}), (14982772999587197970L, {'node': <aconode.ACONode instance at 0x2c71cf8>}), (14982779596556301330L, {'node': <aconode.ACONode instance at 0x2c71d40>}), (14982779595801326610L, {'node': <aconode.ACONode instance at 0x2c71d88>}), (14982779597680346130L, {'node': <aconode.ACONode instance at 0x2c71dd0>}), (14982779597680361490L, {'node': <aconode.ACONode instance at 0x2c71e18>}), (14982779597630030610L, {'node': <aconode.ACONode instance at 0x2c71e60>}), (14982779597803045650L, {'node': <aconode.ACONode instance at 0x2c71ea8>}), (14982779597804094210L, {'node': <aconode.ACONode instance at 0x2c71ef0>}), (14982779597804094240L, {'node': <aconode.ACONode instance at 0x2c71f38>}), (14982779597803766565L, {'node': <aconode.ACONode instance at 0x2c71f80>}), (14982779559149650725L, {'node': <aconode.ACONode instance at 0x2c71fc8>}), (14982778914904556325L, {'node': <aconode.ACONode instance at 0x2c72050>}), (14982772730151650085L, {'node': <aconode.ACONode instance at 0x2c72098>}), (14982784824595006245L, {'node': <aconode.ACONode instance at 0x2c720e0>}), (14982784824645337125L, {'node': <aconode.ACONode instance at 0x2c72128>}), (14982784824645321765L, {'node': <aconode.ACONode instance at 0x2c72170>}), (14982784822766302245L, {'node': <aconode.ACONode instance at 0x2c721b8>}), (14982784823521276965L, {'node': <aconode.ACONode instance at 0x2c72200>}), (14982784823588384805L, {'node': <aconode.ACONode instance at 0x2c72248>}), (14982784823588357925L, {'node': <aconode.ACONode instance at 0x2c72290>}), (14982784822783063845L, {'node': <aconode.ACONode instance at 0x2c722d8>}), (14982784823789696805L, {'node': <aconode.ACONode instance at 0x2c72320>}), (14982784823907135525L, {'node': <aconode.ACONode instance at 0x2c72368>}), (14982784823907136005L, {'node': <aconode.ACONode instance at 0x2c723b0>}), (14982784823906087445L, {'node': <aconode.ACONode instance at 0x2c723f8>}), (14982784411595518485L, {'node': <aconode.ACONode instance at 0x2c72440>}), (14982785055840612885L, {'node': <aconode.ACONode instance at 0x2c72488>}), (14982785094494728725L, {'node': <aconode.ACONode instance at 0x2c724d0>}), (14982785094488830485L, {'node': <aconode.ACONode instance at 0x2c72518>}), (14982784407304548885L, {'node': <aconode.ACONode instance at 0x2c72560>}), (14919734974594036245L, {'node': <aconode.ACONode instance at 0x2c725a8>}), (14974622595052614165L, {'node': <aconode.ACONode instance at 0x2c725f0>}), (14977155831188304405L, {'node': <aconode.ACONode instance at 0x2c72638>}), (14977154929245172245L, {'node': <aconode.ACONode instance at 0x2c72680>}), (14977155616429453845L, {'node': <aconode.ACONode instance at 0x2c726c8>}), (14977155616435352085L, {'node': <aconode.ACONode instance at 0x2c72710>}), (14977155616435679760L, {'node': <aconode.ACONode instance at 0x2c72758>}), (14977155616435679745L, {'node': <aconode.ACONode instance at 0x2c727a0>}), (14977155616435679265L, {'node': <aconode.ACONode instance at 0x2c727e8>}), (14977155616435667745L, {'node': <aconode.ACONode instance at 0x2c72830>}), (14977155615361942305L, {'node': <aconode.ACONode instance at 0x2c72878>}), (14977155617123549985L, {'node': <aconode.ACONode instance at 0x2c728c0>}), (14977155617173880865L, {'node': <aconode.ACONode instance at 0x2c72908>}), (14977155617173865505L, {'node': <aconode.ACONode instance at 0x2c72950>}), (14977155615294845985L, {'node': <aconode.ACONode instance at 0x2c72998>}), (14977155616049820705L, {'node': <aconode.ACONode instance at 0x2c729e0>}), (14977155616144192545L, {'node': <aconode.ACONode instance at 0x2c72a28>}), (14977155616146289665L, {'node': <aconode.ACONode instance at 0x2c72a70>}), (14977155616146288705L, {'node': <aconode.ACONode instance at 0x2c72ab8>}), (14977155616146261825L, {'node': <aconode.ACONode instance at 0x2c72b00>}), (14977155615340967745L, {'node': <aconode.ACONode instance at 0x2c72b48>}), (14977155616850917185L, {'node': <aconode.ACONode instance at 0x2c72b90>}), (14977155616968355905L, {'node': <aconode.ACONode instance at 0x2c72bd8>}), (14977155616968344385L, {'node': <aconode.ACONode instance at 0x2c72c20>}), (14977155615357756225L, {'node': <aconode.ACONode instance at 0x2c72c68>}), (14977155617119363905L, {'node': <aconode.ACONode instance at 0x2c72cb0>}), (14977155617169694785L, {'node': <aconode.ACONode instance at 0x2c72cf8>}), (14977155617169671745L, {'node': <aconode.ACONode instance at 0x2c72d40>}), (14977155615290652225L, {'node': <aconode.ACONode instance at 0x2c72dd0>}), (14977155616045626945L, {'node': <aconode.ACONode instance at 0x2c72ea8>}), (14977155616146288705L, {'node': <aconode.ACONode instance at 0x2c72ab8>}), (14977155616146289665L, {'node': <aconode.ACONode instance at 0x2c72a70>}), (14977155616144192545L, {'node': <aconode.ACONode instance at 0x2c72a28>}), (14977155616049820705L, {'node': <aconode.ACONode instance at 0x2c729e0>}), (14977155615294845985L, {'node': <aconode.ACONode instance at 0x2c72998>}), (14977155617173865505L, {'node': <aconode.ACONode instance at 0x2c72950>}), (14977155617173880865L, {'node': <aconode.ACONode instance at 0x2c72908>}), (14977155617123549985L, {'node': <aconode.ACONode instance at 0x2c728c0>}), (14977155615361942305L, {'node': <aconode.ACONode instance at 0x2c72878>}), (14977155616435667745L, {'node': <aconode.ACONode instance at 0x2c72830>}), (14977155616435679265L, {'node': <aconode.ACONode instance at 0x2c727e8>}), (14977155616435679745L, {'node': <aconode.ACONode instance at 0x2c727a0>}), (14977155616429388385L, {'node': <aconode.ACONode instance at 0x2c74368>}), (14977154929245106785L, {'node': <aconode.ACONode instance at 0x2c74488>}), (14977155831188238945L, {'node': <aconode.ACONode instance at 0x2c745a8>}), (14974622595052548705L, {'node': <aconode.ACONode instance at 0x2c746c8>}), (14919734974593970785L, {'node': <aconode.ACONode instance at 0x2c747e8>}), (14982784407304483425L, {'node': <aconode.ACONode instance at 0x2c74908>}), (14982785094488765025L, {'node': <aconode.ACONode instance at 0x2c74a28>}), (14982785094495056385L, {'node': <aconode.ACONode instance at 0x2c74b48>}), (14982785094495055905L, {'node': <aconode.ACONode instance at 0x2c74c68>}), (14982785094495044385L, {'node': <aconode.ACONode instance at 0x2c74d88>}), (14982785093421318945L, {'node': <aconode.ACONode instance at 0x2c74ea8>}), (14982644358080447265L, {'node': <aconode.ACONode instance at 0x2c74fc8>}), (1147797409030816545, {'node': <aconode.ACONode instance at 0x2c77128>}), (1147797409030816545, {'node': <aconode.ACONode instance at 0x2c77128>})]]
            #print ("Solution "+ str(solution))
            g = nx.Graph()
            g.add_nodes_from(solution)
            #print("graph generated: "+ str(g.node))
            g.add_path([s[0] for s in solution])
            
            self.graph = nx.compose(self.graph, g) # self.graph edges have preference over g
            list_graphs_return.append(g)
        
            #print ("Update graph len nodes(self.graph): " + str(len(self.graph.nodes())))
            #print ("Update graph len edges(self.graph): " + str(len(self.graph.edges())))
            
            i = 0
            for l in list_graphs_return:
                #print ("Update graph len nodes ("+str(i) + "): " + str(len(l.nodes())))
                #print ("Update graph len edges ("+str(i) + "): " + str(len(l.edges())))
                i += 1

        return list_graphs_return

def show_nca(name1, name2, levels=0):
	nca_list=nca(name1, name2)
	G=json_graph.load(open("static/local_instance.json"))
	H=nx.DiGraph()
	for each in nca_list:
		anc_path=nx.compose(color_path(each[0],'green'),color_path(each[1],'yellow'))
		H=nx.compose(H,anc_path)

	for i in range(levels):
		H=expand_graph(H)

	for each in nca_list:
		H.node[each[0][0]]['color']='red' #color the nca different

	data=json_graph.dumps(H)
	return data

def total_overlap(network1, network2, d="directed"):
    """Returns value of total overlap measure for
    two given 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
    -------
    t_overlap : float
    """
    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)

    overlap = 0
    for i in g1.edges():
        if g2.has_edge(i[0], i[1]):
            overlap += 1

    t_overlap = (float(overlap) / float(nx.compose(g1, g2).number_of_edges()))

    return t_overlap

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 recomputeAllSourcesDag(self, all_dag, new_ridx_dag):
        """
        Given the initial all_routers_dag, and the new chosen ridxDag, we compute
        the newly created all_routers_dag merging the previous one while forcing the
        new ridxDag.
        """
        # Add 'flag' in new ridx dag
        edges = new_ridx_dag.edges()
        ridx_dag = nx.DiGraph()
        ridx_dag.add_edges_from(edges, flag=True)
        
        # Compose it with all_dag
        new_adag = nx.compose(all_dag, ridx_dag)

        # Iterate new ridx nodes. Remove those outgoing edges from the same node 
        # in all_dag that do not have 'flag'.
        final_all_dag = new_adag.copy()

        # Get edges to remove
        edges_to_remove = [(x, y) for node in new_ridx_dag.nodes() for
                           (x, y, data) in new_adag.edges(data=True)
                           if node == x and not data.get('flag')]

        # Remove them
        final_all_dag.remove_edges_from(edges_to_remove)
        
        # Return modified all_dag
        return final_all_dag

def construct_RankTh(fCorr, ffMRI):
    #
    # a function to generate rank-based thresholding networks
    #
    #
    # some parameters
    Target_d = [3, 4, 5, 6, 8, 10, 15, 20, 30]
    # Output directory is relative to fCorr directory
    CorrDir, fCorrMat = os.path.split(fCorr)
    BaseDir, CorrDirName = os.path.split(CorrDir)
    OutBase = os.path.join(BaseDir, 'Adjlist')
    if not os.path.exists(OutBase):
        os.makedirs(OutBase)
    OutDir = os.path.join(OutBase, 'Network_RankTh')
    if not os.path.exists(OutDir):
        os.makedirs(OutDir)
    # loading the correlation matrix
    R, NodeInd = NetUtil.load_corrmat_sparse(fCorr, ffMRI)
    # loop for generating rank-th networks
    for iTh in range(len(Target_d)):
        print "Generating a network with threshold d=" + str(Target_d[iTh])
        # generating the network
        if iTh==0:
            G, trR = NetUtil.net_builder_RankTh(R, NodeInd, Target_d[iTh])
            R = [] # releasing the memory
        else:
            # just generate the difference between the previous threshold.
            # then combine the resulting graphs
            deltaG, trR = NetUtil.net_builder_RankTh(trR, NodeInd, 
                                                Target_d[iTh]-Target_d[iTh-1])
            G = nx.compose(G, deltaG)
        # saving the network
        fNetFile = "Network_d" + str(Target_d[iTh]) + ".adjlist"
        fNet = os.path.join(OutDir,fNetFile)
        nx.write_adjlist(G, fNet)

def compose_all(graphs, name=None):
    """Return a new graph, the composition of supplied graphs

    Composition is the simple union of the node sets and edge sets.
    The node sets of the supplied graphs need not be disjoint.

    Parameters
    ----------
    graphs : list of graphs
       Multiple NetworkX graphs

    name : string
       Specify name for new graph

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

    Notes
    -----
    A new graph is returned, of the same class as the first graph in the list.
    It is recommended that the supplied graphs be either all directed or all
    undirected.  If a graph attribute is present in multiple graphs,
    then the first graph in the graphs_list with that attribute takes
    priority for that attribute
    """
    C = graphs.pop(0)
    for H in graphs:
        C = nx.compose(C, H, name=name)
    return C

def msp_associated_graph(BG,N,projection_layer=0):
    bg_graph = nx.Graph();
    for i in range(projection_layer*N,(projection_layer+1)*N):
        nei = BG.neighbors(i);
        k = nx.relabel_nodes(nx.complete_graph(len(nei)),dict(zip(range(len(nei)), nei)));
        bg_graph = nx.compose(bg_graph,k);
    return bg_graph;

 def dumpjson_graph(self):
     assert self.COMM.rank==0        
     import json
     import networkx as nx
     from networkx.readwrite import json_graph
     h=self.h
     #import pickle
     #json_graph.node_link_graph
     #Create a whole network of both transmitter types.
     self.global_whole_net=nx.compose(self.global_ecg, self.global_icg)
     self.global_whole_net.remove_nodes_from(nx.isolates(self.global_whole_net))
     self.global_icg.remove_nodes_from(nx.isolates(self.global_icg))
     self.global_ecg.remove_nodes_from(nx.isolates(self.global_ecg))
     
     d =[]
     whole=nx.to_numpy_matrix(self.global_whole_net)  
     #TODO sort whole (network) here in Python, as Python is arguably easier to understand than JS. 
     d.append(whole.tolist()) 
     #d.append(self.global_whole_net.tolist())
     #d.append(json_graph.node_link_data(self.global_whole_net))                 
     d.append(self.global_namedict)
     json.dump(d, open('web/js/global_whole_network.json','w'))
     d=json.load(open('web/js/global_whole_network.json','r'))
     #read the object just to prove that is readable.
     d=None #destroy the object.    
     print('Wrote JSON data to web/js/network.json')
 
     print('Wrote node-link JSON data to web/js/network.json')