| """ |
| 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 |
| |
