Coverage for pyTooling/Graph/__init__.py: 84%
1374 statements
« prev ^ index » next coverage.py v7.17.0, created at 2026-10-25 13:06 +0000
1# ==================================================================================================================== #
2# _____ _ _ ____ _ #
3# _ __ _ |_ _|__ ___ | (_)_ __ __ _ / ___|_ __ __ _ _ __ | |__ #
4# | '_ \| | | || |/ _ \ / _ \| | | '_ \ / _` || | _| '__/ _` | '_ \| '_ \ #
5# | |_) | |_| || | (_) | (_) | | | | | | (_| || |_| | | | (_| | |_) | | | | #
6# | .__/ \__, ||_|\___/ \___/|_|_|_| |_|\__, (_)____|_| \__,_| .__/|_| |_| #
7# |_| |___/ |___/ |_| #
8# ==================================================================================================================== #
9# Authors: #
10# Patrick Lehmann #
11# #
12# License: #
13# ==================================================================================================================== #
14# Copyright 2017-2026 Patrick Lehmann - Bötzingen, Germany #
15# #
16# Licensed under the Apache License, Version 2.0 (the "License"); #
17# you may not use this file except in compliance with the License. #
18# You may obtain a copy of the License at #
19# #
20# http://www.apache.org/licenses/LICENSE-2.0 #
21# #
22# Unless required by applicable law or agreed to in writing, software #
23# distributed under the License is distributed on an "AS IS" BASIS, #
24# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. #
25# See the License for the specific language governing permissions and #
26# limitations under the License. #
27# #
28# SPDX-License-Identifier: Apache-2.0 #
29# ==================================================================================================================== #
30#
31"""
32A powerful **graph** data structure for Python.
34Graph algorithms using all vertices are provided as methods on the graph instance. Whereas graph algorithms based on a
35starting vertex are provided as methods on a vertex.
37.. admonition:: Example Graph
39 .. mermaid::
40 :caption: A directed graph with backward-edges denoted by dotted vertex relations.
42 %%{init: { "flowchart": { "nodeSpacing": 15, "rankSpacing": 30, "curve": "linear", "useMaxWidth": false } } }%%
43 graph LR
44 A(A); B(B); C(C); D(D); E(E); F(F) ; G(G); H(H); I(I)
46 A --> B --> E
47 G --> F
48 A --> C --> G --> H --> D
49 D -.-> A
50 D & F -.-> B
51 I ---> E --> F --> D
53 classDef node fill:#eee,stroke:#777,font-size:smaller;
55.. seealso::
57 :mod:`pyTooling.Graph.GraphML`
58 |rarr| Writing a graph as a GraphML document.
59 :mod:`pyTooling.Tree`
60 |rarr| A tree, which is a graph without cycles and with a single root.
61 :mod:`pyTooling.StateMachine`
62 |rarr| A statemachine, which is a directed graph of states and transitions.
63"""
64from __future__ import annotations
66import heapq
67from collections import deque
68from enum import Enum
69from itertools import chain
70from typing import Any, TypeVar, Generic, Deque, Union, Optional as Nullable, \
71 Iterator as typing_Iterator, Generator, Iterable, Mapping, Hashable
73from pyTooling.Decorators import export, readonly
74from pyTooling.MetaClasses import ExtendedType
75from pyTooling.Exceptions import DuplicateElementError, NotInSameHierarchyError, ToolingException
76from pyTooling.Common import getFullyQualifiedName
77from pyTooling.DataModel import KeyValuePairsMixin, Predicate
78from pyTooling.Tree import Node
81IDType = TypeVar("IDType", bound=Hashable)
82"""A type variable for an ID."""
84WeightType = TypeVar("WeightType", bound=Union[int, float])
85"""A type variable for a weight."""
87ValueType = TypeVar("ValueType")
88"""A type variable for a value."""
90VertexIDType = TypeVar("VertexIDType", bound=Hashable)
91"""A type variable for a vertex's ID."""
93VertexWeightType = TypeVar("VertexWeightType", bound=Union[int, float])
94"""A type variable for a vertex's weight."""
96VertexValueType = TypeVar("VertexValueType")
97"""A type variable for a vertex's value."""
99EdgeIDType = TypeVar("EdgeIDType", bound=Hashable)
100"""A type variable for an edge's ID."""
102EdgeWeightType = TypeVar("EdgeWeightType", bound=Union[int, float])
103"""A type variable for an edge's weight."""
105EdgeValueType = TypeVar("EdgeValueType")
106"""A type variable for an edge's value."""
108EdgeKindType = TypeVar("EdgeKindType", bound=Enum)
109"""A type variable for an edge's kind, e.g. :class:`EdgeKind`."""
111LinkIDType = TypeVar("LinkIDType", bound=Hashable)
112"""A type variable for an link's ID."""
114LinkWeightType = TypeVar("LinkWeightType", bound=Union[int, float])
115"""A type variable for an link's weight."""
117LinkValueType = TypeVar("LinkValueType")
118"""A type variable for an link's value."""
120LinkKindType = TypeVar("LinkKindType", bound=Enum)
121"""A type variable for a link's kind, e.g. :class:`LinkKind`."""
124@export
125class EdgeKind(Enum):
126 """
127 Kind of an edge.
129 .. seealso::
131 :meth:`BaseGraph.AnnotateTransitiveEdges`
132 |rarr| Mark every edge as direct or transitive.
133 """
134 Default = 0 #: The edge wasn't classified.
135 Direct = 1 #: No longer path connects the edge's source with its destination.
136 Transitive = 2 #: A longer path connects the edge's source with its destination, so the edge is implied by it.
139@export
140class LinkKind(Enum):
141 """
142 Kind of a link between subgraphs.
143 """
144 Default = 0 #: The link wasn't classified.
147@export
148class GraphError(ToolingException):
149 """Base exception of all exceptions raised by :mod:`pyTooling.Graph`."""
152@export
153class InternalError(GraphError):
154 """
155 The exception is raised when a data structure corruption is detected.
157 .. danger::
159 This exception should never be raised.
161 If so, please create an issue at GitHub so the data structure corruption can be investigated and fixed. |br|
162 :gh:`⇒ Bug Tracker at GitHub <pyTooling/pyTooling/issues>`
163 """
166@export
167class NotInSameGraph(GraphError, NotInSameHierarchyError):
168 """The exception is raised when creating an edge between two vertices, but these are not in the same graph."""
171@export
172class NotInDifferentSubgraphs(GraphError):
173 """
174 The exception is raised when creating a link between two vertices, but these are in the same subgraph.
176 A link crosses subgraph boundaries. Two vertices within one subgraph are connected by an edge.
177 """
180@export
181class DuplicateVertexError(GraphError, DuplicateElementError):
182 """The exception is raised when the vertex already exists in the graph."""
184 _vertexID: VertexIDType #: ID of the vertex that already exists in the graph.
186 def __init__(self, message: str, /, *, vertexID: VertexIDType) -> None:
187 """
188 Initializes the exception with the identifier that is already taken.
190 :param message: The exception's message.
191 :param vertexID: The vertex identifier that already exists.
192 """
193 super().__init__(message)
194 self._vertexID = vertexID
196 @readonly
197 def VertexID(self) -> VertexIDType:
198 """
199 Read-only property to access the identifier that already exists (:attr:`_vertexID`).
201 :returns: The duplicate vertex identifier.
202 """
203 return self._vertexID
206@export
207class DuplicateEdgeError(GraphError, DuplicateElementError):
208 """The exception is raised when the edge already exists in the graph."""
210 _edgeID: Nullable[EdgeIDType] #: ID of the edge that already exists in the graph.
212 def __init__(self, message: str, /, *, edgeID: Nullable[EdgeIDType] = None) -> None:
213 """
214 Initializes the exception with the identifier that is already taken.
216 :param message: The exception's message.
217 :param edgeID: Optional, the edge identifier that already exists.
218 """
219 super().__init__(message)
220 self._edgeID = edgeID
222 @readonly
223 def EdgeID(self) -> Nullable[EdgeIDType]:
224 """
225 Read-only property to access the identifier that already exists (:attr:`_edgeID`).
227 :returns: The duplicate edge identifier, or ``None`` if it wasn't recorded.
228 """
229 return self._edgeID
232@export
233class DestinationNotReachable(GraphError):
234 """The exception is raised when a destination vertex is not reachable."""
237@export
238class NotATreeError(GraphError):
239 """
240 The exception is raised when a subgraph is not a tree.
242 Either the subgraph has a cycle (backward edge) or links between branches (cross-edge).
243 """
246@export
247class EdgeNotFoundError(GraphError, LookupError):
248 """
249 The exception is raised when no edge matching the given source or destination vertex was found.
251 It is a :exc:`LookupError` as well, because the edge is looked up by its vertices; catching
252 :exc:`~pyTooling.Graph.GraphError` still catches it.
253 """
255 _source: Nullable[Vertex] #: Vertex the edge was searched from.
256 _destination: Nullable[Vertex] #: Vertex the edge was searched to.
258 def __init__(self, message: str, /, *, source: Nullable[Vertex] = None, destination: Nullable[Vertex] = None) -> None:
259 """
260 Initializes the exception with the two vertices no edge was found between.
262 :param message: The exception's message.
263 :param source: Optional, the vertex the edge was searched from.
264 :param destination: Optional, the vertex the edge was searched to.
265 """
266 super().__init__(message)
267 self._source = source
268 self._destination = destination
270 @readonly
271 def Source(self) -> Nullable[Vertex]:
272 """
273 Read-only property to access the vertex the edge was searched from (:attr:`_source`).
275 :returns: The source vertex, or ``None`` if it wasn't recorded.
276 """
277 return self._source
279 @readonly
280 def Destination(self) -> Nullable[Vertex]:
281 """
282 Read-only property to access the vertex the edge was searched to (:attr:`_destination`).
284 :returns: The destination vertex, or ``None`` if it wasn't recorded.
285 """
286 return self._destination
289@export
290class LinkNotFoundError(GraphError, LookupError):
291 """
292 The exception is raised when no link matching the given source or destination vertex was found.
294 It is a :exc:`LookupError` as well, because the link is looked up by its vertices; catching
295 :exc:`~pyTooling.Graph.GraphError` still catches it.
296 """
298 _source: Nullable[Vertex] #: Vertex the link was searched from.
299 _destination: Nullable[Vertex] #: Vertex the link was searched to.
301 def __init__(self, message: str, /, *, source: Nullable[Vertex] = None, destination: Nullable[Vertex] = None) -> None:
302 """
303 Initializes the exception with the two vertices no link was found between.
305 :param message: The exception's message.
306 :param source: Optional, the vertex the link was searched from.
307 :param destination: Optional, the vertex the link was searched to.
308 """
309 super().__init__(message)
310 self._source = source
311 self._destination = destination
313 @readonly
314 def Source(self) -> Nullable[Vertex]:
315 """
316 Read-only property to access the vertex the link was searched from (:attr:`_source`).
318 :returns: The source vertex, or ``None`` if it wasn't recorded.
319 """
320 return self._source
322 @readonly
323 def Destination(self) -> Nullable[Vertex]:
324 """
325 Read-only property to access the vertex the link was searched to (:attr:`_destination`).
327 :returns: The destination vertex, or ``None`` if it wasn't recorded.
328 """
329 return self._destination
332@export
333class SameGraphError(GraphError):
334 """The exception is raised when a vertex is copied into the graph it already belongs to."""
336 _graph: Nullable[Graph] #: Graph the vertex belongs to already.
338 def __init__(self, message: str, /, *, graph: Nullable[Graph] = None) -> None:
339 """
340 Initializes the exception with the graph the vertex belongs to already.
342 :param message: The exception's message.
343 :param graph: Optional, the graph the vertex belongs to already.
344 """
345 super().__init__(message)
346 self._graph = graph
348 @readonly
349 def Graph(self) -> Nullable[Graph]:
350 """
351 Read-only property to access the graph the vertex belongs to already (:attr:`_graph`).
353 :returns: The graph, or ``None`` if it wasn't recorded.
354 """
355 return self._graph
358@export
359class CycleError(GraphError):
360 """The exception is raised when a not permitted cycle is found."""
362 _path: Nullable[tuple[Vertex, ...]] #: Path of vertices ending in the vertex reached a second time.
364 def __init__(self, message: str, /, *, path: Nullable[tuple[Vertex, ...]] = None) -> None:
365 """
366 Initializes the exception with the path closing the cycle.
368 :param message: The exception's message.
369 :param path: Optional, the path of vertices ending in the vertex reached a second time.
370 """
371 super().__init__(message)
372 self._path = path
374 @readonly
375 def Path(self) -> Nullable[tuple[Vertex, ...]]:
376 """
377 Read-only property to access the path of vertices ending in the vertex reached a second time (:attr:`_path`).
379 :returns: Tuple of vertices, or ``None`` if it wasn't recorded.
380 """
381 return self._path
384@export
385class Base(KeyValuePairsMixin, metaclass=ExtendedType, slots=True):
386 """
387 Base-class for all graph elements, adding a dictionary of arbitrary key-value-pairs to them.
389 Every vertex, edge, link, component, view, subgraph and graph can carry meta information this way.
390 """
392 def __del__(self) -> None:
393 """
394 .. todo:: GRAPH::Base::del Needs documentation.
395 """
396 try:
397 del self._dict
398 except AttributeError:
399 pass
401 def Delete(self) -> None:
402 """
403 Remove this element's attached attributes from internal dictionary.
404 """
405 self._dict.clear()
408@export
409class BaseWithIDValueAndWeight(
410 Base,
411 Generic[IDType, ValueType, WeightType]
412):
413 """
414 Base-class for graph elements identified by an ID and carrying a value and a weight - vertices, edges and links.
416 All three are optional: an element without an ID is still part of the graph, it just can't be looked up by ID.
417 """
419 _id: Nullable[IDType] #: Field storing the object's Identifier.
420 _value: Nullable[ValueType] #: Field storing the object's value of any type.
421 _weight: Nullable[WeightType] #: Field storing the object's weight.
423 def __init__(
424 self,
425 identifier: Nullable[IDType] = None,
426 value: Nullable[ValueType] = None,
427 weight: Nullable[WeightType] = None,
428 keyValuePairs: Nullable[Mapping[Hashable, Any]] = None
429 ) -> None:
430 """
431 Initialize a graph element with an optional ID, value and weight.
433 :param identifier: Optional, unique ID.
434 :param value: Optional, value.
435 :param weight: Optional, weight.
436 :param keyValuePairs: Optional, mapping (dictionary) of key-value-pairs.
437 :raises TypeError: If parameter 'name' is not of type string.
438 """
439 super().__init__(keyValuePairs)
441 self._id = identifier
442 self._value = value
443 self._weight = weight
445 @readonly
446 def ID(self) -> Nullable[IDType]:
447 """
448 Read-only property to access the unique ID (:attr:`_id`).
450 If no ID was given at creation time, ID returns ``None``.
452 :returns: Unique ID, if ID was given at creation time, else ``None``.
453 """
454 return self._id
456 @property
457 def Value(self) -> ValueType:
458 """
459 Property to get and set the value (:attr:`_value`).
461 :returns: The value.
462 """
463 return self._value
465 @Value.setter
466 def Value(self, value: ValueType) -> None:
467 self._value = value
469 @property
470 def Weight(self) -> Nullable[EdgeWeightType]:
471 """
472 Property to get and set the weight (:attr:`_weight`) of an edge.
474 :returns: The weight of an edge.
475 """
476 return self._weight
478 @Weight.setter
479 def Weight(self, value: Nullable[EdgeWeightType]) -> None:
480 self._weight = value
483@export
484class BaseWithName(Base):
485 """Base-class for named graph elements like a graph, a subgraph, a view or a component."""
487 _name: Nullable[str] #: Field storing the object's name.
489 def __init__(
490 self,
491 name: Nullable[str] = None,
492 keyValuePairs: Nullable[Mapping[Hashable, Any]] = None,
493 ) -> None:
494 """
495 Initialize a named graph element with an optional name and optional key-value-pairs.
497 :param name: Optional, name.
498 :param keyValuePairs: Optional, mapping (dictionary) of key-value-pairs.
499 :raises ValueError: If parameter 'graph' is None.
500 :raises TypeError: If parameter 'graph' is not of type :class:`Graph`.
501 """
502 if name is not None and not isinstance(name, str):
503 ex = TypeError("Parameter 'name' is not of type 'str'.")
504 ex.add_note(f"Got type '{getFullyQualifiedName(name)}'.")
505 raise ex
507 super().__init__(keyValuePairs)
509 self._name = name
511 @property
512 def Name(self) -> Nullable[str]:
513 """
514 Property to access the name (:attr:`_name`).
516 :returns: The object's name, or ``None`` if it has none.
517 :raises TypeError: If an assigned value is not of type string.
518 """
519 return self._name
521 @Name.setter
522 def Name(self, value: str) -> None:
523 if not isinstance(value, str):
524 ex = TypeError("Name is not of type 'str'.")
525 ex.add_note(f"Got type '{getFullyQualifiedName(value)}'.")
526 raise ex
528 self._name = value
531@export
532class BaseWithVertices(
533 BaseWithName,
534 Generic[
535 VertexIDType, VertexWeightType, VertexValueType,
536 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeKindType,
537 LinkIDType, LinkWeightType, LinkValueType, LinkKindType
538 ]
539):
540 """Base-class for named graph elements owning a set of vertices - a subgraph, a view or a component."""
542 _graph: _Graph[
543 VertexIDType, VertexWeightType, VertexValueType,
544 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeKindType,
545 LinkIDType, LinkWeightType, LinkValueType, LinkKindType
546 ] #: Field storing a reference to the graph.
547 _vertices: set[Vertex[
548 VertexIDType, VertexWeightType, VertexValueType,
549 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeKindType,
550 LinkIDType, LinkWeightType, LinkValueType, LinkKindType
551 ]] #: Field storing a set of vertices.
553 def __init__(
554 self,
555 graph: Graph,
556 name: Nullable[str] = None,
557 vertices: Nullable[Iterable[Vertex]] = None,
558 keyValuePairs: Nullable[Mapping[Hashable, Any]] = None
559 ) -> None:
560 """
561 Initialize a named graph element owning a set of vertices, and register it at its graph.
563 :param graph: The reference to the graph.
564 :param name: Optional, name.
565 :param vertices: Optional, list of vertices.
566 :param keyValuePairs: Optional, mapping (dictionary) of key-value-pairs.
567 :raises ValueError: If parameter 'graph' is None.
568 :raises TypeError: If parameter 'graph' is not of type :class:`Graph`.
569 """
570 if graph is None: 570 ↛ 571line 570 didn't jump to line 571 because the condition on line 570 was never true
571 raise ValueError("Parameter 'graph' is None.")
572 elif not isinstance(graph, Graph): 572 ↛ 573line 572 didn't jump to line 573 because the condition on line 572 was never true
573 ex = TypeError("Parameter 'graph' is not of type 'Graph'.")
574 ex.add_note(f"Got type '{getFullyQualifiedName(graph)}'.")
575 raise ex
577 super().__init__(name, keyValuePairs)
579 self._graph = graph
580 self._vertices = set() if vertices is None else set(vertices)
582 def __del__(self) -> None:
583 """
584 .. todo:: GRAPH::BaseWithVertices::del Needs documentation.
585 """
586 try:
587 del self._vertices
588 except AttributeError:
589 pass
591 super().__del__()
593 @readonly
594 def Graph(self) -> Graph:
595 """
596 Read-only property to access the graph, this object is associated to (:attr:`_graph`).
598 :returns: The graph this object is associated to.
599 """
600 return self._graph
602 @readonly
603 def Vertices(self) -> set[Vertex]:
604 """
605 Read-only property to access the vertices in this component (:attr:`_vertices`).
607 :returns: The set of vertices in this component.
608 """
609 return self._vertices
611 @readonly
612 def VertexCount(self) -> int:
613 """
614 Read-only property to return the number of vertices referenced by this object.
616 :returns: The number of vertices this object references.
617 """
618 return len(self._vertices)
621@export
622class Vertex(
623 BaseWithIDValueAndWeight[VertexIDType, VertexValueType, VertexWeightType],
624 Generic[
625 VertexIDType, VertexWeightType, VertexValueType,
626 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeKindType,
627 LinkIDType, LinkWeightType, LinkValueType, LinkKindType
628 ]
629):
630 """
631 A **vertex** can have a unique ID, a value and attached meta information as key-value-pairs. A vertex has references
632 to inbound and outbound edges, thus a graph can be traversed in reverse.
633 """
634 _graph: BaseGraph[VertexIDType, VertexWeightType, VertexValueType, EdgeIDType, EdgeWeightType, EdgeValueType, EdgeKindType, LinkIDType, LinkWeightType, LinkValueType, LinkKindType] #: Field storing a reference to the graph.
635 _subgraph: Subgraph[VertexIDType, VertexWeightType, VertexValueType, EdgeIDType, EdgeWeightType, EdgeValueType, EdgeKindType, LinkIDType, LinkWeightType, LinkValueType, LinkKindType] #: Field storing a reference to the subgraph.
636 _component: _Component #: Field storing a reference to the component this vertex belongs to.
637 _views: dict[Hashable, View] #: Field storing the views this vertex is part of, by view name.
638 _inboundEdges: list[Edge[EdgeIDType, EdgeValueType, EdgeWeightType, EdgeKindType]] #: Field storing a list of inbound edges.
639 _outboundEdges: list[Edge[EdgeIDType, EdgeValueType, EdgeWeightType, EdgeKindType]] #: Field storing a list of outbound edges.
640 _inboundLinks: list[Link[LinkIDType, LinkValueType, LinkWeightType, LinkKindType]] #: Field storing a list of inbound links.
641 _outboundLinks: list[Link[LinkIDType, LinkValueType, LinkWeightType, LinkKindType]] #: Field storing a list of outbound links.
643 def __init__(
644 self,
645 vertexID: Nullable[VertexIDType] = None,
646 value: Nullable[VertexValueType] = None,
647 weight: Nullable[VertexWeightType] = None,
648 keyValuePairs: Nullable[Mapping[Hashable, Any]] = None,
649 graph: Nullable[Graph] = None,
650 subgraph: Nullable[Subgraph] = None
651 ) -> None:
652 """
653 Initialize a vertex and register it at its graph or subgraph.
655 :param vertexID: Optional, ID for the new vertex.
656 :param value: Optional, value for the new vertex.
657 :param weight: Optional, weight for the new vertex.
658 :param keyValuePairs: Optional, mapping (dictionary) of key-value-pairs.
659 :param graph: Optional, reference to the graph.
660 :param subgraph: Optional, undocumented
661 :raises TypeError: If parameter 'vertexID' is not of the graph's vertex ID type.
662 :raises DuplicateVertexError: If the given vertex ID already exists in this graph or subgraph.
663 """
664 if vertexID is not None and not isinstance(vertexID, Hashable): 664 ↛ 665line 664 didn't jump to line 665 because the condition on line 664 was never true
665 ex = TypeError("Parameter 'vertexID' is not of type 'VertexIDType'.")
666 ex.add_note(f"Got type '{getFullyQualifiedName(vertexID)}'.")
667 raise ex
669 super().__init__(vertexID, value, weight, keyValuePairs)
671 if subgraph is None:
672 self._graph = graph if graph is not None else Graph()
673 self._subgraph = None
674 self._component = Component(self._graph, vertices=(self,))
676 if vertexID is None:
677 self._graph._verticesWithoutID.append(self)
678 elif vertexID not in self._graph._verticesWithID:
679 self._graph._verticesWithID[vertexID] = self
680 else:
681 raise DuplicateVertexError(f"Vertex ID '{vertexID}' already exists in this graph.", vertexID=vertexID)
682 else:
683 self._graph = subgraph._graph
684 self._subgraph = subgraph
685 self._component = Component(self._graph, vertices=(self,))
687 if vertexID is None:
688 subgraph._verticesWithoutID.append(self)
689 elif vertexID not in subgraph._verticesWithID: 689 ↛ 692line 689 didn't jump to line 692 because the condition on line 689 was always true
690 subgraph._verticesWithID[vertexID] = self
691 else:
692 raise DuplicateVertexError(f"Vertex ID '{vertexID}' already exists in this subgraph.", vertexID=vertexID)
694 self._views = {}
695 self._inboundEdges = []
696 self._outboundEdges = []
697 self._inboundLinks = []
698 self._outboundLinks = []
700 def __del__(self) -> None:
701 """
702 .. todo:: GRAPH::BaseEdge::del Needs documentation.
703 """
704 try:
705 del self._views
706 del self._inboundEdges
707 del self._outboundEdges
708 del self._inboundLinks
709 del self._outboundLinks
710 except AttributeError:
711 pass
713 super().__del__()
715 def Delete(self) -> None:
716 """
717 Delete this vertex and every edge and link connected to it.
719 The vertex is removed from its graph or subgraph, and from its views; every connected edge and link is removed
720 from its other vertex and unregistered from the graph or subgraph it was registered on.
721 """
722 for edge in self._outboundEdges:
723 edge._destination._inboundEdges.remove(edge)
724 edge._Unregister()
725 edge._Delete()
727 for edge in self._inboundEdges:
728 edge._source._outboundEdges.remove(edge)
729 edge._Unregister()
730 edge._Delete()
732 for link in self._outboundLinks:
733 link._destination._inboundLinks.remove(link)
734 link._Unregister()
735 link._Delete()
737 for link in self._inboundLinks: 737 ↛ 738line 737 didn't jump to line 738 because the loop on line 737 never started
738 link._source._outboundLinks.remove(link)
739 link._Unregister()
740 link._Delete()
742 # Remove from Graph or Subgraph - a vertex is registered on the subgraph it lives in, otherwise on the graph.
743 container = self._graph if self._subgraph is None else self._subgraph
744 if self._id is None:
745 container._verticesWithoutID.remove(self)
746 else:
747 del container._verticesWithID[self._id]
749 # component
751 # views
752 self._views.clear()
753 self._inboundEdges.clear()
754 self._outboundEdges.clear()
755 self._inboundLinks.clear()
756 self._outboundLinks.clear()
758 super().Delete()
760 @readonly
761 def Graph(self) -> Graph:
762 """
763 Read-only property to access the graph, this vertex is associated to (:attr:`_graph`).
765 :returns: The graph this vertex is associated to.
766 """
767 return self._graph
769 @readonly
770 def Component(self) -> Component:
771 """
772 Read-only property to access the component, this vertex is associated to (:attr:`_component`).
774 :returns: The component this vertex is associated to.
775 """
776 return self._component
778 @readonly
779 def InboundEdges(self) -> tuple[Edge, ...]:
780 """
781 Read-only property to return the inbound edges (:attr:`_inboundEdges`) as a tuple.
783 :returns: Tuple of inbound edges.
784 """
785 return tuple(self._inboundEdges)
787 @readonly
788 def OutboundEdges(self) -> tuple[Edge, ...]:
789 """
790 Read-only property to return the outbound edges (:attr:`_outboundEdges`) as a tuple.
792 :returns: Tuple of outbound edges.
793 """
794 return tuple(self._outboundEdges)
796 @readonly
797 def InboundLinks(self) -> tuple[Link, ...]:
798 """
799 Read-only property to return the inbound links (:attr:`_inboundLinks`) as a tuple.
801 :returns: Tuple of inbound links.
802 """
803 return tuple(self._inboundLinks)
805 @readonly
806 def OutboundLinks(self) -> tuple[Link, ...]:
807 """
808 Read-only property to return the outbound links (:attr:`_outboundLinks`) as a tuple.
810 :returns: Tuple of outbound links.
811 """
812 return tuple(self._outboundLinks)
814 @readonly
815 def EdgeCount(self) -> int:
816 """
817 Read-only property to return the number of all edges (:attr:`_inboundEdges` and :attr:`_outboundEdges`).
819 :returns: Number of inbound and outbound edges.
820 """
821 return len(self._inboundEdges) + len(self._outboundEdges)
823 @readonly
824 def InboundEdgeCount(self) -> int:
825 """
826 Read-only property to return the number of inbound edges (:attr:`_inboundEdges`).
828 :returns: Number of inbound edges.
829 """
830 return len(self._inboundEdges)
832 @readonly
833 def OutboundEdgeCount(self) -> int:
834 """
835 Read-only property to return the number of outbound edges (:attr:`_outboundEdges`).
837 :returns: Number of outbound edges.
838 """
839 return len(self._outboundEdges)
841 @readonly
842 def LinkCount(self) -> int:
843 """
844 Read-only property to return the number of all links (:attr:`_inboundLinks` and :attr:`_outboundLinks`).
846 :returns: Number of inbound and outbound links.
847 """
848 return len(self._inboundLinks) + len(self._outboundLinks)
850 @readonly
851 def InboundLinkCount(self) -> int:
852 """
853 Read-only property to return the number of inbound links (:attr:`_inboundLinks`).
855 :returns: Number of inbound links.
856 """
857 return len(self._inboundLinks)
859 @readonly
860 def OutboundLinkCount(self) -> int:
861 """
862 Read-only property to return the number of outbound links (:attr:`_outboundLinks`).
864 :returns: Number of outbound links.
865 """
866 return len(self._outboundLinks)
868 @readonly
869 def IsRoot(self) -> bool:
870 """
871 Read-only property to check if this vertex is a root vertex in the graph.
873 A root has no inbound edges (no predecessor vertices).
875 :returns: ``True``, if this vertex is a root.
877 .. seealso::
879 :meth:`Vertex.IsLeaf <pyTooling.Graph.Vertex.IsLeaf>`
880 |rarr| Check if a vertex is a leaf vertex in the graph.
881 :meth:`BaseGraph.IterateRoots <pyTooling.Graph.BaseGraph.IterateRoots>`
882 |rarr| Iterate all roots of a graph.
883 :meth:`BaseGraph.IterateLeafs <pyTooling.Graph.BaseGraph.IterateLeafs>`
884 |rarr| Iterate all leafs of a graph.
885 """
886 return len(self._inboundEdges) == 0
888 @readonly
889 def IsLeaf(self) -> bool:
890 """
891 Read-only property to check if this vertex is a leaf vertex in the graph.
893 A leaf has no outbound edges (no successor vertices).
895 :returns: ``True``, if this vertex is a leaf.
897 .. seealso::
899 :meth:`Vertex.IsRoot <pyTooling.Graph.Vertex.IsRoot>`
900 |rarr| Check if a vertex is a root vertex in the graph.
901 :meth:`BaseGraph.IterateRoots <pyTooling.Graph.BaseGraph.IterateRoots>`
902 |rarr| Iterate all roots of a graph.
903 :meth:`BaseGraph.IterateLeafs <pyTooling.Graph.BaseGraph.IterateLeafs>`
904 |rarr| Iterate all leafs of a graph.
905 """
906 return len(self._outboundEdges) == 0
908 @readonly
909 def Predecessors(self) -> tuple[Vertex, ...]:
910 """
911 Read-only property to return the predecessor vertices, the sources of :attr:`_inboundEdges`.
913 :returns: Tuple of predecessor vertices.
914 """
915 return tuple([edge.Source for edge in self._inboundEdges])
917 @readonly
918 def Successors(self) -> tuple[Vertex, ...]:
919 """
920 Read-only property to return the successor vertices, the destinations of :attr:`_outboundEdges`.
922 :returns: Tuple of successor vertices.
923 """
924 return tuple([edge.Destination for edge in self._outboundEdges])
926 def EdgeToVertex(
927 self,
928 vertex: Vertex,
929 edgeID: Nullable[EdgeIDType] = None,
930 edgeWeight: Nullable[EdgeWeightType] = None,
931 edgeValue: Nullable[VertexValueType] = None,
932 edgeKind: Enum = EdgeKind.Default,
933 keyValuePairs: Nullable[Mapping[Hashable, Any]] = None
934 ) -> Edge:
935 """
936 Create an outbound edge from this vertex to the referenced vertex.
938 :param vertex: The vertex to be linked to.
939 :param edgeID: Optional, the edge's optional ID for the new edge object.
940 :param edgeWeight: Optional, the edge's optional weight for the new edge object.
941 :param edgeValue: Optional, the edge's optional value for the new edge object.
942 :param edgeKind: Optional, the kind of the new edge object. Default: :attr:`EdgeKind.Default`.
943 :param keyValuePairs: Optional, mapping (dictionary) of key-value-pairs for the new edge object.
944 :returns: The edge object linking this vertex and the referenced vertex.
945 :raises DuplicateEdgeError: If the given edge ID already exists in this graph or subgraph.
946 :raises NotInSameGraph: If both vertices are not in the same graph or subgraph. |br|
947 Use :meth:`LinkToVertex` or :meth:`LinkFromVertex` to connect vertices across
948 subgraph boundaries.
950 .. seealso::
952 :meth:`EdgeFromVertex`
953 |rarr| Create an inbound edge from the referenced vertex to this vertex.
954 :meth:`EdgeToNewVertex`
955 |rarr| Create a new vertex and link that vertex by an outbound edge from this vertex.
956 :meth:`EdgeFromNewVertex`
957 |rarr| Create a new vertex and link that vertex by an inbound edge to this vertex.
958 :meth:`LinkToVertex`
959 |rarr| Create an outbound link from this vertex to the referenced vertex.
960 :meth:`LinkFromVertex`
961 |rarr| Create an inbound link from the referenced vertex to this vertex.
962 """
963 if self._subgraph is vertex._subgraph:
964 edge = Edge(self, vertex, edgeID, edgeValue, edgeWeight, edgeKind, keyValuePairs)
966 self._outboundEdges.append(edge)
967 vertex._inboundEdges.append(edge)
969 if self._subgraph is None:
970 # TODO: move into Edge?
971 # TODO: keep _graph pointer in edge and then register edge on graph?
972 if edgeID is None:
973 self._graph._edgesWithoutID.append(edge)
974 elif edgeID not in self._graph._edgesWithID:
975 self._graph._edgesWithID[edgeID] = edge
976 else:
977 raise DuplicateEdgeError(f"Edge ID '{edgeID}' already exists in this graph.", edgeID=edgeID)
978 else:
979 # TODO: keep _graph pointer in edge and then register edge on graph?
980 if edgeID is None:
981 self._subgraph._edgesWithoutID.append(edge)
982 elif edgeID not in self._subgraph._edgesWithID:
983 self._subgraph._edgesWithID[edgeID] = edge
984 else:
985 raise DuplicateEdgeError(f"Edge ID '{edgeID}' already exists in this subgraph.", edgeID=edgeID)
986 else:
987 ex = NotInSameGraph(f"Vertex {self!r} and vertex {vertex!r} are not in the same graph or subgraph.")
988 ex.add_note("An edge can only connect vertices within the same graph or subgraph.")
989 ex.add_note("Use LinkToVertex or LinkFromVertex to connect vertices across subgraph boundaries.")
990 raise ex
992 return edge
994 def EdgeFromVertex(
995 self,
996 vertex: Vertex,
997 edgeID: Nullable[EdgeIDType] = None,
998 edgeWeight: Nullable[EdgeWeightType] = None,
999 edgeValue: Nullable[VertexValueType] = None,
1000 edgeKind: Enum = EdgeKind.Default,
1001 keyValuePairs: Nullable[Mapping[Hashable, Any]] = None
1002 ) -> Edge:
1003 """
1004 Create an inbound edge from the referenced vertex to this vertex.
1006 :param vertex: The vertex to be linked from.
1007 :param edgeID: Optional, the edge's optional ID for the new edge object.
1008 :param edgeWeight: Optional, the edge's optional weight for the new edge object.
1009 :param edgeValue: Optional, the edge's optional value for the new edge object.
1010 :param edgeKind: Optional, the kind of the new edge object. Default: :attr:`EdgeKind.Default`.
1011 :param keyValuePairs: Optional, mapping (dictionary) of key-value-pairs for the new edge object.
1012 :returns: The edge object linking the referenced vertex and this vertex.
1013 :raises DuplicateEdgeError: If the given edge ID already exists in this graph or subgraph.
1014 :raises NotInSameGraph: If both vertices are not in the same graph or subgraph. |br|
1015 Use :meth:`LinkToVertex` or :meth:`LinkFromVertex` to connect vertices across
1016 subgraph boundaries.
1018 .. seealso::
1020 :meth:`EdgeToVertex`
1021 |rarr| Create an outbound edge from this vertex to the referenced vertex.
1022 :meth:`EdgeToNewVertex`
1023 |rarr| Create a new vertex and link that vertex by an outbound edge from this vertex.
1024 :meth:`EdgeFromNewVertex`
1025 |rarr| Create a new vertex and link that vertex by an inbound edge to this vertex.
1026 :meth:`LinkToVertex`
1027 |rarr| Create an outbound link from this vertex to the referenced vertex.
1028 :meth:`LinkFromVertex`
1029 |rarr| Create an inbound link from the referenced vertex to this vertex.
1030 """
1031 if self._subgraph is vertex._subgraph:
1032 edge = Edge(vertex, self, edgeID, edgeValue, edgeWeight, edgeKind, keyValuePairs)
1034 vertex._outboundEdges.append(edge)
1035 self._inboundEdges.append(edge)
1037 if self._subgraph is None:
1038 # TODO: move into Edge?
1039 # TODO: keep _graph pointer in edge and then register edge on graph?
1040 if edgeID is None:
1041 self._graph._edgesWithoutID.append(edge)
1042 elif edgeID not in self._graph._edgesWithID:
1043 self._graph._edgesWithID[edgeID] = edge
1044 else:
1045 raise DuplicateEdgeError(f"Edge ID '{edgeID}' already exists in this graph.", edgeID=edgeID)
1046 else:
1047 # TODO: keep _graph pointer in edge and then register edge on graph?
1048 if edgeID is None:
1049 self._subgraph._edgesWithoutID.append(edge)
1050 elif edgeID not in self._graph._edgesWithID:
1051 self._subgraph._edgesWithID[edgeID] = edge
1052 else:
1053 raise DuplicateEdgeError(f"Edge ID '{edgeID}' already exists in this graph.", edgeID=edgeID)
1054 else:
1055 ex = NotInSameGraph(f"Vertex {self!r} and vertex {vertex!r} are not in the same graph or subgraph.")
1056 ex.add_note("An edge can only connect vertices within the same graph or subgraph.")
1057 ex.add_note("Use LinkToVertex or LinkFromVertex to connect vertices across subgraph boundaries.")
1058 raise ex
1060 return edge
1062 def EdgeToNewVertex(
1063 self,
1064 vertexID: Nullable[VertexIDType] = None,
1065 vertexValue: Nullable[VertexValueType] = None,
1066 vertexWeight: Nullable[VertexWeightType] = None,
1067 vertexKeyValuePairs: Nullable[Mapping[Hashable, Any]] = None,
1068 edgeID: Nullable[EdgeIDType] = None,
1069 edgeWeight: Nullable[EdgeWeightType] = None,
1070 edgeValue: Nullable[VertexValueType] = None,
1071 edgeKind: Enum = EdgeKind.Default,
1072 edgeKeyValuePairs: Nullable[Mapping[Hashable, Any]] = None
1073 ) -> Edge:
1074 """
1075 Create a new vertex and link that vertex by an outbound edge from this vertex.
1077 :param vertexID: Optional, the new vertex' optional ID.
1078 :param vertexValue: Optional, the new vertex' optional value.
1079 :param vertexWeight: Optional, the new vertex' optional weight.
1080 :param vertexKeyValuePairs: Optional, mapping (dictionary) of key-value-pairs for the new vertex.
1081 :param edgeID: Optional, the edge's optional ID for the new edge object.
1082 :param edgeWeight: Optional, the edge's optional weight for the new edge object.
1083 :param edgeValue: Optional, the edge's optional value for the new edge object.
1084 :param edgeKind: Optional, the kind of the new edge object. Default: :attr:`EdgeKind.Default`.
1085 :param edgeKeyValuePairs: Optional, mapping (dictionary) of key-value-pairs for the new edge object.
1086 :returns: The edge object linking this vertex and the created vertex.
1087 :raises DuplicateEdgeError: If the given edge ID already exists in this graph or subgraph.
1088 :raises NotInSameGraph: If both vertices are not in the same graph or subgraph. |br|
1089 Use :meth:`LinkToVertex` or :meth:`LinkFromVertex` to connect vertices across
1090 subgraph boundaries.
1092 .. seealso::
1094 :meth:`EdgeToVertex`
1095 |rarr| Create an outbound edge from this vertex to the referenced vertex.
1096 :meth:`EdgeFromVertex`
1097 |rarr| Create an inbound edge from the referenced vertex to this vertex.
1098 :meth:`EdgeFromNewVertex`
1099 |rarr| Create a new vertex and link that vertex by an inbound edge to this vertex.
1100 :meth:`LinkToVertex`
1101 |rarr| Create an outbound link from this vertex to the referenced vertex.
1102 :meth:`LinkFromVertex`
1103 |rarr| Create an inbound link from the referenced vertex to this vertex.
1104 """
1105 vertex = Vertex(vertexID, vertexValue, vertexWeight, vertexKeyValuePairs, graph=self._graph) # , component=self._component)
1107 if self._subgraph is vertex._subgraph: 1107 ↛ 1131line 1107 didn't jump to line 1131 because the condition on line 1107 was always true
1108 edge = Edge(self, vertex, edgeID, edgeValue, edgeWeight, edgeKind, edgeKeyValuePairs)
1110 self._outboundEdges.append(edge)
1111 vertex._inboundEdges.append(edge)
1113 if self._subgraph is None: 1113 ↛ 1124line 1113 didn't jump to line 1124 because the condition on line 1113 was always true
1114 # TODO: move into Edge?
1115 # TODO: keep _graph pointer in edge and then register edge on graph?
1116 if edgeID is None: 1116 ↛ 1118line 1116 didn't jump to line 1118 because the condition on line 1116 was always true
1117 self._graph._edgesWithoutID.append(edge)
1118 elif edgeID not in self._graph._edgesWithID:
1119 self._graph._edgesWithID[edgeID] = edge
1120 else:
1121 raise DuplicateEdgeError(f"Edge ID '{edgeID}' already exists in this graph.", edgeID=edgeID)
1122 else:
1123 # TODO: keep _graph pointer in edge and then register edge on graph?
1124 if edgeID is None:
1125 self._subgraph._edgesWithoutID.append(edge)
1126 elif edgeID not in self._graph._edgesWithID:
1127 self._subgraph._edgesWithID[edgeID] = edge
1128 else:
1129 raise DuplicateEdgeError(f"Edge ID '{edgeID}' already exists in this graph.", edgeID=edgeID)
1130 else:
1131 ex = NotInSameGraph(f"Vertex {self!r} and vertex {vertex!r} are not in the same graph or subgraph.")
1132 ex.add_note("An edge can only connect vertices within the same graph or subgraph.")
1133 ex.add_note("Use LinkToVertex or LinkFromVertex to connect vertices across subgraph boundaries.")
1134 raise ex
1136 return edge
1138 def EdgeFromNewVertex(
1139 self,
1140 vertexID: Nullable[VertexIDType] = None,
1141 vertexValue: Nullable[VertexValueType] = None,
1142 vertexWeight: Nullable[VertexWeightType] = None,
1143 vertexKeyValuePairs: Nullable[Mapping[Hashable, Any]] = None,
1144 edgeID: Nullable[EdgeIDType] = None,
1145 edgeWeight: Nullable[EdgeWeightType] = None,
1146 edgeValue: Nullable[VertexValueType] = None,
1147 edgeKind: Enum = EdgeKind.Default,
1148 edgeKeyValuePairs: Nullable[Mapping[Hashable, Any]] = None
1149 ) -> Edge:
1150 """
1151 Create a new vertex and link that vertex by an inbound edge to this vertex.
1153 :param vertexID: Optional, the new vertex' optional ID.
1154 :param vertexValue: Optional, the new vertex' optional value.
1155 :param vertexWeight: Optional, the new vertex' optional weight.
1156 :param vertexKeyValuePairs: Optional, mapping (dictionary) of key-value-pairs for the new vertex.
1157 :param edgeID: Optional, the edge's optional ID for the new edge object.
1158 :param edgeWeight: Optional, the edge's optional weight for the new edge object.
1159 :param edgeValue: Optional, the edge's optional value for the new edge object.
1160 :param edgeKind: Optional, the kind of the new edge object. Default: :attr:`EdgeKind.Default`.
1161 :param edgeKeyValuePairs: Optional, mapping (dictionary) of key-value-pairs for the new edge object.
1162 :returns: The edge object linking this vertex and the created vertex.
1163 :raises DuplicateEdgeError: If the given edge ID already exists in this graph or subgraph.
1164 :raises NotInSameGraph: If both vertices are not in the same graph or subgraph. |br|
1165 Use :meth:`LinkToVertex` or :meth:`LinkFromVertex` to connect vertices across
1166 subgraph boundaries.
1168 .. seealso::
1170 :meth:`EdgeToVertex`
1171 |rarr| Create an outbound edge from this vertex to the referenced vertex.
1172 :meth:`EdgeFromVertex`
1173 |rarr| Create an inbound edge from the referenced vertex to this vertex.
1174 :meth:`EdgeToNewVertex`
1175 |rarr| Create a new vertex and link that vertex by an outbound edge from this vertex.
1176 :meth:`LinkToVertex`
1177 |rarr| Create an outbound link from this vertex to the referenced vertex.
1178 :meth:`LinkFromVertex`
1179 |rarr| Create an inbound link from the referenced vertex to this vertex.
1180 """
1181 vertex = Vertex(vertexID, vertexValue, vertexWeight, vertexKeyValuePairs, graph=self._graph) # , component=self._component)
1183 if self._subgraph is vertex._subgraph: 1183 ↛ 1207line 1183 didn't jump to line 1207 because the condition on line 1183 was always true
1184 edge = Edge(vertex, self, edgeID, edgeValue, edgeWeight, edgeKind, edgeKeyValuePairs)
1186 vertex._outboundEdges.append(edge)
1187 self._inboundEdges.append(edge)
1189 if self._subgraph is None: 1189 ↛ 1200line 1189 didn't jump to line 1200 because the condition on line 1189 was always true
1190 # TODO: move into Edge?
1191 # TODO: keep _graph pointer in edge and then register edge on graph?
1192 if edgeID is None: 1192 ↛ 1194line 1192 didn't jump to line 1194 because the condition on line 1192 was always true
1193 self._graph._edgesWithoutID.append(edge)
1194 elif edgeID not in self._graph._edgesWithID:
1195 self._graph._edgesWithID[edgeID] = edge
1196 else:
1197 raise DuplicateEdgeError(f"Edge ID '{edgeID}' already exists in this graph.", edgeID=edgeID)
1198 else:
1199 # TODO: keep _graph pointer in edge and then register edge on graph?
1200 if edgeID is None:
1201 self._subgraph._edgesWithoutID.append(edge)
1202 elif edgeID not in self._graph._edgesWithID:
1203 self._subgraph._edgesWithID[edgeID] = edge
1204 else:
1205 raise DuplicateEdgeError(f"Edge ID '{edgeID}' already exists in this graph.", edgeID=edgeID)
1206 else:
1207 ex = NotInSameGraph(f"Vertex {self!r} and vertex {vertex!r} are not in the same graph or subgraph.")
1208 ex.add_note("An edge can only connect vertices within the same graph or subgraph.")
1209 ex.add_note("Use LinkToVertex or LinkFromVertex to connect vertices across subgraph boundaries.")
1210 raise ex
1212 return edge
1214 def LinkToVertex(
1215 self,
1216 vertex: Vertex,
1217 linkID: Nullable[EdgeIDType] = None,
1218 linkWeight: Nullable[EdgeWeightType] = None,
1219 linkValue: Nullable[VertexValueType] = None,
1220 linkKind: Enum = LinkKind.Default,
1221 keyValuePairs: Nullable[Mapping[Hashable, Any]] = None
1222 ) -> Link:
1223 """
1224 Create an outbound link from this vertex to the referenced vertex.
1226 :param vertex: The vertex to be linked to.
1227 :param linkID: Optional, the link's optional ID for the new link object.
1228 :param linkWeight: Optional, the link's optional weight for the new link object.
1229 :param linkValue: Optional, the link's optional value for the new link object.
1230 :param linkKind: Optional, the kind of the new link object. Default: :attr:`LinkKind.Default`.
1231 :param keyValuePairs: Optional, mapping (dictionary) of key-value-pairs for the new link object.
1232 :returns: The link object linking this vertex and the referenced vertex.
1233 :raises DuplicateEdgeError: If the given link ID already exists in this graph.
1234 :raises NotInDifferentSubgraphs: If both vertices are in the same subgraph - a link connects vertices *across*
1235 subgraph boundaries. |br|
1236 Use :meth:`EdgeToVertex` or :meth:`EdgeFromVertex` to connect vertices within
1237 the same subgraph.
1239 .. seealso::
1241 :meth:`EdgeToVertex`
1242 |rarr| Create an outbound edge from this vertex to the referenced vertex.
1243 :meth:`EdgeFromVertex`
1244 |rarr| Create an inbound edge from the referenced vertex to this vertex.
1245 :meth:`EdgeToNewVertex`
1246 |rarr| Create a new vertex and link that vertex by an outbound edge from this vertex.
1247 :meth:`EdgeFromNewVertex`
1248 |rarr| Create a new vertex and link that vertex by an inbound edge to this vertex.
1249 :meth:`LinkFromVertex`
1250 |rarr| Create an inbound link from the referenced vertex to this vertex.
1251 """
1252 if self._subgraph is vertex._subgraph:
1253 ex = NotInDifferentSubgraphs(f"Vertex {self!r} and vertex {vertex!r} are in the same subgraph.")
1254 ex.add_note("A link can only connect vertices across subgraph boundaries.")
1255 ex.add_note("Use EdgeToVertex or EdgeFromVertex to connect vertices within the same subgraph.")
1256 raise ex
1257 else:
1258 link = Link(self, vertex, linkID, linkValue, linkWeight, linkKind, keyValuePairs)
1260 self._outboundLinks.append(link)
1261 vertex._inboundLinks.append(link)
1263 if self._subgraph is None:
1264 # TODO: move into Edge?
1265 # TODO: keep _graph pointer in link and then register link on graph?
1266 if linkID is None: 1266 ↛ 1268line 1266 didn't jump to line 1268 because the condition on line 1266 was always true
1267 self._graph._linksWithoutID.append(link)
1268 elif linkID not in self._graph._linksWithID:
1269 self._graph._linksWithID[linkID] = link
1270 else:
1271 raise DuplicateEdgeError(f"Link ID '{linkID}' already exists in this graph.", edgeID=linkID)
1272 else:
1273 # TODO: keep _graph pointer in link and then register link on graph?
1274 if linkID is None:
1275 self._subgraph._linksWithoutID.append(link)
1276 vertex._subgraph._linksWithoutID.append(link)
1277 elif linkID not in self._graph._linksWithID: 1277 ↛ 1281line 1277 didn't jump to line 1281 because the condition on line 1277 was always true
1278 self._subgraph._linksWithID[linkID] = link
1279 vertex._subgraph._linksWithID[linkID] = link
1280 else:
1281 raise DuplicateEdgeError(f"Link ID '{linkID}' already exists in this graph.", edgeID=linkID)
1283 return link
1285 def LinkFromVertex(
1286 self,
1287 vertex: Vertex,
1288 linkID: Nullable[EdgeIDType] = None,
1289 linkWeight: Nullable[EdgeWeightType] = None,
1290 linkValue: Nullable[VertexValueType] = None,
1291 linkKind: Enum = LinkKind.Default,
1292 keyValuePairs: Nullable[Mapping[Hashable, Any]] = None
1293 ) -> Link:
1294 """
1295 Create an inbound link from the referenced vertex to this vertex.
1297 :param vertex: The vertex to be linked from.
1298 :param linkID: Optional, the link's optional ID for the new link object.
1299 :param linkWeight: Optional, the link's optional weight for the new link object.
1300 :param linkValue: Optional, the link's optional value for the new link object.
1301 :param linkKind: Optional, the kind of the new link object. Default: :attr:`LinkKind.Default`.
1302 :param keyValuePairs: Optional, mapping (dictionary) of key-value-pairs for the new link object.
1303 :returns: The link object linking the referenced vertex and this vertex.
1304 :raises DuplicateEdgeError: If the given link ID already exists in this graph.
1305 :raises NotInDifferentSubgraphs: If both vertices are in the same subgraph - a link connects vertices *across*
1306 subgraph boundaries. |br|
1307 Use :meth:`EdgeToVertex` or :meth:`EdgeFromVertex` to connect vertices within
1308 the same subgraph.
1310 .. seealso::
1312 :meth:`EdgeToVertex`
1313 |rarr| Create an outbound edge from this vertex to the referenced vertex.
1314 :meth:`EdgeFromVertex`
1315 |rarr| Create an inbound edge from the referenced vertex to this vertex.
1316 :meth:`EdgeToNewVertex`
1317 |rarr| Create a new vertex and link that vertex by an outbound edge from this vertex.
1318 :meth:`EdgeFromNewVertex`
1319 |rarr| Create a new vertex and link that vertex by an inbound edge to this vertex.
1320 :meth:`LinkToVertex`
1321 |rarr| Create an outbound link from this vertex to the referenced vertex.
1322 """
1323 if self._subgraph is vertex._subgraph:
1324 ex = NotInDifferentSubgraphs(f"Vertex {self!r} and vertex {vertex!r} are in the same subgraph.")
1325 ex.add_note("A link can only connect vertices across subgraph boundaries.")
1326 ex.add_note("Use EdgeToVertex or EdgeFromVertex to connect vertices within the same subgraph.")
1327 raise ex
1328 else:
1329 link = Link(vertex, self, linkID, linkValue, linkWeight, linkKind, keyValuePairs)
1331 vertex._outboundLinks.append(link)
1332 self._inboundLinks.append(link)
1334 if self._subgraph is None: 1334 ↛ 1337line 1334 didn't jump to line 1337 because the condition on line 1334 was never true
1335 # TODO: move into Edge?
1336 # TODO: keep _graph pointer in link and then register link on graph?
1337 if linkID is None:
1338 self._graph._linksWithoutID.append(link)
1339 elif linkID not in self._graph._linksWithID:
1340 self._graph._linksWithID[linkID] = link
1341 else:
1342 raise DuplicateEdgeError(f"Link ID '{linkID}' already exists in this graph.", edgeID=linkID)
1343 else:
1344 # TODO: keep _graph pointer in link and then register link on graph?
1345 if linkID is None: 1345 ↛ 1348line 1345 didn't jump to line 1348 because the condition on line 1345 was always true
1346 self._subgraph._linksWithoutID.append(link)
1347 vertex._subgraph._linksWithoutID.append(link)
1348 elif linkID not in self._graph._linksWithID:
1349 self._subgraph._linksWithID[linkID] = link
1350 vertex._subgraph._linksWithID[linkID] = link
1351 else:
1352 raise DuplicateEdgeError(f"Link ID '{linkID}' already exists in this graph.", edgeID=linkID)
1354 return link
1356 def HasEdgeToDestination(self, destination: Vertex) -> bool:
1357 """
1358 Check if this vertex is linked to another vertex by any outbound edge.
1360 :param destination: Destination vertex to check.
1361 :returns: ``True``, if the destination vertex is a destination on any outbound edge.
1363 .. seealso::
1365 :meth:`HasEdgeFromSource`
1366 |rarr| Check if this vertex is linked to another vertex by any inbound edge.
1367 :meth:`HasLinkToDestination`
1368 |rarr| Check if this vertex is linked to another vertex by any outbound link.
1369 :meth:`HasLinkFromSource`
1370 |rarr| Check if this vertex is linked to another vertex by any inbound link.
1371 """
1372 for edge in self._outboundEdges:
1373 if destination is edge.Destination:
1374 return True
1376 return False
1378 def HasEdgeFromSource(self, source: Vertex) -> bool:
1379 """
1380 Check if this vertex is linked to another vertex by any inbound edge.
1382 :param source: Source vertex to check.
1383 :returns: ``True``, if the source vertex is a source on any inbound edge.
1385 .. seealso::
1387 :meth:`HasEdgeToDestination`
1388 |rarr| Check if this vertex is linked to another vertex by any outbound edge.
1389 :meth:`HasLinkToDestination`
1390 |rarr| Check if this vertex is linked to another vertex by any outbound link.
1391 :meth:`HasLinkFromSource`
1392 |rarr| Check if this vertex is linked to another vertex by any inbound link.
1393 """
1394 for edge in self._inboundEdges:
1395 if source is edge.Source: 1395 ↛ 1394line 1395 didn't jump to line 1394 because the condition on line 1395 was always true
1396 return True
1398 return False
1400 def HasLinkToDestination(self, destination: Vertex) -> bool:
1401 """
1402 Check if this vertex is linked to another vertex by any outbound link.
1404 :param destination: Destination vertex to check.
1405 :returns: ``True``, if the destination vertex is a destination on any outbound link.
1407 .. seealso::
1409 :meth:`HasEdgeToDestination`
1410 |rarr| Check if this vertex is linked to another vertex by any outbound edge.
1411 :meth:`HasEdgeFromSource`
1412 |rarr| Check if this vertex is linked to another vertex by any inbound edge.
1413 :meth:`HasLinkFromSource`
1414 |rarr| Check if this vertex is linked to another vertex by any inbound link.
1415 """
1416 for link in self._outboundLinks:
1417 if destination is link.Destination: 1417 ↛ 1416line 1417 didn't jump to line 1416 because the condition on line 1417 was always true
1418 return True
1420 return False
1422 def HasLinkFromSource(self, source: Vertex) -> bool:
1423 """
1424 Check if this vertex is linked to another vertex by any inbound link.
1426 :param source: Source vertex to check.
1427 :returns: ``True``, if the source vertex is a source on any inbound link.
1429 .. seealso::
1431 :meth:`HasEdgeToDestination`
1432 |rarr| Check if this vertex is linked to another vertex by any outbound edge.
1433 :meth:`HasEdgeFromSource`
1434 |rarr| Check if this vertex is linked to another vertex by any inbound edge.
1435 :meth:`HasLinkToDestination`
1436 |rarr| Check if this vertex is linked to another vertex by any outbound link.
1437 """
1438 for link in self._inboundLinks:
1439 if source is link.Source: 1439 ↛ 1438line 1439 didn't jump to line 1438 because the condition on line 1439 was always true
1440 return True
1442 return False
1444 def DeleteEdgeTo(self, destination: Vertex) -> None:
1445 """
1446 Delete the outbound edge to the given vertex.
1448 :param destination: The vertex the edge points to.
1449 :raises EdgeNotFoundError: If no outbound edge to that vertex exists.
1450 """
1451 for edge in self._outboundEdges:
1452 if edge._destination is destination: 1452 ↛ 1451line 1452 didn't jump to line 1451 because the condition on line 1452 was always true
1453 break
1454 else:
1455 raise EdgeNotFoundError(f"No outbound edge found to '{destination!r}'.", source=self, destination=destination)
1457 edge.Delete()
1459 def DeleteEdgeFrom(self, source: Vertex) -> None:
1460 """
1461 Delete the inbound edge from the given vertex.
1463 :param source: The vertex the edge comes from.
1464 :raises EdgeNotFoundError: If no inbound edge from that vertex exists.
1465 """
1466 for edge in self._inboundEdges: 1466 ↛ 1467line 1466 didn't jump to line 1467 because the loop on line 1466 never started
1467 if edge._source is source:
1468 break
1469 else:
1470 raise EdgeNotFoundError(f"No inbound edge found from '{source!r}'.", source=source, destination=self)
1472 edge.Delete()
1474 def DeleteLinkTo(self, destination: Vertex) -> None:
1475 """
1476 Delete the outbound link to the given vertex.
1478 :param destination: The vertex the link points to.
1479 :raises LinkNotFoundError: If no outbound link to that vertex exists.
1480 """
1481 for link in self._outboundLinks: 1481 ↛ 1482line 1481 didn't jump to line 1482 because the loop on line 1481 never started
1482 if link._destination is destination:
1483 break
1484 else:
1485 raise LinkNotFoundError(f"No outbound link found to '{destination!r}'.", source=self, destination=destination)
1487 link.Delete()
1489 def DeleteLinkFrom(self, source: Vertex) -> None:
1490 """
1491 Delete the inbound link from the given vertex.
1493 :param source: The vertex the link comes from.
1494 :raises LinkNotFoundError: If no inbound link from that vertex exists.
1495 """
1496 for link in self._inboundLinks: 1496 ↛ 1497line 1496 didn't jump to line 1497 because the loop on line 1496 never started
1497 if link._source is source:
1498 break
1499 else:
1500 raise LinkNotFoundError(f"No inbound link found from '{source!r}'.", source=source, destination=self)
1502 link.Delete()
1504 def Copy(self, graph: Graph, copyDict: bool = False, linkingKeyToOriginalVertex: Nullable[str] = None, linkingKeyFromOriginalVertex: Nullable[str] = None) -> Vertex:
1505 """
1506 Creates a copy of this vertex in another graph.
1508 Optionally, the vertex's attached attributes (key-value-pairs) can be copied and a linkage between both vertices
1509 can be established.
1511 :param graph: The graph, the vertex is created in.
1512 :param copyDict: Optional, if ``True``, copy all attached attributes into the new vertex.
1513 :param linkingKeyToOriginalVertex: Optional, if not ``None``, add a key-value-pair using this parameter as key
1514 from new vertex to the original vertex.
1515 :param linkingKeyFromOriginalVertex: Optional, if not ``None``, add a key-value-pair using this parameter as key
1516 from original vertex to the new vertex.
1517 :returns: The newly created vertex.
1518 :raises SameGraphError: If source graph and destination graph are the same.
1519 """
1520 if graph is self._graph:
1521 raise SameGraphError("Graph to copy this vertex to, is the same graph.", graph=graph)
1523 vertex = Vertex(self._id, self._value, self._weight, graph=graph)
1524 if copyDict:
1525 vertex._dict = self._dict.copy()
1527 if linkingKeyToOriginalVertex is not None:
1528 vertex._dict[linkingKeyToOriginalVertex] = self
1530 if linkingKeyFromOriginalVertex is not None:
1531 self._dict[linkingKeyFromOriginalVertex] = vertex
1533 return vertex
1535 def IterateOutboundEdges(self, predicate: Nullable[Predicate[Edge]] = None) -> Generator[Edge, None, None]:
1536 """
1537 Iterate all or selected outbound edges of this vertex.
1539 If parameter ``predicate`` is not None, the given filter function is used to skip edges in the generator.
1541 :param predicate: Optional, filter function accepting any edge and returning a boolean.
1542 :returns: A generator to iterate all outbound edges.
1543 """
1544 if predicate is None:
1545 for edge in self._outboundEdges:
1546 yield edge
1547 else:
1548 for edge in self._outboundEdges:
1549 if predicate(edge):
1550 yield edge
1552 def IterateInboundEdges(self, predicate: Nullable[Predicate[Edge]] = None) -> Generator[Edge, None, None]:
1553 """
1554 Iterate all or selected inbound edges of this vertex.
1556 If parameter ``predicate`` is not None, the given filter function is used to skip edges in the generator.
1558 :param predicate: Optional, filter function accepting any edge and returning a boolean.
1559 :returns: A generator to iterate all inbound edges.
1560 """
1561 if predicate is None:
1562 for edge in self._inboundEdges:
1563 yield edge
1564 else:
1565 for edge in self._inboundEdges:
1566 if predicate(edge):
1567 yield edge
1569 def IterateOutboundLinks(self, predicate: Nullable[Predicate[Link]] = None) -> Generator[Link, None, None]:
1570 """
1571 Iterate all or selected outbound links of this vertex.
1573 If parameter ``predicate`` is not None, the given filter function is used to skip links in the generator.
1575 :param predicate: Optional, filter function accepting any link and returning a boolean.
1576 :returns: A generator to iterate all outbound links.
1577 """
1578 if predicate is None:
1579 for link in self._outboundLinks:
1580 yield link
1581 else:
1582 for link in self._outboundLinks:
1583 if predicate(link):
1584 yield link
1586 def IterateInboundLinks(self, predicate: Nullable[Predicate[Link]] = None) -> Generator[Link, None, None]:
1587 """
1588 Iterate all or selected inbound links of this vertex.
1590 If parameter ``predicate`` is not None, the given filter function is used to skip links in the generator.
1592 :param predicate: Optional, filter function accepting any link and returning a boolean.
1593 :returns: A generator to iterate all inbound links.
1594 """
1595 if predicate is None:
1596 for link in self._inboundLinks:
1597 yield link
1598 else:
1599 for link in self._inboundLinks:
1600 if predicate(link):
1601 yield link
1603 def IterateSuccessorVertices(self, predicate: Nullable[Predicate[Edge]] = None) -> Generator[Vertex, None, None]:
1604 """
1605 Iterate all or selected successor vertices of this vertex.
1607 If parameter ``predicate`` is not None, the given filter function is used to skip successors in the generator.
1609 :param predicate: Optional, filter function accepting any edge and returning a boolean.
1610 :returns: A generator to iterate all successor vertices.
1611 """
1612 if predicate is None: 1612 ↛ 1616line 1612 didn't jump to line 1616 because the condition on line 1612 was always true
1613 for edge in self._outboundEdges:
1614 yield edge.Destination
1615 else:
1616 for edge in self._outboundEdges:
1617 if predicate(edge):
1618 yield edge.Destination
1620 def IteratePredecessorVertices(self, predicate: Nullable[Predicate[Edge]] = None) -> Generator[Vertex, None, None]:
1621 """
1622 Iterate all or selected predecessor vertices of this vertex.
1624 If parameter ``predicate`` is not None, the given filter function is used to skip predecessors in the generator.
1626 :param predicate: Optional, filter function accepting any edge and returning a boolean.
1627 :returns: A generator to iterate all predecessor vertices.
1628 """
1629 if predicate is None:
1630 for edge in self._inboundEdges:
1631 yield edge.Source
1632 else:
1633 for edge in self._inboundEdges:
1634 if predicate(edge):
1635 yield edge.Source
1637 def IterateVerticesBFS(self) -> Generator[Vertex, None, None]:
1638 """
1639 A generator to iterate all reachable vertices starting from this node in breadth-first search (BFS) order.
1641 :returns: A generator to iterate vertices traversed in BFS order.
1643 .. seealso::
1645 :meth:`IterateVerticesDFS`
1646 |rarr| Iterate all reachable vertices **depth-first search** order.
1647 """
1648 visited: set[Vertex] = set()
1649 queue: Deque[Vertex] = deque()
1651 yield self
1652 visited.add(self)
1653 for edge in self._outboundEdges:
1654 nextVertex = edge.Destination
1655 if nextVertex is not self: 1655 ↛ 1653line 1655 didn't jump to line 1653 because the condition on line 1655 was always true
1656 queue.appendleft(nextVertex)
1657 visited.add(nextVertex)
1659 while queue:
1660 vertex = queue.pop()
1661 yield vertex
1662 for edge in vertex._outboundEdges:
1663 nextVertex = edge.Destination
1664 if nextVertex not in visited:
1665 queue.appendleft(nextVertex)
1666 visited.add(nextVertex)
1668 def IterateVerticesDFS(self) -> Generator[Vertex, None, None]:
1669 """
1670 A generator to iterate all reachable vertices starting from this node in depth-first search (DFS) order.
1672 :returns: A generator to iterate vertices traversed in DFS order.
1674 .. seealso::
1676 :meth:`IterateVerticesBFS`
1677 |rarr| Iterate all reachable vertices **breadth-first search** order.
1679 Wikipedia - https://en.wikipedia.org/wiki/Depth-first_search
1680 """
1681 visited: set[Vertex] = set()
1682 stack: list[typing_Iterator[Edge]] = list()
1684 yield self
1685 visited.add(self)
1686 stack.append(iter(self._outboundEdges))
1688 while True:
1689 try:
1690 edge = next(stack[-1])
1691 nextVertex = edge._destination
1692 if nextVertex not in visited:
1693 visited.add(nextVertex)
1694 yield nextVertex
1695 if len(nextVertex._outboundEdges) != 0:
1696 stack.append(iter(nextVertex._outboundEdges))
1697 except StopIteration:
1698 stack.pop()
1700 if len(stack) == 0:
1701 return
1703 def IterateAllOutboundPathsAsVertexList(self) -> Generator[tuple[Vertex, ...], None, None]:
1704 """
1705 Iterate all paths starting at this vertex, each as a tuple of vertices.
1707 The traversal is depth-first and keeps the vertices of the current path in a set, so a cycle is detected
1708 instead of iterated endlessly. A vertex without outbound edges yields the path containing only itself.
1710 :returns: A generator yielding one tuple of vertices per path.
1711 :raises CycleError: If a cycle is detected while walking a path.
1712 """
1713 if len(self._outboundEdges) == 0:
1714 yield (self, )
1715 return
1717 visited: set[Vertex] = set()
1718 vertexStack: list[Vertex] = list()
1719 iteratorStack: list[typing_Iterator[Edge]] = list()
1721 visited.add(self)
1722 vertexStack.append(self)
1723 iteratorStack.append(iter(self._outboundEdges))
1725 while True:
1726 try:
1727 edge = next(iteratorStack[-1])
1728 nextVertex = edge._destination
1729 if nextVertex in visited:
1730 ex = CycleError("Loop detected.", path=(*vertexStack, nextVertex))
1731 ex.add_note("First loop is:")
1732 for i, vertex in enumerate(vertexStack):
1733 ex.add_note(f" {i}: {vertex!r}")
1734 raise ex
1736 vertexStack.append(nextVertex)
1737 if len(nextVertex._outboundEdges) == 0:
1738 yield tuple(vertexStack)
1739 vertexStack.pop()
1740 else:
1741 iteratorStack.append(iter(nextVertex._outboundEdges))
1743 except StopIteration:
1744 vertexStack.pop()
1745 iteratorStack.pop()
1747 if len(vertexStack) == 0:
1748 return
1750 def ShortestPathToByHops(self, destination: Vertex) -> Generator[Vertex, None, None]:
1751 """
1752 Compute the shortest path (by hops) between this vertex and the destination vertex.
1754 A generator is return to iterate all vertices along the path including source and destination vertex.
1756 The search algorithm is breadth-first search (BFS) based. The found solution, if any, is not unique but deterministic
1757 as long as the graph was not modified (e.g. ordering of edges on vertices).
1759 :param destination: The destination vertex to reach.
1760 :returns: A generator to iterate all vertices on the path found between this vertex and the
1761 destination vertex.
1762 :raises DestinationNotReachable: If the destination vertex cannot be reached from this vertex.
1763 """
1764 # Trivial case if start is destination
1765 if self is destination: 1765 ↛ 1766line 1765 didn't jump to line 1766 because the condition on line 1765 was never true
1766 yield self
1767 return
1769 # Local struct to create multiple linked-lists forming a paths from current node back to the starting point
1770 # (actually a tree). Each node holds a reference to the vertex it represents.
1771 # Hint: slotted classes are faster than '@dataclasses.dataclass'.
1772 class Node(metaclass=ExtendedType, slots=True):
1773 """A node of the search tree: the vertex it represents and its predecessor on the path."""
1774 parent: Node #: Predecessor on the path back to the starting point.
1775 ref: Vertex #: The vertex this node represents.
1777 def __init__(self, parent: Node, ref: Vertex) -> None:
1778 """
1779 Initialize a search tree node.
1781 :param parent: Predecessor on the path back to the starting point.
1782 :param ref: The vertex this node represents.
1783 """
1784 self.parent = parent
1785 self.ref = ref
1787 def __str__(self) -> str:
1788 """
1789 Return a string representation of this search tree node.
1791 :returns: The ID of the vertex this node represents.
1792 """
1793 return f"Vertex: {self.ref.ID}"
1795 # Initially add all reachable vertices to a queue if vertices to be processed.
1796 startNode = Node(None, self)
1797 visited: set[Vertex] = set()
1798 queue: Deque[Node] = deque()
1800 # Add starting vertex and all its children to the processing list.
1801 # If a child is the destination, break immediately else go into 'else' branch and use BFS algorithm.
1802 visited.add(self)
1803 for edge in self._outboundEdges:
1804 nextVertex = edge.Destination
1805 if nextVertex is destination: 1805 ↛ 1807line 1805 didn't jump to line 1807 because the condition on line 1805 was never true
1806 # Child is destination, so construct the last node for path traversal and break from loop.
1807 destinationNode = Node(startNode, nextVertex)
1808 break
1810 if nextVertex is not self: 1810 ↛ 1803line 1810 didn't jump to line 1803 because the condition on line 1810 was always true
1811 # Ignore backward-edges and side-edges.
1812 # Here self-edges, because there is only the starting vertex in the list of visited edges.
1813 visited.add(nextVertex)
1814 queue.appendleft(Node(startNode, nextVertex))
1815 else:
1816 # Process queue until destination is found or no further vertices are reachable.
1817 while queue:
1818 node = queue.pop()
1819 for edge in node.ref._outboundEdges:
1820 nextVertex = edge.Destination
1821 # Next reachable vertex is destination, so construct the last node for path traversal and break from loop.
1822 if nextVertex is destination:
1823 destinationNode = Node(node, nextVertex)
1824 break
1826 # Ignore backward-edges and side-edges.
1827 if nextVertex not in visited:
1828 visited.add(nextVertex)
1829 queue.appendleft(Node(node, nextVertex))
1830 # Next 3 lines realize a double-break if break was called in inner loop, otherwise continue with outer loop.
1831 else:
1832 continue
1833 break
1834 else:
1835 # All reachable vertices have been processed, but destination was not among them.
1836 raise DestinationNotReachable("Destination is not reachable.")
1838 # Reverse order of linked list from destinationNode to startNode
1839 currentNode = destinationNode
1840 previousNode = destinationNode.parent
1841 currentNode.parent = None
1842 while previousNode is not None:
1843 node = previousNode.parent
1844 previousNode.parent = currentNode
1845 currentNode = previousNode
1846 previousNode = node
1848 # Scan reversed linked-list and yield referenced vertices
1849 yield startNode.ref
1850 node = startNode.parent
1851 while node is not None:
1852 yield node.ref
1853 node = node.parent
1855 def ShortestPathToByWeight(self, destination: Vertex) -> Generator[Vertex, None, None]:
1856 """
1857 Compute the shortest path (by edge weight) between this vertex and the destination vertex.
1859 A generator is return to iterate all vertices along the path including source and destination vertex.
1861 The search algorithm is based on Dijkstra algorithm and using :mod:`heapq`. The found solution, if any, is not
1862 unique but deterministic as long as the graph was not modified (e.g. ordering of edges on vertices).
1864 :param destination: The destination vertex to reach.
1865 :returns: A generator to iterate all vertices on the path found between this vertex and the
1866 destination vertex.
1867 :raises DestinationNotReachable: If the destination vertex cannot be reached from this vertex.
1868 """
1869 # Improvements: both-sided Dijkstra (search from start and destination to reduce discovered area.
1871 # Trivial case if start is destination
1872 if self is destination: 1872 ↛ 1873line 1872 didn't jump to line 1873 because the condition on line 1872 was never true
1873 yield self
1874 return
1876 # Local struct to create multiple-linked lists forming a paths from current node back to the starting point
1877 # (actually a tree). Each node holds the overall weight from start to current node and a reference to the vertex it
1878 # represents.
1879 # Hint: slotted classes are faster than '@dataclasses.dataclass'.
1880 class Node(metaclass=ExtendedType, slots=True):
1881 """A node of the search tree: the vertex, its predecessor, and the accumulated weight to reach it."""
1882 parent: Node #: Predecessor on the path back to the starting point.
1883 distance: EdgeWeightType #: Accumulated edge weight from the starting point to this node.
1884 ref: Vertex #: The vertex this node represents.
1886 def __init__(self, parent: Node, distance: EdgeWeightType, ref: Vertex) -> None:
1887 """
1888 Initialize a search tree node.
1890 :param parent: Predecessor on the path back to the starting point.
1891 :param distance: Accumulated edge weight from the starting point to this node.
1892 :param ref: The vertex this node represents.
1893 """
1894 self.parent = parent
1895 self.distance = distance
1896 self.ref = ref
1898 def __lt__(self, other: Any) -> bool:
1899 """
1900 Compare two search tree nodes by their accumulated distance, so they can be kept in a priority queue.
1902 :param other: Second operand.
1903 :returns: ``True``, if this node is closer to the starting point than the second operand.
1904 """
1905 return self.distance < other.distance
1907 def __str__(self) -> str:
1908 """
1909 Return a string representation of this search tree node.
1911 :returns: The ID of the vertex this node represents.
1912 """
1913 return f"Vertex: {self.ref.ID}"
1915 visited: set[Vertex] = set()
1916 startNode = Node(None, 0, self)
1917 priorityQueue = [startNode]
1919 # Add starting vertex and all its children to the processing list.
1920 # If a child is the destination, break immediately else go into 'else' branch and use Dijkstra algorithm.
1921 visited.add(self)
1922 for edge in self._outboundEdges:
1923 nextVertex = edge.Destination
1924 # Child is destination, so construct the last node for path traversal and break from loop.
1925 if nextVertex is destination: 1925 ↛ 1926line 1925 didn't jump to line 1926 because the condition on line 1925 was never true
1926 destinationNode = Node(startNode, edge._weight, nextVertex)
1927 break
1929 # Ignore backward-edges and side-edges.
1930 # Here self-edges, because there is only the starting vertex in the list of visited edges.
1931 if nextVertex is not self: 1931 ↛ 1922line 1931 didn't jump to line 1922 because the condition on line 1931 was always true
1932 visited.add(nextVertex)
1933 heapq.heappush(priorityQueue, Node(startNode, edge._weight, nextVertex))
1934 else:
1935 # Process priority queue until destination is found or no further vertices are reachable.
1936 while priorityQueue: 1936 ↛ 1955line 1936 didn't jump to line 1955 because the condition on line 1936 was always true
1937 node = heapq.heappop(priorityQueue)
1938 for edge in node.ref._outboundEdges:
1939 nextVertex = edge.Destination
1940 # Next reachable vertex is destination, so construct the last node for path traversal and break from loop.
1941 if nextVertex is destination:
1942 destinationNode = Node(node, node.distance + edge._weight, nextVertex)
1943 break
1945 # Ignore backward-edges and side-edges.
1946 if nextVertex not in visited:
1947 visited.add(nextVertex)
1948 heapq.heappush(priorityQueue, Node(node, node.distance + edge._weight, nextVertex))
1949 # Next 3 lines realize a double-break if break was called in inner loop, otherwise continue with outer loop.
1950 else:
1951 continue
1952 break
1953 else:
1954 # All reachable vertices have been processed, but destination was not among them.
1955 raise DestinationNotReachable("Destination is not reachable.")
1957 # Reverse order of linked-list from destinationNode to startNode
1958 currentNode = destinationNode
1959 previousNode = destinationNode.parent
1960 currentNode.parent = None
1961 while previousNode is not None:
1962 node = previousNode.parent
1963 previousNode.parent = currentNode
1964 currentNode = previousNode
1965 previousNode = node
1967 # Scan reversed linked-list and yield referenced vertices
1968 yield startNode.ref, startNode.distance
1969 node = startNode.parent
1970 while node is not None:
1971 yield node.ref, node.distance
1972 node = node.parent
1974 # Other possible algorithms:
1975 # * Bellman-Ford
1976 # * Floyd-Warshall
1978 # def PathExistsTo(self, destination: 'Vertex'):
1979 # raise NotImplementedError()
1980 # # DFS
1981 # # Union find
1982 #
1983 # def MaximumFlowTo(self, destination: 'Vertex'):
1984 # raise NotImplementedError()
1985 # # Ford-Fulkerson algorithm
1986 # # Edmons-Karp algorithm
1987 # # Dinic's algorithm
1989 def ConvertToTree(self) -> Node:
1990 """
1991 Converts all reachable vertices from this starting vertex to a tree of :class:`~pyTooling.Tree.Node` instances.
1993 The tree is traversed using depths-first-search.
1995 :returns: Root node of the resulting tree, representing this vertex.
1996 :raises NotATreeError: If the graph reachable from this vertex is not a tree, because a vertex has more than one
1997 parent.
1998 """
1999 visited: set[Vertex] = set()
2000 stack: list[tuple[Node, typing_Iterator[Edge]]] = list()
2002 root = Node(nodeID=self._id, value=self._value)
2003 root._dict = self._dict.copy()
2005 visited.add(self)
2006 stack.append((root, iter(self._outboundEdges)))
2008 while True:
2009 try:
2010 edge = next(stack[-1][1])
2011 nextVertex = edge._destination
2012 if nextVertex not in visited: 2012 ↛ 2018line 2012 didn't jump to line 2018 because the condition on line 2012 was always true
2013 node = Node(nextVertex._id, nextVertex._value, parent=stack[-1][0])
2014 visited.add(nextVertex)
2015 if len(nextVertex._outboundEdges) != 0:
2016 stack.append((node, iter(nextVertex._outboundEdges)))
2017 else:
2018 raise NotATreeError("The directed subgraph is not a tree.")
2019 # TODO: compute cycle:
2020 # a) branch 1 is described in stack
2021 # b) branch 2 can be found by walking from joint to root in the tree
2022 except StopIteration:
2023 stack.pop()
2025 if len(stack) == 0:
2026 return root
2028 def __repr__(self) -> str:
2029 """
2030 Returns a detailed string representation of the vertex.
2032 :returns: The detailed string representation of the vertex.
2033 """
2034 vertexID = value = ""
2035 sep = ": "
2036 if self._id is not None:
2037 vertexID = f"{sep}vertexID='{self._id}'"
2038 sep = "; "
2040 if self._value is not None: 2040 ↛ 2041line 2040 didn't jump to line 2041 because the condition on line 2040 was never true
2041 value = f"{sep}value='{self._value}'"
2043 return f"<vertex{vertexID}{value}>"
2045 def __str__(self) -> str:
2046 """
2047 Return a string representation of the vertex.
2049 Order of resolution:
2051 1. If :attr:`_value` is not None, return the string representation of :attr:`_value`.
2052 2. If :attr:`_id` is not None, return the string representation of :attr:`_id`.
2053 3. Else, return :meth:`__repr__`.
2055 :returns: The resolved string representation of the vertex.
2056 """
2057 if self._value is not None: 2057 ↛ 2058line 2057 didn't jump to line 2058 because the condition on line 2057 was never true
2058 return str(self._value)
2059 elif self._id is not None: 2059 ↛ 2060line 2059 didn't jump to line 2060 because the condition on line 2059 was never true
2060 return str(self._id)
2061 else:
2062 return self.__repr__()
2065@export
2066class BaseEdge(
2067 BaseWithIDValueAndWeight[EdgeIDType, EdgeValueType, EdgeWeightType],
2068 Generic[EdgeIDType, EdgeValueType, EdgeWeightType, EdgeKindType]
2069):
2070 """
2071 An **edge** can have a unique ID, a kind, a value, a weight and attached meta information as key-value-pairs. All
2072 edges are directed.
2073 """
2074 _source: Vertex #: Vertex the edge starts at.
2075 _destination: Vertex #: Vertex the edge ends at.
2076 _kind: EdgeKindType #: Kind of the edge, e.g. an :class:`EdgeKind` or a :class:`LinkKind` member.
2078 def __init__(
2079 self,
2080 source: Vertex,
2081 destination: Vertex,
2082 edgeID: Nullable[EdgeIDType] = None,
2083 value: Nullable[EdgeValueType] = None,
2084 weight: Nullable[EdgeWeightType] = None,
2085 kind: Nullable[EdgeKindType] = None,
2086 keyValuePairs: Nullable[Mapping[Hashable, Any]] = None
2087 ) -> None:
2088 """
2089 Initialize an edge between a source and a destination vertex.
2091 :param source: The source of the new edge.
2092 :param destination: The destination of the new edge.
2093 :param edgeID: Optional, unique ID for the new edge.
2094 :param value: Optional, value for the new edge.
2095 :param weight: Optional, weight for the new edge.
2096 :param kind: Optional, the kind of the new edge, a member of an enumeration.
2097 :param keyValuePairs: Optional, mapping (dictionary) of key-value-pairs.
2098 :raises ValueError: If parameter 'kind' is None.
2099 :raises TypeError: If parameter 'kind' is not an enumeration member.
2100 """
2101 super().__init__(edgeID, value, weight, keyValuePairs)
2103 if kind is None:
2104 raise ValueError("Parameter 'kind' is None.")
2105 elif not isinstance(kind, Enum):
2106 ex = TypeError("Parameter 'kind' is not an enumeration member.")
2107 ex.add_note(f"Got type '{getFullyQualifiedName(kind)}'.")
2108 raise ex
2110 self._source = source
2111 self._destination = destination
2112 self._kind = kind
2114 component = source._component
2115 if component is not destination._component:
2116 # TODO: should it be divided into with/without ID?
2117 oldComponent = destination._component
2118 if len(oldComponent._vertices) > len(component._vertices):
2119 component, oldComponent = oldComponent, component
2121 for vertex in oldComponent._vertices:
2122 vertex._component = component
2123 component._vertices.add(vertex)
2124 component._graph._components.remove(oldComponent)
2125 del oldComponent
2127 @readonly
2128 def Source(self) -> Vertex:
2129 """
2130 Read-only property to access the source (:attr:`_source`) of an edge.
2132 :returns: The source of an edge.
2133 """
2134 return self._source
2136 @readonly
2137 def Destination(self) -> Vertex:
2138 """
2139 Read-only property to access the destination (:attr:`_destination`) of an edge.
2141 :returns: The destination of an edge.
2142 """
2143 return self._destination
2145 @readonly
2146 def Kind(self) -> EdgeKindType:
2147 """
2148 Read-only property to access the kind (:attr:`_kind`) of an edge.
2150 The kind is given when the edge is created - :attr:`EdgeKind.Default` or :attr:`LinkKind.Default`, unless stated
2151 otherwise.
2153 :returns: The kind of the edge.
2154 """
2155 return self._kind
2157 def Reverse(self) -> None:
2158 """Reverse the direction of this edge."""
2159 swap = self._source
2160 self._source = self._destination
2161 self._destination = swap
2164@export
2165class Edge(
2166 BaseEdge[EdgeIDType, EdgeValueType, EdgeWeightType, EdgeKindType],
2167 Generic[EdgeIDType, EdgeValueType, EdgeWeightType, EdgeKindType]
2168):
2169 """
2170 An **edge** can have a unique ID, a kind, a value, a weight and attached meta information as key-value-pairs. All
2171 edges are directed.
2173 The kind of an edge might be modified by graph algorithms like :meth:`BaseGraph.AnnotateTransitiveEdges`.
2174 """
2176 def __init__(
2177 self,
2178 source: Vertex,
2179 destination: Vertex,
2180 edgeID: Nullable[EdgeIDType] = None,
2181 value: Nullable[EdgeValueType] = None,
2182 weight: Nullable[EdgeWeightType] = None,
2183 kind: Enum = EdgeKind.Default,
2184 keyValuePairs: Nullable[Mapping[Hashable, Any]] = None
2185 ) -> None:
2186 """
2187 Initialize an edge between two vertices of the same graph or subgraph.
2189 :param source: The source of the new edge.
2190 :param destination: The destination of the new edge.
2191 :param edgeID: Optional, unique ID for the new edge.
2192 :param value: Optional, value for the new edge.
2193 :param weight: Optional, weight for the new edge.
2194 :param kind: Optional, kind of the new edge - a member of :class:`EdgeKind` or of an enumeration of the
2195 user's own. Default: :attr:`EdgeKind.Default`.
2196 :param keyValuePairs: Optional, mapping (dictionary) of key-value-pairs.
2197 :raises TypeError: If parameter 'weight' is not of the graph's edge weight type.
2198 :raises ValueError: If parameter 'kind' is None.
2199 :raises TypeError: If parameter 'kind' is not an enumeration member.
2200 :raises NotInSameGraph: If source and destination vertex are not in the same graph or subgraph.
2201 """
2202 if not isinstance(source, Vertex):
2203 ex = TypeError("Parameter 'source' is not of type 'Vertex'.")
2204 ex.add_note(f"Got type '{getFullyQualifiedName(source)}'.")
2205 raise ex
2207 if not isinstance(destination, Vertex):
2208 ex = TypeError("Parameter 'destination' is not of type 'Vertex'.")
2209 ex.add_note(f"Got type '{getFullyQualifiedName(destination)}'.")
2210 raise ex
2212 if edgeID is not None and not isinstance(edgeID, Hashable):
2213 ex = TypeError("Parameter 'edgeID' is not of type 'EdgeIDType'.")
2214 ex.add_note(f"Got type '{getFullyQualifiedName(edgeID)}'.")
2215 raise ex
2217 # if value is not None and not isinstance(value, Vertex):
2218 # raise TypeError("Parameter 'value' is not of type 'EdgeValueType'.")
2219 if weight is not None and not isinstance(weight, (int, float)):
2220 ex = TypeError("Parameter 'weight' is not of type 'EdgeWeightType'.")
2221 ex.add_note(f"Got type '{getFullyQualifiedName(weight)}'.")
2222 raise ex
2224 if source._graph is not destination._graph:
2225 raise NotInSameGraph("Source vertex and destination vertex are not in same graph.")
2227 super().__init__(source, destination, edgeID, value, weight, kind, keyValuePairs)
2229 def Delete(self) -> None:
2230 """
2231 Delete this edge from both of its vertices and from the graph or subgraph it belongs to.
2232 """
2233 # Remove from Source and Destination
2234 self._source._outboundEdges.remove(self)
2235 self._destination._inboundEdges.remove(self)
2237 self._Unregister()
2238 self._Delete()
2240 def _Unregister(self) -> None:
2241 """
2242 Remove this edge from the graph or subgraph it was registered on.
2244 An edge is registered on the subgraph it lives in, otherwise on the graph. Called by :meth:`Delete` and by
2245 :meth:`Vertex.Delete`, which unlinks the vertices itself.
2246 """
2247 container = self._source._graph if self._source._subgraph is None else self._source._subgraph
2248 if self._id is None:
2249 container._edgesWithoutID.remove(self)
2250 else:
2251 del container._edgesWithID[self._id]
2253 def _Delete(self) -> None:
2254 """
2255 Delete the edge's attached attributes, after it was disconnected.
2256 """
2257 super().Delete()
2259 def Reverse(self) -> None:
2260 """Reverse the direction of this edge."""
2261 self._source._outboundEdges.remove(self)
2262 self._source._inboundEdges.append(self)
2263 self._destination._inboundEdges.remove(self)
2264 self._destination._outboundEdges.append(self)
2266 super().Reverse()
2269@export
2270class Link(
2271 BaseEdge[LinkIDType, LinkValueType, LinkWeightType, LinkKindType],
2272 Generic[LinkIDType, LinkValueType, LinkWeightType, LinkKindType]
2273):
2274 """
2275 A **link** can have a unique ID, a kind, a value, a weight and attached meta information as key-value-pairs. All
2276 links are directed.
2277 """
2279 def __init__(
2280 self,
2281 source: Vertex,
2282 destination: Vertex,
2283 linkID: Nullable[LinkIDType] = None,
2284 value: Nullable[LinkValueType] = None,
2285 weight: Nullable[LinkWeightType] = None,
2286 kind: Enum = LinkKind.Default,
2287 keyValuePairs: Nullable[Mapping[Hashable, Any]] = None
2288 ) -> None:
2289 """
2290 Initialize a link between two vertices of different subgraphs.
2292 :param source: The source of the new link.
2293 :param destination: The destination of the new link.
2294 :param linkID: Optional, unique ID for the new link.
2295 :param value: Optional, value for the new v.
2296 :param weight: Optional, weight for the new link.
2297 :param kind: Optional, kind of the new link - a member of :class:`LinkKind` or of an enumeration of the
2298 user's own. Default: :attr:`LinkKind.Default`.
2299 :param keyValuePairs: Optional, mapping (dictionary) of key-value-pairs.
2300 :raises TypeError: If parameter 'weight' is not of the graph's link weight type.
2301 :raises ValueError: If parameter 'kind' is None.
2302 :raises TypeError: If parameter 'kind' is not an enumeration member.
2303 :raises NotInSameGraph: If source and destination vertex are in the same subgraph, where an edge is to be used.
2304 """
2305 if not isinstance(source, Vertex):
2306 ex = TypeError("Parameter 'source' is not of type 'Vertex'.")
2307 ex.add_note(f"Got type '{getFullyQualifiedName(source)}'.")
2308 raise ex
2310 if not isinstance(destination, Vertex):
2311 ex = TypeError("Parameter 'destination' is not of type 'Vertex'.")
2312 ex.add_note(f"Got type '{getFullyQualifiedName(destination)}'.")
2313 raise ex
2315 if linkID is not None and not isinstance(linkID, Hashable):
2316 ex = TypeError("Parameter 'linkID' is not of type 'LinkIDType'.")
2317 ex.add_note(f"Got type '{getFullyQualifiedName(linkID)}'.")
2318 raise ex
2320 # if value is not None and not isinstance(value, Vertex):
2321 # raise TypeError("Parameter 'value' is not of type 'EdgeValueType'.")
2322 if weight is not None and not isinstance(weight, (int, float)):
2323 ex = TypeError("Parameter 'weight' is not of type 'EdgeWeightType'.")
2324 ex.add_note(f"Got type '{getFullyQualifiedName(weight)}'.")
2325 raise ex
2327 if source._graph is not destination._graph:
2328 raise NotInSameGraph("Source vertex and destination vertex are not in same graph.")
2330 super().__init__(source, destination, linkID, value, weight, kind, keyValuePairs)
2332 def Delete(self) -> None:
2333 """
2334 Delete this link from both of its vertices and from the graph and subgraphs it belongs to.
2335 """
2336 self._source._outboundLinks.remove(self)
2337 self._destination._inboundLinks.remove(self)
2339 self._Unregister()
2340 self._Delete()
2342 def _Unregister(self) -> None:
2343 """
2344 Remove this link from the graph or the subgraphs it was registered on.
2346 A link crossing a subgraph boundary is registered on both subgraphs, a link between two top-level vertices on
2347 the graph. Called by :meth:`Delete` and by :meth:`Vertex.Delete`, which unlinks the vertices itself.
2348 """
2349 if self._source._subgraph is None: 2349 ↛ 2350line 2349 didn't jump to line 2350 because the condition on line 2349 was never true
2350 containers = (self._source._graph, )
2351 else:
2352 containers = tuple(sg for sg in (self._source._subgraph, self._destination._subgraph) if sg is not None)
2354 for container in containers:
2355 if self._id is None:
2356 container._linksWithoutID.remove(self)
2357 else:
2358 del container._linksWithID[self._id]
2360 def _Delete(self) -> None:
2361 """
2362 Delete the link's attached attributes, after it was disconnected.
2363 """
2364 super().Delete()
2366 def Reverse(self) -> None:
2367 """Reverse the direction of this link."""
2368 self._source._outboundLinks.remove(self)
2369 self._source._inboundLinks.append(self)
2370 self._destination._inboundLinks.remove(self)
2371 self._destination._outboundLinks.append(self)
2373 super().Reverse()
2376@export
2377class BaseGraph(
2378 BaseWithName,
2379 Generic[
2380 VertexIDType, VertexWeightType, VertexValueType,
2381 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeKindType,
2382 LinkIDType, LinkWeightType, LinkValueType, LinkKindType
2383 ]
2384):
2385 """
2386 .. todo:: GRAPH::BaseGraph Needs documentation.
2387 """
2389 _verticesWithID: dict[VertexIDType, Vertex[VertexIDType, VertexWeightType, VertexValueType, EdgeIDType, EdgeWeightType, EdgeValueType, EdgeKindType, LinkIDType, LinkWeightType, LinkValueType, LinkKindType]] #: Vertices with an ID, by ID.
2390 _verticesWithoutID: list[Vertex[VertexIDType, VertexWeightType, VertexValueType, EdgeIDType, EdgeWeightType, EdgeValueType, EdgeKindType, LinkIDType, LinkWeightType, LinkValueType, LinkKindType]] #: Vertices without an ID, in insertion order.
2391 _edgesWithID: dict[EdgeIDType, Edge[EdgeIDType, EdgeValueType, EdgeWeightType, EdgeKindType]] #: Edges with an ID, by ID.
2392 _edgesWithoutID: list[Edge[EdgeIDType, EdgeValueType, EdgeWeightType, EdgeKindType]] #: Edges without an ID, in insertion order.
2393 _linksWithID: dict[LinkIDType, Link[LinkIDType, LinkValueType, LinkWeightType, LinkKindType]] #: Links between subgraphs with an ID, by ID.
2394 _linksWithoutID: list[Link[LinkIDType, LinkValueType, LinkWeightType, LinkKindType]] #: Links between subgraphs without an ID, in insertion order.
2396 def __init__(
2397 self,
2398 name: Nullable[str] = None,
2399 keyValuePairs: Nullable[Mapping[Hashable, Any]] = None
2400 #, vertices: Nullable[Iterable[Vertex]] = None) -> None:
2401 ) -> None:
2402 """
2403 .. todo:: GRAPH::BaseGraph::init Needs documentation.
2405 :param name: Optional, name of the graph.
2406 :param keyValuePairs: Optional, mapping (dictionary) of key-value-pairs.
2407 """
2408 super().__init__(name, keyValuePairs)
2410 self._verticesWithoutID = []
2411 self._verticesWithID = {}
2412 self._edgesWithoutID = []
2413 self._edgesWithID = {}
2414 self._linksWithoutID = []
2415 self._linksWithID = {}
2417 def __del__(self) -> None:
2418 """
2419 .. todo:: GRAPH::BaseGraph::del Needs documentation.
2420 """
2421 try:
2422 del self._verticesWithoutID
2423 del self._verticesWithID
2424 del self._edgesWithoutID
2425 del self._edgesWithID
2426 del self._linksWithoutID
2427 del self._linksWithID
2428 except AttributeError:
2429 pass
2431 super().__del__()
2433 @readonly
2434 def VertexCount(self) -> int:
2435 """Read-only property to return the number of vertices in this graph.
2437 :returns: The number of vertices in this graph."""
2438 return len(self._verticesWithoutID) + len(self._verticesWithID)
2440 @readonly
2441 def EdgeCount(self) -> int:
2442 """Read-only property to return the number of edges in this graph.
2444 :returns: The number of edges in this graph."""
2445 return len(self._edgesWithoutID) + len(self._edgesWithID)
2447 @readonly
2448 def LinkCount(self) -> int:
2449 """Read-only property to return the number of links in this graph.
2451 :returns: The number of links in this graph."""
2452 return len(self._linksWithoutID) + len(self._linksWithID)
2454 def IterateVertices(self, predicate: Nullable[Predicate[Vertex]] = None) -> Generator[Vertex[VertexIDType, VertexWeightType, VertexValueType, EdgeIDType, EdgeWeightType, EdgeValueType, EdgeKindType, LinkIDType, LinkWeightType, LinkValueType, LinkKindType], None, None]:
2455 """
2456 Iterate all or selected vertices of a graph.
2458 If parameter ``predicate`` is not None, the given filter function is used to skip vertices in the generator.
2460 :param predicate: Optional, filter function accepting any vertex and returning a boolean.
2461 :returns: A generator to iterate all vertices.
2462 """
2463 if predicate is None:
2464 yield from self._verticesWithoutID
2465 yield from self._verticesWithID.values()
2467 else:
2468 for vertex in self._verticesWithoutID:
2469 if predicate(vertex):
2470 yield vertex
2472 for vertex in self._verticesWithID.values():
2473 if predicate(vertex):
2474 yield vertex
2476 def IterateRoots(self, predicate: Nullable[Predicate[Vertex]] = None) -> Generator[Vertex[VertexIDType, VertexWeightType, VertexValueType, EdgeIDType, EdgeWeightType, EdgeValueType, EdgeKindType, LinkIDType, LinkWeightType, LinkValueType, LinkKindType], None, None]:
2477 """
2478 Iterate all or selected roots (vertices without inbound edges / without predecessors) of a graph.
2480 If parameter ``predicate`` is not None, the given filter function is used to skip vertices in the generator.
2482 :param predicate: Optional, filter function accepting any vertex and returning a boolean.
2483 :returns: A generator to iterate all vertices without inbound edges.
2485 .. seealso::
2487 :meth:`BaseGraph.IterateLeafs <pyTooling.Graph.BaseGraph.IterateLeafs>`
2488 |rarr| Iterate leafs of a graph.
2489 :meth:`Vertex.IsRoot <pyTooling.Graph.Vertex.IsRoot>`
2490 |rarr| Check if a vertex is a root vertex in the graph.
2491 :meth:`Vertex.IsLeaf <pyTooling.Graph.Vertex.IsLeaf>`
2492 |rarr| Check if a vertex is a leaf vertex in the graph.
2493 """
2494 if predicate is None:
2495 for vertex in self._verticesWithoutID:
2496 if len(vertex._inboundEdges) == 0:
2497 yield vertex
2499 for vertex in self._verticesWithID.values(): 2499 ↛ 2500line 2499 didn't jump to line 2500 because the loop on line 2499 never started
2500 if len(vertex._inboundEdges) == 0:
2501 yield vertex
2502 else:
2503 for vertex in self._verticesWithoutID:
2504 if len(vertex._inboundEdges) == 0 and predicate(vertex):
2505 yield vertex
2507 for vertex in self._verticesWithID.values(): 2507 ↛ 2508line 2507 didn't jump to line 2508 because the loop on line 2507 never started
2508 if len(vertex._inboundEdges) == 0 and predicate(vertex):
2509 yield vertex
2511 def IterateLeafs(self, predicate: Nullable[Predicate[Vertex]] = None) -> Generator[Vertex[VertexIDType, VertexWeightType, VertexValueType, EdgeIDType, EdgeWeightType, EdgeValueType, EdgeKindType, LinkIDType, LinkWeightType, LinkValueType, LinkKindType], None, None]:
2512 """
2513 Iterate all or selected leafs (vertices without outbound edges / without successors) of a graph.
2515 If parameter ``predicate`` is not None, the given filter function is used to skip vertices in the generator.
2517 :param predicate: Optional, filter function accepting any vertex and returning a boolean.
2518 :returns: A generator to iterate all vertices without outbound edges.
2520 .. seealso::
2522 :meth:`BaseGraph.IterateRoots <pyTooling.Graph.BaseGraph.IterateRoots>`
2523 |rarr| Iterate roots of a graph.
2524 :meth:`Vertex.IsRoot <pyTooling.Graph.Vertex.IsRoot>`
2525 |rarr| Check if a vertex is a root vertex in the graph.
2526 :meth:`Vertex.IsLeaf <pyTooling.Graph.Vertex.IsLeaf>`
2527 |rarr| Check if a vertex is a leaf vertex in the graph.
2528 """
2529 if predicate is None:
2530 for vertex in self._verticesWithoutID:
2531 if len(vertex._outboundEdges) == 0:
2532 yield vertex
2534 for vertex in self._verticesWithID.values():
2535 if len(vertex._outboundEdges) == 0:
2536 yield vertex
2537 else:
2538 for vertex in self._verticesWithoutID:
2539 if len(vertex._outboundEdges) == 0 and predicate(vertex):
2540 yield vertex
2542 for vertex in self._verticesWithID.values():
2543 if len(vertex._outboundEdges) == 0 and predicate(vertex): 2543 ↛ 2544line 2543 didn't jump to line 2544 because the condition on line 2543 was never true
2544 yield vertex
2546 # def IterateBFS(self, predicate: Nullable[Predicate[Vertex]] = None) -> Generator[Vertex[VertexIDType, VertexWeightType, VertexValueType, EdgeIDType, EdgeWeightType, EdgeValueType, EdgeKindType, LinkIDType, LinkWeightType, LinkValueType, LinkKindType], None, None]:
2547 # raise NotImplementedError()
2548 #
2549 # def IterateDFS(self, predicate: Nullable[Predicate[Vertex]] = None) -> Generator[Vertex[VertexIDType, VertexWeightType, VertexValueType, EdgeIDType, EdgeWeightType, EdgeValueType, EdgeKindType, LinkIDType, LinkWeightType, LinkValueType, LinkKindType], None, None]:
2550 # raise NotImplementedError()
2552 def IterateTopologically(self, predicate: Nullable[Predicate[Vertex]] = None) -> Generator[Vertex[VertexIDType, VertexWeightType, VertexValueType, EdgeIDType, EdgeWeightType, EdgeValueType, EdgeKindType, LinkIDType, LinkWeightType, LinkValueType, LinkKindType], None, None]:
2553 """
2554 Iterate all or selected vertices in topological order.
2556 A vertex is yielded after every destination of its outbound edges, so the vertices without outbound edges come
2557 first. An edge points the way control flows or jobs execute, so the order is the reverse execution order: a control
2558 flow graph yields its exit first.
2560 If parameter ``predicate`` is not None, the given filter function is used to skip vertices in the generator.
2562 :param predicate: Optional, filter function accepting any vertex and returning a boolean.
2563 :returns: A generator to iterate all vertices in topological order.
2564 :raises CycleError: If the graph contains a cycle, so no topological order exists.
2565 :raises InternalError: If the algorithm's internal state became inconsistent.
2566 """
2567 outboundEdgeCounts = {}
2568 leafVertices = []
2570 for vertex in self._verticesWithoutID:
2571 if (count := len(vertex._outboundEdges)) == 0:
2572 leafVertices.append(vertex)
2573 else:
2574 outboundEdgeCounts[vertex] = count
2576 for vertex in self._verticesWithID.values():
2577 if (count := len(vertex._outboundEdges)) == 0:
2578 leafVertices.append(vertex)
2579 else:
2580 outboundEdgeCounts[vertex] = count
2582 if not leafVertices: 2582 ↛ 2583line 2582 didn't jump to line 2583 because the condition on line 2582 was never true
2583 raise CycleError("Graph has no leafs. Thus, no topological sorting exists.")
2585 overallCount = len(outboundEdgeCounts) + len(leafVertices)
2587 def removeVertex(vertex: Vertex):
2588 """
2589 Nested function removing a vertex from the counting, and queuing the vertices that became leafs.
2591 :param vertex: The vertex that was just yielded.
2592 """
2593 nonlocal overallCount
2594 overallCount -= 1
2595 for inboundEdge in vertex._inboundEdges:
2596 sourceVertex = inboundEdge.Source
2597 count = outboundEdgeCounts[sourceVertex] - 1
2598 outboundEdgeCounts[sourceVertex] = count
2599 if count == 0:
2600 leafVertices.append(sourceVertex)
2602 if predicate is None:
2603 for vertex in leafVertices:
2604 yield vertex
2606 removeVertex(vertex)
2607 else:
2608 for vertex in leafVertices:
2609 if predicate(vertex):
2610 yield vertex
2612 removeVertex(vertex)
2614 if overallCount == 0:
2615 return
2616 elif overallCount > 0:
2617 raise CycleError("Graph has remaining vertices. Thus, the graph has at least one cycle.")
2619 raise InternalError("Graph data structure is corrupted.") # pragma: no cover
2621 def IterateEdges(self, predicate: Nullable[Predicate[Edge]] = None) -> Generator[Edge[EdgeIDType, EdgeValueType, EdgeWeightType, EdgeKindType], None, None]:
2622 """
2623 Iterate all or selected edges of a graph.
2625 If parameter ``predicate`` is not None, the given filter function is used to skip edges in the generator.
2627 :param predicate: Optional, filter function accepting any edge and returning a boolean.
2628 :returns: A generator to iterate all edges.
2629 """
2630 if predicate is None:
2631 yield from self._edgesWithoutID
2632 yield from self._edgesWithID.values()
2634 else:
2635 for edge in self._edgesWithoutID:
2636 if predicate(edge):
2637 yield edge
2639 for edge in self._edgesWithID.values():
2640 if predicate(edge):
2641 yield edge
2643 def IterateLinks(self, predicate: Nullable[Predicate[Link]] = None) -> Generator[Link[LinkIDType, LinkValueType, LinkWeightType, LinkKindType], None, None]:
2644 """
2645 Iterate all or selected links of a graph.
2647 If parameter ``predicate`` is not None, the given filter function is used to skip links in the generator.
2649 :param predicate: Optional, filter function accepting any link and returning a boolean.
2650 :returns: A generator to iterate all links.
2651 """
2652 if predicate is None: 2652 ↛ 2657line 2652 didn't jump to line 2657 because the condition on line 2652 was always true
2653 yield from self._linksWithoutID
2654 yield from self._linksWithID.values()
2656 else:
2657 for link in self._linksWithoutID:
2658 if predicate(link):
2659 yield link
2661 for link in self._linksWithID.values():
2662 if predicate(link):
2663 yield link
2665 def ReverseEdges(self, predicate: Nullable[Predicate[Edge]] = None) -> None:
2666 """
2667 Reverse all or selected edges of a graph.
2669 If parameter ``predicate`` is not None, the given filter function is used to skip edges.
2671 :param predicate: Optional, filter function accepting any edge and returning a boolean.
2672 """
2673 if predicate is None:
2674 for edge in self._edgesWithoutID:
2675 swap = edge._source
2676 edge._source = edge._destination
2677 edge._destination = swap
2679 for edge in self._edgesWithID.values():
2680 swap = edge._source
2681 edge._source = edge._destination
2682 edge._destination = swap
2684 for vertex in self._verticesWithoutID:
2685 swap = vertex._inboundEdges
2686 vertex._inboundEdges = vertex._outboundEdges
2687 vertex._outboundEdges = swap
2689 for vertex in self._verticesWithID.values():
2690 swap = vertex._inboundEdges
2691 vertex._inboundEdges = vertex._outboundEdges
2692 vertex._outboundEdges = swap
2693 else:
2694 for edge in self._edgesWithoutID:
2695 if predicate(edge):
2696 edge.Reverse()
2698 for edge in self._edgesWithID.values():
2699 if predicate(edge):
2700 edge.Reverse()
2702 def ReverseLinks(self, predicate: Nullable[Predicate[Link]] = None) -> None:
2703 """
2704 Reverse all or selected links of a graph.
2706 If parameter ``predicate`` is not None, the given filter function is used to skip links.
2708 :param predicate: Optional, filter function accepting any link and returning a boolean.
2709 """
2710 if predicate is None:
2711 for link in self._linksWithoutID:
2712 swap = link._source
2713 link._source = link._destination
2714 link._destination = swap
2716 for link in self._linksWithID.values():
2717 swap = link._source
2718 link._source = link._destination
2719 link._destination = swap
2721 for vertex in self._verticesWithoutID:
2722 swap = vertex._inboundLinks
2723 vertex._inboundLinks = vertex._outboundLinks
2724 vertex._outboundLinks = swap
2726 for vertex in self._verticesWithID.values():
2727 swap = vertex._inboundLinks
2728 vertex._inboundLinks = vertex._outboundLinks
2729 vertex._outboundLinks = swap
2730 else:
2731 for link in self._linksWithoutID:
2732 if predicate(link):
2733 link.Reverse()
2735 for link in self._linksWithID.values():
2736 if predicate(link):
2737 link.Reverse()
2739 def RemoveEdges(self, predicate: Nullable[Predicate[Edge]] = None) -> None:
2740 """
2741 Remove all or selected edges of a graph.
2743 If parameter ``predicate`` is not None, the given filter function is used to skip edges.
2745 :param predicate: Optional, filter function accepting any edge and returning a boolean.
2746 """
2747 if predicate is None:
2748 for edge in self._edgesWithoutID:
2749 edge._Delete()
2751 for edge in self._edgesWithID.values():
2752 edge._Delete()
2754 self._edgesWithoutID = []
2755 self._edgesWithID = {}
2757 for vertex in self._verticesWithoutID:
2758 vertex._inboundEdges = []
2759 vertex._outboundEdges = []
2761 for vertex in self._verticesWithID.values():
2762 vertex._inboundEdges = []
2763 vertex._outboundEdges = []
2765 else:
2766 delEdges = [edge for edge in self._edgesWithID.values() if predicate(edge)]
2767 for edge in delEdges:
2768 del self._edgesWithID[edge._id]
2770 edge._source._outboundEdges.remove(edge)
2771 edge._destination._inboundEdges.remove(edge)
2772 edge._Delete()
2774 for edge in self._edgesWithoutID:
2775 if predicate(edge):
2776 self._edgesWithoutID.remove(edge)
2778 edge._source._outboundEdges.remove(edge)
2779 edge._destination._inboundEdges.remove(edge)
2780 edge._Delete()
2782 def RemoveLinks(self, predicate: Nullable[Predicate[Link]] = None) -> None:
2783 """
2784 Remove all or selected links of a graph.
2786 If parameter ``predicate`` is not None, the given filter function is used to skip links.
2788 :param predicate: Optional, filter function accepting any link and returning a boolean.
2789 """
2790 if predicate is None: 2790 ↛ 2809line 2790 didn't jump to line 2809 because the condition on line 2790 was always true
2791 for link in self._linksWithoutID: 2791 ↛ 2792line 2791 didn't jump to line 2792 because the loop on line 2791 never started
2792 link._Delete()
2794 for link in self._linksWithID.values():
2795 link._Delete()
2797 self._linksWithoutID = []
2798 self._linksWithID = {}
2800 for vertex in self._verticesWithoutID:
2801 vertex._inboundLinks = []
2802 vertex._outboundLinks = []
2804 for vertex in self._verticesWithID.values():
2805 vertex._inboundLinks = []
2806 vertex._outboundLinks = []
2808 else:
2809 delLinks = [link for link in self._linksWithID.values() if predicate(link)]
2810 for link in delLinks:
2811 del self._linksWithID[link._id]
2813 link._source._outboundLinks.remove(link)
2814 link._destination._inboundLinks.remove(link)
2815 link._Delete()
2817 for link in self._linksWithoutID:
2818 if predicate(link):
2819 self._linksWithoutID.remove(link)
2821 link._source._outboundLinks.remove(link)
2822 link._destination._inboundLinks.remove(link)
2823 link._Delete()
2825 def _DeleteElements(self) -> None:
2826 """
2827 Delete the vertices, edges and links registered on this graph or subgraph, and their attached attributes.
2829 Called by :meth:`Graph.Delete`, which deletes the subgraphs, views and components itself.
2830 """
2831 self.RemoveEdges()
2832 self.RemoveLinks()
2834 for vertex in self._verticesWithoutID:
2835 vertex._views = {}
2836 vertex._dict.clear()
2838 for vertex in self._verticesWithID.values():
2839 vertex._views = {}
2840 vertex._dict.clear()
2842 self._verticesWithoutID = []
2843 self._verticesWithID = {}
2845 def HasCycle(self) -> bool:
2846 """
2847 Check if the graph contains at least one cycle.
2849 The graph is traversed depth-first from every unvisited vertex; a vertex reached again while it is still on the
2850 current path closes a cycle.
2852 :returns: ``True``, if the graph contains a cycle.
2853 :raises InternalError: If the graph's data structure is corrupted.
2854 """
2855 # IsAcyclic ?
2857 # Handle trivial case if graph is empty
2858 if len(self._verticesWithID) + len(self._verticesWithoutID) == 0:
2859 return False
2861 outboundEdgeCounts = {}
2862 leafVertices = []
2864 for vertex in self._verticesWithoutID:
2865 if (count := len(vertex._outboundEdges)) == 0:
2866 leafVertices.append(vertex)
2867 else:
2868 outboundEdgeCounts[vertex] = count
2870 for vertex in self._verticesWithID.values():
2871 if (count := len(vertex._outboundEdges)) == 0:
2872 leafVertices.append(vertex)
2873 else:
2874 outboundEdgeCounts[vertex] = count
2876 # If there are no leafs, then each vertex has at least one inbound and one outbound edges. Thus, there is a cycle.
2877 if not leafVertices:
2878 return True
2880 overallCount = len(outboundEdgeCounts) + len(leafVertices)
2882 for vertex in leafVertices:
2883 overallCount -= 1
2884 for inboundEdge in vertex._inboundEdges:
2885 sourceVertex = inboundEdge.Source
2886 count = outboundEdgeCounts[sourceVertex] - 1
2887 outboundEdgeCounts[sourceVertex] = count
2888 if count == 0:
2889 leafVertices.append(sourceVertex)
2891 # If all vertices were processed, no cycle exists.
2892 if overallCount == 0:
2893 return False
2894 # If there are remaining vertices, then a cycle exists.
2895 elif overallCount > 0:
2896 return True
2898 raise InternalError("Graph data structure is corrupted.") # pragma: no cover
2900 def IterateTransitiveEdges(self) -> Generator[Edge, None, None]:
2901 """
2902 Iterate the edges a longer path already implies.
2904 An edge from ``A`` to ``C`` is implied, if ``C`` is also reachable from ``A`` through another vertex, e.g. by the
2905 edges ``A → B`` and ``B → C``. A second edge between the same two vertices is implied by the first. Removing every
2906 implied edge leaves the graph's *transitive reduction*: every vertex stays reachable from every vertex it was
2907 reachable from before, by the fewest edges. See :meth:`RemoveTransitiveEdges`.
2909 Only the edges of this graph are taken into account, not its links, and for a :class:`Graph` not the vertices of
2910 its subgraphs. A :class:`Subgraph` is reduced by calling the method on it.
2912 An edge is yielded as soon as it is found, and may be removed while iterating. In a graph with a cycle, edges of its
2913 acyclic part may be yielded before :exc:`CycleError` is raised.
2915 :returns: A generator to iterate the implied edges.
2916 :raises CycleError: If the graph contains a cycle, which has no unique transitive reduction.
2918 .. seealso::
2920 :meth:`IterateTransitiveEdgesWithPath`
2921 |rarr| Iterate the edges a longer path already implies, each with that path.
2922 :meth:`RemoveTransitiveEdges`
2923 |rarr| Remove the edges a longer path already implies.
2924 :meth:`IterateTopologically`
2925 |rarr| Iterate all or selected vertices in topological order.
2926 """
2927 if self.VertexCount == 0:
2928 return
2930 descendants: dict[Vertex, set[Vertex]] = {}
2932 # A vertex is yielded after every vertex it has an edge to, so its successors' descendants are known already.
2933 for vertex in self.IterateTopologically():
2934 successors = set()
2935 indirect = set()
2936 outboundEdges = tuple(vertex._outboundEdges)
2937 for edge in outboundEdges:
2938 indirect |= descendants[edge._destination]
2940 for edge in outboundEdges:
2941 if edge._destination in indirect or edge._destination in successors:
2942 yield edge
2943 else:
2944 successors.add(edge._destination)
2946 descendants[vertex] = successors | indirect
2948 def IterateTransitiveEdgesWithPath(self) -> Generator[tuple[Edge, tuple[Vertex, ...]], None, None]:
2949 """
2950 Iterate the edges a longer path already implies, each with that path.
2952 The edges are those :meth:`IterateTransitiveEdges` yields. An edge's path is a tuple of vertices from its source to
2953 its destination along direct edges, e.g. ``(A, B, C)`` for the edge ``A → C``. An edge is yielded as soon as it is
2954 found, and may be removed while iterating.
2956 :returns: A generator to iterate the implied edges, each with its path.
2957 :raises CycleError: If the graph contains a cycle, which has no unique transitive reduction.
2959 .. seealso::
2961 :meth:`IterateTransitiveEdges`
2962 |rarr| Iterate the edges a longer path already implies.
2963 """
2964 if self.VertexCount == 0: 2964 ↛ 2965line 2964 didn't jump to line 2965 because the condition on line 2964 was never true
2965 return
2967 # For every vertex, the vertices reachable from it are mapped to the direct successor they are reached through.
2968 reachable: dict[Vertex, dict[Vertex, Vertex]] = {}
2970 for vertex in self.IterateTopologically():
2971 outboundEdges = tuple(vertex._outboundEdges)
2972 indirect = set()
2973 for edge in outboundEdges:
2974 indirect.update(reachable[edge._destination])
2976 successors = []
2977 transitiveEdges = []
2978 for edge in outboundEdges:
2979 if edge._destination in indirect or edge._destination in successors:
2980 transitiveEdges.append(edge)
2981 else:
2982 successors.append(edge._destination)
2984 via = {}
2985 for successor in successors:
2986 via.setdefault(successor, successor)
2987 for descendant in reachable[successor]:
2988 via.setdefault(descendant, successor)
2989 reachable[vertex] = via
2991 for edge in transitiveEdges:
2992 path = [vertex]
2993 current = vertex
2994 while current is not edge._destination:
2995 current = reachable[current][edge._destination]
2996 path.append(current)
2998 yield edge, tuple(path)
3000 def RemoveTransitiveEdges(self) -> None:
3001 """
3002 Remove the edges a longer path already implies, which leaves the graph's *transitive reduction*.
3004 Reachability is preserved: every vertex stays reachable from every vertex it was reachable from before. The edges
3005 removed are those :meth:`IterateTransitiveEdges` yields. A graph with a cycle is left unchanged.
3007 :raises CycleError: If the graph contains a cycle, which has no unique transitive reduction.
3009 .. seealso::
3011 :meth:`IterateTransitiveEdges`
3012 |rarr| Iterate the edges a longer path already implies.
3013 """
3014 if self.HasCycle():
3015 raise CycleError("Graph has a cycle. Thus, no unique transitive reduction exists.")
3017 for edge in self.IterateTransitiveEdges():
3018 edge.Delete()
3020 def AnnotateTransitiveEdges(
3021 self,
3022 directKind: Enum = EdgeKind.Direct,
3023 transitiveKind: Enum = EdgeKind.Transitive,
3024 keyName: Nullable[str] = None
3025 ) -> None:
3026 """
3027 Mark every edge as direct or transitive, and optionally record the path implying a transitive edge.
3029 The edges marked transitive are those :meth:`IterateTransitiveEdges` yields; every other edge is marked direct.
3030 Nothing is removed, so the graph keeps every dependency and a consumer can still tell the implied ones apart. A
3031 graph with a cycle is left unchanged.
3033 If parameter ``keyName`` is given, a transitive edge gets the path implying it as a key-value-pair: a tuple of
3034 vertices from the edge's source to its destination along direct edges, e.g. ``(A, B, C)`` for ``A → C``. A direct
3035 edge's pair of that key is removed. ``"transitive.path"`` is a suggested key.
3037 :param directKind: Optional, the kind a direct edge gets - a member of :class:`EdgeKind` or of an enumeration
3038 of the user's own. Default: :attr:`EdgeKind.Direct`.
3039 :param transitiveKind: Optional, the kind a transitive edge gets. Default: :attr:`EdgeKind.Transitive`.
3040 :param keyName: Optional, the key the path of a transitive edge is stored as. Default: ``None``, no path is
3041 computed.
3042 :raises ValueError: If parameter 'directKind' or 'transitiveKind' is None.
3043 :raises TypeError: If parameter 'directKind' or 'transitiveKind' is not an enumeration member.
3044 :raises TypeError: If parameter 'keyName' is not a string.
3045 :raises CycleError: If the graph contains a cycle, which has no unique transitive reduction.
3047 .. seealso::
3049 :meth:`RemoveTransitiveEdges`
3050 |rarr| Remove the edges a longer path already implies.
3051 """
3052 for name, kind in (("directKind", directKind), ("transitiveKind", transitiveKind)):
3053 if kind is None:
3054 raise ValueError(f"Parameter '{name}' is None.")
3055 elif not isinstance(kind, Enum):
3056 ex = TypeError(f"Parameter '{name}' is not an enumeration member.")
3057 ex.add_note(f"Got type '{getFullyQualifiedName(kind)}'.")
3058 raise ex
3060 if self.HasCycle():
3061 raise CycleError("Graph has a cycle. Thus, no unique transitive reduction exists.")
3063 if keyName is None:
3064 for edge in (*self._edgesWithoutID, *self._edgesWithID.values()):
3065 edge._kind = directKind
3067 for edge in self.IterateTransitiveEdges():
3068 edge._kind = transitiveKind
3069 elif not isinstance(keyName, str):
3070 ex = TypeError("Parameter 'keyName' is not of type 'str'.")
3071 ex.add_note(f"Got type '{getFullyQualifiedName(keyName)}'.")
3072 raise ex
3073 else:
3074 for edge in (*self._edgesWithoutID, *self._edgesWithID.values()):
3075 edge._kind = directKind
3076 edge._dict.pop(keyName, None)
3078 for edge, path in self.IterateTransitiveEdgesWithPath():
3079 edge._kind = transitiveKind
3080 edge._dict[keyName] = path
3083@export
3084class Subgraph(
3085 BaseGraph[
3086 VertexIDType, VertexWeightType, VertexValueType,
3087 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeKindType,
3088 LinkIDType, LinkWeightType, LinkValueType, LinkKindType
3089 ],
3090 Generic[
3091 VertexIDType, VertexWeightType, VertexValueType,
3092 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeKindType,
3093 LinkIDType, LinkWeightType, LinkValueType, LinkKindType
3094 ]
3095):
3096 """
3097 .. todo:: GRAPH::Subgraph Needs documentation.
3098 """
3100 _graph: _Graph #: Reference to the graph this subgraph is part of.
3102 def __init__(
3103 self,
3104 graph: Graph,
3105 name: Nullable[str] = None,
3106 # vertices: Nullable[Iterable[Vertex]] = None,
3107 keyValuePairs: Nullable[Mapping[Hashable, Any]] = None
3108 ) -> None:
3109 """
3110 Initialize a subgraph and register it at its graph.
3112 :param graph: The reference to the graph.
3113 :param name: Optional, name of the new sub-graph.
3114 :param keyValuePairs: Optional, mapping (dictionary) of key-value-pairs.
3115 :raises ValueError: If parameter 'graph' is None.
3116 :raises TypeError: If parameter 'graph' is not of type :class:`Graph`.
3117 """
3118 if graph is None: 3118 ↛ 3119line 3118 didn't jump to line 3119 because the condition on line 3118 was never true
3119 raise ValueError("Parameter 'graph' is None.")
3120 elif not isinstance(graph, Graph): 3120 ↛ 3121line 3120 didn't jump to line 3121 because the condition on line 3120 was never true
3121 ex = TypeError("Parameter 'graph' is not of type 'Graph'.")
3122 ex.add_note(f"Got type '{getFullyQualifiedName(graph)}'.")
3123 raise ex
3125 super().__init__(name, keyValuePairs)
3127 graph._subgraphs.add(self)
3129 self._graph = graph
3131 def __del__(self) -> None:
3132 """
3133 .. todo:: GRAPH::Subgraph::del Needs documentation.
3134 """
3135 super().__del__()
3137 @readonly
3138 def Graph(self) -> Graph:
3139 """
3140 Read-only property to access the graph, this subgraph is associated to (:attr:`_graph`).
3142 :returns: The graph this subgraph is associated to.
3143 """
3144 return self._graph
3146 def __str__(self) -> str:
3147 """
3148 Return a string representation of this subgraph.
3150 :returns: The subgraph's name, or ``"Unnamed subgraph"`` if it has none.
3151 """
3152 return self._name if self._name is not None else "Unnamed subgraph"
3155@export
3156class View(
3157 BaseWithVertices[
3158 VertexIDType, VertexWeightType, VertexValueType,
3159 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeKindType,
3160 LinkIDType, LinkWeightType, LinkValueType, LinkKindType
3161 ],
3162 Generic[
3163 VertexIDType, VertexWeightType, VertexValueType,
3164 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeKindType,
3165 LinkIDType, LinkWeightType, LinkValueType, LinkKindType
3166 ]
3167):
3168 """
3169 .. todo:: GRAPH::View Needs documentation.
3170 """
3172 def __init__(
3173 self,
3174 graph: Graph,
3175 name: Nullable[str] = None,
3176 vertices: Nullable[Iterable[Vertex]] = None,
3177 keyValuePairs: Nullable[Mapping[Hashable, Any]] = None
3178 ) -> None:
3179 """
3180 .. todo:: GRAPH::View::init Needs documentation.
3182 :param graph: The reference to the graph.
3183 :param name: Optional, name of the new view.
3184 :param vertices: Optional, list of vertices in the new view.
3185 :param keyValuePairs: Optional, mapping (dictionary) of key-value-pairs.
3186 """
3187 super().__init__(graph, name, vertices, keyValuePairs)
3189 graph._views.add(self)
3191 def __del__(self) -> None:
3192 """
3193 .. todo:: GRAPH::View::del Needs documentation.
3194 """
3195 super().__del__()
3197 def __str__(self) -> str:
3198 """
3199 Return a string representation of this view.
3201 :returns: The view's name, or ``"Unnamed view"`` if it has none.
3202 """
3203 return self._name if self._name is not None else "Unnamed view"
3206@export
3207class Component(
3208 BaseWithVertices[
3209 VertexIDType, VertexWeightType, VertexValueType,
3210 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeKindType,
3211 LinkIDType, LinkWeightType, LinkValueType, LinkKindType
3212 ],
3213 Generic[
3214 VertexIDType, VertexWeightType, VertexValueType,
3215 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeKindType,
3216 LinkIDType, LinkWeightType, LinkValueType, LinkKindType
3217 ]
3218):
3219 """
3220 .. todo:: GRAPH::Component Needs documentation.
3221 """
3223 def __init__(
3224 self,
3225 graph: Graph,
3226 name: Nullable[str] = None,
3227 vertices: Nullable[Iterable[Vertex]] = None,
3228 keyValuePairs: Nullable[Mapping[Hashable, Any]] = None
3229 ) -> None:
3230 """
3231 Initialize a component of a graph and register it at that graph.
3233 :param graph: The reference to the graph.
3234 :param name: Optional, name of the new component.
3235 :param vertices: Optional, list of vertices in the new component.
3236 :param keyValuePairs: Optional, mapping (dictionary) of key-value-pairs.
3237 """
3238 super().__init__(graph, name, vertices, keyValuePairs)
3240 graph._components.add(self)
3242 def __del__(self) -> None:
3243 """
3244 .. todo:: GRAPH::Component::del Needs documentation.
3245 """
3246 super().__del__()
3248 def __str__(self) -> str:
3249 """
3250 Return a string representation of this component.
3252 :returns: The component's name, or ``"Unnamed component"`` if it has none.
3253 """
3254 return self._name if self._name is not None else "Unnamed component"
3257@export
3258class Graph(
3259 BaseGraph[
3260 VertexIDType, VertexWeightType, VertexValueType,
3261 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeKindType,
3262 LinkIDType, LinkWeightType, LinkValueType, LinkKindType
3263 ],
3264 Generic[
3267 VertexIDType, VertexWeightType, VertexValueType,
3268 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeKindType,
3269 LinkIDType, LinkWeightType, LinkValueType, LinkKindType
3270 ]
3271):
3272 """
3273 A **graph** data structure is represented by an instance of :class:`~pyTooling.Graph.Graph` holding references to
3274 all nodes. Nodes are instances of :class:`~pyTooling.Graph.Vertex` classes and directed links between nodes are
3275 made of :class:`~pyTooling.Graph.Edge` instances. A graph can have attached meta information as key-value-pairs.
3276 """
3277 _subgraphs: set[Subgraph[VertexIDType, VertexWeightType, VertexValueType, EdgeIDType, EdgeWeightType, EdgeValueType, EdgeKindType, LinkIDType, LinkWeightType, LinkValueType, LinkKindType]] #: Subgraphs of this graph.
3278 _views: set[View[VertexIDType, VertexWeightType, VertexValueType, EdgeIDType, EdgeWeightType, EdgeValueType, EdgeKindType, LinkIDType, LinkWeightType, LinkValueType, LinkKindType]] #: Views defined on this graph.
3279 _components: set[Component[VertexIDType, VertexWeightType, VertexValueType, EdgeIDType, EdgeWeightType, EdgeValueType, EdgeKindType, LinkIDType, LinkWeightType, LinkValueType, LinkKindType]] #: Connected components of this graph.
3281 def __init__(
3282 self,
3283 name: Nullable[str] = None,
3284 keyValuePairs: Nullable[Mapping[Hashable, Any]] = None
3285 ) -> None:
3286 """
3287 .. todo:: GRAPH::Graph::init Needs documentation.
3289 :param name: Optional, name of the new graph.
3290 :param keyValuePairs: Optional, mapping (dictionary) of key-value-pairs.#
3291 """
3292 super().__init__(name, keyValuePairs)
3294 self._subgraphs = set()
3295 self._views = set()
3296 self._components = set()
3298 def __del__(self) -> None:
3299 """
3300 .. todo:: GRAPH::Graph::del Needs documentation.
3301 """
3302 try:
3303 del self._subgraphs
3304 del self._views
3305 del self._components
3306 except AttributeError:
3307 pass
3309 super().__del__()
3311 @readonly
3312 def Subgraphs(self) -> set[Subgraph]:
3313 """Read-only property to access the subgraphs in this graph (:attr:`_subgraphs`).
3315 :returns: The set of subgraphs in this graph."""
3316 return self._subgraphs
3318 @readonly
3319 def Views(self) -> set[View]:
3320 """Read-only property to access the views in this graph (:attr:`_views`).
3322 :returns: The set of views in this graph."""
3323 return self._views
3325 @readonly
3326 def Components(self) -> set[Component]:
3327 """Read-only property to access the components in this graph (:attr:`_components`).
3329 :returns: The set of components in this graph."""
3330 return self._components
3332 @readonly
3333 def SubgraphCount(self) -> int:
3334 """Read-only property to return the number of subgraphs in this graph.
3336 :returns: The number of subgraphs in this graph."""
3337 return len(self._subgraphs)
3339 @readonly
3340 def ViewCount(self) -> int:
3341 """Read-only property to return the number of views in this graph.
3343 :returns: The number of views in this graph."""
3344 return len(self._views)
3346 @readonly
3347 def ComponentCount(self) -> int:
3348 """Read-only property to return the number of components in this graph.
3350 :returns: The number of components in this graph."""
3351 return len(self._components)
3353 def Delete(self) -> None:
3354 """
3355 Delete all subgraphs, views, components, vertices, edges and links of this graph.
3357 Afterwards, the graph is empty: no vertex has an edge or a link, no subgraph, view or component lists a vertex,
3358 and every element's attached attributes are removed, the graph's own too. The graph can be filled again.
3360 .. seealso::
3362 :ref:`Deleting a graph <STRUCT/Graph/Delete>`
3363 |rarr| Reference cycles in a graph and Python's garbage collector.
3364 :meth:`Vertex.Delete <pyTooling.Graph.Vertex.Delete>`
3365 |rarr| Delete a single vertex with its edges and links.
3366 """
3367 for subgraph in self._subgraphs:
3368 subgraph._DeleteElements()
3369 subgraph._dict.clear()
3371 for view in self._views:
3372 view._vertices = set()
3373 view._dict.clear()
3375 for component in self._components:
3376 component._vertices = set()
3377 component._dict.clear()
3379 self._DeleteElements()
3381 self._subgraphs = set()
3382 self._views = set()
3383 self._components = set()
3385 super().Delete()
3387 def ContainsVertexByID(self, vertexID: Nullable[VertexIDType]) -> bool:
3388 """
3389 Check if a vertex with the given ID exists in this graph.
3391 :param vertexID: ID to look for, or ``None`` for a vertex without an ID.
3392 :returns: ``True``, if such a vertex exists.
3393 """
3394 if vertexID is None:
3395 return len(self._verticesWithoutID) >= 1
3396 else:
3397 return vertexID in self._verticesWithID
3399 def ContainsVertexByValue(self, value: Nullable[VertexValueType]) -> bool:
3400 """
3401 Check if a vertex carrying the given value exists in this graph.
3403 :param value: Value to look for.
3404 :returns: ``True``, if such a vertex exists.
3405 """
3406 return any(vertex._value == value for vertex in chain(self._verticesWithoutID, self._verticesWithID.values()))
3408 def GetVertexByID(self, vertexID: Nullable[VertexIDType]) -> Vertex:
3409 """
3410 Return the vertex with the given ID.
3412 A vertex created without an ID can be looked up with ``None``, provided it is the only such vertex.
3414 :param vertexID: ID of the vertex to return, or ``None`` for the vertex without an ID.
3415 :returns: The vertex with that ID.
3416 :raises KeyError: If no vertex has that ID, or if more than one vertex matches ``None``.
3417 """
3418 if vertexID is None:
3419 if (l := len(self._verticesWithoutID)) == 1:
3420 return self._verticesWithoutID[0]
3421 elif l == 0:
3422 raise KeyError("Found no vertex with ID `None`.")
3423 else:
3424 raise KeyError("Found multiple vertices with ID `None`.")
3425 else:
3426 return self._verticesWithID[vertexID]
3428 def GetVertexByValue(self, value: Nullable[VertexValueType]) -> Vertex:
3429 """
3430 Return the vertex carrying the given value.
3432 :param value: Value of the vertex to return.
3433 :returns: The vertex with that value.
3434 :raises KeyError: If no vertex carries that value, or if more than one vertex does.
3435 """
3436 # FIXME: optimize: iterate only until first item is found and check for a second to produce error
3437 vertices = [
3438 vertex for vertex in (*self._verticesWithoutID, *self._verticesWithID.values()) if vertex._value == value
3439 ]
3440 if (l := len(vertices)) == 1:
3441 return vertices[0]
3442 elif l == 0:
3443 raise KeyError(f"Found no vertex with Value == `{value}`.")
3444 else:
3445 raise KeyError(f"Found multiple vertices with Value == `{value}`.")
3447 def CopyGraph(self) -> Graph:
3448 """
3449 Create a copy of this graph.
3451 :returns: A new graph with copies of this graph's vertices and edges.
3452 :raises NotImplementedError: Copying a whole graph is not implemented yet.
3453 """
3454 raise NotImplementedError()
3456 def CopyVertices(self, predicate: Nullable[Predicate[Vertex]] = None, copyGraphDict: bool = True, copyVertexDict: bool = True) -> Graph:
3457 """
3458 Create a new graph and copy all or selected vertices of the original graph.
3460 If parameter ``predicate`` is not None, the given filter function is used to skip vertices.
3462 :param predicate: Optional, filter function accepting any vertex and returning a boolean.
3463 :param copyGraphDict: Optional, if ``True``, copy all graph attached attributes into the new graph.
3464 :param copyVertexDict: Optional, if ``True``, copy all vertex attached attributes into the new vertices.
3465 :returns: A new graph with copies of the selected vertices.
3466 """
3467 graph = Graph(self._name)
3468 if copyGraphDict:
3469 graph._dict = self._dict.copy()
3471 if predicate is None:
3472 for vertex in self._verticesWithoutID:
3473 v = Vertex(None, vertex._value, graph=graph)
3474 if copyVertexDict:
3475 v._dict = vertex._dict.copy()
3477 for vertexID, vertex in self._verticesWithID.items():
3478 v = Vertex(vertexID, vertex._value, graph=graph)
3479 if copyVertexDict:
3480 v._dict = vertex._dict.copy()
3481 else:
3482 for vertex in self._verticesWithoutID:
3483 if predicate(vertex):
3484 v = Vertex(None, vertex._value, graph=graph)
3485 if copyVertexDict: 3485 ↛ 3482line 3485 didn't jump to line 3482 because the condition on line 3485 was always true
3486 v._dict = vertex._dict.copy()
3488 for vertexID, vertex in self._verticesWithID.items():
3489 if predicate(vertex):
3490 v = Vertex(vertexID, vertex._value, graph=graph)
3491 if copyVertexDict: 3491 ↛ 3492line 3491 didn't jump to line 3492 because the condition on line 3491 was never true
3492 v._dict = vertex._dict.copy()
3494 return graph
3496 # class Iterator():
3497 # visited = [False for _ in range(self.__len__())]
3499 # def CheckForNegativeCycles(self):
3500 # raise NotImplementedError()
3501 # # Bellman-Ford
3502 # # Floyd-Warshall
3503 #
3504 # def IsStronglyConnected(self):
3505 # raise NotImplementedError()
3506 #
3507 # def GetStronglyConnectedComponents(self):
3508 # raise NotImplementedError()
3509 # # Tarjan's and Kosaraju's algorithm
3510 #
3511 # def TravelingSalesmanProblem(self):
3512 # raise NotImplementedError()
3513 # # Held-Karp
3514 # # branch and bound
3515 #
3516 # def GetBridges(self):
3517 # raise NotImplementedError()
3518 #
3519 # def GetArticulationPoints(self):
3520 # raise NotImplementedError()
3521 #
3522 # def MinimumSpanningTree(self):
3523 # raise NotImplementedError()
3524 # # Kruskal
3525 # # Prim's algorithm
3526 # # Buruvka's algorithm
3528 def __repr__(self) -> str:
3529 """
3530 Return a detailed string representation of this graph.
3532 :returns: The graph's name and its vertex and edge counts.
3533 """
3534 statistics = f", vertices: {self.VertexCount}, edges: {self.EdgeCount}"
3535 if self._name is None:
3536 return f"<graph: unnamed graph{statistics}>"
3537 else:
3538 return f"<graph: '{self._name}'{statistics}>"
3540 def __str__(self) -> str:
3541 """
3542 Return a string representation of this graph.
3544 :returns: The graph's name, or ``"Unnamed graph"`` if it has none.
3545 """
3546 if self._name is None:
3547 return "Graph: unnamed graph"
3548 else:
3549 return f"Graph: '{self._name}'"
3552# A class with a property named like a class - ``Graph``, ``Component`` - can't name that class in the annotation of a
3553# field: the class body's namespace, where annotations are evaluated, binds the name to the property.
3554_Graph = Graph
3555_Component = Component