Skip to main content
`Ctrl`+`K`

# Source code for networkx.generators.line

    """Functions for generating line graphs."""

    from collections import defaultdict
    from functools import partial
    from itertools import combinations

    import networkx as nx
    from networkx.utils import arbitrary_element
    from networkx.utils.decorators import not_implemented_for

    __all__ = ["line_graph", "inverse_line_graph"]

    @nx._dispatchable(returns_graph=True)
    def line_graph(G, create_using=None):
        r"""Returns 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 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.

        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 : graph
            The line graph of G.

        Examples
        --------
        >>> G = nx.star_graph(3)
        >>> 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)]]

        Edge attributes from `G` are not copied over as node attributes in `L`, but
        attributes can be copied manually:

        >>> G = nx.path_graph(4)
        >>> G.add_edges_from((u, v, {"tot": u + v}) for u, v in G.edges)
        >>> G.edges(data=True)
        EdgeDataView([(0, 1, {'tot': 1}), (1, 2, {'tot': 3}), (2, 3, {'tot': 5})])
        >>> H = nx.line_graph(G)
        >>> H.add_nodes_from((node, G.edges[node]) for node in H)
        >>> H.nodes(data=True)
        NodeDataView({(0, 1): {'tot': 1}, (2, 3): {'tot': 5}, (1, 2): {'tot': 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.

        *Self-loops in undirected graphs*

        For an undirected graph `G` without multiple edges, each edge can be
        written as a set `\{u, v\}`.  Its line graph `L` has the edges of `G` as
        its nodes. If `x` and `y` are two nodes in `L`, then `\{x, y\}` is an edge
        in `L` if and only if the intersection of `x` and `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 `(u, v)`. Its line graph `L` has the edges of `G` as its
        nodes. If `x` and `y` are two nodes in `L`, then `(x, y)` is an edge in `L`
        if and only if the tail of `x` matches the head of `y`, for example, if `x
        = (a, b)` and `y = (b, c)` for some vertices `a`, `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.

        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.

        """
        if G.is_directed():
            L = _lg_directed(G, create_using=create_using)
        else:
            L = _lg_undirected(G, selfloops=False, create_using=create_using)
        return L

    def _lg_directed(G, create_using=None):
        """Returns the line graph L of the (multi)digraph G.

        Edges in G appear as nodes in L, represented as tuples of the form (u,v)
        or (u,v,key) if G is a multidigraph. A node in L corresponding to the edge
        (u,v) is connected to every node corresponding to an edge (v,w).

        Parameters
        ----------
        G : digraph
            A directed graph or directed multigraph.
        create_using : NetworkX graph constructor, optional
           Graph type to create. If graph instance, then cleared before populated.
           Default is to use the same graph class as `G`.

        """
        L = nx.empty_graph(0, create_using, default=G.__class__)

        # Create a graph specific edge function.
        get_edges = partial(G.edges, keys=True) if G.is_multigraph() else G.edges

        for from_node in get_edges():
            # from_node is: (u,v) or (u,v,key)
            L.add_node(from_node)
            for to_node in get_edges(from_node[1]):
                L.add_edge(from_node, to_node)

        return L

    def _lg_undirected(G, selfloops=False, create_using=None):
        """Returns the line graph L of the (multi)graph G.

        Edges in G appear as nodes in L, represented as sorted tuples of the form
        (u,v), or (u,v,key) if G is a multigraph. A node in L corresponding to
        the edge {u,v} is connected to every node corresponding to an edge that
        involves u or v.

        Parameters
        ----------
        G : graph
            An undirected graph or multigraph.
        selfloops : bool
            If `True`, then self-loops are included in the line graph. If `False`,
            they are excluded.
        create_using : NetworkX graph constructor, optional (default=nx.Graph)
           Graph type to create. If graph instance, then cleared before populated.

        Notes
        -----
        The standard algorithm for line graphs of undirected graphs does not
        produce self-loops.

        """
        L = nx.empty_graph(0, create_using, default=G.__class__)

        # Graph specific functions for edges.
        get_edges = partial(G.edges, keys=True) if G.is_multigraph() else G.edges

        # Determine if we include self-loops or not.
        shift = 0 if selfloops else 1

        # Introduce numbering of nodes
        node_index = {n: i for i, n in enumerate(G)}

        # Lift canonical representation of nodes to edges in line graph
        edge_key_function = lambda edge: (node_index[edge[0]], node_index[edge[1]])

        edges = set()
        for u in G:
            # Label nodes as a sorted tuple of nodes in original graph.
            # Decide on representation of {u, v} as (u, v) or (v, u) depending on node_index.
            # -> This ensures a canonical representation and avoids comparing values of different types.
            nodes = [tuple(sorted(x[:2], key=node_index.get)) + x[2:] for x in get_edges(u)]

            if len(nodes) == 1:
                # Then the edge will be an isolated node in L.
                L.add_node(nodes[0])

            # Add a clique of `nodes` to graph. To prevent double adding edges,
            # especially important for multigraphs, we store the edges in
            # canonical form in a set.
            for i, a in enumerate(nodes):
                edges.update(
                    [
                        tuple(sorted((a, b), key=edge_key_function))
                        for b in nodes[i + shift :]
                    ]
                )

        L.add_edges_from(edges)
        return L

    @not_implemented_for("directed")
    @not_implemented_for("multigraph")
    @nx._dispatchable(returns_graph=True)
    def 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[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 <https://doi.org/10.1016/0020-0190(73)90029-X>`_

        """
        if G.number_of_nodes() == 0:
            return nx.empty_graph(1)
        elif G.number_of_nodes() == 1:
            v = arbitrary_element(G)
            a = (v, 0)
            b = (v, 1)
            H = nx.Graph([(a, b)])
            return H
        elif G.number_of_nodes() > 1 and G.number_of_edges() == 0:
            msg = (
                "inverse_line_graph() doesn't work on an edgeless graph. "
                "Please use this function on each component separately."
            )
            raise nx.NetworkXError(msg)

        if nx.number_of_selfloops(G) != 0:
            msg = (
                "A line graph as generated by NetworkX has no selfloops, so G has no "
                "inverse line graph. Please remove the selfloops from G and try again."
            )
            raise nx.NetworkXError(msg)

        starting_cell = _select_starting_cell(G)
        P = _find_partition(G, starting_cell)
        # count how many times each vertex appears in the partition set
        P_count = {u: 0 for u in G.nodes}
        for p in P:
            for u in p:
                P_count[u] += 1

        if max(P_count.values()) > 2:
            msg = "G is not a line graph (vertex found in more than two partition cells)"
            raise nx.NetworkXError(msg)
        W = tuple((u,) for u in P_count if P_count[u] == 1)
        H = nx.Graph()
        H.add_nodes_from(P)
        H.add_nodes_from(W)
        for a, b in combinations(H.nodes, 2):
            if any(a_bit in b for a_bit in a):
                H.add_edge(a, b)
        return H

    def _triangles(G, e):
        """Return list of all triangles containing edge e"""
        u, v = e
        if u not in G:
            raise nx.NetworkXError(f"Vertex {u} not in graph")
        if v not in G[u]:
            raise nx.NetworkXError(f"Edge ({u}, {v}) not in graph")
        triangle_list = []
        for x in G[u]:
            if x in G[v]:
                triangle_list.append((u, v, x))
        return triangle_list

    def _odd_triangle(G, T):
        """Test whether T is an odd triangle in G

        Parameters
        ----------
        G : NetworkX Graph
        T : 3-tuple of vertices forming triangle in G

        Returns
        -------
        True is T is an odd triangle
        False otherwise

        Raises
        ------
        NetworkXError
            T is not a triangle in G

        Notes
        -----
        An odd triangle is one in which there exists another vertex in G which is
        adjacent to either exactly one or exactly all three of the vertices in the
        triangle.

        """
        for u in T:
            if u not in G.nodes():
                raise nx.NetworkXError(f"Vertex {u} not in graph")
        for e in list(combinations(T, 2)):
            if e[0] not in G[e[1]]:
                raise nx.NetworkXError(f"Edge ({e[0]}, {e[1]}) not in graph")

        T_nbrs = defaultdict(int)
        for t in T:
            for v in G[t]:
                if v not in T:
                    T_nbrs[v] += 1
        return any(T_nbrs[v] in [1, 3] for v in T_nbrs)

    def _find_partition(G, starting_cell):
        """Find a partition of the vertices of G into cells of complete graphs

        Parameters
        ----------
        G : NetworkX Graph
        starting_cell : tuple of vertices in G which form a cell

        Returns
        -------
        List of tuples of vertices of G

        Raises
        ------
        NetworkXError
            If a cell is not a complete subgraph then G is not a line graph
        """
        G_partition = G.copy()
        P = [starting_cell]  # partition set
        G_partition.remove_edges_from(list(combinations(starting_cell, 2)))
        # keep list of partitioned nodes which might have an edge in G_partition
        partitioned_vertices = list(starting_cell)
        while G_partition.number_of_edges() > 0:
            # there are still edges left and so more cells to be made
            u = partitioned_vertices.pop()
            deg_u = len(G_partition[u])
            if deg_u != 0:
                # if u still has edges then we need to find its other cell
                # this other cell must be a complete subgraph or else G is
                # not a line graph
                new_cell = [u] + list(G_partition[u])
                for u in new_cell:
                    for v in new_cell:
                        if (u != v) and (v not in G_partition[u]):
                            msg = (
                                "G is not a line graph "
                                "(partition cell not a complete subgraph)"
                            )
                            raise nx.NetworkXError(msg)
                P.append(tuple(new_cell))
                G_partition.remove_edges_from(list(combinations(new_cell, 2)))
                partitioned_vertices += new_cell
        return P

    def _select_starting_cell(G, starting_edge=None):
        """Select a cell to initiate _find_partition

        Parameters
        ----------
        G : NetworkX Graph
        starting_edge: an edge to build the starting cell from

        Returns
        -------
        Tuple of vertices in G

        Raises
        ------
        NetworkXError
            If it is determined that G is not a line graph

        Notes
        -----
        If starting edge not specified then pick an arbitrary edge - doesn't
        matter which. However, this function may call itself requiring a
        specific starting edge. Note that the r, s notation for counting
        triangles is the same as in the Roussopoulos paper cited above.
        """
        if starting_edge is None:
            e = arbitrary_element(G.edges())
        else:
            e = starting_edge
            if e[0] not in G.nodes():
                raise nx.NetworkXError(f"Vertex {e[0]} not in graph")
            if e[1] not in G[e[0]]:
                msg = f"starting_edge ({e[0]}, {e[1]}) is not in the Graph"
                raise nx.NetworkXError(msg)
        e_triangles = _triangles(G, e)
        r = len(e_triangles)
        if r == 0:
            # there are no triangles containing e, so the starting cell is just e
            starting_cell = e
        elif r == 1:
            # there is exactly one triangle, T, containing e. If other 2 edges
            # of T belong only to this triangle then T is starting cell
            T = e_triangles[0]
            a, b, c = T
            # ab was original edge so check the other 2 edges
            ac_edges = len(_triangles(G, (a, c)))
            bc_edges = len(_triangles(G, (b, c)))
            if ac_edges == 1:
                if bc_edges == 1:
                    starting_cell = T
                else:
                    return _select_starting_cell(G, starting_edge=(b, c))
            else:
                return _select_starting_cell(G, starting_edge=(a, c))
        else:
            # r >= 2 so we need to count the number of odd triangles, s
            s = 0
            odd_triangles = []
            for T in e_triangles:
                if _odd_triangle(G, T):
                    s += 1
                    odd_triangles.append(T)
            if r == 2 and s == 0:
                # in this case either triangle works, so just use T
                starting_cell = T
            elif r - 1 <= s <= r:
                # check if odd triangles containing e form complete subgraph
                triangle_nodes = set()
                for T in odd_triangles:
                    for x in T:
                        triangle_nodes.add(x)

                for u in triangle_nodes:
                    for v in triangle_nodes:
                        if u != v and (v not in G[u]):
                            msg = (
                                "G is not a line graph (odd triangles "
                                "do not form complete subgraph)"
                            )
                            raise nx.NetworkXError(msg)
                # otherwise then we can use this as the starting cell
                starting_cell = tuple(triangle_nodes)

            else:
                msg = (
                    "G is not a line graph (incorrect number of "
                    "odd triangles around starting edge)"
                )
                raise nx.NetworkXError(msg)
        return starting_cell