def sampleNodesFromGraph(inputGraph, proportionToKeep): 
        # 0.9 ... keep 90% of the nodes, remove the rest along with incident edges

        filename = inputGraph+'_sampled_'+str(proportionToKeep)
        if os.path.isfile(filename):
                 G = nx.read_dot(filename)
                 print "Cached %s loaded." % filename
                 return G
                 
        Gorig = nx.read_dot(inputGraph)
        G = nx.read_dot(inputGraph)
        #G = nx.Graph(Gorig)
        print "%s loaded." % inputGraph

        nodes = Gorig.nodes()
        random.shuffle(nodes)
        N = len(nodes)
        # keep k nodes
        k = int(round(N*(1-proportionToKeep)))
        
        for n in range(0,k):
                G.remove_node(nodes[n])

        nx.write_dot(G, filename)
        print "\tGraph sampled. Original graph had %d nodes, sampled graph has %d nodes." % (len(Gorig.nodes()), len(G.nodes())) 

        return G

def main(argv):
    
    file1 = argv[1]
    file2 = argv[2]
    file3 = argv[3]

    network = nx.read_dot(file1) 
    traffic = nx.read_dot(file3)
    
    file2 = open(file2,'r')
    rawNodeCaps = file2.readlines()
    nodeCaps={}
    for line in rawNodeCaps:
        splitLine = line.split()
        nodeCaps[str(splitLine[0])]= int(splitLine[1])

    #while (network.number_of_edges())>(int(network.number_of_nodes())/2):

    for node1 in network:
	for node2 in network:
	    if node1 != node2:
	    
		if(node1 in network.neighbors(node2) and (node2 in network.neighbors(node1))): 
		
		    print "~~~~~~~~~~~~~~~~~~~"             #this is how to reference edge weights
                                                                                        # |
                                                                                        # |
                                                                                        # V
		    print(node1+"->"+node2+" weight: " + str(network[node1][node2][0]['label']))    
		
		elif (node2 in network.neighbors(node1)and (node1 in network.neighbors(node2))):
	
		    print "~~~~~~~~~~~~~~~~~~~"
		    print(node2+"->"+node1+" weight: " + str(network[node2][node1][0]['label']))

		else:
		    n = network.number_of_edges(node1, node2)
		    #print(n)              
		     
		
	    #do anti-parallel edge removal by adding intermediate node
    
    #print(network.nodes())
    print("~~~~~~~~~~~~~~~~~~~")
    #print(network.edges())

    #print(network)
    #print(nodeCaps)
    #print(traffic)

    
    file2.close()

def main(argv):

	#Script usage
    	try:
        	opts, args = getopt.getopt(argv,"ha:b:c:",["help", "fileName=", "field=", "type="])
    	except getopt.GetoptError:
        	print 'USAGE: python workflow_graph.py -p <parameter-file>'
        	sys.exit(2)
    	for opt, arg in opts:
        	if opt == '-h':
            		print 'USAGE: python workflow_graph.py -p <parameter-file>'
            		sys.exit()
        	elif opt in ("-a", "--fileName"):
            		fileName = arg
        	elif opt in ("-b", "--field"):
            		field = arg
        	elif opt in ("-c", "--type"):
            		fieldType = arg

	g=nx.DiGraph(nx.read_dot(fileName))
	if fieldType == 'edge':
		aux_init_data = np.ndarray(len(g.edges()), dtype='float')
		indexE = 0
		for e in g.edges():
			aux_init_data[indexE] = g.edge[e[0]][e[1]][field]
			indexE = indexE + 1
	elif fieldType == 'node':
		aux_init_data = np.ndarray(len(g.nodes()), dtype='float')
		for v in g.nodes():	
			aux_init_data[int(v[1:])] = g.node[v][field]
	g.clear()

	np.save(field, aux_init_data)

def compose_breakpoint_graph(base_dot, predicted_dot, true_edges):
    base_graph = nx.read_dot(base_dot)
    predicted_edges = nx.read_dot(predicted_dot)
    out_graph = nx.MultiGraph()

    for v1, v2, data in base_graph.edges_iter(data=True):
        color = g2c(data["genome_id"])
        out_graph.add_edge(v1, v2, color=color)
    for v1, v2 in predicted_edges.edges_iter():
        out_graph.add_edge(v1, v2, color="red", style="dashed")
    for (v1, v2, infinite) in true_edges:
        label = "oo" if infinite else ""
        out_graph.add_edge(str(v1), str(v2), color="red",
                           style="bold", label=label)

    return out_graph

    def fromStatement(self,statement,fname):
        """ Populates the BuchiAutomaton's fields to construct an automaton
        that is used to check a given LTL formula.  Wraps to lbt.
        Inputs:
            statement: A string using ltl2ba syntax that gives the 
                LTL formula to be checked
            fname: file name used to save intermediate data
        """
        ###Begin wrapping to lbt####
#        txtfile= fname+ '.txt'
#        subprocess.call(['touch',txtfile])
#        fout = open(txtfile,'w');fout.write(statement);fout.close()
#        subprocess.call(paths.PATH_TO_IN2PRE+"in2preLTL " + txtfile + " " + txtfile,shell=True)
#        subprocess.call("lbt < "+ txtfile+" > automaton.txt",shell=True) 
#        subprocess.call("lbt2dot < automaton.txt > automaton.dot",shell=True)
        txtfile= fname+ '.txt'
        fout = open(txtfile,'w');fout.write(statement);fout.close()
        subprocess.call("./ltl2dot_new.sh "+fname,shell=True)
        #### End wrapping to lbt ###
        self.graph = nx.read_dot(fname+".dot")
        for node in self.graph.nodes():
            self.states.add(node)
            label = self.graph.node[node]['label']
            if self.graph.node[node]['shape'] == "doublecircle":
            #if 'n' in label:
            #if peripheries:
                self.acceptingStates.add(node)
        for edge in self.graph.edges():
            label = self.graph[edge[0]][edge[1]][0]['label']
            for prop in stripProps(buchiProcess(label)):
                self.inputLanguage.add(prop)
        self.calculateDistanceToacceptingStates()
        self.initialStates.add('0')
        self.currentStates.add('0')

def add_overlap_edges(graph, overlap_dot, contigs_file):
    contigs = get_contig_permutations(contigs_file)
    contig_begins = {}
    contig_ends = {}
    for name, blocks in contigs.items():
        contig_begins[blocks[0]] = "+" + name
        contig_begins[-blocks[-1]] = "-" + name
        contig_ends[-blocks[-1]] = "+" + name
        contig_ends[blocks[0]] = "-" + name

    overlap_graph = nx.read_dot(overlap_dot)

    subgraphs = nx.connected_component_subgraphs(graph)
    for subgr in subgraphs:
        for v1, v2 in combinations(subgr.nodes, 2):
            v1, v2 = int(v1), int(v2)

            if v1 in contig_ends and v2 in contig_begins:
                src = contig_ends[v1]
                dst = contig_begins[v2]
            elif v2 in contig_ends and v1 in contig_begins:
                src = contig_ends[v2]
                dst = contig_begins[v1]
            else:
                continue

            if not (overlap_graph.has_node(src) and
                    overlap_graph.has_node(dst)):
                continue

            if not nx.has_path(overlap_graph, src, dst):
                continue

            if my_has_path(overlap_graph, contigs, src, dst):
                graph.add_edge(str(v1), str(v2), weight=0.1)

def main(argv):

	#Script usage
    	try:
        	opts, args = getopt.getopt(argv,"ha:b:",["help", "fileName=", "field="])
    	except getopt.GetoptError:
        	print 'USAGE: python workflow_graph.py -p <parameter-file>'
        	sys.exit(2)
    	for opt, arg in opts:
        	if opt == '-h':
            		print 'USAGE: python workflow_graph.py -p <parameter-file>'
            		sys.exit()
        	elif opt in ("-a", "--fileName"):
            		fileName = arg
        	elif opt in ("-b", "--field"):
            		field = arg

	g=nx.DiGraph(nx.read_dot(fileName))
	aux_init_data = [None] * len(g.nodes())
	for v in g.nodes():
		pop = np.ndarray(g.out_degree(v), dtype='float')
		index = 0
		for vn in g.neighbors(v):
			pop[index] = g.node[vn][field]
			index = index + 1
		aux_init_data[int(v[1:])] = pop
	g.clear()

	np.save(field, aux_init_data)

	def testDot(self):
		self.assertEqual( self.g.number_of_edges(), 4 )	
		self.assertEqual( self.g.number_of_edges(), 4 )	
		nx.write_dot( self.g, './test.dot' )
		g1 = nx.read_dot( './test.dot' )
		self.assertEqual( g1.number_of_edges(), self.g.number_of_edges() )
		self.assertEqual( g1.number_of_edges(), 4 )

 def __init__(self, parent, data=None, nodes=None, **kwargs):
     """
     :param parent: type of the graph. nx.Graph, nx.DiGraph or nx.MultiGraph
     :param data: see :meth:`to_networkx_graph` for valid types
     """
     self.parent=parent 
     self.idx=None # index is created at first call to add_node
     
     self._map={} #map from original node name to position for AGraph and other graphs were 'pos' is a node attribute
     
     if data:
         if isinstance(data,six.string_types): # suppose data is a filename
             ext=data.split('.')[-1].lower()
             if ext=='dot':
                 data=nx.read_dot(data)
             else:
                 raise(Exception('unknown file format'))
         elif isinstance(data,AGraph):
             if not getattr(data,'has_layout',False):
                 data.layout()
             
         to_networkx_graph(data,self)
     elif nodes:
         for node in nodes:
             self.add_node(node)
         
     self.render_args={}

def main():
    args = parse_args(sys.argv)
    graph = nx.read_dot(args.infile)

    droppers = [re.compile(pattern) for pattern in args.drop]
    keepers = [re.compile(pattern) for pattern in args.keep]

    rm_nodes = []
    num_parents = graph.out_degree()
    degree = graph.degree()
    for node in graph.nodes():
        if matches_any(node, droppers) and not matches_any(node, keepers):
            rm_nodes.append(node)
        elif degree[node] == 0:
            rm_nodes.append(node)
        elif num_parents[node] == 0:
            graph.node[node]['shape'] = 'hexagon'
        else:
            pass  # Node will not be changed.

    detours = get_detours(graph, rm_nodes)
    graph.remove_nodes_from(rm_nodes)
    graph.add_edges_from(detours, style='dashed')

    graph.graph = {}  # Clear all graph, edge, and node attributes
    # nx.write_dot(graph) should work,
    # but doesn't, because it calls nx.to_agraph(graph).clear()
    a = nx.to_agraph(graph)
    # print(graph.edge, file=sys.stderr)
    a.write(sys.stdout)

 def __init__(self, path = None):
   """
     Load and convert dot graph.
   """
   self._G = nx.MultiDiGraph()
   if not path is None:
     self._file_path = path
     self._G = nx.read_dot(path)
     self._transform()

    def test_graphviz():
        G=nx.complete_graph(5)   # start with K5 in networkx
        A=nx.to_agraph(G)        # convert to a graphviz graph
        X1=nx.from_agraph(A)     # convert back to networkx (but as Graph)
        X2=nx.Graph(A)          # fancy way to do conversion
        G1=nx.Graph(X1)          # now make it a Graph

        A.write('k5.dot')     # write to dot file
        X3=nx.read_dot('k5.dot') # read from dotfile
        pass

def dotStr2Graph(dotstr):
    tfile = os.tmpfile()
    tfile.write(dotstr)
    tfile.seek(0)

    g = nx.read_dot(tfile)

    tfile.close()

    return g

def get_physical_net():
    global physical_net_f, phy_g, pos_phy
    options = {}
    options['title'] = 'Select physical network DOT format file'
    options['filetypes'] = [('dot files', '.dot')]
    options['defaultextension'] = '.dot'
    physical_net_f = tkFileDialog.askopenfilename(**options)
    phy_g = nx.read_dot(physical_net_f)
    pos_phy=nx.graphviz_layout(phy_g, prog='fdp')
    update_color_physical_network(nx.nodes(phy_g), 'r')
    canvas.draw()

def get_experimental_net():
    global virtual_net_f, pos_virt, virt_g
    options = {}
    options['title'] = 'Select virtual network DOT format file'
    options['filetypes'] = [('dot files', '.dot')]
    options['defaultextension'] = '.dot'
    virtual_net_f = tkFileDialog.askopenfilename(**options)
    virt_g = nx.read_dot(virtual_net_f)
    pos_virt=nx.graphviz_layout(virt_g, prog='fdp')
    update_color_virtual_network(nx.nodes(virt_g), 'g')
    canvas.draw()

 def load_config(self, config, configtype="json"):
     try:
         if configtype == "dot":
             self.graph = read_dot(config)
         elif configtype == "json":
             self.graph = json_graph.node_link_graph(json.load(open(config)))
         elif configtype == "gml":
             self.graph = read_gml(config)
     except Exception,e:
         print "Config read error: {}".format(str(e))
         self.logger.error("Error reading configuration: {}".format(str(e)))
         sys.exit(-1)

    def __init__(self, directory, name, weight_id, aggregate_number):

        self.name               = name
        self.directory          = directory 
        # self.G                  = nx.read_gexf(self.directory+self.name+'.gexf')
        self.G                  = nx.read_dot(self.directory+self.name+'.dot')
        self.weight_id          = weight_id
        self.features           = []
        self.aggregate_number   = aggregate_number
        self.Stats              = StatsHandler(name)
        
        self.standard_text_distribution = ',standard deviation,skewness,kurtosis,hhi,q90%,q80%,q70%,q60%,q50%,q40%,q30%,q20%,q10%,q5%,q1%'

def pruneGraphKeepDir(inputGraph, MIN_CLIQUE_SIZE=1):
        # remove all cliques of size less than 

        G = nx.read_dot(inputGraph)
        print "%s loaded." % inputGraph

        ########################################################
        # find cliques

        cliques = list(nx.find_cliques(G))

        num_cliques = 0
        keep = set()
        NODEtoCOLOR = {}

        print "---------------------------"
        print "Cliques:"
        print "["
        for c in sorted(cliques, cmp=bylength, reverse=True):
                if len(c) < MIN_CLIQUE_SIZE:
                        break
                num_cliques += 1
                print "%s," % (c)
                for node in c:
                        keep.add(node)
                        # colorize nodes
                        color = num_cliques/len(c)
                        try:
                                # blend
                                NODEtoCOLOR[node] = (NODEtoCOLOR[node]+float(color))/2.0
                        except KeyError:
                                NODEtoCOLOR[node] = float(color)

        print "]"
        print "\tCliques considered: %s." % (num_cliques)
        print "---------------------------"

        # remove nodes not belonging to larger cliques
        node_size = []
        node_color = []
        #G = nx.read_dot(inputGraph)
        for n in G.nodes():
                if not(n in keep):
                        G.remove_node(n)
                else:
                        # get node size
                        node_size.append( float(len(G.predecessors(n)) + len(G.successors(n)) + 0.5) )
                        node_color.append( NODEtoCOLOR[n] )

        print "\tNodes kept: %s (out of %s original)." % (len(keep), len(G.nodes()))
        return (G, node_size, node_color)

def countStats(old, new, t):
	count = GraphStatistic.objects.get(id='1').data
	edges = GraphStatistic.objects.get(id='2').data
	nodes = GraphStatistic.objects.get(id='3').data
	if new != None:
		G_new=nx.Graph(nx.read_dot("def_dots/" + new))
	if old != None:
		G_old=nx.Graph(nx.read_dot("def_dots/" + old))
	#DELETE
	if old != None and new == None and t == "delete":
		GraphStatistic.objects.filter(id='1').update(data=count-1)
		GraphStatistic.objects.filter(id='2').update(data=edges-G_old.number_of_edges())
		GraphStatistic.objects.filter(id='3').update(data=nodes-G_old.number_of_nodes())
	elif old == None and new != None and t == "new": #NEW
		GraphStatistic.objects.filter(id='1').update(data=count+1)
		GraphStatistic.objects.filter(id='2').update(data=edges+G_new.number_of_edges())
		GraphStatistic.objects.filter(id='3').update(data=nodes+G_new.number_of_nodes())
	elif old != None and new != None and t == "update": #EDIT
		asd = G_new.number_of_nodes()
		asd2 = G_old.number_of_nodes()
		GraphStatistic.objects.filter(id='2').update(data=edges+G_new.number_of_edges()-G_old.number_of_edges())
		GraphStatistic.objects.filter(id='3').update(data=nodes+G_new.number_of_nodes()-G_old.number_of_nodes())
	return 0

def __main__():
    g = nx.read_dot('shortened_winter_wheat_56mresolution_upstate_ny_20box_radius_inf.dot')
    cc = nx.connected_component_subgraphs(g)
    for sub_graph in cc:
        if len(sub_graph.nodes()) > 2:
            A = nx.adjacency_matrix(sub_graph)
            eigenvalues = eig(A)[0]
            MFPT_matrix = find_MFPT_matrix(A, sub_graph, 0.005, 1000)
        
            fout = open('Connected Component ' + str(cc.index(sub_graph)) + '.npz', 'w+')
            np.savez(fout, A, eigenvalues, MFPT_matrix)
            fout.close
                 
    return None