line_graph(G, create_using=None)
The line graph of a graph G has a node for each edge in G and an edge joining those nodes if the two edges in G 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 2-tuples of nodes in the original graph (or 3-tuples for multigraphs, with the key of the edge as the third element).
For information about self-loops and more discussion, see the Notes section below.
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.
Self-loops in undirected graphs
For an undirected graph G without multiple edges, each edge can be written as a set :None:None:`\{u, v\}`. Its line graph L has the edges of G as its nodes. If :None:None:`x` and :None:None:`y` are two nodes in L, then :None:None:`\{x, y\}` is an edge in L if and only if the intersection of :None:None:`x` and :None:None:`y` is nonempty. Thus, the set of all edges is determined by the set of all pairwise intersections of edges in G.
Trivially, every edge in G would have a nonzero intersection with itself, and so every node in L should have a self-loop. This is not so interesting, and the original context of line graphs was with simple graphs, which had no self-loops or multiple edges. The line graph was also meant to be a simple graph and thus, self-loops in L 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.
Self-loops and multiple edges in G add nodes to L in a natural way, and do not require any fundamental changes to the definition. It might be argued that the self-loops we excluded before should now be included. However, the self-loops are still "trivial" in some sense and thus, are usually excluded.
Self-loops in directed graphs
For a directed graph G without multiple edges, each edge can be written as a tuple :None:None:`(u, v)`. Its line graph L has the edges of G as its nodes. If :None:None:`x` and :None:None:`y` are two nodes in L, then :None:None:`(x, y)` is an edge in L if and only if the tail of :None:None:`x` matches the head of :None:None:`y`, for example, if :None:None:`x
= (a, b)` and :None:None:`y = (b, c)` for some vertices a, :None:None:`b`, and c in G.
Due to the directed nature of the edges, it is no longer the case that every edge in G should have a self-loop in L. Now, the only time self-loops arise is if a node in G itself has a self-loop. So such self-loops are no longer "trivial" but instead, represent essential features of the topology of G. For this reason, the historical development of line digraphs is such that self-loops are included. When the graph G has multiple edges, once again only superficial changes are required to the definition.
A NetworkX Graph, DiGraph, MultiGraph, or MultiDigraph.
Graph type to create. If graph instance, then cleared before populated.
The line graph of G.
Returns the line graph of the graph or digraph G.
>>> G = nx.star_graph(3)See :
... L = nx.line_graph(G)
... print(sorted(map(sorted, L.edges()))) # makes a 3-clique, K3 [[(0, 1), (0, 2)], [(0, 1), (0, 3)], [(0, 2), (0, 3)]]
The following pages refer to to this document either explicitly or contain code examples using this.
networkx.algorithms.dag.topological_sort
networkx.generators.line.line_graph
Hover to see nodes names; edges to Self not shown, Caped at 50 nodes.
Using a canvas is more power efficient and can get hundred of nodes ; but does not allow hyperlinks; , arrows or text (beyond on hover)
SVG is more flexible but power hungry; and does not scale well to 50 + nodes.
All aboves nodes referred to, (or are referred from) current nodes; Edges from Self to other have been omitted (or all nodes would be connected to the central node "self" which is not useful). Nodes are colored by the library they belong to, and scaled with the number of references pointing them