diff env/lib/python3.9/site-packages/networkx/generators/interval_graph.py @ 0:4f3585e2f14b draft default tip

"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author shellac
date Mon, 22 Mar 2021 18:12:50 +0000
parents
children
line wrap: on
line diff
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/env/lib/python3.9/site-packages/networkx/generators/interval_graph.py	Mon Mar 22 18:12:50 2021 +0000
@@ -0,0 +1,69 @@
+"""
+Generators for interval graph.
+"""
+from collections.abc import Sequence
+import networkx as nx
+
+__all__ = ["interval_graph"]
+
+
+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. " f"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