Skip to main content
`Ctrl`+`K`

# Source code for networkx.generators.interval_graph

    """
    Generators for interval graph.
    """

    from collections.abc import Sequence

    import networkx as nx

    __all__ = ["interval_graph"]

    @nx._dispatchable(graphs=None, returns_graph=True)
    def interval_graph(intervals):
        """Generates an interval graph for a list of intervals given.

        In graph theory, an interval graph is an undirected graph formed from a set
        of closed intervals on the real line, with a vertex for each interval
        and an edge between vertices whose intervals intersect.
        It is the intersection graph of the intervals.

        More information can be found at:
        https://en.wikipedia.org/wiki/Interval_graph

        Parameters
        ----------
        intervals : a sequence of intervals, say (l, r) where l is the left end,
        and r is the right end of the closed interval.

        Returns
        -------
        G : networkx graph

        Examples
        --------
        >>> intervals = [(-2, 3), [1, 4], (2, 3), (4, 6)]
        >>> G = nx.interval_graph(intervals)
        >>> sorted(G.edges)
        [((-2, 3), (1, 4)), ((-2, 3), (2, 3)), ((1, 4), (2, 3)), ((1, 4), (4, 6))]

        Raises
        ------
        :exc:`TypeError`
            if `intervals` contains None or an element which is not
            collections.abc.Sequence or not a length of 2.
        :exc:`ValueError`
            if `intervals` contains an interval such that min1 > max1
            where min1,max1 = interval
        """
        intervals = list(intervals)
        for interval in intervals:
            if not (isinstance(interval, Sequence) and len(interval) == 2):
                raise TypeError(
                    "Each interval must have length 2, and be a "
                    "collections.abc.Sequence such as tuple or list."
                )
            if interval[0] > interval[1]:
                raise ValueError(f"Interval must have lower value first. Got {interval}")

        graph = nx.Graph()

        tupled_intervals = [tuple(interval) for interval in intervals]
        graph.add_nodes_from(tupled_intervals)

        while tupled_intervals:
            min1, max1 = interval1 = tupled_intervals.pop()
            for interval2 in tupled_intervals:
                min2, max2 = interval2
                if max1 >= min2 and max2 >= min1:
                    graph.add_edge(interval1, interval2)
        return graph