Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/isomorphism/temporalisomorphvf2.py @ 0:4f3585e2f14b draft default tip
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author | shellac |
---|---|
date | Mon, 22 Mar 2021 18:12:50 +0000 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:4f3585e2f14b |
---|---|
1 """ | |
2 ***************************** | |
3 Time-respecting VF2 Algorithm | |
4 ***************************** | |
5 | |
6 An extension of the VF2 algorithm for time-respecting graph ismorphism | |
7 testing in temporal graphs. | |
8 | |
9 A temporal graph is one in which edges contain a datetime attribute, | |
10 denoting when interaction occurred between the incident nodes. A | |
11 time-respecting subgraph of a temporal graph is a subgraph such that | |
12 all interactions incident to a node occurred within a time threshold, | |
13 delta, of each other. A directed time-respecting subgraph has the | |
14 added constraint that incoming interactions to a node must precede | |
15 outgoing interactions from the same node - this enforces a sense of | |
16 directed flow. | |
17 | |
18 Introduction | |
19 ------------ | |
20 | |
21 The TimeRespectingGraphMatcher and TimeRespectingDiGraphMatcher | |
22 extend the GraphMatcher and DiGraphMatcher classes, respectively, | |
23 to include temporal constraints on matches. This is achieved through | |
24 a semantic check, via the semantic_feasibility() function. | |
25 | |
26 As well as including G1 (the graph in which to seek embeddings) and | |
27 G2 (the subgraph structure of interest), the name of the temporal | |
28 attribute on the edges and the time threshold, delta, must be supplied | |
29 as arguments to the matching constructors. | |
30 | |
31 A delta of zero is the strictest temporal constraint on the match - | |
32 only embeddings in which all interactions occur at the same time will | |
33 be returned. A delta of one day will allow embeddings in which | |
34 adjacent interactions occur up to a day apart. | |
35 | |
36 Examples | |
37 -------- | |
38 | |
39 Examples will be provided when the datetime type has been incorporated. | |
40 | |
41 | |
42 Temporal Subgraph Isomorphism | |
43 ----------------------------- | |
44 | |
45 A brief discussion of the somewhat diverse current literature will be | |
46 included here. | |
47 | |
48 References | |
49 ---------- | |
50 | |
51 [1] Redmond, U. and Cunningham, P. Temporal subgraph isomorphism. In: | |
52 The 2013 IEEE/ACM International Conference on Advances in Social | |
53 Networks Analysis and Mining (ASONAM). Niagara Falls, Canada; 2013: | |
54 pages 1451 - 1452. [65] | |
55 | |
56 For a discussion of the literature on temporal networks: | |
57 | |
58 [3] P. Holme and J. Saramaki. Temporal networks. Physics Reports, | |
59 519(3):97–125, 2012. | |
60 | |
61 Notes | |
62 ----- | |
63 | |
64 Handles directed and undirected graphs and graphs with parallel edges. | |
65 | |
66 """ | |
67 | |
68 import networkx as nx | |
69 from .isomorphvf2 import GraphMatcher, DiGraphMatcher | |
70 | |
71 __all__ = ["TimeRespectingGraphMatcher", "TimeRespectingDiGraphMatcher"] | |
72 | |
73 | |
74 class TimeRespectingGraphMatcher(GraphMatcher): | |
75 def __init__(self, G1, G2, temporal_attribute_name, delta): | |
76 """Initialize TimeRespectingGraphMatcher. | |
77 | |
78 G1 and G2 should be nx.Graph or nx.MultiGraph instances. | |
79 | |
80 Examples | |
81 -------- | |
82 To create a TimeRespectingGraphMatcher which checks for | |
83 syntactic and semantic feasibility: | |
84 | |
85 >>> from networkx.algorithms import isomorphism | |
86 >>> from datetime import timedelta | |
87 >>> G1 = nx.Graph(nx.path_graph(4, create_using=nx.Graph())) | |
88 | |
89 >>> G2 = nx.Graph(nx.path_graph(4, create_using=nx.Graph())) | |
90 | |
91 >>> GM = isomorphism.TimeRespectingGraphMatcher( | |
92 ... G1, G2, "date", timedelta(days=1) | |
93 ... ) | |
94 """ | |
95 self.temporal_attribute_name = temporal_attribute_name | |
96 self.delta = delta | |
97 super().__init__(G1, G2) | |
98 | |
99 def one_hop(self, Gx, Gx_node, neighbors): | |
100 """ | |
101 Edges one hop out from a node in the mapping should be | |
102 time-respecting with respect to each other. | |
103 """ | |
104 dates = [] | |
105 for n in neighbors: | |
106 if isinstance(Gx, nx.Graph): # Graph G[u][v] returns the data dictionary. | |
107 dates.append(Gx[Gx_node][n][self.temporal_attribute_name]) | |
108 else: # MultiGraph G[u][v] returns a dictionary of key -> data dictionary. | |
109 for edge in Gx[Gx_node][ | |
110 n | |
111 ].values(): # Iterates all edges between node pair. | |
112 dates.append(edge[self.temporal_attribute_name]) | |
113 if any(x is None for x in dates): | |
114 raise ValueError("Datetime not supplied for at least one edge.") | |
115 return not dates or max(dates) - min(dates) <= self.delta | |
116 | |
117 def two_hop(self, Gx, core_x, Gx_node, neighbors): | |
118 """ | |
119 Paths of length 2 from Gx_node should be time-respecting. | |
120 """ | |
121 return all( | |
122 self.one_hop(Gx, v, [n for n in Gx[v] if n in core_x] + [Gx_node]) | |
123 for v in neighbors | |
124 ) | |
125 | |
126 def semantic_feasibility(self, G1_node, G2_node): | |
127 """Returns True if adding (G1_node, G2_node) is semantically | |
128 feasible. | |
129 | |
130 Any subclass which redefines semantic_feasibility() must | |
131 maintain the self.tests if needed, to keep the match() method | |
132 functional. Implementations should consider multigraphs. | |
133 """ | |
134 neighbors = [n for n in self.G1[G1_node] if n in self.core_1] | |
135 if not self.one_hop(self.G1, G1_node, neighbors): # Fail fast on first node. | |
136 return False | |
137 if not self.two_hop(self.G1, self.core_1, G1_node, neighbors): | |
138 return False | |
139 # Otherwise, this node is semantically feasible! | |
140 return True | |
141 | |
142 | |
143 class TimeRespectingDiGraphMatcher(DiGraphMatcher): | |
144 def __init__(self, G1, G2, temporal_attribute_name, delta): | |
145 """Initialize TimeRespectingDiGraphMatcher. | |
146 | |
147 G1 and G2 should be nx.DiGraph or nx.MultiDiGraph instances. | |
148 | |
149 Examples | |
150 -------- | |
151 To create a TimeRespectingDiGraphMatcher which checks for | |
152 syntactic and semantic feasibility: | |
153 | |
154 >>> from networkx.algorithms import isomorphism | |
155 >>> from datetime import timedelta | |
156 >>> G1 = nx.DiGraph(nx.path_graph(4, create_using=nx.DiGraph())) | |
157 | |
158 >>> G2 = nx.DiGraph(nx.path_graph(4, create_using=nx.DiGraph())) | |
159 | |
160 >>> GM = isomorphism.TimeRespectingDiGraphMatcher( | |
161 ... G1, G2, "date", timedelta(days=1) | |
162 ... ) | |
163 """ | |
164 self.temporal_attribute_name = temporal_attribute_name | |
165 self.delta = delta | |
166 super().__init__(G1, G2) | |
167 | |
168 def get_pred_dates(self, Gx, Gx_node, core_x, pred): | |
169 """ | |
170 Get the dates of edges from predecessors. | |
171 """ | |
172 pred_dates = [] | |
173 if isinstance(Gx, nx.DiGraph): # Graph G[u][v] returns the data dictionary. | |
174 for n in pred: | |
175 pred_dates.append(Gx[n][Gx_node][self.temporal_attribute_name]) | |
176 else: # MultiGraph G[u][v] returns a dictionary of key -> data dictionary. | |
177 for n in pred: | |
178 for edge in Gx[n][ | |
179 Gx_node | |
180 ].values(): # Iterates all edge data between node pair. | |
181 pred_dates.append(edge[self.temporal_attribute_name]) | |
182 return pred_dates | |
183 | |
184 def get_succ_dates(self, Gx, Gx_node, core_x, succ): | |
185 """ | |
186 Get the dates of edges to successors. | |
187 """ | |
188 succ_dates = [] | |
189 if isinstance(Gx, nx.DiGraph): # Graph G[u][v] returns the data dictionary. | |
190 for n in succ: | |
191 succ_dates.append(Gx[Gx_node][n][self.temporal_attribute_name]) | |
192 else: # MultiGraph G[u][v] returns a dictionary of key -> data dictionary. | |
193 for n in succ: | |
194 for edge in Gx[Gx_node][ | |
195 n | |
196 ].values(): # Iterates all edge data between node pair. | |
197 succ_dates.append(edge[self.temporal_attribute_name]) | |
198 return succ_dates | |
199 | |
200 def one_hop(self, Gx, Gx_node, core_x, pred, succ): | |
201 """ | |
202 The ego node. | |
203 """ | |
204 pred_dates = self.get_pred_dates(Gx, Gx_node, core_x, pred) | |
205 succ_dates = self.get_succ_dates(Gx, Gx_node, core_x, succ) | |
206 return self.test_one(pred_dates, succ_dates) and self.test_two( | |
207 pred_dates, succ_dates | |
208 ) | |
209 | |
210 def two_hop_pred(self, Gx, Gx_node, core_x, pred): | |
211 """ | |
212 The predeccessors of the ego node. | |
213 """ | |
214 return all( | |
215 self.one_hop( | |
216 Gx, | |
217 p, | |
218 core_x, | |
219 self.preds(Gx, core_x, p), | |
220 self.succs(Gx, core_x, p, Gx_node), | |
221 ) | |
222 for p in pred | |
223 ) | |
224 | |
225 def two_hop_succ(self, Gx, Gx_node, core_x, succ): | |
226 """ | |
227 The successors of the ego node. | |
228 """ | |
229 return all( | |
230 self.one_hop( | |
231 Gx, | |
232 s, | |
233 core_x, | |
234 self.preds(Gx, core_x, s, Gx_node), | |
235 self.succs(Gx, core_x, s), | |
236 ) | |
237 for s in succ | |
238 ) | |
239 | |
240 def preds(self, Gx, core_x, v, Gx_node=None): | |
241 pred = [n for n in Gx.predecessors(v) if n in core_x] | |
242 if Gx_node: | |
243 pred.append(Gx_node) | |
244 return pred | |
245 | |
246 def succs(self, Gx, core_x, v, Gx_node=None): | |
247 succ = [n for n in Gx.successors(v) if n in core_x] | |
248 if Gx_node: | |
249 succ.append(Gx_node) | |
250 return succ | |
251 | |
252 def test_one(self, pred_dates, succ_dates): | |
253 """ | |
254 Edges one hop out from Gx_node in the mapping should be | |
255 time-respecting with respect to each other, regardless of | |
256 direction. | |
257 """ | |
258 time_respecting = True | |
259 dates = pred_dates + succ_dates | |
260 | |
261 if any(x is None for x in dates): | |
262 raise ValueError("Date or datetime not supplied for at least one edge.") | |
263 | |
264 dates.sort() # Small to large. | |
265 if 0 < len(dates) and not (dates[-1] - dates[0] <= self.delta): | |
266 time_respecting = False | |
267 return time_respecting | |
268 | |
269 def test_two(self, pred_dates, succ_dates): | |
270 """ | |
271 Edges from a dual Gx_node in the mapping should be ordered in | |
272 a time-respecting manner. | |
273 """ | |
274 time_respecting = True | |
275 pred_dates.sort() | |
276 succ_dates.sort() | |
277 # First out before last in; negative of the necessary condition for time-respect. | |
278 if ( | |
279 0 < len(succ_dates) | |
280 and 0 < len(pred_dates) | |
281 and succ_dates[0] < pred_dates[-1] | |
282 ): | |
283 time_respecting = False | |
284 return time_respecting | |
285 | |
286 def semantic_feasibility(self, G1_node, G2_node): | |
287 """Returns True if adding (G1_node, G2_node) is semantically | |
288 feasible. | |
289 | |
290 Any subclass which redefines semantic_feasibility() must | |
291 maintain the self.tests if needed, to keep the match() method | |
292 functional. Implementations should consider multigraphs. | |
293 """ | |
294 pred, succ = ( | |
295 [n for n in self.G1.predecessors(G1_node) if n in self.core_1], | |
296 [n for n in self.G1.successors(G1_node) if n in self.core_1], | |
297 ) | |
298 if not self.one_hop( | |
299 self.G1, G1_node, self.core_1, pred, succ | |
300 ): # Fail fast on first node. | |
301 return False | |
302 if not self.two_hop_pred(self.G1, G1_node, self.core_1, pred): | |
303 return False | |
304 if not self.two_hop_succ(self.G1, G1_node, self.core_1, succ): | |
305 return False | |
306 # Otherwise, this node is semantically feasible! | |
307 return True |