networkx.generators.line.inverse_line_graph¶
-
inverse_line_graph
(G)[source]¶ Returns the inverse line graph of graph G.
If H is a graph, and G is the line graph of H, such that H = L(G). Then H is the inverse line graph of G.
Not all graphs are line graphs and these do not have an inverse line graph. In these cases this generator returns a NetworkXError.
- Parameters
G (graph) – A NetworkX Graph
- Returns
H – The inverse line graph of G.
- Return type
graph
- Raises
NetworkXNotImplemented – If G is directed or a multigraph
NetworkXError – If G is not a line graph
Notes
This is an implementation of the Roussopoulos algorithm.
If G consists of multiple components, then the algorithm doesn’t work. You should invert every component seperately:
>>> K5 = nx.complete_graph(5) >>> P4 = nx.Graph([("a", "b"), ("b", "c"), ("c", "d")]) >>> G = nx.union(K5, P4) >>> root_graphs = [] >>> for comp in nx.connected_components(G): ... root_graphs.append(nx.inverse_line_graph(G.subgraph(comp))) >>> len(root_graphs) 2
References
Roussopolous, N, “A max {m, n} algorithm for determining the graph H from its line graph G”, Information Processing Letters 2, (1973), 108–112.