def test_create_empty_copy(self):
     G=networkx.create_empty_copy(self.G, with_nodes=False)
     assert_equal(G.nodes(),[])
     assert_equal(G.graph,{})
     assert_equal(G.node,{})
     assert_equal(G.edge,{})
     G=networkx.create_empty_copy(self.G)
     assert_equal(G.nodes(),self.G.nodes())
     assert_equal(G.graph,{})
     assert_equal(G.node,{}.fromkeys(self.G.nodes(),{}))
     assert_equal(G.edge,{}.fromkeys(self.G.nodes(),{}))

 def test_create_empty_copy(self):
     G = nx.create_empty_copy(self.G, with_data=False)
     assert_nodes_equal(G, list(self.G))
     assert_equal(G.graph, {})
     assert_equal(G._node, {}.fromkeys(self.G.nodes(), {}))
     assert_equal(G._adj, {}.fromkeys(self.G.nodes(), {}))
     G = nx.create_empty_copy(self.G)
     assert_nodes_equal(G, list(self.G))
     assert_equal(G.graph, self.G.graph)
     assert_equal(G._node, self.G._node)
     assert_equal(G._adj, {}.fromkeys(self.G.nodes(), {}))

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 allocate_role(self):
        # Make a copy of the graph
        graph = nx.create_empty_copy(self._graph, with_nodes=True)
        graph.add_edges_from(self._graph.edges())

        while len(graph.nodes()) > 0:
            # Try to get a node with degree 1
            nodes = self._get_nodes_with_degree_one(graph)
            if len(nodes) > 0:
                for node in nodes:
                    #if not self._has_p_neighbors(node):
                    # Mark as PE
                    self._graph.node[node]['vrf_role'] = 'PE'
                    # Mark neighbor as P
                    neighbors = graph.neighbors(node)
                    for neighbor in neighbors:
                        self._graph.node[neighbor]['vrf_role'] = 'P'
                graph.remove_node(node)
                graph.remove_nodes_from(neighbors)
                    #else:
                        # Mark as P and remove
                    #    self._graph.node[node]['vrf_role'] = 'P'
                    #    print ' - Mark %s as P' % node
                    #    graph.remove_node(node)
            else:
                node_with_max_degree = self._get_max_degree_node(graph)
                if node_with_max_degree is not None:
                    self._graph.node[node_with_max_degree]['vrf_role'] = 'P'
                    graph.remove_node(node_with_max_degree)

def max_flow(graph, source, sink, attribute='capacity'):
    """Return the maximum flow through a flow network.

    Uses the Edmonds-Karp algorithm.
    Parameters:
    graph -- an nx.Digraph object representing the flow network. Antiparallel
        edges are supported, but other contraints on flow networks must hold.
    source -- The source node on the graph.
    sink -- The sink node on the graph.
    attribute -- the edge attribute containing the capacities.

    Returns: An nx.Digraph representing the flow.
    """
    # Eliminate any antiparallel edges.
    simplified_graph = graph.copy()
    fake_nodes = remove_antiparallel(simplified_graph)

    # Create the empty flow.
    curr_flow = nx.create_empty_copy(simplified_graph)

    # Keep augmenting the flow with paths from the residual network until
    # no more augmenting paths exist.
    can_augment = True
    while can_augment:
        can_augment = augment(simplified_graph, curr_flow,
                              source, sink, attribute)

    # Restore antiparallel edges.
    restore_antiparallel(curr_flow, fake_nodes)

    return curr_flow

def residual_flow(network, flow, attribute='capacity'):
    """Return the residual flow through a flow network.

    Parameters:
    network -- The flow network, represented using an nx.DiGraph object.
    flow -- The flow through the network, also represented by an nx.DiGraph.
    attribute -- The name of the edge attribute containing the capacity.

    Returns: An nx.Digraph representing the residual flow.
    """
    residual = nx.create_empty_copy(network)
    for u, v in network.edges_iter():
        # Get the edge attributes from each graph
        capacity = network[u][v][attribute]
        used = flow[u][v][attribute] if (u, v) in flow.edges() else 0
        excess = capacity - used
        assert excess >= 0, "Flow had edges greater than capacity."

        # Add in any leftover forward capacity.
        if excess > 0:
            residual.add_edge(u, v, {attribute: excess})
        # Add in the decreasing flow residual
        if used > 0:
            residual.add_edge(v, u, {attribute: used})

    return residual