Skip to main content
`Ctrl`+`K`

# inverse_line_graph

inverse_line_graph(G)

  Returns the inverse line graph of graph G.

  If H is a graph, and G is the line graph of H, such that G = L(H). 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 function raises a NetworkXError.

  Parameters:
    G graph

      A NetworkX Graph

  Returns:
    H graph

      The inverse line graph of G.

  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[R90abc5507a69-1]_.

  If G consists of multiple components, then the algorithm doesn’t work. You should invert every component separately:

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

  [1]

  Roussopoulos, N.D. , “A max {m, n} algorithm for determining the graph H from its line graph G”, Information Processing Letters 2, (1973), 108–112, ISSN 0020-0190, DOI link