15917088825

Committed 05 Jun 2025 04:18AM UTC coverage: 84.482% (+0.5%) from 84.017%

Build # 15917088825

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #3271 from PrincetonUniversity/devel

Devel

Run Details

9909 of 12966 branches covered (76.42%)

Branch coverage included in aggregate %.

1708 of 1908 new or added lines in 54 files covered. (89.52%)

25 existing lines in 14 files now uncovered.

34484 of 39581 relevant lines covered (87.12%)

0.87 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

91.63

/psyneulink/core/globals/graph.py

import collections
import enum
import logging
import typing

import networkx

from psyneulink._typing import Union
from psyneulink.core.globals.keywords import MAYBE

__all__ = [
    'EdgeType', 'GraphError'
]


logger = logging.getLogger(__name__)


class GraphError(Exception):
    pass


class EdgeType(enum.Enum):
    """
        Attributes:
            NON_FEEDBACK
                A standard edge that if it exists in a cycle will only be flattened, not pruned

            FEEDBACK
                A "feedbacK" edge that will be immediately pruned to create an acyclic graph

            FLEXIBLE
                An edge that will be pruned only if it exists in a cycle
    """
    NON_FEEDBACK = False
    FEEDBACK = True
    FLEXIBLE = MAYBE

    @classmethod
    def from_any(cls, value) -> 'EdgeType':
        """
        Returns:
            EdgeType: an `EdgeType` corresponding to **value** if it
            exists
        """
        try:
            value = value.upper()
        except AttributeError:
            # not a string
            pass

        try:
            return cls[value]
        except KeyError:
            # allow ValueError to raise
            return cls(value)

    @classmethod
    def has(cls, value) -> bool:
        """
        Returns:
            bool: True if **value** corresponds to an `EdgeType`, or
            False otherwise
        """
        try:
            cls.from_any(value)
        except ValueError:
            return False
        else:
            return True


class Vertex(object):
    """
        Stores a Component for use with a :py:class:`Graph`

        Arguments
        ---------

        component : Component
            the `Component <Component>` represented by this Vertex

        parents : list[Vertex]
            the `Vertices <Vertex>` corresponding to the incoming edges of this `Vertex`

        children : list[Vertex]
            the `Vertices <Vertex>` corresponding to the outgoing edges of this `Vertex`

        Attributes
        ----------

        component : Component
            the `Component <Component>` represented by this Vertex

        parents : list[Vertex]
            the `Vertices <Vertex>` corresponding to the incoming edges of this `Vertex`

        children : list[Vertex]
            the `Vertices <Vertex>` corresponding to the outgoing edges of this `Vertex`
    """

    def __init__(self, component, parents=None, children=None, feedback=None):
        self.component = component
        if parents is not None:
            self.parents = parents
        else:
            self.parents = []
        if children is not None:
            self.children = children
        else:
            self.children = []

        self.feedback = feedback

        # when pruning a vertex for a processing graph, we store the connection type (the vertex.feedback)
        # to the new child or parent here
        # self.source_types = collections.defaultdict(EdgeType.NORMAL)
        self.source_types = {}

    def __repr__(self):
        return '(Vertex {0} {1})'.format(id(self), self.component)

    @property
    def feedback(self):
        return self._feedback

    @feedback.setter
    def feedback(self, value: Union[bool, EdgeType]):
        if value is None:
            self._feedback = None
        else:
            self._feedback = EdgeType.from_any(value)


class Graph(object):
    """A Graph of vertices and edges.

    Attributes
    ----------

    comp_to_vertex : Dict[`Component <Component>` : `Vertex`]
        maps `Component` in the graph to the `Vertices <Vertex>` that represent them.

    vertices : List[Vertex]
        the `Vertices <Vertex>` contained in this Graph;  each can be a `Node <Composition_Nodes>` or a
        `Projection <Component_Projections>`.

    dependency_dict : Dict[`Component` : Set(`Component`)]
        maps each of the graph's Components to the others from which it receives input
        (i.e., their `value <Component.value>`).  For a `Node <Components_Nodes>`, this is one or more
        `Projections <Projection>`;  for a Projection, it is a single Node.

    """

    def __init__(self):
        self.comp_to_vertex = collections.OrderedDict()  # Translate from PNL Mech, Comp or Proj to corresponding vertex
        self.vertices = []  # List of vertices within graph

        self.cycle_vertices = []

    def copy(self):
        """
            Returns
            -------

            A copy of the Graph. `Vertices <Vertex>` are distinct from their originals, and point to the same
            `Component <Component>` object : :py:class:`Graph`
        """
        g = Graph()

        for vertex in self.vertices:
            g.add_vertex(Vertex(vertex.component, feedback=vertex.feedback))

        for i in range(len(self.vertices)):
            g.vertices[i].parents = [g.comp_to_vertex[parent_vertex.component] for parent_vertex in
                                     self.vertices[i].parents]
            g.vertices[i].children = [g.comp_to_vertex[parent_vertex.component] for parent_vertex in
                                      self.vertices[i].children]

        return g

    def add_component(self, component, feedback=False):
        if component in [vertex.component for vertex in self.vertices]:
            logger.info('Component {1} is already in graph {0}'.format(component, self))
        else:
            vertex = Vertex(component, feedback=feedback)
            self.comp_to_vertex[component] = vertex
            self.add_vertex(vertex)

    def add_vertex(self, vertex):
        if vertex in self.vertices:
            logger.info('Vertex {1} is already in graph {0}'.format(vertex, self))
        else:
            self.vertices.append(vertex)
            self.comp_to_vertex[vertex.component] = vertex

    def remove_component(self, component):
        try:
            self.remove_vertex(self.comp_to_vertex[component])
        except KeyError as e:
            raise GraphError('Component {1} not found in graph {2}: {0}'.format(e, component, self))

    def remove_vertex(self, vertex):
        try:
            for parent in vertex.parents:
                parent.children.remove(vertex)
            for child in vertex.children:
                child.parents.remove(vertex)

            self.vertices.remove(vertex)
            del self.comp_to_vertex[vertex.component]
            # TODO:
            #   check if this removal puts the graph in an inconsistent state
        except ValueError as e:
            raise GraphError('Vertex {1} not found in graph {2}: {0}'.format(e, vertex, self))

    def connect_components(self, parent, child):
        try:
            self.connect_vertices(self.comp_to_vertex[parent], self.comp_to_vertex[child])
        except KeyError as e:
            if parent not in self.comp_to_vertex:
                raise GraphError(
                    "Sender ({}) of Projection ({}) not (yet) assigned".format(
                        repr(parent.name), repr(child.name)
                    )
                )
            elif child not in self.comp_to_vertex:
                raise GraphError(
                    "Projection ({}) to {} not (yet) assigned".format(
                        repr(parent.name), repr(child.name)
                    )
                )
            else:
                raise KeyError(e)

    def connect_vertices(self, parent, child):
        if child not in parent.children:
            parent.children.append(child)
        if parent not in child.parents:
            child.parents.append(parent)

    def get_parents_from_component(self, component):
        """
            Arguments
            ---------

            component : Component
                the Component whose parents will be returned

            Returns
            -------

            list[`Vertex`] :
              list of the parent `Vertices <Vertex>` of the Vertex associated with **component**.
        """
        return self.comp_to_vertex[component].parents

    def get_children_from_component(self, component):
        """
            Arguments
            ---------

            component : Component
                the Component whose children will be returned

            Returns
            -------

            list[`Vertex`] :
                list of the child `Vertices <Vertex>` of the Vertex associated with **component**.
        """
        return self.comp_to_vertex[component].children

    def prune_feedback_edges(self):
        """
            Produces an acyclic graph from this Graph. `Feedback <EdgeType.FEEDBACK>` edges are pruned, as well as
            any edges that are `potentially feedback <EdgeType.FLEXIBLE>` that are in cycles. After these edges are
            removed, if cycles still remain, they are "flattened." That is, each edge in the cycle is pruned, and
            each the dependencies of each Node in the cycle are set to the pre-flattened union of all cyclic nodes'
            parents that are themselves not in a cycle.

            Returns:
                a tuple containing
                - the acyclic dependency dictionary produced from this
                Graph
                - a dependency dictionary containing only the edges
                removed to create the acyclic graph
                - the unmodified cyclic dependency dictionary of this
                Graph
        """

        # stores a modified version of the self in which cycles are "flattened"
        execution_dependencies = self.dependency_dict
        # stores the original unmodified dependencies
        structural_dependencies = self.dependency_dict
        # wipe and reconstruct list of vertices in cycles
        self.cycle_vertices = []
        flexible_edges = set()

        for node in execution_dependencies:
            # prune recurrent edges
            try:
                execution_dependencies[node].remove(node)
                self.cycle_vertices.append([node])
            except KeyError:
                pass

            for dep in tuple(execution_dependencies[node]):
                vert = self.comp_to_vertex[node]
                dep_vert = self.comp_to_vertex[dep]

                if dep_vert in vert.source_types:
                    # prune standard edges labeled as feedback
                    if vert.source_types[dep_vert] is EdgeType.FEEDBACK:
                        execution_dependencies[node].remove(dep)
                    # store flexible edges for potential pruning later
                    elif vert.source_types[dep_vert] is EdgeType.FLEXIBLE:
                        flexible_edges.add((dep, node))

        # construct a parallel networkx graph to use its cycle algorithms
        nx_graph = self._generate_networkx_graph(execution_dependencies)
        connected_components = list(networkx.strongly_connected_components(nx_graph))

        # prune only one flexible edge per attempt, to remove as few
        # edges as possible
        # For now, just prune the first flexible edge each time. Maybe
        # look for "best" edges to prune in future by frequency in
        # cycles, if that occurs
        try:
            flexible_edges_iter = sorted(flexible_edges)
        except TypeError:
            flexible_edges_iter = flexible_edges
        for parent, child in flexible_edges_iter:
            cycles = [c for c in connected_components if len(c) > 1]

            if len(cycles) == 0:
                break

            if any((parent in c and child in c) for c in cycles):
                # prune
                execution_dependencies[child].remove(parent)
                self.comp_to_vertex[child].source_types[self.comp_to_vertex[parent]] = EdgeType.FEEDBACK
                nx_graph.remove_edge(parent, child)
                # recompute cycles after each prune
                connected_components = list(networkx.strongly_connected_components(nx_graph))

        # find all the parent nodes for each node in a cycle, excluding
        # parents that are part of the cycle
        for cycle in [c for c in connected_components if len(c) > 1]:
            acyclic_dependencies = set()

            for node in cycle:
                acyclic_dependencies = acyclic_dependencies.union({
                    parent for parent in execution_dependencies[node]
                    if parent not in cycle
                })

            # replace the dependencies of each node in the cycle with
            # each of the above parents outside of the cycle. This
            # ensures that they all share the same parents and will then
            # exist in the same consideration set

            # NOTE: it is unnecessary to change any childrens'
            # dependencies because any child dependent on a node n_i in
            # a cycle will still depend on n_i when it is part of a
            # flattened cycle. The flattened cycle will simply add more
            # nodes to the consideration set in which n_i exists
            cycle_verts = []
            for child in cycle:
                cycle_verts.append(child)
                execution_dependencies[child] = acyclic_dependencies
            self.cycle_vertices.append(cycle_verts)

        return (
            execution_dependencies,
            {
                node: structural_dependencies[node] - execution_dependencies[node]
                for node in execution_dependencies
            },
            structural_dependencies
        )

    def get_strongly_connected_components(
        self,
        nx_graph: typing.Optional[networkx.DiGraph] = None
    ):
        if nx_graph is None:
            nx_graph = self._generate_networkx_graph()

        return list(networkx.strongly_connected_components(nx_graph))

    def _generate_networkx_graph(self, dependency_dict=None):
        if dependency_dict is None:
            dependency_dict = self.dependency_dict

        nx_graph = networkx.DiGraph()
        nx_graph.add_nodes_from(list(dependency_dict.keys()))
        for child in dependency_dict:
            for parent in dependency_dict[child]:
                nx_graph.add_edge(parent, child)

        return nx_graph

    @property
    def dependency_dict(self):
        return dict((v.component, set(d.component for d in v.parents)) for v in self.vertices)

1	import collections	1✔
2	import enum	1✔
3	import logging	1✔
4	import typing	1✔
5
6	import networkx	1✔
7
8	from psyneulink._typing import Union	1✔
9	from psyneulink.core.globals.keywords import MAYBE	1✔
10
11	__all__ = [	1✔
12	'EdgeType', 'GraphError'
13	]
14
15
16	logger = logging.getLogger(__name__)	1✔
17
18
19	class GraphError(Exception):	1✔
20	pass	1✔
21
22
23	class EdgeType(enum.Enum):	1✔
24	"""
25	Attributes:
26	NON_FEEDBACK
27	A standard edge that if it exists in a cycle will only be flattened, not pruned
28
29	FEEDBACK
30	A "feedbacK" edge that will be immediately pruned to create an acyclic graph
31
32	FLEXIBLE
33	An edge that will be pruned only if it exists in a cycle
34	"""
35	NON_FEEDBACK = False	1✔
36	FEEDBACK = True	1✔
37	FLEXIBLE = MAYBE	1✔
38
39	@classmethod	1✔
40	def from_any(cls, value) -> 'EdgeType':	1✔
41	"""
42	Returns:
43	EdgeType: an `EdgeType` corresponding to value if it
44	exists
45	"""
46	try:	1✔
47	value = value.upper()	1✔
48	except AttributeError:	1✔
49	# not a string
50	pass	1✔
51
52	try:	1✔
53	return cls[value]	1✔
54	except KeyError:	1✔
55	# allow ValueError to raise
56	return cls(value)	1✔
57
58	@classmethod	1✔
59	def has(cls, value) -> bool:	1✔
60	"""
61	Returns:
62	bool: True if value corresponds to an `EdgeType`, or
63	False otherwise
64	"""
65	try:	1✔
66	cls.from_any(value)	1✔
NEW 67	except ValueError:	×
NEW 68	return False	×
69	else:
70	return True	1✔
71
72
73	class Vertex(object):	1✔
74	"""
75	Stores a Component for use with a :py:class:`Graph`
76
77	Arguments
78	---------
79
80	component : Component
81	the `Component <Component>` represented by this Vertex
82
83	parents : list[Vertex]
84	the `Vertices <Vertex>` corresponding to the incoming edges of this `Vertex`
85
86	children : list[Vertex]
87	the `Vertices <Vertex>` corresponding to the outgoing edges of this `Vertex`
88
89	Attributes
90	----------
91
92	component : Component
93	the `Component <Component>` represented by this Vertex
94
95	parents : list[Vertex]
96	the `Vertices <Vertex>` corresponding to the incoming edges of this `Vertex`
97
98	children : list[Vertex]
99	the `Vertices <Vertex>` corresponding to the outgoing edges of this `Vertex`
100	"""
101
102	def __init__(self, component, parents=None, children=None, feedback=None):	1✔
103	self.component = component	1✔
104	if parents is not None:	1!
NEW 105	self.parents = parents	×
106	else:
107	self.parents = []	1✔
108	if children is not None:	1!
NEW 109	self.children = children	×
110	else:
111	self.children = []	1✔
112
113	self.feedback = feedback	1✔
114
115	# when pruning a vertex for a processing graph, we store the connection type (the vertex.feedback)
116	# to the new child or parent here
117	# self.source_types = collections.defaultdict(EdgeType.NORMAL)
118	self.source_types = {}	1✔
119
120	def __repr__(self):
121	return '(Vertex {0} {1})'.format(id(self), self.component)
122
123	@property	1✔
124	def feedback(self):	1✔
125	return self._feedback	1✔
126
127	@feedback.setter	1✔
128	def feedback(self, value: Union[bool, EdgeType]):	1✔
129	if value is None:	1✔
130	self._feedback = None	1✔
131	else:
132	self._feedback = EdgeType.from_any(value)	1✔
133
134
135	class Graph(object):	1✔
136	"""A Graph of vertices and edges.
137
138	Attributes
139	----------
140
141	comp_to_vertex : Dict[`Component <Component>` : `Vertex`]
142	maps `Component` in the graph to the `Vertices <Vertex>` that represent them.
143
144	vertices : List[Vertex]
145	the `Vertices <Vertex>` contained in this Graph; each can be a `Node <Composition_Nodes>` or a
146	`Projection <Component_Projections>`.
147
148	dependency_dict : Dict[`Component` : Set(`Component`)]
149	maps each of the graph's Components to the others from which it receives input
150	(i.e., their `value <Component.value>`). For a `Node <Components_Nodes>`, this is one or more
151	`Projections <Projection>`; for a Projection, it is a single Node.
152
153	"""
154
155	def __init__(self):	1✔
156	self.comp_to_vertex = collections.OrderedDict() # Translate from PNL Mech, Comp or Proj to corresponding vertex	1✔
157	self.vertices = [] # List of vertices within graph	1✔
158
159	self.cycle_vertices = []	1✔
160
161	def copy(self):	1✔
162	"""
163	Returns
164	-------
165
166	A copy of the Graph. `Vertices <Vertex>` are distinct from their originals, and point to the same
167	`Component <Component>` object : :py:class:`Graph`
168	"""
169	g = Graph()	1✔
170
171	for vertex in self.vertices:	1✔
172	g.add_vertex(Vertex(vertex.component, feedback=vertex.feedback))	1✔
173
174	for i in range(len(self.vertices)):	1✔
175	g.vertices[i].parents = [g.comp_to_vertex[parent_vertex.component] for parent_vertex in	1✔
176	self.vertices[i].parents]
177	g.vertices[i].children = [g.comp_to_vertex[parent_vertex.component] for parent_vertex in	1✔
178	self.vertices[i].children]
179
180	return g	1✔
181
182	def add_component(self, component, feedback=False):	1✔
183	if component in [vertex.component for vertex in self.vertices]:	1!
NEW 184	logger.info('Component {1} is already in graph {0}'.format(component, self))	×
185	else:
186	vertex = Vertex(component, feedback=feedback)	1✔
187	self.comp_to_vertex[component] = vertex	1✔
188	self.add_vertex(vertex)	1✔
189
190	def add_vertex(self, vertex):	1✔
191	if vertex in self.vertices:	1!
NEW 192	logger.info('Vertex {1} is already in graph {0}'.format(vertex, self))	×
193	else:
194	self.vertices.append(vertex)	1✔
195	self.comp_to_vertex[vertex.component] = vertex	1✔
196
197	def remove_component(self, component):	1✔
198	try:	1✔
199	self.remove_vertex(self.comp_to_vertex[component])	1✔
NEW 200	except KeyError as e:	×
201	raise GraphError('Component {1} not found in graph {2}: {0}'.format(e, component, self))
202
203	def remove_vertex(self, vertex):	1✔
204	try:	1✔
205	for parent in vertex.parents:	1✔
206	parent.children.remove(vertex)	1✔
207	for child in vertex.children:	1✔
208	child.parents.remove(vertex)	1✔
209
210	self.vertices.remove(vertex)	1✔
211	del self.comp_to_vertex[vertex.component]	1✔
212	# TODO:
213	# check if this removal puts the graph in an inconsistent state
NEW 214	except ValueError as e:	×
215	raise GraphError('Vertex {1} not found in graph {2}: {0}'.format(e, vertex, self))
216
217	def connect_components(self, parent, child):	1✔
218	try:	1✔
219	self.connect_vertices(self.comp_to_vertex[parent], self.comp_to_vertex[child])	1✔
NEW 220	except KeyError as e:	×
NEW 221	if parent not in self.comp_to_vertex:	×
222	raise GraphError(
223	"Sender ({}) of Projection ({}) not (yet) assigned".format(
224	repr(parent.name), repr(child.name)
225	)
226	)
NEW 227	elif child not in self.comp_to_vertex:	×
228	raise GraphError(
229	"Projection ({}) to {} not (yet) assigned".format(
230	repr(parent.name), repr(child.name)
231	)
232	)
233	else:
234	raise KeyError(e)
235
236	def connect_vertices(self, parent, child):	1✔
237	if child not in parent.children:	1✔
238	parent.children.append(child)	1✔
239	if parent not in child.parents:	1✔
240	child.parents.append(parent)	1✔
241
242	def get_parents_from_component(self, component):	1✔
243	"""
244	Arguments
245	---------
246
247	component : Component
248	the Component whose parents will be returned
249
250	Returns
251	-------
252
253	list[`Vertex`] :
254	list of the parent `Vertices <Vertex>` of the Vertex associated with component.
255	"""
256	return self.comp_to_vertex[component].parents	1✔
257
258	def get_children_from_component(self, component):	1✔
259	"""
260	Arguments
261	---------
262
263	component : Component
264	the Component whose children will be returned
265
266	Returns
267	-------
268
269	list[`Vertex`] :
270	list of the child `Vertices <Vertex>` of the Vertex associated with component.
271	"""
272	return self.comp_to_vertex[component].children	1✔
273
274	def prune_feedback_edges(self):	1✔
275	"""
276	Produces an acyclic graph from this Graph. `Feedback <EdgeType.FEEDBACK>` edges are pruned, as well as
277	any edges that are `potentially feedback <EdgeType.FLEXIBLE>` that are in cycles. After these edges are
278	removed, if cycles still remain, they are "flattened." That is, each edge in the cycle is pruned, and
279	each the dependencies of each Node in the cycle are set to the pre-flattened union of all cyclic nodes'
280	parents that are themselves not in a cycle.
281
282	Returns:
283	a tuple containing
284	- the acyclic dependency dictionary produced from this
285	Graph
286	- a dependency dictionary containing only the edges
287	removed to create the acyclic graph
288	- the unmodified cyclic dependency dictionary of this
289	Graph
290	"""
291
292	# stores a modified version of the self in which cycles are "flattened"
293	execution_dependencies = self.dependency_dict	1✔
294	# stores the original unmodified dependencies
295	structural_dependencies = self.dependency_dict	1✔
296	# wipe and reconstruct list of vertices in cycles
297	self.cycle_vertices = []	1✔
298	flexible_edges = set()	1✔
299
300	for node in execution_dependencies:	1✔
301	# prune recurrent edges
302	try:	1✔
303	execution_dependencies[node].remove(node)	1✔
304	self.cycle_vertices.append([node])	1✔
305	except KeyError:	1✔
306	pass	1✔
307
308	for dep in tuple(execution_dependencies[node]):	1✔
309	vert = self.comp_to_vertex[node]	1✔
310	dep_vert = self.comp_to_vertex[dep]	1✔
311
312	if dep_vert in vert.source_types:	1✔
313	# prune standard edges labeled as feedback
314	if vert.source_types[dep_vert] is EdgeType.FEEDBACK:	1✔
315	execution_dependencies[node].remove(dep)	1✔
316	# store flexible edges for potential pruning later
317	elif vert.source_types[dep_vert] is EdgeType.FLEXIBLE:	1✔
318	flexible_edges.add((dep, node))	1✔
319
320	# construct a parallel networkx graph to use its cycle algorithms
321	nx_graph = self._generate_networkx_graph(execution_dependencies)	1✔
322	connected_components = list(networkx.strongly_connected_components(nx_graph))	1✔
323
324	# prune only one flexible edge per attempt, to remove as few
325	# edges as possible
326	# For now, just prune the first flexible edge each time. Maybe
327	# look for "best" edges to prune in future by frequency in
328	# cycles, if that occurs
329	try:	1✔
330	flexible_edges_iter = sorted(flexible_edges)	1✔
NEW 331	except TypeError:	×
NEW 332	flexible_edges_iter = flexible_edges	×
333	for parent, child in flexible_edges_iter:	1✔
334	cycles = [c for c in connected_components if len(c) > 1]	1✔
335
336	if len(cycles) == 0:	1✔
337	break	1✔
338
339	if any((parent in c and child in c) for c in cycles):	1✔
340	# prune
341	execution_dependencies[child].remove(parent)	1✔
342	self.comp_to_vertex[child].source_types[self.comp_to_vertex[parent]] = EdgeType.FEEDBACK	1✔
343	nx_graph.remove_edge(parent, child)	1✔
344	# recompute cycles after each prune
345	connected_components = list(networkx.strongly_connected_components(nx_graph))	1✔
346
347	# find all the parent nodes for each node in a cycle, excluding
348	# parents that are part of the cycle
349	for cycle in [c for c in connected_components if len(c) > 1]:	1✔
350	acyclic_dependencies = set()	1✔
351
352	for node in cycle:	1✔
353	acyclic_dependencies = acyclic_dependencies.union({	1✔
354	parent for parent in execution_dependencies[node]
355	if parent not in cycle
356	})
357
358	# replace the dependencies of each node in the cycle with
359	# each of the above parents outside of the cycle. This
360	# ensures that they all share the same parents and will then
361	# exist in the same consideration set
362
363	# NOTE: it is unnecessary to change any childrens'
364	# dependencies because any child dependent on a node n_i in
365	# a cycle will still depend on n_i when it is part of a
366	# flattened cycle. The flattened cycle will simply add more
367	# nodes to the consideration set in which n_i exists
368	cycle_verts = []	1✔
369	for child in cycle:	1✔
370	cycle_verts.append(child)	1✔
371	execution_dependencies[child] = acyclic_dependencies	1✔
372	self.cycle_vertices.append(cycle_verts)	1✔
373
374	return (	1✔
375	execution_dependencies,
376	{
377	node: structural_dependencies[node] - execution_dependencies[node]
378	for node in execution_dependencies
379	},
380	structural_dependencies
381	)
382
383	def get_strongly_connected_components(	1✔
384	self,
385	nx_graph: typing.Optional[networkx.DiGraph] = None
386	):
387	if nx_graph is None:	1!
388	nx_graph = self._generate_networkx_graph()	1✔
389
390	return list(networkx.strongly_connected_components(nx_graph))	1✔
391
392	def _generate_networkx_graph(self, dependency_dict=None):	1✔
393	if dependency_dict is None:	1✔
394	dependency_dict = self.dependency_dict	1✔
395
396	nx_graph = networkx.DiGraph()	1✔
397	nx_graph.add_nodes_from(list(dependency_dict.keys()))	1✔
398	for child in dependency_dict:	1✔
399	for parent in dependency_dict[child]:	1✔
400	nx_graph.add_edge(parent, child)	1✔
401
402	return nx_graph	1✔
403
404	@property	1✔
405	def dependency_dict(self):	1✔
406	return dict((v.component, set(d.component for d in v.parents)) for v in self.vertices)	1✔

PrincetonUniversity / PsyNeuLink / 15917088825

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous