def __init__(self, config, logger):
        self.config = config
        self.logger = logger

        self.logger.info('Creating Network')

        graph_type = self.config['graph']['type']
        self.logger.info('Creating {}'.format(graph_type))
        eval_str = '{}'.format(graph_type)
        self.logger.debug('eval: {}'. format(eval_str))
        self.graph = eval(eval_str)
        self.logger.debug('Type of self.graph: {}'.format(type(self.graph)))

        self.logger.info('Creating network from NetworkX Graph Generator')
        graph_generator = self.config['graph']['generator']
        self.logger.info('Graph Generator: {}'.format(graph_generator))
        eval_str = '{}'.format(graph_generator)
        self.logger.debug('eval: {}'.format(eval_str))
        network = eval(eval_str)
        self.logger.debug('Type of network: {}'.format(type(network)))
        self.nx_graph = network  # used to generate network using agent as nodes

        nx_edge_list_filename = self.config['graph']['nx_edge_list_filename']
        self.logger.info(
            'Writing networkx edge list: {}'.format(nx_edge_list_filename))
        nx.write_edgelist(network, nx_edge_list_filename)

def motifOrder(data,key,orderSize,motifSize,degree):			
	graphs = data[key]
	pattern = {}
	for G in graphs:
		#calculate threshold
		sortedWeights = np.sort(G,axis=None)
		threshold = sortedWeights[-len(G)*degree-1]
		#Output graph to txt file
		graph = nx.DiGraph(G>threshold)
		graph = nx.convert_node_labels_to_integers(graph,1)
		with open('result2/OUTPUT.txt','wb') as f:
			nx.write_edgelist(graph,f,data=False)
		#Jenky way to use c++ motif finder in python
		os.system("./fanmod_command_line_linux " +str(motifSize) + " 100000 1 result2/OUTPUT.txt 1 0 0 2 0 0 0 1 3 3 result2/MotifCount.txt 0 1")
		data = parseOutput("result2/MotifCount.txt")
		
		order = []
		for iD,total,percent in data:
			order.append((iD,total))
		keys = sorted(order,key=lambda x:-x[1])
		keys = [int(k[0]) for k in keys]
		pat = tuple(keys[:orderSize])
		pattern[pat] = pattern.setdefault(pat,0) + 1/float(len(graphs))
		
		
	total = sorted(pattern.items(), key = lambda x: -x[1])
	
	for key,value in total:
		print str(key)+": " + str(value)

def main():
    arg_parser = ArgumentParser(description='generate random tree')
    arg_parser.add_argument('--output', required=True,
                            help='output file name')
    arg_parser.add_argument('--branching', dest='max_branch', type=int,
                            default=3, help='maximum node branching')
    arg_parser.add_argument('--height', dest='max_height', type=int,
                            default=4, help='maximum tree height')
    arg_parser.add_argument('--seed', type=int, default=None,
                            help='seed for random number generator')
    arg_parser.add_argument('--delim', dest='delimiter', default=' ',
                            help='delimiter for edge list')
    arg_parser.add_argument('--no-data', action='store_true',
                            dest='no_data', help='show edge data')
    arg_parser.add_argument('--edge-list', action='store_true',
                            dest='edge_list',
                            help='generate edge list output')
    options = arg_parser.parse_args()
    random.seed(options.seed)
    tree = random_tree(options.max_branch, options.max_height)
    if options.edge_list:
        nx.write_edgelist(tree, options.output,
                          delimiter=options.delimiter,
                          data=not options.no_data)
    else:
        nx.write_graphml(tree, options.output)
    return 0

def find_shortest_paths(graph, out_filename, sources, targets, k_paths):
    """ Use pathlinker to find shortest paths

    Args:
        graph: a networkx graph
        out_filename: file to print paths to (is a temporary file)
        sources: a list of source nodes
        targets: a list of target nodes
        k_paths: number of shortest paths to find

    Returns:
        List of networkx graphs, which should be thought of as paths.
        If sources are not connect to targets, then returns empty list.
    """
    assert(k_paths > 0)
    edgelist_filename = out_filename + "edgelist.temp"
    srctgt_filename = out_filename + "srctgt.temp"
    nx.write_edgelist(graph, edgelist_filename)

    with open(srctgt_filename, 'w') as f:
        for node in graph.nodes():
            if node in sources:
                f.write(str(node) + '\tsource\n')
            elif node in targets:
                f.write(str(node) + '\ttarget\n')

    s = "python PathLinker/PathLinker.py {} {} -o {} --write-paths --k-param={}"\
            .format(edgelist_filename, srctgt_filename, out_filename, k_paths)
    try:
        os.system(s)
        return read_paths(out_filename + "k_100-paths.txt")
    except Exception as e:
        print(e)
        return []

def get_community_biconnections(commid, df, graph):

    print "Find biconnections in the community :", commid
    
    print nx.info(graph)

    biconnected_nodes = []
    for e in graph.edges():
        a, b = e
        if graph.has_edge(b,a) and a != b:
            # check if already there in the list
            if (a,b) in biconnected_nodes or (b,a) in biconnected_nodes:
                pass
            else:
                biconnected_nodes.append((a,b))

    print "number of biconnected edges:", len(biconnected_nodes)

    source_nodes, target_nodes = zip(*biconnected_nodes)
    all_subgraph_nodes = set(source_nodes).union(set(target_nodes))
    print "Unique nodes in the biconnections", len(all_subgraph_nodes)

    # get the subgraph of all biconnected edges 
    # plot 
    dfname = biconnbase+ str(commid) + '_biz_info.csv'
    bicon_df = df.loc[all_subgraph_nodes]
    print bicon_df.shape
    bicon_df.to_csv(dfname)

    # subgraph generated from the coordinates
    sgname = biconnbase+ str(commid) + '_sg_edgelist.ntx'
    sg = graph.subgraph(list(all_subgraph_nodes))
    print nx.info(sg)
    nx.write_edgelist(sg, sgname, data=False)

def permute_network( G, Q, numEdges, outputFile ):
    # Permutes network by swapping edges Q * numEdges times
    H = G.copy()
    nswap = Q*numEdges
    swaps = nx.connected_double_edge_swap(H, nswap=nswap)
    nx.write_edgelist(H, outputFile)
    return swaps

def filterNet(DG,mindegree=None,indegree=100,outdegree=50,outdegreemax=9999999,indegreemax=999999):
	print 'In filterNet'
	filter=[]
	for n in DG:
		if outdegreemax==None or DG.out_degree(n)<=outdegreemax:
			if mindegree!=None:
				if DG.degree(n)>=mindegree:
					filter.append(n)
			else:
				if indegree!=None:
					if DG.in_degree(n)>=indegree:
						filter.append(n)
				if outdegree!=None:
					if DG.out_degree(n)>=outdegree:
						filter.append(n)
	#the filter represents the intersect of the *degreesets
	#indegree and outdegree values are ignored if mindegree is set
	filter=set(filter)
	H=DG.subgraph(filter)
	#Superstitiously, perhaps, make sure we only grab nodes that project edges...
	filter= [n for n in H if H.degree(n)>0]
	L=H.subgraph(filter)
	print "Filter set:",filter
	print L.order(),L.size()
	L=labelGraph(L,filter)
	nx.write_graphml(L, projname+"/followersCommonFriends.graphml")
	nx.write_edgelist(L, projname+"/followersCommonFriends.txt",data=False)

def main(n_start, n_count=1, n_inc=1, c_in_start=10, c_in_count=1, c_in_inc=1, c_out_start=5, c_out_count=1, c_out_inc=1, comm_count = 2, DC=False, i=0):
    bp_uncertain = 'src/bp'

    edge_frac = 1.
    nonedge_mult = 5.
    b = 2
    trials = 2

    os.makedirs('out', exist_ok=True)
    os.makedirs('data', exist_ok=True)

    for n in custom_range(n_start, n_count, n_inc):
        for c_in in custom_range(c_in_start, c_in_count, c_in_inc):
            for c_out in custom_range(c_out_start, c_out_count, c_out_inc):
                original_net = 'data/original_net-%d-%f-%f-%f-%f-%f-%d.edges'%(n,c_in,c_out,b,edge_frac,nonedge_mult, i)
                uncertain_net = 'data/noisy_net-%d-%f-%f-%f-%f-%f-%d.edges'%(n,c_in,c_out,b,edge_frac,nonedge_mult, i)
                uncertain_comms = 'out/uncertain_comms-%d-%f-%f-%f-%f-%f-%d.out'%(n,c_in,c_out,b,edge_frac,nonedge_mult, i)
 
                print("making and fuzzing network")
                G_orig = make_net(c_in, c_out, n)
                write_edgelist(G_orig, original_net)
                G, _ = fuzz_network(G_orig, 1, b, edge_frac, nonedge_mult)
                write_weighted_edgelist(G, uncertain_net)
 
                start1 = time()
                print("running belief propagation")
                os.system('%s -i %s -o %s -c %d -l %d -n %d' % (bp_uncertain, uncertain_net, uncertain_comms, comm_count, 3, trials))
                end1 = time()

                with open('out/results.txt', 'a+') as out_file:
                    out_file.write("%d %f %f\t%f %f %f\t %f %f\t %s %d\n" %(n,
                                    c_in, c_out,
                                    b,edge_frac,nonedge_mult,
                                    evaluate(uncertain_comms, n), end1-start1,
                                    str(datetime.now()), i))

    def splitGraphs(self,labels):
        """
        split the graph into several subgraphs by labels
        """
       
        id_label = []

        ## load labels
        ## Node id start from 0
        fid = open('labels','r')
        for line in fid:
            field = line.strip()
            id_label.append(int(field))
        fid.close()
    
        ## calculate the number of different labels
        nodup_labels = set(id_label)
        K = len(nodup_labels)

        for i in range(0,K):
            f = open('subgraph_' + str(i) +'.sub','w')
            
            subG = []
            
            for j in range(0,len(id_label)):
                if id_label[j] == i:
                    subG.append(str(j))

            
            G = self.G.subgraph(subG)
            print nx.info(G)

            nx.write_edgelist(G,f)

def filterNet(DG,mindegree):
	if addUserFriendships==1:
		DG=addFocus(DG,user,typ)
	mindegree=int(mindegree)
	filter=[]
	filter= [n for n in DG if DG.degree(n)>=mindegree]
	H=DG.subgraph(filter)
	print "Filter set:",filter
	print H.order(),H.size()
	LH=labelGraph(H,filter)

	now = datetime.datetime.now()
	ts = now.strftime("_%Y-%m-%d-%H-%M-%S")
  
	nx.write_graphml(H, '/'.join([path,agent,typ,tt+"degree"+str(mindegree)+ts+".graphml"]))

	nx.write_edgelist(H, '/'.join([path,agent,typ,tt+"degree"+str(mindegree)+ts+".txt"]),data=False)
	#delimiter=''

	#indegree=sorted(nx.indegree(DG).values(),reverse=True)
	indegree=H.in_degree()
	outdegree=H.out_degree()

	inout = [indegree, outdegree]
	inoutpair = {}
	for k in indegree.iterkeys():
		inoutpair[k] = tuple(inoutpair[k] for inoutpair in inout)
    
	fig = plt.figure()
	ax = fig.add_subplot(111)
	#ax.plot(indegree,outdegree, 'o')
	#ax.set_title('Indegree vs outdegree')
	degree_sequence=sorted(indegree.values(),reverse=True)
	plt.loglog(degree_sequence)
	plt.savefig( '/'.join([path,agent,typ,tt+"degree"+str(mindegree)+"outdegree_histogram.png"]))

def post_processing_attack(G_min, out_file):    
    aG = nx.Graph()
    for e in G_min.edges_iter(data=True):
        if e[2]['p'] > 0.5:
            aG.add_edge(e[0], e[1])
            
    nx.write_edgelist(aG, out_file, '#', '\t', False, 'utf-8')

def aggregate_max(G, sigma, k, eps, c, q, filename):
    edge_dict = {}
    count = 0
    for u in G.nodes_iter():
        if G.degree(u) < 5:
            continue
        print "u =", u
        count += 1
        if count % 10 == 0:
            print "count =", count        
    
        sG, S1, S2 = get_subgraph(G, u)
        (eps_min, sG_min) = generate_obfuscation(sG, u, S1, S2, sigma, k, eps, c, q)
        
        for e in sG_min.edges_iter():
            v = e[0]
            w = e[1]
            if v > w:   # swap to normalize v < w
                v = e[1]
                w = e[0]
            if (v,w) not in edge_dict:
                edge_dict[(v,w)] = sG_min[v][w]['p']
            else:
                if edge_dict[(v,w)] < sG_min[v][w]['p']:
                    edge_dict[(v,w)] = sG_min[v][w]['p']    # max
    #
    aG = nx.Graph()
    for ((v,w),weight) in edge_dict.iteritems():
        aG.add_edge(v, w, {'p':weight})    
    #
    nx.write_edgelist(aG, filename, '#', '\t', data=['p'])

def run(args):
    """Permutes the given PPI network the specified number of times."""
    import sys, os
    # Load network
    G = load_network(args.network_edgelist)

    if args.verbose:
        print 'Input network has', len( G.edges() ), 'edges among', len(G.nodes()),
        print 'nodes.\nPerforming', len( G.edges() ) * args.Q, 'edge swaps.'

    # Make sure output directory exists
    os.system('mkdir -p ' + args.output_dir)

    # Permute network and output files
    for i in range(args.num_networks):
        if args.verbose:
            sys.stdout.write('+')
            sys.stdout.flush()

        # Permute graph and output as an edge list
        H = permute_network(G, args.Q)
        filename = args.output_dir + "/" + str(i + args.start_index) + ".txt"
        nx.write_edgelist(H, filename)

    if args.verbose: print

def run(output_path, graph_type, force,
        seed, num_nodes, edge_prob, solution_path):

    any_op_file_exists = (P.exists(output_path) or P.exists(solution_path))

    if any_op_file_exists and not force:
        print('Cannot overwrite without --force', file=sys.stderr)
        sys.exit(-1)

    g = None
    if graph_type == 'erdos':
        g = nx.erdos_renyi_graph(num_nodes, edge_prob,
                                 seed=seed, directed=True)
    else:
        print('Unknown graph type: ', graph_type, file=sys.stderr)
        sys.exit(-1)

    A = np.zeros((num_nodes, num_nodes), dtype='float')
    # All edges are given uniformly random weights.
    for u, v, d in g.edges(data=True):
        d['act_prob'] = R.random()
        A[u, v] = d['act_prob']

    nx.write_edgelist(g, output_path)
    np.savetxt(solution_path, A, delimiter=',')

    def start(self):
        for id in self.oidRootNamePairs:
            self.oidNamePairs,currIDs=Utils.getoidNames(self.oidNamePairs,id,Def.typ)
            Utils.report('Processing current IDs: '+str(currIDs))
            flip=(Def.typ=='fr')
            self.addDirectedEdges(id, currIDs,flip=flip)
            n=len(currIDs)
            Utils.report('Total amount of IDs: '+str(n))
            c=1
            for cid in currIDs:
                Utils.report('\tSub-level run: getting '+Def.typ2,str(c)+'of'+str(n)+Def.typ+cid)
                self.oidNamePairs,ccurrIDs=Utils.getoidNames(self.oidNamePairs,cid,Def.typ2)
                self.addDirectedEdges( cid, ccurrIDs)
                c=c+1
        for id in self.oidRootNamePairs:
            if id not in self.oidNamePairs:
                self.oidNamePairs[id]=self.oidRootNamePairs[id]
        self.labelNodes(self.oidNamePairs)
        Utils.report(nx.info(self.DG))

        now = datetime.datetime.now()
        timestamp = now.strftime("_%Y-%m-%d-%H-%M-%S")

        fname=UserID._name.replace(' ','_')
        nx.write_graphml(self.DG, '/'.join(['reports',fname+'_google'+Def.typ+'Friends_'+timestamp+".graphml"]))
        nx.write_edgelist(self.DG, '/'.join(['reports',fname+'_google'+Def.typ+'Friends_'+timestamp+".txt"]),data=False)

def save_object(obj, folder, obj_name, extension):
    """Saves object to a file with naming convention folder/obj_name.extension. File format depends on the extension."""
    filename = folder + '/' + obj_name + '.' + extension
    did_save = False
    try:
        print("\nSaving %s to '%s'..." % (obj_name, filename))
        if (extension == 'csv'):
            pd.DataFrame.to_csv(obj, filename, index = False)
            did_save = True
        elif (extension == 'pickle'):
            pickle.dump(obj, open(filename, 'wb'))
            did_save = True
        elif (extension == 'ig.edges'):
            ig.Graph.write_edgelist(obj, filename)
            did_save = True
        elif (extension == 'nx.edges'):
            nx.write_edgelist(obj, filename, data = False)
            did_save = True
        elif (extension == 'coo'):
            with open(filename, 'w') as f:
                f.write("%d " % obj.shape[0])
                if (obj.shape[1] != obj.shape[0]):
                    f.write("%d " % obj.shape[1])
                f.write('\n')
                for (row, col, val) in zip(obj.row, obj.col, obj.data):
                    f.write("%d %d %s\n" % (row, col, repr(val)))
            did_save = True
        if did_save:
            print("Successfully saved %s." % obj_name)
    except:
        pass
    if (not did_save):
        raise IOError("Failed to save %s to file." % obj_name)

def normalize_and_save_graph(G, new_file, node_map_file = None):
    newG = nx.Graph()
    
    min_id = min(G.nodes_iter())
    max_id = max(G.nodes_iter())
    print "min_id =", min_id
    print "max_id =", max_id
    
    i = 0
    id_dict = {}    # dict for node ids
    for u in G.nodes_iter():
        id_dict[u] = i
        i += 1
    
    # write to node_map_file
    f = open(node_map_file, 'w')
    for (u,i) in id_dict.iteritems():
        f.write("%d %d\n"%(u,i)) 
    f.close();   
    print "write .nodemap file - DONE"
    
    #
    for (u,v) in G.edges_iter():
        if u != v:
            newG.add_edge(id_dict[u], id_dict[v])
        else:
            print "self-loop at ", u

    # write to file
    nx.write_edgelist(newG, new_file, '#', '\t', False, 'utf-8')   # data = False

def main():
    arg_parser = ArgumentParser(description='add edge weights to tree')
    arg_parser.add_argument('--input', required=True,
                            help='inpput file')
    arg_parser.add_argument('--output', required=True,
                            help='outpput file')
    arg_parser.add_argument('--seed', type=int, default=None,
                            help='seed for random number generator')
    arg_parser.add_argument('--delim', dest='delimiter', default=' ',
                            help='delimiter for edge list')
    arg_parser.add_argument('--no-data', action='store_true',
                            dest='no_data', help='show edge data')
    arg_parser.add_argument('--edge-list', action='store_true',
                            help='generate edge list output')
    options = arg_parser.parse_args()
    random.seed(options.seed)
    tree = nx.read_graphml(options.input)
    add_edge_weights(tree)
    if options.edge_list:
        nx.write_edgelist(tree, options.output,
                          delimiter=options.delimiter,
                          data=not options.no_data)
    else:
        nx.write_graphml(tree, options.output)
    return 0

    def save_celltype_graph(self, filename="celltype_conn.gml", format="gml"):
        """
        Save the celltype-to-celltype connectivity information in a file.
        
        filename -- path of the file to be saved.

        format -- format to save in. Using GML as GraphML support is
        not complete in NetworkX.  

        """
        start = datetime.now()
        if format == "gml":
            nx.write_gml(self.__celltype_graph, filename)
        elif format == "yaml":
            nx.write_yaml(self.__celltype_graph, filename)
        elif format == "graphml":
            nx.write_graphml(self.__celltype_graph, filename)
        elif format == "edgelist":
            nx.write_edgelist(self.__celltype_graph, filename)
        elif format == "pickle":
            nx.write_gpickle(self.__celltype_graph, filename)
        else:
            raise Exception("Supported formats: gml, graphml, yaml. Received: %s" % (format))
        end = datetime.now()
        delta = end - start
        config.BENCHMARK_LOGGER.info(
            "Saved celltype_graph in file %s of format %s in %g s"
            % (filename, format, delta.seconds + delta.microseconds * 1e-6)
        )
        print "Saved celltype connectivity graph in", filename

 def test_write_edgelist_2(self):
     fh = io.BytesIO()
     G = nx.OrderedGraph()
     G.add_edges_from([(1, 2), (2, 3)])
     nx.write_edgelist(G, fh, data=True)
     fh.seek(0)
     assert_equal(fh.read(), b"1 2 {}\n2 3 {}\n")