Coverage for pyTooling/Graph/__init__.py: 79%
1253 statements
« prev ^ index » next coverage.py v7.15.4, created at 2026-08-22 21:29 +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 itertools import chain
69from typing import Any, TypeVar, Generic, Deque, Union, Optional as Nullable
70from typing import Callable, Iterator as typing_Iterator, Generator, Iterable, Mapping, Hashable
72from pyTooling.Decorators import export, readonly
73from pyTooling.MetaClasses import ExtendedType
74from pyTooling.Exceptions import ToolingException
75from pyTooling.Common import getFullyQualifiedName
76from pyTooling.Tree import Node
79DictKeyType = TypeVar("DictKeyType", bound=Hashable)
80"""A type variable for dictionary keys."""
82DictValueType = TypeVar("DictValueType")
83"""A type variable for dictionary values."""
85IDType = TypeVar("IDType", bound=Hashable)
86"""A type variable for an ID."""
88WeightType = TypeVar("WeightType", bound=Union[int, float])
89"""A type variable for a weight."""
91ValueType = TypeVar("ValueType")
92"""A type variable for a value."""
94VertexIDType = TypeVar("VertexIDType", bound=Hashable)
95"""A type variable for a vertex's ID."""
97VertexWeightType = TypeVar("VertexWeightType", bound=Union[int, float])
98"""A type variable for a vertex's weight."""
100VertexValueType = TypeVar("VertexValueType")
101"""A type variable for a vertex's value."""
103VertexDictKeyType = TypeVar("VertexDictKeyType", bound=Hashable)
104"""A type variable for a vertex's dictionary keys."""
106VertexDictValueType = TypeVar("VertexDictValueType")
107"""A type variable for a vertex's dictionary values."""
109EdgeIDType = TypeVar("EdgeIDType", bound=Hashable)
110"""A type variable for an edge's ID."""
112EdgeWeightType = TypeVar("EdgeWeightType", bound=Union[int, float])
113"""A type variable for an edge's weight."""
115EdgeValueType = TypeVar("EdgeValueType")
116"""A type variable for an edge's value."""
118EdgeDictKeyType = TypeVar("EdgeDictKeyType", bound=Hashable)
119"""A type variable for an edge's dictionary keys."""
121EdgeDictValueType = TypeVar("EdgeDictValueType")
122"""A type variable for an edge's dictionary values."""
124LinkIDType = TypeVar("LinkIDType", bound=Hashable)
125"""A type variable for an link's ID."""
127LinkWeightType = TypeVar("LinkWeightType", bound=Union[int, float])
128"""A type variable for an link's weight."""
130LinkValueType = TypeVar("LinkValueType")
131"""A type variable for an link's value."""
133LinkDictKeyType = TypeVar("LinkDictKeyType", bound=Hashable)
134"""A type variable for an link's dictionary keys."""
136LinkDictValueType = TypeVar("LinkDictValueType")
137"""A type variable for an link's dictionary values."""
139ComponentDictKeyType = TypeVar("ComponentDictKeyType", bound=Hashable)
140"""A type variable for a component's dictionary keys."""
142ComponentDictValueType = TypeVar("ComponentDictValueType")
143"""A type variable for a component's dictionary values."""
145SubgraphDictKeyType = TypeVar("SubgraphDictKeyType", bound=Hashable)
146"""A type variable for a component's dictionary keys."""
148SubgraphDictValueType = TypeVar("SubgraphDictValueType")
149"""A type variable for a component's dictionary values."""
151ViewDictKeyType = TypeVar("ViewDictKeyType", bound=Hashable)
152"""A type variable for a component's dictionary keys."""
154ViewDictValueType = TypeVar("ViewDictValueType")
155"""A type variable for a component's dictionary values."""
157GraphDictKeyType = TypeVar("GraphDictKeyType", bound=Hashable)
158"""A type variable for a graph's dictionary keys."""
160GraphDictValueType = TypeVar("GraphDictValueType")
161"""A type variable for a graph's dictionary values."""
164@export
165class GraphException(ToolingException):
166 """Base exception of all exceptions raised by :mod:`pyTooling.Graph`."""
169@export
170class InternalError(GraphException):
171 """
172 The exception is raised when a data structure corruption is detected.
174 .. danger::
176 This exception should never be raised.
178 If so, please create an issue at GitHub so the data structure corruption can be investigated and fixed. |br|
179 `⇒ Bug Tracker at GitHub <https://github.com/pyTooling/pyTooling/issues>`__
180 """
183@export
184class NotInSameGraph(GraphException):
185 """The exception is raised when creating an edge between two vertices, but these are not in the same graph."""
188@export
189class NotInDifferentSubgraphs(GraphException):
190 """
191 The exception is raised when creating a link between two vertices, but these are in the same subgraph.
193 A link crosses subgraph boundaries. Two vertices within one subgraph are connected by an edge.
194 """
197@export
198class DuplicateVertexError(GraphException):
199 """The exception is raised when the vertex already exists in the graph."""
201 _vertexID: Nullable[VertexIDType] #: ID of the vertex that already exists in the graph.
203 def __init__(self, message: str, /, *, vertexID: Nullable[VertexIDType] = None) -> None:
204 """
205 Initializes the exception with the identifier that is already taken.
207 :param message: The exception's message.
208 :param vertexID: Optional, the vertex identifier that already exists.
209 """
210 super().__init__(message)
211 self._vertexID = vertexID
213 @readonly
214 def VertexID(self) -> Nullable[VertexIDType]:
215 """
216 Read-only property to access the identifier that already exists (:attr:`_vertexID`).
218 :returns: The duplicate vertex identifier, or ``None`` if it wasn't recorded.
219 """
220 return self._vertexID
223@export
224class DuplicateEdgeError(GraphException):
225 """The exception is raised when the edge already exists in the graph."""
227 _edgeID: Nullable[EdgeIDType] #: ID of the edge that already exists in the graph.
229 def __init__(self, message: str, /, *, edgeID: Nullable[EdgeIDType] = None) -> None:
230 """
231 Initializes the exception with the identifier that is already taken.
233 :param message: The exception's message.
234 :param edgeID: Optional, the edge identifier that already exists.
235 """
236 super().__init__(message)
237 self._edgeID = edgeID
239 @readonly
240 def EdgeID(self) -> Nullable[EdgeIDType]:
241 """
242 Read-only property to access the identifier that already exists (:attr:`_edgeID`).
244 :returns: The duplicate edge identifier, or ``None`` if it wasn't recorded.
245 """
246 return self._edgeID
249@export
250class DestinationNotReachable(GraphException):
251 """The exception is raised when a destination vertex is not reachable."""
254@export
255class NotATreeError(GraphException):
256 """
257 The exception is raised when a subgraph is not a tree.
259 Either the subgraph has a cycle (backward edge) or links between branches (cross-edge).
260 """
263@export
264class CycleError(GraphException):
265 """The exception is raised when a not permitted cycle is found."""
268@export
269class Base(
270 Generic[DictKeyType, DictValueType],
271 metaclass=ExtendedType, slots=True
272):
273 """
274 Base-class for all graph elements, adding a dictionary of arbitrary key-value-pairs to them.
276 Every vertex, edge, link, component, view, subgraph and graph can carry meta information this way.
277 """
279 _dict: dict[DictKeyType, DictValueType] #: A dictionary to store arbitrary key-value-pairs.
281 def __init__(
282 self,
283 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None
284 ) -> None:
285 """
286 .. todo:: GRAPH::Base::init Needs documentation.
288 :param keyValuePairs: Optional, mapping (dictionary) of key-value-pairs.
289 :raises TypeError: If parameter 'name' is not of type string.
290 """
291 self._dict = {key: value for key, value in keyValuePairs.items()} if keyValuePairs is not None else {}
293 def __del__(self) -> None:
294 """
295 .. todo:: GRAPH::Base::del Needs documentation.
297 """
298 try:
299 del self._dict
300 except AttributeError:
301 pass
303 def Delete(self) -> None:
304 """
305 Remove this element's attached attributes from internal dictionary.
306 """
307 self._dict.clear()
309 def __getitem__(self, key: DictKeyType) -> DictValueType:
310 """
311 Read a vertex's attached attributes (key-value-pairs) by key.
313 :param key: The key to look for.
314 :returns: The value associated to the given key.
315 """
316 return self._dict[key]
318 def __setitem__(self, key: DictKeyType, value: DictValueType) -> None:
319 """
320 Create or update a vertex's attached attributes (key-value-pairs) by key.
322 If a key doesn't exist yet, a new key-value-pair is created.
324 :param key: The key to create or update.
325 :param value: Optional, the value to associate to the given key.
326 """
327 self._dict[key] = value
329 def __delitem__(self, key: DictKeyType) -> None:
330 """
331 Remove an entry from vertex's attached attributes (key-value-pairs) by key.
333 :param key: The key to remove.
334 :raises KeyError: If key doesn't exist in the vertex's attributes.
335 """
336 del self._dict[key]
338 def __contains__(self, key: DictKeyType) -> bool:
339 """
340 Checks if the key is an attached attribute (key-value-pairs) on this vertex.
342 :param key: The key to check.
343 :returns: ``True``, if the key is an attached attribute.
344 """
345 return key in self._dict
347 def __len__(self) -> int:
348 """
349 Returns the number of attached attributes (key-value-pairs) on this vertex.
351 :returns: Number of attached attributes.
352 """
353 return len(self._dict)
356@export
357class BaseWithIDValueAndWeight(
358 Base[DictKeyType, DictValueType],
359 Generic[IDType, ValueType, WeightType, DictKeyType, DictValueType]
360):
361 """
362 Base-class for graph elements identified by an ID and carrying a value and a weight - vertices, edges and links.
364 All three are optional: an element without an ID is still part of the graph, it just can't be looked up by ID.
365 """
367 _id: Nullable[IDType] #: Field storing the object's Identifier.
368 _value: Nullable[ValueType] #: Field storing the object's value of any type.
369 _weight: Nullable[WeightType] #: Field storing the object's weight.
371 def __init__(
372 self,
373 identifier: Nullable[IDType] = None,
374 value: Nullable[ValueType] = None,
375 weight: Nullable[WeightType] = None,
376 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None
377 ) -> None:
378 """
379 Initialize a graph element with an optional ID, value and weight.
381 :param identifier: Optional, unique ID.
382 :param value: Optional, value.
383 :param weight: Optional, weight.
384 :param keyValuePairs: Optional, mapping (dictionary) of key-value-pairs.
385 :raises TypeError: If parameter 'name' is not of type string.
386 """
387 super().__init__(keyValuePairs)
389 self._id = identifier
390 self._value = value
391 self._weight = weight
393 @readonly
394 def ID(self) -> Nullable[IDType]:
395 """
396 Read-only property to access the unique ID (:attr:`_id`).
398 If no ID was given at creation time, ID returns ``None``.
400 :returns: Unique ID, if ID was given at creation time, else ``None``.
401 """
402 return self._id
404 @property
405 def Value(self) -> ValueType:
406 """
407 Property to get and set the value (:attr:`_value`).
409 :returns: The value.
410 """
411 return self._value
413 @Value.setter
414 def Value(self, value: ValueType) -> None:
415 self._value = value
417 @property
418 def Weight(self) -> Nullable[EdgeWeightType]:
419 """
420 Property to get and set the weight (:attr:`_weight`) of an edge.
422 :returns: The weight of an edge.
423 """
424 return self._weight
426 @Weight.setter
427 def Weight(self, value: Nullable[EdgeWeightType]) -> None:
428 self._weight = value
431@export
432class BaseWithName(
433 Base[DictKeyType, DictValueType],
434 Generic[DictKeyType, DictValueType]
435):
436 """Base-class for named graph elements like a graph, a subgraph, a view or a component."""
438 _name: Nullable[str] #: Field storing the object's name.
440 def __init__(
441 self,
442 name: Nullable[str] = None,
443 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None,
444 ) -> None:
445 """
446 Initialize a named graph element with an optional name and optional key-value-pairs.
448 :param name: Optional, name.
449 :param keyValuePairs: Optional, mapping (dictionary) of key-value-pairs.
450 :raises ValueError: If parameter 'graph' is None.
451 :raises TypeError: If parameter 'graph' is not of type :class:`Graph`.
452 """
453 if name is not None and not isinstance(name, str):
454 ex = TypeError("Parameter 'name' is not of type 'str'.")
455 ex.add_note(f"Got type '{getFullyQualifiedName(name)}'.")
456 raise ex
458 super().__init__(keyValuePairs)
460 self._name = name
462 @property
463 def Name(self) -> Nullable[str]:
464 """
465 Property to access the name (:attr:`_name`).
467 :returns: The object's name, or ``None`` if it has none.
468 :raises TypeError: If an assigned value is not of type string.
469 """
470 return self._name
472 @Name.setter
473 def Name(self, value: str) -> None:
474 if not isinstance(value, str):
475 ex = TypeError("Name is not of type 'str'.")
476 ex.add_note(f"Got type '{getFullyQualifiedName(value)}'.")
477 raise ex
479 self._name = value
482@export
483class BaseWithVertices(
484 BaseWithName[DictKeyType, DictValueType],
485 Generic[
486 DictKeyType, DictValueType,
487 GraphDictKeyType, GraphDictValueType,
488 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,
489 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,
490 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType
491 ]
492):
493 """Base-class for named graph elements owning a set of vertices - a subgraph, a view or a component."""
495 _graph: Graph[
496 GraphDictKeyType, GraphDictValueType,
497 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,
498 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,
499 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType
500 ] #: Field storing a reference to the graph.
501 _vertices: set[Vertex[
502 GraphDictKeyType, GraphDictValueType,
503 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,
504 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,
505 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType
506 ]] #: Field storing a set of vertices.
508 def __init__(
509 self,
510 graph: Graph,
511 name: Nullable[str] = None,
512 vertices: Nullable[Iterable[Vertex]] = None,
513 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None
514 ) -> None:
515 """
516 Initialize a named graph element owning a set of vertices, and register it at its graph.
518 :param graph: Optional, the reference to the graph.
519 :param name: Optional, name.
520 :param vertices: Optional, list of vertices.
521 :param keyValuePairs: Optional, mapping (dictionary) of key-value-pairs.
522 :raises ValueError: If parameter 'graph' is None.
523 :raises TypeError: If parameter 'graph' is not of type :class:`Graph`.
524 """
525 if graph is None: 525 ↛ 526line 525 didn't jump to line 526 because the condition on line 525 was never true
526 raise ValueError("Parameter 'graph' is None.")
527 elif not isinstance(graph, Graph): 527 ↛ 528line 527 didn't jump to line 528 because the condition on line 527 was never true
528 ex = TypeError("Parameter 'graph' is not of type 'Graph'.")
529 ex.add_note(f"Got type '{getFullyQualifiedName(graph)}'.")
530 raise ex
532 super().__init__(name, keyValuePairs)
534 self._graph = graph
535 self._vertices = set() if vertices is None else {v for v in vertices}
537 def __del__(self) -> None:
538 """
539 .. todo:: GRAPH::BaseWithVertices::del Needs documentation.
541 """
542 try:
543 del self._vertices
544 except AttributeError:
545 pass
547 super().__del__()
549 @readonly
550 def Graph(self) -> Graph:
551 """
552 Read-only property to access the graph, this object is associated to (:attr:`_graph`).
554 :returns: The graph this object is associated to.
555 """
556 return self._graph
558 @readonly
559 def Vertices(self) -> set[Vertex]:
560 """
561 Read-only property to access the vertices in this component (:attr:`_vertices`).
563 :returns: The set of vertices in this component.
564 """
565 return self._vertices
567 @readonly
568 def VertexCount(self) -> int:
569 """
570 Read-only property to return the number of vertices referenced by this object.
572 :returns: The number of vertices this object references.
573 """
574 return len(self._vertices)
577@export
578class Vertex(
579 BaseWithIDValueAndWeight[VertexIDType, VertexValueType, VertexWeightType, VertexDictKeyType, VertexDictValueType],
580 Generic[
581 GraphDictKeyType, GraphDictValueType,
582 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,
583 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,
584 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType
585 ]
586):
587 """
588 A **vertex** can have a unique ID, a value and attached meta information as key-value-pairs. A vertex has references
589 to inbound and outbound edges, thus a graph can be traversed in reverse.
590 """
591 _graph: BaseGraph[GraphDictKeyType, GraphDictValueType, VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType, EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType] #: Field storing a reference to the graph.
592 _subgraph: Subgraph[GraphDictKeyType, GraphDictValueType, VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType, EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType] #: Field storing a reference to the subgraph.
593 _component: Component #: Field storing a reference to the component this vertex belongs to.
594 _views: dict[Hashable, View] #: Field storing the views this vertex is part of, by view name.
595 _inboundEdges: list[Edge[EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType]] #: Field storing a list of inbound edges.
596 _outboundEdges: list[Edge[EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType]] #: Field storing a list of outbound edges.
597 _inboundLinks: list[Link[EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType]] #: Field storing a list of inbound links.
598 _outboundLinks: list[Link[EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType]] #: Field storing a list of outbound links.
600 def __init__(
601 self,
602 vertexID: Nullable[VertexIDType] = None,
603 value: Nullable[VertexValueType] = None,
604 weight: Nullable[VertexWeightType] = None,
605 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None,
606 graph: Nullable[Graph] = None,
607 subgraph: Nullable[Subgraph] = None
608 ) -> None:
609 """
610 Initialize a vertex and register it at its graph or subgraph.
612 :param vertexID: Optional, ID for the new vertex.
613 :param value: Optional, value for the new vertex.
614 :param weight: Optional, weight for the new vertex.
615 :param keyValuePairs: Optional, mapping (dictionary) of key-value-pairs.
616 :param graph: Optional, reference to the graph.
617 :param subgraph: Optional, undocumented
618 :raises TypeError: If parameter 'vertexID' is not of the graph's vertex ID type.
619 :raises DuplicateVertexError: If the given vertex ID already exists in this graph or subgraph.
620 """
621 if vertexID is not None and not isinstance(vertexID, Hashable): 621 ↛ 622line 621 didn't jump to line 622 because the condition on line 621 was never true
622 ex = TypeError("Parameter 'vertexID' is not of type 'VertexIDType'.")
623 ex.add_note(f"Got type '{getFullyQualifiedName(vertexID)}'.")
624 raise ex
626 super().__init__(vertexID, value, weight, keyValuePairs)
628 if subgraph is None:
629 self._graph = graph if graph is not None else Graph()
630 self._subgraph = None
631 self._component = Component(self._graph, vertices=(self,))
633 if vertexID is None:
634 self._graph._verticesWithoutID.append(self)
635 elif vertexID not in self._graph._verticesWithID:
636 self._graph._verticesWithID[vertexID] = self
637 else:
638 raise DuplicateVertexError(f"Vertex ID '{vertexID}' already exists in this graph.", vertexID=vertexID)
639 else:
640 self._graph = subgraph._graph
641 self._subgraph = subgraph
642 self._component = Component(self._graph, vertices=(self,))
644 if vertexID is None:
645 subgraph._verticesWithoutID.append(self)
646 elif vertexID not in subgraph._verticesWithID: 646 ↛ 649line 646 didn't jump to line 649 because the condition on line 646 was always true
647 subgraph._verticesWithID[vertexID] = self
648 else:
649 raise DuplicateVertexError(f"Vertex ID '{vertexID}' already exists in this subgraph.", vertexID=vertexID)
651 self._views = {}
652 self._inboundEdges = []
653 self._outboundEdges = []
654 self._inboundLinks = []
655 self._outboundLinks = []
657 def __del__(self) -> None:
658 """
659 .. todo:: GRAPH::BaseEdge::del Needs documentation.
661 """
662 try:
663 del self._views
664 del self._inboundEdges
665 del self._outboundEdges
666 del self._inboundLinks
667 del self._outboundLinks
668 except AttributeError:
669 pass
671 super().__del__()
673 def Delete(self) -> None:
674 """
675 Delete this vertex and every edge and link connected to it.
677 The vertex is removed from its graph or subgraph, and from its views; every connected edge and link is removed
678 from its other vertex and unregistered from the graph or subgraph it was registered on.
679 """
680 for edge in self._outboundEdges:
681 edge._destination._inboundEdges.remove(edge)
682 edge._Unregister()
683 edge._Delete()
684 for edge in self._inboundEdges:
685 edge._source._outboundEdges.remove(edge)
686 edge._Unregister()
687 edge._Delete()
688 for link in self._outboundLinks:
689 link._destination._inboundLinks.remove(link)
690 link._Unregister()
691 link._Delete()
692 for link in self._inboundLinks: 692 ↛ 693line 692 didn't jump to line 693 because the loop on line 692 never started
693 link._source._outboundLinks.remove(link)
694 link._Unregister()
695 link._Delete()
697 # Remove from Graph or Subgraph - a vertex is registered on the subgraph it lives in, otherwise on the graph.
698 container = self._graph if self._subgraph is None else self._subgraph
699 if self._id is None:
700 container._verticesWithoutID.remove(self)
701 else:
702 del container._verticesWithID[self._id]
704 # component
706 # views
707 self._views.clear()
708 self._inboundEdges.clear()
709 self._outboundEdges.clear()
710 self._inboundLinks.clear()
711 self._outboundLinks.clear()
713 super().Delete()
715 @readonly
716 def Graph(self) -> Graph:
717 """
718 Read-only property to access the graph, this vertex is associated to (:attr:`_graph`).
720 :returns: The graph this vertex is associated to.
721 """
722 return self._graph
724 @readonly
725 def Component(self) -> Component:
726 """
727 Read-only property to access the component, this vertex is associated to (:attr:`_component`).
729 :returns: The component this vertex is associated to.
730 """
731 return self._component
733 @readonly
734 def InboundEdges(self) -> tuple[Edge, ...]:
735 """
736 Read-only property to get a tuple of inbound edges (:attr:`_inboundEdges`).
738 :returns: Tuple of inbound edges.
739 """
740 return tuple(self._inboundEdges)
742 @readonly
743 def OutboundEdges(self) -> tuple[Edge, ...]:
744 """
745 Read-only property to get a tuple of outbound edges (:attr:`_outboundEdges`).
747 :returns: Tuple of outbound edges.
748 """
749 return tuple(self._outboundEdges)
751 @readonly
752 def InboundLinks(self) -> tuple[Link, ...]:
753 """
754 Read-only property to get a tuple of inbound links (:attr:`_inboundLinks`).
756 :returns: Tuple of inbound links.
757 """
758 return tuple(self._inboundLinks)
760 @readonly
761 def OutboundLinks(self) -> tuple[Link, ...]:
762 """
763 Read-only property to get a tuple of outbound links (:attr:`_outboundLinks`).
765 :returns: Tuple of outbound links.
766 """
767 return tuple(self._outboundLinks)
769 @readonly
770 def EdgeCount(self) -> int:
771 """
772 Read-only property to get the number of all edges (inbound and outbound).
774 :returns: Number of inbound and outbound edges.
775 """
776 return len(self._inboundEdges) + len(self._outboundEdges)
778 @readonly
779 def InboundEdgeCount(self) -> int:
780 """
781 Read-only property to get the number of inbound edges.
783 :returns: Number of inbound edges.
784 """
785 return len(self._inboundEdges)
787 @readonly
788 def OutboundEdgeCount(self) -> int:
789 """
790 Read-only property to get the number of outbound edges.
792 :returns: Number of outbound edges.
793 """
794 return len(self._outboundEdges)
796 @readonly
797 def LinkCount(self) -> int:
798 """
799 Read-only property to get the number of all links (inbound and outbound).
801 :returns: Number of inbound and outbound links.
802 """
803 return len(self._inboundLinks) + len(self._outboundLinks)
805 @readonly
806 def InboundLinkCount(self) -> int:
807 """
808 Read-only property to get the number of inbound links.
810 :returns: Number of inbound links.
811 """
812 return len(self._inboundLinks)
814 @readonly
815 def OutboundLinkCount(self) -> int:
816 """
817 Read-only property to get the number of outbound links.
819 :returns: Number of outbound links.
820 """
821 return len(self._outboundLinks)
823 @readonly
824 def IsRoot(self) -> bool:
825 """
826 Read-only property to check if this vertex is a root vertex in the graph.
828 A root has no inbound edges (no predecessor vertices).
830 :returns: ``True``, if this vertex is a root.
832 .. seealso::
834 :meth:`Vertex.IsLeaf <pyTooling.Graph.Vertex.IsLeaf>`
835 |rarr| Check if a vertex is a leaf vertex in the graph.
836 :meth:`BaseGraph.IterateRoots <pyTooling.Graph.BaseGraph.IterateRoots>`
837 |rarr| Iterate all roots of a graph.
838 :meth:`BaseGraph.IterateLeafs <pyTooling.Graph.BaseGraph.IterateLeafs>`
839 |rarr| Iterate all leafs of a graph.
840 """
841 return len(self._inboundEdges) == 0
843 @readonly
844 def IsLeaf(self) -> bool:
845 """
846 Read-only property to check if this vertex is a leaf vertex in the graph.
848 A leaf has no outbound edges (no successor vertices).
850 :returns: ``True``, if this vertex is a leaf.
852 .. seealso::
854 :meth:`Vertex.IsRoot <pyTooling.Graph.Vertex.IsRoot>`
855 |rarr| Check if a vertex is a root vertex in the graph.
856 :meth:`BaseGraph.IterateRoots <pyTooling.Graph.BaseGraph.IterateRoots>`
857 |rarr| Iterate all roots of a graph.
858 :meth:`BaseGraph.IterateLeafs <pyTooling.Graph.BaseGraph.IterateLeafs>`
859 |rarr| Iterate all leafs of a graph.
860 """
861 return len(self._outboundEdges) == 0
863 @readonly
864 def Predecessors(self) -> tuple[Vertex, ...]:
865 """
866 Read-only property to get a tuple of predecessor vertices.
868 :returns: Tuple of predecessor vertices.
869 """
870 return tuple([edge.Source for edge in self._inboundEdges])
872 @readonly
873 def Successors(self) -> tuple[Vertex, ...]:
874 """
875 Read-only property to get a tuple of successor vertices.
877 :returns: Tuple of successor vertices.
878 """
879 return tuple([edge.Destination for edge in self._outboundEdges])
881 def EdgeToVertex(
882 self,
883 vertex: Vertex,
884 edgeID: Nullable[EdgeIDType] = None,
885 edgeWeight: Nullable[EdgeWeightType] = None,
886 edgeValue: Nullable[VertexValueType] = None,
887 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None
888 ) -> Edge:
889 """
890 Create an outbound edge from this vertex to the referenced vertex.
892 :param vertex: The vertex to be linked to.
893 :param edgeID: Optional, the edge's optional ID for the new edge object.
894 :param edgeWeight: Optional, the edge's optional weight for the new edge object.
895 :param edgeValue: Optional, the edge's optional value for the new edge object.
896 :param keyValuePairs: Optional, mapping (dictionary) of key-value-pairs for the new edge object.
897 :returns: The edge object linking this vertex and the referenced vertex.
898 :raises DuplicateEdgeError: If the given edge ID already exists in this graph or subgraph.
899 :raises NotInSameGraph: If both vertices are not in the same graph or subgraph. |br|
900 Use :meth:`LinkToVertex` or :meth:`LinkFromVertex` to connect vertices across
901 subgraph boundaries.
903 .. seealso::
905 :meth:`EdgeFromVertex`
906 |rarr| Create an inbound edge from the referenced vertex to this vertex.
907 :meth:`EdgeToNewVertex`
908 |rarr| Create a new vertex and link that vertex by an outbound edge from this vertex.
909 :meth:`EdgeFromNewVertex`
910 |rarr| Create a new vertex and link that vertex by an inbound edge to this vertex.
911 :meth:`LinkToVertex`
912 |rarr| Create an outbound link from this vertex to the referenced vertex.
913 :meth:`LinkFromVertex`
914 |rarr| Create an inbound link from the referenced vertex to this vertex.
916 """
917 if self._subgraph is vertex._subgraph:
918 edge = Edge(self, vertex, edgeID, edgeValue, edgeWeight, keyValuePairs)
920 self._outboundEdges.append(edge)
921 vertex._inboundEdges.append(edge)
923 if self._subgraph is None:
924 # TODO: move into Edge?
925 # TODO: keep _graph pointer in edge and then register edge on graph?
926 if edgeID is None:
927 self._graph._edgesWithoutID.append(edge)
928 elif edgeID not in self._graph._edgesWithID:
929 self._graph._edgesWithID[edgeID] = edge
930 else:
931 raise DuplicateEdgeError(f"Edge ID '{edgeID}' already exists in this graph.", edgeID=edgeID)
932 else:
933 # TODO: keep _graph pointer in edge and then register edge on graph?
934 if edgeID is None:
935 self._subgraph._edgesWithoutID.append(edge)
936 elif edgeID not in self._subgraph._edgesWithID:
937 self._subgraph._edgesWithID[edgeID] = edge
938 else:
939 raise DuplicateEdgeError(f"Edge ID '{edgeID}' already exists in this subgraph.", edgeID=edgeID)
940 else:
941 ex = NotInSameGraph(f"Vertex {self!r} and vertex {vertex!r} are not in the same graph or subgraph.")
942 ex.add_note(f"An edge can only connect vertices within the same graph or subgraph.")
943 ex.add_note(f"Use LinkToVertex or LinkFromVertex to connect vertices across subgraph boundaries.")
944 raise ex
946 return edge
948 def EdgeFromVertex(
949 self,
950 vertex: Vertex,
951 edgeID: Nullable[EdgeIDType] = None,
952 edgeWeight: Nullable[EdgeWeightType] = None,
953 edgeValue: Nullable[VertexValueType] = None,
954 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None
955 ) -> Edge:
956 """
957 Create an inbound edge from the referenced vertex to this vertex.
959 :param vertex: The vertex to be linked from.
960 :param edgeID: Optional, the edge's optional ID for the new edge object.
961 :param edgeWeight: Optional, the edge's optional weight for the new edge object.
962 :param edgeValue: Optional, the edge's optional value for the new edge object.
963 :param keyValuePairs: Optional, mapping (dictionary) of key-value-pairs for the new edge object.
964 :returns: The edge object linking the referenced vertex and this vertex.
965 :raises DuplicateEdgeError: If the given edge ID already exists in this graph or subgraph.
966 :raises NotInSameGraph: If both vertices are not in the same graph or subgraph. |br|
967 Use :meth:`LinkToVertex` or :meth:`LinkFromVertex` to connect vertices across
968 subgraph boundaries.
970 .. seealso::
972 :meth:`EdgeToVertex`
973 |rarr| Create an outbound edge from this vertex to the referenced vertex.
974 :meth:`EdgeToNewVertex`
975 |rarr| Create a new vertex and link that vertex by an outbound edge from this vertex.
976 :meth:`EdgeFromNewVertex`
977 |rarr| Create a new vertex and link that vertex by an inbound edge to this vertex.
978 :meth:`LinkToVertex`
979 |rarr| Create an outbound link from this vertex to the referenced vertex.
980 :meth:`LinkFromVertex`
981 |rarr| Create an inbound link from the referenced vertex to this vertex.
983 """
984 if self._subgraph is vertex._subgraph:
985 edge = Edge(vertex, self, edgeID, edgeValue, edgeWeight, keyValuePairs)
987 vertex._outboundEdges.append(edge)
988 self._inboundEdges.append(edge)
990 if self._subgraph is None:
991 # TODO: move into Edge?
992 # TODO: keep _graph pointer in edge and then register edge on graph?
993 if edgeID is None:
994 self._graph._edgesWithoutID.append(edge)
995 elif edgeID not in self._graph._edgesWithID:
996 self._graph._edgesWithID[edgeID] = edge
997 else:
998 raise DuplicateEdgeError(f"Edge ID '{edgeID}' already exists in this graph.", edgeID=edgeID)
999 else:
1000 # TODO: keep _graph pointer in edge and then register edge on graph?
1001 if edgeID is None:
1002 self._subgraph._edgesWithoutID.append(edge)
1003 elif edgeID not in self._graph._edgesWithID:
1004 self._subgraph._edgesWithID[edgeID] = edge
1005 else:
1006 raise DuplicateEdgeError(f"Edge ID '{edgeID}' already exists in this graph.", edgeID=edgeID)
1007 else:
1008 ex = NotInSameGraph(f"Vertex {self!r} and vertex {vertex!r} are not in the same graph or subgraph.")
1009 ex.add_note(f"An edge can only connect vertices within the same graph or subgraph.")
1010 ex.add_note(f"Use LinkToVertex or LinkFromVertex to connect vertices across subgraph boundaries.")
1011 raise ex
1013 return edge
1015 def EdgeToNewVertex(
1016 self,
1017 vertexID: Nullable[VertexIDType] = None,
1018 vertexValue: Nullable[VertexValueType] = None,
1019 vertexWeight: Nullable[VertexWeightType] = None,
1020 vertexKeyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None,
1021 edgeID: Nullable[EdgeIDType] = None,
1022 edgeWeight: Nullable[EdgeWeightType] = None,
1023 edgeValue: Nullable[VertexValueType] = None,
1024 edgeKeyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None
1025 ) -> Edge:
1026 """
1027 Create a new vertex and link that vertex by an outbound edge from this vertex.
1029 :param vertexID: Optional, the new vertex' optional ID.
1030 :param vertexValue: Optional, the new vertex' optional value.
1031 :param vertexWeight: Optional, the new vertex' optional weight.
1032 :param vertexKeyValuePairs: Optional, mapping (dictionary) of key-value-pairs for the new vertex.
1033 :param edgeID: Optional, the edge's optional ID for the new edge object.
1034 :param edgeWeight: Optional, the edge's optional weight for the new edge object.
1035 :param edgeValue: Optional, the edge's optional value for the new edge object.
1036 :param edgeKeyValuePairs: Optional, mapping (dictionary) of key-value-pairs for the new edge object.
1037 :returns: The edge object linking this vertex and the created vertex.
1038 :raises DuplicateEdgeError: If the given edge ID already exists in this graph or subgraph.
1039 :raises NotInSameGraph: If both vertices are not in the same graph or subgraph. |br|
1040 Use :meth:`LinkToVertex` or :meth:`LinkFromVertex` to connect vertices across
1041 subgraph boundaries.
1043 .. seealso::
1045 :meth:`EdgeToVertex`
1046 |rarr| Create an outbound edge from this vertex to the referenced vertex.
1047 :meth:`EdgeFromVertex`
1048 |rarr| Create an inbound edge from the referenced vertex to this vertex.
1049 :meth:`EdgeFromNewVertex`
1050 |rarr| Create a new vertex and link that vertex by an inbound edge to this vertex.
1051 :meth:`LinkToVertex`
1052 |rarr| Create an outbound link from this vertex to the referenced vertex.
1053 :meth:`LinkFromVertex`
1054 |rarr| Create an inbound link from the referenced vertex to this vertex.
1056 """
1057 vertex = Vertex(vertexID, vertexValue, vertexWeight, vertexKeyValuePairs, graph=self._graph) # , component=self._component)
1059 if self._subgraph is vertex._subgraph: 1059 ↛ 1083line 1059 didn't jump to line 1083 because the condition on line 1059 was always true
1060 edge = Edge(self, vertex, edgeID, edgeValue, edgeWeight, edgeKeyValuePairs)
1062 self._outboundEdges.append(edge)
1063 vertex._inboundEdges.append(edge)
1065 if self._subgraph is None: 1065 ↛ 1076line 1065 didn't jump to line 1076 because the condition on line 1065 was always true
1066 # TODO: move into Edge?
1067 # TODO: keep _graph pointer in edge and then register edge on graph?
1068 if edgeID is None: 1068 ↛ 1070line 1068 didn't jump to line 1070 because the condition on line 1068 was always true
1069 self._graph._edgesWithoutID.append(edge)
1070 elif edgeID not in self._graph._edgesWithID:
1071 self._graph._edgesWithID[edgeID] = edge
1072 else:
1073 raise DuplicateEdgeError(f"Edge ID '{edgeID}' already exists in this graph.", edgeID=edgeID)
1074 else:
1075 # TODO: keep _graph pointer in edge and then register edge on graph?
1076 if edgeID is None:
1077 self._subgraph._edgesWithoutID.append(edge)
1078 elif edgeID not in self._graph._edgesWithID:
1079 self._subgraph._edgesWithID[edgeID] = edge
1080 else:
1081 raise DuplicateEdgeError(f"Edge ID '{edgeID}' already exists in this graph.", edgeID=edgeID)
1082 else:
1083 ex = NotInSameGraph(f"Vertex {self!r} and vertex {vertex!r} are not in the same graph or subgraph.")
1084 ex.add_note(f"An edge can only connect vertices within the same graph or subgraph.")
1085 ex.add_note(f"Use LinkToVertex or LinkFromVertex to connect vertices across subgraph boundaries.")
1086 raise ex
1088 return edge
1090 def EdgeFromNewVertex(
1091 self,
1092 vertexID: Nullable[VertexIDType] = None,
1093 vertexValue: Nullable[VertexValueType] = None,
1094 vertexWeight: Nullable[VertexWeightType] = None,
1095 vertexKeyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None,
1096 edgeID: Nullable[EdgeIDType] = None,
1097 edgeWeight: Nullable[EdgeWeightType] = None,
1098 edgeValue: Nullable[VertexValueType] = None,
1099 edgeKeyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None
1100 ) -> Edge:
1101 """
1102 Create a new vertex and link that vertex by an inbound edge to this vertex.
1104 :param vertexID: Optional, the new vertex' optional ID.
1105 :param vertexValue: Optional, the new vertex' optional value.
1106 :param vertexWeight: Optional, the new vertex' optional weight.
1107 :param vertexKeyValuePairs: Optional, mapping (dictionary) of key-value-pairs for the new vertex.
1108 :param edgeID: Optional, the edge's optional ID for the new edge object.
1109 :param edgeWeight: Optional, the edge's optional weight for the new edge object.
1110 :param edgeValue: Optional, the edge's optional value for the new edge object.
1111 :param edgeKeyValuePairs: Optional, mapping (dictionary) of key-value-pairs for the new edge object.
1112 :returns: The edge object linking this vertex and the created vertex.
1113 :raises DuplicateEdgeError: If the given edge ID already exists in this graph or subgraph.
1114 :raises NotInSameGraph: If both vertices are not in the same graph or subgraph. |br|
1115 Use :meth:`LinkToVertex` or :meth:`LinkFromVertex` to connect vertices across
1116 subgraph boundaries.
1118 .. seealso::
1120 :meth:`EdgeToVertex`
1121 |rarr| Create an outbound edge from this vertex to the referenced vertex.
1122 :meth:`EdgeFromVertex`
1123 |rarr| Create an inbound edge from the referenced vertex to this vertex.
1124 :meth:`EdgeToNewVertex`
1125 |rarr| Create a new vertex and link that vertex by an outbound edge from this vertex.
1126 :meth:`LinkToVertex`
1127 |rarr| Create an outbound link from this vertex to the referenced vertex.
1128 :meth:`LinkFromVertex`
1129 |rarr| Create an inbound link from the referenced vertex to this vertex.
1131 """
1132 vertex = Vertex(vertexID, vertexValue, vertexWeight, vertexKeyValuePairs, graph=self._graph) # , component=self._component)
1134 if self._subgraph is vertex._subgraph: 1134 ↛ 1158line 1134 didn't jump to line 1158 because the condition on line 1134 was always true
1135 edge = Edge(vertex, self, edgeID, edgeValue, edgeWeight, edgeKeyValuePairs)
1137 vertex._outboundEdges.append(edge)
1138 self._inboundEdges.append(edge)
1140 if self._subgraph is None: 1140 ↛ 1151line 1140 didn't jump to line 1151 because the condition on line 1140 was always true
1141 # TODO: move into Edge?
1142 # TODO: keep _graph pointer in edge and then register edge on graph?
1143 if edgeID is None: 1143 ↛ 1145line 1143 didn't jump to line 1145 because the condition on line 1143 was always true
1144 self._graph._edgesWithoutID.append(edge)
1145 elif edgeID not in self._graph._edgesWithID:
1146 self._graph._edgesWithID[edgeID] = edge
1147 else:
1148 raise DuplicateEdgeError(f"Edge ID '{edgeID}' already exists in this graph.", edgeID=edgeID)
1149 else:
1150 # TODO: keep _graph pointer in edge and then register edge on graph?
1151 if edgeID is None:
1152 self._subgraph._edgesWithoutID.append(edge)
1153 elif edgeID not in self._graph._edgesWithID:
1154 self._subgraph._edgesWithID[edgeID] = edge
1155 else:
1156 raise DuplicateEdgeError(f"Edge ID '{edgeID}' already exists in this graph.", edgeID=edgeID)
1157 else:
1158 ex = NotInSameGraph(f"Vertex {self!r} and vertex {vertex!r} are not in the same graph or subgraph.")
1159 ex.add_note(f"An edge can only connect vertices within the same graph or subgraph.")
1160 ex.add_note(f"Use LinkToVertex or LinkFromVertex to connect vertices across subgraph boundaries.")
1161 raise ex
1163 return edge
1165 def LinkToVertex(
1166 self,
1167 vertex: Vertex,
1168 linkID: Nullable[EdgeIDType] = None,
1169 linkWeight: Nullable[EdgeWeightType] = None,
1170 linkValue: Nullable[VertexValueType] = None,
1171 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None,
1172 ) -> Link:
1173 """
1174 Create an outbound link from this vertex to the referenced vertex.
1176 :param vertex: The vertex to be linked to.
1177 :param linkID: Optional, the link's optional ID for the new link object.
1178 :param linkWeight: Optional, the link's optional weight for the new link object.
1179 :param linkValue: Optional, the link's optional value for the new link object.
1180 :param keyValuePairs: Optional, mapping (dictionary) of key-value-pairs for the new link object.
1181 :returns: The link object linking this vertex and the referenced vertex.
1182 :raises DuplicateEdgeError: If the given link ID already exists in this graph.
1183 :raises NotInDifferentSubgraphs: If both vertices are in the same subgraph - a link connects vertices *across*
1184 subgraph boundaries. |br|
1185 Use :meth:`EdgeToVertex` or :meth:`EdgeFromVertex` to connect vertices within
1186 the same subgraph.
1188 .. seealso::
1190 :meth:`EdgeToVertex`
1191 |rarr| Create an outbound edge from this vertex to the referenced vertex.
1192 :meth:`EdgeFromVertex`
1193 |rarr| Create an inbound edge from the referenced vertex to this vertex.
1194 :meth:`EdgeToNewVertex`
1195 |rarr| Create a new vertex and link that vertex by an outbound edge from this vertex.
1196 :meth:`EdgeFromNewVertex`
1197 |rarr| Create a new vertex and link that vertex by an inbound edge to this vertex.
1198 :meth:`LinkFromVertex`
1199 |rarr| Create an inbound link from the referenced vertex to this vertex.
1201 """
1202 if self._subgraph is vertex._subgraph:
1203 ex = NotInDifferentSubgraphs(f"Vertex {self!r} and vertex {vertex!r} are in the same subgraph.")
1204 ex.add_note(f"A link can only connect vertices across subgraph boundaries.")
1205 ex.add_note(f"Use EdgeToVertex or EdgeFromVertex to connect vertices within the same subgraph.")
1206 raise ex
1207 else:
1208 link = Link(self, vertex, linkID, linkValue, linkWeight, keyValuePairs)
1210 self._outboundLinks.append(link)
1211 vertex._inboundLinks.append(link)
1213 if self._subgraph is None:
1214 # TODO: move into Edge?
1215 # TODO: keep _graph pointer in link and then register link on graph?
1216 if linkID is None: 1216 ↛ 1218line 1216 didn't jump to line 1218 because the condition on line 1216 was always true
1217 self._graph._linksWithoutID.append(link)
1218 elif linkID not in self._graph._linksWithID:
1219 self._graph._linksWithID[linkID] = link
1220 else:
1221 raise DuplicateEdgeError(f"Link ID '{linkID}' already exists in this graph.", edgeID=linkID)
1222 else:
1223 # TODO: keep _graph pointer in link and then register link on graph?
1224 if linkID is None:
1225 self._subgraph._linksWithoutID.append(link)
1226 vertex._subgraph._linksWithoutID.append(link)
1227 elif linkID not in self._graph._linksWithID: 1227 ↛ 1231line 1227 didn't jump to line 1231 because the condition on line 1227 was always true
1228 self._subgraph._linksWithID[linkID] = link
1229 vertex._subgraph._linksWithID[linkID] = link
1230 else:
1231 raise DuplicateEdgeError(f"Link ID '{linkID}' already exists in this graph.", edgeID=linkID)
1233 return link
1235 def LinkFromVertex(
1236 self,
1237 vertex: Vertex,
1238 linkID: Nullable[EdgeIDType] = None,
1239 linkWeight: Nullable[EdgeWeightType] = None,
1240 linkValue: Nullable[VertexValueType] = None,
1241 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None
1242 ) -> Edge:
1243 """
1244 Create an inbound link from the referenced vertex to this vertex.
1246 :param vertex: The vertex to be linked from.
1247 :param linkID: Optional, the link's optional ID for the new link object.
1248 :param linkWeight: Optional, the link's optional weight for the new link object.
1249 :param linkValue: Optional, the link's optional value for the new link object.
1250 :param keyValuePairs: Optional, mapping (dictionary) of key-value-pairs for the new link object.
1251 :returns: The link object linking the referenced vertex and this vertex.
1252 :raises DuplicateEdgeError: If the given link ID already exists in this graph.
1253 :raises NotInDifferentSubgraphs: If both vertices are in the same subgraph - a link connects vertices *across*
1254 subgraph boundaries. |br|
1255 Use :meth:`EdgeToVertex` or :meth:`EdgeFromVertex` to connect vertices within
1256 the same subgraph.
1258 .. seealso::
1260 :meth:`EdgeToVertex`
1261 |rarr| Create an outbound edge from this vertex to the referenced vertex.
1262 :meth:`EdgeFromVertex`
1263 |rarr| Create an inbound edge from the referenced vertex to this vertex.
1264 :meth:`EdgeToNewVertex`
1265 |rarr| Create a new vertex and link that vertex by an outbound edge from this vertex.
1266 :meth:`EdgeFromNewVertex`
1267 |rarr| Create a new vertex and link that vertex by an inbound edge to this vertex.
1268 :meth:`LinkToVertex`
1269 |rarr| Create an outbound link from this vertex to the referenced vertex.
1271 """
1272 if self._subgraph is vertex._subgraph:
1273 ex = NotInDifferentSubgraphs(f"Vertex {self!r} and vertex {vertex!r} are in the same subgraph.")
1274 ex.add_note(f"A link can only connect vertices across subgraph boundaries.")
1275 ex.add_note(f"Use EdgeToVertex or EdgeFromVertex to connect vertices within the same subgraph.")
1276 raise ex
1277 else:
1278 link = Link(vertex, self, linkID, linkValue, linkWeight, keyValuePairs)
1280 vertex._outboundLinks.append(link)
1281 self._inboundLinks.append(link)
1283 if self._subgraph is None: 1283 ↛ 1286line 1283 didn't jump to line 1286 because the condition on line 1283 was never true
1284 # TODO: move into Edge?
1285 # TODO: keep _graph pointer in link and then register link on graph?
1286 if linkID is None:
1287 self._graph._linksWithoutID.append(link)
1288 elif linkID not in self._graph._linksWithID:
1289 self._graph._linksWithID[linkID] = link
1290 else:
1291 raise DuplicateEdgeError(f"Link ID '{linkID}' already exists in this graph.", edgeID=linkID)
1292 else:
1293 # TODO: keep _graph pointer in link and then register link on graph?
1294 if linkID is None: 1294 ↛ 1297line 1294 didn't jump to line 1297 because the condition on line 1294 was always true
1295 self._subgraph._linksWithoutID.append(link)
1296 vertex._subgraph._linksWithoutID.append(link)
1297 elif linkID not in self._graph._linksWithID:
1298 self._subgraph._linksWithID[linkID] = link
1299 vertex._subgraph._linksWithID[linkID] = link
1300 else:
1301 raise DuplicateEdgeError(f"Link ID '{linkID}' already exists in this graph.", edgeID=linkID)
1303 return link
1305 def HasEdgeToDestination(self, destination: Vertex) -> bool:
1306 """
1307 Check if this vertex is linked to another vertex by any outbound edge.
1309 :param destination: Destination vertex to check.
1310 :returns: ``True``, if the destination vertex is a destination on any outbound edge.
1312 .. seealso::
1314 :meth:`HasEdgeFromSource`
1315 |rarr| Check if this vertex is linked to another vertex by any inbound edge.
1316 :meth:`HasLinkToDestination`
1317 |rarr| Check if this vertex is linked to another vertex by any outbound link.
1318 :meth:`HasLinkFromSource`
1319 |rarr| Check if this vertex is linked to another vertex by any inbound link.
1320 """
1321 for edge in self._outboundEdges:
1322 if destination is edge.Destination: 1322 ↛ 1321line 1322 didn't jump to line 1321 because the condition on line 1322 was always true
1323 return True
1325 return False
1327 def HasEdgeFromSource(self, source: Vertex) -> bool:
1328 """
1329 Check if this vertex is linked to another vertex by any inbound edge.
1331 :param source: Source vertex to check.
1332 :returns: ``True``, if the source vertex is a source on any inbound edge.
1334 .. seealso::
1336 :meth:`HasEdgeToDestination`
1337 |rarr| Check if this vertex is linked to another vertex by any outbound edge.
1338 :meth:`HasLinkToDestination`
1339 |rarr| Check if this vertex is linked to another vertex by any outbound link.
1340 :meth:`HasLinkFromSource`
1341 |rarr| Check if this vertex is linked to another vertex by any inbound link.
1342 """
1343 for edge in self._inboundEdges:
1344 if source is edge.Source: 1344 ↛ 1343line 1344 didn't jump to line 1343 because the condition on line 1344 was always true
1345 return True
1347 return False
1349 def HasLinkToDestination(self, destination: Vertex) -> bool:
1350 """
1351 Check if this vertex is linked to another vertex by any outbound link.
1353 :param destination: Destination vertex to check.
1354 :returns: ``True``, if the destination vertex is a destination on any outbound link.
1356 .. seealso::
1358 :meth:`HasEdgeToDestination`
1359 |rarr| Check if this vertex is linked to another vertex by any outbound edge.
1360 :meth:`HasEdgeFromSource`
1361 |rarr| Check if this vertex is linked to another vertex by any inbound edge.
1362 :meth:`HasLinkFromSource`
1363 |rarr| Check if this vertex is linked to another vertex by any inbound link.
1364 """
1365 for link in self._outboundLinks:
1366 if destination is link.Destination: 1366 ↛ 1365line 1366 didn't jump to line 1365 because the condition on line 1366 was always true
1367 return True
1369 return False
1371 def HasLinkFromSource(self, source: Vertex) -> bool:
1372 """
1373 Check if this vertex is linked to another vertex by any inbound link.
1375 :param source: Source vertex to check.
1376 :returns: ``True``, if the source vertex is a source on any inbound link.
1378 .. seealso::
1380 :meth:`HasEdgeToDestination`
1381 |rarr| Check if this vertex is linked to another vertex by any outbound edge.
1382 :meth:`HasEdgeFromSource`
1383 |rarr| Check if this vertex is linked to another vertex by any inbound edge.
1384 :meth:`HasLinkToDestination`
1385 |rarr| Check if this vertex is linked to another vertex by any outbound link.
1386 """
1387 for link in self._inboundLinks:
1388 if source is link.Source: 1388 ↛ 1387line 1388 didn't jump to line 1387 because the condition on line 1388 was always true
1389 return True
1391 return False
1393 def DeleteEdgeTo(self, destination: Vertex) -> None:
1394 """
1395 Delete the outbound edge to the given vertex.
1397 :param destination: The vertex the edge points to.
1398 :raises GraphException: If no outbound edge to that vertex exists.
1399 """
1400 for edge in self._outboundEdges: 1400 ↛ 1404line 1400 didn't jump to line 1404 because the loop on line 1400 didn't complete
1401 if edge._destination is destination: 1401 ↛ 1400line 1401 didn't jump to line 1400 because the condition on line 1401 was always true
1402 break
1403 else:
1404 raise GraphException(f"No outbound edge found to '{destination!r}'.")
1406 edge.Delete()
1408 def DeleteEdgeFrom(self, source: Vertex) -> None:
1409 """
1410 Delete the inbound edge from the given vertex.
1412 :param source: The vertex the edge comes from.
1413 :raises GraphException: If no inbound edge from that vertex exists.
1414 """
1415 for edge in self._inboundEdges:
1416 if edge._source is source:
1417 break
1418 else:
1419 raise GraphException(f"No inbound edge found to '{source!r}'.")
1421 edge.Delete()
1423 def DeleteLinkTo(self, destination: Vertex) -> None:
1424 """
1425 Delete the outbound link to the given vertex.
1427 :param destination: The vertex the link points to.
1428 :raises GraphException: If no outbound link to that vertex exists.
1429 """
1430 for link in self._outboundLinks:
1431 if link._destination is destination:
1432 break
1433 else:
1434 raise GraphException(f"No outbound link found to '{destination!r}'.")
1436 link.Delete()
1438 def DeleteLinkFrom(self, source: Vertex) -> None:
1439 """
1440 Delete the inbound link from the given vertex.
1442 :param source: The vertex the link comes from.
1443 :raises GraphException: If no inbound link from that vertex exists.
1444 """
1445 for link in self._inboundLinks:
1446 if link._source is source:
1447 break
1448 else:
1449 raise GraphException(f"No inbound link found to '{source!r}'.")
1451 link.Delete()
1453 def Copy(self, graph: Graph, copyDict: bool = False, linkingKeyToOriginalVertex: Nullable[str] = None, linkingKeyFromOriginalVertex: Nullable[str] = None) -> Vertex:
1454 """
1455 Creates a copy of this vertex in another graph.
1457 Optionally, the vertex's attached attributes (key-value-pairs) can be copied and a linkage between both vertices
1458 can be established.
1460 :param graph: Optional, the graph, the vertex is created in.
1461 :param copyDict: Optional, if ``True``, copy all attached attributes into the new vertex.
1462 :param linkingKeyToOriginalVertex: Optional, if not ``None``, add a key-value-pair using this parameter as key
1463 from new vertex to the original vertex.
1464 :param linkingKeyFromOriginalVertex: Optional, if not ``None``, add a key-value-pair using this parameter as key
1465 from original vertex to the new vertex.
1466 :returns: The newly created vertex.
1467 :raises GraphException: If source graph and destination graph are the same.
1468 """
1469 if graph is self._graph:
1470 raise GraphException("Graph to copy this vertex to, is the same graph.")
1472 vertex = Vertex(self._id, self._value, self._weight, graph=graph)
1473 if copyDict:
1474 vertex._dict = self._dict.copy()
1476 if linkingKeyToOriginalVertex is not None:
1477 vertex._dict[linkingKeyToOriginalVertex] = self
1478 if linkingKeyFromOriginalVertex is not None:
1479 self._dict[linkingKeyFromOriginalVertex] = vertex
1481 return vertex
1483 def IterateOutboundEdges(self, predicate: Nullable[Callable[[Edge], bool]] = None) -> Generator[Edge, None, None]:
1484 """
1485 Iterate all or selected outbound edges of this vertex.
1487 If parameter ``predicate`` is not None, the given filter function is used to skip edges in the generator.
1489 :param predicate: Optional, filter function accepting any edge and returning a boolean.
1490 :returns: A generator to iterate all outbound edges.
1491 """
1492 if predicate is None:
1493 for edge in self._outboundEdges:
1494 yield edge
1495 else:
1496 for edge in self._outboundEdges:
1497 if predicate(edge):
1498 yield edge
1500 def IterateInboundEdges(self, predicate: Nullable[Callable[[Edge], bool]] = None) -> Generator[Edge, None, None]:
1501 """
1502 Iterate all or selected inbound edges of this vertex.
1504 If parameter ``predicate`` is not None, the given filter function is used to skip edges in the generator.
1506 :param predicate: Optional, filter function accepting any edge and returning a boolean.
1507 :returns: A generator to iterate all inbound edges.
1508 """
1509 if predicate is None:
1510 for edge in self._inboundEdges:
1511 yield edge
1512 else:
1513 for edge in self._inboundEdges:
1514 if predicate(edge):
1515 yield edge
1517 def IterateOutboundLinks(self, predicate: Nullable[Callable[[Link], bool]] = None) -> Generator[Link, None, None]:
1518 """
1519 Iterate all or selected outbound links of this vertex.
1521 If parameter ``predicate`` is not None, the given filter function is used to skip links in the generator.
1523 :param predicate: Optional, filter function accepting any link and returning a boolean.
1524 :returns: A generator to iterate all outbound links.
1525 """
1526 if predicate is None:
1527 for link in self._outboundLinks:
1528 yield link
1529 else:
1530 for link in self._outboundLinks:
1531 if predicate(link):
1532 yield link
1534 def IterateInboundLinks(self, predicate: Nullable[Callable[[Link], bool]] = None) -> Generator[Link, None, None]:
1535 """
1536 Iterate all or selected inbound links of this vertex.
1538 If parameter ``predicate`` is not None, the given filter function is used to skip links in the generator.
1540 :param predicate: Optional, filter function accepting any link and returning a boolean.
1541 :returns: A generator to iterate all inbound links.
1542 """
1543 if predicate is None:
1544 for link in self._inboundLinks:
1545 yield link
1546 else:
1547 for link in self._inboundLinks:
1548 if predicate(link):
1549 yield link
1551 def IterateSuccessorVertices(self, predicate: Nullable[Callable[[Edge], bool]] = None) -> Generator[Vertex, None, None]:
1552 """
1553 Iterate all or selected successor vertices of this vertex.
1555 If parameter ``predicate`` is not None, the given filter function is used to skip successors in the generator.
1557 :param predicate: Optional, filter function accepting any edge and returning a boolean.
1558 :returns: A generator to iterate all successor vertices.
1559 """
1560 if predicate is None:
1561 for edge in self._outboundEdges:
1562 yield edge.Destination
1563 else:
1564 for edge in self._outboundEdges:
1565 if predicate(edge):
1566 yield edge.Destination
1568 def IteratePredecessorVertices(self, predicate: Nullable[Callable[[Edge], bool]] = None) -> Generator[Vertex, None, None]:
1569 """
1570 Iterate all or selected predecessor vertices of this vertex.
1572 If parameter ``predicate`` is not None, the given filter function is used to skip predecessors in the generator.
1574 :param predicate: Optional, filter function accepting any edge and returning a boolean.
1575 :returns: A generator to iterate all predecessor vertices.
1576 """
1577 if predicate is None:
1578 for edge in self._inboundEdges:
1579 yield edge.Source
1580 else:
1581 for edge in self._inboundEdges:
1582 if predicate(edge):
1583 yield edge.Source
1585 def IterateVerticesBFS(self) -> Generator[Vertex, None, None]:
1586 """
1587 A generator to iterate all reachable vertices starting from this node in breadth-first search (BFS) order.
1589 :returns: A generator to iterate vertices traversed in BFS order.
1591 .. seealso::
1593 :meth:`IterateVerticesDFS`
1594 |rarr| Iterate all reachable vertices **depth-first search** order.
1595 """
1596 visited: set[Vertex] = set()
1597 queue: Deque[Vertex] = deque()
1599 yield self
1600 visited.add(self)
1601 for edge in self._outboundEdges:
1602 nextVertex = edge.Destination
1603 if nextVertex is not self: 1603 ↛ 1601line 1603 didn't jump to line 1601 because the condition on line 1603 was always true
1604 queue.appendleft(nextVertex)
1605 visited.add(nextVertex)
1607 while queue:
1608 vertex = queue.pop()
1609 yield vertex
1610 for edge in vertex._outboundEdges:
1611 nextVertex = edge.Destination
1612 if nextVertex not in visited:
1613 queue.appendleft(nextVertex)
1614 visited.add(nextVertex)
1616 def IterateVerticesDFS(self) -> Generator[Vertex, None, None]:
1617 """
1618 A generator to iterate all reachable vertices starting from this node in depth-first search (DFS) order.
1620 :returns: A generator to iterate vertices traversed in DFS order.
1622 .. seealso::
1624 :meth:`IterateVerticesBFS`
1625 |rarr| Iterate all reachable vertices **breadth-first search** order.
1627 Wikipedia - https://en.wikipedia.org/wiki/Depth-first_search
1628 """
1629 visited: set[Vertex] = set()
1630 stack: list[typing_Iterator[Edge]] = list()
1632 yield self
1633 visited.add(self)
1634 stack.append(iter(self._outboundEdges))
1636 while True:
1637 try:
1638 edge = next(stack[-1])
1639 nextVertex = edge._destination
1640 if nextVertex not in visited:
1641 visited.add(nextVertex)
1642 yield nextVertex
1643 if len(nextVertex._outboundEdges) != 0:
1644 stack.append(iter(nextVertex._outboundEdges))
1645 except StopIteration:
1646 stack.pop()
1648 if len(stack) == 0:
1649 return
1651 def IterateAllOutboundPathsAsVertexList(self) -> Generator[tuple[Vertex, ...], None, None]:
1652 """
1653 Iterate all paths starting at this vertex, each as a tuple of vertices.
1655 The traversal is depth-first and keeps the vertices of the current path in a set, so a cycle is detected
1656 instead of iterated endlessly. A vertex without outbound edges yields the path containing only itself.
1658 :returns: A generator yielding one tuple of vertices per path.
1659 :raises CycleError: If a cycle is detected while walking a path.
1660 """
1661 if len(self._outboundEdges) == 0:
1662 yield (self, )
1663 return
1665 visited: set[Vertex] = set()
1666 vertexStack: list[Vertex] = list()
1667 iteratorStack: list[typing_Iterator[Edge]] = list()
1669 visited.add(self)
1670 vertexStack.append(self)
1671 iteratorStack.append(iter(self._outboundEdges))
1673 while True:
1674 try:
1675 edge = next(iteratorStack[-1])
1676 nextVertex = edge._destination
1677 if nextVertex in visited:
1678 ex = CycleError(f"Loop detected.")
1679 ex.add_note(f"First loop is:")
1680 for i, vertex in enumerate(vertexStack):
1681 ex.add_note(f" {i}: {vertex!r}")
1682 raise ex
1684 vertexStack.append(nextVertex)
1685 if len(nextVertex._outboundEdges) == 0:
1686 yield tuple(vertexStack)
1687 vertexStack.pop()
1688 else:
1689 iteratorStack.append(iter(nextVertex._outboundEdges))
1691 except StopIteration:
1692 vertexStack.pop()
1693 iteratorStack.pop()
1695 if len(vertexStack) == 0:
1696 return
1698 def ShortestPathToByHops(self, destination: Vertex) -> Generator[Vertex, None, None]:
1699 """
1700 Compute the shortest path (by hops) between this vertex and the destination vertex.
1702 A generator is return to iterate all vertices along the path including source and destination vertex.
1704 The search algorithm is breadth-first search (BFS) based. The found solution, if any, is not unique but deterministic
1705 as long as the graph was not modified (e.g. ordering of edges on vertices).
1707 :param destination: The destination vertex to reach.
1708 :returns: A generator to iterate all vertices on the path found between this vertex and the
1709 destination vertex.
1710 :raises DestinationNotReachable: If the destination vertex cannot be reached from this vertex.
1711 """
1712 # Trivial case if start is destination
1713 if self is destination: 1713 ↛ 1714line 1713 didn't jump to line 1714 because the condition on line 1713 was never true
1714 yield self
1715 return
1717 # Local struct to create multiple linked-lists forming a paths from current node back to the starting point
1718 # (actually a tree). Each node holds a reference to the vertex it represents.
1719 # Hint: slotted classes are faster than '@dataclasses.dataclass'.
1720 class Node(metaclass=ExtendedType, slots=True):
1721 """A node of the search tree: the vertex it represents and its predecessor on the path."""
1722 parent: Node #: Predecessor on the path back to the starting point.
1723 ref: Vertex #: The vertex this node represents.
1725 def __init__(self, parent: Node, ref: Vertex) -> None:
1726 """
1727 Initialize a search tree node.
1729 :param parent: Predecessor on the path back to the starting point.
1730 :param ref: The vertex this node represents.
1731 """
1732 self.parent = parent
1733 self.ref = ref
1735 def __str__(self) -> str:
1736 """
1737 Return a string representation of this search tree node.
1739 :returns: The ID of the vertex this node represents.
1740 """
1741 return f"Vertex: {self.ref.ID}"
1743 # Initially add all reachable vertices to a queue if vertices to be processed.
1744 startNode = Node(None, self)
1745 visited: set[Vertex] = set()
1746 queue: Deque[Node] = deque()
1748 # Add starting vertex and all its children to the processing list.
1749 # If a child is the destination, break immediately else go into 'else' branch and use BFS algorithm.
1750 visited.add(self)
1751 for edge in self._outboundEdges:
1752 nextVertex = edge.Destination
1753 if nextVertex is destination: 1753 ↛ 1755line 1753 didn't jump to line 1755 because the condition on line 1753 was never true
1754 # Child is destination, so construct the last node for path traversal and break from loop.
1755 destinationNode = Node(startNode, nextVertex)
1756 break
1757 if nextVertex is not self: 1757 ↛ 1751line 1757 didn't jump to line 1751 because the condition on line 1757 was always true
1758 # Ignore backward-edges and side-edges.
1759 # Here self-edges, because there is only the starting vertex in the list of visited edges.
1760 visited.add(nextVertex)
1761 queue.appendleft(Node(startNode, nextVertex))
1762 else:
1763 # Process queue until destination is found or no further vertices are reachable.
1764 while queue:
1765 node = queue.pop()
1766 for edge in node.ref._outboundEdges:
1767 nextVertex = edge.Destination
1768 # Next reachable vertex is destination, so construct the last node for path traversal and break from loop.
1769 if nextVertex is destination:
1770 destinationNode = Node(node, nextVertex)
1771 break
1772 # Ignore backward-edges and side-edges.
1773 if nextVertex not in visited:
1774 visited.add(nextVertex)
1775 queue.appendleft(Node(node, nextVertex))
1776 # Next 3 lines realize a double-break if break was called in inner loop, otherwise continue with outer loop.
1777 else:
1778 continue
1779 break
1780 else:
1781 # All reachable vertices have been processed, but destination was not among them.
1782 raise DestinationNotReachable(f"Destination is not reachable.")
1784 # Reverse order of linked list from destinationNode to startNode
1785 currentNode = destinationNode
1786 previousNode = destinationNode.parent
1787 currentNode.parent = None
1788 while previousNode is not None:
1789 node = previousNode.parent
1790 previousNode.parent = currentNode
1791 currentNode = previousNode
1792 previousNode = node
1794 # Scan reversed linked-list and yield referenced vertices
1795 yield startNode.ref
1796 node = startNode.parent
1797 while node is not None:
1798 yield node.ref
1799 node = node.parent
1801 def ShortestPathToByWeight(self, destination: Vertex) -> Generator[Vertex, None, None]:
1802 """
1803 Compute the shortest path (by edge weight) between this vertex and the destination vertex.
1805 A generator is return to iterate all vertices along the path including source and destination vertex.
1807 The search algorithm is based on Dijkstra algorithm and using :mod:`heapq`. The found solution, if any, is not
1808 unique but deterministic as long as the graph was not modified (e.g. ordering of edges on vertices).
1810 :param destination: The destination vertex to reach.
1811 :returns: A generator to iterate all vertices on the path found between this vertex and the
1812 destination vertex.
1813 :raises DestinationNotReachable: If the destination vertex cannot be reached from this vertex.
1814 """
1815 # Improvements: both-sided Dijkstra (search from start and destination to reduce discovered area.
1817 # Trivial case if start is destination
1818 if self is destination: 1818 ↛ 1819line 1818 didn't jump to line 1819 because the condition on line 1818 was never true
1819 yield self
1820 return
1822 # Local struct to create multiple-linked lists forming a paths from current node back to the starting point
1823 # (actually a tree). Each node holds the overall weight from start to current node and a reference to the vertex it
1824 # represents.
1825 # Hint: slotted classes are faster than '@dataclasses.dataclass'.
1826 class Node(metaclass=ExtendedType, slots=True):
1827 """A node of the search tree: the vertex, its predecessor, and the accumulated weight to reach it."""
1828 parent: Node #: Predecessor on the path back to the starting point.
1829 distance: EdgeWeightType #: Accumulated edge weight from the starting point to this node.
1830 ref: Vertex #: The vertex this node represents.
1832 def __init__(self, parent: Node, distance: EdgeWeightType, ref: Vertex) -> None:
1833 """
1834 Initialize a search tree node.
1836 :param parent: Predecessor on the path back to the starting point.
1837 :param distance: Accumulated edge weight from the starting point to this node.
1838 :param ref: The vertex this node represents.
1839 """
1840 self.parent = parent
1841 self.distance = distance
1842 self.ref = ref
1844 def __lt__(self, other: Any) -> bool:
1845 """
1846 Compare two search tree nodes by their accumulated distance, so they can be kept in a priority queue.
1848 :param other: Second operand.
1849 :returns: ``True``, if this node is closer to the starting point than the second operand.
1850 """
1851 return self.distance < other.distance
1853 def __str__(self) -> str:
1854 """
1855 Return a string representation of this search tree node.
1857 :returns: The ID of the vertex this node represents.
1858 """
1859 return f"Vertex: {self.ref.ID}"
1861 visited: set[Vertex] = set()
1862 startNode = Node(None, 0, self)
1863 priorityQueue = [startNode]
1865 # Add starting vertex and all its children to the processing list.
1866 # If a child is the destination, break immediately else go into 'else' branch and use Dijkstra algorithm.
1867 visited.add(self)
1868 for edge in self._outboundEdges:
1869 nextVertex = edge.Destination
1870 # Child is destination, so construct the last node for path traversal and break from loop.
1871 if nextVertex is destination: 1871 ↛ 1872line 1871 didn't jump to line 1872 because the condition on line 1871 was never true
1872 destinationNode = Node(startNode, edge._weight, nextVertex)
1873 break
1874 # Ignore backward-edges and side-edges.
1875 # Here self-edges, because there is only the starting vertex in the list of visited edges.
1876 if nextVertex is not self: 1876 ↛ 1868line 1876 didn't jump to line 1868 because the condition on line 1876 was always true
1877 visited.add(nextVertex)
1878 heapq.heappush(priorityQueue, Node(startNode, edge._weight, nextVertex))
1879 else:
1880 # Process priority queue until destination is found or no further vertices are reachable.
1881 while priorityQueue: 1881 ↛ 1899line 1881 didn't jump to line 1899 because the condition on line 1881 was always true
1882 node = heapq.heappop(priorityQueue)
1883 for edge in node.ref._outboundEdges:
1884 nextVertex = edge.Destination
1885 # Next reachable vertex is destination, so construct the last node for path traversal and break from loop.
1886 if nextVertex is destination:
1887 destinationNode = Node(node, node.distance + edge._weight, nextVertex)
1888 break
1889 # Ignore backward-edges and side-edges.
1890 if nextVertex not in visited:
1891 visited.add(nextVertex)
1892 heapq.heappush(priorityQueue, Node(node, node.distance + edge._weight, nextVertex))
1893 # Next 3 lines realize a double-break if break was called in inner loop, otherwise continue with outer loop.
1894 else:
1895 continue
1896 break
1897 else:
1898 # All reachable vertices have been processed, but destination was not among them.
1899 raise DestinationNotReachable(f"Destination is not reachable.")
1901 # Reverse order of linked-list from destinationNode to startNode
1902 currentNode = destinationNode
1903 previousNode = destinationNode.parent
1904 currentNode.parent = None
1905 while previousNode is not None:
1906 node = previousNode.parent
1907 previousNode.parent = currentNode
1908 currentNode = previousNode
1909 previousNode = node
1911 # Scan reversed linked-list and yield referenced vertices
1912 yield startNode.ref, startNode.distance
1913 node = startNode.parent
1914 while node is not None:
1915 yield node.ref, node.distance
1916 node = node.parent
1918 # Other possible algorithms:
1919 # * Bellman-Ford
1920 # * Floyd-Warshall
1922 # def PathExistsTo(self, destination: 'Vertex'):
1923 # raise NotImplementedError()
1924 # # DFS
1925 # # Union find
1926 #
1927 # def MaximumFlowTo(self, destination: 'Vertex'):
1928 # raise NotImplementedError()
1929 # # Ford-Fulkerson algorithm
1930 # # Edmons-Karp algorithm
1931 # # Dinic's algorithm
1933 def ConvertToTree(self) -> Node:
1934 """
1935 Converts all reachable vertices from this starting vertex to a tree of :class:`~pyTooling.Tree.Node` instances.
1937 The tree is traversed using depths-first-search.
1939 :returns: Root node of the resulting tree, representing this vertex.
1940 :raises NotATreeError: If the graph reachable from this vertex is not a tree, because a vertex has more than one
1941 parent.
1942 """
1943 visited: set[Vertex] = set()
1944 stack: list[tuple[Node, typing_Iterator[Edge]]] = list()
1946 root = Node(nodeID=self._id, value=self._value)
1947 root._dict = self._dict.copy()
1949 visited.add(self)
1950 stack.append((root, iter(self._outboundEdges)))
1952 while True:
1953 try:
1954 edge = next(stack[-1][1])
1955 nextVertex = edge._destination
1956 if nextVertex not in visited: 1956 ↛ 1962line 1956 didn't jump to line 1962 because the condition on line 1956 was always true
1957 node = Node(nextVertex._id, nextVertex._value, parent=stack[-1][0])
1958 visited.add(nextVertex)
1959 if len(nextVertex._outboundEdges) != 0:
1960 stack.append((node, iter(nextVertex._outboundEdges)))
1961 else:
1962 raise NotATreeError(f"The directed subgraph is not a tree.")
1963 # TODO: compute cycle:
1964 # a) branch 1 is described in stack
1965 # b) branch 2 can be found by walking from joint to root in the tree
1966 except StopIteration:
1967 stack.pop()
1969 if len(stack) == 0:
1970 return root
1972 def __repr__(self) -> str:
1973 """
1974 Returns a detailed string representation of the vertex.
1976 :returns: The detailed string representation of the vertex.
1977 """
1978 vertexID = value = ""
1979 sep = ": "
1980 if self._id is not None:
1981 vertexID = f"{sep}vertexID='{self._id}'"
1982 sep = "; "
1983 if self._value is not None: 1983 ↛ 1984line 1983 didn't jump to line 1984 because the condition on line 1983 was never true
1984 value = f"{sep}value='{self._value}'"
1986 return f"<vertex{vertexID}{value}>"
1988 def __str__(self) -> str:
1989 """
1990 Return a string representation of the vertex.
1992 Order of resolution:
1994 1. If :attr:`_value` is not None, return the string representation of :attr:`_value`.
1995 2. If :attr:`_id` is not None, return the string representation of :attr:`_id`.
1996 3. Else, return :meth:`__repr__`.
1998 :returns: The resolved string representation of the vertex.
1999 """
2000 if self._value is not None: 2000 ↛ 2001line 2000 didn't jump to line 2001 because the condition on line 2000 was never true
2001 return str(self._value)
2002 elif self._id is not None: 2002 ↛ 2003line 2002 didn't jump to line 2003 because the condition on line 2002 was never true
2003 return str(self._id)
2004 else:
2005 return self.__repr__()
2008@export
2009class BaseEdge(
2010 BaseWithIDValueAndWeight[EdgeIDType, EdgeValueType, EdgeWeightType, EdgeDictKeyType, EdgeDictValueType],
2011 Generic[EdgeIDType, EdgeValueType, EdgeWeightType, EdgeDictKeyType, EdgeDictValueType]
2012):
2013 """
2014 An **edge** can have a unique ID, a value, a weight and attached meta information as key-value-pairs. All edges are
2015 directed.
2016 """
2017 _source: Vertex #: Vertex the edge starts at.
2018 _destination: Vertex #: Vertex the edge ends at.
2020 def __init__(
2021 self,
2022 source: Vertex,
2023 destination: Vertex,
2024 edgeID: Nullable[EdgeIDType] = None,
2025 value: Nullable[EdgeValueType] = None,
2026 weight: Nullable[EdgeWeightType] = None,
2027 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None
2028 ) -> None:
2029 """
2030 Initialize an edge between a source and a destination vertex.
2032 :param source: The source of the new edge.
2033 :param destination: The destination of the new edge.
2034 :param edgeID: Optional, unique ID for the new edge.
2035 :param value: Optional, value for the new edge.
2036 :param weight: Optional, weight for the new edge.
2037 :param keyValuePairs: Optional, mapping (dictionary) of key-value-pairs.
2038 """
2039 super().__init__(edgeID, value, weight, keyValuePairs)
2041 self._source = source
2042 self._destination = destination
2044 component = source._component
2045 if component is not destination._component:
2046 # TODO: should it be divided into with/without ID?
2047 oldComponent = destination._component
2048 for vertex in oldComponent._vertices:
2049 vertex._component = component
2050 component._vertices.add(vertex)
2051 component._graph._components.remove(oldComponent)
2052 del oldComponent
2054 @readonly
2055 def Source(self) -> Vertex:
2056 """
2057 Read-only property to get the source (:attr:`_source`) of an edge.
2059 :returns: The source of an edge.
2060 """
2061 return self._source
2063 @readonly
2064 def Destination(self) -> Vertex:
2065 """
2066 Read-only property to get the destination (:attr:`_destination`) of an edge.
2068 :returns: The destination of an edge.
2069 """
2070 return self._destination
2072 def Reverse(self) -> None:
2073 """Reverse the direction of this edge."""
2074 swap = self._source
2075 self._source = self._destination
2076 self._destination = swap
2079@export
2080class Edge(
2081 BaseEdge[EdgeIDType, EdgeValueType, EdgeWeightType, EdgeDictKeyType, EdgeDictValueType],
2082 Generic[EdgeIDType, EdgeValueType, EdgeWeightType, EdgeDictKeyType, EdgeDictValueType]
2083):
2084 """
2085 An **edge** can have a unique ID, a value, a weight and attached meta information as key-value-pairs. All edges are
2086 directed.
2087 """
2089 def __init__(
2090 self,
2091 source: Vertex,
2092 destination: Vertex,
2093 edgeID: Nullable[EdgeIDType] = None,
2094 value: Nullable[EdgeValueType] = None,
2095 weight: Nullable[EdgeWeightType] = None,
2096 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None
2097 ) -> None:
2098 """
2099 Initialize an edge between two vertices of the same graph or subgraph.
2101 :param source: The source of the new edge.
2102 :param destination: The destination of the new edge.
2103 :param edgeID: Optional, unique ID for the new edge.
2104 :param value: Optional, value for the new edge.
2105 :param weight: Optional, weight for the new edge.
2106 :param keyValuePairs: Optional, mapping (dictionary) of key-value-pairs.
2107 :raises TypeError: If parameter 'weight' is not of the graph's edge weight type.
2108 :raises NotInSameGraph: If source and destination vertex are not in the same graph or subgraph.
2109 """
2110 if not isinstance(source, Vertex):
2111 ex = TypeError("Parameter 'source' is not of type 'Vertex'.")
2112 ex.add_note(f"Got type '{getFullyQualifiedName(source)}'.")
2113 raise ex
2114 if not isinstance(destination, Vertex):
2115 ex = TypeError("Parameter 'destination' is not of type 'Vertex'.")
2116 ex.add_note(f"Got type '{getFullyQualifiedName(destination)}'.")
2117 raise ex
2118 if edgeID is not None and not isinstance(edgeID, Hashable):
2119 ex = TypeError("Parameter 'edgeID' is not of type 'EdgeIDType'.")
2120 ex.add_note(f"Got type '{getFullyQualifiedName(edgeID)}'.")
2121 raise ex
2122 # if value is not None and not isinstance(value, Vertex):
2123 # raise TypeError("Parameter 'value' is not of type 'EdgeValueType'.")
2124 if weight is not None and not isinstance(weight, (int, float)):
2125 ex = TypeError("Parameter 'weight' is not of type 'EdgeWeightType'.")
2126 ex.add_note(f"Got type '{getFullyQualifiedName(weight)}'.")
2127 raise ex
2128 if source._graph is not destination._graph:
2129 raise NotInSameGraph(f"Source vertex and destination vertex are not in same graph.")
2131 super().__init__(source, destination, edgeID, value, weight, keyValuePairs)
2133 def Delete(self) -> None:
2134 """
2135 Delete this edge from both of its vertices and from the graph or subgraph it belongs to.
2136 """
2137 # Remove from Source and Destination
2138 self._source._outboundEdges.remove(self)
2139 self._destination._inboundEdges.remove(self)
2141 self._Unregister()
2142 self._Delete()
2144 def _Unregister(self) -> None:
2145 """
2146 Remove this edge from the graph or subgraph it was registered on.
2148 An edge is registered on the subgraph it lives in, otherwise on the graph. Called by :meth:`Delete` and by
2149 :meth:`Vertex.Delete`, which unlinks the vertices itself.
2150 """
2151 container = self._source._graph if self._source._subgraph is None else self._source._subgraph
2152 if self._id is None:
2153 container._edgesWithoutID.remove(self)
2154 else:
2155 del container._edgesWithID[self._id]
2157 def _Delete(self) -> None:
2158 """
2159 Delete the edge's attached attributes, after it was disconnected.
2160 """
2161 super().Delete()
2163 def Reverse(self) -> None:
2164 """Reverse the direction of this edge."""
2165 self._source._outboundEdges.remove(self)
2166 self._source._inboundEdges.append(self)
2167 self._destination._inboundEdges.remove(self)
2168 self._destination._outboundEdges.append(self)
2170 super().Reverse()
2173@export
2174class Link(
2175 BaseEdge[LinkIDType, LinkValueType, LinkWeightType, LinkDictKeyType, LinkDictValueType],
2176 Generic[LinkIDType, LinkValueType, LinkWeightType, LinkDictKeyType, LinkDictValueType]
2177):
2178 """
2179 A **link** can have a unique ID, a value, a weight and attached meta information as key-value-pairs. All links are
2180 directed.
2181 """
2183 def __init__(
2184 self,
2185 source: Vertex,
2186 destination: Vertex,
2187 linkID: LinkIDType = None,
2188 value: LinkValueType = None,
2189 weight: Nullable[LinkWeightType] = None,
2190 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None
2191 ) -> None:
2192 """
2193 Initialize a link between two vertices of different subgraphs.
2195 :param source: The source of the new link.
2196 :param destination: The destination of the new link.
2197 :param linkID: Optional, unique ID for the new link.
2198 :param value: Optional, value for the new v.
2199 :param weight: Optional, weight for the new link.
2200 :param keyValuePairs: Optional, mapping (dictionary) of key-value-pairs.
2201 :raises TypeError: If parameter 'weight' is not of the graph's link weight type.
2202 :raises NotInSameGraph: If source and destination vertex are in the same subgraph, where an edge is to be used.
2203 """
2204 if not isinstance(source, Vertex):
2205 ex = TypeError("Parameter 'source' is not of type 'Vertex'.")
2206 ex.add_note(f"Got type '{getFullyQualifiedName(source)}'.")
2207 raise ex
2208 if not isinstance(destination, Vertex):
2209 ex = TypeError("Parameter 'destination' is not of type 'Vertex'.")
2210 ex.add_note(f"Got type '{getFullyQualifiedName(destination)}'.")
2211 raise ex
2212 if linkID is not None and not isinstance(linkID, Hashable):
2213 ex = TypeError("Parameter 'linkID' is not of type 'LinkIDType'.")
2214 ex.add_note(f"Got type '{getFullyQualifiedName(linkID)}'.")
2215 raise ex
2216 # if value is not None and not isinstance(value, Vertex):
2217 # raise TypeError("Parameter 'value' is not of type 'EdgeValueType'.")
2218 if weight is not None and not isinstance(weight, (int, float)):
2219 ex = TypeError("Parameter 'weight' is not of type 'EdgeWeightType'.")
2220 ex.add_note(f"Got type '{getFullyQualifiedName(weight)}'.")
2221 raise ex
2222 if source._graph is not destination._graph:
2223 raise NotInSameGraph(f"Source vertex and destination vertex are not in same graph.")
2225 super().__init__(source, destination, linkID, value, weight, keyValuePairs)
2227 def Delete(self) -> None:
2228 """
2229 Delete this link from both of its vertices and from the graph and subgraphs it belongs to.
2230 """
2231 self._source._outboundLinks.remove(self)
2232 self._destination._inboundLinks.remove(self)
2234 self._Unregister()
2235 self._Delete()
2237 def _Unregister(self) -> None:
2238 """
2239 Remove this link from the graph or the subgraphs it was registered on.
2241 A link crossing a subgraph boundary is registered on both subgraphs, a link between two top-level vertices on
2242 the graph. Called by :meth:`Delete` and by :meth:`Vertex.Delete`, which unlinks the vertices itself.
2243 """
2244 if self._source._subgraph is None: 2244 ↛ 2245line 2244 didn't jump to line 2245 because the condition on line 2244 was never true
2245 containers = (self._source._graph, )
2246 else:
2247 containers = tuple(sg for sg in (self._source._subgraph, self._destination._subgraph) if sg is not None)
2249 for container in containers:
2250 if self._id is None:
2251 container._linksWithoutID.remove(self)
2252 else:
2253 del container._linksWithID[self._id]
2255 def _Delete(self) -> None:
2256 """
2257 Delete the link's attached attributes, after it was disconnected.
2258 """
2259 super().Delete()
2261 def Reverse(self) -> None:
2262 """Reverse the direction of this link."""
2263 self._source._outboundLinks.remove(self)
2264 self._source._inboundLinks.append(self)
2265 self._destination._inboundLinks.remove(self)
2266 self._destination._outboundLinks.append(self)
2268 super().Reverse()
2271@export
2272class BaseGraph(
2273 BaseWithName[GraphDictKeyType, GraphDictValueType],
2274 Generic[
2275 GraphDictKeyType, GraphDictValueType,
2276 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,
2277 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,
2278 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType
2279 ]
2280):
2281 """
2282 .. todo:: GRAPH::BaseGraph Needs documentation.
2284 """
2286 _verticesWithID: dict[VertexIDType, Vertex[GraphDictKeyType, GraphDictValueType, VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType, EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType, LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType]] #: Vertices with an ID, by ID.
2287 _verticesWithoutID: list[Vertex[GraphDictKeyType, GraphDictValueType, VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType, EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType, LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType]] #: Vertices without an ID, in insertion order.
2288 _edgesWithID: dict[EdgeIDType, Edge[EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType]] #: Edges with an ID, by ID.
2289 _edgesWithoutID: list[Edge[EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType]] #: Edges without an ID, in insertion order.
2290 _linksWithID: dict[EdgeIDType, Link[LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType]] #: Links between subgraphs with an ID, by ID.
2291 _linksWithoutID: list[Link[LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType]] #: Links between subgraphs without an ID, in insertion order.
2293 def __init__(
2294 self,
2295 name: Nullable[str] = None,
2296 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None
2297 #, vertices: Nullable[Iterable[Vertex]] = None) -> None:
2298 ) -> None:
2299 """
2300 .. todo:: GRAPH::BaseGraph::init Needs documentation.
2302 :param name: Optional, name of the graph.
2303 :param keyValuePairs: Optional, mapping (dictionary) of key-value-pairs.
2304 """
2305 super().__init__(name, keyValuePairs)
2307 self._verticesWithoutID = []
2308 self._verticesWithID = {}
2309 self._edgesWithoutID = []
2310 self._edgesWithID = {}
2311 self._linksWithoutID = []
2312 self._linksWithID = {}
2314 def __del__(self) -> None:
2315 """
2316 .. todo:: GRAPH::BaseGraph::del Needs documentation.
2318 """
2319 try:
2320 del self._verticesWithoutID
2321 del self._verticesWithID
2322 del self._edgesWithoutID
2323 del self._edgesWithID
2324 del self._linksWithoutID
2325 del self._linksWithID
2326 except AttributeError:
2327 pass
2329 super().__del__()
2331 @readonly
2332 def VertexCount(self) -> int:
2333 """Read-only property to return the number of vertices in this graph.
2335 :returns: The number of vertices in this graph."""
2336 return len(self._verticesWithoutID) + len(self._verticesWithID)
2338 @readonly
2339 def EdgeCount(self) -> int:
2340 """Read-only property to return the number of edges in this graph.
2342 :returns: The number of edges in this graph."""
2343 return len(self._edgesWithoutID) + len(self._edgesWithID)
2345 @readonly
2346 def LinkCount(self) -> int:
2347 """Read-only property to return the number of links in this graph.
2349 :returns: The number of links in this graph."""
2350 return len(self._linksWithoutID) + len(self._linksWithID)
2352 def IterateVertices(self, predicate: Nullable[Callable[[Vertex], bool]] = None) -> Generator[Vertex[GraphDictKeyType, GraphDictValueType, VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType, EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType, LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType], None, None]:
2353 """
2354 Iterate all or selected vertices of a graph.
2356 If parameter ``predicate`` is not None, the given filter function is used to skip vertices in the generator.
2358 :param predicate: Optional, filter function accepting any vertex and returning a boolean.
2359 :returns: A generator to iterate all vertices.
2360 """
2361 if predicate is None:
2362 yield from self._verticesWithoutID
2363 yield from self._verticesWithID.values()
2365 else:
2366 for vertex in self._verticesWithoutID:
2367 if predicate(vertex):
2368 yield vertex
2370 for vertex in self._verticesWithID.values():
2371 if predicate(vertex):
2372 yield vertex
2374 def IterateRoots(self, predicate: Nullable[Callable[[Vertex], bool]] = None) -> Generator[Vertex[GraphDictKeyType, GraphDictValueType, VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType, EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType, LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType], None, None]:
2375 """
2376 Iterate all or selected roots (vertices without inbound edges / without predecessors) of a graph.
2378 If parameter ``predicate`` is not None, the given filter function is used to skip vertices in the generator.
2380 :param predicate: Optional, filter function accepting any vertex and returning a boolean.
2381 :returns: A generator to iterate all vertices without inbound edges.
2383 .. seealso::
2385 :meth:`BaseGraph.IterateLeafs <pyTooling.Graph.BaseGraph.IterateLeafs>`
2386 |rarr| Iterate leafs of a graph.
2387 :meth:`Vertex.IsRoot <pyTooling.Graph.Vertex.IsRoot>`
2388 |rarr| Check if a vertex is a root vertex in the graph.
2389 :meth:`Vertex.IsLeaf <pyTooling.Graph.Vertex.IsLeaf>`
2390 |rarr| Check if a vertex is a leaf vertex in the graph.
2391 """
2392 if predicate is None:
2393 for vertex in self._verticesWithoutID:
2394 if len(vertex._inboundEdges) == 0:
2395 yield vertex
2397 for vertex in self._verticesWithID.values(): 2397 ↛ 2398line 2397 didn't jump to line 2398 because the loop on line 2397 never started
2398 if len(vertex._inboundEdges) == 0:
2399 yield vertex
2400 else:
2401 for vertex in self._verticesWithoutID:
2402 if len(vertex._inboundEdges) == 0 and predicate(vertex):
2403 yield vertex
2405 for vertex in self._verticesWithID.values(): 2405 ↛ 2406line 2405 didn't jump to line 2406 because the loop on line 2405 never started
2406 if len(vertex._inboundEdges) == 0 and predicate(vertex):
2407 yield vertex
2409 def IterateLeafs(self, predicate: Nullable[Callable[[Vertex], bool]] = None) -> Generator[Vertex[GraphDictKeyType, GraphDictValueType, VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType, EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType, LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType], None, None]:
2410 """
2411 Iterate all or selected leafs (vertices without outbound edges / without successors) of a graph.
2413 If parameter ``predicate`` is not None, the given filter function is used to skip vertices in the generator.
2415 :param predicate: Optional, filter function accepting any vertex and returning a boolean.
2416 :returns: A generator to iterate all vertices without outbound edges.
2418 .. seealso::
2420 :meth:`BaseGraph.IterateRoots <pyTooling.Graph.BaseGraph.IterateRoots>`
2421 |rarr| Iterate roots of a graph.
2422 :meth:`Vertex.IsRoot <pyTooling.Graph.Vertex.IsRoot>`
2423 |rarr| Check if a vertex is a root vertex in the graph.
2424 :meth:`Vertex.IsLeaf <pyTooling.Graph.Vertex.IsLeaf>`
2425 |rarr| Check if a vertex is a leaf vertex in the graph.
2426 """
2427 if predicate is None:
2428 for vertex in self._verticesWithoutID:
2429 if len(vertex._outboundEdges) == 0:
2430 yield vertex
2432 for vertex in self._verticesWithID.values():
2433 if len(vertex._outboundEdges) == 0:
2434 yield vertex
2435 else:
2436 for vertex in self._verticesWithoutID:
2437 if len(vertex._outboundEdges) == 0 and predicate(vertex):
2438 yield vertex
2440 for vertex in self._verticesWithID.values():
2441 if len(vertex._outboundEdges) == 0 and predicate(vertex): 2441 ↛ 2442line 2441 didn't jump to line 2442 because the condition on line 2441 was never true
2442 yield vertex
2444 # def IterateBFS(self, predicate: Nullable[Callable[[Vertex], bool]] = None) -> Generator[Vertex[GraphDictKeyType, GraphDictValueType, VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType, EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType, LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType], None, None]:
2445 # raise NotImplementedError()
2446 #
2447 # def IterateDFS(self, predicate: Nullable[Callable[[Vertex], bool]] = None) -> Generator[Vertex[GraphDictKeyType, GraphDictValueType, VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType, EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType, LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType], None, None]:
2448 # raise NotImplementedError()
2450 def IterateTopologically(self, predicate: Nullable[Callable[[Vertex], bool]] = None) -> Generator[Vertex[GraphDictKeyType, GraphDictValueType, VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType, EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType, LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType], None, None]:
2451 """
2452 Iterate all or selected vertices in topological order.
2454 If parameter ``predicate`` is not None, the given filter function is used to skip vertices in the generator.
2456 :param predicate: Optional, filter function accepting any vertex and returning a boolean.
2457 :returns: A generator to iterate all vertices in topological order.
2458 :raises CycleError: If the graph contains a cycle, so no topological order exists.
2459 :raises InternalError: If the algorithm's internal state became inconsistent.
2460 :except CycleError: Raised if graph is cyclic, thus topological sorting isn't possible.
2461 """
2462 outboundEdgeCounts = {}
2463 leafVertices = []
2465 for vertex in self._verticesWithoutID:
2466 if (count := len(vertex._outboundEdges)) == 0:
2467 leafVertices.append(vertex)
2468 else:
2469 outboundEdgeCounts[vertex] = count
2471 for vertex in self._verticesWithID.values():
2472 if (count := len(vertex._outboundEdges)) == 0:
2473 leafVertices.append(vertex)
2474 else:
2475 outboundEdgeCounts[vertex] = count
2477 if not leafVertices: 2477 ↛ 2478line 2477 didn't jump to line 2478 because the condition on line 2477 was never true
2478 raise CycleError(f"Graph has no leafs. Thus, no topological sorting exists.")
2480 overallCount = len(outboundEdgeCounts) + len(leafVertices)
2482 def removeVertex(vertex: Vertex):
2483 """
2484 Nested function removing a vertex from the counting, and queuing the vertices that became leafs.
2486 :param vertex: The vertex that was just yielded.
2487 """
2488 nonlocal overallCount
2489 overallCount -= 1
2490 for inboundEdge in vertex._inboundEdges:
2491 sourceVertex = inboundEdge.Source
2492 count = outboundEdgeCounts[sourceVertex] - 1
2493 outboundEdgeCounts[sourceVertex] = count
2494 if count == 0:
2495 leafVertices.append(sourceVertex)
2497 if predicate is None:
2498 for vertex in leafVertices:
2499 yield vertex
2501 removeVertex(vertex)
2502 else:
2503 for vertex in leafVertices:
2504 if predicate(vertex):
2505 yield vertex
2507 removeVertex(vertex)
2509 if overallCount == 0: 2509 ↛ 2511line 2509 didn't jump to line 2511 because the condition on line 2509 was always true
2510 return
2511 elif overallCount > 0:
2512 raise CycleError(f"Graph has remaining vertices. Thus, the graph has at least one cycle.")
2514 raise InternalError(f"Graph data structure is corrupted.") # pragma: no cover
2516 def IterateEdges(self, predicate: Nullable[Callable[[Edge], bool]] = None) -> Generator[Edge[EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType], None, None]:
2517 """
2518 Iterate all or selected edges of a graph.
2520 If parameter ``predicate`` is not None, the given filter function is used to skip edges in the generator.
2522 :param predicate: Optional, filter function accepting any edge and returning a boolean.
2523 :returns: A generator to iterate all edges.
2524 """
2525 if predicate is None:
2526 yield from self._edgesWithoutID
2527 yield from self._edgesWithID.values()
2529 else:
2530 for edge in self._edgesWithoutID:
2531 if predicate(edge):
2532 yield edge
2534 for edge in self._edgesWithID.values():
2535 if predicate(edge):
2536 yield edge
2538 def IterateLinks(self, predicate: Nullable[Callable[[Link], bool]] = None) -> Generator[Link[LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType], None, None]:
2539 """
2540 Iterate all or selected links of a graph.
2542 If parameter ``predicate`` is not None, the given filter function is used to skip links in the generator.
2544 :param predicate: Optional, filter function accepting any link and returning a boolean.
2545 :returns: A generator to iterate all links.
2546 """
2547 if predicate is None: 2547 ↛ 2552line 2547 didn't jump to line 2552 because the condition on line 2547 was always true
2548 yield from self._linksWithoutID
2549 yield from self._linksWithID.values()
2551 else:
2552 for link in self._linksWithoutID:
2553 if predicate(link):
2554 yield link
2556 for link in self._linksWithID.values():
2557 if predicate(link):
2558 yield link
2560 def ReverseEdges(self, predicate: Nullable[Callable[[Edge], bool]] = None) -> None:
2561 """
2562 Reverse all or selected edges of a graph.
2564 If parameter ``predicate`` is not None, the given filter function is used to skip edges.
2566 :param predicate: Optional, filter function accepting any edge and returning a boolean.
2567 """
2568 if predicate is None:
2569 for edge in self._edgesWithoutID:
2570 swap = edge._source
2571 edge._source = edge._destination
2572 edge._destination = swap
2574 for edge in self._edgesWithID.values():
2575 swap = edge._source
2576 edge._source = edge._destination
2577 edge._destination = swap
2579 for vertex in self._verticesWithoutID:
2580 swap = vertex._inboundEdges
2581 vertex._inboundEdges = vertex._outboundEdges
2582 vertex._outboundEdges = swap
2584 for vertex in self._verticesWithID.values():
2585 swap = vertex._inboundEdges
2586 vertex._inboundEdges = vertex._outboundEdges
2587 vertex._outboundEdges = swap
2588 else:
2589 for edge in self._edgesWithoutID:
2590 if predicate(edge):
2591 edge.Reverse()
2593 for edge in self._edgesWithID.values():
2594 if predicate(edge):
2595 edge.Reverse()
2597 def ReverseLinks(self, predicate: Nullable[Callable[[Link], bool]] = None) -> None:
2598 """
2599 Reverse all or selected links of a graph.
2601 If parameter ``predicate`` is not None, the given filter function is used to skip links.
2603 :param predicate: Optional, filter function accepting any link and returning a boolean.
2604 """
2605 if predicate is None:
2606 for link in self._linksWithoutID:
2607 swap = link._source
2608 link._source = link._destination
2609 link._destination = swap
2611 for link in self._linksWithID.values():
2612 swap = link._source
2613 link._source = link._destination
2614 link._destination = swap
2616 for vertex in self._verticesWithoutID:
2617 swap = vertex._inboundLinks
2618 vertex._inboundLinks = vertex._outboundLinks
2619 vertex._outboundLinks = swap
2621 for vertex in self._verticesWithID.values():
2622 swap = vertex._inboundLinks
2623 vertex._inboundLinks = vertex._outboundLinks
2624 vertex._outboundLinks = swap
2625 else:
2626 for link in self._linksWithoutID:
2627 if predicate(link):
2628 link.Reverse()
2630 for link in self._linksWithID.values():
2631 if predicate(link):
2632 link.Reverse()
2634 def RemoveEdges(self, predicate: Nullable[Callable[[Edge], bool]] = None) -> None:
2635 """
2636 Remove all or selected edges of a graph.
2638 If parameter ``predicate`` is not None, the given filter function is used to skip edges.
2640 :param predicate: Optional, filter function accepting any edge and returning a boolean.
2641 """
2642 if predicate is None:
2643 for edge in self._edgesWithoutID:
2644 edge._Delete()
2646 for edge in self._edgesWithID.values():
2647 edge._Delete()
2649 self._edgesWithoutID = []
2650 self._edgesWithID = {}
2652 for vertex in self._verticesWithoutID:
2653 vertex._inboundEdges = []
2654 vertex._outboundEdges = []
2656 for vertex in self._verticesWithID.values():
2657 vertex._inboundEdges = []
2658 vertex._outboundEdges = []
2660 else:
2661 delEdges = [edge for edge in self._edgesWithID.values() if predicate(edge)]
2662 for edge in delEdges:
2663 del self._edgesWithID[edge._id]
2665 edge._source._outboundEdges.remove(edge)
2666 edge._destination._inboundEdges.remove(edge)
2667 edge._Delete()
2669 for edge in self._edgesWithoutID:
2670 if predicate(edge):
2671 self._edgesWithoutID.remove(edge)
2673 edge._source._outboundEdges.remove(edge)
2674 edge._destination._inboundEdges.remove(edge)
2675 edge._Delete()
2677 def RemoveLinks(self, predicate: Nullable[Callable[[Link], bool]] = None) -> None:
2678 """
2679 Remove all or selected links of a graph.
2681 If parameter ``predicate`` is not None, the given filter function is used to skip links.
2683 :param predicate: Optional, filter function accepting any link and returning a boolean.
2684 """
2685 if predicate is None:
2686 for link in self._linksWithoutID:
2687 link._Delete()
2689 for link in self._linksWithID.values():
2690 link._Delete()
2692 self._linksWithoutID = []
2693 self._linksWithID = {}
2695 for vertex in self._verticesWithoutID:
2696 vertex._inboundLinks = []
2697 vertex._outboundLinks = []
2699 for vertex in self._verticesWithID.values():
2700 vertex._inboundLinks = []
2701 vertex._outboundLinks = []
2703 else:
2704 delLinks = [link for link in self._linksWithID.values() if predicate(link)]
2705 for link in delLinks:
2706 del self._linksWithID[link._id]
2708 link._source._outboundLinks.remove(link)
2709 link._destination._inboundLinks.remove(link)
2710 link._Delete()
2712 for link in self._linksWithoutID:
2713 if predicate(link):
2714 self._linksWithoutID.remove(link)
2716 link._source._outboundLinks.remove(link)
2717 link._destination._inboundLinks.remove(link)
2718 link._Delete()
2720 def HasCycle(self) -> bool:
2721 """
2722 Check if the graph contains at least one cycle.
2724 The graph is traversed depth-first from every unvisited vertex; a vertex reached again while it is still on the
2725 current path closes a cycle.
2727 :returns: ``True``, if the graph contains a cycle.
2728 :raises InternalError: If the graph's data structure is corrupted.
2729 """
2730 # IsAcyclic ?
2732 # Handle trivial case if graph is empty
2733 if len(self._verticesWithID) + len(self._verticesWithoutID) == 0: 2733 ↛ 2734line 2733 didn't jump to line 2734 because the condition on line 2733 was never true
2734 return False
2736 outboundEdgeCounts = {}
2737 leafVertices = []
2739 for vertex in self._verticesWithoutID:
2740 if (count := len(vertex._outboundEdges)) == 0:
2741 leafVertices.append(vertex)
2742 else:
2743 outboundEdgeCounts[vertex] = count
2745 for vertex in self._verticesWithID.values():
2746 if (count := len(vertex._outboundEdges)) == 0:
2747 leafVertices.append(vertex)
2748 else:
2749 outboundEdgeCounts[vertex] = count
2751 # If there are no leafs, then each vertex has at least one inbound and one outbound edges. Thus, there is a cycle.
2752 if not leafVertices: 2752 ↛ 2753line 2752 didn't jump to line 2753 because the condition on line 2752 was never true
2753 return True
2755 overallCount = len(outboundEdgeCounts) + len(leafVertices)
2757 for vertex in leafVertices:
2758 overallCount -= 1
2759 for inboundEdge in vertex._inboundEdges:
2760 sourceVertex = inboundEdge.Source
2761 count = outboundEdgeCounts[sourceVertex] - 1
2762 outboundEdgeCounts[sourceVertex] = count
2763 if count == 0:
2764 leafVertices.append(sourceVertex)
2766 # If all vertices were processed, no cycle exists.
2767 if overallCount == 0:
2768 return False
2769 # If there are remaining vertices, then a cycle exists.
2770 elif overallCount > 0:
2771 return True
2773 raise InternalError(f"Graph data structure is corrupted.") # pragma: no cover
2776@export
2777class Subgraph(
2778 BaseGraph[
2779 SubgraphDictKeyType, SubgraphDictValueType,
2780 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,
2781 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,
2782 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType
2783 ],
2784 Generic[
2785 SubgraphDictKeyType, SubgraphDictValueType,
2786 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,
2787 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,
2788 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType
2789 ]
2790):
2791 """
2792 .. todo:: GRAPH::Subgraph Needs documentation.
2794 """
2796 _graph: Graph #: Reference to the graph this subgraph is part of.
2798 def __init__(
2799 self,
2800 graph: Graph,
2801 name: Nullable[str] = None,
2802 # vertices: Nullable[Iterable[Vertex]] = None,
2803 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None
2804 ) -> None:
2805 """
2806 Initialize a subgraph and register it at its graph.
2808 :param graph: Optional, the reference to the graph.
2809 :param name: Optional, name of the new sub-graph.
2810 :param keyValuePairs: Optional, mapping (dictionary) of key-value-pairs.
2811 :raises ValueError: If parameter 'graph' is None.
2812 :raises TypeError: If parameter 'graph' is not of type :class:`Graph`.
2813 """
2814 if graph is None: 2814 ↛ 2815line 2814 didn't jump to line 2815 because the condition on line 2814 was never true
2815 raise ValueError("Parameter 'graph' is None.")
2816 if not isinstance(graph, Graph): 2816 ↛ 2817line 2816 didn't jump to line 2817 because the condition on line 2816 was never true
2817 ex = TypeError("Parameter 'graph' is not of type 'Graph'.")
2818 ex.add_note(f"Got type '{getFullyQualifiedName(graph)}'.")
2819 raise ex
2821 super().__init__(name, keyValuePairs)
2823 graph._subgraphs.add(self)
2825 self._graph = graph
2827 def __del__(self) -> None:
2828 """
2829 .. todo:: GRAPH::Subgraph::del Needs documentation.
2831 """
2832 super().__del__()
2834 @readonly
2835 def Graph(self) -> Graph:
2836 """
2837 Read-only property to access the graph, this subgraph is associated to (:attr:`_graph`).
2839 :returns: The graph this subgraph is associated to.
2840 """
2841 return self._graph
2843 def __str__(self) -> str:
2844 """
2845 Return a string representation of this subgraph.
2847 :returns: The subgraph's name, or ``"Unnamed subgraph"`` if it has none.
2848 """
2849 return self._name if self._name is not None else "Unnamed subgraph"
2852@export
2853class View(
2854 BaseWithVertices[
2855 ViewDictKeyType, ViewDictValueType,
2856 GraphDictKeyType, GraphDictValueType,
2857 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,
2858 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,
2859 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType
2860 ],
2861 Generic[
2862 ViewDictKeyType, ViewDictValueType,
2863 GraphDictKeyType, GraphDictValueType,
2864 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,
2865 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,
2866 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType
2867 ]
2868):
2869 """
2870 .. todo:: GRAPH::View Needs documentation.
2872 """
2874 def __init__(
2875 self,
2876 graph: Graph,
2877 name: Nullable[str] = None,
2878 vertices: Nullable[Iterable[Vertex]] = None,
2879 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None
2880 ) -> None:
2881 """
2882 .. todo:: GRAPH::View::init Needs documentation.
2884 :param graph: Optional, the reference to the graph.
2885 :param name: Optional, name of the new view.
2886 :param vertices: Optional, list of vertices in the new view.
2887 :param keyValuePairs: Optional, mapping (dictionary) of key-value-pairs.
2888 """
2889 super().__init__(graph, name, vertices, keyValuePairs)
2891 graph._views.add(self)
2893 def __del__(self) -> None:
2894 """
2895 .. todo:: GRAPH::View::del Needs documentation.
2897 """
2898 super().__del__()
2900 def __str__(self) -> str:
2901 """
2902 Return a string representation of this view.
2904 :returns: The view's name, or ``"Unnamed view"`` if it has none.
2905 """
2906 return self._name if self._name is not None else "Unnamed view"
2909@export
2910class Component(
2911 BaseWithVertices[
2912 ComponentDictKeyType, ComponentDictValueType,
2913 GraphDictKeyType, GraphDictValueType,
2914 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,
2915 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,
2916 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType
2917 ],
2918 Generic[
2919 ComponentDictKeyType, ComponentDictValueType,
2920 GraphDictKeyType, GraphDictValueType,
2921 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,
2922 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,
2923 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType
2924 ]
2925):
2926 """
2927 .. todo:: GRAPH::Component Needs documentation.
2929 """
2931 def __init__(
2932 self,
2933 graph: Graph,
2934 name: Nullable[str] = None,
2935 vertices: Nullable[Iterable[Vertex]] = None,
2936 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None
2937 ) -> None:
2938 """
2939 Initialize a component of a graph and register it at that graph.
2941 :param graph: Optional, the reference to the graph.
2942 :param name: Optional, name of the new component.
2943 :param vertices: Optional, list of vertices in the new component.
2944 :param keyValuePairs: Optional, mapping (dictionary) of key-value-pairs.
2945 """
2946 super().__init__(graph, name, vertices, keyValuePairs)
2948 graph._components.add(self)
2950 def __del__(self) -> None:
2951 """
2952 .. todo:: GRAPH::Component::del Needs documentation.
2954 """
2955 super().__del__()
2957 def __str__(self) -> str:
2958 """
2959 Return a string representation of this component.
2961 :returns: The component's name, or ``"Unnamed component"`` if it has none.
2962 """
2963 return self._name if self._name is not None else "Unnamed component"
2966@export
2967class Graph(
2968 BaseGraph[
2969 GraphDictKeyType, GraphDictValueType,
2970 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,
2971 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,
2972 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType
2973 ],
2974 Generic[
2975 GraphDictKeyType, GraphDictValueType,
2976 ComponentDictKeyType, ComponentDictValueType,
2977 SubgraphDictKeyType, SubgraphDictValueType,
2978 ViewDictKeyType, ViewDictValueType,
2979 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,
2980 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,
2981 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType
2982 ]
2983):
2984 """
2985 A **graph** data structure is represented by an instance of :class:`~pyTooling.Graph.Graph` holding references to
2986 all nodes. Nodes are instances of :class:`~pyTooling.Graph.Vertex` classes and directed links between nodes are
2987 made of :class:`~pyTooling.Graph.Edge` instances. A graph can have attached meta information as key-value-pairs.
2988 """
2989 _subgraphs: set[Subgraph[SubgraphDictKeyType, SubgraphDictValueType, VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType, EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType, LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType]] #: Subgraphs of this graph.
2990 _views: set[View[ViewDictKeyType, ViewDictValueType, GraphDictKeyType, GraphDictValueType, VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType, EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType, LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType]] #: Views defined on this graph.
2991 _components: set[Component[ComponentDictKeyType, ComponentDictValueType, GraphDictKeyType, GraphDictValueType, VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType, EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType, LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType]] #: Connected components of this graph.
2993 def __init__(
2994 self,
2995 name: Nullable[str] = None,
2996 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None
2997 ) -> None:
2998 """
2999 .. todo:: GRAPH::Graph::init Needs documentation.
3001 :param name: Optional, name of the new graph.
3002 :param keyValuePairs: Optional, mapping (dictionary) of key-value-pairs.#
3003 """
3004 super().__init__(name, keyValuePairs)
3006 self._subgraphs = set()
3007 self._views = set()
3008 self._components = set()
3010 def __del__(self) -> None:
3011 """
3012 .. todo:: GRAPH::Graph::del Needs documentation.
3014 """
3015 try:
3016 del self._subgraphs
3017 del self._views
3018 del self._components
3019 except AttributeError:
3020 pass
3022 super().__del__()
3024 @readonly
3025 def Subgraphs(self) -> set[Subgraph]:
3026 """Read-only property to access the subgraphs in this graph (:attr:`_subgraphs`).
3028 :returns: The set of subgraphs in this graph."""
3029 return self._subgraphs
3031 @readonly
3032 def Views(self) -> set[View]:
3033 """Read-only property to access the views in this graph (:attr:`_views`).
3035 :returns: The set of views in this graph."""
3036 return self._views
3038 @readonly
3039 def Components(self) -> set[Component]:
3040 """Read-only property to access the components in this graph (:attr:`_components`).
3042 :returns: The set of components in this graph."""
3043 return self._components
3045 @readonly
3046 def SubgraphCount(self) -> int:
3047 """Read-only property to return the number of subgraphs in this graph.
3049 :returns: The number of subgraphs in this graph."""
3050 return len(self._subgraphs)
3052 @readonly
3053 def ViewCount(self) -> int:
3054 """Read-only property to return the number of views in this graph.
3056 :returns: The number of views in this graph."""
3057 return len(self._views)
3059 @readonly
3060 def ComponentCount(self) -> int:
3061 """Read-only property to return the number of components in this graph.
3063 :returns: The number of components in this graph."""
3064 return len(self._components)
3066 def __iter__(self) -> typing_Iterator[Vertex[GraphDictKeyType, GraphDictValueType, VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType, EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType, LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType]]:
3067 """
3068 Iterate all vertices of this graph.
3070 :returns: An iterator over the vertices without an ID, followed by those with one.
3071 """
3072 def gen():
3073 """
3074 Nested generator function chaining the vertices without an ID and those with one.
3076 :returns: A generator yielding every vertex of the graph.
3077 """
3078 yield from self._verticesWithoutID
3079 yield from self._verticesWithID
3080 return iter(gen())
3082 def HasVertexByID(self, vertexID: Nullable[VertexIDType]) -> bool:
3083 """
3084 Check if a vertex with the given ID exists in this graph.
3086 :param vertexID: Optional, ID to look for, or ``None`` for a vertex without an ID.
3087 :returns: ``True``, if such a vertex exists.
3088 """
3089 if vertexID is None:
3090 return len(self._verticesWithoutID) >= 1
3091 else:
3092 return vertexID in self._verticesWithID
3094 def HasVertexByValue(self, value: Nullable[VertexValueType]) -> bool:
3095 """
3096 Check if a vertex carrying the given value exists in this graph.
3098 :param value: Optional, value to look for.
3099 :returns: ``True``, if such a vertex exists.
3100 """
3101 return any(vertex._value == value for vertex in chain(self._verticesWithoutID, self._verticesWithID.values()))
3103 def GetVertexByID(self, vertexID: Nullable[VertexIDType]) -> Vertex:
3104 """
3105 Return the vertex with the given ID.
3107 A vertex created without an ID can be looked up with ``None``, provided it is the only such vertex.
3109 :param vertexID: Optional, ID of the vertex to return, or ``None`` for the vertex without an ID.
3110 :returns: The vertex with that ID.
3111 :raises KeyError: If no vertex has that ID, or if more than one vertex matches ``None``.
3112 """
3113 if vertexID is None:
3114 if (l := len(self._verticesWithoutID)) == 1:
3115 return self._verticesWithoutID[0]
3116 elif l == 0:
3117 raise KeyError(f"Found no vertex with ID `None`.")
3118 else:
3119 raise KeyError(f"Found multiple vertices with ID `None`.")
3120 else:
3121 return self._verticesWithID[vertexID]
3123 def GetVertexByValue(self, value: Nullable[VertexValueType]) -> Vertex:
3124 """
3125 Return the vertex carrying the given value.
3127 :param value: Optional, value of the vertex to return.
3128 :returns: The vertex with that value.
3129 :raises KeyError: If no vertex carries that value, or if more than one vertex does.
3130 """
3131 # FIXME: optimize: iterate only until first item is found and check for a second to produce error
3132 vertices = [vertex for vertex in chain(self._verticesWithoutID, self._verticesWithID.values()) if vertex._value == value]
3133 if (l := len(vertices)) == 1:
3134 return vertices[0]
3135 elif l == 0:
3136 raise KeyError(f"Found no vertex with Value == `{value}`.")
3137 else:
3138 raise KeyError(f"Found multiple vertices with Value == `{value}`.")
3140 def CopyGraph(self) -> Graph:
3141 """
3142 Create a copy of this graph.
3144 :returns: A new graph with copies of this graph's vertices and edges.
3145 :raises NotImplementedError: Copying a whole graph is not implemented yet.
3146 """
3147 raise NotImplementedError()
3149 def CopyVertices(self, predicate: Nullable[Callable[[Vertex], bool]] = None, copyGraphDict: bool = True, copyVertexDict: bool = True) -> Graph:
3150 """
3151 Create a new graph and copy all or selected vertices of the original graph.
3153 If parameter ``predicate`` is not None, the given filter function is used to skip vertices.
3155 :param predicate: Optional, filter function accepting any vertex and returning a boolean.
3156 :param copyGraphDict: Optional, if ``True``, copy all graph attached attributes into the new graph.
3157 :param copyVertexDict: Optional, if ``True``, copy all vertex attached attributes into the new vertices.
3158 :returns: A new graph with copies of the selected vertices.
3159 """
3160 graph = Graph(self._name)
3161 if copyGraphDict:
3162 graph._dict = self._dict.copy()
3164 if predicate is None:
3165 for vertex in self._verticesWithoutID:
3166 v = Vertex(None, vertex._value, graph=graph)
3167 if copyVertexDict:
3168 v._dict = vertex._dict.copy()
3170 for vertexID, vertex in self._verticesWithID.items():
3171 v = Vertex(vertexID, vertex._value, graph=graph)
3172 if copyVertexDict:
3173 v._dict = vertex._dict.copy()
3174 else:
3175 for vertex in self._verticesWithoutID:
3176 if predicate(vertex):
3177 v = Vertex(None, vertex._value, graph=graph)
3178 if copyVertexDict: 3178 ↛ 3175line 3178 didn't jump to line 3175 because the condition on line 3178 was always true
3179 v._dict = vertex._dict.copy()
3181 for vertexID, vertex in self._verticesWithID.items():
3182 if predicate(vertex):
3183 v = Vertex(vertexID, vertex._value, graph=graph)
3184 if copyVertexDict: 3184 ↛ 3185line 3184 didn't jump to line 3185 because the condition on line 3184 was never true
3185 v._dict = vertex._dict.copy()
3187 return graph
3189 # class Iterator():
3190 # visited = [False for _ in range(self.__len__())]
3192 # def CheckForNegativeCycles(self):
3193 # raise NotImplementedError()
3194 # # Bellman-Ford
3195 # # Floyd-Warshall
3196 #
3197 # def IsStronglyConnected(self):
3198 # raise NotImplementedError()
3199 #
3200 # def GetStronglyConnectedComponents(self):
3201 # raise NotImplementedError()
3202 # # Tarjan's and Kosaraju's algorithm
3203 #
3204 # def TravelingSalesmanProblem(self):
3205 # raise NotImplementedError()
3206 # # Held-Karp
3207 # # branch and bound
3208 #
3209 # def GetBridges(self):
3210 # raise NotImplementedError()
3211 #
3212 # def GetArticulationPoints(self):
3213 # raise NotImplementedError()
3214 #
3215 # def MinimumSpanningTree(self):
3216 # raise NotImplementedError()
3217 # # Kruskal
3218 # # Prim's algorithm
3219 # # Buruvka's algorithm
3221 def __repr__(self) -> str:
3222 """
3223 Return a detailed string representation of this graph.
3225 :returns: The graph's name and its vertex and edge counts.
3226 """
3227 statistics = f", vertices: {self.VertexCount}, edges: {self.EdgeCount}"
3228 if self._name is None:
3229 return f"<graph: unnamed graph{statistics}>"
3230 else:
3231 return f"<graph: '{self._name}'{statistics}>"
3233 def __str__(self) -> str:
3234 """
3235 Return a string representation of this graph.
3237 :returns: The graph's name, or ``"Unnamed graph"`` if it has none.
3238 """
3239 if self._name is None:
3240 return f"Graph: unnamed graph"
3241 else:
3242 return f"Graph: '{self._name}'"