Coverage for pyTooling/Graph/__init__.py: 76%
1212 statements
« prev ^ index » next coverage.py v7.11.0, created at 2025-10-24 22:21 +0000
1# ==================================================================================================================== #
2# _____ _ _ ____ _ #
3# _ __ _ |_ _|__ ___ | (_)_ __ __ _ / ___|_ __ __ _ _ __ | |__ #
4# | '_ \| | | || |/ _ \ / _ \| | | '_ \ / _` || | _| '__/ _` | '_ \| '_ \ #
5# | |_) | |_| || | (_) | (_) | | | | | | (_| || |_| | | | (_| | |_) | | | | #
6# | .__/ \__, ||_|\___/ \___/|_|_|_| |_|\__, (_)____|_| \__,_| .__/|_| |_| #
7# |_| |___/ |___/ |_| #
8# ==================================================================================================================== #
9# Authors: #
10# Patrick Lehmann #
11# #
12# License: #
13# ==================================================================================================================== #
14# Copyright 2017-2025 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;
54"""
55import heapq
56from collections import deque
57from itertools import chain
58from sys import version_info # needed for versions before Python 3.11
59from typing import TypeVar, Generic, List, Tuple, Dict, Set, Deque, Union, Optional as Nullable
60from typing import Callable, Iterator as typing_Iterator, Generator, Iterable, Mapping, Hashable
62try:
63 from pyTooling.Decorators import export, readonly
64 from pyTooling.MetaClasses import ExtendedType
65 from pyTooling.Exceptions import ToolingException
66 from pyTooling.Common import getFullyQualifiedName
67 from pyTooling.Tree import Node
68except (ImportError, ModuleNotFoundError): # pragma: no cover
69 print("[pyTooling.Graph] Could not import from 'pyTooling.*'!")
71 try:
72 from Decorators import export, readonly
73 from MetaClasses import ExtendedType, mixin
74 from Exceptions import ToolingException
75 from Common import getFullyQualifiedName
76 from Tree import Node
77 except (ImportError, ModuleNotFoundError) as ex: # pragma: no cover
78 print("[pyTooling.Graph] Could not import directly!")
79 raise ex
82DictKeyType = TypeVar("DictKeyType", bound=Hashable)
83"""A type variable for dictionary keys."""
85DictValueType = TypeVar("DictValueType")
86"""A type variable for dictionary values."""
88IDType = TypeVar("IDType", bound=Hashable)
89"""A type variable for an ID."""
91WeightType = TypeVar("WeightType", bound=Union[int, float])
92"""A type variable for a weight."""
94ValueType = TypeVar("ValueType")
95"""A type variable for a value."""
97VertexIDType = TypeVar("VertexIDType", bound=Hashable)
98"""A type variable for a vertex's ID."""
100VertexWeightType = TypeVar("VertexWeightType", bound=Union[int, float])
101"""A type variable for a vertex's weight."""
103VertexValueType = TypeVar("VertexValueType")
104"""A type variable for a vertex's value."""
106VertexDictKeyType = TypeVar("VertexDictKeyType", bound=Hashable)
107"""A type variable for a vertex's dictionary keys."""
109VertexDictValueType = TypeVar("VertexDictValueType")
110"""A type variable for a vertex's dictionary values."""
112EdgeIDType = TypeVar("EdgeIDType", bound=Hashable)
113"""A type variable for an edge's ID."""
115EdgeWeightType = TypeVar("EdgeWeightType", bound=Union[int, float])
116"""A type variable for an edge's weight."""
118EdgeValueType = TypeVar("EdgeValueType")
119"""A type variable for an edge's value."""
121EdgeDictKeyType = TypeVar("EdgeDictKeyType", bound=Hashable)
122"""A type variable for an edge's dictionary keys."""
124EdgeDictValueType = TypeVar("EdgeDictValueType")
125"""A type variable for an edge's dictionary values."""
127LinkIDType = TypeVar("LinkIDType", bound=Hashable)
128"""A type variable for an link's ID."""
130LinkWeightType = TypeVar("LinkWeightType", bound=Union[int, float])
131"""A type variable for an link's weight."""
133LinkValueType = TypeVar("LinkValueType")
134"""A type variable for an link's value."""
136LinkDictKeyType = TypeVar("LinkDictKeyType", bound=Hashable)
137"""A type variable for an link's dictionary keys."""
139LinkDictValueType = TypeVar("LinkDictValueType")
140"""A type variable for an link's dictionary values."""
142ComponentDictKeyType = TypeVar("ComponentDictKeyType", bound=Hashable)
143"""A type variable for a component's dictionary keys."""
145ComponentDictValueType = TypeVar("ComponentDictValueType")
146"""A type variable for a component's dictionary values."""
148SubgraphDictKeyType = TypeVar("SubgraphDictKeyType", bound=Hashable)
149"""A type variable for a component's dictionary keys."""
151SubgraphDictValueType = TypeVar("SubgraphDictValueType")
152"""A type variable for a component's dictionary values."""
154ViewDictKeyType = TypeVar("ViewDictKeyType", bound=Hashable)
155"""A type variable for a component's dictionary keys."""
157ViewDictValueType = TypeVar("ViewDictValueType")
158"""A type variable for a component's dictionary values."""
160GraphDictKeyType = TypeVar("GraphDictKeyType", bound=Hashable)
161"""A type variable for a graph's dictionary keys."""
163GraphDictValueType = TypeVar("GraphDictValueType")
164"""A type variable for a graph's dictionary values."""
167@export
168class GraphException(ToolingException):
169 """Base exception of all exceptions raised by :mod:`pyTooling.Graph`."""
172@export
173class InternalError(GraphException):
174 """
175 The exception is raised when a data structure corruption is detected.
177 .. danger::
179 This exception should never be raised.
181 If so, please create an issue at GitHub so the data structure corruption can be investigated and fixed. |br|
182 `⇒ Bug Tracker at GitHub <https://github.com/pyTooling/pyTooling/issues>`__
183 """
186@export
187class NotInSameGraph(GraphException):
188 """The exception is raised when creating an edge between two vertices, but these are not in the same graph."""
191@export
192class DuplicateVertexError(GraphException):
193 """The exception is raised when the vertex already exists in the graph."""
196@export
197class DuplicateEdgeError(GraphException):
198 """The exception is raised when the edge already exists in the graph."""
201@export
202class DestinationNotReachable(GraphException):
203 """The exception is raised when a destination vertex is not reachable."""
206@export
207class NotATreeError(GraphException):
208 """
209 The exception is raised when a subgraph is not a tree.
211 Either the subgraph has a cycle (backward edge) or links between branches (cross-edge).
212 """
215@export
216class CycleError(GraphException):
217 """The exception is raised when a not permitted cycle is found."""
220@export
221class Base(
222 Generic[DictKeyType, DictValueType],
223 metaclass=ExtendedType, slots=True
224):
225 _dict: Dict[DictKeyType, DictValueType] #: A dictionary to store arbitrary key-value-pairs.
227 def __init__(
228 self,
229 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None
230 ) -> None:
231 """
232 .. todo:: GRAPH::Base::init Needs documentation.
234 :param keyValuePairs: The optional mapping (dictionary) of key-value-pairs.
235 """
236 self._dict = {key: value for key, value in keyValuePairs.items()} if keyValuePairs is not None else {}
238 def __del__(self):
239 """
240 .. todo:: GRAPH::Base::del Needs documentation.
242 """
243 try:
244 del self._dict
245 except AttributeError:
246 pass
248 def Delete(self) -> None:
249 self._dict = None
251 def __getitem__(self, key: DictKeyType) -> DictValueType:
252 """
253 Read a vertex's attached attributes (key-value-pairs) by key.
255 :param key: The key to look for.
256 :returns: The value associated to the given key.
257 """
258 return self._dict[key]
260 def __setitem__(self, key: DictKeyType, value: DictValueType) -> None:
261 """
262 Create or update a vertex's attached attributes (key-value-pairs) by key.
264 If a key doesn't exist yet, a new key-value-pair is created.
266 :param key: The key to create or update.
267 :param value: The value to associate to the given key.
268 """
269 self._dict[key] = value
271 def __delitem__(self, key: DictKeyType) -> None:
272 """
273 Remove an entry from vertex's attached attributes (key-value-pairs) by key.
275 :param key: The key to remove.
276 :raises KeyError: If key doesn't exist in the vertex's attributes.
277 """
278 del self._dict[key]
280 def __contains__(self, key: DictKeyType) -> bool:
281 """
282 Checks if the key is an attached attribute (key-value-pairs) on this vertex.
284 :param key: The key to check.
285 :returns: ``True``, if the key is an attached attribute.
286 """
287 return key in self._dict
289 def __len__(self) -> int:
290 """
291 Returns the number of attached attributes (key-value-pairs) on this vertex.
293 :returns: Number of attached attributes.
294 """
295 return len(self._dict)
298@export
299class BaseWithIDValueAndWeight(
300 Base[DictKeyType, DictValueType],
301 Generic[IDType, ValueType, WeightType, DictKeyType, DictValueType]
302):
303 _id: Nullable[IDType] #: Field storing the object's Identifier.
304 _value: Nullable[ValueType] #: Field storing the object's value of any type.
305 _weight: Nullable[WeightType] #: Field storing the object's weight.
307 def __init__(
308 self,
309 identifier: Nullable[IDType] = None,
310 value: Nullable[ValueType] = None,
311 weight: Nullable[WeightType] = None,
312 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None
313 ) -> None:
314 """
315 .. todo:: GRAPH::Vertex::init Needs documentation.
317 :param identifier: The optional unique ID.
318 :param value: The optional value.
319 :param weight: The optional weight.
320 :param keyValuePairs: The optional mapping (dictionary) of key-value-pairs.
321 """
322 super().__init__(keyValuePairs)
324 self._id = identifier
325 self._value = value
326 self._weight = weight
328 @readonly
329 def ID(self) -> Nullable[IDType]:
330 """
331 Read-only property to access the unique ID (:attr:`_id`).
333 If no ID was given at creation time, ID returns ``None``.
335 :returns: Unique ID, if ID was given at creation time, else ``None``.
336 """
337 return self._id
339 @property
340 def Value(self) -> ValueType:
341 """
342 Property to get and set the value (:attr:`_value`).
344 :returns: The value.
345 """
346 return self._value
348 @Value.setter
349 def Value(self, value: ValueType) -> None:
350 self._value = value
352 @property
353 def Weight(self) -> Nullable[EdgeWeightType]:
354 """
355 Property to get and set the weight (:attr:`_weight`) of an edge.
357 :returns: The weight of an edge.
358 """
359 return self._weight
361 @Weight.setter
362 def Weight(self, value: Nullable[EdgeWeightType]) -> None:
363 self._weight = value
366@export
367class BaseWithName(
368 Base[DictKeyType, DictValueType],
369 Generic[DictKeyType, DictValueType]
370):
371 _name: Nullable[str] #: Field storing the object's name.
373 def __init__(
374 self,
375 name: Nullable[str] = None,
376 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None,
377 ) -> None:
378 """
379 .. todo:: GRAPH::BaseWithName::init Needs documentation.
381 :param name: The optional name.
382 :param keyValuePairs: The optional mapping (dictionary) of key-value-pairs.
383 """
384 if name is not None and not isinstance(name, str):
385 ex = TypeError("Parameter 'name' is not of type 'str'.")
386 ex.add_note(f"Got type '{getFullyQualifiedName(name)}'.")
387 raise ex
389 super().__init__(keyValuePairs)
391 self._name = name
393 @property
394 def Name(self) -> Nullable[str]:
395 """
396 Property to get and set the name (:attr:`_name`).
398 :returns: The value of a component.
399 """
400 return self._name
402 @Name.setter
403 def Name(self, value: str) -> None:
404 if not isinstance(value, str):
405 ex = TypeError("Name is not of type 'str'.")
406 ex.add_note(f"Got type '{getFullyQualifiedName(value)}'.")
407 raise ex
409 self._name = value
412@export
413class BaseWithVertices(
414 BaseWithName[DictKeyType, DictValueType],
415 Generic[
416 DictKeyType, DictValueType,
417 GraphDictKeyType, GraphDictValueType,
418 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,
419 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,
420 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType
421 ]
422):
423 _graph: 'Graph[GraphDictKeyType, GraphDictValueType,' \
424 'VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,' \
425 'EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,' \
426 'LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType' \
427 ']' #: Field storing a reference to the graph.
428 _vertices: Set['Vertex[GraphDictKeyType, GraphDictValueType,'
429 'VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,'
430 'EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,'
431 'LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType'
432 ']'] #: Field storing a set of vertices.
434 def __init__(
435 self,
436 graph: 'Graph',
437 name: Nullable[str] = None,
438 vertices: Nullable[Iterable['Vertex']] = None,
439 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None
440 ) -> None:
441 """
442 .. todo:: GRAPH::Component::init Needs documentation.
444 :param graph: The reference to the graph.
445 :param name: The optional name.
446 :param vertices: The optional list of vertices.
447 :param keyValuePairs: The optional mapping (dictionary) of key-value-pairs.
448 """
449 if graph is None: 449 ↛ 450line 449 didn't jump to line 450 because the condition on line 449 was never true
450 raise ValueError("Parameter 'graph' is None.")
451 elif not isinstance(graph, Graph): 451 ↛ 452line 451 didn't jump to line 452 because the condition on line 451 was never true
452 ex = TypeError("Parameter 'graph' is not of type 'Graph'.")
453 ex.add_note(f"Got type '{getFullyQualifiedName(graph)}'.")
454 raise ex
456 super().__init__(name, keyValuePairs)
458 self._graph = graph
459 self._vertices = set() if vertices is None else {v for v in vertices}
461 def __del__(self):
462 """
463 .. todo:: GRAPH::BaseWithVertices::del Needs documentation.
465 """
466 try:
467 del self._vertices
468 except AttributeError:
469 pass
471 super().__del__()
473 @readonly
474 def Graph(self) -> 'Graph':
475 """
476 Read-only property to access the graph, this object is associated to (:attr:`_graph`).
478 :returns: The graph this object is associated to.
479 """
480 return self._graph
482 @readonly
483 def Vertices(self) -> Set['Vertex']:
484 """
485 Read-only property to access the vertices in this component (:attr:`_vertices`).
487 :returns: The set of vertices in this component.
488 """
489 return self._vertices
491 @readonly
492 def VertexCount(self) -> int:
493 """
494 Read-only property to access the number of vertices referenced by this object.
496 :returns: The number of vertices this object references.
497 """
498 return len(self._vertices)
501@export
502class Vertex(
503 BaseWithIDValueAndWeight[VertexIDType, VertexValueType, VertexWeightType, VertexDictKeyType, VertexDictValueType],
504 Generic[
505 GraphDictKeyType, GraphDictValueType,
506 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,
507 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,
508 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType
509 ]
510):
511 """
512 A **vertex** can have a unique ID, a value and attached meta information as key-value-pairs. A vertex has references
513 to inbound and outbound edges, thus a graph can be traversed in reverse.
514 """
515 _graph: 'BaseGraph[GraphDictKeyType, GraphDictValueType, VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType, EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType]' #: Field storing a reference to the graph.
516 _subgraph: 'Subgraph[GraphDictKeyType, GraphDictValueType, VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType, EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType]' #: Field storing a reference to the subgraph.
517 _component: 'Component'
518 _views: Dict[Hashable, 'View']
519 _inboundEdges: List['Edge[EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType]'] #: Field storing a list of inbound edges.
520 _outboundEdges: List['Edge[EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType]'] #: Field storing a list of outbound edges.
521 _inboundLinks: List['Link[EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType]'] #: Field storing a list of inbound links.
522 _outboundLinks: List['Link[EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType]'] #: Field storing a list of outbound links.
524 def __init__(
525 self,
526 vertexID: Nullable[VertexIDType] = None,
527 value: Nullable[VertexValueType] = None,
528 weight: Nullable[VertexWeightType] = None,
529 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None,
530 graph: Nullable['Graph'] = None,
531 subgraph: Nullable['Subgraph'] = None
532 ) -> None:
533 """
534 .. todo:: GRAPH::Vertex::init Needs documentation.
536 :param vertexID: The optional ID for the new vertex.
537 :param value: The optional value for the new vertex.
538 :param weight: The optional weight for the new vertex.
539 :param keyValuePairs: The optional mapping (dictionary) of key-value-pairs.
540 :param graph: The optional reference to the graph.
541 :param subgraph: undocumented
542 """
543 if vertexID is not None and not isinstance(vertexID, Hashable): 543 ↛ 544line 543 didn't jump to line 544 because the condition on line 543 was never true
544 ex = TypeError("Parameter 'vertexID' is not of type 'VertexIDType'.")
545 ex.add_note(f"Got type '{getFullyQualifiedName(vertexID)}'.")
546 raise ex
548 super().__init__(vertexID, value, weight, keyValuePairs)
550 if subgraph is None:
551 self._graph = graph if graph is not None else Graph()
552 self._subgraph = None
553 self._component = Component(self._graph, vertices=(self,))
555 if vertexID is None:
556 self._graph._verticesWithoutID.append(self)
557 elif vertexID not in self._graph._verticesWithID:
558 self._graph._verticesWithID[vertexID] = self
559 else:
560 raise DuplicateVertexError(f"Vertex ID '{vertexID}' already exists in this graph.")
561 else:
562 self._graph = subgraph._graph
563 self._subgraph = subgraph
564 self._component = Component(self._graph, vertices=(self,))
566 if vertexID is None:
567 subgraph._verticesWithoutID.append(self)
568 elif vertexID not in subgraph._verticesWithID: 568 ↛ 571line 568 didn't jump to line 571 because the condition on line 568 was always true
569 subgraph._verticesWithID[vertexID] = self
570 else:
571 raise DuplicateVertexError(f"Vertex ID '{vertexID}' already exists in this subgraph.")
573 self._views = {}
574 self._inboundEdges = []
575 self._outboundEdges = []
576 self._inboundLinks = []
577 self._outboundLinks = []
579 def __del__(self):
580 """
581 .. todo:: GRAPH::BaseEdge::del Needs documentation.
583 """
584 try:
585 del self._views
586 del self._inboundEdges
587 del self._outboundEdges
588 del self._inboundLinks
589 del self._outboundLinks
590 except AttributeError:
591 pass
593 super().__del__()
595 def Delete(self) -> None:
596 for edge in self._outboundEdges:
597 edge._destination._inboundEdges.remove(edge)
598 edge._Delete()
599 for edge in self._inboundEdges:
600 edge._source._outboundEdges.remove(edge)
601 edge._Delete()
602 for link in self._outboundLinks:
603 link._destination._inboundLinks.remove(link)
604 link._Delete()
605 for link in self._inboundLinks:
606 link._source._outboundLinks.remove(link)
607 link._Delete()
609 if self._id is None:
610 self._graph._verticesWithoutID.remove(self)
611 else:
612 del self._graph._verticesWithID[self._id]
614 # subgraph
616 # component
618 # views
619 self._views = None
620 self._inboundEdges = None
621 self._outboundEdges = None
622 self._inboundLinks = None
623 self._outboundLinks = None
625 super().Delete()
626 assert getrefcount(self) == 1
628 @readonly
629 def Graph(self) -> 'Graph':
630 """
631 Read-only property to access the graph, this vertex is associated to (:attr:`_graph`).
633 :returns: The graph this vertex is associated to.
634 """
635 return self._graph
637 @readonly
638 def Component(self) -> 'Component':
639 """
640 Read-only property to access the component, this vertex is associated to (:attr:`_component`).
642 :returns: The component this vertex is associated to.
643 """
644 return self._component
646 @readonly
647 def InboundEdges(self) -> Tuple['Edge', ...]:
648 """
649 Read-only property to get a tuple of inbound edges (:attr:`_inboundEdges`).
651 :returns: Tuple of inbound edges.
652 """
653 return tuple(self._inboundEdges)
655 @readonly
656 def OutboundEdges(self) -> Tuple['Edge', ...]:
657 """
658 Read-only property to get a tuple of outbound edges (:attr:`_outboundEdges`).
660 :returns: Tuple of outbound edges.
661 """
662 return tuple(self._outboundEdges)
664 @readonly
665 def InboundLinks(self) -> Tuple['Link', ...]:
666 """
667 Read-only property to get a tuple of inbound links (:attr:`_inboundLinks`).
669 :returns: Tuple of inbound links.
670 """
671 return tuple(self._inboundLinks)
673 @readonly
674 def OutboundLinks(self) -> Tuple['Link', ...]:
675 """
676 Read-only property to get a tuple of outbound links (:attr:`_outboundLinks`).
678 :returns: Tuple of outbound links.
679 """
680 return tuple(self._outboundLinks)
682 @readonly
683 def EdgeCount(self) -> int:
684 """
685 Read-only property to get the number of all edges (inbound and outbound).
687 :returns: Number of inbound and outbound edges.
688 """
689 return len(self._inboundEdges) + len(self._outboundEdges)
691 @readonly
692 def InboundEdgeCount(self) -> int:
693 """
694 Read-only property to get the number of inbound edges.
696 :returns: Number of inbound edges.
697 """
698 return len(self._inboundEdges)
700 @readonly
701 def OutboundEdgeCount(self) -> int:
702 """
703 Read-only property to get the number of outbound edges.
705 :returns: Number of outbound edges.
706 """
707 return len(self._outboundEdges)
709 @readonly
710 def LinkCount(self) -> int:
711 """
712 Read-only property to get the number of all links (inbound and outbound).
714 :returns: Number of inbound and outbound links.
715 """
716 return len(self._inboundLinks) + len(self._outboundLinks)
718 @readonly
719 def InboundLinkCount(self) -> int:
720 """
721 Read-only property to get the number of inbound links.
723 :returns: Number of inbound links.
724 """
725 return len(self._inboundLinks)
727 @readonly
728 def OutboundLinkCount(self) -> int:
729 """
730 Read-only property to get the number of outbound links.
732 :returns: Number of outbound links.
733 """
734 return len(self._outboundLinks)
736 @readonly
737 def IsRoot(self) -> bool:
738 """
739 Read-only property to check if this vertex is a root vertex in the graph.
741 A root has no inbound edges (no predecessor vertices).
743 :returns: ``True``, if this vertex is a root.
745 .. seealso::
747 :meth:`IsLeaf` |br|
748 |rarr| Check if a vertex is a leaf vertex in the graph.
749 :meth:`Graph.IterateRoots <pyTooling.Graph.Graph.IterateRoots>` |br|
750 |rarr| Iterate all roots of a graph.
751 :meth:`Graph.IterateLeafs <pyTooling.Graph.Graph.IterateLeafs>` |br|
752 |rarr| Iterate all leafs of a graph.
753 """
754 return len(self._inboundEdges) == 0
756 @readonly
757 def IsLeaf(self) -> bool:
758 """
759 Read-only property to check if this vertex is a leaf vertex in the graph.
761 A leaf has no outbound edges (no successor vertices).
763 :returns: ``True``, if this vertex is a leaf.
765 .. seealso::
767 :meth:`IsRoot` |br|
768 |rarr| Check if a vertex is a root vertex in the graph.
769 :meth:`Graph.IterateRoots <pyTooling.Graph.Graph.IterateRoots>` |br|
770 |rarr| Iterate all roots of a graph.
771 :meth:`Graph.IterateLeafs <pyTooling.Graph.Graph.IterateLeafs>` |br|
772 |rarr| Iterate all leafs of a graph.
773 """
774 return len(self._outboundEdges) == 0
776 @readonly
777 def Predecessors(self) -> Tuple['Vertex', ...]:
778 """
779 Read-only property to get a tuple of predecessor vertices.
781 :returns: Tuple of predecessor vertices.
782 """
783 return tuple([edge.Source for edge in self._inboundEdges])
785 @readonly
786 def Successors(self) -> Tuple['Vertex', ...]:
787 """
788 Read-only property to get a tuple of successor vertices.
790 :returns: Tuple of successor vertices.
791 """
792 return tuple([edge.Destination for edge in self._outboundEdges])
794 def EdgeToVertex(
795 self,
796 vertex: 'Vertex',
797 edgeID: Nullable[EdgeIDType] = None,
798 edgeWeight: Nullable[EdgeWeightType] = None,
799 edgeValue: Nullable[VertexValueType] = None,
800 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None
801 ) -> 'Edge':
802 """
803 Create an outbound edge from this vertex to the referenced vertex.
805 :param vertex: The vertex to be linked to.
806 :param edgeID: The edge's optional ID for the new edge object.
807 :param edgeWeight: The edge's optional weight for the new edge object.
808 :param edgeValue: The edge's optional value for the new edge object.
809 :param keyValuePairs: An optional mapping (dictionary) of key-value-pairs for the new edge object.
810 :returns: The edge object linking this vertex and the referenced vertex.
812 .. seealso::
814 :meth:`EdgeFromVertex` |br|
815 |rarr| Create an inbound edge from the referenced vertex to this vertex.
816 :meth:`EdgeToNewVertex` |br|
817 |rarr| Create a new vertex and link that vertex by an outbound edge from this vertex.
818 :meth:`EdgeFromNewVertex` |br|
819 |rarr| Create a new vertex and link that vertex by an inbound edge to this vertex.
820 :meth:`LinkToVertex` |br|
821 |rarr| Create an outbound link from this vertex to the referenced vertex.
822 :meth:`LinkFromVertex` |br|
823 |rarr| Create an inbound link from the referenced vertex to this vertex.
825 .. todo:: GRAPH::Vertex::EdgeToVertex Needs possible exceptions to be documented.
826 """
827 if self._subgraph is vertex._subgraph:
828 edge = Edge(self, vertex, edgeID, edgeValue, edgeWeight, keyValuePairs)
830 self._outboundEdges.append(edge)
831 vertex._inboundEdges.append(edge)
833 if self._subgraph is None:
834 # TODO: move into Edge?
835 # TODO: keep _graph pointer in edge and then register edge on graph?
836 if edgeID is None:
837 self._graph._edgesWithoutID.append(edge)
838 elif edgeID not in self._graph._edgesWithID:
839 self._graph._edgesWithID[edgeID] = edge
840 else:
841 raise DuplicateEdgeError(f"Edge ID '{edgeID}' already exists in this graph.")
842 else:
843 # TODO: keep _graph pointer in edge and then register edge on graph?
844 if edgeID is None:
845 self._subgraph._edgesWithoutID.append(edge)
846 elif edgeID not in self._subgraph._edgesWithID:
847 self._subgraph._edgesWithID[edgeID] = edge
848 else:
849 raise DuplicateEdgeError(f"Edge ID '{edgeID}' already exists in this subgraph.")
850 else:
851 # FIXME: needs an error message
852 raise GraphException()
854 return edge
856 def EdgeFromVertex(
857 self,
858 vertex: 'Vertex',
859 edgeID: Nullable[EdgeIDType] = None,
860 edgeWeight: Nullable[EdgeWeightType] = None,
861 edgeValue: Nullable[VertexValueType] = None,
862 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None
863 ) -> 'Edge':
864 """
865 Create an inbound edge from the referenced vertex to this vertex.
867 :param vertex: The vertex to be linked from.
868 :param edgeID: The edge's optional ID for the new edge object.
869 :param edgeWeight: The edge's optional weight for the new edge object.
870 :param edgeValue: The edge's optional value for the new edge object.
871 :param keyValuePairs: An optional mapping (dictionary) of key-value-pairs for the new edge object.
872 :returns: The edge object linking the referenced vertex and this vertex.
874 .. seealso::
876 :meth:`EdgeToVertex` |br|
877 |rarr| Create an outbound edge from this vertex to the referenced vertex.
878 :meth:`EdgeToNewVertex` |br|
879 |rarr| Create a new vertex and link that vertex by an outbound edge from this vertex.
880 :meth:`EdgeFromNewVertex` |br|
881 |rarr| Create a new vertex and link that vertex by an inbound edge to this vertex.
882 :meth:`LinkToVertex` |br|
883 |rarr| Create an outbound link from this vertex to the referenced vertex.
884 :meth:`LinkFromVertex` |br|
885 |rarr| Create an inbound link from the referenced vertex to this vertex.
887 .. todo:: GRAPH::Vertex::EdgeFromVertex Needs possible exceptions to be documented.
888 """
889 if self._subgraph is vertex._subgraph: 889 ↛ 914line 889 didn't jump to line 914 because the condition on line 889 was always true
890 edge = Edge(vertex, self, edgeID, edgeValue, edgeWeight, keyValuePairs)
892 vertex._outboundEdges.append(edge)
893 self._inboundEdges.append(edge)
895 if self._subgraph is None:
896 # TODO: move into Edge?
897 # TODO: keep _graph pointer in edge and then register edge on graph?
898 if edgeID is None:
899 self._graph._edgesWithoutID.append(edge)
900 elif edgeID not in self._graph._edgesWithID:
901 self._graph._edgesWithID[edgeID] = edge
902 else:
903 raise DuplicateEdgeError(f"Edge ID '{edgeID}' already exists in this graph.")
904 else:
905 # TODO: keep _graph pointer in edge and then register edge on graph?
906 if edgeID is None:
907 self._subgraph._edgesWithoutID.append(edge)
908 elif edgeID not in self._graph._edgesWithID:
909 self._subgraph._edgesWithID[edgeID] = edge
910 else:
911 raise DuplicateEdgeError(f"Edge ID '{edgeID}' already exists in this graph.")
912 else:
913 # FIXME: needs an error message
914 raise GraphException()
916 return edge
918 def EdgeToNewVertex(
919 self,
920 vertexID: Nullable[VertexIDType] = None,
921 vertexValue: Nullable[VertexValueType] = None,
922 vertexWeight: Nullable[VertexWeightType] = None,
923 vertexKeyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None,
924 edgeID: Nullable[EdgeIDType] = None,
925 edgeWeight: Nullable[EdgeWeightType] = None,
926 edgeValue: Nullable[VertexValueType] = None,
927 edgeKeyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None
928 ) -> 'Edge':
929 """
930 Create a new vertex and link that vertex by an outbound edge from this vertex.
932 :param vertexID: The new vertex' optional ID.
933 :param vertexValue: The new vertex' optional value.
934 :param vertexWeight: The new vertex' optional weight.
935 :param vertexKeyValuePairs: An optional mapping (dictionary) of key-value-pairs for the new vertex.
936 :param edgeID: The edge's optional ID for the new edge object.
937 :param edgeWeight: The edge's optional weight for the new edge object.
938 :param edgeValue: The edge's optional value for the new edge object.
939 :param edgeKeyValuePairs: An optional mapping (dictionary) of key-value-pairs for the new edge object.
940 :returns: The edge object linking this vertex and the created vertex.
942 .. seealso::
944 :meth:`EdgeToVertex` |br|
945 |rarr| Create an outbound edge from this vertex to the referenced vertex.
946 :meth:`EdgeFromVertex` |br|
947 |rarr| Create an inbound edge from the referenced vertex to this vertex.
948 :meth:`EdgeFromNewVertex` |br|
949 |rarr| Create a new vertex and link that vertex by an inbound edge to this vertex.
950 :meth:`LinkToVertex` |br|
951 |rarr| Create an outbound link from this vertex to the referenced vertex.
952 :meth:`LinkFromVertex` |br|
953 |rarr| Create an inbound link from the referenced vertex to this vertex.
955 .. todo:: GRAPH::Vertex::EdgeToNewVertex Needs possible exceptions to be documented.
956 """
957 vertex = Vertex(vertexID, vertexValue, vertexWeight, vertexKeyValuePairs, graph=self._graph) # , component=self._component)
959 if self._subgraph is vertex._subgraph: 959 ↛ 984line 959 didn't jump to line 984 because the condition on line 959 was always true
960 edge = Edge(self, vertex, edgeID, edgeValue, edgeWeight, edgeKeyValuePairs)
962 self._outboundEdges.append(edge)
963 vertex._inboundEdges.append(edge)
965 if self._subgraph is None: 965 ↛ 976line 965 didn't jump to line 976 because the condition on line 965 was always true
966 # TODO: move into Edge?
967 # TODO: keep _graph pointer in edge and then register edge on graph?
968 if edgeID is None: 968 ↛ 970line 968 didn't jump to line 970 because the condition on line 968 was always true
969 self._graph._edgesWithoutID.append(edge)
970 elif edgeID not in self._graph._edgesWithID:
971 self._graph._edgesWithID[edgeID] = edge
972 else:
973 raise DuplicateEdgeError(f"Edge ID '{edgeID}' already exists in this graph.")
974 else:
975 # TODO: keep _graph pointer in edge and then register edge on graph?
976 if edgeID is None:
977 self._subgraph._edgesWithoutID.append(edge)
978 elif edgeID not in self._graph._edgesWithID:
979 self._subgraph._edgesWithID[edgeID] = edge
980 else:
981 raise DuplicateEdgeError(f"Edge ID '{edgeID}' already exists in this graph.")
982 else:
983 # FIXME: needs an error message
984 raise GraphException()
986 return edge
988 def EdgeFromNewVertex(
989 self,
990 vertexID: Nullable[VertexIDType] = None,
991 vertexValue: Nullable[VertexValueType] = None,
992 vertexWeight: Nullable[VertexWeightType] = None,
993 vertexKeyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None,
994 edgeID: Nullable[EdgeIDType] = None,
995 edgeWeight: Nullable[EdgeWeightType] = None,
996 edgeValue: Nullable[VertexValueType] = None,
997 edgeKeyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None
998 ) -> 'Edge':
999 """
1000 Create a new vertex and link that vertex by an inbound edge to this vertex.
1002 :param vertexID: The new vertex' optional ID.
1003 :param vertexValue: The new vertex' optional value.
1004 :param vertexWeight: The new vertex' optional weight.
1005 :param vertexKeyValuePairs: An optional mapping (dictionary) of key-value-pairs for the new vertex.
1006 :param edgeID: The edge's optional ID for the new edge object.
1007 :param edgeWeight: The edge's optional weight for the new edge object.
1008 :param edgeValue: The edge's optional value for the new edge object.
1009 :param edgeKeyValuePairs: An optional mapping (dictionary) of key-value-pairs for the new edge object.
1010 :returns: The edge object linking this vertex and the created vertex.
1012 .. seealso::
1014 :meth:`EdgeToVertex` |br|
1015 |rarr| Create an outbound edge from this vertex to the referenced vertex.
1016 :meth:`EdgeFromVertex` |br|
1017 |rarr| Create an inbound edge from the referenced vertex to this vertex.
1018 :meth:`EdgeToNewVertex` |br|
1019 |rarr| Create a new vertex and link that vertex by an outbound edge from this vertex.
1020 :meth:`LinkToVertex` |br|
1021 |rarr| Create an outbound link from this vertex to the referenced vertex.
1022 :meth:`LinkFromVertex` |br|
1023 |rarr| Create an inbound link from the referenced vertex to this vertex.
1025 .. todo:: GRAPH::Vertex::EdgeFromNewVertex Needs possible exceptions to be documented.
1026 """
1027 vertex = Vertex(vertexID, vertexValue, vertexWeight, vertexKeyValuePairs, graph=self._graph) # , component=self._component)
1029 if self._subgraph is vertex._subgraph: 1029 ↛ 1054line 1029 didn't jump to line 1054 because the condition on line 1029 was always true
1030 edge = Edge(vertex, self, edgeID, edgeValue, edgeWeight, edgeKeyValuePairs)
1032 vertex._outboundEdges.append(edge)
1033 self._inboundEdges.append(edge)
1035 if self._subgraph is None: 1035 ↛ 1046line 1035 didn't jump to line 1046 because the condition on line 1035 was always true
1036 # TODO: move into Edge?
1037 # TODO: keep _graph pointer in edge and then register edge on graph?
1038 if edgeID is None: 1038 ↛ 1040line 1038 didn't jump to line 1040 because the condition on line 1038 was always true
1039 self._graph._edgesWithoutID.append(edge)
1040 elif edgeID not in self._graph._edgesWithID:
1041 self._graph._edgesWithID[edgeID] = edge
1042 else:
1043 raise DuplicateEdgeError(f"Edge ID '{edgeID}' already exists in this graph.")
1044 else:
1045 # TODO: keep _graph pointer in edge and then register edge on graph?
1046 if edgeID is None:
1047 self._subgraph._edgesWithoutID.append(edge)
1048 elif edgeID not in self._graph._edgesWithID:
1049 self._subgraph._edgesWithID[edgeID] = edge
1050 else:
1051 raise DuplicateEdgeError(f"Edge ID '{edgeID}' already exists in this graph.")
1052 else:
1053 # FIXME: needs an error message
1054 raise GraphException()
1056 return edge
1058 def LinkToVertex(
1059 self,
1060 vertex: 'Vertex',
1061 linkID: Nullable[EdgeIDType] = None,
1062 linkWeight: Nullable[EdgeWeightType] = None,
1063 linkValue: Nullable[VertexValueType] = None,
1064 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None,
1065 ) -> 'Link':
1066 """
1067 Create an outbound link from this vertex to the referenced vertex.
1069 :param vertex: The vertex to be linked to.
1070 :param edgeID: The edge's optional ID for the new link object.
1071 :param edgeWeight: The edge's optional weight for the new link object.
1072 :param edgeValue: The edge's optional value for the new link object.
1073 :param keyValuePairs: An optional mapping (dictionary) of key-value-pairs for the new link object.
1074 :returns: The link object linking this vertex and the referenced vertex.
1076 .. seealso::
1078 :meth:`EdgeToVertex` |br|
1079 |rarr| Create an outbound edge from this vertex to the referenced vertex.
1080 :meth:`EdgeFromVertex` |br|
1081 |rarr| Create an inbound edge from the referenced vertex to this vertex.
1082 :meth:`EdgeToNewVertex` |br|
1083 |rarr| Create a new vertex and link that vertex by an outbound edge from this vertex.
1084 :meth:`EdgeFromNewVertex` |br|
1085 |rarr| Create a new vertex and link that vertex by an inbound edge to this vertex.
1086 :meth:`LinkFromVertex` |br|
1087 |rarr| Create an inbound link from the referenced vertex to this vertex.
1089 .. todo:: GRAPH::Vertex::LinkToVertex Needs possible exceptions to be documented.
1090 """
1091 if self._subgraph is vertex._subgraph: 1091 ↛ 1093line 1091 didn't jump to line 1093 because the condition on line 1091 was never true
1092 # FIXME: needs an error message
1093 raise GraphException()
1094 else:
1095 link = Link(self, vertex, linkID, linkValue, linkWeight, keyValuePairs)
1097 self._outboundLinks.append(link)
1098 vertex._inboundLinks.append(link)
1100 if self._subgraph is None:
1101 # TODO: move into Edge?
1102 # TODO: keep _graph pointer in link and then register link on graph?
1103 if linkID is None: 1103 ↛ 1105line 1103 didn't jump to line 1105 because the condition on line 1103 was always true
1104 self._graph._linksWithoutID.append(link)
1105 elif linkID not in self._graph._linksWithID:
1106 self._graph._linksWithID[linkID] = link
1107 else:
1108 raise DuplicateEdgeError(f"Link ID '{linkID}' already exists in this graph.")
1109 else:
1110 # TODO: keep _graph pointer in link and then register link on graph?
1111 if linkID is None: 1111 ↛ 1114line 1111 didn't jump to line 1114 because the condition on line 1111 was always true
1112 self._subgraph._linksWithoutID.append(link)
1113 vertex._subgraph._linksWithoutID.append(link)
1114 elif linkID not in self._graph._linksWithID:
1115 self._subgraph._linksWithID[linkID] = link
1116 vertex._subgraph._linksWithID[linkID] = link
1117 else:
1118 raise DuplicateEdgeError(f"Link ID '{linkID}' already exists in this graph.")
1120 return link
1122 def LinkFromVertex(
1123 self,
1124 vertex: 'Vertex',
1125 linkID: Nullable[EdgeIDType] = None,
1126 linkWeight: Nullable[EdgeWeightType] = None,
1127 linkValue: Nullable[VertexValueType] = None,
1128 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None
1129 ) -> 'Edge':
1130 """
1131 Create an inbound link from the referenced vertex to this vertex.
1133 :param vertex: The vertex to be linked from.
1134 :param edgeID: The edge's optional ID for the new link object.
1135 :param edgeWeight: The edge's optional weight for the new link object.
1136 :param edgeValue: The edge's optional value for the new link object.
1137 :param keyValuePairs: An optional mapping (dictionary) of key-value-pairs for the new link object.
1138 :returns: The link object linking the referenced vertex and this vertex.
1140 .. seealso::
1142 :meth:`EdgeToVertex` |br|
1143 |rarr| Create an outbound edge from this vertex to the referenced vertex.
1144 :meth:`EdgeFromVertex` |br|
1145 |rarr| Create an inbound edge from the referenced vertex to this vertex.
1146 :meth:`EdgeToNewVertex` |br|
1147 |rarr| Create a new vertex and link that vertex by an outbound edge from this vertex.
1148 :meth:`EdgeFromNewVertex` |br|
1149 |rarr| Create a new vertex and link that vertex by an inbound edge to this vertex.
1150 :meth:`LinkToVertex` |br|
1151 |rarr| Create an outbound link from this vertex to the referenced vertex.
1153 .. todo:: GRAPH::Vertex::LinkFromVertex Needs possible exceptions to be documented.
1154 """
1155 if self._subgraph is vertex._subgraph: 1155 ↛ 1157line 1155 didn't jump to line 1157 because the condition on line 1155 was never true
1156 # FIXME: needs an error message
1157 raise GraphException()
1158 else:
1159 link = Link(vertex, self, linkID, linkValue, linkWeight, keyValuePairs)
1161 vertex._outboundLinks.append(link)
1162 self._inboundLinks.append(link)
1164 if self._subgraph is None: 1164 ↛ 1167line 1164 didn't jump to line 1167 because the condition on line 1164 was never true
1165 # TODO: move into Edge?
1166 # TODO: keep _graph pointer in link and then register link on graph?
1167 if linkID is None:
1168 self._graph._linksWithoutID.append(link)
1169 elif linkID not in self._graph._linksWithID:
1170 self._graph._linksWithID[linkID] = link
1171 else:
1172 raise DuplicateEdgeError(f"Link ID '{linkID}' already exists in this graph.")
1173 else:
1174 # TODO: keep _graph pointer in link and then register link on graph?
1175 if linkID is None: 1175 ↛ 1178line 1175 didn't jump to line 1178 because the condition on line 1175 was always true
1176 self._subgraph._linksWithoutID.append(link)
1177 vertex._subgraph._linksWithoutID.append(link)
1178 elif linkID not in self._graph._linksWithID:
1179 self._subgraph._linksWithID[linkID] = link
1180 vertex._subgraph._linksWithID[linkID] = link
1181 else:
1182 raise DuplicateEdgeError(f"Link ID '{linkID}' already exists in this graph.")
1184 return link
1186 def HasEdgeToDestination(self, destination: 'Vertex') -> bool:
1187 """
1188 Check if this vertex is linked to another vertex by any outbound edge.
1190 :param destination: Destination vertex to check.
1191 :returns: ``True``, if the destination vertex is a destination on any outbound edge.
1193 .. seealso::
1195 :meth:`HasEdgeFromSource` |br|
1196 |rarr| Check if this vertex is linked to another vertex by any inbound edge.
1197 :meth:`HasLinkToDestination` |br|
1198 |rarr| Check if this vertex is linked to another vertex by any outbound link.
1199 :meth:`HasLinkFromSource` |br|
1200 |rarr| Check if this vertex is linked to another vertex by any inbound link.
1201 """
1202 for edge in self._outboundEdges:
1203 if destination is edge.Destination: 1203 ↛ 1202line 1203 didn't jump to line 1202 because the condition on line 1203 was always true
1204 return True
1206 return False
1208 def HasEdgeFromSource(self, source: 'Vertex') -> bool:
1209 """
1210 Check if this vertex is linked to another vertex by any inbound edge.
1212 :param source: Source vertex to check.
1213 :returns: ``True``, if the source vertex is a source on any inbound edge.
1215 .. seealso::
1217 :meth:`HasEdgeToDestination` |br|
1218 |rarr| Check if this vertex is linked to another vertex by any outbound edge.
1219 :meth:`HasLinkToDestination` |br|
1220 |rarr| Check if this vertex is linked to another vertex by any outbound link.
1221 :meth:`HasLinkFromSource` |br|
1222 |rarr| Check if this vertex is linked to another vertex by any inbound link.
1223 """
1224 for edge in self._inboundEdges:
1225 if source is edge.Source: 1225 ↛ 1224line 1225 didn't jump to line 1224 because the condition on line 1225 was always true
1226 return True
1228 return False
1230 def HasLinkToDestination(self, destination: 'Vertex') -> bool:
1231 """
1232 Check if this vertex is linked to another vertex by any outbound link.
1234 :param destination: Destination vertex to check.
1235 :returns: ``True``, if the destination vertex is a destination on any outbound link.
1237 .. seealso::
1239 :meth:`HasEdgeToDestination` |br|
1240 |rarr| Check if this vertex is linked to another vertex by any outbound edge.
1241 :meth:`HasEdgeFromSource` |br|
1242 |rarr| Check if this vertex is linked to another vertex by any inbound edge.
1243 :meth:`HasLinkFromSource` |br|
1244 |rarr| Check if this vertex is linked to another vertex by any inbound link.
1245 """
1246 for link in self._outboundLinks:
1247 if destination is link.Destination: 1247 ↛ 1246line 1247 didn't jump to line 1246 because the condition on line 1247 was always true
1248 return True
1250 return False
1252 def HasLinkFromSource(self, source: 'Vertex') -> bool:
1253 """
1254 Check if this vertex is linked to another vertex by any inbound link.
1256 :param source: Source vertex to check.
1257 :returns: ``True``, if the source vertex is a source on any inbound link.
1259 .. seealso::
1261 :meth:`HasEdgeToDestination` |br|
1262 |rarr| Check if this vertex is linked to another vertex by any outbound edge.
1263 :meth:`HasEdgeFromSource` |br|
1264 |rarr| Check if this vertex is linked to another vertex by any inbound edge.
1265 :meth:`HasLinkToDestination` |br|
1266 |rarr| Check if this vertex is linked to another vertex by any outbound link.
1267 """
1268 for link in self._inboundLinks:
1269 if source is link.Source: 1269 ↛ 1268line 1269 didn't jump to line 1268 because the condition on line 1269 was always true
1270 return True
1272 return False
1274 def DeleteEdgeTo(self, destination: 'Vertex'):
1275 for edge in self._outboundEdges: 1275 ↛ 1279line 1275 didn't jump to line 1279 because the loop on line 1275 didn't complete
1276 if edge._destination is destination: 1276 ↛ 1275line 1276 didn't jump to line 1275 because the condition on line 1276 was always true
1277 break
1278 else:
1279 raise GraphException(f"No outbound edge found to '{destination!r}'.")
1281 edge.Delete()
1283 def DeleteEdgeFrom(self, source: 'Vertex'):
1284 for edge in self._inboundEdges:
1285 if edge._source is source:
1286 break
1287 else:
1288 raise GraphException(f"No inbound edge found to '{source!r}'.")
1290 edge.Delete()
1292 def DeleteLinkTo(self, destination: 'Vertex'):
1293 for link in self._outboundLinks:
1294 if link._destination is destination:
1295 break
1296 else:
1297 raise GraphException(f"No outbound link found to '{destination!r}'.")
1299 link.Delete()
1301 def DeleteLinkFrom(self, source: 'Vertex'):
1302 for link in self._inboundLinks:
1303 if link._source is source:
1304 break
1305 else:
1306 raise GraphException(f"No inbound link found to '{source!r}'.")
1308 link.Delete()
1310 def Copy(self, graph: Graph, copyDict: bool = False, linkingKeyToOriginalVertex: Nullable[str] = None, linkingKeyFromOriginalVertex: Nullable[str] = None) -> 'Vertex':
1311 """
1312 Creates a copy of this vertex in another graph.
1314 Optionally, the vertex's attached attributes (key-value-pairs) can be copied and a linkage between both vertices
1315 can be established.
1317 :param graph: The graph, the vertex is created in.
1318 :param copyDict: If ``True``, copy all attached attributes into the new vertex.
1319 :param linkingKeyToOriginalVertex: If not ``None``, add a key-value-pair using this parameter as key from new vertex to the original vertex.
1320 :param linkingKeyFromOriginalVertex: If not ``None``, add a key-value-pair using this parameter as key from original vertex to the new vertex.
1321 :returns: The newly created vertex.
1322 :raises GraphException: If source graph and destination graph are the same.
1323 """
1324 if graph is self._graph:
1325 raise GraphException("Graph to copy this vertex to, is the same graph.")
1327 vertex = Vertex(self._id, self._value, self._weight, graph=graph)
1328 if copyDict:
1329 vertex._dict = self._dict.copy()
1331 if linkingKeyToOriginalVertex is not None:
1332 vertex._dict[linkingKeyToOriginalVertex] = self
1333 if linkingKeyFromOriginalVertex is not None:
1334 self._dict[linkingKeyFromOriginalVertex] = vertex
1336 return vertex
1338 def IterateOutboundEdges(self, predicate: Nullable[Callable[['Edge'], bool]] = None) -> Generator['Edge', None, None]:
1339 """
1340 Iterate all or selected outbound edges of this vertex.
1342 If parameter ``predicate`` is not None, the given filter function is used to skip edges in the generator.
1344 :param predicate: Filter function accepting any edge and returning a boolean.
1345 :returns: A generator to iterate all outbound edges.
1346 """
1347 if predicate is None:
1348 for edge in self._outboundEdges:
1349 yield edge
1350 else:
1351 for edge in self._outboundEdges:
1352 if predicate(edge):
1353 yield edge
1355 def IterateInboundEdges(self, predicate: Nullable[Callable[['Edge'], bool]] = None) -> Generator['Edge', None, None]:
1356 """
1357 Iterate all or selected inbound edges of this vertex.
1359 If parameter ``predicate`` is not None, the given filter function is used to skip edges in the generator.
1361 :param predicate: Filter function accepting any edge and returning a boolean.
1362 :returns: A generator to iterate all inbound edges.
1363 """
1364 if predicate is None:
1365 for edge in self._inboundEdges:
1366 yield edge
1367 else:
1368 for edge in self._inboundEdges:
1369 if predicate(edge):
1370 yield edge
1372 def IterateOutboundLinks(self, predicate: Nullable[Callable[['Link'], bool]] = None) -> Generator['Link', None, None]:
1373 """
1374 Iterate all or selected outbound links of this vertex.
1376 If parameter ``predicate`` is not None, the given filter function is used to skip links in the generator.
1378 :param predicate: Filter function accepting any link and returning a boolean.
1379 :returns: A generator to iterate all outbound links.
1380 """
1381 if predicate is None:
1382 for link in self._outboundLinks:
1383 yield link
1384 else:
1385 for link in self._outboundLinks:
1386 if predicate(link):
1387 yield link
1389 def IterateInboundLinks(self, predicate: Nullable[Callable[['Link'], bool]] = None) -> Generator['Link', None, None]:
1390 """
1391 Iterate all or selected inbound links of this vertex.
1393 If parameter ``predicate`` is not None, the given filter function is used to skip links in the generator.
1395 :param predicate: Filter function accepting any link and returning a boolean.
1396 :returns: A generator to iterate all inbound links.
1397 """
1398 if predicate is None:
1399 for link in self._inboundLinks:
1400 yield link
1401 else:
1402 for link in self._inboundLinks:
1403 if predicate(link):
1404 yield link
1406 def IterateSuccessorVertices(self, predicate: Nullable[Callable[['Edge'], bool]] = None) -> Generator['Vertex', None, None]:
1407 """
1408 Iterate all or selected successor vertices of this vertex.
1410 If parameter ``predicate`` is not None, the given filter function is used to skip successors in the generator.
1412 :param predicate: Filter function accepting any edge and returning a boolean.
1413 :returns: A generator to iterate all successor vertices.
1414 """
1415 if predicate is None:
1416 for edge in self._outboundEdges:
1417 yield edge.Destination
1418 else:
1419 for edge in self._outboundEdges:
1420 if predicate(edge):
1421 yield edge.Destination
1423 def IteratePredecessorVertices(self, predicate: Nullable[Callable[['Edge'], bool]] = None) -> Generator['Vertex', None, None]:
1424 """
1425 Iterate all or selected predecessor vertices of this vertex.
1427 If parameter ``predicate`` is not None, the given filter function is used to skip predecessors in the generator.
1429 :param predicate: Filter function accepting any edge and returning a boolean.
1430 :returns: A generator to iterate all predecessor vertices.
1431 """
1432 if predicate is None:
1433 for edge in self._inboundEdges:
1434 yield edge.Source
1435 else:
1436 for edge in self._inboundEdges:
1437 if predicate(edge):
1438 yield edge.Source
1440 def IterateVerticesBFS(self) -> Generator['Vertex', None, None]:
1441 """
1442 A generator to iterate all reachable vertices starting from this node in breadth-first search (BFS) order.
1444 :returns: A generator to iterate vertices traversed in BFS order.
1446 .. seealso::
1448 :meth:`IterateVerticesDFS` |br|
1449 |rarr| Iterate all reachable vertices **depth-first search** order.
1450 """
1451 visited: Set[Vertex] = set()
1452 queue: Deque[Vertex] = deque()
1454 yield self
1455 visited.add(self)
1456 for edge in self._outboundEdges:
1457 nextVertex = edge.Destination
1458 if nextVertex is not self: 1458 ↛ 1456line 1458 didn't jump to line 1456 because the condition on line 1458 was always true
1459 queue.appendleft(nextVertex)
1460 visited.add(nextVertex)
1462 while queue:
1463 vertex = queue.pop()
1464 yield vertex
1465 for edge in vertex._outboundEdges:
1466 nextVertex = edge.Destination
1467 if nextVertex not in visited:
1468 queue.appendleft(nextVertex)
1469 visited.add(nextVertex)
1471 def IterateVerticesDFS(self) -> Generator['Vertex', None, None]:
1472 """
1473 A generator to iterate all reachable vertices starting from this node in depth-first search (DFS) order.
1475 :returns: A generator to iterate vertices traversed in DFS order.
1477 .. seealso::
1479 :meth:`IterateVerticesBFS` |br|
1480 |rarr| Iterate all reachable vertices **breadth-first search** order.
1482 Wikipedia - https://en.wikipedia.org/wiki/Depth-first_search
1483 """
1484 visited: Set[Vertex] = set()
1485 stack: List[typing_Iterator[Edge]] = list()
1487 yield self
1488 visited.add(self)
1489 stack.append(iter(self._outboundEdges))
1491 while True:
1492 try:
1493 edge = next(stack[-1])
1494 nextVertex = edge._destination
1495 if nextVertex not in visited:
1496 visited.add(nextVertex)
1497 yield nextVertex
1498 if len(nextVertex._outboundEdges) != 0:
1499 stack.append(iter(nextVertex._outboundEdges))
1500 except StopIteration:
1501 stack.pop()
1503 if len(stack) == 0:
1504 return
1506 def IterateAllOutboundPathsAsVertexList(self) -> Generator[Tuple['Vertex', ...], None, None]:
1507 if len(self._outboundEdges) == 0:
1508 yield (self, )
1509 return
1511 visited: Set[Vertex] = set()
1512 vertexStack: List[Vertex] = list()
1513 iteratorStack: List[typing_Iterator[Edge]] = list()
1515 visited.add(self)
1516 vertexStack.append(self)
1517 iteratorStack.append(iter(self._outboundEdges))
1519 while True:
1520 try:
1521 edge = next(iteratorStack[-1])
1522 nextVertex = edge._destination
1523 if nextVertex in visited:
1524 ex = CycleError(f"Loop detected.")
1525 ex.add_note(f"First loop is:")
1526 for i, vertex in enumerate(vertexStack):
1527 ex.add_note(f" {i}: {vertex!r}")
1528 raise ex
1530 vertexStack.append(nextVertex)
1531 if len(nextVertex._outboundEdges) == 0:
1532 yield tuple(vertexStack)
1533 vertexStack.pop()
1534 else:
1535 iteratorStack.append(iter(nextVertex._outboundEdges))
1537 except StopIteration:
1538 vertexStack.pop()
1539 iteratorStack.pop()
1541 if len(vertexStack) == 0:
1542 return
1544 def ShortestPathToByHops(self, destination: 'Vertex') -> Generator['Vertex', None, None]:
1545 """
1546 Compute the shortest path (by hops) between this vertex and the destination vertex.
1548 A generator is return to iterate all vertices along the path including source and destination vertex.
1550 The search algorithm is breadth-first search (BFS) based. The found solution, if any, is not unique but deterministic
1551 as long as the graph was not modified (e.g. ordering of edges on vertices).
1553 :param destination: The destination vertex to reach.
1554 :returns: A generator to iterate all vertices on the path found between this vertex and the destination vertex.
1555 """
1556 # Trivial case if start is destination
1557 if self is destination: 1557 ↛ 1558line 1557 didn't jump to line 1558 because the condition on line 1557 was never true
1558 yield self
1559 return
1561 # Local struct to create multiple linked-lists forming a paths from current node back to the starting point
1562 # (actually a tree). Each node holds a reference to the vertex it represents.
1563 # Hint: slotted classes are faster than '@dataclasses.dataclass'.
1564 class Node(metaclass=ExtendedType, slots=True):
1565 parent: 'Node'
1566 ref: Vertex
1568 def __init__(self, parent: 'Node', ref: Vertex) -> None:
1569 self.parent = parent
1570 self.ref = ref
1572 def __str__(self):
1573 return f"Vertex: {self.ref.ID}"
1575 # Initially add all reachable vertices to a queue if vertices to be processed.
1576 startNode = Node(None, self)
1577 visited: Set[Vertex] = set()
1578 queue: Deque[Node] = deque()
1580 # Add starting vertex and all its children to the processing list.
1581 # If a child is the destination, break immediately else go into 'else' branch and use BFS algorithm.
1582 visited.add(self)
1583 for edge in self._outboundEdges:
1584 nextVertex = edge.Destination
1585 if nextVertex is destination: 1585 ↛ 1587line 1585 didn't jump to line 1587 because the condition on line 1585 was never true
1586 # Child is destination, so construct the last node for path traversal and break from loop.
1587 destinationNode = Node(startNode, nextVertex)
1588 break
1589 if nextVertex is not self: 1589 ↛ 1583line 1589 didn't jump to line 1583 because the condition on line 1589 was always true
1590 # Ignore backward-edges and side-edges.
1591 # Here self-edges, because there is only the starting vertex in the list of visited edges.
1592 visited.add(nextVertex)
1593 queue.appendleft(Node(startNode, nextVertex))
1594 else:
1595 # Process queue until destination is found or no further vertices are reachable.
1596 while queue:
1597 node = queue.pop()
1598 for edge in node.ref._outboundEdges:
1599 nextVertex = edge.Destination
1600 # Next reachable vertex is destination, so construct the last node for path traversal and break from loop.
1601 if nextVertex is destination:
1602 destinationNode = Node(node, nextVertex)
1603 break
1604 # Ignore backward-edges and side-edges.
1605 if nextVertex not in visited:
1606 visited.add(nextVertex)
1607 queue.appendleft(Node(node, nextVertex))
1608 # Next 3 lines realize a double-break if break was called in inner loop, otherwise continue with outer loop.
1609 else:
1610 continue
1611 break
1612 else:
1613 # All reachable vertices have been processed, but destination was not among them.
1614 raise DestinationNotReachable(f"Destination is not reachable.")
1616 # Reverse order of linked list from destinationNode to startNode
1617 currentNode = destinationNode
1618 previousNode = destinationNode.parent
1619 currentNode.parent = None
1620 while previousNode is not None:
1621 node = previousNode.parent
1622 previousNode.parent = currentNode
1623 currentNode = previousNode
1624 previousNode = node
1626 # Scan reversed linked-list and yield referenced vertices
1627 yield startNode.ref
1628 node = startNode.parent
1629 while node is not None:
1630 yield node.ref
1631 node = node.parent
1633 def ShortestPathToByWeight(self, destination: 'Vertex') -> Generator['Vertex', None, None]:
1634 """
1635 Compute the shortest path (by edge weight) between this vertex and the destination vertex.
1637 A generator is return to iterate all vertices along the path including source and destination vertex.
1639 The search algorithm is based on Dijkstra algorithm and using :mod:`heapq`. The found solution, if any, is not
1640 unique but deterministic as long as the graph was not modified (e.g. ordering of edges on vertices).
1642 :param destination: The destination vertex to reach.
1643 :returns: A generator to iterate all vertices on the path found between this vertex and the destination vertex.
1644 """
1645 # Improvements: both-sided Dijkstra (search from start and destination to reduce discovered area.
1647 # Trivial case if start is destination
1648 if self is destination: 1648 ↛ 1649line 1648 didn't jump to line 1649 because the condition on line 1648 was never true
1649 yield self
1650 return
1652 # Local struct to create multiple-linked lists forming a paths from current node back to the starting point
1653 # (actually a tree). Each node holds the overall weight from start to current node and a reference to the vertex it
1654 # represents.
1655 # Hint: slotted classes are faster than '@dataclasses.dataclass'.
1656 class Node(metaclass=ExtendedType, slots=True):
1657 parent: 'Node'
1658 distance: EdgeWeightType
1659 ref: Vertex
1661 def __init__(self, parent: 'Node', distance: EdgeWeightType, ref: Vertex) -> None:
1662 self.parent = parent
1663 self.distance = distance
1664 self.ref = ref
1666 def __lt__(self, other):
1667 return self.distance < other.distance
1669 def __str__(self):
1670 return f"Vertex: {self.ref.ID}"
1672 visited: Set['Vertex'] = set()
1673 startNode = Node(None, 0, self)
1674 priorityQueue = [startNode]
1676 # Add starting vertex and all its children to the processing list.
1677 # If a child is the destination, break immediately else go into 'else' branch and use Dijkstra algorithm.
1678 visited.add(self)
1679 for edge in self._outboundEdges:
1680 nextVertex = edge.Destination
1681 # Child is destination, so construct the last node for path traversal and break from loop.
1682 if nextVertex is destination: 1682 ↛ 1683line 1682 didn't jump to line 1683 because the condition on line 1682 was never true
1683 destinationNode = Node(startNode, edge._weight, nextVertex)
1684 break
1685 # Ignore backward-edges and side-edges.
1686 # Here self-edges, because there is only the starting vertex in the list of visited edges.
1687 if nextVertex is not self: 1687 ↛ 1679line 1687 didn't jump to line 1679 because the condition on line 1687 was always true
1688 visited.add(nextVertex)
1689 heapq.heappush(priorityQueue, Node(startNode, edge._weight, nextVertex))
1690 else:
1691 # Process priority queue until destination is found or no further vertices are reachable.
1692 while priorityQueue: 1692 ↛ 1710line 1692 didn't jump to line 1710 because the condition on line 1692 was always true
1693 node = heapq.heappop(priorityQueue)
1694 for edge in node.ref._outboundEdges:
1695 nextVertex = edge.Destination
1696 # Next reachable vertex is destination, so construct the last node for path traversal and break from loop.
1697 if nextVertex is destination:
1698 destinationNode = Node(node, node.distance + edge._weight, nextVertex)
1699 break
1700 # Ignore backward-edges and side-edges.
1701 if nextVertex not in visited:
1702 visited.add(nextVertex)
1703 heapq.heappush(priorityQueue, Node(node, node.distance + edge._weight, nextVertex))
1704 # Next 3 lines realize a double-break if break was called in inner loop, otherwise continue with outer loop.
1705 else:
1706 continue
1707 break
1708 else:
1709 # All reachable vertices have been processed, but destination was not among them.
1710 raise DestinationNotReachable(f"Destination is not reachable.")
1712 # Reverse order of linked-list from destinationNode to startNode
1713 currentNode = destinationNode
1714 previousNode = destinationNode.parent
1715 currentNode.parent = None
1716 while previousNode is not None:
1717 node = previousNode.parent
1718 previousNode.parent = currentNode
1719 currentNode = previousNode
1720 previousNode = node
1722 # Scan reversed linked-list and yield referenced vertices
1723 yield startNode.ref, startNode.distance
1724 node = startNode.parent
1725 while node is not None:
1726 yield node.ref, node.distance
1727 node = node.parent
1729 # Other possible algorithms:
1730 # * Bellman-Ford
1731 # * Floyd-Warshall
1733 # def PathExistsTo(self, destination: 'Vertex'):
1734 # raise NotImplementedError()
1735 # # DFS
1736 # # Union find
1737 #
1738 # def MaximumFlowTo(self, destination: 'Vertex'):
1739 # raise NotImplementedError()
1740 # # Ford-Fulkerson algorithm
1741 # # Edmons-Karp algorithm
1742 # # Dinic's algorithm
1744 def ConvertToTree(self) -> Node:
1745 """
1746 Converts all reachable vertices from this starting vertex to a tree of :class:`~pyTooling.Tree.Node` instances.
1748 The tree is traversed using depths-first-search.
1750 :returns:
1751 """
1752 visited: Set[Vertex] = set()
1753 stack: List[Tuple[Node, typing_Iterator[Edge]]] = list()
1755 root = Node(nodeID=self._id, value=self._value)
1756 root._dict = self._dict.copy()
1758 visited.add(self)
1759 stack.append((root, iter(self._outboundEdges)))
1761 while True:
1762 try:
1763 edge = next(stack[-1][1])
1764 nextVertex = edge._destination
1765 if nextVertex not in visited: 1765 ↛ 1771line 1765 didn't jump to line 1771 because the condition on line 1765 was always true
1766 node = Node(nextVertex._id, nextVertex._value, parent=stack[-1][0])
1767 visited.add(nextVertex)
1768 if len(nextVertex._outboundEdges) != 0:
1769 stack.append((node, iter(nextVertex._outboundEdges)))
1770 else:
1771 raise NotATreeError(f"The directed subgraph is not a tree.")
1772 # TODO: compute cycle:
1773 # a) branch 1 is described in stack
1774 # b) branch 2 can be found by walking from joint to root in the tree
1775 except StopIteration:
1776 stack.pop()
1778 if len(stack) == 0:
1779 return root
1781 def __repr__(self) -> str:
1782 """
1783 Returns a detailed string representation of the vertex.
1785 :returns: The detailed string representation of the vertex.
1786 """
1787 vertexID = value = ""
1788 sep = ": "
1789 if self._id is not None:
1790 vertexID = f"{sep}vertexID='{self._id}'"
1791 sep = "; "
1792 if self._value is not None: 1792 ↛ 1793line 1792 didn't jump to line 1793 because the condition on line 1792 was never true
1793 value = f"{sep}value='{self._value}'"
1795 return f"<vertex{vertexID}{value}>"
1797 def __str__(self) -> str:
1798 """
1799 Return a string representation of the vertex.
1801 Order of resolution:
1803 1. If :attr:`_value` is not None, return the string representation of :attr:`_value`.
1804 2. If :attr:`_id` is not None, return the string representation of :attr:`_id`.
1805 3. Else, return :meth:`__repr__`.
1807 :returns: The resolved string representation of the vertex.
1808 """
1809 if self._value is not None: 1809 ↛ 1810line 1809 didn't jump to line 1810 because the condition on line 1809 was never true
1810 return str(self._value)
1811 elif self._id is not None: 1811 ↛ 1812line 1811 didn't jump to line 1812 because the condition on line 1811 was never true
1812 return str(self._id)
1813 else:
1814 return self.__repr__()
1817@export
1818class BaseEdge(
1819 BaseWithIDValueAndWeight[EdgeIDType, EdgeValueType, EdgeWeightType, EdgeDictKeyType, EdgeDictValueType],
1820 Generic[EdgeIDType, EdgeValueType, EdgeWeightType, EdgeDictKeyType, EdgeDictValueType]
1821):
1822 """
1823 An **edge** can have a unique ID, a value, a weight and attached meta information as key-value-pairs. All edges are
1824 directed.
1825 """
1826 _source: Vertex
1827 _destination: Vertex
1829 def __init__(
1830 self,
1831 source: Vertex,
1832 destination: Vertex,
1833 edgeID: Nullable[EdgeIDType] = None,
1834 value: Nullable[EdgeValueType] = None,
1835 weight: Nullable[EdgeWeightType] = None,
1836 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None
1837 ) -> None:
1838 """
1839 .. todo:: GRAPH::BaseEdge::init Needs documentation.
1841 :param source: The source of the new edge.
1842 :param destination: The destination of the new edge.
1843 :param edgeID: The optional unique ID for the new edge.
1844 :param value: The optional value for the new edge.
1845 :param weight: The optional weight for the new edge.
1846 :param keyValuePairs: The optional mapping (dictionary) of key-value-pairs.
1847 """
1848 super().__init__(edgeID, value, weight, keyValuePairs)
1850 self._source = source
1851 self._destination = destination
1853 component = source._component
1854 if component is not destination._component:
1855 # TODO: should it be divided into with/without ID?
1856 oldComponent = destination._component
1857 for vertex in oldComponent._vertices:
1858 vertex._component = component
1859 component._vertices.add(vertex)
1860 component._graph._components.remove(oldComponent)
1861 del oldComponent
1863 @readonly
1864 def Source(self) -> Vertex:
1865 """
1866 Read-only property to get the source (:attr:`_source`) of an edge.
1868 :returns: The source of an edge.
1869 """
1870 return self._source
1872 @readonly
1873 def Destination(self) -> Vertex:
1874 """
1875 Read-only property to get the destination (:attr:`_destination`) of an edge.
1877 :returns: The destination of an edge.
1878 """
1879 return self._destination
1881 def Reverse(self) -> None:
1882 """Reverse the direction of this edge."""
1883 swap = self._source
1884 self._source = self._destination
1885 self._destination = swap
1888@export
1889class Edge(
1890 BaseEdge[EdgeIDType, EdgeValueType, EdgeWeightType, EdgeDictKeyType, EdgeDictValueType],
1891 Generic[EdgeIDType, EdgeValueType, EdgeWeightType, EdgeDictKeyType, EdgeDictValueType]
1892):
1893 """
1894 An **edge** can have a unique ID, a value, a weight and attached meta information as key-value-pairs. All edges are
1895 directed.
1896 """
1898 def __init__(
1899 self,
1900 source: Vertex,
1901 destination: Vertex,
1902 edgeID: Nullable[EdgeIDType] = None,
1903 value: Nullable[EdgeValueType] = None,
1904 weight: Nullable[EdgeWeightType] = None,
1905 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None
1906 ) -> None:
1907 """
1908 .. todo:: GRAPH::Edge::init Needs documentation.
1910 :param source: The source of the new edge.
1911 :param destination: The destination of the new edge.
1912 :param edgeID: The optional unique ID for the new edge.
1913 :param value: The optional value for the new edge.
1914 :param weight: The optional weight for the new edge.
1915 :param keyValuePairs: The optional mapping (dictionary) of key-value-pairs.
1916 """
1917 if not isinstance(source, Vertex):
1918 ex = TypeError("Parameter 'source' is not of type 'Vertex'.")
1919 ex.add_note(f"Got type '{getFullyQualifiedName(source)}'.")
1920 raise ex
1921 if not isinstance(destination, Vertex):
1922 ex = TypeError("Parameter 'destination' is not of type 'Vertex'.")
1923 ex.add_note(f"Got type '{getFullyQualifiedName(destination)}'.")
1924 raise ex
1925 if edgeID is not None and not isinstance(edgeID, Hashable):
1926 ex = TypeError("Parameter 'edgeID' is not of type 'EdgeIDType'.")
1927 ex.add_note(f"Got type '{getFullyQualifiedName(edgeID)}'.")
1928 raise ex
1929 # if value is not None and not isinstance(value, Vertex):
1930 # raise TypeError("Parameter 'value' is not of type 'EdgeValueType'.")
1931 if weight is not None and not isinstance(weight, (int, float)):
1932 ex = TypeError("Parameter 'weight' is not of type 'EdgeWeightType'.")
1933 ex.add_note(f"Got type '{getFullyQualifiedName(weight)}'.")
1934 raise ex
1935 if source._graph is not destination._graph:
1936 raise NotInSameGraph(f"Source vertex and destination vertex are not in same graph.")
1938 super().__init__(source, destination, edgeID, value, weight, keyValuePairs)
1940 def Delete(self) -> None:
1941 # Remove from Source and Destination
1942 self._source._outboundEdges.remove(self)
1943 self._destination._inboundEdges.remove(self)
1945 # Remove from Graph and Subgraph
1946 if self._id is None: 1946 ↛ 1951line 1946 didn't jump to line 1951 because the condition on line 1946 was always true
1947 self._source._graph._edgesWithoutID.remove(self)
1948 if self._source._subgraph is not None: 1948 ↛ 1949line 1948 didn't jump to line 1949 because the condition on line 1948 was never true
1949 self._source._subgraph._edgesWithoutID.remove(self)
1950 else:
1951 del self._source._graph._edgesWithID[self._id]
1952 if self._source._subgraph is not None:
1953 del self._source._subgraph._edgesWithID[self]
1955 self._Delete()
1957 def _Delete(self) -> None:
1958 super().Delete()
1960 def Reverse(self) -> None:
1961 """Reverse the direction of this edge."""
1962 self._source._outboundEdges.remove(self)
1963 self._source._inboundEdges.append(self)
1964 self._destination._inboundEdges.remove(self)
1965 self._destination._outboundEdges.append(self)
1967 super().Reverse()
1970@export
1971class Link(
1972 BaseEdge[LinkIDType, LinkValueType, LinkWeightType, LinkDictKeyType, LinkDictValueType],
1973 Generic[LinkIDType, LinkValueType, LinkWeightType, LinkDictKeyType, LinkDictValueType]
1974):
1975 """
1976 A **link** can have a unique ID, a value, a weight and attached meta information as key-value-pairs. All links are
1977 directed.
1978 """
1980 def __init__(
1981 self,
1982 source: Vertex,
1983 destination: Vertex,
1984 linkID: LinkIDType = None,
1985 value: LinkValueType = None,
1986 weight: Nullable[LinkWeightType] = None,
1987 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None
1988 ) -> None:
1989 """
1990 .. todo:: GRAPH::Edge::init Needs documentation.
1992 :param source: The source of the new link.
1993 :param destination: The destination of the new link.
1994 :param linkID: The optional unique ID for the new link.
1995 :param value: The optional value for the new v.
1996 :param weight: The optional weight for the new link.
1997 :param keyValuePairs: The optional mapping (dictionary) of key-value-pairs.
1998 """
1999 if not isinstance(source, Vertex):
2000 ex = TypeError("Parameter 'source' is not of type 'Vertex'.")
2001 ex.add_note(f"Got type '{getFullyQualifiedName(source)}'.")
2002 raise ex
2003 if not isinstance(destination, Vertex):
2004 ex = TypeError("Parameter 'destination' is not of type 'Vertex'.")
2005 ex.add_note(f"Got type '{getFullyQualifiedName(destination)}'.")
2006 raise ex
2007 if linkID is not None and not isinstance(linkID, Hashable):
2008 ex = TypeError("Parameter 'linkID' is not of type 'LinkIDType'.")
2009 ex.add_note(f"Got type '{getFullyQualifiedName(linkID)}'.")
2010 raise ex
2011 # if value is not None and not isinstance(value, Vertex):
2012 # raise TypeError("Parameter 'value' is not of type 'EdgeValueType'.")
2013 if weight is not None and not isinstance(weight, (int, float)):
2014 ex = TypeError("Parameter 'weight' is not of type 'EdgeWeightType'.")
2015 ex.add_note(f"Got type '{getFullyQualifiedName(weight)}'.")
2016 raise ex
2017 if source._graph is not destination._graph:
2018 raise NotInSameGraph(f"Source vertex and destination vertex are not in same graph.")
2020 super().__init__(source, destination, linkID, value, weight, keyValuePairs)
2022 def Delete(self) -> None:
2023 self._source._outboundEdges.remove(self)
2024 self._destination._inboundEdges.remove(self)
2026 if self._id is None:
2027 self._source._graph._linksWithoutID.remove(self)
2028 else:
2029 del self._source._graph._linksWithID[self._id]
2031 self._Delete()
2032 assert getrefcount(self) == 1
2034 def _Delete(self) -> None:
2035 super().Delete()
2037 def Reverse(self) -> None:
2038 """Reverse the direction of this link."""
2039 self._source._outboundEdges.remove(self)
2040 self._source._inboundEdges.append(self)
2041 self._destination._inboundEdges.remove(self)
2042 self._destination._outboundEdges.append(self)
2044 super().Reverse()
2047@export
2048class BaseGraph(
2049 BaseWithName[GraphDictKeyType, GraphDictValueType],
2050 Generic[
2051 GraphDictKeyType, GraphDictValueType,
2052 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,
2053 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,
2054 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType
2055 ]
2056):
2057 """
2058 .. todo:: GRAPH::BaseGraph Needs documentation.
2060 """
2062 _verticesWithID: Dict[VertexIDType, Vertex[GraphDictKeyType, GraphDictValueType, VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType, EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType, LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType]]
2063 _verticesWithoutID: List[Vertex[GraphDictKeyType, GraphDictValueType, VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType, EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType, LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType]]
2064 _edgesWithID: Dict[EdgeIDType, Edge[EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType]]
2065 _edgesWithoutID: List[Edge[EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType]]
2066 _linksWithID: Dict[EdgeIDType, Link[LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType]]
2067 _linksWithoutID: List[Link[LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType]]
2069 def __init__(
2070 self,
2071 name: Nullable[str] = None,
2072 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None
2073 #, vertices: Nullable[Iterable[Vertex]] = None) -> None:
2074 ):
2075 """
2076 .. todo:: GRAPH::BaseGraph::init Needs documentation.
2078 :param name: The optional name of the graph.
2079 :param keyValuePairs: The optional mapping (dictionary) of key-value-pairs.
2080 """
2081 super().__init__(name, keyValuePairs)
2083 self._verticesWithoutID = []
2084 self._verticesWithID = {}
2085 self._edgesWithoutID = []
2086 self._edgesWithID = {}
2087 self._linksWithoutID = []
2088 self._linksWithID = {}
2090 def __del__(self):
2091 """
2092 .. todo:: GRAPH::BaseGraph::del Needs documentation.
2094 """
2095 try:
2096 del self._verticesWithoutID
2097 del self._verticesWithID
2098 del self._edgesWithoutID
2099 del self._edgesWithID
2100 del self._linksWithoutID
2101 del self._linksWithID
2102 except AttributeError:
2103 pass
2105 super().__del__()
2107 @readonly
2108 def VertexCount(self) -> int:
2109 """Read-only property to access the number of vertices in this graph.
2111 :returns: The number of vertices in this graph."""
2112 return len(self._verticesWithoutID) + len(self._verticesWithID)
2114 @readonly
2115 def EdgeCount(self) -> int:
2116 """Read-only property to access the number of edges in this graph.
2118 :returns: The number of edges in this graph."""
2119 return len(self._edgesWithoutID) + len(self._edgesWithID)
2121 @readonly
2122 def LinkCount(self) -> int:
2123 """Read-only property to access the number of links in this graph.
2125 :returns: The number of links in this graph."""
2126 return len(self._linksWithoutID) + len(self._linksWithID)
2128 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]:
2129 """
2130 Iterate all or selected vertices of a graph.
2132 If parameter ``predicate`` is not None, the given filter function is used to skip vertices in the generator.
2134 :param predicate: Filter function accepting any vertex and returning a boolean.
2135 :returns: A generator to iterate all vertices.
2136 """
2137 if predicate is None:
2138 yield from self._verticesWithoutID
2139 yield from self._verticesWithID.values()
2141 else:
2142 for vertex in self._verticesWithoutID:
2143 if predicate(vertex):
2144 yield vertex
2146 for vertex in self._verticesWithID.values():
2147 if predicate(vertex):
2148 yield vertex
2150 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]:
2151 """
2152 Iterate all or selected roots (vertices without inbound edges / without predecessors) of a graph.
2154 If parameter ``predicate`` is not None, the given filter function is used to skip vertices in the generator.
2156 :param predicate: Filter function accepting any vertex and returning a boolean.
2157 :returns: A generator to iterate all vertices without inbound edges.
2159 .. seealso::
2161 :meth:`IterateLeafs` |br|
2162 |rarr| Iterate leafs of a graph.
2163 :meth:`Vertex.IsRoot <pyTooling.Graph.Vertex.IsRoot>` |br|
2164 |rarr| Check if a vertex is a root vertex in the graph.
2165 :meth:`Vertex.IsLeaf <pyTooling.Graph.Vertex.IsLeaf>` |br|
2166 |rarr| Check if a vertex is a leaf vertex in the graph.
2167 """
2168 if predicate is None:
2169 for vertex in self._verticesWithoutID:
2170 if len(vertex._inboundEdges) == 0:
2171 yield vertex
2173 for vertex in self._verticesWithID.values(): 2173 ↛ 2174line 2173 didn't jump to line 2174 because the loop on line 2173 never started
2174 if len(vertex._inboundEdges) == 0:
2175 yield vertex
2176 else:
2177 for vertex in self._verticesWithoutID:
2178 if len(vertex._inboundEdges) == 0 and predicate(vertex):
2179 yield vertex
2181 for vertex in self._verticesWithID.values(): 2181 ↛ 2182line 2181 didn't jump to line 2182 because the loop on line 2181 never started
2182 if len(vertex._inboundEdges) == 0 and predicate(vertex):
2183 yield vertex
2185 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]:
2186 """
2187 Iterate all or selected leafs (vertices without outbound edges / without successors) of a graph.
2189 If parameter ``predicate`` is not None, the given filter function is used to skip vertices in the generator.
2191 :param predicate: Filter function accepting any vertex and returning a boolean.
2192 :returns: A generator to iterate all vertices without outbound edges.
2194 .. seealso::
2196 :meth:`IterateRoots` |br|
2197 |rarr| Iterate roots of a graph.
2198 :meth:`Vertex.IsRoot <pyTooling.Graph.Vertex.IsRoot>` |br|
2199 |rarr| Check if a vertex is a root vertex in the graph.
2200 :meth:`Vertex.IsLeaf <pyTooling.Graph.Vertex.IsLeaf>` |br|
2201 |rarr| Check if a vertex is a leaf vertex in the graph.
2202 """
2203 if predicate is None:
2204 for vertex in self._verticesWithoutID:
2205 if len(vertex._outboundEdges) == 0:
2206 yield vertex
2208 for vertex in self._verticesWithID.values():
2209 if len(vertex._outboundEdges) == 0:
2210 yield vertex
2211 else:
2212 for vertex in self._verticesWithoutID:
2213 if len(vertex._outboundEdges) == 0 and predicate(vertex):
2214 yield vertex
2216 for vertex in self._verticesWithID.values():
2217 if len(vertex._outboundEdges) == 0 and predicate(vertex): 2217 ↛ 2218line 2217 didn't jump to line 2218 because the condition on line 2217 was never true
2218 yield vertex
2220 # 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]:
2221 # raise NotImplementedError()
2222 #
2223 # 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]:
2224 # raise NotImplementedError()
2226 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]:
2227 """
2228 Iterate all or selected vertices in topological order.
2230 If parameter ``predicate`` is not None, the given filter function is used to skip vertices in the generator.
2232 :param predicate: Filter function accepting any vertex and returning a boolean.
2233 :returns: A generator to iterate all vertices in topological order.
2234 :except CycleError: Raised if graph is cyclic, thus topological sorting isn't possible.
2235 """
2236 outboundEdgeCounts = {}
2237 leafVertices = []
2239 for vertex in self._verticesWithoutID:
2240 if (count := len(vertex._outboundEdges)) == 0:
2241 leafVertices.append(vertex)
2242 else:
2243 outboundEdgeCounts[vertex] = count
2245 for vertex in self._verticesWithID.values():
2246 if (count := len(vertex._outboundEdges)) == 0:
2247 leafVertices.append(vertex)
2248 else:
2249 outboundEdgeCounts[vertex] = count
2251 if not leafVertices: 2251 ↛ 2252line 2251 didn't jump to line 2252 because the condition on line 2251 was never true
2252 raise CycleError(f"Graph has no leafs. Thus, no topological sorting exists.")
2254 overallCount = len(outboundEdgeCounts) + len(leafVertices)
2256 def removeVertex(vertex: Vertex):
2257 nonlocal overallCount
2258 overallCount -= 1
2259 for inboundEdge in vertex._inboundEdges:
2260 sourceVertex = inboundEdge.Source
2261 count = outboundEdgeCounts[sourceVertex] - 1
2262 outboundEdgeCounts[sourceVertex] = count
2263 if count == 0:
2264 leafVertices.append(sourceVertex)
2266 if predicate is None:
2267 for vertex in leafVertices:
2268 yield vertex
2270 removeVertex(vertex)
2271 else:
2272 for vertex in leafVertices:
2273 if predicate(vertex):
2274 yield vertex
2276 removeVertex(vertex)
2278 if overallCount == 0: 2278 ↛ 2280line 2278 didn't jump to line 2280 because the condition on line 2278 was always true
2279 return
2280 elif overallCount > 0:
2281 raise CycleError(f"Graph has remaining vertices. Thus, the graph has at least one cycle.")
2283 raise InternalError(f"Graph data structure is corrupted.") # pragma: no cover
2285 def IterateEdges(self, predicate: Nullable[Callable[[Edge], bool]] = None) -> Generator[Edge[EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType], None, None]:
2286 """
2287 Iterate all or selected edges of a graph.
2289 If parameter ``predicate`` is not None, the given filter function is used to skip edges in the generator.
2291 :param predicate: Filter function accepting any edge and returning a boolean.
2292 :returns: A generator to iterate all edges.
2293 """
2294 if predicate is None:
2295 yield from self._edgesWithoutID
2296 yield from self._edgesWithID.values()
2298 else:
2299 for edge in self._edgesWithoutID:
2300 if predicate(edge):
2301 yield edge
2303 for edge in self._edgesWithID.values():
2304 if predicate(edge):
2305 yield edge
2307 def IterateLinks(self, predicate: Nullable[Callable[[Link], bool]] = None) -> Generator[Link[LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType], None, None]:
2308 """
2309 Iterate all or selected links of a graph.
2311 If parameter ``predicate`` is not None, the given filter function is used to skip links in the generator.
2313 :param predicate: Filter function accepting any link and returning a boolean.
2314 :returns: A generator to iterate all links.
2315 """
2316 if predicate is None: 2316 ↛ 2321line 2316 didn't jump to line 2321 because the condition on line 2316 was always true
2317 yield from self._linksWithoutID
2318 yield from self._linksWithID.values()
2320 else:
2321 for link in self._linksWithoutID:
2322 if predicate(link):
2323 yield link
2325 for link in self._linksWithID.values():
2326 if predicate(link):
2327 yield link
2329 def ReverseEdges(self, predicate: Nullable[Callable[[Edge], bool]] = None) -> None:
2330 """
2331 Reverse all or selected edges of a graph.
2333 If parameter ``predicate`` is not None, the given filter function is used to skip edges.
2335 :param predicate: Filter function accepting any edge and returning a boolean.
2336 """
2337 if predicate is None:
2338 for edge in self._edgesWithoutID:
2339 swap = edge._source
2340 edge._source = edge._destination
2341 edge._destination = swap
2343 for edge in self._edgesWithID.values():
2344 swap = edge._source
2345 edge._source = edge._destination
2346 edge._destination = swap
2348 for vertex in self._verticesWithoutID:
2349 swap = vertex._inboundEdges
2350 vertex._inboundEdges = vertex._outboundEdges
2351 vertex._outboundEdges = swap
2353 for vertex in self._verticesWithID.values():
2354 swap = vertex._inboundEdges
2355 vertex._inboundEdges = vertex._outboundEdges
2356 vertex._outboundEdges = swap
2357 else:
2358 for edge in self._edgesWithoutID:
2359 if predicate(edge):
2360 edge.Reverse()
2362 for edge in self._edgesWithID.values():
2363 if predicate(edge):
2364 edge.Reverse()
2366 def ReverseLinks(self, predicate: Nullable[Callable[[Link], bool]] = None) -> None:
2367 """
2368 Reverse all or selected links of a graph.
2370 If parameter ``predicate`` is not None, the given filter function is used to skip links.
2372 :param predicate: Filter function accepting any link and returning a boolean.
2373 """
2374 if predicate is None:
2375 for link in self._linksWithoutID:
2376 swap = link._source
2377 link._source = link._destination
2378 link._destination = swap
2380 for link in self._linksWithID.values():
2381 swap = link._source
2382 link._source = link._destination
2383 link._destination = swap
2385 for vertex in self._verticesWithoutID:
2386 swap = vertex._inboundLinks
2387 vertex._inboundLinks = vertex._outboundLinks
2388 vertex._outboundLinks = swap
2390 for vertex in self._verticesWithID.values():
2391 swap = vertex._inboundLinks
2392 vertex._inboundLinks = vertex._outboundLinks
2393 vertex._outboundLinks = swap
2394 else:
2395 for link in self._linksWithoutID:
2396 if predicate(link):
2397 link.Reverse()
2399 for link in self._linksWithID.values():
2400 if predicate(link):
2401 link.Reverse()
2403 def RemoveEdges(self, predicate: Nullable[Callable[[Edge], bool]] = None):
2404 """
2405 Remove all or selected edges of a graph.
2407 If parameter ``predicate`` is not None, the given filter function is used to skip edges.
2409 :param predicate: Filter function accepting any edge and returning a boolean.
2410 """
2411 if predicate is None:
2412 for edge in self._edgesWithoutID:
2413 edge._Delete()
2415 for edge in self._edgesWithID.values():
2416 edge._Delete()
2418 self._edgesWithoutID = []
2419 self._edgesWithID = {}
2421 for vertex in self._verticesWithoutID:
2422 vertex._inboundEdges = []
2423 vertex._outboundEdges = []
2425 for vertex in self._verticesWithID.values():
2426 vertex._inboundEdges = []
2427 vertex._outboundEdges = []
2429 else:
2430 delEdges = [edge for edge in self._edgesWithID.values() if predicate(edge)]
2431 for edge in delEdges:
2432 del self._edgesWithID[edge._id]
2434 edge._source._outboundEdges.remove(edge)
2435 edge._destination._inboundEdges.remove(edge)
2436 edge._Delete()
2438 for edge in self._edgesWithoutID:
2439 if predicate(edge):
2440 self._edgesWithoutID.remove(edge)
2442 edge._source._outboundEdges.remove(edge)
2443 edge._destination._inboundEdges.remove(edge)
2444 edge._Delete()
2446 def RemoveLinks(self, predicate: Nullable[Callable[[Link], bool]] = None):
2447 """
2448 Remove all or selected links of a graph.
2450 If parameter ``predicate`` is not None, the given filter function is used to skip links.
2452 :param predicate: Filter function accepting any link and returning a boolean.
2453 """
2454 if predicate is None:
2455 for link in self._linksWithoutID:
2456 link._Delete()
2458 for link in self._linksWithID.values():
2459 link._Delete()
2461 self._linksWithoutID = []
2462 self._linksWithID = {}
2464 for vertex in self._verticesWithoutID:
2465 vertex._inboundLinks = []
2466 vertex._outboundLinks = []
2468 for vertex in self._verticesWithID.values():
2469 vertex._inboundLinks = []
2470 vertex._outboundLinks = []
2472 else:
2473 delLinks = [link for link in self._linksWithID.values() if predicate(link)]
2474 for link in delLinks:
2475 del self._linksWithID[link._id]
2477 link._source._outboundLinks.remove(link)
2478 link._destination._inboundLinks.remove(link)
2479 link._Delete()
2481 for link in self._linksWithoutID:
2482 if predicate(link):
2483 self._linksWithoutID.remove(link)
2485 link._source._outboundLinks.remove(link)
2486 link._destination._inboundLinks.remove(link)
2487 link._Delete()
2489 def HasCycle(self) -> bool:
2490 """
2491 .. todo:: GRAPH::BaseGraph::HasCycle Needs documentation.
2493 """
2494 # IsAcyclic ?
2496 # Handle trivial case if graph is empty
2497 if len(self._verticesWithID) + len(self._verticesWithoutID) == 0: 2497 ↛ 2498line 2497 didn't jump to line 2498 because the condition on line 2497 was never true
2498 return False
2500 outboundEdgeCounts = {}
2501 leafVertices = []
2503 for vertex in self._verticesWithoutID:
2504 if (count := len(vertex._outboundEdges)) == 0:
2505 leafVertices.append(vertex)
2506 else:
2507 outboundEdgeCounts[vertex] = count
2509 for vertex in self._verticesWithID.values():
2510 if (count := len(vertex._outboundEdges)) == 0:
2511 leafVertices.append(vertex)
2512 else:
2513 outboundEdgeCounts[vertex] = count
2515 # If there are no leafs, then each vertex has at least one inbound and one outbound edges. Thus, there is a cycle.
2516 if not leafVertices: 2516 ↛ 2517line 2516 didn't jump to line 2517 because the condition on line 2516 was never true
2517 return True
2519 overallCount = len(outboundEdgeCounts) + len(leafVertices)
2521 for vertex in leafVertices:
2522 overallCount -= 1
2523 for inboundEdge in vertex._inboundEdges:
2524 sourceVertex = inboundEdge.Source
2525 count = outboundEdgeCounts[sourceVertex] - 1
2526 outboundEdgeCounts[sourceVertex] = count
2527 if count == 0:
2528 leafVertices.append(sourceVertex)
2530 # If all vertices were processed, no cycle exists.
2531 if overallCount == 0:
2532 return False
2533 # If there are remaining vertices, then a cycle exists.
2534 elif overallCount > 0:
2535 return True
2537 raise InternalError(f"Graph data structure is corrupted.") # pragma: no cover
2540@export
2541class Subgraph(
2542 BaseGraph[
2543 SubgraphDictKeyType, SubgraphDictValueType,
2544 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,
2545 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,
2546 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType
2547 ],
2548 Generic[
2549 SubgraphDictKeyType, SubgraphDictValueType,
2550 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,
2551 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,
2552 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType
2553 ]
2554):
2555 """
2556 .. todo:: GRAPH::Subgraph Needs documentation.
2558 """
2560 _graph: 'Graph'
2562 def __init__(
2563 self,
2564 graph: 'Graph',
2565 name: Nullable[str] = None,
2566 # vertices: Nullable[Iterable[Vertex]] = None,
2567 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None
2568 ) -> None:
2569 """
2570 .. todo:: GRAPH::Subgraph::init Needs documentation.
2572 :param graph: The reference to the graph.
2573 :param name: The optional name of the new sub-graph.
2574 :param keyValuePairs: The optional mapping (dictionary) of key-value-pairs.
2575 """
2576 if graph is None: 2576 ↛ 2577line 2576 didn't jump to line 2577 because the condition on line 2576 was never true
2577 raise ValueError("Parameter 'graph' is None.")
2578 if not isinstance(graph, Graph): 2578 ↛ 2579line 2578 didn't jump to line 2579 because the condition on line 2578 was never true
2579 ex = TypeError("Parameter 'graph' is not of type 'Graph'.")
2580 ex.add_note(f"Got type '{getFullyQualifiedName(graph)}'.")
2581 raise ex
2583 super().__init__(name, keyValuePairs)
2585 graph._subgraphs.add(self)
2587 self._graph = graph
2589 def __del__(self):
2590 """
2591 .. todo:: GRAPH::Subgraph::del Needs documentation.
2593 """
2594 super().__del__()
2596 @readonly
2597 def Graph(self) -> 'Graph':
2598 """
2599 Read-only property to access the graph, this subgraph is associated to (:attr:`_graph`).
2601 :returns: The graph this subgraph is associated to.
2602 """
2603 return self._graph
2605 def __str__(self) -> str:
2606 """
2607 .. todo:: GRAPH::Subgraph::str Needs documentation.
2609 """
2610 return self._name if self._name is not None else "Unnamed subgraph"
2613@export
2614class View(
2615 BaseWithVertices[
2616 ViewDictKeyType, ViewDictValueType,
2617 GraphDictKeyType, GraphDictValueType,
2618 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,
2619 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,
2620 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType
2621 ],
2622 Generic[
2623 ViewDictKeyType, ViewDictValueType,
2624 GraphDictKeyType, GraphDictValueType,
2625 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,
2626 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,
2627 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType
2628 ]
2629):
2630 """
2631 .. todo:: GRAPH::View Needs documentation.
2633 """
2635 def __init__(
2636 self,
2637 graph: 'Graph',
2638 name: Nullable[str] = None,
2639 vertices: Nullable[Iterable[Vertex]] = None,
2640 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None
2641 ) -> None:
2642 """
2643 .. todo:: GRAPH::View::init Needs documentation.
2645 :param graph: The reference to the graph.
2646 :param name: The optional name of the new view.
2647 :param vertices: The optional list of vertices in the new view.
2648 :param keyValuePairs: The optional mapping (dictionary) of key-value-pairs.
2649 """
2650 super().__init__(graph, name, vertices, keyValuePairs)
2652 graph._views.add(self)
2654 def __del__(self):
2655 """
2656 .. todo:: GRAPH::View::del Needs documentation.
2658 """
2659 super().__del__()
2661 def __str__(self) -> str:
2662 """
2663 .. todo:: GRAPH::View::str Needs documentation.
2665 """
2666 return self._name if self._name is not None else "Unnamed view"
2669@export
2670class Component(
2671 BaseWithVertices[
2672 ComponentDictKeyType, ComponentDictValueType,
2673 GraphDictKeyType, GraphDictValueType,
2674 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,
2675 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,
2676 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType
2677 ],
2678 Generic[
2679 ComponentDictKeyType, ComponentDictValueType,
2680 GraphDictKeyType, GraphDictValueType,
2681 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,
2682 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,
2683 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType
2684 ]
2685):
2686 """
2687 .. todo:: GRAPH::Component Needs documentation.
2689 """
2691 def __init__(
2692 self,
2693 graph: 'Graph',
2694 name: Nullable[str] = None,
2695 vertices: Nullable[Iterable[Vertex]] = None,
2696 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None
2697 ) -> None:
2698 """
2699 .. todo:: GRAPH::Component::init Needs documentation.
2701 :param graph: The reference to the graph.
2702 :param name: The optional name of the new component.
2703 :param vertices: The optional list of vertices in the new component.
2704 :param keyValuePairs: The optional mapping (dictionary) of key-value-pairs.
2705 """
2706 super().__init__(graph, name, vertices, keyValuePairs)
2708 graph._components.add(self)
2710 def __del__(self):
2711 """
2712 .. todo:: GRAPH::Component::del Needs documentation.
2714 """
2715 super().__del__()
2717 def __str__(self) -> str:
2718 """
2719 .. todo:: GRAPH::Component::str Needs documentation.
2721 """
2722 return self._name if self._name is not None else "Unnamed component"
2725@export
2726class Graph(
2727 BaseGraph[
2728 GraphDictKeyType, GraphDictValueType,
2729 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,
2730 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,
2731 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType
2732 ],
2733 Generic[
2734 GraphDictKeyType, GraphDictValueType,
2735 ComponentDictKeyType, ComponentDictValueType,
2736 SubgraphDictKeyType, SubgraphDictValueType,
2737 ViewDictKeyType, ViewDictValueType,
2738 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,
2739 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,
2740 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType
2741 ]
2742):
2743 """
2744 A **graph** data structure is represented by an instance of :class:`~pyTooling.Graph.Graph` holding references to
2745 all nodes. Nodes are instances of :class:`~pyTooling.Graph.Vertex` classes and directed links between nodes are
2746 made of :class:`~pyTooling.Graph.Edge` instances. A graph can have attached meta information as key-value-pairs.
2747 """
2748 _subgraphs: Set[Subgraph[SubgraphDictKeyType, SubgraphDictValueType, VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType, EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType, LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType]]
2749 _views: Set[View[ViewDictKeyType, ViewDictValueType, GraphDictKeyType, GraphDictValueType, VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType, EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType, LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType]]
2750 _components: Set[Component[ComponentDictKeyType, ComponentDictValueType, GraphDictKeyType, GraphDictValueType, VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType, EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType, LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType]]
2752 def __init__(
2753 self,
2754 name: Nullable[str] = None,
2755 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None
2756 ) -> None:
2757 """
2758 .. todo:: GRAPH::Graph::init Needs documentation.
2760 :param name: The optional name of the new graph.
2761 :param keyValuePairs: The optional mapping (dictionary) of key-value-pairs.#
2762 """
2763 super().__init__(name, keyValuePairs)
2765 self._subgraphs = set()
2766 self._views = set()
2767 self._components = set()
2769 def __del__(self):
2770 """
2771 .. todo:: GRAPH::Graph::del Needs documentation.
2773 """
2774 try:
2775 del self._subgraphs
2776 del self._views
2777 del self._components
2778 except AttributeError:
2779 pass
2781 super().__del__()
2783 @readonly
2784 def Subgraphs(self) -> Set[Subgraph]:
2785 """Read-only property to access the subgraphs in this graph (:attr:`_subgraphs`).
2787 :returns: The set of subgraphs in this graph."""
2788 return self._subgraphs
2790 @readonly
2791 def Views(self) -> Set[View]:
2792 """Read-only property to access the views in this graph (:attr:`_views`).
2794 :returns: The set of views in this graph."""
2795 return self._views
2797 @readonly
2798 def Components(self) -> Set[Component]:
2799 """Read-only property to access the components in this graph (:attr:`_components`).
2801 :returns: The set of components in this graph."""
2802 return self._components
2804 @readonly
2805 def SubgraphCount(self) -> int:
2806 """Read-only property to access the number of subgraphs in this graph.
2808 :returns: The number of subgraphs in this graph."""
2809 return len(self._subgraphs)
2811 @readonly
2812 def ViewCount(self) -> int:
2813 """Read-only property to access the number of views in this graph.
2815 :returns: The number of views in this graph."""
2816 return len(self._views)
2818 @readonly
2819 def ComponentCount(self) -> int:
2820 """Read-only property to access the number of components in this graph.
2822 :returns: The number of components in this graph."""
2823 return len(self._components)
2825 def __iter__(self) -> typing_Iterator[Vertex[GraphDictKeyType, GraphDictValueType, VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType, EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType, LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType]]:
2826 """
2827 .. todo:: GRAPH::Graph::iter Needs documentation.
2829 """
2830 def gen():
2831 yield from self._verticesWithoutID
2832 yield from self._verticesWithID
2833 return iter(gen())
2835 def HasVertexByID(self, vertexID: Nullable[VertexIDType]) -> bool:
2836 """
2837 .. todo:: GRAPH::Graph::HasVertexByID Needs documentation.
2839 """
2840 if vertexID is None:
2841 return len(self._verticesWithoutID) >= 1
2842 else:
2843 return vertexID in self._verticesWithID
2845 def HasVertexByValue(self, value: Nullable[VertexValueType]) -> bool:
2846 """
2847 .. todo:: GRAPH::Graph::HasVertexByValue Needs documentation.
2849 """
2850 return any(vertex._value == value for vertex in chain(self._verticesWithoutID, self._verticesWithID.values()))
2852 def GetVertexByID(self, vertexID: Nullable[VertexIDType]) -> Vertex:
2853 """
2854 .. todo:: GRAPH::Graph::GetVertexByID Needs documentation.
2856 """
2857 if vertexID is None:
2858 if (l := len(self._verticesWithoutID)) == 1:
2859 return self._verticesWithoutID[0]
2860 elif l == 0:
2861 raise KeyError(f"Found no vertex with ID `None`.")
2862 else:
2863 raise KeyError(f"Found multiple vertices with ID `None`.")
2864 else:
2865 return self._verticesWithID[vertexID]
2867 def GetVertexByValue(self, value: Nullable[VertexValueType]) -> Vertex:
2868 """
2869 .. todo:: GRAPH::Graph::GetVertexByValue Needs documentation.
2871 """
2872 # FIXME: optimize: iterate only until first item is found and check for a second to produce error
2873 vertices = [vertex for vertex in chain(self._verticesWithoutID, self._verticesWithID.values()) if vertex._value == value]
2874 if (l := len(vertices)) == 1:
2875 return vertices[0]
2876 elif l == 0:
2877 raise KeyError(f"Found no vertex with Value == `{value}`.")
2878 else:
2879 raise KeyError(f"Found multiple vertices with Value == `{value}`.")
2881 def CopyGraph(self) -> 'Graph':
2882 raise NotImplementedError()
2884 def CopyVertices(self, predicate: Nullable[Callable[[Vertex], bool]] = None, copyGraphDict: bool = True, copyVertexDict: bool = True) -> 'Graph':
2885 """
2886 Create a new graph and copy all or selected vertices of the original graph.
2888 If parameter ``predicate`` is not None, the given filter function is used to skip vertices.
2890 :param predicate: Filter function accepting any vertex and returning a boolean.
2891 :param copyGraphDict: If ``True``, copy all graph attached attributes into the new graph.
2892 :param copyVertexDict: If ``True``, copy all vertex attached attributes into the new vertices.
2893 """
2894 graph = Graph(self._name)
2895 if copyGraphDict:
2896 graph._dict = self._dict.copy()
2898 if predicate is None:
2899 for vertex in self._verticesWithoutID:
2900 v = Vertex(None, vertex._value, graph=graph)
2901 if copyVertexDict:
2902 v._dict = vertex._dict.copy()
2904 for vertexID, vertex in self._verticesWithID.items():
2905 v = Vertex(vertexID, vertex._value, graph=graph)
2906 if copyVertexDict:
2907 v._dict = vertex._dict.copy()
2908 else:
2909 for vertex in self._verticesWithoutID:
2910 if predicate(vertex):
2911 v = Vertex(None, vertex._value, graph=graph)
2912 if copyVertexDict: 2912 ↛ 2909line 2912 didn't jump to line 2909 because the condition on line 2912 was always true
2913 v._dict = vertex._dict.copy()
2915 for vertexID, vertex in self._verticesWithID.items():
2916 if predicate(vertex):
2917 v = Vertex(vertexID, vertex._value, graph=graph)
2918 if copyVertexDict: 2918 ↛ 2919line 2918 didn't jump to line 2919 because the condition on line 2918 was never true
2919 v._dict = vertex._dict.copy()
2921 return graph
2923 # class Iterator():
2924 # visited = [False for _ in range(self.__len__())]
2926 # def CheckForNegativeCycles(self):
2927 # raise NotImplementedError()
2928 # # Bellman-Ford
2929 # # Floyd-Warshall
2930 #
2931 # def IsStronglyConnected(self):
2932 # raise NotImplementedError()
2933 #
2934 # def GetStronglyConnectedComponents(self):
2935 # raise NotImplementedError()
2936 # # Tarjan's and Kosaraju's algorithm
2937 #
2938 # def TravelingSalesmanProblem(self):
2939 # raise NotImplementedError()
2940 # # Held-Karp
2941 # # branch and bound
2942 #
2943 # def GetBridges(self):
2944 # raise NotImplementedError()
2945 #
2946 # def GetArticulationPoints(self):
2947 # raise NotImplementedError()
2948 #
2949 # def MinimumSpanningTree(self):
2950 # raise NotImplementedError()
2951 # # Kruskal
2952 # # Prim's algorithm
2953 # # Buruvka's algorithm
2955 def __repr__(self) -> str:
2956 """
2957 .. todo:: GRAPH::Graph::repr Needs documentation.
2959 """
2960 statistics = f", vertices: {self.VertexCount}, edges: {self.EdgeCount}"
2961 if self._name is None:
2962 return f"<graph: unnamed graph{statistics}>"
2963 else:
2964 return f"<graph: '{self._name}'{statistics}>"
2966 def __str__(self) -> str:
2967 """
2968 .. todo:: GRAPH::Graph::str Needs documentation.
2970 """
2971 if self._name is None:
2972 return f"Graph: unnamed graph"
2973 else:
2974 return f"Graph: '{self._name}'"