Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1"""
2Algorithm for testing d-separation in DAGs.
4*d-separation* is a test for conditional independence in probability
5distributions that can be factorized using DAGs. It is a purely
6graphical test that uses the underlying graph and makes no reference
7to the actual distribution parameters. See [1]_ for a formal
8definition.
10The implementation is based on the conceptually simple linear time
11algorithm presented in [2]_. Refer to [3]_, [4]_ for a couple of
12alternative algorithms.
14The functional interface in NetworkX consists of three functions:
16- `find_minimal_d_separator` returns a minimal d-separator set ``z``.
17 That is, removing any node or nodes from it makes it no longer a d-separator.
18- `is_d_separator` checks if a given set is a d-separator.
19- `is_minimal_d_separator` checks if a given set is a minimal d-separator.
21D-separators
22------------
24Here, we provide a brief overview of d-separation and related concepts that
25are relevant for understanding it:
27The ideas of d-separation and d-connection relate to paths being open or blocked.
29- A "path" is a sequence of nodes connected in order by edges. Unlike for most
30 graph theory analysis, the direction of the edges is ignored. Thus the path
31 can be thought of as a traditional path on the undirected version of the graph.
32- A "candidate d-separator" ``z`` is a set of nodes being considered as
33 possibly blocking all paths between two prescribed sets ``x`` and ``y`` of nodes.
34 We refer to each node in the candidate d-separator as "known".
35- A "collider" node on a path is a node that is a successor of its two neighbor
36 nodes on the path. That is, ``c`` is a collider if the edge directions
37 along the path look like ``... u -> c <- v ...``.
38- If a collider node or any of its descendants are "known", the collider
39 is called an "open collider". Otherwise it is a "blocking collider".
40- Any path can be "blocked" in two ways. If the path contains a "known" node
41 that is not a collider, the path is blocked. Also, if the path contains a
42 collider that is not a "known" node, the path is blocked.
43- A path is "open" if it is not blocked. That is, it is open if every node is
44 either an open collider or not a "known". Said another way, every
45 "known" in the path is a collider and every collider is open (has a
46 "known" as a inclusive descendant). The concept of "open path" is meant to
47 demonstrate a probabilistic conditional dependence between two nodes given
48 prescribed knowledge ("known" nodes).
49- Two sets ``x`` and ``y`` of nodes are "d-separated" by a set of nodes ``z``
50 if all paths between nodes in ``x`` and nodes in ``y`` are blocked. That is,
51 if there are no open paths from any node in ``x`` to any node in ``y``.
52 Such a set ``z`` is a "d-separator" of ``x`` and ``y``.
53- A "minimal d-separator" is a d-separator ``z`` for which no node or subset
54 of nodes can be removed with it still being a d-separator.
56The d-separator blocks some paths between ``x`` and ``y`` but opens others.
57Nodes in the d-separator block paths if the nodes are not colliders.
58But if a collider or its descendant nodes are in the d-separation set, the
59colliders are open, allowing a path through that collider.
61Illustration of D-separation with examples
62------------------------------------------
64A pair of two nodes, ``u`` and ``v``, are d-connected if there is a path
65from ``u`` to ``v`` that is not blocked. That means, there is an open
66path from ``u`` to ``v``.
68For example, if the d-separating set is the empty set, then the following paths are
69open between ``u`` and ``v``:
71- u <- n -> v
72- u -> w -> ... -> n -> v
74If on the other hand, ``n`` is in the d-separating set, then ``n`` blocks
75those paths between ``u`` and ``v``.
77Colliders block a path if they and their descendants are not included
78in the d-separating set. An example of a path that is blocked when the
79d-separating set is empty is:
81- u -> w -> ... -> n <- v
83The node ``n`` is a collider in this path and is not in the d-separating set.
84So ``n`` blocks this path. However, if ``n`` or a descendant of ``n`` is
85included in the d-separating set, then the path through the collider
86at ``n`` (... -> n <- ...) is "open".
88D-separation is concerned with blocking all paths between nodes from ``x`` to ``y``.
89A d-separating set between ``x`` and ``y`` is one where all paths are blocked.
91D-separation and its applications in probability
92------------------------------------------------
94D-separation is commonly used in probabilistic causal-graph models. D-separation
95connects the idea of probabilistic "dependence" with separation in a graph. If
96one assumes the causal Markov condition [5]_, (every node is conditionally
97independent of its non-descendants, given its parents) then d-separation implies
98conditional independence in probability distributions.
99Symmetrically, d-connection implies dependence.
101The intuition is as follows. The edges on a causal graph indicate which nodes
102influence the outcome of other nodes directly. An edge from u to v
103implies that the outcome of event ``u`` influences the probabilities for
104the outcome of event ``v``. Certainly knowing ``u`` changes predictions for ``v``.
105But also knowing ``v`` changes predictions for ``u``. The outcomes are dependent.
106Furthermore, an edge from ``v`` to ``w`` would mean that ``w`` and ``v`` are dependent
107and thus that ``u`` could indirectly influence ``w``.
109Without any knowledge about the system (candidate d-separating set is empty)
110a causal graph ``u -> v -> w`` allows all three nodes to be dependent. But
111if we know the outcome of ``v``, the conditional probabilities of outcomes for
112``u`` and ``w`` are independent of each other. That is, once we know the outcome
113for ``v``, the probabilities for ``w`` do not depend on the outcome for ``u``.
114This is the idea behind ``v`` blocking the path if it is "known" (in the candidate
115d-separating set).
117The same argument works whether the direction of the edges are both
118left-going and when both arrows head out from the middle. Having a "known"
119node on a path blocks the collider-free path because those relationships
120make the conditional probabilities independent.
122The direction of the causal edges does impact dependence precisely in the
123case of a collider e.g. ``u -> v <- w``. In that situation, both ``u`` and ``w``
124influence ``v``. But they do not directly influence each other. So without any
125knowledge of any outcomes, ``u`` and ``w`` are independent. That is the idea behind
126colliders blocking the path. But, if ``v`` is known, the conditional probabilities
127of ``u`` and ``w`` can be dependent. This is the heart of Berkson's Paradox [6]_.
128For example, suppose ``u`` and ``w`` are boolean events (they either happen or do not)
129and ``v`` represents the outcome "at least one of ``u`` and ``w`` occur". Then knowing
130``v`` is true makes the conditional probabilities of ``u`` and ``w`` dependent.
131Essentially, knowing that at least one of them is true raises the probability of
132each. But further knowledge that ``w`` is true (or false) change the conditional
133probability of ``u`` to either the original value or 1. So the conditional
134probability of ``u`` depends on the outcome of ``w`` even though there is no
135causal relationship between them. When a collider is known, dependence can
136occur across paths through that collider. This is the reason open colliders
137do not block paths.
139Furthermore, even if ``v`` is not "known", if one of its descendants is "known"
140we can use that information to know more about ``v`` which again makes
141``u`` and ``w`` potentially dependent. Suppose the chance of ``n`` occurring
142is much higher when ``v`` occurs ("at least one of ``u`` and ``w`` occur").
143Then if we know ``n`` occurred, it is more likely that ``v`` occurred and that
144makes the chance of ``u`` and ``w`` dependent. This is the idea behind why
145a collider does no block a path if any descendant of the collider is "known".
147When two sets of nodes ``x`` and ``y`` are d-separated by a set ``z``,
148it means that given the outcomes of the nodes in ``z``, the probabilities
149of outcomes of the nodes in ``x`` are independent of the outcomes of the
150nodes in ``y`` and vice versa.
152Examples
153--------
154A Hidden Markov Model with 5 observed states and 5 hidden states
155where the hidden states have causal relationships resulting in
156a path results in the following causal network. We check that
157early states along the path are separated from late state in
158the path by the d-separator of the middle hidden state.
159Thus if we condition on the middle hidden state, the early
160state probabilities are independent of the late state outcomes.
162>>> G = nx.DiGraph()
163>>> G.add_edges_from(
164... [
165... ("H1", "H2"),
166... ("H2", "H3"),
167... ("H3", "H4"),
168... ("H4", "H5"),
169... ("H1", "O1"),
170... ("H2", "O2"),
171... ("H3", "O3"),
172... ("H4", "O4"),
173... ("H5", "O5"),
174... ]
175... )
176>>> x, y, z = ({"H1", "O1"}, {"H5", "O5"}, {"H3"})
177>>> nx.is_d_separator(G, x, y, z)
178True
179>>> nx.is_minimal_d_separator(G, x, y, z)
180True
181>>> nx.is_minimal_d_separator(G, x, y, z | {"O3"})
182False
183>>> z = nx.find_minimal_d_separator(G, x | y, {"O2", "O3", "O4"})
184>>> z == {"H2", "H4"}
185True
187If no minimal_d_separator exists, `None` is returned
189>>> other_z = nx.find_minimal_d_separator(G, x | y, {"H2", "H3"})
190>>> other_z is None
191True
194References
195----------
197.. [1] Pearl, J. (2009). Causality. Cambridge: Cambridge University Press.
199.. [2] Darwiche, A. (2009). Modeling and reasoning with Bayesian networks.
200 Cambridge: Cambridge University Press.
202.. [3] Shachter, Ross D. "Bayes-ball: The rational pastime (for
203 determining irrelevance and requisite information in belief networks
204 and influence diagrams)." In Proceedings of the Fourteenth Conference
205 on Uncertainty in Artificial Intelligence (UAI), (pp. 480–487). 1998.
207.. [4] Koller, D., & Friedman, N. (2009).
208 Probabilistic graphical models: principles and techniques. The MIT Press.
210.. [5] https://en.wikipedia.org/wiki/Causal_Markov_condition
212.. [6] https://en.wikipedia.org/wiki/Berkson%27s_paradox
214"""
216from collections import deque
217from itertools import chain
219import networkx as nx
220from networkx.utils import UnionFind, not_implemented_for
222__all__ = [
223 "is_d_separator",
224 "is_minimal_d_separator",
225 "find_minimal_d_separator",
226]
229@not_implemented_for("undirected")
230@nx._dispatchable
231def is_d_separator(G, x, y, z):
232 """Return whether node sets `x` and `y` are d-separated by `z`.
234 Parameters
235 ----------
236 G : nx.DiGraph
237 A NetworkX DAG.
239 x : node or set of nodes
240 First node or set of nodes in `G`.
242 y : node or set of nodes
243 Second node or set of nodes in `G`.
245 z : node or set of nodes
246 Potential separator (set of conditioning nodes in `G`). Can be empty set.
248 Returns
249 -------
250 b : bool
251 A boolean that is true if `x` is d-separated from `y` given `z` in `G`.
253 Raises
254 ------
255 NetworkXError
256 The *d-separation* test is commonly used on disjoint sets of
257 nodes in acyclic directed graphs. Accordingly, the algorithm
258 raises a :exc:`NetworkXError` if the node sets are not
259 disjoint or if the input graph is not a DAG.
261 NodeNotFound
262 If any of the input nodes are not found in the graph,
263 a :exc:`NodeNotFound` exception is raised
265 Notes
266 -----
267 A d-separating set in a DAG is a set of nodes that
268 blocks all paths between the two sets. Nodes in `z`
269 block a path if they are part of the path and are not a collider,
270 or a descendant of a collider. Also colliders that are not in `z`
271 block a path. A collider structure along a path
272 is ``... -> c <- ...`` where ``c`` is the collider node.
274 https://en.wikipedia.org/wiki/Bayesian_network#d-separation
275 """
276 try:
277 x = {x} if x in G else x
278 y = {y} if y in G else y
279 z = {z} if z in G else z
281 intersection = x & y or x & z or y & z
282 if intersection:
283 raise nx.NetworkXError(
284 f"The sets are not disjoint, with intersection {intersection}"
285 )
287 set_v = x | y | z
288 if set_v - G.nodes:
289 raise nx.NodeNotFound(f"The node(s) {set_v - G.nodes} are not found in G")
290 except TypeError:
291 raise nx.NodeNotFound("One of x, y, or z is not a node or a set of nodes in G")
293 if not nx.is_directed_acyclic_graph(G):
294 raise nx.NetworkXError("graph should be directed acyclic")
296 # contains -> and <-> edges from starting node T
297 forward_deque = deque([])
298 forward_visited = set()
300 # contains <- and - edges from starting node T
301 backward_deque = deque(x)
302 backward_visited = set()
304 ancestors_or_z = set().union(*[nx.ancestors(G, node) for node in x]) | z | x
306 while forward_deque or backward_deque:
307 if backward_deque:
308 node = backward_deque.popleft()
309 backward_visited.add(node)
310 if node in y:
311 return False
312 if node in z:
313 continue
315 # add <- edges to backward deque
316 backward_deque.extend(G.pred[node].keys() - backward_visited)
317 # add -> edges to forward deque
318 forward_deque.extend(G.succ[node].keys() - forward_visited)
320 if forward_deque:
321 node = forward_deque.popleft()
322 forward_visited.add(node)
323 if node in y:
324 return False
326 # Consider if -> node <- is opened due to ancestor of node in z
327 if node in ancestors_or_z:
328 # add <- edges to backward deque
329 backward_deque.extend(G.pred[node].keys() - backward_visited)
330 if node not in z:
331 # add -> edges to forward deque
332 forward_deque.extend(G.succ[node].keys() - forward_visited)
334 return True
337@not_implemented_for("undirected")
338@nx._dispatchable
339def find_minimal_d_separator(G, x, y, *, included=None, restricted=None):
340 """Returns a minimal d-separating set between `x` and `y` if possible
342 A d-separating set in a DAG is a set of nodes that blocks all
343 paths between the two sets of nodes, `x` and `y`. This function
344 constructs a d-separating set that is "minimal", meaning no nodes can
345 be removed without it losing the d-separating property for `x` and `y`.
346 If no d-separating sets exist for `x` and `y`, this returns `None`.
348 In a DAG there may be more than one minimal d-separator between two
349 sets of nodes. Minimal d-separators are not always unique. This function
350 returns one minimal d-separator, or `None` if no d-separator exists.
352 Uses the algorithm presented in [1]_. The complexity of the algorithm
353 is :math:`O(m)`, where :math:`m` stands for the number of edges in
354 the subgraph of G consisting of only the ancestors of `x` and `y`.
355 For full details, see [1]_.
357 Parameters
358 ----------
359 G : graph
360 A networkx DAG.
361 x : set | node
362 A node or set of nodes in the graph.
363 y : set | node
364 A node or set of nodes in the graph.
365 included : set | node | None
366 A node or set of nodes which must be included in the found separating set,
367 default is None, which means the empty set.
368 restricted : set | node | None
369 Restricted node or set of nodes to consider. Only these nodes can be in
370 the found separating set, default is None meaning all nodes in ``G``.
372 Returns
373 -------
374 z : set | None
375 The minimal d-separating set, if at least one d-separating set exists,
376 otherwise None.
378 Raises
379 ------
380 NetworkXError
381 Raises a :exc:`NetworkXError` if the input graph is not a DAG
382 or if node sets `x`, `y`, and `included` are not disjoint.
384 NodeNotFound
385 If any of the input nodes are not found in the graph,
386 a :exc:`NodeNotFound` exception is raised.
388 References
389 ----------
390 .. [1] van der Zander, Benito, and Maciej Liśkiewicz. "Finding
391 minimal d-separators in linear time and applications." In
392 Uncertainty in Artificial Intelligence, pp. 637-647. PMLR, 2020.
393 """
394 if not nx.is_directed_acyclic_graph(G):
395 raise nx.NetworkXError("graph should be directed acyclic")
397 try:
398 x = {x} if x in G else x
399 y = {y} if y in G else y
401 if included is None:
402 included = set()
403 elif included in G:
404 included = {included}
406 if restricted is None:
407 restricted = set(G)
408 elif restricted in G:
409 restricted = {restricted}
411 set_y = x | y | included | restricted
412 if set_y - G.nodes:
413 raise nx.NodeNotFound(f"The node(s) {set_y - G.nodes} are not found in G")
414 except TypeError:
415 raise nx.NodeNotFound(
416 "One of x, y, included or restricted is not a node or set of nodes in G"
417 )
419 if not included <= restricted:
420 raise nx.NetworkXError(
421 f"Included nodes {included} must be in restricted nodes {restricted}"
422 )
424 intersection = x & y or x & included or y & included
425 if intersection:
426 raise nx.NetworkXError(
427 f"The sets x, y, included are not disjoint. Overlap: {intersection}"
428 )
430 nodeset = x | y | included
431 ancestors_x_y_included = nodeset.union(*[nx.ancestors(G, node) for node in nodeset])
433 z_init = restricted & (ancestors_x_y_included - (x | y))
435 x_closure = _reachable(G, x, ancestors_x_y_included, z_init)
436 if x_closure & y:
437 return None
439 z_updated = z_init & (x_closure | included)
440 y_closure = _reachable(G, y, ancestors_x_y_included, z_updated)
441 return z_updated & (y_closure | included)
444@not_implemented_for("undirected")
445@nx._dispatchable
446def is_minimal_d_separator(G, x, y, z, *, included=None, restricted=None):
447 """Determine if `z` is a minimal d-separator for `x` and `y`.
449 A d-separator, `z`, in a DAG is a set of nodes that blocks
450 all paths from nodes in set `x` to nodes in set `y`.
451 A minimal d-separator is a d-separator `z` such that removing
452 any subset of nodes makes it no longer a d-separator.
454 Note: This function checks whether `z` is a d-separator AND is
455 minimal. One can use the function `is_d_separator` to only check if
456 `z` is a d-separator. See examples below.
458 Parameters
459 ----------
460 G : nx.DiGraph
461 A NetworkX DAG.
462 x : node | set
463 A node or set of nodes in the graph.
464 y : node | set
465 A node or set of nodes in the graph.
466 z : node | set
467 The node or set of nodes to check if it is a minimal d-separating set.
468 The function :func:`is_d_separator` is called inside this function
469 to verify that `z` is in fact a d-separator.
470 included : set | node | None
471 A node or set of nodes which must be included in the found separating set,
472 default is ``None``, which means the empty set.
473 restricted : set | node | None
474 Restricted node or set of nodes to consider. Only these nodes can be in
475 the found separating set, default is ``None`` meaning all nodes in ``G``.
477 Returns
478 -------
479 bool
480 Whether or not the set `z` is a minimal d-separator subject to
481 `restricted` nodes and `included` node constraints.
483 Examples
484 --------
485 >>> G = nx.path_graph([0, 1, 2, 3], create_using=nx.DiGraph)
486 >>> G.add_node(4)
487 >>> nx.is_minimal_d_separator(G, 0, 2, {1})
488 True
489 >>> # since {1} is the minimal d-separator, {1, 3, 4} is not minimal
490 >>> nx.is_minimal_d_separator(G, 0, 2, {1, 3, 4})
491 False
492 >>> # alternatively, if we only want to check that {1, 3, 4} is a d-separator
493 >>> nx.is_d_separator(G, 0, 2, {1, 3, 4})
494 True
496 Raises
497 ------
498 NetworkXError
499 Raises a :exc:`NetworkXError` if the input graph is not a DAG.
501 NodeNotFound
502 If any of the input nodes are not found in the graph,
503 a :exc:`NodeNotFound` exception is raised.
505 References
506 ----------
507 .. [1] van der Zander, Benito, and Maciej Liśkiewicz. "Finding
508 minimal d-separators in linear time and applications." In
509 Uncertainty in Artificial Intelligence, pp. 637-647. PMLR, 2020.
511 Notes
512 -----
513 This function works on verifying that a set is minimal and
514 d-separating between two nodes. Uses criterion (a), (b), (c) on
515 page 4 of [1]_. a) closure(`x`) and `y` are disjoint. b) `z` contains
516 all nodes from `included` and is contained in the `restricted`
517 nodes and in the union of ancestors of `x`, `y`, and `included`.
518 c) the nodes in `z` not in `included` are contained in both
519 closure(x) and closure(y). The closure of a set is the set of nodes
520 connected to the set by a directed path in G.
522 The complexity is :math:`O(m)`, where :math:`m` stands for the
523 number of edges in the subgraph of G consisting of only the
524 ancestors of `x` and `y`.
526 For full details, see [1]_.
527 """
528 if not nx.is_directed_acyclic_graph(G):
529 raise nx.NetworkXError("graph should be directed acyclic")
531 try:
532 x = {x} if x in G else x
533 y = {y} if y in G else y
534 z = {z} if z in G else z
536 if included is None:
537 included = set()
538 elif included in G:
539 included = {included}
541 if restricted is None:
542 restricted = set(G)
543 elif restricted in G:
544 restricted = {restricted}
546 set_y = x | y | included | restricted
547 if set_y - G.nodes:
548 raise nx.NodeNotFound(f"The node(s) {set_y - G.nodes} are not found in G")
549 except TypeError:
550 raise nx.NodeNotFound(
551 "One of x, y, z, included or restricted is not a node or set of nodes in G"
552 )
554 if not included <= z:
555 raise nx.NetworkXError(
556 f"Included nodes {included} must be in proposed separating set z {x}"
557 )
558 if not z <= restricted:
559 raise nx.NetworkXError(
560 f"Separating set {z} must be contained in restricted set {restricted}"
561 )
563 intersection = x.intersection(y) or x.intersection(z) or y.intersection(z)
564 if intersection:
565 raise nx.NetworkXError(
566 f"The sets are not disjoint, with intersection {intersection}"
567 )
569 nodeset = x | y | included
570 ancestors_x_y_included = nodeset.union(*[nx.ancestors(G, n) for n in nodeset])
572 # criterion (a) -- check that z is actually a separator
573 x_closure = _reachable(G, x, ancestors_x_y_included, z)
574 if x_closure & y:
575 return False
577 # criterion (b) -- basic constraint; included and restricted already checked above
578 if not (z <= ancestors_x_y_included):
579 return False
581 # criterion (c) -- check that z is minimal
582 y_closure = _reachable(G, y, ancestors_x_y_included, z)
583 if not ((z - included) <= (x_closure & y_closure)):
584 return False
585 return True
588@not_implemented_for("undirected")
589def _reachable(G, x, a, z):
590 """Modified Bayes-Ball algorithm for finding d-connected nodes.
592 Find all nodes in `a` that are d-connected to those in `x` by
593 those in `z`. This is an implementation of the function
594 `REACHABLE` in [1]_ (which is itself a modification of the
595 Bayes-Ball algorithm [2]_) when restricted to DAGs.
597 Parameters
598 ----------
599 G : nx.DiGraph
600 A NetworkX DAG.
601 x : node | set
602 A node in the DAG, or a set of nodes.
603 a : node | set
604 A (set of) node(s) in the DAG containing the ancestors of `x`.
605 z : node | set
606 The node or set of nodes conditioned on when checking d-connectedness.
608 Returns
609 -------
610 w : set
611 The closure of `x` in `a` with respect to d-connectedness
612 given `z`.
614 References
615 ----------
616 .. [1] van der Zander, Benito, and Maciej Liśkiewicz. "Finding
617 minimal d-separators in linear time and applications." In
618 Uncertainty in Artificial Intelligence, pp. 637-647. PMLR, 2020.
620 .. [2] Shachter, Ross D. "Bayes-ball: The rational pastime
621 (for determining irrelevance and requisite information in
622 belief networks and influence diagrams)." In Proceedings of the
623 Fourteenth Conference on Uncertainty in Artificial Intelligence
624 (UAI), (pp. 480–487). 1998.
625 """
627 def _pass(e, v, f, n):
628 """Whether a ball entering node `v` along edge `e` passes to `n` along `f`.
630 Boolean function defined on page 6 of [1]_.
632 Parameters
633 ----------
634 e : bool
635 Directed edge by which the ball got to node `v`; `True` iff directed into `v`.
636 v : node
637 Node where the ball is.
638 f : bool
639 Directed edge connecting nodes `v` and `n`; `True` iff directed `n`.
640 n : node
641 Checking whether the ball passes to this node.
643 Returns
644 -------
645 b : bool
646 Whether the ball passes or not.
648 References
649 ----------
650 .. [1] van der Zander, Benito, and Maciej Liśkiewicz. "Finding
651 minimal d-separators in linear time and applications." In
652 Uncertainty in Artificial Intelligence, pp. 637-647. PMLR, 2020.
653 """
654 is_element_of_A = n in a
655 # almost_definite_status = True # always true for DAGs; not so for RCGs
656 collider_if_in_Z = v not in z or (e and not f)
657 return is_element_of_A and collider_if_in_Z # and almost_definite_status
659 queue = deque([])
660 for node in x:
661 if bool(G.pred[node]):
662 queue.append((True, node))
663 if bool(G.succ[node]):
664 queue.append((False, node))
665 processed = queue.copy()
667 while any(queue):
668 e, v = queue.popleft()
669 preds = ((False, n) for n in G.pred[v])
670 succs = ((True, n) for n in G.succ[v])
671 f_n_pairs = chain(preds, succs)
672 for f, n in f_n_pairs:
673 if (f, n) not in processed and _pass(e, v, f, n):
674 queue.append((f, n))
675 processed.append((f, n))
677 return {w for (_, w) in processed}