def augmentNodes(g):
    r1 = nx.eigenvector_centrality_numpy(g)
    r2 = nx.degree_centrality(g) # DP MY
    r3 = nx.betweenness_centrality(g)
    r5 = nx.load_centrality(g,weight='weight') # DY, WY-writename # Scientific collaboration networks: II. Shortest paths, weighted networks, and centrality, M. E. J. Newman, Phys. Rev. E 64, 016132 (2001).
    r6 = nx.pagerank(g, alpha=0.85, personalization=None, max_iter=100, tol=1e-08, nstart=None, weight='weight')
    
    if nx.is_directed(g) == True:
        r8 = nx.in_degree_centrality(g)
        r9 = nx.out_degree_centrality(g)
#        r10 = nx.hits(g, max_iter=100, tol=1e-08, nstart=None)
    else:
        r4 = nx.communicability_centrality(g)
        r7 = nx.clustering(g, weight='weight')
        
    for x in g.nodes():
        g.node[x]['eigenvector_centrality_numpy'] = r1[x]
        g.node[x]['degree_centrality'] = r2[x]  
        g.node[x]['betweenness_centrality'] = r3[x]
        g.node[x]['load_centrality'] = r5[x]  
        g.node[x]['pagerank'] = r6[x]

        if nx.is_directed(g) == True:
            g.node[x]['in_degree_centrality'] = r8[x]
            g.node[x]['out_degree_centrality'] = r9[x]
#            g.node[x]['hits'] = r10[x]
        else:
            g.node[x]['communicability_centrality'] = r4[x]
            g.node[x]['clustering'] = r7[x]
    return g        

def _create_flow_graph(G, H, infcapFlows):
    """Creates the flow graph on G corresponding to the auxiliary
    digraph H and infinite capacity edges flows infcapFlows.
    """
    if nx.is_directed(G):
        flowGraph = nx.DiGraph(G)
    else:
        flowGraph = nx.Graph(G)

    for (u, v) in flowGraph.edges():
        if H.has_edge(u, v):
            try:
                flowGraph[u][v]['flow'] = abs(G[u][v]['capacity']
                                              - H[u][v]['capacity'])
            except KeyError: # (u, v) has infinite capacity
                try:
                    flowGraph[u][v]['flow'] = H[v][u]['capacity']
                except KeyError:
                    # Infinite capacity digon in the original graph.
                    if nx.is_directed(G):
                        flowGraph[u][v]['flow'] = max(infcapFlows[(u, v)]
                                                    - infcapFlows[(v, u)], 0)
                    else:
                        flowGraph[u][v]['flow'] = abs(infcapFlows[(u, v)]
                                                    - infcapFlows[(v, u)])
        else:
            flowGraph[u][v]['flow'] = G[u][v]['capacity']

    return flowGraph

def calculate_network_measures(net, analyser):
    deg=nx.degree_centrality(net)
    clust=[]

    if(net.is_multigraph()):
        net = analyser.flatGraph(net)

    if(nx.is_directed(net)):
        tmp_net=net.to_undirected()
        clust=nx.clustering(tmp_net)
    else:
        clust=nx.clustering(net)



    if(nx.is_directed(net)):
        tmp_net=net.to_undirected()
        paths=nx.shortest_path(tmp_net, source=None, target=None, weight=None)
    else:
        paths=nx.shortest_path(net, source=None, target=None, weight=None)

    lengths = [map(lambda a: len(a[1]), x[1].items()[1:]) for x in paths.items()]
    all_lengths=[]
    for a in lengths:
        all_lengths.extend(a)
    max_value=max(all_lengths)
    #all_lengths = [x / float(max_value) for x in all_lengths]

    return deg.values(),clust.values(),all_lengths

def output_graph_sgf(G):
    print("# Simple Graph Format")
    print("# name:", G.name)

    if nx.is_directed(G):
        d = "d"
    else:
        d = "u"
    print(d, G.number_of_nodes(), G.number_of_edges())
    cnt = 0
    for node in G.nodes_iter(data=True):
        node_id = node[0]
        if node_id != cnt:
            raise ("non-consecutive node exception")
        # if 'weight' in node[1]:
        cnt += 1
        # print(G.out_edges([node[0]]))
        print(node_id, end="|")
        edges = []
        # edges = [str(edge[1]) for edge in nx.edges_iter(G, [node[0]])]
        for edge in G.edges_iter([node[0]], data="weight"):
            # print('edge', edge)
            src = edge[0]
            dst = edge[1]
            weight = edge[2]
            if src != node_id:
                raise ("invalid link")
            if weight != None:
                edges.append(str(dst) + ":" + str(weight))
            else:
                edges.append(str(dst))

        print(",".join(edges))
    if cnt != G.number_of_nodes():
        raise ("non-consecutive node exception")

    def prepare_visjs_data(g):
        nodes = []
        for node in g.nodes_iter():
            new = {'id': str(node),
                   'label': str(g.node[node]['label']) if 'label' in g.node[node] else str(node),
                   'shape': 'box'
            }
            nodes.append(new)

        edges = []
        for fromnode, tonode, etype in g.edges_iter(keys=True):
            if 'label' in g[fromnode][tonode][etype]:
                label = str(g[fromnode][tonode][etype]['label'])
            elif 'weight' in g[fromnode][tonode][etype]:
                label = str(g[fromnode][tonode][etype]['weight'])
            else:
                #label = str(etype)
                label = ''
            new = {'from': str(fromnode),
                   'to': str(tonode),
                   'label': label,
                   'color': {'color': 'black', 'highlight': 'blue', 'hover': 'blue'},
            }
            if nx.is_directed(g):
                new['arrows'] = 'to'
            edges.append(new)

        return {'nodes': nodes,
                'edges': edges}

def _create_auxiliary_digraph(G):
    """Initialize an auxiliary digraph and dict of infinite capacity
    edges for a given graph G.
    Ignore edges with capacity <= 0.
    """
    auxiliary = nx.DiGraph()
    infcapFlows = {}

    if nx.is_directed(G):
        for edge in G.edges(data = True):
            if edge[2].has_key('capacity'):
                if edge[2]['capacity'] > 0:
                    auxiliary.add_edge(*edge)
            else:
                auxiliary.add_edge(*edge)
                infcapFlows[(edge[0], edge[1])] = 0
    else:
        for edge in G.edges(data = True):
            if edge[2].has_key('capacity'):
                if edge[2]['capacity'] > 0:
                    auxiliary.add_edge(*edge)
                    auxiliary.add_edge(edge[1], edge[0], edge[2])
            else:
                auxiliary.add_edge(*edge)
                auxiliary.add_edge(edge[1], edge[0], edge[2])
                infcapFlows[(edge[0], edge[1])] = 0
                infcapFlows[(edge[1], edge[0])] = 0

    return auxiliary, infcapFlows

def WC_model(G, a):                 # a: the set of initial active nodes
                                    # each edge from node u to v is assigned probability 1/in-degree(v) of activating v
    A = set(a)                      # A: the set of active nodes, initially a
    B = set(a)                      # B: the set of nodes activated in the last completed iteration
    converged = False
 
    if nx.is_directed(G):
        my_degree_function = G.in_degree
    else:
        my_degree_function = G.degree

    while not converged:
        nextB = set()
        for n in B:
            for m in set(G.neighbors(n)) - A:
                prob = random.random()	# in the range [0.0, 1.0)
                p = 1.0/my_degree_function(m)
                if prob <= p:
                    nextB.add(m)
        B = set(nextB)
        if not B:
            converged = True
        A |= B

    return len(A)

def estimate_joint_dist(graph, nsteps):
    assert(not nx.is_directed(graph))
    assert('labeled' in graph.graph and graph.graph['labeled'])

    n = nsteps  #total num seen
    n_iod = {}  #total seen with indeg i, outdeg o, deg d

    # random initial node; don't include in estimator
    node = random.choice(graph.nodes())
    
    # rw
    for i in xrange(nsteps):
        node = random.choice(list(nx.all_neighbors(graph, node)))
        iod_tuple = (graph.node[node]['in-degree'],
                     graph.node[node]['out-degree'],
                     graph.node[node]['degree'])
        n_iod[iod_tuple] = n_iod.get(iod_tuple,0) + 1

    # degree distribution parameters
    max_indeg  = max([graph.node[k]['in-degree'] for k in graph.node.keys()])
    max_outdeg = max([graph.node[k]['out-degree'] for k in graph.node.keys()])
    deg_par = np.zeros((max_indeg + 1, max_outdeg + 1))

    for (indeg, outdeg, deg) in n_iod.keys():
        val = n_iod[(indeg, outdeg, deg)]
        deg_par[indeg, outdeg] += float(val) / float(n * deg)
        #deg_par[indeg, outdeg] += float(val) / float(deg)

    # normalize
    deg_par /= deg_par.sum()

    np.savetxt("deg_par.csv", deg_par, delimiter=",")

    return deg_par

def scaling_mincostflow(G, s, t, capacity='capacity', weight='weight',
                        demand='demand', refine_scaling_constant=2):
    """Find a minimum cost flow solution using the push-relabel
    algorithm/successive approximation algorithm
    """
    if G.is_multigraph():
        raise nx.NetworkXError(
            'MultiGraph and MultiDiGraph not supported (yet).')
    if not nx.is_directed(G):
        raise nx.NetworkXError(
            'Undirected graphs are not supported (yet).')

    getcontext().prec = 28
    G_copy = nx.DiGraph(G)
    max_cost = max([G_copy[u][v][weight] for u,v in G_copy.edges_iter()])

    #initialization
    price='price'
    for v in G_copy:
        G_copy.node[v][price] = 0
    epsilon = Decimal(max_cost)
    
    _get_maxflow(G_copy, s, t, capacity)
    
    len_G = len(G_copy)
    tol = Decimal(1/Decimal(len_G))

    while epsilon >= tol:
        epsilon = _refine(epsilon, G_copy, capacity, weight, refine_scaling_constant, s, t)
    
    return _create_flow_dict(G, G_copy, t)

    def __init__(
        self,
        graph,
        weight='weight',
        cap='capacity',
        ):
        """
        Constructor
        """

        self.wt = weight
        self.cap = cap
        self.g = graph
        self.pathHeap = []  # Use the heapq module functions heappush(pathHeap, item) and heappop(pathHeap, item)
        self.pathList = []  # Contains WeightedPath objects
        self.deletedEdges = set()
        self.deletedNodes = set()
        self.kPath = None

        # Make a copy of the graph tempG that we can manipulate

        if isinstance(graph, nx.Graph):

            # self.tempG = graph.copy()

            if nx.is_directed(graph):
                self.tempG = nx.DiGraph(graph)
            else:
                self.tempG = nx.Graph(graph)
        else:
            self.tempG = None

def random_rewiring(network):
    """
    Rewires a pair of edges such that the degree sequence is preserved.

    Arguments:
        network => The input network.

    Returns:
        A network with one pair of edges randomly rewired.
    """

    # Don't terminate until the rewiring is performed.
    while True:

        # Store the number of edges in the network to avoid repeated computation.
        network_edges = nx.edges(network)

        # If there isn't at least 1 edge, break out and return.
        if len(network_edges) == 0:
            break

        # Randomly selected a link from the network.
        link1 = (source1, target1) = random.choice(network_edges)

        # Find all the edges that share no nodes with link1.
        disjoint_links = [link for link in network_edges if not any(node in link for node in link1)]

        # If there are no disjoint links, it would be impossible to randomize the network while
        # still preserving the degree sequence, so break out and return.
        if len(disjoint_links) == 0:
            break

        # Randomly selected a DIFFERENT link from the network (no sharing of nodes allowed).
        link2 = (source2, target2) = random.choice(disjoint_links)

        # If the graph is directed, there is only one option.
        # If the graph is undirected, there are two options, each with a 50-50 chance.
        if not nx.is_directed(network) and random.random() < 0.5:

            # Rewire links A-B and C-D to A-C and B-D.
            new_link1 = (source1, source2)
            new_link2 = (target1, target2)

        else:

            # Rewire links A-B and C-D to A-D and C-B.
            new_link1 = (source1, target2)
            new_link2 = (source2, target1)

        # If the new links aren't in the network already, replace the old links with the new links.
        if not network.has_edge(*new_link1) and not network.has_edge(*new_link2):

            # Remove the old links.
            network.remove_edges_from([link1, link2])

            # Add the new links.
            network.add_edges_from([new_link1, new_link2])

            # Returned the slightly altered new network.
            return network

def DFS(G, s):
    cor = {}
    pred = {}
    d = {}
    f = {}

    tempo = 0

    for v in G.nodes():
        cor[v] = "branco"  # cores possíveis: branco cinza e preto
        pred[v] = None

    for v in G.nodes():
        if cor[v] == "branco":
            tempo = visit(G, v, cor, pred, d, f, tempo)

    H = nx.create_empty_copy(G)

    for v1, v2, data in G.edges(data=True):
        if (pred[v2] is v1) or (pred[v1] is v2 and not nx.is_directed(H)):
            H.add_edge(v1, v2, data)
            H.node[v1]["begin_time"] = d[v1]
            H.node[v2]["begin_time"] = d[v2]
            H.node[v1]["finish_time"] = f[v1]
            H.node[v2]["finish_time"] = f[v2]

    return H

def _create_auxiliary_digraph(G, capacity="capacity"):
    """Initialize an auxiliary digraph and dict of infinite capacity
    edges for a given nxgraph G.
    Ignore edges with capacity <= 0.
    """
    auxiliary = nx.DiGraph()
    auxiliary.add_nodes_from(G)
    inf_capacity_flows = {}
    if nx.is_directed(G):
        for edge in G.edges(data=True):
            if capacity in edge[2]:
                if edge[2][capacity] > 0:
                    auxiliary.add_edge(*edge)
            else:
                auxiliary.add_edge(*edge)
                inf_capacity_flows[(edge[0], edge[1])] = 0
    else:
        for edge in G.edges(data=True):
            if capacity in edge[2]:
                if edge[2][capacity] > 0:
                    auxiliary.add_edge(*edge)
                    auxiliary.add_edge(edge[1], edge[0], edge[2])
            else:
                auxiliary.add_edge(*edge)
                auxiliary.add_edge(edge[1], edge[0], edge[2])
                inf_capacity_flows[(edge[0], edge[1])] = 0
                inf_capacity_flows[(edge[1], edge[0])] = 0

    return auxiliary, inf_capacity_flows

def attack_based_max_closeness(G):
    """ Recalcuat closeness attack
    """
    n = G.number_of_nodes()
    tot_ND = [0] * (n+1)
    tot_T = [0] * (n+1)

    ND, ND_lambda = ECT.get_number_of_driver_nodes(G)
    tot_ND[0] = ND
    tot_T[0] = 0

    # remember when all the closeness have been zero for all nodes
    for i in range(1, n+1):
        all_closeness = nx.closeness_centrality(G)
        # get node with max betweenness       
        node = max(all_closeness, key=all_closeness.get)
        
        # remove all the edges adjacent to node
        if not nx.is_directed(G):   # undirected graph
            for key in G[node].keys():
                G.remove_edge(node, key)
        else:   # directed graph
            for x in [v for u, v in G.out_edges_iter(node)]:
                G.remove_edge(node, x)
            for x in [u for u, v in G.in_edges_iter(node)]:
                G.remove_edge(x, node)
        # calculate driver node number ND
        ND, ND_lambda = ECT.get_number_of_driver_nodes(G)
        tot_ND[i] = ND
        tot_T[i]  = i
    return (tot_ND, tot_T, Max_Betweenness_Zero_T)

def attack_based_max_eigenvector(G):
    """ Recalculate eigenvector centrality attack
    """
    n = G.number_of_nodes()
    tot_ND = [0] * (n+1)
    tot_T = [0] * (n+1)

    ND, ND_lambda = ECT.get_number_of_driver_nodes(G)
    tot_ND[0] = ND
    tot_T[0] = 0

    for i in range(1, n+1):
        # calculate all nodes' eigenvector centrality
        allEigenvectorCentrality = nx.eigenvector_centrality(G, max_iter=1000, weight=None)
        # get node with max eigenvector centrality       
        node = max(allEigenvectorCentrality, key=allEigenvectorCentrality.get)
        # remove all the edges adjacent to node
        if not nx.is_directed(G):   # undirected graph
            for key in G[node].keys():
                G.remove_edge(node, key)
        else:   # directed graph
            for x in [v for u, v in G.out_edges_iter(node)]:
                G.remove_edge(node, x)
            for x in [u for u, v in G.in_edges_iter(node)]:
                G.remove_edge(x, node)
        ND, ND_lambda = ECT.get_number_of_driver_nodes(G)
        tot_ND[i] = ND
        tot_T[i]  = i
    return (tot_ND, tot_T)

def single_discount_high_degree_nodes_gen(k, G):

    if nx.is_directed(G):
        my_degree_function = G.out_degree
    else:
        my_degree_function = G.degree

    D = []

    for i in range(k):
        # find the node of max out_degree, discounting any out-edge
        # to a node already in D
        maxoutdeg_i = -1
        v_i = -1
        for v in list(set(G.nodes()) - set(D)):
            outdeg = my_degree_function(v)
            for u in D:
                if G.has_edge(v, u):
                    outdeg -= 1
            if outdeg > maxoutdeg_i:
                maxoutdeg_i = outdeg
                v_i = v

        D.append(v_i)
        yield D

def Prim(G = nx.Graph(), R = None):
    # Q é a lista de vértices que não estão na árvore
    Q    = {}
    # pred armazenará o predecessor de cada vértice
    pred = {}

    # Inicializamos Q com todos os vértices com valor infinito, pois neste
    # ponto ainda não há ligação entre nenhum vértice. Igualmente, nenhum
    # vértice tem predecessor, portanto utilizamos o valor 'null'.
    for v,data in G.nodes(data=True):
        Q[v]    = n.inf
        pred[v] = 'null'

    # Caso não haja pesos definidos para os vértices, atribuímos o valor 1.0.
    # Esta é uma abordagem alternativa à que usamos em Kruskal, de utilizar uma
    # variável para verificar se estamos levando em conta o peso ou não.
    for e,x in G.edges():
        if ('weight' not in G[e][x]):
            G[e][x]['weight'] = 1.0

    # Inicializamos a raiz da árvore com valor 0, e criamos uma árvore chamada
    # MST apenas com os vértices de G.
    Q[R] = 0.0
    MST  = nx.create_empty_copy(G)

    while Q:
        # u := índice do menor elemento de Q
        # pois queremos o vértice de menor peso
        u = min(Q,key=Q.get)

        # removemos de Q, pois ele será adicionado na árvore
        del Q[u]

        # guardamos os pesos mínimos de cada vizinho de u em Q, se forem
        # menores do que os já armazenados
        for vizinho in G[u]:
            if vizinho in Q:
                if G[u][vizinho]['weight'] < Q[vizinho]:
                    pred[vizinho] = u
                    Q[vizinho]    = G[u][vizinho]['weight']

        # Se existirem predecessores para u, então adicionaremos as arestas
        # conectando o vértice u a seus predecessores
        if pred[u] is not 'null':
            for v1,v2,data in G.edges(data=True):
                # para preservar os dados da aresta, foi necessário esse loop
                # que verifica todas as arestas do grafo e procura a aresta
                # (pred(u),u), porém, como um grafo não direcionado da
                # biblioteca não duplica a existência de suas arestas no
                # conjunto de arestas, isto é, se tem (u,v) não tem (v,u), há a
                # necessidade de verificar, no caso de grafos não direcionados,
                # se há a existência da aresta (u,pred(u)) ao invés de
                # (pred(u),u)
                if ( v1 is pred[u] and v2 is u ):
                    MST.add_edge(pred[u],u,data)
                elif (  ( v1 is u and v2 is pred[u] ) and
                        ( not nx.is_directed(G) )  ):
                    MST.add_edge(pred[u],u,data)

    return MST

def _create_flow_dict(G, H, infcapFlows, capacity="capacity"):
    """Creates the flow dict of dicts on G corresponding to the
    auxiliary digraph H and infinite capacity edges flows infcapFlows.
    """
    flowDict = {}

    for u in G.nodes_iter():
        if not u in flowDict:
            flowDict[u] = {}
        for v in G.neighbors(u):
            if H.has_edge(u, v):
                try:
                    flowDict[u][v] = abs(G[u][v][capacity] - H[u][v][capacity])
                except KeyError:  # (u, v) has infinite capacity
                    try:
                        flowDict[u][v] = H[v][u][capacity]
                    except KeyError:
                        try:  # Infinite capacity digon in the original graph.
                            if nx.is_directed(G):
                                flowDict[u][v] = max(infcapFlows[(u, v)] - infcapFlows[(v, u)], 0)
                            else:
                                flowDict[u][v] = abs(infcapFlows[(u, v)] - infcapFlows[(v, u)])
                        except KeyError:  # Zero flow
                            flowDict[u][v] = 0
            else:
                flowDict[u][v] = G[u][v][capacity]
    return flowDict

    def matchingVertices(self, graph, trie_node, nodes_used, states):
        candidates = []
        
        if not trie_node.areConditionsRespectedWeak(nodes_used):
            return candidates
        
        min_value = trie_node.getMinLabelForCurrentPos(nodes_used)

        if nodes_used == []:
            candidates = [x for x in graph.nodes() if x >= min_value]
        else:
            cand_graph = graph.to_undirected() if networkx.is_directed(graph) else graph
            connections = [set(cand_graph.neighbors(x)) for x in nodes_used]
            if trie_node.getGraph().degree(trie_node.getGraph().nodes()[len(nodes_used)]) == 0:
                connections.append(set([x for x, y in graph.degree_iter() if y == 0]))
            connections = list(set.union(*connections))
            connections = [x for x in connections if x >= min_value]
            candidates = [x for x in connections if x not in nodes_used]
            
            #Testing the space reduction
            #candidates.sort(key=lambda x: len(graph.neighbors(x)))
            #candidates = [x for x in candidates if len(graph.neighbors(x)) == len(graph.neighbors(candidates[0]))]
            #candidates = [x for x in candidates if x not in nodes_used]
            #candidates = []
            #if len(connections) > 0:
                #candidates = [x for x in graph.neighbors(connections[0]) if x not in nodes_used]
            
        vertices = []
        for node in candidates:
            cand_test = []
            test_nodes = copy.deepcopy(nodes_used)
            test_nodes.append(node)
            if states:
                if graph.node[node] == trie_node.getNodeStates()[len(nodes_used)]:
                    for i in range(0, len(trie_node.getInLinks())):
                        if ((trie_node.getInLinks()[i] == 1 and node in graph.edge[test_nodes[i]] and 
                             trie_node.getInLinkStates()[i] == graph.edge[test_nodes[i]][node]) or 
                            (trie_node.getInLinks()[i] == 0 and node not in graph.edge[test_nodes[i]])) and \
                            ((trie_node.getOutLinks()[i] == 1 and test_nodes[i] in graph.edge[node] and 
                              trie_node.getOutLinkStates()[i] == graph.edge[node][test_nodes[i]]) or
                            (trie_node.getOutLinks()[i] == 0 and test_nodes[i] not in graph.edge[node])):
                            cand_test.append(True)                    
                        else:
                            cand_test.append(False)
                    if False not in cand_test:
                        vertices.append(node)
            else:
                for i in range(0, len(trie_node.getInLinks())):
                    if ((trie_node.getInLinks()[i] == 1 and node in graph.edge[test_nodes[i]]) or 
                        (trie_node.getInLinks()[i] == 0 and node not in graph.edge[test_nodes[i]])) and \
                        ((trie_node.getOutLinks()[i] == 1 and test_nodes[i] in graph.edge[node]) or
                        (trie_node.getOutLinks()[i] == 0 and test_nodes[i] not in graph.edge[node])):
                        cand_test.append(True)                    
                    else:
                        cand_test.append(False)
                if False not in cand_test:
                    vertices.append(node)                
                     
        return vertices

def print_node_edge_data(DG):
    print '#Source----Destination---weight#'
    if(nx.is_directed(DG)):
        for node in DG.nodes_iter():
            for item in DG.adjacency_iter():
                    if item[1].has_key(node):
                            print str(item[0])+'--->'+str(node)+' : '+str(item[1][node])
    else:
        print 'Not a Directed Graph'