def __init__(self, graph, sd):
     #We need a deepcopy if the self.graph gets modified.
     self.graph = graph.copy() 
     np.random.seed()
     self.result_graph = nx.Graph()
     
     #Sets with/without monitors.
     self.monitor_set = set()
     self.monitor_free=nx.nodes(self.graph) #Save this list to speed computations.
     
     #Internal dictionaries
     self.next_highest = {}
     self.seen = Counter()
     
     #2-Colored Components
     self.blueseen = 0
     self.redseen = 0
     self.monitor_fancy = list()
     
                     
     #Initialize all fake degrees to degree
     self.fake_degree=dict()
     #for node in self.monitor_free:
     for node in nx.nodes(self.graph):
         self.fake_degree[node]=self.graph.degree(node)

def occurenceCounter(charList, graphFile, bookNetworksPath):
    g = nx.read_gexf(graphFile)

    if not charList:
        # Get characters from overall.gexf graph
        overallGraphFile = bookNetworksPath + "overall.gexf"
        overall_g = nx.read_gexf(overallGraphFile)
        overallChars = nx.nodes(overall_g)

        # Sort dictionary by name (key of dictionary)
        sortedChars = sorted(overallChars)

        return sortedChars

    else:
        charList = [item for item in charList]

        for index, item in enumerate(charList):
            currentChar = None
            for node in nx.nodes(g):
                if node == item:
                    occurrence = 1
                    charList[index] = (item, occurrence)
                    currentChar = node
            # If current character is not present in the current chapter assign 0 influence.
            if not currentChar:
                occurrence = 0
                charList[index] = (item, occurrence)

        return charList

    def write_blast_graph_file(self):
        file_name = "{}/blast_graph.txt".format(self.blast_output_path)
        if len(nx.nodes(self.blast_graph)) > 0:
            with open(file_name, "wb") as f_handle:
                f_handle.write(
                    'Source' + ', Species,' + str(
                        [value for value in self.blast_graph.node[nx.nodes(self.blast_graph)[0]].iterkeys()]).strip(
                        '[]') + ',')
                f_handle.write(
                    'Target' + ', Species,' + str(
                        [value for value in self.blast_graph.node[nx.nodes(self.blast_graph)[0]].iterkeys()]).strip(
                        '[]') + ',')
                f_handle.write(
                    'evalue' + ',' + 'identpct' + ',' + 'mismatchno' + ',' + 'aln' + ',' + 'alnspn' + ',' + 'gapopenno' + ',' + 'bitscore' + '\n')

                for u, v, edata in self.blast_graph.edges(data=True):
                    f_handle.write(
                        str(u) + ',' + self.get_species_name(str(u)) + str(
                            [value for value in self.blast_graph.node[u].itervalues()]).strip(
                            '[]') + ',')
                    f_handle.write(
                        str(v) + ',' + self.get_species_name(str(v)) + str(
                            [value for value in self.blast_graph.node[v].itervalues()]).strip(
                            '[]') + ',')
                    f_handle.write(
                        str(edata['evalue']) + ',' + str(edata['identpct']) + ',' + str(edata['mismatchno']) + ',' +
                        str(edata['aln']) + ',' + str(edata['alnspn']) + ',' +
                        str(edata['gapopenno']) + ',' + str(edata['bitscore']) + '\n')

def get_region_colors(adjacency_matrix):
    """
    Calculate color for each region in the graph.

    Input: adjacency_matrix - graph adjacency_matrix where [x][y] = 1 means
                              that region x and region y share common border.

    Output: colors_dictionary - dictionary object where key is region number
                                and value is color (witches - 1, vampires - 2, werewolves - 3, hybrids - 4)
    """
    G = nx.Graph()
    colors_dictionary = {}

    if len(adjacency_matrix) == 1:
        colors_dictionary[0] = 1
        return colors_dictionary

    G = create_color_none_graph(adjacency_matrix, G)
    G = set_node_colors(G)

    for node in nx.nodes(G):
        node_color = G.node[node]['color']
        node_color += 1
        G.node[node]['color'] = node_color

    for node in nx.nodes(G):
        colors_dictionary[node] = G.node[node]['color']

    return colors_dictionary

def gimme():
    l = Linkbase(LinkNode)
    l.new_node(u'There once was a man from Nantucket.')
    l.new_node(u'who put all on the line for a bucket.')
    l.link(0,1,0)
    print networkx.nodes(l.store)
    return l

def make_graph(list, density):
    g = nx.DiGraph()
    for i in list:
        g.add_node(i)
    for node in nx.nodes(g):
        while g.out_degree(node)<density:
            rand = random.choice(nx.nodes(g))
            if rand != node:
                g.add_edge(node, rand)
    return g

    def execute(self, G, epsilon=0.0, weighted=False, min_community_size=1):
        """
        Execute Demon algorithm

        :param G: the networkx graph on which perform Demon
        :param epsilon: the tolerance required in order to merge communities (default 0.25)
        :param weighted: Whether the graph is weighted or not
        :param min_community_size:min nodes needed to form a community
        """

        #######
        self.G = G
        self.epsilon = epsilon
        self.min_community_size = min_community_size
        for n in self.G.nodes():
            G.node[n]['communities'] = [n]
        self.weighted = weighted
        #######

        all_communities = {}

        total_nodes = len(nx.nodes(self.G))
        actual = 0

        for ego in nx.nodes(self.G):
            percentage = float(actual * 100)/total_nodes

            #if (int(percentage) % 1) == 0:
            #    print 'Ego-network analyzed: %d/100 (communities identified: %d)' % (
            #        percentage, len(all_communities))
            actual += 1

            #ego_minus_ego
            ego_minus_ego = nx.ego_graph(self.G, ego, 1, False)
            community_to_nodes = self.__overlapping_label_propagation(ego_minus_ego, ego)

            #merging phase
            for c in community_to_nodes.keys():
                if len(community_to_nodes[c]) > self.min_community_size:
                    actual_community = community_to_nodes[c]
                    all_communities = self.__merge_communities(all_communities, actual_community)

        #print communities
        #out_file_com = open("communities", "w")
        idc = 0
        for c in all_communities.keys():
            #out_file_com.write("%d\t%s\n" % (idc, ','.join([str(x) for x in sorted(c)])))
            print("%d\t%s" % (idc, ','.join([str(x) for x in sorted(c)])))
            idc += 1
        #out_file_com.flush()
        #out_file_com.write("\n")
        #out_file_com.flush()
        #out_file_com.close()

        return

def get_graph(filename, with_root=False):
    DG = nx.DiGraph()
    f = open(filename, 'r')
    line = None
    edges = []
    coordinates = []
    terms = []
    if with_root:
        root = None
    while line != 'EOF':
        line = f.readline().strip()
        toks = line.split(' ')
        if toks[0] == 'A':
            t = tuple(int(x) for x in toks[1:])
            edges.append(t)
        if toks[0] == 'T':
            terms.append(int(toks[1]))
        if toks[0] == 'Root':
            if with_root:
                root = int(toks[1])
        if toks[0] == 'DD':
            t = tuple(int(x) for x in toks[1:])
            coordinates.append(t)
    for coord in coordinates:
        DG.add_node(coord[0], pos=(coord[1], coord[2]))
    terms.sort()
    DG.add_weighted_edges_from(edges)
    # print_graph(DG)
    # nx.draw(DG, node_size=50)
    # plt.show()
    # f.close()
    if with_root:
        return DG, terms, root
    else:
        print_graph(DG)
        max_len = 0
        max_node = None
        for node in nx.nodes(DG):
            # print(node, tr_cl.out_edges(node))
            descs = nx.descendants(DG, node)
            # desc_numb = len(descs)
            if len(set(terms) & set(descs)) == len(descs):
                # max_len = desc_numb
                max_node = node
        if max_len == len(nx.nodes(DG)):
            return DG, terms, max_node
        else:
            reachable = set(nx.descendants(DG, max_node)) | {max_node}
            unreachable = set(nx.nodes(DG)) - reachable
            for node in unreachable:
                DG.remove_node(node)
        terms = list(set(terms) & reachable)
        print('terms =', len(terms))
        return DG, terms, max_node

    def execute(self):
        """
        Execute Demon algorithm

        """

        sys.stdout.write('\n[Community Extraction]\n')
        sys.stdout.flush()

        for n in self.g.nodes():
            self.g.node[n]['communities'] = [n]

        all_communities = {}

        total_nodes = len(nx.nodes(self.g))
        old_p = 0
        actual = 1

        bar_length = 20

        for ego in nx.nodes(self.g):

            ego_minus_ego = nx.ego_graph(self.g, ego, 1, False)
            community_to_nodes = self.__overlapping_label_propagation(ego_minus_ego, ego)

            # merging phase
            for c in community_to_nodes.keys():
                if len(community_to_nodes[c]) > self.min_community_size:
                    actual_community = community_to_nodes[c]
                    all_communities = self.__merge_communities(all_communities, actual_community)

            # progress bar update
            percentage = int(float(actual * 100) / total_nodes)
            if percentage > old_p:
                hashes = '#' * int(round(percentage/5))
                spaces = ' ' * (bar_length - len(hashes))
                sys.stdout.write("\rExec: [{0}] {1}%".format(hashes + spaces, int(round(percentage))))
                sys.stdout.flush()
                old_p = percentage
            actual += 1

        if self.file_output:
            out_file_com = open("%s.txt" % self.file_output, "w")
            idc = 0
            for c in all_communities.keys():
                out_file_com.write("%d\t%s\n" % (idc, str(sorted(c))))
                idc += 1
            out_file_com.flush()
            out_file_com.close()
            return all_communities
        else:
            return all_communities

def random_walk(g,start=None,seed=None):
    random.seed(seed)
    if start is None:
        start=random.choice(nx.nodes(g))
    walk=[]
    unused_nodes=set(nx.nodes(g))
    unused_nodes.remove(start)
    while len(unused_nodes) > 0:
        p=start
        start=random.choice([x for x in nx.all_neighbors(g,start)]) # follow random edge
        walk.append((p,start))
        if start in unused_nodes:
            unused_nodes.remove(start)
    return walk

    def findDominatingSet(self, graph):
        print "Algorithm: Modified greedy"

        modify_graph = copy.deepcopy(graph)
        dominating_set = []
        nodes = nx.nodes(modify_graph)

        while not len(nodes) == 0:
            node = self.findMaxDegreeNode(modify_graph)
            dominating_set.append(node)
            modify_graph = self.removeNodeAndNeighbors(modify_graph, node)
            nodes = nx.nodes(modify_graph)

        return dominating_set

    def execute(self, G, epsilon=0.25, weighted=False, min_community_size=3):
        """
        Execute Demon algorithm

        :param G: the networkx graph on which perform Demon
        :param epsilon: the tolerance required in order to merge communities
        :param weighted: Whether the graph is weighted or not
        :param min_community_size:min nodes needed to form a community
        """

        #######
        self.G = G
        self.epsilon = epsilon
        self.min_community_size = min_community_size
        for n in self.G.nodes():
            G.node[n]['communities'] = [n]
        self.weighted = weighted
        #######

        print  'hello'
        all_communities = {}

        total_nodes = len(list(nx.nodes(self.G)))
        actual = 0
        old_percentage = 0
        for ego in nx.nodes(self.G):
            percentage = float(actual * 100) / total_nodes

            actual += 1

            # ego_minus_ego
            ego_minus_ego = nx.ego_graph(self.G, ego, 1, False)
            community_to_nodes = self.__overlapping_label_propagation(ego_minus_ego, ego)

            # merging phase
            for c in community_to_nodes.keys():
                if len(community_to_nodes[c]) > self.min_community_size:
                    actual_community = community_to_nodes[c]
                    all_communities = self.__merge_communities(all_communities, actual_community)

        # print communities
        out_file_com = open("communities.txt", "w")
        idc = 0
        for c in all_communities.keys():
            out_file_com.write("%d\t%s\n" % (idc, str(sorted(c))))
            idc += 1
        out_file_com.flush()
        out_file_com.close()

        return

def averageNeighDegree(G):
    sum=0
    l=nx.nodes(G)
    for elt in l:
        sum+=G.degree(elt)
    avg=sum/(nx.number_of_nodes(G))
    return avg

	def give_output_list(self, game):
		""" This returns a list of the selected nodes. The twin attack player
		finds the highest degree nodes, and for each, it selects two
		neighbors of that node and"""

		nodes = nx.nodes(game.network)

		nodes.sort(key=lambda x : nx.degree(game.network, x), reverse=True)

		selections = set()

		for node in nodes:

			adjacents = list(nx.all_neighbors(game.network, node))

			for adj_node in adjacents[:2]:

				selections.add(adj_node)
				if len(selections) == game.num_seeds:
					break

			if len(selections) == game.num_seeds:
				break

		assert len(selections) == game.num_seeds
		return list(selections)

def atom_graph(g):
    # determine if subgroup is attached
    h = nx.Graph()
    v = []
    tris = {}
    edges = {}
    for node,data in g.nodes(data=True):
        g.node[node]['atoms'] = set([])

    # triplet
    for node in nx.nodes(g):
        for each in g[node]:
            if each == node: continue
            neighbors = set(g[node]).intersection(set(g[each]))
            #print(node, each, neighbors, set(g[node]), g[each], set(g[each]))
            for neighbor in neighbors:
                t = tuple(sorted((node, each, neighbor)))
                if t not in list(tris.keys()):
                    nr = len(h.nodes())
                    tris[t] = nr
                    h.add_node(nr)
                    g.node[node]['atoms'].add(nr)
                    g.node[each]['atoms'].add(nr)
                    g.node[neighbor]['atoms'].add(nr)
                    #print(node, each, neighbor)
                    for k in tris:
                        if len(set(k).intersection(set(t))) == 2:
                            h.add_edge(nr, tris[k])
                            edges[tuple(sorted(set(k).intersection(set(t))))] = nr

    #if nx.cycle_basis(h):
    #    extra_nodes = set(h.nodes()).difference(set(np.concatenate(nx.cycle_basis(h))))
    #    for n in extra_nodes:
    #        h.remove_node(n)
    return h

def printAttributes(comp,chromo,G):
    #for n in nx.nodes_iter(G):
    for n in nx.nodes(G):
        intensity=G.node[n]['intensity']
        gene=G.node[n]['gene']
        print ("\tcluster->%i,%s" % (comp,intensity))
    return

def fast_approximate_solution_two(graph):
    """
    Given a graph, construct a solution greedily using approximation methods.
    Performs bad.
    """
    new_graph = nx.Graph()
    degrees = nx.degree_centrality(graph) 
    largest = argmax(degrees)
    new_graph.add_node(largest)
    while new_graph.number_of_edges() < graph.number_of_nodes() - 1:
        degrees = {n: count_uncovered_degree(graph, new_graph, n) for n in nx.nodes(graph)}
        neighbor_list = [nx.neighbors(graph, n) for n in new_graph.nodes()]
        neighbors = set()
        for lst in neighbor_list:
            neighbors = neighbors.union(lst)
        if not neighbors:
            break
        next_largest = argmax_in(degrees, neighbors, exceptions = new_graph.nodes())
        possible_edge_ends = [n for n in nx.neighbors(graph, next_largest) 
                              if graph.has_edge(n, next_largest) 
                              and n in new_graph.nodes()]
        new_graph.add_node(next_largest)
        edge_end = argmax_in(degrees, possible_edge_ends)
        new_graph.add_edge(edge_end, next_largest)

    return new_graph

def calculate(g, voltage):
    edges_num = nx.number_of_edges(g)
    # sort nodes in edges
    edges = [edge if edge[0] < edge[1] else (edge[1], edge[0])
             for edge in nx.edges(g)]

    a = np.zeros((edges_num, edges_num))
    b = np.zeros((edges_num, 1))
    i = 0
    # first law
    for node in [node for node in nx.nodes(g) if node != 0]:
        for neighbor in nx.all_neighbors(g, node):
            edge = tuple(sorted((node, neighbor)))
            a[i][edges.index(edge)] = 1 if neighbor < node else -1
        i += 1
    # second law
    cycles = nx.cycle_basis(g, 0)
    for cycle in cycles:
        for j in range(0, len(cycle)):
            node = cycle[j]
            next_node = cycle[(j + 1) % len(cycle)]
            edge = tuple(sorted((node, next_node)))
            resistance = g[node][next_node]['weight']
            a[i][edges.index(edge)] = resistance if node < next_node else -resistance
        if 0 in cycle:
            b[i] = voltage
        i += 1
    # solve
    x = np.linalg.solve(a, b)
    for (x1, x2), res in zip(edges, x):
        g[x1][x2]['current'] = res[0]

 def getCoverageSets(self, graph):
     coverage_sets = []
     nodes = nx.nodes(graph)
     for node in nodes:
         coverage_set = self.getCoverageSet(graph, node)
         coverage_sets.append(coverage_set)
     return coverage_sets

    def select_random_biome(self, adj_list=list()):
        if adj_list:
            the_graph = self.neighbors_subgraph(adj_list)
        else:
            the_graph = self

        return random.choice(nx.nodes(the_graph))