#    Copyright (C) 2006-2013 by
#    Aric Hagberg <hagberg@lanl.gov>
#    Dan Schult <dschult@colgate.edu>
#    Pieter Swart <swart@lanl.gov>
#    All rights reserved.
#    BSD license.
import networkx as nx
__author__ = """\n""".join(['Aric Hagberg <aric.hagberg@gmail.com>',
                           'Pieter Swart (swart@lanl.gov)',
                           'Dan Schult (dschult@colgate.edu)'])
__all__ = ['convert_node_labels_to_integers', 'relabel_nodes']

def relabel_nodes(G, mapping, copy=True):
    """Relabel the nodes of the graph G.

    Parameters
    ----------
    G : graph
       A NetworkX graph

    mapping : dictionary
       A dictionary with the old labels as keys and new labels as values.
       A partial mapping is allowed.

    copy : bool (optional, default=True)
       If True return a copy, or if False relabel the nodes in place.

    Examples
    --------
    >>> G=nx.path_graph(3)  # nodes 0-1-2
    >>> mapping={0:'a',1:'b',2:'c'}
    >>> H=nx.relabel_nodes(G,mapping)
    >>> print(sorted(H.nodes()))
    ['a', 'b', 'c']

    >>> G=nx.path_graph(26) # nodes 0..25
    >>> mapping=dict(zip(G.nodes(),"abcdefghijklmnopqrstuvwxyz"))
    >>> H=nx.relabel_nodes(G,mapping) # nodes a..z
    >>> mapping=dict(zip(G.nodes(),range(1,27)))
    >>> G1=nx.relabel_nodes(G,mapping) # nodes 1..26

    Partial in-place mapping:

    >>> G=nx.path_graph(3)  # nodes 0-1-2
    >>> mapping={0:'a',1:'b'} # 0->'a' and 1->'b'
    >>> G=nx.relabel_nodes(G,mapping, copy=False)

    print(G.nodes())
    [2, 'b', 'a']

    Mapping as function:

    >>> G=nx.path_graph(3)
    >>> def mapping(x):
    ...    return x**2
    >>> H=nx.relabel_nodes(G,mapping)
    >>> print(H.nodes())
    [0, 1, 4]

    Notes
    -----
    Only the nodes specified in the mapping will be relabeled.

    The keyword setting copy=False modifies the graph in place.
    This is not always possible if the mapping is circular.
    In that case use copy=True.

    See Also
    --------
    convert_node_labels_to_integers
    """
    # you can pass a function f(old_label)->new_label
    # but we'll just make a dictionary here regardless
    if not hasattr(mapping,"__getitem__"):
        m = dict((n, mapping(n)) for n in G)
    else:
        m = mapping
    if copy:
        return _relabel_copy(G, m)
    else:
        return _relabel_inplace(G, m)


def _relabel_inplace(G, mapping):
    old_labels = set(mapping.keys())
    new_labels = set(mapping.values())
    if len(old_labels & new_labels) > 0:
        # labels sets overlap
        # can we topological sort and still do the relabeling?
        D = nx.DiGraph(list(mapping.items()))
        D.remove_edges_from(D.selfloop_edges())
        try:
            nodes = nx.topological_sort(D, reverse=True)
        except nx.NetworkXUnfeasible:
            raise nx.NetworkXUnfeasible('The node label sets are overlapping '
                                        'and no ordering can resolve the '
                                        'mapping. Use copy=True.')
    else:
        # non-overlapping label sets
        nodes = old_labels

    multigraph = G.is_multigraph()
    directed = G.is_directed()

    for old in nodes:
        try:
            new = mapping[old]
        except KeyError:
            continue
        if new == old:
            continue
        try:
            G.add_node(new, attr_dict=G.node[old])
        except KeyError:
            raise KeyError("Node %s is not in the graph"%old)
        if multigraph:
            new_edges = [(new, new if old == target else target, key, data)