networkx.generators.line.line_graph¶

line_graph
(G, create_using=None)[source]¶ Returns the line graph of the graph or digraph
G
.The line graph of a graph
G
has a node for each edge inG
and an edge joining those nodes if the two edges inG
share a common node. For directed graphs, nodes are adjacent exactly when the edges they represent form a directed path of length two.The nodes of the line graph are 2tuples of nodes in the original graph (or 3tuples for multigraphs, with the key of the edge as the third element).
For information about selfloops and more discussion, see the Notes section below.
 Parameters
G (graph) – A NetworkX Graph, DiGraph, MultiGraph, or MultiDigraph.
create_using (NetworkX graph constructor, optional (default=nx.Graph)) – Graph type to create. If graph instance, then cleared before populated.
 Returns
L – The line graph of G.
 Return type
graph
Examples
>>> G = nx.star_graph(3) >>> L = nx.line_graph(G) >>> print(sorted(map(sorted, L.edges()))) # makes a 3clique, K3 [[(0, 1), (0, 2)], [(0, 1), (0, 3)], [(0, 2), (0, 3)]]
Notes
Graph, node, and edge data are not propagated to the new graph. For undirected graphs, the nodes in G must be sortable, otherwise the constructed line graph may not be correct.
Selfloops in undirected graphs
For an undirected graph
G
without multiple edges, each edge can be written as a set{u, v}
. Its line graphL
has the edges ofG
as its nodes. Ifx
andy
are two nodes inL
, then{x, y}
is an edge inL
if and only if the intersection ofx
andy
is nonempty. Thus, the set of all edges is determined by the set of all pairwise intersections of edges inG
.Trivially, every edge in G would have a nonzero intersection with itself, and so every node in
L
should have a selfloop. This is not so interesting, and the original context of line graphs was with simple graphs, which had no selfloops or multiple edges. The line graph was also meant to be a simple graph and thus, selfloops inL
are not part of the standard definition of a line graph. In a pairwise intersection matrix, this is analogous to excluding the diagonal entries from the line graph definition.Selfloops and multiple edges in
G
add nodes toL
in a natural way, and do not require any fundamental changes to the definition. It might be argued that the selfloops we excluded before should now be included. However, the selfloops are still “trivial” in some sense and thus, are usually excluded.Selfloops in directed graphs
For a directed graph
G
without multiple edges, each edge can be written as a tuple(u, v)
. Its line graphL
has the edges ofG
as its nodes. Ifx
andy
are two nodes inL
, then(x, y)
is an edge inL
if and only if the tail ofx
matches the head ofy
, for example, ifx = (a, b)
andy = (b, c)
for some verticesa
,b
, andc
inG
.Due to the directed nature of the edges, it is no longer the case that every edge in
G
should have a selfloop inL
. Now, the only time selfloops arise is if a node inG
itself has a selfloop. So such selfloops are no longer “trivial” but instead, represent essential features of the topology ofG
. For this reason, the historical development of line digraphs is such that selfloops are included. When the graphG
has multiple edges, once again only superficial changes are required to the definition.References
Harary, Frank, and Norman, Robert Z., “Some properties of line digraphs”, Rend. Circ. Mat. Palermo, II. Ser. 9 (1960), 161–168.
Hemminger, R. L.; Beineke, L. W. (1978), “Line graphs and line digraphs”, in Beineke, L. W.; Wilson, R. J., Selected Topics in Graph Theory, Academic Press Inc., pp. 271–305.