• Home
  • Features
  • Pricing
  • Docs
  • Announcements
  • Sign In

PrincetonUniversity / PsyNeuLink / 15917088825

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

push

github

web-flow
Merge pull request #3271 from PrincetonUniversity/devel

Devel

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
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✔
STATUS · Troubleshooting · Open an Issue · Sales · Support · CAREERS · ENTERPRISE · START FREE · SCHEDULE DEMO
ANNOUNCEMENTS · TWITTER · TOS & SLA · Supported CI Services · What's a CI service? · Automated Testing

© 2025 Coveralls, Inc