"""
Line graphs.

"""
#    Copyright (C) 2010 by 
#    Aric Hagberg <hagberg@lanl.gov>
#    Dan Schult <dschult@colgate.edu>
#    Pieter Swart <swart@lanl.gov>
#    All rights reserved.
#    BSD license.
__author__ = """Aric Hagberg (hagberg@lanl.gov)\nPieter Swart (swart@lanl.gov)\nDan Schult(dschult@colgate.edu)"""

__all__ = ['line_graph']

import networkx as nx

def line_graph(G):
    """Return the line graph of the graph or digraph G.

    The line graph of a graph G has a node for each edge 
    in G and an edge between those nodes if the two edges
    in G share a common node.

    For DiGraphs an edge an edge represents a directed path of length 2.

    The original node labels are kept as two-tuple node labels
    in the line graph.  

    Parameters
    ----------
    G : graph
       A NetworkX Graph or DiGraph

    Examples
    --------    
    >>> G=nx.star_graph(3)
    >>> L=nx.line_graph(G)
    >>> print(sorted(L.edges())) # makes a clique, K3
    [((0, 1), (0, 2)), ((0, 1), (0, 3)), ((0, 3), (0, 2))]

    Notes
    -----
    Not implemented for MultiGraph or MultiDiGraph classes.

    Graph, node, and edge data are not propagated to the new graph.

    """
    if type(G) == nx.MultiGraph or type(G) == nx.MultiDiGraph:
        raise Exception("Line graph not implemented for Multi(Di)Graphs")
    L=G.__class__()
    if G.is_directed():
        for u,nlist in G.adjacency_iter():  # same as successors for digraph
            # look for directed path of length two
            for n in nlist:
                nbrs=G[n] # successors 
                for nbr in nbrs:
                    if nbr!=u:
                        L.add_edge((u,n),(n,nbr))
    else:
        for u,nlist in G.adjacency_iter():
            # label nodes as tuple of edge endpoints in original graph
            # "node tuple" must be in lexigraphical order
            nodes=[tuple(sorted(n)) for n in zip([u]*len(nlist),nlist)]
            # add clique of nodes to graph
            while nodes:
                u=nodes.pop()
                L.add_edges_from((u,v) for v in nodes)
    return L