def test_modularity_measure(function):

    def print_info(graph, name):
        print name, "N:", len(graph), "M:", graph.size()
        print "Q:", round(function(graph)[0], 3)

    graph = nx.read_gml(archive.extractfile("networks/karate-newman-1977.gml"))
    print_info(graph, "Karate")
    graph = nx.read_gml(archive.extractfile("networks/yeast_protein_interaction-barabasi-2001.tsv"))
    print_info(graph, "Protein Interaction")
    graph = pp.read_pajek(zipfile.ZipFile("networks/jazz.zip",
        "r").open("jazz.net"))
    print_info(graph, "Jazz musicians")
    graph = pp.read_pajek(zipfile.ZipFile("networks/celegans_metabolic.zip",
        "r").open("celegans_metabolic.net"))
    print_info(graph, "Metabolic")
    graph = nx.read_edgelist(zipfile.ZipFile("networks/email.zip",
        "r").open("email.txt"), data=False)
    print_info(graph, "E-mail")
    graph = pp.read_pajek(zipfile.ZipFile("networks/PGP.zip",
        "r").open("PGPgiantcompo.net"))
    print_info(graph, "Key signing")
    graph = nx.read_gml(zipfile.ZipFile("networks/cond-mat-2003.zip",
        "r").open("cond-mat-2003.gml"))
    print_info(graph, "Physicists")

	def __init__(self, ppi1filename, ppi2filename, matchfilename, outmatchfilename):
		self.ppi1 = nx.read_gml(ppi1filename, relabel = True)
		self.ppi2 = nx.read_gml(ppi2filename, relabel = True)
		in_to_node1 = {}
		in_to_node2 = {}
		for n1 in self.ppi1.nodes():
			in_to_node1[self.ppi1.node[n1]['index']] = n1
		for n2 in self.ppi2.nodes():
			in_to_node2[self.ppi2.node[n2]['index']] = n2

		matchfile = open(matchfilename)
		outmatchfile = open(outmatchfilename, "w")
		self.I = []
		for line in matchfile:
			if line[0] == "!":
				outmatchfile.write(line)
				continue
			cols = line.split()
			outmatchfile.write(in_to_node1[int(cols[0])] + " ")
			outmatchfile.write(in_to_node2[int(cols[1])] + "\n")
			self.I.append([in_to_node1[int(cols[0])], in_to_node2[int(cols[1])]])

		#check if it's a legal match
		for (i, j) in itertools.product(self.I, self.I):
			if i!= j:
				if (i[0] == j[0]) or (i[1] == j[1]):
					print "not a legal match: ", (i,j)
					return
		print "Legal match" 


		matchfile.close()
		outmatchfile.close()

def load_3(gml1,gml2,name):
	g1 = nx.read_gml(gml1)			
	g2 = nx.read_gml(gml2)
	
	q1 = qucik_hash(g1)
	q2 = qucik_hash(g2)
	
	if not q1:
		return 0
		
	if not q2:
		return 0
	
	v1 = q1[1]
	v2 = q2[1]
	s1 = q1[0]
	s2 = q2[0]
	
	if v1 == v2:
		#print "skip"
		return 0
	#print s1	
	#print s2
	
	to_write = []

	to_write.append(name)
	
	with open("result_openssl.txt", "a") as myfile:
		for item in to_write:
			myfile.write(item)
			myfile.write("\n")
	return 1

    def generateGraph(self, ticket, bnglContents, graphtype):
        print ticket
        pointer = tempfile.mkstemp(suffix='.bngl', text=True)
        with open(pointer[1], 'w') as f:
            f.write(bnglContents)
        try:
            if graphtype in ['regulatory', 'contactmap']:
                consoleCommands.setBngExecutable(bngDistro)
                consoleCommands.generateGraph(pointer[1], graphtype)
                name = pointer[1].split('.')[0].split('/')[-1]
                with open('{0}_{1}.gml'.format(name, graphtype), 'r') as f:
                    graphContent = f.read()

                gml = networkx.read_gml('{0}_{1}.gml'.format(name, graphtype))
                result = gml2cyjson(gml, graphtype=graphtype)
                jsonStr = json.dumps(result, indent=1, separators=(',', ': '))

                result = {'jsonStr': jsonStr, 'gmlStr': graphContent}
                self.addToDict(ticket, result)
                os.remove('{0}_{1}.gml'.format(name, graphtype))
                print 'success', ticket

            elif graphtype in ['sbgn_er']:
                consoleCommands.setBngExecutable(bngDistro)
                consoleCommands.generateGraph(pointer[1], 'contactmap')
                name = pointer[1].split('.')[0].split('/')[-1]
                # with open('{0}_{1}.gml'.format(name,'contactmap'),'r') as f:
                #   graphContent = f.read()
                graphContent = networkx.read_gml(
                    '{0}_{1}.gml'.format(name, 'contactmap'))
                sbgn = libsbgn.createSBNG_ER_gml(graphContent)
                self.addToDict(ticket, sbgn)
                os.remove('{0}_{1}.gml'.format(name, 'contactmap'))
                print 'success', ticket
            elif graphtype in ['std']:
                consoleCommands.setBngExecutable(bngDistro)
                consoleCommands.bngl2xml(pointer[1])
                xmlFileName = pointer[1].split('.')[0] + '.xml'
                xmlFileName = xmlFileName.split(os.sep)[-1]

                graph = stdgraph.generateSTDGML(xmlFileName)
                gmlGraph = networkx.generate_gml(graph)


                #os.remove('{0}.gml'.format(xmlFileName))
                result = gml2cyjson(graph, graphtype=graphtype)
                jsonStr = json.dumps(result, indent=1, separators=(',', ': '))

                result = {'jsonStr': jsonStr, 'gmlStr': ''.join(gmlGraph)}

                #self.addToDict(ticket, ''.join(gmlGraph))
                self.addToDict(ticket, result)
                print 'success', ticket
        except:
            import traceback
            traceback.print_exc()
            self.addToDict(ticket,-5)
            print 'failure',ticket
        finally:
            task.deferLater(reactor, 600,  freeQueue, ticket)

def ato_write_gml(graph, fileName, labelGraphics):
    def writeDict(gml, key, label, contents, space, labelGraphics=None):
        gml.write('{1}{0} [\n'.format(key, space))
        for subKey in contents:
            if type(contents[subKey]) in [str]:
                gml.write('{2}\t{0} "{1}"\n'.format(subKey, contents[subKey], space))
            elif type(contents[subKey]) in [int]:
                gml.write('{2}\t{0} {1}\n'.format(subKey, contents[subKey], space))
            elif type(contents[subKey]) in [dict]:
                writeDict(gml, subKey, subKey, contents[subKey], space + '\t')
            if labelGraphics and label in labelGraphics:
                for labelInstance in labelGraphics[label]:
                    writeDict(gml, 'LabelGraphics', 'LabelGraphics', labelInstance, space + '\t')
        gml.write('{0}]\n'.format(space))

    gml = StringIO.StringIO()
    gml.write('graph [\n')
    gml.write('\tdirected 1\n')
    for node in graph.node:

        writeDict(gml, 'node', node, graph.node[node], '\t', labelGraphics)

    flag = False
    for x in nx.generate_gml(graph):
        if 'edge' in x and not flag:
            flag = True
        if flag:
            gml.write(x + '\n')
            

    #gml.write(']\n')
    with open(fileName, 'w') as f:
        f.write(gml.getvalue())
    nx.read_gml(fileName)

def copy_layout(from_fname, to_fname):
    if not from_fname[-4:]  =='.gml': from_name +='.gml'
    if not to_fname[-4:]    =='.gml': to_name   +='.gml'

    print 'reading A=', from_fname,'..',
    g1 =  NX.read_gml(from_fname)
    labels1 = NX.get_node_attributes(g1, 'label')
    n1 = set(labels1.values())
    print len(n1),'nodes'
    
    print 'reading B=', to_fname,'..',
    g2 =    NX.read_gml(to_fname)
    labels2 = NX.get_node_attributes(g2, 'label')
    n2 = set(labels2.values())
    print len(n2),'nodes'

    intersection = len(n2.intersection(n1))
    percent=100.*intersection/len(n2)
    print 'B.intersect(A)=',intersection,'(%.1f%%)'%percent

    print 'copying layout..',
    mapping = {}
    for L1 in labels1:
        for L2 in labels2:
            if labels1[L1]==labels2[L2]:
                mapping[L1] = L2
                break

    layout = NX.get_node_attributes(g1, 'graphics')
    attr = dict([  (  mapping[ID],  {'x':layout[ID]['x'],'y':layout[ID]['y']}  )   for ID in mapping])
    
    NX.set_node_attributes(g2, 'graphics', attr)
    NX.write_gml(g2, to_fname)
    print 'done.'

def main():
	#extract_intra_function_cfg("C:\\Users\\Xu Zhengzi\\Desktop\\oh\\")
	cfg1 = nx.read_gml("C:\\Users\\Xu Zhengzi\\Desktop\\og\\dtls1_reassemble_fragment.gml")
	cfg2 = nx.read_gml("C:\\Users\\Xu Zhengzi\\Desktop\\oh\\dtls1_reassemble_fragment.gml")
	nodes1 = ['0x80c0b14', '0x80c0b9a', '0x80c0c3c', '0x80c0c57', '0x80c0c5d', '0x80c0c8c', '0x80c0ccc', '0x80c0d0a', '0x80c0d2c', '0x80c0e83', '0x80c0fb4', '0x80c0eb6', '0x80c0f53', '0x80c0b97', '0x80c0d88', '0x80c0de1', '0x80c0db5', '0x80c0fac', '0x80c0f73', '0x80c0dd9']
	extract_trace(cfg1, 3, nodes1)

	print "Finish"

def main():
    favorites_graph = nx.read_gml(FAVORITES_GML_OUTPUT_PATH)
    output_metrics(favorites_graph)
    favorites_graph = None

    comments_graph = nx.read_gml(COMMENTS_GML_OUTPUT_PATH)
    output_metrics(comments_graph)
    comments_graph = None

def read_graph(path):
    if path.endswith('.txt'):
        A = np.loadtxt(path)
        
        G = nx.from_numpy_matrix(A)
        return G

    if path.endswith('.gml'):
        A = nx.read_gml(path, 'label')
        return nx.read_gml(path, 'label')

def dolphins():
    """ Loads the dolphin social graph
    """
    try:
        gml_graph = nx.read_gml(DATA_PATH_1 + DOLPHINS)
    except:
        gml_graph = nx.read_gml(DATA_PATH_2 + DOLPHINS)
        
    dgraph = nx.Graph()
    dgraph.add_nodes_from(gml_graph.nodes(), size=1.)
    edges = gml_graph.edges()
    edges = [(u, v, {'weight': 1.}) for (u,v) in edges]
    dgraph.add_edges_from(edges)
    return dgraph

    def test_output(self):
        """
        test the output management function. should only output to file if an output
        format is given. otherwise output to console in adj list text.
        :return:
        """
        custom_filename = 'custom.out'

        try:
            yt_script.generate_output(self.MOCK_GRAPH, None, self.MOCK_FILE_OUTPUT)
            self.assertFalse(os.path.exists(self.MOCK_FILE_OUTPUT))
        except AttributeError:
            self.fail()

        try:
            yt_script.generate_output(self.MOCK_GRAPH, 'gml', self.MOCK_FILE_OUTPUT)
            result_graph = nx.read_gml(self.MOCK_FILE_OUTPUT)
            for node in self.MOCK_GRAPH.nodes():
                self.assertIn(node, result_graph.nodes())
            for edge in self.MOCK_GRAPH.edges():
                try:
                    self.assertIn(edge, result_graph.edges())
                except AssertionError:
                    edge = (edge[1], edge[0])
                    self.assertIn(edge, result_graph.edges())
                    continue
        except AttributeError:
            self.fail()

        try:
            yt_script.generate_output(self.MOCK_GRAPH, 'gml', custom_filename)
            result_graph = nx.read_gml(custom_filename)
            for node in self.MOCK_GRAPH.nodes():
                self.assertIn(node, result_graph.nodes())
            for edge in self.MOCK_GRAPH.edges():
                try:
                    self.assertIn(edge, result_graph.edges())
                except AssertionError:
                    edge = (edge[1], edge[0])
                    self.assertIn(edge, result_graph.edges())
                    continue
        except AttributeError:
            self.fail()

        self.assertRaises(RuntimeError, yt_script.generate_output,
                          self.MOCK_GRAPH, 'fake_format', custom_filename)

        if os.path.exists(custom_filename):
            os.remove(custom_filename)

def load(gml1,gml2,name):
	g1 = nx.read_gml(gml1)			
	g2 = nx.read_gml(gml2)	
	s1 = t(g1)
	s2 = t(g2)
	#print s1	
	#print s2
	
	with open("result.txt", "a") as myfile:
		myfile.write(name)
		myfile.write("\n") 
		
		m = lcs(s1,s2)
		
		index = find_index(m)
		
		
		match1 = []
		match2 = []
		
		for item in index:
		
			myfile.write(hex(s1[item[0]][0]) + " " + hex(s2[item[1]][0]))
			myfile.write("\n") 
		
			#print hex(s1[item[0]][0]) + " " + hex(s2[item[1]][0])
			match1.append(s1[item[0]][0])
			match2.append(s2[item[1]][0])
			
		myfile.write("o")
		myfile.write("\n") 	
		
		for item in s1:
			if item[0] not in match1:
				#print hex(item[0])
				myfile.write(hex(item[0]))
				myfile.write("\n") 
				
		myfile.write("p")
		myfile.write("\n") 
		
		for item in s2:
			if item[0] not in match2:
				#print hex(item[0])
				myfile.write(hex(item[0]))
				myfile.write("\n") 
				
		#print 	
	return 0

def graph_product(G_file):
    
    #TODO: take in a graph (eg when called from graphml) rather than re-reading the graph again
    LOG.info("Applying graph product to %s" % G_file)
    H_graphs = {}
    try:
        G = nx.read_graphml(G_file).to_undirected()
    except IOError:
        G = nx.read_gml(G_file).to_undirected()
        return
    G = remove_yed_edge_id(G)
    G = remove_gml_node_id(G)
#Note: copy=True causes problems if relabelling with same node name -> loses node data
    G = nx.relabel_nodes(G, dict((n, data.get('label', n)) for n, data in G.nodes(data=True)))
    G_path = os.path.split(G_file)[0]
    H_labels  = defaultdict(list)
    for n, data in G.nodes(data=True):
        H_labels[data.get("H")].append(n)

    for label in H_labels.keys():
        try:
            H_file = os.path.join(G_path, "%s.graphml" % label)
            H = nx.read_graphml(H_file).to_undirected()
        except IOError:
            try:
                H_file = os.path.join(G_path, "%s.gml" % label)
                H = nx.read_gml(H_file).to_undirected()
            except IOError:
                LOG.warn("Unable to read H_graph %s, used on nodes %s" % (H_file, ", ".join(H_labels[label])))
                return
        root_nodes = [n for n in H if H.node[n].get("root")]
        if len(root_nodes):
# some nodes have root set
            non_root_nodes = set(H.nodes()) - set(root_nodes)
            H.add_nodes_from( (n, dict(root=False)) for n in non_root_nodes)
        H = remove_yed_edge_id(H)
        H = remove_gml_node_id(H)
        nx.relabel_nodes(H, dict((n, data.get('label', n)) for n, data in H.nodes(data=True)), copy=False)
        H_graphs[label] = H

    G_out = nx.Graph()
    G_out.add_nodes_from(node_list(G, H_graphs))
    G_out.add_nodes_from(propagate_node_attributes(G, H_graphs, G_out.nodes()))
    G_out.add_edges_from(intra_pop_links(G, H_graphs))
    G_out.add_edges_from(inter_pop_links(G, H_graphs))
    G_out.add_edges_from(propagate_edge_attributes(G, H_graphs, G_out.edges()))
#TODO: need to set default ASN, etc?
    return G_out

def main():
  G = nx.read_gml(filename, relabel=False)
  power_law_est(G)
  #power_law_est_igraph(filename)
  max_degrees(G)
  max_bcentrality(G)
  max_pagerank(G)

def loadNetwork(f, ext):
  if ext == "gml":
    try:
      return nx.read_gml(f)
    except Exception, e:
      print("Couldn't load " + f + " as gml.")
      return False

def main():
    graph = nx.read_gml("../data/network.gml")

    nodes = [{
        "id": data['id'],
        "name": data.get("name") or "(Null)",
        "group": data['group'],
        "x": data["graphics"]["x"],
        "y": data["graphics"]["y"],
        "w": data["graphics"]["w"],
        "h": data["graphics"]["h"],
        "weight": data["weight"],
        "fixed": True,
    } for _, data in graph.nodes(data=True)]

    links = [{
        "source": get_node_index(nodes, source),
        "target": get_node_index(nodes, target),
        "name": data["label"],
        "value": data["value"]
    } for source, target, data in graph.edges(data=True)]

    json.dump({
        "nodes": nodes,
        "links": links
    }, open("../data/network.json", "w"), indent=4)

    def _read_cell_graph(self, filename, format):
        """Load the cell-to-cell connectivity graph from a
        file. 

        Returns None if any error happens.
        """
        cell_graph = None
        if filename:
            try:
                start = datetime.now()
                if format == "gml":
                    cell_graph = nx.read_gml(filename)
                elif format == "pickle":
                    cell_graph = nx.read_gpickle(filename)
                elif format == "edgelist":
                    cell_graph = nx.read_edgelist(filename)
                elif format == "yaml":
                    cell_graph = nx.read_yaml(filename)
                elif format == "graphml":
                    cell_graph = cell_graph = nx.read_graphml(filename)
                else:
                    print "Unrecognized format:", format
                end = datetime.now()
                delta = end - start
                config.BENCHMARK_LOGGER.info(
                    "Read cell_graph from file %s of format %s in %g s"
                    % (filename, format, delta.seconds + 1e-6 * delta.microseconds)
                )
            except Exception, e:
                print e

    def _read_celltype_graph(self, celltypes_file, format="gml"):
        """
        Read celltype-celltype connectivity graph from file.

        celltypes_file -- the path of the file containing
        the graph.
        
        format -- format of the file. allowed values: gml, graphml, edgelist, pickle, yaml.

        """
        start = datetime.now()
        celltype_graph = None
        try:
            if format == "gml":
                celltype_graph = nx.read_gml(celltypes_file)
            elif format == "edgelist":
                celltype_graph = nx.read_edgelist(celltypes_file)
            elif format == "graphml":
                celltype_graph = nx.read_graphml(celltypes_file)
            elif format == "pickle":
                celltype_graph = nx.read_gpickle(celltypes_file)
            elif format == "yaml":
                celltype_graph = nx.read_yaml(celltypes_file)
            else:
                print "Unrecognized format %s" % (format)
        except Exception, e:
            print e

def copy_layout_GML2NX(Fname, Graph, verbose=1):
    if not Fname[-4:]=='.gml': Fname+='.gml'
    print 'Copying layout from', Fname+'..'
    
    g1 =  NX.read_gml( Fname )
    labels1 = NX.get_node_attributes(g1, 'label')
    n1 = set(labels1.values())
    
    nodes = set( Graph.nodes() )

    if not n1:
        print '   empty layout graph'
        return
    if not nodes:
        print '   empty target graph'
        return

    mapping = {}
    for L1 in labels1:
        for name in nodes:
            if labels1[L1]==name:
                mapping[L1] = name
                break

    intersection = len(nodes.intersection(n1))
    percent=100.*intersection/len(nodes)
    print '   %.1f%%'%percent,'(%i positions)'%intersection

    layout = NX.get_node_attributes(g1, 'graphics')
    attr = dict([  (  mapping[ID],  {'x':layout[ID]['x'],'y':layout[ID]['y']}  )   for ID in mapping])
    
    NX.set_node_attributes( Graph, 'graphics', attr)

def usufyToGmlExport(d, fPath):
    '''
        Workaround to export to a gml file.
        :param d: Data to export.
        :param fPath: File path.
    '''
    # Reading the previous gml file      
    try:
        oldData=nx.read_gml(fPath)
    except UnicodeDecodeError as e:
        print "UnicodeDecodeError:\t" + str(e)
        print "Something went wrong when reading the .gml file relating to the decoding of UNICODE."
        import time as time
        fPath+="_" +str(time.time()) 
        print "To avoid losing data, the output file will be renamed to use the timestamp as:\n" + fPath + "_" + str(time.time()) 
        print        
        # No information has been recovered
        oldData = nx.Graph()
    except Exception as e:
        # No information has been recovered
        oldData = nx.Graph()
    newGraph = _generateGraphData(d, oldData)

    # Writing the gml file
    nx.write_gml(newGraph,fPath)