### annotate env/lib/python3.9/site-packages/networkx/generators/interval_graph.py @ 0:4f3585e2f14bdraftdefaulttip

author shellac Mon, 22 Mar 2021 18:12:50 +0000
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
0
shellac
parents:
diff changeset
1 """
shellac
parents:
diff changeset
2 Generators for interval graph.
shellac
parents:
diff changeset
3 """
shellac
parents:
diff changeset
4 from collections.abc import Sequence
shellac
parents:
diff changeset
5 import networkx as nx
shellac
parents:
diff changeset
6
shellac
parents:
diff changeset
7 __all__ = ["interval_graph"]
shellac
parents:
diff changeset
8
shellac
parents:
diff changeset
9
shellac
parents:
diff changeset
10 def interval_graph(intervals):
shellac
parents:
diff changeset
11 """ Generates an interval graph for a list of intervals given.
shellac
parents:
diff changeset
12
shellac
parents:
diff changeset
13 In graph theory, an interval graph is an undirected graph formed from a set
shellac
parents:
diff changeset
14 of closed intervals on the real line, with a vertex for each interval
shellac
parents:
diff changeset
15 and an edge between vertices whose intervals intersect.
shellac
parents:
diff changeset
16 It is the intersection graph of the intervals.
shellac
parents:
diff changeset
17
shellac
parents:
diff changeset
shellac
parents:
diff changeset
19 https://en.wikipedia.org/wiki/Interval_graph
shellac
parents:
diff changeset
20
shellac
parents:
diff changeset
21 Parameters
shellac
parents:
diff changeset
22 ----------
shellac
parents:
diff changeset
23 intervals : a sequence of intervals, say (l, r) where l is the left end,
shellac
parents:
diff changeset
24 and r is the right end of the closed interval.
shellac
parents:
diff changeset
25
shellac
parents:
diff changeset
26 Returns
shellac
parents:
diff changeset
27 -------
shellac
parents:
diff changeset
28 G : networkx graph
shellac
parents:
diff changeset
29
shellac
parents:
diff changeset
30 Examples
shellac
parents:
diff changeset
31 --------
shellac
parents:
diff changeset
32 >>> intervals = [(-2, 3), [1, 4], (2, 3), (4, 6)]
shellac
parents:
diff changeset
33 >>> G = nx.interval_graph(intervals)
shellac
parents:
diff changeset
34 >>> sorted(G.edges)
shellac
parents:
diff changeset
35 [((-2, 3), (1, 4)), ((-2, 3), (2, 3)), ((1, 4), (2, 3)), ((1, 4), (4, 6))]
shellac
parents:
diff changeset
36
shellac
parents:
diff changeset
37 Raises
shellac
parents:
diff changeset
38 --------
shellac
parents:
diff changeset
39 :exc:`TypeError`
shellac
parents:
diff changeset
40 if `intervals` contains None or an element which is not
shellac
parents:
diff changeset
41 collections.abc.Sequence or not a length of 2.
shellac
parents:
diff changeset
42 :exc:`ValueError`
shellac
parents:
diff changeset
43 if `intervals` contains an interval such that min1 > max1
shellac
parents:
diff changeset
44 where min1,max1 = interval
shellac
parents:
diff changeset
45 """
shellac
parents:
diff changeset
46 intervals = list(intervals)
shellac
parents:
diff changeset
47 for interval in intervals:
shellac
parents:
diff changeset
48 if not (isinstance(interval, Sequence) and len(interval) == 2):
shellac
parents:
diff changeset
49 raise TypeError(
shellac
parents:
diff changeset
50 "Each interval must have length 2, and be a "
shellac
parents:
diff changeset
51 "collections.abc.Sequence such as tuple or list."
shellac
parents:
diff changeset
52 )
shellac
parents:
diff changeset
53 if interval[0] > interval[1]:
shellac
parents:
diff changeset
54 raise ValueError(
shellac
parents:
diff changeset
55 f"Interval must have lower value first. " f"Got {interval}"
shellac
parents:
diff changeset
56 )
shellac
parents:
diff changeset
57
shellac
parents:
diff changeset
58 graph = nx.Graph()
shellac
parents:
diff changeset
59
shellac
parents:
diff changeset
60 tupled_intervals = [tuple(interval) for interval in intervals]
shellac
parents:
diff changeset
shellac
parents:
diff changeset
62
shellac
parents:
diff changeset
63 while tupled_intervals:
shellac
parents:
diff changeset
64 min1, max1 = interval1 = tupled_intervals.pop()
shellac
parents:
diff changeset
65 for interval2 in tupled_intervals:
shellac
parents:
diff changeset
66 min2, max2 = interval2
shellac
parents:
diff changeset
67 if max1 >= min2 and max2 >= min1: