Coverage for pyTooling/Graph/__init__.py: 79%
1259 statements
« prev ^ index » next coverage.py v7.16.1, created at 2026-09-21 19:41 +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 GraphError(ToolingException):
166 """Base exception of all exceptions raised by :mod:`pyTooling.Graph`."""
169@export
170class InternalError(GraphError):
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(GraphError):
185 """The exception is raised when creating an edge between two vertices, but these are not in the same graph."""
188@export
189class NotInDifferentSubgraphs(GraphError):
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(GraphError):
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(GraphError):
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(GraphError):
251 """The exception is raised when a destination vertex is not reachable."""
254@export
255class NotATreeError(GraphError):
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 EdgeNotFoundError(GraphError):
265 """The exception is raised when no edge matching the given source or destination vertex was found."""
268@export
269class LinkNotFoundError(GraphError):
270 """The exception is raised when no link matching the given source or destination vertex was found."""
273@export
274class SameGraphError(GraphError):
275 """The exception is raised when a vertex is copied into the graph it already belongs to."""
278@export
279class CycleError(GraphError):
280 """The exception is raised when a not permitted cycle is found."""
283@export
284class Base(
285 Generic[DictKeyType, DictValueType],
286 metaclass=ExtendedType, slots=True
287):
288 """
289 Base-class for all graph elements, adding a dictionary of arbitrary key-value-pairs to them.
291 Every vertex, edge, link, component, view, subgraph and graph can carry meta information this way.
292 """
294 _dict: dict[DictKeyType, DictValueType] #: A dictionary to store arbitrary key-value-pairs.
296 def __init__(
297 self,
298 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None
299 ) -> None:
300 """
301 .. todo:: GRAPH::Base::init Needs documentation.
303 :param keyValuePairs: Optional, mapping (dictionary) of key-value-pairs.
304 :raises TypeError: If parameter 'name' is not of type string.
305 """
306 self._dict = {key: value for key, value in keyValuePairs.items()} if keyValuePairs is not None else {}
308 def __del__(self) -> None:
309 """
310 .. todo:: GRAPH::Base::del Needs documentation.
311 """
312 try:
313 del self._dict
314 except AttributeError:
315 pass
317 def Delete(self) -> None:
318 """
319 Remove this element's attached attributes from internal dictionary.
320 """
321 self._dict.clear()
323 def __getitem__(self, key: DictKeyType) -> DictValueType:
324 """
325 Read a vertex's attached attributes (key-value-pairs) by key.
327 :param key: The key to look for.
328 :returns: The value associated to the given key.
329 """
330 return self._dict[key]
332 def __setitem__(self, key: DictKeyType, value: DictValueType) -> None:
333 """
334 Create or update a vertex's attached attributes (key-value-pairs) by key.
336 If a key doesn't exist yet, a new key-value-pair is created.
338 :param key: The key to create or update.
339 :param value: Optional, the value to associate to the given key.
340 """
341 self._dict[key] = value
343 def __delitem__(self, key: DictKeyType) -> None:
344 """
345 Remove an entry from vertex's attached attributes (key-value-pairs) by key.
347 :param key: The key to remove.
348 :raises KeyError: If key doesn't exist in the vertex's attributes.
349 """
350 del self._dict[key]
352 def __contains__(self, key: DictKeyType) -> bool:
353 """
354 Checks if the key is an attached attribute (key-value-pairs) on this vertex.
356 :param key: The key to check.
357 :returns: ``True``, if the key is an attached attribute.
358 """
359 return key in self._dict
361 def __len__(self) -> int:
362 """
363 Returns the number of attached attributes (key-value-pairs) on this vertex.
365 :returns: Number of attached attributes.
366 """
367 return len(self._dict)
370@export
371class BaseWithIDValueAndWeight(
372 Base[DictKeyType, DictValueType],
373 Generic[IDType, ValueType, WeightType, DictKeyType, DictValueType]
374):
375 """
376 Base-class for graph elements identified by an ID and carrying a value and a weight - vertices, edges and links.
378 All three are optional: an element without an ID is still part of the graph, it just can't be looked up by ID.
379 """
381 _id: Nullable[IDType] #: Field storing the object's Identifier.
382 _value: Nullable[ValueType] #: Field storing the object's value of any type.
383 _weight: Nullable[WeightType] #: Field storing the object's weight.
385 def __init__(
386 self,
387 identifier: Nullable[IDType] = None,
388 value: Nullable[ValueType] = None,
389 weight: Nullable[WeightType] = None,
390 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None
391 ) -> None:
392 """
393 Initialize a graph element with an optional ID, value and weight.
395 :param identifier: Optional, unique ID.
396 :param value: Optional, value.
397 :param weight: Optional, weight.
398 :param keyValuePairs: Optional, mapping (dictionary) of key-value-pairs.
399 :raises TypeError: If parameter 'name' is not of type string.
400 """
401 super().__init__(keyValuePairs)
403 self._id = identifier
404 self._value = value
405 self._weight = weight
407 @readonly
408 def ID(self) -> Nullable[IDType]:
409 """
410 Read-only property to access the unique ID (:attr:`_id`).
412 If no ID was given at creation time, ID returns ``None``.
414 :returns: Unique ID, if ID was given at creation time, else ``None``.
415 """
416 return self._id
418 @property
419 def Value(self) -> ValueType:
420 """
421 Property to get and set the value (:attr:`_value`).
423 :returns: The value.
424 """
425 return self._value
427 @Value.setter
428 def Value(self, value: ValueType) -> None:
429 self._value = value
431 @property
432 def Weight(self) -> Nullable[EdgeWeightType]:
433 """
434 Property to get and set the weight (:attr:`_weight`) of an edge.
436 :returns: The weight of an edge.
437 """
438 return self._weight
440 @Weight.setter
441 def Weight(self, value: Nullable[EdgeWeightType]) -> None:
442 self._weight = value
445@export
446class BaseWithName(
447 Base[DictKeyType, DictValueType],
448 Generic[DictKeyType, DictValueType]
449):
450 """Base-class for named graph elements like a graph, a subgraph, a view or a component."""
452 _name: Nullable[str] #: Field storing the object's name.
454 def __init__(
455 self,
456 name: Nullable[str] = None,
457 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None,
458 ) -> None:
459 """
460 Initialize a named graph element with an optional name and optional key-value-pairs.
462 :param name: Optional, name.
463 :param keyValuePairs: Optional, mapping (dictionary) of key-value-pairs.
464 :raises ValueError: If parameter 'graph' is None.
465 :raises TypeError: If parameter 'graph' is not of type :class:`Graph`.
466 """
467 if name is not None and not isinstance(name, str):
468 ex = TypeError("Parameter 'name' is not of type 'str'.")
469 ex.add_note(f"Got type '{getFullyQualifiedName(name)}'.")
470 raise ex
472 super().__init__(keyValuePairs)
474 self._name = name
476 @property
477 def Name(self) -> Nullable[str]:
478 """
479 Property to access the name (:attr:`_name`).
481 :returns: The object's name, or ``None`` if it has none.
482 :raises TypeError: If an assigned value is not of type string.
483 """
484 return self._name
486 @Name.setter
487 def Name(self, value: str) -> None:
488 if not isinstance(value, str):
489 ex = TypeError("Name is not of type 'str'.")
490 ex.add_note(f"Got type '{getFullyQualifiedName(value)}'.")
491 raise ex
493 self._name = value
496@export
497class BaseWithVertices(
498 BaseWithName[DictKeyType, DictValueType],
499 Generic[
500 DictKeyType, DictValueType,
501 GraphDictKeyType, GraphDictValueType,
502 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,
503 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,
504 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType
505 ]
506):
507 """Base-class for named graph elements owning a set of vertices - a subgraph, a view or a component."""
509 _graph: Graph[
510 GraphDictKeyType, GraphDictValueType,
511 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,
512 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,
513 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType
514 ] #: Field storing a reference to the graph.
515 _vertices: set[Vertex[
516 GraphDictKeyType, GraphDictValueType,
517 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,
518 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,
519 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType
520 ]] #: Field storing a set of vertices.
522 def __init__(
523 self,
524 graph: Graph,
525 name: Nullable[str] = None,
526 vertices: Nullable[Iterable[Vertex]] = None,
527 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None
528 ) -> None:
529 """
530 Initialize a named graph element owning a set of vertices, and register it at its graph.
532 :param graph: Optional, the reference to the graph.
533 :param name: Optional, name.
534 :param vertices: Optional, list of vertices.
535 :param keyValuePairs: Optional, mapping (dictionary) of key-value-pairs.
536 :raises ValueError: If parameter 'graph' is None.
537 :raises TypeError: If parameter 'graph' is not of type :class:`Graph`.
538 """
539 if graph is None: 539 ↛ 540line 539 didn't jump to line 540 because the condition on line 539 was never true
540 raise ValueError("Parameter 'graph' is None.")
541 elif not isinstance(graph, Graph): 541 ↛ 542line 541 didn't jump to line 542 because the condition on line 541 was never true
542 ex = TypeError("Parameter 'graph' is not of type 'Graph'.")
543 ex.add_note(f"Got type '{getFullyQualifiedName(graph)}'.")
544 raise ex
546 super().__init__(name, keyValuePairs)
548 self._graph = graph
549 self._vertices = set() if vertices is None else {v for v in vertices}
551 def __del__(self) -> None:
552 """
553 .. todo:: GRAPH::BaseWithVertices::del Needs documentation.
554 """
555 try:
556 del self._vertices
557 except AttributeError:
558 pass
560 super().__del__()
562 @readonly
563 def Graph(self) -> Graph:
564 """
565 Read-only property to access the graph, this object is associated to (:attr:`_graph`).
567 :returns: The graph this object is associated to.
568 """
569 return self._graph
571 @readonly
572 def Vertices(self) -> set[Vertex]:
573 """
574 Read-only property to access the vertices in this component (:attr:`_vertices`).
576 :returns: The set of vertices in this component.
577 """
578 return self._vertices
580 @readonly
581 def VertexCount(self) -> int:
582 """
583 Read-only property to return the number of vertices referenced by this object.
585 :returns: The number of vertices this object references.
586 """
587 return len(self._vertices)
590@export
591class Vertex(
592 BaseWithIDValueAndWeight[VertexIDType, VertexValueType, VertexWeightType, VertexDictKeyType, VertexDictValueType],
593 Generic[
594 GraphDictKeyType, GraphDictValueType,
595 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,
596 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,
597 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType
598 ]
599):
600 """
601 A **vertex** can have a unique ID, a value and attached meta information as key-value-pairs. A vertex has references
602 to inbound and outbound edges, thus a graph can be traversed in reverse.
603 """
604 _graph: BaseGraph[GraphDictKeyType, GraphDictValueType, VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType, EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType] #: Field storing a reference to the graph.
605 _subgraph: Subgraph[GraphDictKeyType, GraphDictValueType, VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType, EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType] #: Field storing a reference to the subgraph.
606 _component: Component #: Field storing a reference to the component this vertex belongs to.
607 _views: dict[Hashable, View] #: Field storing the views this vertex is part of, by view name.
608 _inboundEdges: list[Edge[EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType]] #: Field storing a list of inbound edges.
609 _outboundEdges: list[Edge[EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType]] #: Field storing a list of outbound edges.
610 _inboundLinks: list[Link[EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType]] #: Field storing a list of inbound links.
611 _outboundLinks: list[Link[EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType]] #: Field storing a list of outbound links.
613 def __init__(
614 self,
615 vertexID: Nullable[VertexIDType] = None,
616 value: Nullable[VertexValueType] = None,
617 weight: Nullable[VertexWeightType] = None,
618 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None,
619 graph: Nullable[Graph] = None,
620 subgraph: Nullable[Subgraph] = None
621 ) -> None:
622 """
623 Initialize a vertex and register it at its graph or subgraph.
625 :param vertexID: Optional, ID for the new vertex.
626 :param value: Optional, value for the new vertex.
627 :param weight: Optional, weight for the new vertex.
628 :param keyValuePairs: Optional, mapping (dictionary) of key-value-pairs.
629 :param graph: Optional, reference to the graph.
630 :param subgraph: Optional, undocumented
631 :raises TypeError: If parameter 'vertexID' is not of the graph's vertex ID type.
632 :raises DuplicateVertexError: If the given vertex ID already exists in this graph or subgraph.
633 """
634 if vertexID is not None and not isinstance(vertexID, Hashable): 634 ↛ 635line 634 didn't jump to line 635 because the condition on line 634 was never true
635 ex = TypeError("Parameter 'vertexID' is not of type 'VertexIDType'.")
636 ex.add_note(f"Got type '{getFullyQualifiedName(vertexID)}'.")
637 raise ex
639 super().__init__(vertexID, value, weight, keyValuePairs)
641 if subgraph is None:
642 self._graph = graph if graph is not None else Graph()
643 self._subgraph = None
644 self._component = Component(self._graph, vertices=(self,))
646 if vertexID is None:
647 self._graph._verticesWithoutID.append(self)
648 elif vertexID not in self._graph._verticesWithID:
649 self._graph._verticesWithID[vertexID] = self
650 else:
651 raise DuplicateVertexError(f"Vertex ID '{vertexID}' already exists in this graph.", vertexID=vertexID)
652 else:
653 self._graph = subgraph._graph
654 self._subgraph = subgraph
655 self._component = Component(self._graph, vertices=(self,))
657 if vertexID is None:
658 subgraph._verticesWithoutID.append(self)
659 elif vertexID not in subgraph._verticesWithID: 659 ↛ 662line 659 didn't jump to line 662 because the condition on line 659 was always true
660 subgraph._verticesWithID[vertexID] = self
661 else:
662 raise DuplicateVertexError(f"Vertex ID '{vertexID}' already exists in this subgraph.", vertexID=vertexID)
664 self._views = {}
665 self._inboundEdges = []
666 self._outboundEdges = []
667 self._inboundLinks = []
668 self._outboundLinks = []
670 def __del__(self) -> None:
671 """
672 .. todo:: GRAPH::BaseEdge::del Needs documentation.
673 """
674 try:
675 del self._views
676 del self._inboundEdges
677 del self._outboundEdges
678 del self._inboundLinks
679 del self._outboundLinks
680 except AttributeError:
681 pass
683 super().__del__()
685 def Delete(self) -> None:
686 """
687 Delete this vertex and every edge and link connected to it.
689 The vertex is removed from its graph or subgraph, and from its views; every connected edge and link is removed
690 from its other vertex and unregistered from the graph or subgraph it was registered on.
691 """
692 for edge in self._outboundEdges:
693 edge._destination._inboundEdges.remove(edge)
694 edge._Unregister()
695 edge._Delete()
696 for edge in self._inboundEdges:
697 edge._source._outboundEdges.remove(edge)
698 edge._Unregister()
699 edge._Delete()
700 for link in self._outboundLinks:
701 link._destination._inboundLinks.remove(link)
702 link._Unregister()
703 link._Delete()
704 for link in self._inboundLinks: 704 ↛ 705line 704 didn't jump to line 705 because the loop on line 704 never started
705 link._source._outboundLinks.remove(link)
706 link._Unregister()
707 link._Delete()
709 # Remove from Graph or Subgraph - a vertex is registered on the subgraph it lives in, otherwise on the graph.
710 container = self._graph if self._subgraph is None else self._subgraph
711 if self._id is None:
712 container._verticesWithoutID.remove(self)
713 else:
714 del container._verticesWithID[self._id]
716 # component
718 # views
719 self._views.clear()
720 self._inboundEdges.clear()
721 self._outboundEdges.clear()
722 self._inboundLinks.clear()
723 self._outboundLinks.clear()
725 super().Delete()
727 @readonly
728 def Graph(self) -> Graph:
729 """
730 Read-only property to access the graph, this vertex is associated to (:attr:`_graph`).
732 :returns: The graph this vertex is associated to.
733 """
734 return self._graph
736 @readonly
737 def Component(self) -> Component:
738 """
739 Read-only property to access the component, this vertex is associated to (:attr:`_component`).
741 :returns: The component this vertex is associated to.
742 """
743 return self._component
745 @readonly
746 def InboundEdges(self) -> tuple[Edge, ...]:
747 """
748 Read-only property to get a tuple of inbound edges (:attr:`_inboundEdges`).
750 :returns: Tuple of inbound edges.
751 """
752 return tuple(self._inboundEdges)
754 @readonly
755 def OutboundEdges(self) -> tuple[Edge, ...]:
756 """
757 Read-only property to get a tuple of outbound edges (:attr:`_outboundEdges`).
759 :returns: Tuple of outbound edges.
760 """
761 return tuple(self._outboundEdges)
763 @readonly
764 def InboundLinks(self) -> tuple[Link, ...]:
765 """
766 Read-only property to get a tuple of inbound links (:attr:`_inboundLinks`).
768 :returns: Tuple of inbound links.
769 """
770 return tuple(self._inboundLinks)
772 @readonly
773 def OutboundLinks(self) -> tuple[Link, ...]:
774 """
775 Read-only property to get a tuple of outbound links (:attr:`_outboundLinks`).
777 :returns: Tuple of outbound links.
778 """
779 return tuple(self._outboundLinks)
781 @readonly
782 def EdgeCount(self) -> int:
783 """
784 Read-only property to get the number of all edges (inbound and outbound).
786 :returns: Number of inbound and outbound edges.
787 """
788 return len(self._inboundEdges) + len(self._outboundEdges)
790 @readonly
791 def InboundEdgeCount(self) -> int:
792 """
793 Read-only property to get the number of inbound edges.
795 :returns: Number of inbound edges.
796 """
797 return len(self._inboundEdges)
799 @readonly
800 def OutboundEdgeCount(self) -> int:
801 """
802 Read-only property to get the number of outbound edges.
804 :returns: Number of outbound edges.
805 """
806 return len(self._outboundEdges)
808 @readonly
809 def LinkCount(self) -> int:
810 """
811 Read-only property to get the number of all links (inbound and outbound).
813 :returns: Number of inbound and outbound links.
814 """
815 return len(self._inboundLinks) + len(self._outboundLinks)
817 @readonly
818 def InboundLinkCount(self) -> int:
819 """
820 Read-only property to get the number of inbound links.
822 :returns: Number of inbound links.
823 """
824 return len(self._inboundLinks)
826 @readonly
827 def OutboundLinkCount(self) -> int:
828 """
829 Read-only property to get the number of outbound links.
831 :returns: Number of outbound links.
832 """
833 return len(self._outboundLinks)
835 @readonly
836 def IsRoot(self) -> bool:
837 """
838 Read-only property to check if this vertex is a root vertex in the graph.
840 A root has no inbound edges (no predecessor vertices).
842 :returns: ``True``, if this vertex is a root.
844 .. seealso::
846 :meth:`Vertex.IsLeaf <pyTooling.Graph.Vertex.IsLeaf>`
847 |rarr| Check if a vertex is a leaf vertex in the graph.
848 :meth:`BaseGraph.IterateRoots <pyTooling.Graph.BaseGraph.IterateRoots>`
849 |rarr| Iterate all roots of a graph.
850 :meth:`BaseGraph.IterateLeafs <pyTooling.Graph.BaseGraph.IterateLeafs>`
851 |rarr| Iterate all leafs of a graph.
852 """
853 return len(self._inboundEdges) == 0
855 @readonly
856 def IsLeaf(self) -> bool:
857 """
858 Read-only property to check if this vertex is a leaf vertex in the graph.
860 A leaf has no outbound edges (no successor vertices).
862 :returns: ``True``, if this vertex is a leaf.
864 .. seealso::
866 :meth:`Vertex.IsRoot <pyTooling.Graph.Vertex.IsRoot>`
867 |rarr| Check if a vertex is a root vertex in the graph.
868 :meth:`BaseGraph.IterateRoots <pyTooling.Graph.BaseGraph.IterateRoots>`
869 |rarr| Iterate all roots of a graph.
870 :meth:`BaseGraph.IterateLeafs <pyTooling.Graph.BaseGraph.IterateLeafs>`
871 |rarr| Iterate all leafs of a graph.
872 """
873 return len(self._outboundEdges) == 0
875 @readonly
876 def Predecessors(self) -> tuple[Vertex, ...]:
877 """
878 Read-only property to get a tuple of predecessor vertices.
880 :returns: Tuple of predecessor vertices.
881 """
882 return tuple([edge.Source for edge in self._inboundEdges])
884 @readonly
885 def Successors(self) -> tuple[Vertex, ...]:
886 """
887 Read-only property to get a tuple of successor vertices.
889 :returns: Tuple of successor vertices.
890 """
891 return tuple([edge.Destination for edge in self._outboundEdges])
893 def EdgeToVertex(
894 self,
895 vertex: Vertex,
896 edgeID: Nullable[EdgeIDType] = None,
897 edgeWeight: Nullable[EdgeWeightType] = None,
898 edgeValue: Nullable[VertexValueType] = None,
899 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None
900 ) -> Edge:
901 """
902 Create an outbound edge from this vertex to the referenced vertex.
904 :param vertex: The vertex to be linked to.
905 :param edgeID: Optional, the edge's optional ID for the new edge object.
906 :param edgeWeight: Optional, the edge's optional weight for the new edge object.
907 :param edgeValue: Optional, the edge's optional value for the new edge object.
908 :param keyValuePairs: Optional, mapping (dictionary) of key-value-pairs for the new edge object.
909 :returns: The edge object linking this vertex and the referenced vertex.
910 :raises DuplicateEdgeError: If the given edge ID already exists in this graph or subgraph.
911 :raises NotInSameGraph: If both vertices are not in the same graph or subgraph. |br|
912 Use :meth:`LinkToVertex` or :meth:`LinkFromVertex` to connect vertices across
913 subgraph boundaries.
915 .. seealso::
917 :meth:`EdgeFromVertex`
918 |rarr| Create an inbound edge from the referenced vertex to this vertex.
919 :meth:`EdgeToNewVertex`
920 |rarr| Create a new vertex and link that vertex by an outbound edge from this vertex.
921 :meth:`EdgeFromNewVertex`
922 |rarr| Create a new vertex and link that vertex by an inbound edge to this vertex.
923 :meth:`LinkToVertex`
924 |rarr| Create an outbound link from this vertex to the referenced vertex.
925 :meth:`LinkFromVertex`
926 |rarr| Create an inbound link from the referenced vertex to this vertex.
927 """
928 if self._subgraph is vertex._subgraph:
929 edge = Edge(self, vertex, edgeID, edgeValue, edgeWeight, keyValuePairs)
931 self._outboundEdges.append(edge)
932 vertex._inboundEdges.append(edge)
934 if self._subgraph is None:
935 # TODO: move into Edge?
936 # TODO: keep _graph pointer in edge and then register edge on graph?
937 if edgeID is None:
938 self._graph._edgesWithoutID.append(edge)
939 elif edgeID not in self._graph._edgesWithID:
940 self._graph._edgesWithID[edgeID] = edge
941 else:
942 raise DuplicateEdgeError(f"Edge ID '{edgeID}' already exists in this graph.", edgeID=edgeID)
943 else:
944 # TODO: keep _graph pointer in edge and then register edge on graph?
945 if edgeID is None:
946 self._subgraph._edgesWithoutID.append(edge)
947 elif edgeID not in self._subgraph._edgesWithID:
948 self._subgraph._edgesWithID[edgeID] = edge
949 else:
950 raise DuplicateEdgeError(f"Edge ID '{edgeID}' already exists in this subgraph.", edgeID=edgeID)
951 else:
952 ex = NotInSameGraph(f"Vertex {self!r} and vertex {vertex!r} are not in the same graph or subgraph.")
953 ex.add_note("An edge can only connect vertices within the same graph or subgraph.")
954 ex.add_note("Use LinkToVertex or LinkFromVertex to connect vertices across subgraph boundaries.")
955 raise ex
957 return edge
959 def EdgeFromVertex(
960 self,
961 vertex: Vertex,
962 edgeID: Nullable[EdgeIDType] = None,
963 edgeWeight: Nullable[EdgeWeightType] = None,
964 edgeValue: Nullable[VertexValueType] = None,
965 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None
966 ) -> Edge:
967 """
968 Create an inbound edge from the referenced vertex to this vertex.
970 :param vertex: The vertex to be linked from.
971 :param edgeID: Optional, the edge's optional ID for the new edge object.
972 :param edgeWeight: Optional, the edge's optional weight for the new edge object.
973 :param edgeValue: Optional, the edge's optional value for the new edge object.
974 :param keyValuePairs: Optional, mapping (dictionary) of key-value-pairs for the new edge object.
975 :returns: The edge object linking the referenced vertex and this vertex.
976 :raises DuplicateEdgeError: If the given edge ID already exists in this graph or subgraph.
977 :raises NotInSameGraph: If both vertices are not in the same graph or subgraph. |br|
978 Use :meth:`LinkToVertex` or :meth:`LinkFromVertex` to connect vertices across
979 subgraph boundaries.
981 .. seealso::
983 :meth:`EdgeToVertex`
984 |rarr| Create an outbound edge from this vertex to the referenced vertex.
985 :meth:`EdgeToNewVertex`
986 |rarr| Create a new vertex and link that vertex by an outbound edge from this vertex.
987 :meth:`EdgeFromNewVertex`
988 |rarr| Create a new vertex and link that vertex by an inbound edge to this vertex.
989 :meth:`LinkToVertex`
990 |rarr| Create an outbound link from this vertex to the referenced vertex.
991 :meth:`LinkFromVertex`
992 |rarr| Create an inbound link from the referenced vertex to this vertex.
993 """
994 if self._subgraph is vertex._subgraph:
995 edge = Edge(vertex, self, edgeID, edgeValue, edgeWeight, keyValuePairs)
997 vertex._outboundEdges.append(edge)
998 self._inboundEdges.append(edge)
1000 if self._subgraph is None:
1001 # TODO: move into Edge?
1002 # TODO: keep _graph pointer in edge and then register edge on graph?
1003 if edgeID is None:
1004 self._graph._edgesWithoutID.append(edge)
1005 elif edgeID not in self._graph._edgesWithID:
1006 self._graph._edgesWithID[edgeID] = edge
1007 else:
1008 raise DuplicateEdgeError(f"Edge ID '{edgeID}' already exists in this graph.", edgeID=edgeID)
1009 else:
1010 # TODO: keep _graph pointer in edge and then register edge on graph?
1011 if edgeID is None:
1012 self._subgraph._edgesWithoutID.append(edge)
1013 elif edgeID not in self._graph._edgesWithID:
1014 self._subgraph._edgesWithID[edgeID] = edge
1015 else:
1016 raise DuplicateEdgeError(f"Edge ID '{edgeID}' already exists in this graph.", edgeID=edgeID)
1017 else:
1018 ex = NotInSameGraph(f"Vertex {self!r} and vertex {vertex!r} are not in the same graph or subgraph.")
1019 ex.add_note("An edge can only connect vertices within the same graph or subgraph.")
1020 ex.add_note("Use LinkToVertex or LinkFromVertex to connect vertices across subgraph boundaries.")
1021 raise ex
1023 return edge
1025 def EdgeToNewVertex(
1026 self,
1027 vertexID: Nullable[VertexIDType] = None,
1028 vertexValue: Nullable[VertexValueType] = None,
1029 vertexWeight: Nullable[VertexWeightType] = None,
1030 vertexKeyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None,
1031 edgeID: Nullable[EdgeIDType] = None,
1032 edgeWeight: Nullable[EdgeWeightType] = None,
1033 edgeValue: Nullable[VertexValueType] = None,
1034 edgeKeyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None
1035 ) -> Edge:
1036 """
1037 Create a new vertex and link that vertex by an outbound edge from this vertex.
1039 :param vertexID: Optional, the new vertex' optional ID.
1040 :param vertexValue: Optional, the new vertex' optional value.
1041 :param vertexWeight: Optional, the new vertex' optional weight.
1042 :param vertexKeyValuePairs: Optional, mapping (dictionary) of key-value-pairs for the new vertex.
1043 :param edgeID: Optional, the edge's optional ID for the new edge object.
1044 :param edgeWeight: Optional, the edge's optional weight for the new edge object.
1045 :param edgeValue: Optional, the edge's optional value for the new edge object.
1046 :param edgeKeyValuePairs: Optional, mapping (dictionary) of key-value-pairs for the new edge object.
1047 :returns: The edge object linking this vertex and the created vertex.
1048 :raises DuplicateEdgeError: If the given edge ID already exists in this graph or subgraph.
1049 :raises NotInSameGraph: If both vertices are not in the same graph or subgraph. |br|
1050 Use :meth:`LinkToVertex` or :meth:`LinkFromVertex` to connect vertices across
1051 subgraph boundaries.
1053 .. seealso::
1055 :meth:`EdgeToVertex`
1056 |rarr| Create an outbound edge from this vertex to the referenced vertex.
1057 :meth:`EdgeFromVertex`
1058 |rarr| Create an inbound edge from the referenced vertex to this vertex.
1059 :meth:`EdgeFromNewVertex`
1060 |rarr| Create a new vertex and link that vertex by an inbound edge to this vertex.
1061 :meth:`LinkToVertex`
1062 |rarr| Create an outbound link from this vertex to the referenced vertex.
1063 :meth:`LinkFromVertex`
1064 |rarr| Create an inbound link from the referenced vertex to this vertex.
1065 """
1066 vertex = Vertex(vertexID, vertexValue, vertexWeight, vertexKeyValuePairs, graph=self._graph) # , component=self._component)
1068 if self._subgraph is vertex._subgraph: 1068 ↛ 1092line 1068 didn't jump to line 1092 because the condition on line 1068 was always true
1069 edge = Edge(self, vertex, edgeID, edgeValue, edgeWeight, edgeKeyValuePairs)
1071 self._outboundEdges.append(edge)
1072 vertex._inboundEdges.append(edge)
1074 if self._subgraph is None: 1074 ↛ 1085line 1074 didn't jump to line 1085 because the condition on line 1074 was always true
1075 # TODO: move into Edge?
1076 # TODO: keep _graph pointer in edge and then register edge on graph?
1077 if edgeID is None: 1077 ↛ 1079line 1077 didn't jump to line 1079 because the condition on line 1077 was always true
1078 self._graph._edgesWithoutID.append(edge)
1079 elif edgeID not in self._graph._edgesWithID:
1080 self._graph._edgesWithID[edgeID] = edge
1081 else:
1082 raise DuplicateEdgeError(f"Edge ID '{edgeID}' already exists in this graph.", edgeID=edgeID)
1083 else:
1084 # TODO: keep _graph pointer in edge and then register edge on graph?
1085 if edgeID is None:
1086 self._subgraph._edgesWithoutID.append(edge)
1087 elif edgeID not in self._graph._edgesWithID:
1088 self._subgraph._edgesWithID[edgeID] = edge
1089 else:
1090 raise DuplicateEdgeError(f"Edge ID '{edgeID}' already exists in this graph.", edgeID=edgeID)
1091 else:
1092 ex = NotInSameGraph(f"Vertex {self!r} and vertex {vertex!r} are not in the same graph or subgraph.")
1093 ex.add_note("An edge can only connect vertices within the same graph or subgraph.")
1094 ex.add_note("Use LinkToVertex or LinkFromVertex to connect vertices across subgraph boundaries.")
1095 raise ex
1097 return edge
1099 def EdgeFromNewVertex(
1100 self,
1101 vertexID: Nullable[VertexIDType] = None,
1102 vertexValue: Nullable[VertexValueType] = None,
1103 vertexWeight: Nullable[VertexWeightType] = None,
1104 vertexKeyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None,
1105 edgeID: Nullable[EdgeIDType] = None,
1106 edgeWeight: Nullable[EdgeWeightType] = None,
1107 edgeValue: Nullable[VertexValueType] = None,
1108 edgeKeyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None
1109 ) -> Edge:
1110 """
1111 Create a new vertex and link that vertex by an inbound edge to this vertex.
1113 :param vertexID: Optional, the new vertex' optional ID.
1114 :param vertexValue: Optional, the new vertex' optional value.
1115 :param vertexWeight: Optional, the new vertex' optional weight.
1116 :param vertexKeyValuePairs: Optional, mapping (dictionary) of key-value-pairs for the new vertex.
1117 :param edgeID: Optional, the edge's optional ID for the new edge object.
1118 :param edgeWeight: Optional, the edge's optional weight for the new edge object.
1119 :param edgeValue: Optional, the edge's optional value for the new edge object.
1120 :param edgeKeyValuePairs: Optional, mapping (dictionary) of key-value-pairs for the new edge object.
1121 :returns: The edge object linking this vertex and the created vertex.
1122 :raises DuplicateEdgeError: If the given edge ID already exists in this graph or subgraph.
1123 :raises NotInSameGraph: If both vertices are not in the same graph or subgraph. |br|
1124 Use :meth:`LinkToVertex` or :meth:`LinkFromVertex` to connect vertices across
1125 subgraph boundaries.
1127 .. seealso::
1129 :meth:`EdgeToVertex`
1130 |rarr| Create an outbound edge from this vertex to the referenced vertex.
1131 :meth:`EdgeFromVertex`
1132 |rarr| Create an inbound edge from the referenced vertex to this vertex.
1133 :meth:`EdgeToNewVertex`
1134 |rarr| Create a new vertex and link that vertex by an outbound edge from this vertex.
1135 :meth:`LinkToVertex`
1136 |rarr| Create an outbound link from this vertex to the referenced vertex.
1137 :meth:`LinkFromVertex`
1138 |rarr| Create an inbound link from the referenced vertex to this vertex.
1139 """
1140 vertex = Vertex(vertexID, vertexValue, vertexWeight, vertexKeyValuePairs, graph=self._graph) # , component=self._component)
1142 if self._subgraph is vertex._subgraph: 1142 ↛ 1166line 1142 didn't jump to line 1166 because the condition on line 1142 was always true
1143 edge = Edge(vertex, self, edgeID, edgeValue, edgeWeight, edgeKeyValuePairs)
1145 vertex._outboundEdges.append(edge)
1146 self._inboundEdges.append(edge)
1148 if self._subgraph is None: 1148 ↛ 1159line 1148 didn't jump to line 1159 because the condition on line 1148 was always true
1149 # TODO: move into Edge?
1150 # TODO: keep _graph pointer in edge and then register edge on graph?
1151 if edgeID is None: 1151 ↛ 1153line 1151 didn't jump to line 1153 because the condition on line 1151 was always true
1152 self._graph._edgesWithoutID.append(edge)
1153 elif edgeID not in self._graph._edgesWithID:
1154 self._graph._edgesWithID[edgeID] = edge
1155 else:
1156 raise DuplicateEdgeError(f"Edge ID '{edgeID}' already exists in this graph.", edgeID=edgeID)
1157 else:
1158 # TODO: keep _graph pointer in edge and then register edge on graph?
1159 if edgeID is None:
1160 self._subgraph._edgesWithoutID.append(edge)
1161 elif edgeID not in self._graph._edgesWithID:
1162 self._subgraph._edgesWithID[edgeID] = edge
1163 else:
1164 raise DuplicateEdgeError(f"Edge ID '{edgeID}' already exists in this graph.", edgeID=edgeID)
1165 else:
1166 ex = NotInSameGraph(f"Vertex {self!r} and vertex {vertex!r} are not in the same graph or subgraph.")
1167 ex.add_note("An edge can only connect vertices within the same graph or subgraph.")
1168 ex.add_note("Use LinkToVertex or LinkFromVertex to connect vertices across subgraph boundaries.")
1169 raise ex
1171 return edge
1173 def LinkToVertex(
1174 self,
1175 vertex: Vertex,
1176 linkID: Nullable[EdgeIDType] = None,
1177 linkWeight: Nullable[EdgeWeightType] = None,
1178 linkValue: Nullable[VertexValueType] = None,
1179 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None,
1180 ) -> Link:
1181 """
1182 Create an outbound link from this vertex to the referenced vertex.
1184 :param vertex: The vertex to be linked to.
1185 :param linkID: Optional, the link's optional ID for the new link object.
1186 :param linkWeight: Optional, the link's optional weight for the new link object.
1187 :param linkValue: Optional, the link's optional value for the new link object.
1188 :param keyValuePairs: Optional, mapping (dictionary) of key-value-pairs for the new link object.
1189 :returns: The link object linking this vertex and the referenced vertex.
1190 :raises DuplicateEdgeError: If the given link ID already exists in this graph.
1191 :raises NotInDifferentSubgraphs: If both vertices are in the same subgraph - a link connects vertices *across*
1192 subgraph boundaries. |br|
1193 Use :meth:`EdgeToVertex` or :meth:`EdgeFromVertex` to connect vertices within
1194 the same subgraph.
1196 .. seealso::
1198 :meth:`EdgeToVertex`
1199 |rarr| Create an outbound edge from this vertex to the referenced vertex.
1200 :meth:`EdgeFromVertex`
1201 |rarr| Create an inbound edge from the referenced vertex to this vertex.
1202 :meth:`EdgeToNewVertex`
1203 |rarr| Create a new vertex and link that vertex by an outbound edge from this vertex.
1204 :meth:`EdgeFromNewVertex`
1205 |rarr| Create a new vertex and link that vertex by an inbound edge to this vertex.
1206 :meth:`LinkFromVertex`
1207 |rarr| Create an inbound link from the referenced vertex to this vertex.
1208 """
1209 if self._subgraph is vertex._subgraph:
1210 ex = NotInDifferentSubgraphs(f"Vertex {self!r} and vertex {vertex!r} are in the same subgraph.")
1211 ex.add_note("A link can only connect vertices across subgraph boundaries.")
1212 ex.add_note("Use EdgeToVertex or EdgeFromVertex to connect vertices within the same subgraph.")
1213 raise ex
1214 else:
1215 link = Link(self, vertex, linkID, linkValue, linkWeight, keyValuePairs)
1217 self._outboundLinks.append(link)
1218 vertex._inboundLinks.append(link)
1220 if self._subgraph is None:
1221 # TODO: move into Edge?
1222 # TODO: keep _graph pointer in link and then register link on graph?
1223 if linkID is None: 1223 ↛ 1225line 1223 didn't jump to line 1225 because the condition on line 1223 was always true
1224 self._graph._linksWithoutID.append(link)
1225 elif linkID not in self._graph._linksWithID:
1226 self._graph._linksWithID[linkID] = link
1227 else:
1228 raise DuplicateEdgeError(f"Link ID '{linkID}' already exists in this graph.", edgeID=linkID)
1229 else:
1230 # TODO: keep _graph pointer in link and then register link on graph?
1231 if linkID is None:
1232 self._subgraph._linksWithoutID.append(link)
1233 vertex._subgraph._linksWithoutID.append(link)
1234 elif linkID not in self._graph._linksWithID: 1234 ↛ 1238line 1234 didn't jump to line 1238 because the condition on line 1234 was always true
1235 self._subgraph._linksWithID[linkID] = link
1236 vertex._subgraph._linksWithID[linkID] = link
1237 else:
1238 raise DuplicateEdgeError(f"Link ID '{linkID}' already exists in this graph.", edgeID=linkID)
1240 return link
1242 def LinkFromVertex(
1243 self,
1244 vertex: Vertex,
1245 linkID: Nullable[EdgeIDType] = None,
1246 linkWeight: Nullable[EdgeWeightType] = None,
1247 linkValue: Nullable[VertexValueType] = None,
1248 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None
1249 ) -> Edge:
1250 """
1251 Create an inbound link from the referenced vertex to this vertex.
1253 :param vertex: The vertex to be linked from.
1254 :param linkID: Optional, the link's optional ID for the new link object.
1255 :param linkWeight: Optional, the link's optional weight for the new link object.
1256 :param linkValue: Optional, the link's optional value for the new link object.
1257 :param keyValuePairs: Optional, mapping (dictionary) of key-value-pairs for the new link object.
1258 :returns: The link object linking the referenced vertex and this vertex.
1259 :raises DuplicateEdgeError: If the given link ID already exists in this graph.
1260 :raises NotInDifferentSubgraphs: If both vertices are in the same subgraph - a link connects vertices *across*
1261 subgraph boundaries. |br|
1262 Use :meth:`EdgeToVertex` or :meth:`EdgeFromVertex` to connect vertices within
1263 the same subgraph.
1265 .. seealso::
1267 :meth:`EdgeToVertex`
1268 |rarr| Create an outbound edge from this vertex to the referenced vertex.
1269 :meth:`EdgeFromVertex`
1270 |rarr| Create an inbound edge from the referenced vertex to this vertex.
1271 :meth:`EdgeToNewVertex`
1272 |rarr| Create a new vertex and link that vertex by an outbound edge from this vertex.
1273 :meth:`EdgeFromNewVertex`
1274 |rarr| Create a new vertex and link that vertex by an inbound edge to this vertex.
1275 :meth:`LinkToVertex`
1276 |rarr| Create an outbound link from this vertex to the referenced vertex.
1277 """
1278 if self._subgraph is vertex._subgraph:
1279 ex = NotInDifferentSubgraphs(f"Vertex {self!r} and vertex {vertex!r} are in the same subgraph.")
1280 ex.add_note("A link can only connect vertices across subgraph boundaries.")
1281 ex.add_note("Use EdgeToVertex or EdgeFromVertex to connect vertices within the same subgraph.")
1282 raise ex
1283 else:
1284 link = Link(vertex, self, linkID, linkValue, linkWeight, keyValuePairs)
1286 vertex._outboundLinks.append(link)
1287 self._inboundLinks.append(link)
1289 if self._subgraph is None: 1289 ↛ 1292line 1289 didn't jump to line 1292 because the condition on line 1289 was never true
1290 # TODO: move into Edge?
1291 # TODO: keep _graph pointer in link and then register link on graph?
1292 if linkID is None:
1293 self._graph._linksWithoutID.append(link)
1294 elif linkID not in self._graph._linksWithID:
1295 self._graph._linksWithID[linkID] = link
1296 else:
1297 raise DuplicateEdgeError(f"Link ID '{linkID}' already exists in this graph.", edgeID=linkID)
1298 else:
1299 # TODO: keep _graph pointer in link and then register link on graph?
1300 if linkID is None: 1300 ↛ 1303line 1300 didn't jump to line 1303 because the condition on line 1300 was always true
1301 self._subgraph._linksWithoutID.append(link)
1302 vertex._subgraph._linksWithoutID.append(link)
1303 elif linkID not in self._graph._linksWithID:
1304 self._subgraph._linksWithID[linkID] = link
1305 vertex._subgraph._linksWithID[linkID] = link
1306 else:
1307 raise DuplicateEdgeError(f"Link ID '{linkID}' already exists in this graph.", edgeID=linkID)
1309 return link
1311 def HasEdgeToDestination(self, destination: Vertex) -> bool:
1312 """
1313 Check if this vertex is linked to another vertex by any outbound edge.
1315 :param destination: Destination vertex to check.
1316 :returns: ``True``, if the destination vertex is a destination on any outbound edge.
1318 .. seealso::
1320 :meth:`HasEdgeFromSource`
1321 |rarr| Check if this vertex is linked to another vertex by any inbound edge.
1322 :meth:`HasLinkToDestination`
1323 |rarr| Check if this vertex is linked to another vertex by any outbound link.
1324 :meth:`HasLinkFromSource`
1325 |rarr| Check if this vertex is linked to another vertex by any inbound link.
1326 """
1327 for edge in self._outboundEdges:
1328 if destination is edge.Destination: 1328 ↛ 1327line 1328 didn't jump to line 1327 because the condition on line 1328 was always true
1329 return True
1331 return False
1333 def HasEdgeFromSource(self, source: Vertex) -> bool:
1334 """
1335 Check if this vertex is linked to another vertex by any inbound edge.
1337 :param source: Source vertex to check.
1338 :returns: ``True``, if the source vertex is a source on any inbound edge.
1340 .. seealso::
1342 :meth:`HasEdgeToDestination`
1343 |rarr| Check if this vertex is linked to another vertex by any outbound edge.
1344 :meth:`HasLinkToDestination`
1345 |rarr| Check if this vertex is linked to another vertex by any outbound link.
1346 :meth:`HasLinkFromSource`
1347 |rarr| Check if this vertex is linked to another vertex by any inbound link.
1348 """
1349 for edge in self._inboundEdges:
1350 if source is edge.Source: 1350 ↛ 1349line 1350 didn't jump to line 1349 because the condition on line 1350 was always true
1351 return True
1353 return False
1355 def HasLinkToDestination(self, destination: Vertex) -> bool:
1356 """
1357 Check if this vertex is linked to another vertex by any outbound link.
1359 :param destination: Destination vertex to check.
1360 :returns: ``True``, if the destination vertex is a destination on any outbound link.
1362 .. seealso::
1364 :meth:`HasEdgeToDestination`
1365 |rarr| Check if this vertex is linked to another vertex by any outbound edge.
1366 :meth:`HasEdgeFromSource`
1367 |rarr| Check if this vertex is linked to another vertex by any inbound edge.
1368 :meth:`HasLinkFromSource`
1369 |rarr| Check if this vertex is linked to another vertex by any inbound link.
1370 """
1371 for link in self._outboundLinks:
1372 if destination is link.Destination: 1372 ↛ 1371line 1372 didn't jump to line 1371 because the condition on line 1372 was always true
1373 return True
1375 return False
1377 def HasLinkFromSource(self, source: Vertex) -> bool:
1378 """
1379 Check if this vertex is linked to another vertex by any inbound link.
1381 :param source: Source vertex to check.
1382 :returns: ``True``, if the source vertex is a source on any inbound link.
1384 .. seealso::
1386 :meth:`HasEdgeToDestination`
1387 |rarr| Check if this vertex is linked to another vertex by any outbound edge.
1388 :meth:`HasEdgeFromSource`
1389 |rarr| Check if this vertex is linked to another vertex by any inbound edge.
1390 :meth:`HasLinkToDestination`
1391 |rarr| Check if this vertex is linked to another vertex by any outbound link.
1392 """
1393 for link in self._inboundLinks:
1394 if source is link.Source: 1394 ↛ 1393line 1394 didn't jump to line 1393 because the condition on line 1394 was always true
1395 return True
1397 return False
1399 def DeleteEdgeTo(self, destination: Vertex) -> None:
1400 """
1401 Delete the outbound edge to the given vertex.
1403 :param destination: The vertex the edge points to.
1404 :raises EdgeNotFoundError: If no outbound edge to that vertex exists.
1405 """
1406 for edge in self._outboundEdges: 1406 ↛ 1410line 1406 didn't jump to line 1410 because the loop on line 1406 didn't complete
1407 if edge._destination is destination: 1407 ↛ 1406line 1407 didn't jump to line 1406 because the condition on line 1407 was always true
1408 break
1409 else:
1410 raise EdgeNotFoundError(f"No outbound edge found to '{destination!r}'.")
1412 edge.Delete()
1414 def DeleteEdgeFrom(self, source: Vertex) -> None:
1415 """
1416 Delete the inbound edge from the given vertex.
1418 :param source: The vertex the edge comes from.
1419 :raises EdgeNotFoundError: If no inbound edge from that vertex exists.
1420 """
1421 for edge in self._inboundEdges:
1422 if edge._source is source:
1423 break
1424 else:
1425 raise EdgeNotFoundError(f"No inbound edge found to '{source!r}'.")
1427 edge.Delete()
1429 def DeleteLinkTo(self, destination: Vertex) -> None:
1430 """
1431 Delete the outbound link to the given vertex.
1433 :param destination: The vertex the link points to.
1434 :raises LinkNotFoundError: If no outbound link to that vertex exists.
1435 """
1436 for link in self._outboundLinks:
1437 if link._destination is destination:
1438 break
1439 else:
1440 raise LinkNotFoundError(f"No outbound link found to '{destination!r}'.")
1442 link.Delete()
1444 def DeleteLinkFrom(self, source: Vertex) -> None:
1445 """
1446 Delete the inbound link from the given vertex.
1448 :param source: The vertex the link comes from.
1449 :raises LinkNotFoundError: If no inbound link from that vertex exists.
1450 """
1451 for link in self._inboundLinks:
1452 if link._source is source:
1453 break
1454 else:
1455 raise LinkNotFoundError(f"No inbound link found to '{source!r}'.")
1457 link.Delete()
1459 def Copy(self, graph: Graph, copyDict: bool = False, linkingKeyToOriginalVertex: Nullable[str] = None, linkingKeyFromOriginalVertex: Nullable[str] = None) -> Vertex:
1460 """
1461 Creates a copy of this vertex in another graph.
1463 Optionally, the vertex's attached attributes (key-value-pairs) can be copied and a linkage between both vertices
1464 can be established.
1466 :param graph: Optional, the graph, the vertex is created in.
1467 :param copyDict: Optional, if ``True``, copy all attached attributes into the new vertex.
1468 :param linkingKeyToOriginalVertex: Optional, if not ``None``, add a key-value-pair using this parameter as key
1469 from new vertex to the original vertex.
1470 :param linkingKeyFromOriginalVertex: Optional, if not ``None``, add a key-value-pair using this parameter as key
1471 from original vertex to the new vertex.
1472 :returns: The newly created vertex.
1473 :raises SameGraphError: If source graph and destination graph are the same.
1474 """
1475 if graph is self._graph:
1476 raise SameGraphError("Graph to copy this vertex to, is the same graph.")
1478 vertex = Vertex(self._id, self._value, self._weight, graph=graph)
1479 if copyDict:
1480 vertex._dict = self._dict.copy()
1482 if linkingKeyToOriginalVertex is not None:
1483 vertex._dict[linkingKeyToOriginalVertex] = self
1484 if linkingKeyFromOriginalVertex is not None:
1485 self._dict[linkingKeyFromOriginalVertex] = vertex
1487 return vertex
1489 def IterateOutboundEdges(self, predicate: Nullable[Callable[[Edge], bool]] = None) -> Generator[Edge, None, None]:
1490 """
1491 Iterate all or selected outbound edges of this vertex.
1493 If parameter ``predicate`` is not None, the given filter function is used to skip edges in the generator.
1495 :param predicate: Optional, filter function accepting any edge and returning a boolean.
1496 :returns: A generator to iterate all outbound edges.
1497 """
1498 if predicate is None:
1499 for edge in self._outboundEdges:
1500 yield edge
1501 else:
1502 for edge in self._outboundEdges:
1503 if predicate(edge):
1504 yield edge
1506 def IterateInboundEdges(self, predicate: Nullable[Callable[[Edge], bool]] = None) -> Generator[Edge, None, None]:
1507 """
1508 Iterate all or selected inbound edges of this vertex.
1510 If parameter ``predicate`` is not None, the given filter function is used to skip edges in the generator.
1512 :param predicate: Optional, filter function accepting any edge and returning a boolean.
1513 :returns: A generator to iterate all inbound edges.
1514 """
1515 if predicate is None:
1516 for edge in self._inboundEdges:
1517 yield edge
1518 else:
1519 for edge in self._inboundEdges:
1520 if predicate(edge):
1521 yield edge
1523 def IterateOutboundLinks(self, predicate: Nullable[Callable[[Link], bool]] = None) -> Generator[Link, None, None]:
1524 """
1525 Iterate all or selected outbound links of this vertex.
1527 If parameter ``predicate`` is not None, the given filter function is used to skip links in the generator.
1529 :param predicate: Optional, filter function accepting any link and returning a boolean.
1530 :returns: A generator to iterate all outbound links.
1531 """
1532 if predicate is None:
1533 for link in self._outboundLinks:
1534 yield link
1535 else:
1536 for link in self._outboundLinks:
1537 if predicate(link):
1538 yield link
1540 def IterateInboundLinks(self, predicate: Nullable[Callable[[Link], bool]] = None) -> Generator[Link, None, None]:
1541 """
1542 Iterate all or selected inbound links of this vertex.
1544 If parameter ``predicate`` is not None, the given filter function is used to skip links in the generator.
1546 :param predicate: Optional, filter function accepting any link and returning a boolean.
1547 :returns: A generator to iterate all inbound links.
1548 """
1549 if predicate is None:
1550 for link in self._inboundLinks:
1551 yield link
1552 else:
1553 for link in self._inboundLinks:
1554 if predicate(link):
1555 yield link
1557 def IterateSuccessorVertices(self, predicate: Nullable[Callable[[Edge], bool]] = None) -> Generator[Vertex, None, None]:
1558 """
1559 Iterate all or selected successor vertices of this vertex.
1561 If parameter ``predicate`` is not None, the given filter function is used to skip successors in the generator.
1563 :param predicate: Optional, filter function accepting any edge and returning a boolean.
1564 :returns: A generator to iterate all successor vertices.
1565 """
1566 if predicate is None:
1567 for edge in self._outboundEdges:
1568 yield edge.Destination
1569 else:
1570 for edge in self._outboundEdges:
1571 if predicate(edge):
1572 yield edge.Destination
1574 def IteratePredecessorVertices(self, predicate: Nullable[Callable[[Edge], bool]] = None) -> Generator[Vertex, None, None]:
1575 """
1576 Iterate all or selected predecessor vertices of this vertex.
1578 If parameter ``predicate`` is not None, the given filter function is used to skip predecessors in the generator.
1580 :param predicate: Optional, filter function accepting any edge and returning a boolean.
1581 :returns: A generator to iterate all predecessor vertices.
1582 """
1583 if predicate is None:
1584 for edge in self._inboundEdges:
1585 yield edge.Source
1586 else:
1587 for edge in self._inboundEdges:
1588 if predicate(edge):
1589 yield edge.Source
1591 def IterateVerticesBFS(self) -> Generator[Vertex, None, None]:
1592 """
1593 A generator to iterate all reachable vertices starting from this node in breadth-first search (BFS) order.
1595 :returns: A generator to iterate vertices traversed in BFS order.
1597 .. seealso::
1599 :meth:`IterateVerticesDFS`
1600 |rarr| Iterate all reachable vertices **depth-first search** order.
1601 """
1602 visited: set[Vertex] = set()
1603 queue: Deque[Vertex] = deque()
1605 yield self
1606 visited.add(self)
1607 for edge in self._outboundEdges:
1608 nextVertex = edge.Destination
1609 if nextVertex is not self: 1609 ↛ 1607line 1609 didn't jump to line 1607 because the condition on line 1609 was always true
1610 queue.appendleft(nextVertex)
1611 visited.add(nextVertex)
1613 while queue:
1614 vertex = queue.pop()
1615 yield vertex
1616 for edge in vertex._outboundEdges:
1617 nextVertex = edge.Destination
1618 if nextVertex not in visited:
1619 queue.appendleft(nextVertex)
1620 visited.add(nextVertex)
1622 def IterateVerticesDFS(self) -> Generator[Vertex, None, None]:
1623 """
1624 A generator to iterate all reachable vertices starting from this node in depth-first search (DFS) order.
1626 :returns: A generator to iterate vertices traversed in DFS order.
1628 .. seealso::
1630 :meth:`IterateVerticesBFS`
1631 |rarr| Iterate all reachable vertices **breadth-first search** order.
1633 Wikipedia - https://en.wikipedia.org/wiki/Depth-first_search
1634 """
1635 visited: set[Vertex] = set()
1636 stack: list[typing_Iterator[Edge]] = list()
1638 yield self
1639 visited.add(self)
1640 stack.append(iter(self._outboundEdges))
1642 while True:
1643 try:
1644 edge = next(stack[-1])
1645 nextVertex = edge._destination
1646 if nextVertex not in visited:
1647 visited.add(nextVertex)
1648 yield nextVertex
1649 if len(nextVertex._outboundEdges) != 0:
1650 stack.append(iter(nextVertex._outboundEdges))
1651 except StopIteration:
1652 stack.pop()
1654 if len(stack) == 0:
1655 return
1657 def IterateAllOutboundPathsAsVertexList(self) -> Generator[tuple[Vertex, ...], None, None]:
1658 """
1659 Iterate all paths starting at this vertex, each as a tuple of vertices.
1661 The traversal is depth-first and keeps the vertices of the current path in a set, so a cycle is detected
1662 instead of iterated endlessly. A vertex without outbound edges yields the path containing only itself.
1664 :returns: A generator yielding one tuple of vertices per path.
1665 :raises CycleError: If a cycle is detected while walking a path.
1666 """
1667 if len(self._outboundEdges) == 0:
1668 yield (self, )
1669 return
1671 visited: set[Vertex] = set()
1672 vertexStack: list[Vertex] = list()
1673 iteratorStack: list[typing_Iterator[Edge]] = list()
1675 visited.add(self)
1676 vertexStack.append(self)
1677 iteratorStack.append(iter(self._outboundEdges))
1679 while True:
1680 try:
1681 edge = next(iteratorStack[-1])
1682 nextVertex = edge._destination
1683 if nextVertex in visited:
1684 ex = CycleError("Loop detected.")
1685 ex.add_note("First loop is:")
1686 for i, vertex in enumerate(vertexStack):
1687 ex.add_note(f" {i}: {vertex!r}")
1688 raise ex
1690 vertexStack.append(nextVertex)
1691 if len(nextVertex._outboundEdges) == 0:
1692 yield tuple(vertexStack)
1693 vertexStack.pop()
1694 else:
1695 iteratorStack.append(iter(nextVertex._outboundEdges))
1697 except StopIteration:
1698 vertexStack.pop()
1699 iteratorStack.pop()
1701 if len(vertexStack) == 0:
1702 return
1704 def ShortestPathToByHops(self, destination: Vertex) -> Generator[Vertex, None, None]:
1705 """
1706 Compute the shortest path (by hops) between this vertex and the destination vertex.
1708 A generator is return to iterate all vertices along the path including source and destination vertex.
1710 The search algorithm is breadth-first search (BFS) based. The found solution, if any, is not unique but deterministic
1711 as long as the graph was not modified (e.g. ordering of edges on vertices).
1713 :param destination: The destination vertex to reach.
1714 :returns: A generator to iterate all vertices on the path found between this vertex and the
1715 destination vertex.
1716 :raises DestinationNotReachable: If the destination vertex cannot be reached from this vertex.
1717 """
1718 # Trivial case if start is destination
1719 if self is destination: 1719 ↛ 1720line 1719 didn't jump to line 1720 because the condition on line 1719 was never true
1720 yield self
1721 return
1723 # Local struct to create multiple linked-lists forming a paths from current node back to the starting point
1724 # (actually a tree). Each node holds a reference to the vertex it represents.
1725 # Hint: slotted classes are faster than '@dataclasses.dataclass'.
1726 class Node(metaclass=ExtendedType, slots=True):
1727 """A node of the search tree: the vertex it represents and its predecessor on the path."""
1728 parent: Node #: Predecessor on the path back to the starting point.
1729 ref: Vertex #: The vertex this node represents.
1731 def __init__(self, parent: Node, ref: Vertex) -> None:
1732 """
1733 Initialize a search tree node.
1735 :param parent: Predecessor on the path back to the starting point.
1736 :param ref: The vertex this node represents.
1737 """
1738 self.parent = parent
1739 self.ref = ref
1741 def __str__(self) -> str:
1742 """
1743 Return a string representation of this search tree node.
1745 :returns: The ID of the vertex this node represents.
1746 """
1747 return f"Vertex: {self.ref.ID}"
1749 # Initially add all reachable vertices to a queue if vertices to be processed.
1750 startNode = Node(None, self)
1751 visited: set[Vertex] = set()
1752 queue: Deque[Node] = deque()
1754 # Add starting vertex and all its children to the processing list.
1755 # If a child is the destination, break immediately else go into 'else' branch and use BFS algorithm.
1756 visited.add(self)
1757 for edge in self._outboundEdges:
1758 nextVertex = edge.Destination
1759 if nextVertex is destination: 1759 ↛ 1761line 1759 didn't jump to line 1761 because the condition on line 1759 was never true
1760 # Child is destination, so construct the last node for path traversal and break from loop.
1761 destinationNode = Node(startNode, nextVertex)
1762 break
1763 if nextVertex is not self: 1763 ↛ 1757line 1763 didn't jump to line 1757 because the condition on line 1763 was always true
1764 # Ignore backward-edges and side-edges.
1765 # Here self-edges, because there is only the starting vertex in the list of visited edges.
1766 visited.add(nextVertex)
1767 queue.appendleft(Node(startNode, nextVertex))
1768 else:
1769 # Process queue until destination is found or no further vertices are reachable.
1770 while queue:
1771 node = queue.pop()
1772 for edge in node.ref._outboundEdges:
1773 nextVertex = edge.Destination
1774 # Next reachable vertex is destination, so construct the last node for path traversal and break from loop.
1775 if nextVertex is destination:
1776 destinationNode = Node(node, nextVertex)
1777 break
1778 # Ignore backward-edges and side-edges.
1779 if nextVertex not in visited:
1780 visited.add(nextVertex)
1781 queue.appendleft(Node(node, nextVertex))
1782 # Next 3 lines realize a double-break if break was called in inner loop, otherwise continue with outer loop.
1783 else:
1784 continue
1785 break
1786 else:
1787 # All reachable vertices have been processed, but destination was not among them.
1788 raise DestinationNotReachable("Destination is not reachable.")
1790 # Reverse order of linked list from destinationNode to startNode
1791 currentNode = destinationNode
1792 previousNode = destinationNode.parent
1793 currentNode.parent = None
1794 while previousNode is not None:
1795 node = previousNode.parent
1796 previousNode.parent = currentNode
1797 currentNode = previousNode
1798 previousNode = node
1800 # Scan reversed linked-list and yield referenced vertices
1801 yield startNode.ref
1802 node = startNode.parent
1803 while node is not None:
1804 yield node.ref
1805 node = node.parent
1807 def ShortestPathToByWeight(self, destination: Vertex) -> Generator[Vertex, None, None]:
1808 """
1809 Compute the shortest path (by edge weight) between this vertex and the destination vertex.
1811 A generator is return to iterate all vertices along the path including source and destination vertex.
1813 The search algorithm is based on Dijkstra algorithm and using :mod:`heapq`. The found solution, if any, is not
1814 unique but deterministic as long as the graph was not modified (e.g. ordering of edges on vertices).
1816 :param destination: The destination vertex to reach.
1817 :returns: A generator to iterate all vertices on the path found between this vertex and the
1818 destination vertex.
1819 :raises DestinationNotReachable: If the destination vertex cannot be reached from this vertex.
1820 """
1821 # Improvements: both-sided Dijkstra (search from start and destination to reduce discovered area.
1823 # Trivial case if start is destination
1824 if self is destination: 1824 ↛ 1825line 1824 didn't jump to line 1825 because the condition on line 1824 was never true
1825 yield self
1826 return
1828 # Local struct to create multiple-linked lists forming a paths from current node back to the starting point
1829 # (actually a tree). Each node holds the overall weight from start to current node and a reference to the vertex it
1830 # represents.
1831 # Hint: slotted classes are faster than '@dataclasses.dataclass'.
1832 class Node(metaclass=ExtendedType, slots=True):
1833 """A node of the search tree: the vertex, its predecessor, and the accumulated weight to reach it."""
1834 parent: Node #: Predecessor on the path back to the starting point.
1835 distance: EdgeWeightType #: Accumulated edge weight from the starting point to this node.
1836 ref: Vertex #: The vertex this node represents.
1838 def __init__(self, parent: Node, distance: EdgeWeightType, ref: Vertex) -> None:
1839 """
1840 Initialize a search tree node.
1842 :param parent: Predecessor on the path back to the starting point.
1843 :param distance: Accumulated edge weight from the starting point to this node.
1844 :param ref: The vertex this node represents.
1845 """
1846 self.parent = parent
1847 self.distance = distance
1848 self.ref = ref
1850 def __lt__(self, other: Any) -> bool:
1851 """
1852 Compare two search tree nodes by their accumulated distance, so they can be kept in a priority queue.
1854 :param other: Second operand.
1855 :returns: ``True``, if this node is closer to the starting point than the second operand.
1856 """
1857 return self.distance < other.distance
1859 def __str__(self) -> str:
1860 """
1861 Return a string representation of this search tree node.
1863 :returns: The ID of the vertex this node represents.
1864 """
1865 return f"Vertex: {self.ref.ID}"
1867 visited: set[Vertex] = set()
1868 startNode = Node(None, 0, self)
1869 priorityQueue = [startNode]
1871 # Add starting vertex and all its children to the processing list.
1872 # If a child is the destination, break immediately else go into 'else' branch and use Dijkstra algorithm.
1873 visited.add(self)
1874 for edge in self._outboundEdges:
1875 nextVertex = edge.Destination
1876 # Child is destination, so construct the last node for path traversal and break from loop.
1877 if nextVertex is destination: 1877 ↛ 1878line 1877 didn't jump to line 1878 because the condition on line 1877 was never true
1878 destinationNode = Node(startNode, edge._weight, nextVertex)
1879 break
1880 # Ignore backward-edges and side-edges.
1881 # Here self-edges, because there is only the starting vertex in the list of visited edges.
1882 if nextVertex is not self: 1882 ↛ 1874line 1882 didn't jump to line 1874 because the condition on line 1882 was always true
1883 visited.add(nextVertex)
1884 heapq.heappush(priorityQueue, Node(startNode, edge._weight, nextVertex))
1885 else:
1886 # Process priority queue until destination is found or no further vertices are reachable.
1887 while priorityQueue: 1887 ↛ 1905line 1887 didn't jump to line 1905 because the condition on line 1887 was always true
1888 node = heapq.heappop(priorityQueue)
1889 for edge in node.ref._outboundEdges:
1890 nextVertex = edge.Destination
1891 # Next reachable vertex is destination, so construct the last node for path traversal and break from loop.
1892 if nextVertex is destination:
1893 destinationNode = Node(node, node.distance + edge._weight, nextVertex)
1894 break
1895 # Ignore backward-edges and side-edges.
1896 if nextVertex not in visited:
1897 visited.add(nextVertex)
1898 heapq.heappush(priorityQueue, Node(node, node.distance + edge._weight, nextVertex))
1899 # Next 3 lines realize a double-break if break was called in inner loop, otherwise continue with outer loop.
1900 else:
1901 continue
1902 break
1903 else:
1904 # All reachable vertices have been processed, but destination was not among them.
1905 raise DestinationNotReachable("Destination is not reachable.")
1907 # Reverse order of linked-list from destinationNode to startNode
1908 currentNode = destinationNode
1909 previousNode = destinationNode.parent
1910 currentNode.parent = None
1911 while previousNode is not None:
1912 node = previousNode.parent
1913 previousNode.parent = currentNode
1914 currentNode = previousNode
1915 previousNode = node
1917 # Scan reversed linked-list and yield referenced vertices
1918 yield startNode.ref, startNode.distance
1919 node = startNode.parent
1920 while node is not None:
1921 yield node.ref, node.distance
1922 node = node.parent
1924 # Other possible algorithms:
1925 # * Bellman-Ford
1926 # * Floyd-Warshall
1928 # def PathExistsTo(self, destination: 'Vertex'):
1929 # raise NotImplementedError()
1930 # # DFS
1931 # # Union find
1932 #
1933 # def MaximumFlowTo(self, destination: 'Vertex'):
1934 # raise NotImplementedError()
1935 # # Ford-Fulkerson algorithm
1936 # # Edmons-Karp algorithm
1937 # # Dinic's algorithm
1939 def ConvertToTree(self) -> Node:
1940 """
1941 Converts all reachable vertices from this starting vertex to a tree of :class:`~pyTooling.Tree.Node` instances.
1943 The tree is traversed using depths-first-search.
1945 :returns: Root node of the resulting tree, representing this vertex.
1946 :raises NotATreeError: If the graph reachable from this vertex is not a tree, because a vertex has more than one
1947 parent.
1948 """
1949 visited: set[Vertex] = set()
1950 stack: list[tuple[Node, typing_Iterator[Edge]]] = list()
1952 root = Node(nodeID=self._id, value=self._value)
1953 root._dict = self._dict.copy()
1955 visited.add(self)
1956 stack.append((root, iter(self._outboundEdges)))
1958 while True:
1959 try:
1960 edge = next(stack[-1][1])
1961 nextVertex = edge._destination
1962 if nextVertex not in visited: 1962 ↛ 1968line 1962 didn't jump to line 1968 because the condition on line 1962 was always true
1963 node = Node(nextVertex._id, nextVertex._value, parent=stack[-1][0])
1964 visited.add(nextVertex)
1965 if len(nextVertex._outboundEdges) != 0:
1966 stack.append((node, iter(nextVertex._outboundEdges)))
1967 else:
1968 raise NotATreeError("The directed subgraph is not a tree.")
1969 # TODO: compute cycle:
1970 # a) branch 1 is described in stack
1971 # b) branch 2 can be found by walking from joint to root in the tree
1972 except StopIteration:
1973 stack.pop()
1975 if len(stack) == 0:
1976 return root
1978 def __repr__(self) -> str:
1979 """
1980 Returns a detailed string representation of the vertex.
1982 :returns: The detailed string representation of the vertex.
1983 """
1984 vertexID = value = ""
1985 sep = ": "
1986 if self._id is not None:
1987 vertexID = f"{sep}vertexID='{self._id}'"
1988 sep = "; "
1989 if self._value is not None: 1989 ↛ 1990line 1989 didn't jump to line 1990 because the condition on line 1989 was never true
1990 value = f"{sep}value='{self._value}'"
1992 return f"<vertex{vertexID}{value}>"
1994 def __str__(self) -> str:
1995 """
1996 Return a string representation of the vertex.
1998 Order of resolution:
2000 1. If :attr:`_value` is not None, return the string representation of :attr:`_value`.
2001 2. If :attr:`_id` is not None, return the string representation of :attr:`_id`.
2002 3. Else, return :meth:`__repr__`.
2004 :returns: The resolved string representation of the vertex.
2005 """
2006 if self._value is not None: 2006 ↛ 2007line 2006 didn't jump to line 2007 because the condition on line 2006 was never true
2007 return str(self._value)
2008 elif self._id is not None: 2008 ↛ 2009line 2008 didn't jump to line 2009 because the condition on line 2008 was never true
2009 return str(self._id)
2010 else:
2011 return self.__repr__()
2014@export
2015class BaseEdge(
2016 BaseWithIDValueAndWeight[EdgeIDType, EdgeValueType, EdgeWeightType, EdgeDictKeyType, EdgeDictValueType],
2017 Generic[EdgeIDType, EdgeValueType, EdgeWeightType, EdgeDictKeyType, EdgeDictValueType]
2018):
2019 """
2020 An **edge** can have a unique ID, a value, a weight and attached meta information as key-value-pairs. All edges are
2021 directed.
2022 """
2023 _source: Vertex #: Vertex the edge starts at.
2024 _destination: Vertex #: Vertex the edge ends at.
2026 def __init__(
2027 self,
2028 source: Vertex,
2029 destination: Vertex,
2030 edgeID: Nullable[EdgeIDType] = None,
2031 value: Nullable[EdgeValueType] = None,
2032 weight: Nullable[EdgeWeightType] = None,
2033 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None
2034 ) -> None:
2035 """
2036 Initialize an edge between a source and a destination vertex.
2038 :param source: The source of the new edge.
2039 :param destination: The destination of the new edge.
2040 :param edgeID: Optional, unique ID for the new edge.
2041 :param value: Optional, value for the new edge.
2042 :param weight: Optional, weight for the new edge.
2043 :param keyValuePairs: Optional, mapping (dictionary) of key-value-pairs.
2044 """
2045 super().__init__(edgeID, value, weight, keyValuePairs)
2047 self._source = source
2048 self._destination = destination
2050 component = source._component
2051 if component is not destination._component:
2052 # TODO: should it be divided into with/without ID?
2053 oldComponent = destination._component
2054 for vertex in oldComponent._vertices:
2055 vertex._component = component
2056 component._vertices.add(vertex)
2057 component._graph._components.remove(oldComponent)
2058 del oldComponent
2060 @readonly
2061 def Source(self) -> Vertex:
2062 """
2063 Read-only property to get the source (:attr:`_source`) of an edge.
2065 :returns: The source of an edge.
2066 """
2067 return self._source
2069 @readonly
2070 def Destination(self) -> Vertex:
2071 """
2072 Read-only property to get the destination (:attr:`_destination`) of an edge.
2074 :returns: The destination of an edge.
2075 """
2076 return self._destination
2078 def Reverse(self) -> None:
2079 """Reverse the direction of this edge."""
2080 swap = self._source
2081 self._source = self._destination
2082 self._destination = swap
2085@export
2086class Edge(
2087 BaseEdge[EdgeIDType, EdgeValueType, EdgeWeightType, EdgeDictKeyType, EdgeDictValueType],
2088 Generic[EdgeIDType, EdgeValueType, EdgeWeightType, EdgeDictKeyType, EdgeDictValueType]
2089):
2090 """
2091 An **edge** can have a unique ID, a value, a weight and attached meta information as key-value-pairs. All edges are
2092 directed.
2093 """
2095 def __init__(
2096 self,
2097 source: Vertex,
2098 destination: Vertex,
2099 edgeID: Nullable[EdgeIDType] = None,
2100 value: Nullable[EdgeValueType] = None,
2101 weight: Nullable[EdgeWeightType] = None,
2102 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None
2103 ) -> None:
2104 """
2105 Initialize an edge between two vertices of the same graph or subgraph.
2107 :param source: The source of the new edge.
2108 :param destination: The destination of the new edge.
2109 :param edgeID: Optional, unique ID for the new edge.
2110 :param value: Optional, value for the new edge.
2111 :param weight: Optional, weight for the new edge.
2112 :param keyValuePairs: Optional, mapping (dictionary) of key-value-pairs.
2113 :raises TypeError: If parameter 'weight' is not of the graph's edge weight type.
2114 :raises NotInSameGraph: If source and destination vertex are not in the same graph or subgraph.
2115 """
2116 if not isinstance(source, Vertex):
2117 ex = TypeError("Parameter 'source' is not of type 'Vertex'.")
2118 ex.add_note(f"Got type '{getFullyQualifiedName(source)}'.")
2119 raise ex
2120 if not isinstance(destination, Vertex):
2121 ex = TypeError("Parameter 'destination' is not of type 'Vertex'.")
2122 ex.add_note(f"Got type '{getFullyQualifiedName(destination)}'.")
2123 raise ex
2124 if edgeID is not None and not isinstance(edgeID, Hashable):
2125 ex = TypeError("Parameter 'edgeID' is not of type 'EdgeIDType'.")
2126 ex.add_note(f"Got type '{getFullyQualifiedName(edgeID)}'.")
2127 raise ex
2128 # if value is not None and not isinstance(value, Vertex):
2129 # raise TypeError("Parameter 'value' is not of type 'EdgeValueType'.")
2130 if weight is not None and not isinstance(weight, (int, float)):
2131 ex = TypeError("Parameter 'weight' is not of type 'EdgeWeightType'.")
2132 ex.add_note(f"Got type '{getFullyQualifiedName(weight)}'.")
2133 raise ex
2134 if source._graph is not destination._graph:
2135 raise NotInSameGraph("Source vertex and destination vertex are not in same graph.")
2137 super().__init__(source, destination, edgeID, value, weight, keyValuePairs)
2139 def Delete(self) -> None:
2140 """
2141 Delete this edge from both of its vertices and from the graph or subgraph it belongs to.
2142 """
2143 # Remove from Source and Destination
2144 self._source._outboundEdges.remove(self)
2145 self._destination._inboundEdges.remove(self)
2147 self._Unregister()
2148 self._Delete()
2150 def _Unregister(self) -> None:
2151 """
2152 Remove this edge from the graph or subgraph it was registered on.
2154 An edge is registered on the subgraph it lives in, otherwise on the graph. Called by :meth:`Delete` and by
2155 :meth:`Vertex.Delete`, which unlinks the vertices itself.
2156 """
2157 container = self._source._graph if self._source._subgraph is None else self._source._subgraph
2158 if self._id is None:
2159 container._edgesWithoutID.remove(self)
2160 else:
2161 del container._edgesWithID[self._id]
2163 def _Delete(self) -> None:
2164 """
2165 Delete the edge's attached attributes, after it was disconnected.
2166 """
2167 super().Delete()
2169 def Reverse(self) -> None:
2170 """Reverse the direction of this edge."""
2171 self._source._outboundEdges.remove(self)
2172 self._source._inboundEdges.append(self)
2173 self._destination._inboundEdges.remove(self)
2174 self._destination._outboundEdges.append(self)
2176 super().Reverse()
2179@export
2180class Link(
2181 BaseEdge[LinkIDType, LinkValueType, LinkWeightType, LinkDictKeyType, LinkDictValueType],
2182 Generic[LinkIDType, LinkValueType, LinkWeightType, LinkDictKeyType, LinkDictValueType]
2183):
2184 """
2185 A **link** can have a unique ID, a value, a weight and attached meta information as key-value-pairs. All links are
2186 directed.
2187 """
2189 def __init__(
2190 self,
2191 source: Vertex,
2192 destination: Vertex,
2193 linkID: Nullable[LinkIDType] = None,
2194 value: Nullable[LinkValueType] = None,
2195 weight: Nullable[LinkWeightType] = None,
2196 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None
2197 ) -> None:
2198 """
2199 Initialize a link between two vertices of different subgraphs.
2201 :param source: The source of the new link.
2202 :param destination: The destination of the new link.
2203 :param linkID: Optional, unique ID for the new link.
2204 :param value: Optional, value for the new v.
2205 :param weight: Optional, weight for the new link.
2206 :param keyValuePairs: Optional, mapping (dictionary) of key-value-pairs.
2207 :raises TypeError: If parameter 'weight' is not of the graph's link weight type.
2208 :raises NotInSameGraph: If source and destination vertex are in the same subgraph, where an edge is to be used.
2209 """
2210 if not isinstance(source, Vertex):
2211 ex = TypeError("Parameter 'source' is not of type 'Vertex'.")
2212 ex.add_note(f"Got type '{getFullyQualifiedName(source)}'.")
2213 raise ex
2214 if not isinstance(destination, Vertex):
2215 ex = TypeError("Parameter 'destination' is not of type 'Vertex'.")
2216 ex.add_note(f"Got type '{getFullyQualifiedName(destination)}'.")
2217 raise ex
2218 if linkID is not None and not isinstance(linkID, Hashable):
2219 ex = TypeError("Parameter 'linkID' is not of type 'LinkIDType'.")
2220 ex.add_note(f"Got type '{getFullyQualifiedName(linkID)}'.")
2221 raise ex
2222 # if value is not None and not isinstance(value, Vertex):
2223 # raise TypeError("Parameter 'value' is not of type 'EdgeValueType'.")
2224 if weight is not None and not isinstance(weight, (int, float)):
2225 ex = TypeError("Parameter 'weight' is not of type 'EdgeWeightType'.")
2226 ex.add_note(f"Got type '{getFullyQualifiedName(weight)}'.")
2227 raise ex
2228 if source._graph is not destination._graph:
2229 raise NotInSameGraph("Source vertex and destination vertex are not in same graph.")
2231 super().__init__(source, destination, linkID, value, weight, keyValuePairs)
2233 def Delete(self) -> None:
2234 """
2235 Delete this link from both of its vertices and from the graph and subgraphs it belongs to.
2236 """
2237 self._source._outboundLinks.remove(self)
2238 self._destination._inboundLinks.remove(self)
2240 self._Unregister()
2241 self._Delete()
2243 def _Unregister(self) -> None:
2244 """
2245 Remove this link from the graph or the subgraphs it was registered on.
2247 A link crossing a subgraph boundary is registered on both subgraphs, a link between two top-level vertices on
2248 the graph. Called by :meth:`Delete` and by :meth:`Vertex.Delete`, which unlinks the vertices itself.
2249 """
2250 if self._source._subgraph is None: 2250 ↛ 2251line 2250 didn't jump to line 2251 because the condition on line 2250 was never true
2251 containers = (self._source._graph, )
2252 else:
2253 containers = tuple(sg for sg in (self._source._subgraph, self._destination._subgraph) if sg is not None)
2255 for container in containers:
2256 if self._id is None:
2257 container._linksWithoutID.remove(self)
2258 else:
2259 del container._linksWithID[self._id]
2261 def _Delete(self) -> None:
2262 """
2263 Delete the link's attached attributes, after it was disconnected.
2264 """
2265 super().Delete()
2267 def Reverse(self) -> None:
2268 """Reverse the direction of this link."""
2269 self._source._outboundLinks.remove(self)
2270 self._source._inboundLinks.append(self)
2271 self._destination._inboundLinks.remove(self)
2272 self._destination._outboundLinks.append(self)
2274 super().Reverse()
2277@export
2278class BaseGraph(
2279 BaseWithName[GraphDictKeyType, GraphDictValueType],
2280 Generic[
2281 GraphDictKeyType, GraphDictValueType,
2282 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,
2283 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,
2284 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType
2285 ]
2286):
2287 """
2288 .. todo:: GRAPH::BaseGraph Needs documentation.
2289 """
2291 _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.
2292 _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.
2293 _edgesWithID: dict[EdgeIDType, Edge[EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType]] #: Edges with an ID, by ID.
2294 _edgesWithoutID: list[Edge[EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType]] #: Edges without an ID, in insertion order.
2295 _linksWithID: dict[EdgeIDType, Link[LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType]] #: Links between subgraphs with an ID, by ID.
2296 _linksWithoutID: list[Link[LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType]] #: Links between subgraphs without an ID, in insertion order.
2298 def __init__(
2299 self,
2300 name: Nullable[str] = None,
2301 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None
2302 #, vertices: Nullable[Iterable[Vertex]] = None) -> None:
2303 ) -> None:
2304 """
2305 .. todo:: GRAPH::BaseGraph::init Needs documentation.
2307 :param name: Optional, name of the graph.
2308 :param keyValuePairs: Optional, mapping (dictionary) of key-value-pairs.
2309 """
2310 super().__init__(name, keyValuePairs)
2312 self._verticesWithoutID = []
2313 self._verticesWithID = {}
2314 self._edgesWithoutID = []
2315 self._edgesWithID = {}
2316 self._linksWithoutID = []
2317 self._linksWithID = {}
2319 def __del__(self) -> None:
2320 """
2321 .. todo:: GRAPH::BaseGraph::del Needs documentation.
2322 """
2323 try:
2324 del self._verticesWithoutID
2325 del self._verticesWithID
2326 del self._edgesWithoutID
2327 del self._edgesWithID
2328 del self._linksWithoutID
2329 del self._linksWithID
2330 except AttributeError:
2331 pass
2333 super().__del__()
2335 @readonly
2336 def VertexCount(self) -> int:
2337 """Read-only property to return the number of vertices in this graph.
2339 :returns: The number of vertices in this graph."""
2340 return len(self._verticesWithoutID) + len(self._verticesWithID)
2342 @readonly
2343 def EdgeCount(self) -> int:
2344 """Read-only property to return the number of edges in this graph.
2346 :returns: The number of edges in this graph."""
2347 return len(self._edgesWithoutID) + len(self._edgesWithID)
2349 @readonly
2350 def LinkCount(self) -> int:
2351 """Read-only property to return the number of links in this graph.
2353 :returns: The number of links in this graph."""
2354 return len(self._linksWithoutID) + len(self._linksWithID)
2356 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]:
2357 """
2358 Iterate all or selected vertices of a graph.
2360 If parameter ``predicate`` is not None, the given filter function is used to skip vertices in the generator.
2362 :param predicate: Optional, filter function accepting any vertex and returning a boolean.
2363 :returns: A generator to iterate all vertices.
2364 """
2365 if predicate is None:
2366 yield from self._verticesWithoutID
2367 yield from self._verticesWithID.values()
2369 else:
2370 for vertex in self._verticesWithoutID:
2371 if predicate(vertex):
2372 yield vertex
2374 for vertex in self._verticesWithID.values():
2375 if predicate(vertex):
2376 yield vertex
2378 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]:
2379 """
2380 Iterate all or selected roots (vertices without inbound edges / without predecessors) of a graph.
2382 If parameter ``predicate`` is not None, the given filter function is used to skip vertices in the generator.
2384 :param predicate: Optional, filter function accepting any vertex and returning a boolean.
2385 :returns: A generator to iterate all vertices without inbound edges.
2387 .. seealso::
2389 :meth:`BaseGraph.IterateLeafs <pyTooling.Graph.BaseGraph.IterateLeafs>`
2390 |rarr| Iterate leafs of a graph.
2391 :meth:`Vertex.IsRoot <pyTooling.Graph.Vertex.IsRoot>`
2392 |rarr| Check if a vertex is a root vertex in the graph.
2393 :meth:`Vertex.IsLeaf <pyTooling.Graph.Vertex.IsLeaf>`
2394 |rarr| Check if a vertex is a leaf vertex in the graph.
2395 """
2396 if predicate is None:
2397 for vertex in self._verticesWithoutID:
2398 if len(vertex._inboundEdges) == 0:
2399 yield vertex
2401 for vertex in self._verticesWithID.values(): 2401 ↛ 2402line 2401 didn't jump to line 2402 because the loop on line 2401 never started
2402 if len(vertex._inboundEdges) == 0:
2403 yield vertex
2404 else:
2405 for vertex in self._verticesWithoutID:
2406 if len(vertex._inboundEdges) == 0 and predicate(vertex):
2407 yield vertex
2409 for vertex in self._verticesWithID.values(): 2409 ↛ 2410line 2409 didn't jump to line 2410 because the loop on line 2409 never started
2410 if len(vertex._inboundEdges) == 0 and predicate(vertex):
2411 yield vertex
2413 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]:
2414 """
2415 Iterate all or selected leafs (vertices without outbound edges / without successors) of a graph.
2417 If parameter ``predicate`` is not None, the given filter function is used to skip vertices in the generator.
2419 :param predicate: Optional, filter function accepting any vertex and returning a boolean.
2420 :returns: A generator to iterate all vertices without outbound edges.
2422 .. seealso::
2424 :meth:`BaseGraph.IterateRoots <pyTooling.Graph.BaseGraph.IterateRoots>`
2425 |rarr| Iterate roots of a graph.
2426 :meth:`Vertex.IsRoot <pyTooling.Graph.Vertex.IsRoot>`
2427 |rarr| Check if a vertex is a root vertex in the graph.
2428 :meth:`Vertex.IsLeaf <pyTooling.Graph.Vertex.IsLeaf>`
2429 |rarr| Check if a vertex is a leaf vertex in the graph.
2430 """
2431 if predicate is None:
2432 for vertex in self._verticesWithoutID:
2433 if len(vertex._outboundEdges) == 0:
2434 yield vertex
2436 for vertex in self._verticesWithID.values():
2437 if len(vertex._outboundEdges) == 0:
2438 yield vertex
2439 else:
2440 for vertex in self._verticesWithoutID:
2441 if len(vertex._outboundEdges) == 0 and predicate(vertex):
2442 yield vertex
2444 for vertex in self._verticesWithID.values():
2445 if len(vertex._outboundEdges) == 0 and predicate(vertex): 2445 ↛ 2446line 2445 didn't jump to line 2446 because the condition on line 2445 was never true
2446 yield vertex
2448 # 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]:
2449 # raise NotImplementedError()
2450 #
2451 # 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]:
2452 # raise NotImplementedError()
2454 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]:
2455 """
2456 Iterate all or selected vertices in topological order.
2458 If parameter ``predicate`` is not None, the given filter function is used to skip vertices in the generator.
2460 :param predicate: Optional, filter function accepting any vertex and returning a boolean.
2461 :returns: A generator to iterate all vertices in topological order.
2462 :raises CycleError: If the graph contains a cycle, so no topological order exists.
2463 :raises InternalError: If the algorithm's internal state became inconsistent.
2464 """
2465 outboundEdgeCounts = {}
2466 leafVertices = []
2468 for vertex in self._verticesWithoutID:
2469 if (count := len(vertex._outboundEdges)) == 0:
2470 leafVertices.append(vertex)
2471 else:
2472 outboundEdgeCounts[vertex] = count
2474 for vertex in self._verticesWithID.values():
2475 if (count := len(vertex._outboundEdges)) == 0:
2476 leafVertices.append(vertex)
2477 else:
2478 outboundEdgeCounts[vertex] = count
2480 if not leafVertices: 2480 ↛ 2481line 2480 didn't jump to line 2481 because the condition on line 2480 was never true
2481 raise CycleError("Graph has no leafs. Thus, no topological sorting exists.")
2483 overallCount = len(outboundEdgeCounts) + len(leafVertices)
2485 def removeVertex(vertex: Vertex):
2486 """
2487 Nested function removing a vertex from the counting, and queuing the vertices that became leafs.
2489 :param vertex: The vertex that was just yielded.
2490 """
2491 nonlocal overallCount
2492 overallCount -= 1
2493 for inboundEdge in vertex._inboundEdges:
2494 sourceVertex = inboundEdge.Source
2495 count = outboundEdgeCounts[sourceVertex] - 1
2496 outboundEdgeCounts[sourceVertex] = count
2497 if count == 0:
2498 leafVertices.append(sourceVertex)
2500 if predicate is None:
2501 for vertex in leafVertices:
2502 yield vertex
2504 removeVertex(vertex)
2505 else:
2506 for vertex in leafVertices:
2507 if predicate(vertex):
2508 yield vertex
2510 removeVertex(vertex)
2512 if overallCount == 0: 2512 ↛ 2514line 2512 didn't jump to line 2514 because the condition on line 2512 was always true
2513 return
2514 elif overallCount > 0:
2515 raise CycleError("Graph has remaining vertices. Thus, the graph has at least one cycle.")
2517 raise InternalError("Graph data structure is corrupted.") # pragma: no cover
2519 def IterateEdges(self, predicate: Nullable[Callable[[Edge], bool]] = None) -> Generator[Edge[EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType], None, None]:
2520 """
2521 Iterate all or selected edges of a graph.
2523 If parameter ``predicate`` is not None, the given filter function is used to skip edges in the generator.
2525 :param predicate: Optional, filter function accepting any edge and returning a boolean.
2526 :returns: A generator to iterate all edges.
2527 """
2528 if predicate is None:
2529 yield from self._edgesWithoutID
2530 yield from self._edgesWithID.values()
2532 else:
2533 for edge in self._edgesWithoutID:
2534 if predicate(edge):
2535 yield edge
2537 for edge in self._edgesWithID.values():
2538 if predicate(edge):
2539 yield edge
2541 def IterateLinks(self, predicate: Nullable[Callable[[Link], bool]] = None) -> Generator[Link[LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType], None, None]:
2542 """
2543 Iterate all or selected links of a graph.
2545 If parameter ``predicate`` is not None, the given filter function is used to skip links in the generator.
2547 :param predicate: Optional, filter function accepting any link and returning a boolean.
2548 :returns: A generator to iterate all links.
2549 """
2550 if predicate is None: 2550 ↛ 2555line 2550 didn't jump to line 2555 because the condition on line 2550 was always true
2551 yield from self._linksWithoutID
2552 yield from self._linksWithID.values()
2554 else:
2555 for link in self._linksWithoutID:
2556 if predicate(link):
2557 yield link
2559 for link in self._linksWithID.values():
2560 if predicate(link):
2561 yield link
2563 def ReverseEdges(self, predicate: Nullable[Callable[[Edge], bool]] = None) -> None:
2564 """
2565 Reverse all or selected edges of a graph.
2567 If parameter ``predicate`` is not None, the given filter function is used to skip edges.
2569 :param predicate: Optional, filter function accepting any edge and returning a boolean.
2570 """
2571 if predicate is None:
2572 for edge in self._edgesWithoutID:
2573 swap = edge._source
2574 edge._source = edge._destination
2575 edge._destination = swap
2577 for edge in self._edgesWithID.values():
2578 swap = edge._source
2579 edge._source = edge._destination
2580 edge._destination = swap
2582 for vertex in self._verticesWithoutID:
2583 swap = vertex._inboundEdges
2584 vertex._inboundEdges = vertex._outboundEdges
2585 vertex._outboundEdges = swap
2587 for vertex in self._verticesWithID.values():
2588 swap = vertex._inboundEdges
2589 vertex._inboundEdges = vertex._outboundEdges
2590 vertex._outboundEdges = swap
2591 else:
2592 for edge in self._edgesWithoutID:
2593 if predicate(edge):
2594 edge.Reverse()
2596 for edge in self._edgesWithID.values():
2597 if predicate(edge):
2598 edge.Reverse()
2600 def ReverseLinks(self, predicate: Nullable[Callable[[Link], bool]] = None) -> None:
2601 """
2602 Reverse all or selected links of a graph.
2604 If parameter ``predicate`` is not None, the given filter function is used to skip links.
2606 :param predicate: Optional, filter function accepting any link and returning a boolean.
2607 """
2608 if predicate is None:
2609 for link in self._linksWithoutID:
2610 swap = link._source
2611 link._source = link._destination
2612 link._destination = swap
2614 for link in self._linksWithID.values():
2615 swap = link._source
2616 link._source = link._destination
2617 link._destination = swap
2619 for vertex in self._verticesWithoutID:
2620 swap = vertex._inboundLinks
2621 vertex._inboundLinks = vertex._outboundLinks
2622 vertex._outboundLinks = swap
2624 for vertex in self._verticesWithID.values():
2625 swap = vertex._inboundLinks
2626 vertex._inboundLinks = vertex._outboundLinks
2627 vertex._outboundLinks = swap
2628 else:
2629 for link in self._linksWithoutID:
2630 if predicate(link):
2631 link.Reverse()
2633 for link in self._linksWithID.values():
2634 if predicate(link):
2635 link.Reverse()
2637 def RemoveEdges(self, predicate: Nullable[Callable[[Edge], bool]] = None) -> None:
2638 """
2639 Remove all or selected edges of a graph.
2641 If parameter ``predicate`` is not None, the given filter function is used to skip edges.
2643 :param predicate: Optional, filter function accepting any edge and returning a boolean.
2644 """
2645 if predicate is None:
2646 for edge in self._edgesWithoutID:
2647 edge._Delete()
2649 for edge in self._edgesWithID.values():
2650 edge._Delete()
2652 self._edgesWithoutID = []
2653 self._edgesWithID = {}
2655 for vertex in self._verticesWithoutID:
2656 vertex._inboundEdges = []
2657 vertex._outboundEdges = []
2659 for vertex in self._verticesWithID.values():
2660 vertex._inboundEdges = []
2661 vertex._outboundEdges = []
2663 else:
2664 delEdges = [edge for edge in self._edgesWithID.values() if predicate(edge)]
2665 for edge in delEdges:
2666 del self._edgesWithID[edge._id]
2668 edge._source._outboundEdges.remove(edge)
2669 edge._destination._inboundEdges.remove(edge)
2670 edge._Delete()
2672 for edge in self._edgesWithoutID:
2673 if predicate(edge):
2674 self._edgesWithoutID.remove(edge)
2676 edge._source._outboundEdges.remove(edge)
2677 edge._destination._inboundEdges.remove(edge)
2678 edge._Delete()
2680 def RemoveLinks(self, predicate: Nullable[Callable[[Link], bool]] = None) -> None:
2681 """
2682 Remove all or selected links of a graph.
2684 If parameter ``predicate`` is not None, the given filter function is used to skip links.
2686 :param predicate: Optional, filter function accepting any link and returning a boolean.
2687 """
2688 if predicate is None:
2689 for link in self._linksWithoutID:
2690 link._Delete()
2692 for link in self._linksWithID.values():
2693 link._Delete()
2695 self._linksWithoutID = []
2696 self._linksWithID = {}
2698 for vertex in self._verticesWithoutID:
2699 vertex._inboundLinks = []
2700 vertex._outboundLinks = []
2702 for vertex in self._verticesWithID.values():
2703 vertex._inboundLinks = []
2704 vertex._outboundLinks = []
2706 else:
2707 delLinks = [link for link in self._linksWithID.values() if predicate(link)]
2708 for link in delLinks:
2709 del self._linksWithID[link._id]
2711 link._source._outboundLinks.remove(link)
2712 link._destination._inboundLinks.remove(link)
2713 link._Delete()
2715 for link in self._linksWithoutID:
2716 if predicate(link):
2717 self._linksWithoutID.remove(link)
2719 link._source._outboundLinks.remove(link)
2720 link._destination._inboundLinks.remove(link)
2721 link._Delete()
2723 def HasCycle(self) -> bool:
2724 """
2725 Check if the graph contains at least one cycle.
2727 The graph is traversed depth-first from every unvisited vertex; a vertex reached again while it is still on the
2728 current path closes a cycle.
2730 :returns: ``True``, if the graph contains a cycle.
2731 :raises InternalError: If the graph's data structure is corrupted.
2732 """
2733 # IsAcyclic ?
2735 # Handle trivial case if graph is empty
2736 if len(self._verticesWithID) + len(self._verticesWithoutID) == 0: 2736 ↛ 2737line 2736 didn't jump to line 2737 because the condition on line 2736 was never true
2737 return False
2739 outboundEdgeCounts = {}
2740 leafVertices = []
2742 for vertex in self._verticesWithoutID:
2743 if (count := len(vertex._outboundEdges)) == 0:
2744 leafVertices.append(vertex)
2745 else:
2746 outboundEdgeCounts[vertex] = count
2748 for vertex in self._verticesWithID.values():
2749 if (count := len(vertex._outboundEdges)) == 0:
2750 leafVertices.append(vertex)
2751 else:
2752 outboundEdgeCounts[vertex] = count
2754 # If there are no leafs, then each vertex has at least one inbound and one outbound edges. Thus, there is a cycle.
2755 if not leafVertices: 2755 ↛ 2756line 2755 didn't jump to line 2756 because the condition on line 2755 was never true
2756 return True
2758 overallCount = len(outboundEdgeCounts) + len(leafVertices)
2760 for vertex in leafVertices:
2761 overallCount -= 1
2762 for inboundEdge in vertex._inboundEdges:
2763 sourceVertex = inboundEdge.Source
2764 count = outboundEdgeCounts[sourceVertex] - 1
2765 outboundEdgeCounts[sourceVertex] = count
2766 if count == 0:
2767 leafVertices.append(sourceVertex)
2769 # If all vertices were processed, no cycle exists.
2770 if overallCount == 0:
2771 return False
2772 # If there are remaining vertices, then a cycle exists.
2773 elif overallCount > 0:
2774 return True
2776 raise InternalError("Graph data structure is corrupted.") # pragma: no cover
2779@export
2780class Subgraph(
2781 BaseGraph[
2782 SubgraphDictKeyType, SubgraphDictValueType,
2783 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,
2784 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,
2785 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType
2786 ],
2787 Generic[
2788 SubgraphDictKeyType, SubgraphDictValueType,
2789 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,
2790 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,
2791 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType
2792 ]
2793):
2794 """
2795 .. todo:: GRAPH::Subgraph Needs documentation.
2796 """
2798 _graph: Graph #: Reference to the graph this subgraph is part of.
2800 def __init__(
2801 self,
2802 graph: Graph,
2803 name: Nullable[str] = None,
2804 # vertices: Nullable[Iterable[Vertex]] = None,
2805 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None
2806 ) -> None:
2807 """
2808 Initialize a subgraph and register it at its graph.
2810 :param graph: Optional, the reference to the graph.
2811 :param name: Optional, name of the new sub-graph.
2812 :param keyValuePairs: Optional, mapping (dictionary) of key-value-pairs.
2813 :raises ValueError: If parameter 'graph' is None.
2814 :raises TypeError: If parameter 'graph' is not of type :class:`Graph`.
2815 """
2816 if graph is None: 2816 ↛ 2817line 2816 didn't jump to line 2817 because the condition on line 2816 was never true
2817 raise ValueError("Parameter 'graph' is None.")
2818 if not isinstance(graph, Graph): 2818 ↛ 2819line 2818 didn't jump to line 2819 because the condition on line 2818 was never true
2819 ex = TypeError("Parameter 'graph' is not of type 'Graph'.")
2820 ex.add_note(f"Got type '{getFullyQualifiedName(graph)}'.")
2821 raise ex
2823 super().__init__(name, keyValuePairs)
2825 graph._subgraphs.add(self)
2827 self._graph = graph
2829 def __del__(self) -> None:
2830 """
2831 .. todo:: GRAPH::Subgraph::del Needs documentation.
2832 """
2833 super().__del__()
2835 @readonly
2836 def Graph(self) -> Graph:
2837 """
2838 Read-only property to access the graph, this subgraph is associated to (:attr:`_graph`).
2840 :returns: The graph this subgraph is associated to.
2841 """
2842 return self._graph
2844 def __str__(self) -> str:
2845 """
2846 Return a string representation of this subgraph.
2848 :returns: The subgraph's name, or ``"Unnamed subgraph"`` if it has none.
2849 """
2850 return self._name if self._name is not None else "Unnamed subgraph"
2853@export
2854class View(
2855 BaseWithVertices[
2856 ViewDictKeyType, ViewDictValueType,
2857 GraphDictKeyType, GraphDictValueType,
2858 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,
2859 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,
2860 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType
2861 ],
2862 Generic[
2863 ViewDictKeyType, ViewDictValueType,
2864 GraphDictKeyType, GraphDictValueType,
2865 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,
2866 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,
2867 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType
2868 ]
2869):
2870 """
2871 .. 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.
2896 """
2897 super().__del__()
2899 def __str__(self) -> str:
2900 """
2901 Return a string representation of this view.
2903 :returns: The view's name, or ``"Unnamed view"`` if it has none.
2904 """
2905 return self._name if self._name is not None else "Unnamed view"
2908@export
2909class Component(
2910 BaseWithVertices[
2911 ComponentDictKeyType, ComponentDictValueType,
2912 GraphDictKeyType, GraphDictValueType,
2913 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,
2914 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,
2915 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType
2916 ],
2917 Generic[
2918 ComponentDictKeyType, ComponentDictValueType,
2919 GraphDictKeyType, GraphDictValueType,
2920 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,
2921 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,
2922 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType
2923 ]
2924):
2925 """
2926 .. todo:: GRAPH::Component Needs documentation.
2927 """
2929 def __init__(
2930 self,
2931 graph: Graph,
2932 name: Nullable[str] = None,
2933 vertices: Nullable[Iterable[Vertex]] = None,
2934 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None
2935 ) -> None:
2936 """
2937 Initialize a component of a graph and register it at that graph.
2939 :param graph: Optional, the reference to the graph.
2940 :param name: Optional, name of the new component.
2941 :param vertices: Optional, list of vertices in the new component.
2942 :param keyValuePairs: Optional, mapping (dictionary) of key-value-pairs.
2943 """
2944 super().__init__(graph, name, vertices, keyValuePairs)
2946 graph._components.add(self)
2948 def __del__(self) -> None:
2949 """
2950 .. todo:: GRAPH::Component::del Needs documentation.
2951 """
2952 super().__del__()
2954 def __str__(self) -> str:
2955 """
2956 Return a string representation of this component.
2958 :returns: The component's name, or ``"Unnamed component"`` if it has none.
2959 """
2960 return self._name if self._name is not None else "Unnamed component"
2963@export
2964class Graph(
2965 BaseGraph[
2966 GraphDictKeyType, GraphDictValueType,
2967 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,
2968 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,
2969 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType
2970 ],
2971 Generic[
2972 GraphDictKeyType, GraphDictValueType,
2973 ComponentDictKeyType, ComponentDictValueType,
2974 SubgraphDictKeyType, SubgraphDictValueType,
2975 ViewDictKeyType, ViewDictValueType,
2976 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,
2977 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,
2978 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType
2979 ]
2980):
2981 """
2982 A **graph** data structure is represented by an instance of :class:`~pyTooling.Graph.Graph` holding references to
2983 all nodes. Nodes are instances of :class:`~pyTooling.Graph.Vertex` classes and directed links between nodes are
2984 made of :class:`~pyTooling.Graph.Edge` instances. A graph can have attached meta information as key-value-pairs.
2985 """
2986 _subgraphs: set[Subgraph[SubgraphDictKeyType, SubgraphDictValueType, VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType, EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType, LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType]] #: Subgraphs of this graph.
2987 _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.
2988 _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.
2990 def __init__(
2991 self,
2992 name: Nullable[str] = None,
2993 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None
2994 ) -> None:
2995 """
2996 .. todo:: GRAPH::Graph::init Needs documentation.
2998 :param name: Optional, name of the new graph.
2999 :param keyValuePairs: Optional, mapping (dictionary) of key-value-pairs.#
3000 """
3001 super().__init__(name, keyValuePairs)
3003 self._subgraphs = set()
3004 self._views = set()
3005 self._components = set()
3007 def __del__(self) -> None:
3008 """
3009 .. todo:: GRAPH::Graph::del Needs documentation.
3010 """
3011 try:
3012 del self._subgraphs
3013 del self._views
3014 del self._components
3015 except AttributeError:
3016 pass
3018 super().__del__()
3020 @readonly
3021 def Subgraphs(self) -> set[Subgraph]:
3022 """Read-only property to access the subgraphs in this graph (:attr:`_subgraphs`).
3024 :returns: The set of subgraphs in this graph."""
3025 return self._subgraphs
3027 @readonly
3028 def Views(self) -> set[View]:
3029 """Read-only property to access the views in this graph (:attr:`_views`).
3031 :returns: The set of views in this graph."""
3032 return self._views
3034 @readonly
3035 def Components(self) -> set[Component]:
3036 """Read-only property to access the components in this graph (:attr:`_components`).
3038 :returns: The set of components in this graph."""
3039 return self._components
3041 @readonly
3042 def SubgraphCount(self) -> int:
3043 """Read-only property to return the number of subgraphs in this graph.
3045 :returns: The number of subgraphs in this graph."""
3046 return len(self._subgraphs)
3048 @readonly
3049 def ViewCount(self) -> int:
3050 """Read-only property to return the number of views in this graph.
3052 :returns: The number of views in this graph."""
3053 return len(self._views)
3055 @readonly
3056 def ComponentCount(self) -> int:
3057 """Read-only property to return the number of components in this graph.
3059 :returns: The number of components in this graph."""
3060 return len(self._components)
3062 def __iter__(self) -> typing_Iterator[Vertex[GraphDictKeyType, GraphDictValueType, VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType, EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType, LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType]]:
3063 """
3064 Iterate all vertices of this graph.
3066 :returns: An iterator over the vertices without an ID, followed by those with one.
3067 """
3068 def gen():
3069 """
3070 Nested generator function chaining the vertices without an ID and those with one.
3072 :returns: A generator yielding every vertex of the graph.
3073 """
3074 yield from self._verticesWithoutID
3075 yield from self._verticesWithID
3076 return iter(gen())
3078 def HasVertexByID(self, vertexID: Nullable[VertexIDType]) -> bool:
3079 """
3080 Check if a vertex with the given ID exists in this graph.
3082 :param vertexID: Optional, ID to look for, or ``None`` for a vertex without an ID.
3083 :returns: ``True``, if such a vertex exists.
3084 """
3085 if vertexID is None:
3086 return len(self._verticesWithoutID) >= 1
3087 else:
3088 return vertexID in self._verticesWithID
3090 def HasVertexByValue(self, value: Nullable[VertexValueType]) -> bool:
3091 """
3092 Check if a vertex carrying the given value exists in this graph.
3094 :param value: Optional, value to look for.
3095 :returns: ``True``, if such a vertex exists.
3096 """
3097 return any(vertex._value == value for vertex in chain(self._verticesWithoutID, self._verticesWithID.values()))
3099 def GetVertexByID(self, vertexID: Nullable[VertexIDType]) -> Vertex:
3100 """
3101 Return the vertex with the given ID.
3103 A vertex created without an ID can be looked up with ``None``, provided it is the only such vertex.
3105 :param vertexID: Optional, ID of the vertex to return, or ``None`` for the vertex without an ID.
3106 :returns: The vertex with that ID.
3107 :raises KeyError: If no vertex has that ID, or if more than one vertex matches ``None``.
3108 """
3109 if vertexID is None:
3110 if (l := len(self._verticesWithoutID)) == 1:
3111 return self._verticesWithoutID[0]
3112 elif l == 0:
3113 raise KeyError("Found no vertex with ID `None`.")
3114 else:
3115 raise KeyError("Found multiple vertices with ID `None`.")
3116 else:
3117 return self._verticesWithID[vertexID]
3119 def GetVertexByValue(self, value: Nullable[VertexValueType]) -> Vertex:
3120 """
3121 Return the vertex carrying the given value.
3123 :param value: Optional, value of the vertex to return.
3124 :returns: The vertex with that value.
3125 :raises KeyError: If no vertex carries that value, or if more than one vertex does.
3126 """
3127 # FIXME: optimize: iterate only until first item is found and check for a second to produce error
3128 vertices = [vertex for vertex in chain(self._verticesWithoutID, self._verticesWithID.values()) if vertex._value == value]
3129 if (l := len(vertices)) == 1:
3130 return vertices[0]
3131 elif l == 0:
3132 raise KeyError(f"Found no vertex with Value == `{value}`.")
3133 else:
3134 raise KeyError(f"Found multiple vertices with Value == `{value}`.")
3136 def CopyGraph(self) -> Graph:
3137 """
3138 Create a copy of this graph.
3140 :returns: A new graph with copies of this graph's vertices and edges.
3141 :raises NotImplementedError: Copying a whole graph is not implemented yet.
3142 """
3143 raise NotImplementedError()
3145 def CopyVertices(self, predicate: Nullable[Callable[[Vertex], bool]] = None, copyGraphDict: bool = True, copyVertexDict: bool = True) -> Graph:
3146 """
3147 Create a new graph and copy all or selected vertices of the original graph.
3149 If parameter ``predicate`` is not None, the given filter function is used to skip vertices.
3151 :param predicate: Optional, filter function accepting any vertex and returning a boolean.
3152 :param copyGraphDict: Optional, if ``True``, copy all graph attached attributes into the new graph.
3153 :param copyVertexDict: Optional, if ``True``, copy all vertex attached attributes into the new vertices.
3154 :returns: A new graph with copies of the selected vertices.
3155 """
3156 graph = Graph(self._name)
3157 if copyGraphDict:
3158 graph._dict = self._dict.copy()
3160 if predicate is None:
3161 for vertex in self._verticesWithoutID:
3162 v = Vertex(None, vertex._value, graph=graph)
3163 if copyVertexDict:
3164 v._dict = vertex._dict.copy()
3166 for vertexID, vertex in self._verticesWithID.items():
3167 v = Vertex(vertexID, vertex._value, graph=graph)
3168 if copyVertexDict:
3169 v._dict = vertex._dict.copy()
3170 else:
3171 for vertex in self._verticesWithoutID:
3172 if predicate(vertex):
3173 v = Vertex(None, vertex._value, graph=graph)
3174 if copyVertexDict: 3174 ↛ 3171line 3174 didn't jump to line 3171 because the condition on line 3174 was always true
3175 v._dict = vertex._dict.copy()
3177 for vertexID, vertex in self._verticesWithID.items():
3178 if predicate(vertex):
3179 v = Vertex(vertexID, vertex._value, graph=graph)
3180 if copyVertexDict: 3180 ↛ 3181line 3180 didn't jump to line 3181 because the condition on line 3180 was never true
3181 v._dict = vertex._dict.copy()
3183 return graph
3185 # class Iterator():
3186 # visited = [False for _ in range(self.__len__())]
3188 # def CheckForNegativeCycles(self):
3189 # raise NotImplementedError()
3190 # # Bellman-Ford
3191 # # Floyd-Warshall
3192 #
3193 # def IsStronglyConnected(self):
3194 # raise NotImplementedError()
3195 #
3196 # def GetStronglyConnectedComponents(self):
3197 # raise NotImplementedError()
3198 # # Tarjan's and Kosaraju's algorithm
3199 #
3200 # def TravelingSalesmanProblem(self):
3201 # raise NotImplementedError()
3202 # # Held-Karp
3203 # # branch and bound
3204 #
3205 # def GetBridges(self):
3206 # raise NotImplementedError()
3207 #
3208 # def GetArticulationPoints(self):
3209 # raise NotImplementedError()
3210 #
3211 # def MinimumSpanningTree(self):
3212 # raise NotImplementedError()
3213 # # Kruskal
3214 # # Prim's algorithm
3215 # # Buruvka's algorithm
3217 def __repr__(self) -> str:
3218 """
3219 Return a detailed string representation of this graph.
3221 :returns: The graph's name and its vertex and edge counts.
3222 """
3223 statistics = f", vertices: {self.VertexCount}, edges: {self.EdgeCount}"
3224 if self._name is None:
3225 return f"<graph: unnamed graph{statistics}>"
3226 else:
3227 return f"<graph: '{self._name}'{statistics}>"
3229 def __str__(self) -> str:
3230 """
3231 Return a string representation of this graph.
3233 :returns: The graph's name, or ``"Unnamed graph"`` if it has none.
3234 """
3235 if self._name is None:
3236 return "Graph: unnamed graph"
3237 else:
3238 return f"Graph: '{self._name}'"