Coverage for pyTooling / Graph / __init__.py: 76%
1211 statements
« prev ^ index » next coverage.py v7.12.0, created at 2025-11-21 22:22 +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 typing import TypeVar, Generic, List, Tuple, Dict, Set, Deque, Union, Optional as Nullable
59from typing import Callable, Iterator as typing_Iterator, Generator, Iterable, Mapping, Hashable
61try:
62 from pyTooling.Decorators import export, readonly
63 from pyTooling.MetaClasses import ExtendedType
64 from pyTooling.Exceptions import ToolingException
65 from pyTooling.Common import getFullyQualifiedName
66 from pyTooling.Tree import Node
67except (ImportError, ModuleNotFoundError): # pragma: no cover
68 print("[pyTooling.Graph] Could not import from 'pyTooling.*'!")
70 try:
71 from Decorators import export, readonly
72 from MetaClasses import ExtendedType, mixin
73 from Exceptions import ToolingException
74 from Common import getFullyQualifiedName
75 from Tree import Node
76 except (ImportError, ModuleNotFoundError) as ex: # pragma: no cover
77 print("[pyTooling.Graph] Could not import directly!")
78 raise ex
81DictKeyType = TypeVar("DictKeyType", bound=Hashable)
82"""A type variable for dictionary keys."""
84DictValueType = TypeVar("DictValueType")
85"""A type variable for dictionary values."""
87IDType = TypeVar("IDType", bound=Hashable)
88"""A type variable for an ID."""
90WeightType = TypeVar("WeightType", bound=Union[int, float])
91"""A type variable for a weight."""
93ValueType = TypeVar("ValueType")
94"""A type variable for a value."""
96VertexIDType = TypeVar("VertexIDType", bound=Hashable)
97"""A type variable for a vertex's ID."""
99VertexWeightType = TypeVar("VertexWeightType", bound=Union[int, float])
100"""A type variable for a vertex's weight."""
102VertexValueType = TypeVar("VertexValueType")
103"""A type variable for a vertex's value."""
105VertexDictKeyType = TypeVar("VertexDictKeyType", bound=Hashable)
106"""A type variable for a vertex's dictionary keys."""
108VertexDictValueType = TypeVar("VertexDictValueType")
109"""A type variable for a vertex's dictionary values."""
111EdgeIDType = TypeVar("EdgeIDType", bound=Hashable)
112"""A type variable for an edge's ID."""
114EdgeWeightType = TypeVar("EdgeWeightType", bound=Union[int, float])
115"""A type variable for an edge's weight."""
117EdgeValueType = TypeVar("EdgeValueType")
118"""A type variable for an edge's value."""
120EdgeDictKeyType = TypeVar("EdgeDictKeyType", bound=Hashable)
121"""A type variable for an edge's dictionary keys."""
123EdgeDictValueType = TypeVar("EdgeDictValueType")
124"""A type variable for an edge's dictionary values."""
126LinkIDType = TypeVar("LinkIDType", bound=Hashable)
127"""A type variable for an link's ID."""
129LinkWeightType = TypeVar("LinkWeightType", bound=Union[int, float])
130"""A type variable for an link's weight."""
132LinkValueType = TypeVar("LinkValueType")
133"""A type variable for an link's value."""
135LinkDictKeyType = TypeVar("LinkDictKeyType", bound=Hashable)
136"""A type variable for an link's dictionary keys."""
138LinkDictValueType = TypeVar("LinkDictValueType")
139"""A type variable for an link's dictionary values."""
141ComponentDictKeyType = TypeVar("ComponentDictKeyType", bound=Hashable)
142"""A type variable for a component's dictionary keys."""
144ComponentDictValueType = TypeVar("ComponentDictValueType")
145"""A type variable for a component's dictionary values."""
147SubgraphDictKeyType = TypeVar("SubgraphDictKeyType", bound=Hashable)
148"""A type variable for a component's dictionary keys."""
150SubgraphDictValueType = TypeVar("SubgraphDictValueType")
151"""A type variable for a component's dictionary values."""
153ViewDictKeyType = TypeVar("ViewDictKeyType", bound=Hashable)
154"""A type variable for a component's dictionary keys."""
156ViewDictValueType = TypeVar("ViewDictValueType")
157"""A type variable for a component's dictionary values."""
159GraphDictKeyType = TypeVar("GraphDictKeyType", bound=Hashable)
160"""A type variable for a graph's dictionary keys."""
162GraphDictValueType = TypeVar("GraphDictValueType")
163"""A type variable for a graph's dictionary values."""
166@export
167class GraphException(ToolingException):
168 """Base exception of all exceptions raised by :mod:`pyTooling.Graph`."""
171@export
172class InternalError(GraphException):
173 """
174 The exception is raised when a data structure corruption is detected.
176 .. danger::
178 This exception should never be raised.
180 If so, please create an issue at GitHub so the data structure corruption can be investigated and fixed. |br|
181 `⇒ Bug Tracker at GitHub <https://github.com/pyTooling/pyTooling/issues>`__
182 """
185@export
186class NotInSameGraph(GraphException):
187 """The exception is raised when creating an edge between two vertices, but these are not in the same graph."""
190@export
191class DuplicateVertexError(GraphException):
192 """The exception is raised when the vertex already exists in the graph."""
195@export
196class DuplicateEdgeError(GraphException):
197 """The exception is raised when the edge already exists in the graph."""
200@export
201class DestinationNotReachable(GraphException):
202 """The exception is raised when a destination vertex is not reachable."""
205@export
206class NotATreeError(GraphException):
207 """
208 The exception is raised when a subgraph is not a tree.
210 Either the subgraph has a cycle (backward edge) or links between branches (cross-edge).
211 """
214@export
215class CycleError(GraphException):
216 """The exception is raised when a not permitted cycle is found."""
219@export
220class Base(
221 Generic[DictKeyType, DictValueType],
222 metaclass=ExtendedType, slots=True
223):
224 _dict: Dict[DictKeyType, DictValueType] #: A dictionary to store arbitrary key-value-pairs.
226 def __init__(
227 self,
228 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None
229 ) -> None:
230 """
231 .. todo:: GRAPH::Base::init Needs documentation.
233 :param keyValuePairs: The optional mapping (dictionary) of key-value-pairs.
234 """
235 self._dict = {key: value for key, value in keyValuePairs.items()} if keyValuePairs is not None else {}
237 def __del__(self):
238 """
239 .. todo:: GRAPH::Base::del Needs documentation.
241 """
242 try:
243 del self._dict
244 except AttributeError:
245 pass
247 def Delete(self) -> None:
248 self._dict = None
250 def __getitem__(self, key: DictKeyType) -> DictValueType:
251 """
252 Read a vertex's attached attributes (key-value-pairs) by key.
254 :param key: The key to look for.
255 :returns: The value associated to the given key.
256 """
257 return self._dict[key]
259 def __setitem__(self, key: DictKeyType, value: DictValueType) -> None:
260 """
261 Create or update a vertex's attached attributes (key-value-pairs) by key.
263 If a key doesn't exist yet, a new key-value-pair is created.
265 :param key: The key to create or update.
266 :param value: The value to associate to the given key.
267 """
268 self._dict[key] = value
270 def __delitem__(self, key: DictKeyType) -> None:
271 """
272 Remove an entry from vertex's attached attributes (key-value-pairs) by key.
274 :param key: The key to remove.
275 :raises KeyError: If key doesn't exist in the vertex's attributes.
276 """
277 del self._dict[key]
279 def __contains__(self, key: DictKeyType) -> bool:
280 """
281 Checks if the key is an attached attribute (key-value-pairs) on this vertex.
283 :param key: The key to check.
284 :returns: ``True``, if the key is an attached attribute.
285 """
286 return key in self._dict
288 def __len__(self) -> int:
289 """
290 Returns the number of attached attributes (key-value-pairs) on this vertex.
292 :returns: Number of attached attributes.
293 """
294 return len(self._dict)
297@export
298class BaseWithIDValueAndWeight(
299 Base[DictKeyType, DictValueType],
300 Generic[IDType, ValueType, WeightType, DictKeyType, DictValueType]
301):
302 _id: Nullable[IDType] #: Field storing the object's Identifier.
303 _value: Nullable[ValueType] #: Field storing the object's value of any type.
304 _weight: Nullable[WeightType] #: Field storing the object's weight.
306 def __init__(
307 self,
308 identifier: Nullable[IDType] = None,
309 value: Nullable[ValueType] = None,
310 weight: Nullable[WeightType] = None,
311 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None
312 ) -> None:
313 """
314 .. todo:: GRAPH::Vertex::init Needs documentation.
316 :param identifier: The optional unique ID.
317 :param value: The optional value.
318 :param weight: The optional weight.
319 :param keyValuePairs: The optional mapping (dictionary) of key-value-pairs.
320 """
321 super().__init__(keyValuePairs)
323 self._id = identifier
324 self._value = value
325 self._weight = weight
327 @readonly
328 def ID(self) -> Nullable[IDType]:
329 """
330 Read-only property to access the unique ID (:attr:`_id`).
332 If no ID was given at creation time, ID returns ``None``.
334 :returns: Unique ID, if ID was given at creation time, else ``None``.
335 """
336 return self._id
338 @property
339 def Value(self) -> ValueType:
340 """
341 Property to get and set the value (:attr:`_value`).
343 :returns: The value.
344 """
345 return self._value
347 @Value.setter
348 def Value(self, value: ValueType) -> None:
349 self._value = value
351 @property
352 def Weight(self) -> Nullable[EdgeWeightType]:
353 """
354 Property to get and set the weight (:attr:`_weight`) of an edge.
356 :returns: The weight of an edge.
357 """
358 return self._weight
360 @Weight.setter
361 def Weight(self, value: Nullable[EdgeWeightType]) -> None:
362 self._weight = value
365@export
366class BaseWithName(
367 Base[DictKeyType, DictValueType],
368 Generic[DictKeyType, DictValueType]
369):
370 _name: Nullable[str] #: Field storing the object's name.
372 def __init__(
373 self,
374 name: Nullable[str] = None,
375 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None,
376 ) -> None:
377 """
378 .. todo:: GRAPH::BaseWithName::init Needs documentation.
380 :param name: The optional name.
381 :param keyValuePairs: The optional mapping (dictionary) of key-value-pairs.
382 """
383 if name is not None and not isinstance(name, str):
384 ex = TypeError("Parameter 'name' is not of type 'str'.")
385 ex.add_note(f"Got type '{getFullyQualifiedName(name)}'.")
386 raise ex
388 super().__init__(keyValuePairs)
390 self._name = name
392 @property
393 def Name(self) -> Nullable[str]:
394 """
395 Property to get and set the name (:attr:`_name`).
397 :returns: The value of a component.
398 """
399 return self._name
401 @Name.setter
402 def Name(self, value: str) -> None:
403 if not isinstance(value, str):
404 ex = TypeError("Name is not of type 'str'.")
405 ex.add_note(f"Got type '{getFullyQualifiedName(value)}'.")
406 raise ex
408 self._name = value
411@export
412class BaseWithVertices(
413 BaseWithName[DictKeyType, DictValueType],
414 Generic[
415 DictKeyType, DictValueType,
416 GraphDictKeyType, GraphDictValueType,
417 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,
418 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,
419 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType
420 ]
421):
422 _graph: 'Graph[GraphDictKeyType, GraphDictValueType,' \
423 'VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,' \
424 'EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,' \
425 'LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType' \
426 ']' #: Field storing a reference to the graph.
427 _vertices: Set['Vertex[GraphDictKeyType, GraphDictValueType,'
428 'VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,'
429 'EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,'
430 'LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType'
431 ']'] #: Field storing a set of vertices.
433 def __init__(
434 self,
435 graph: 'Graph',
436 name: Nullable[str] = None,
437 vertices: Nullable[Iterable['Vertex']] = None,
438 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None
439 ) -> None:
440 """
441 .. todo:: GRAPH::Component::init Needs documentation.
443 :param graph: The reference to the graph.
444 :param name: The optional name.
445 :param vertices: The optional list of vertices.
446 :param keyValuePairs: The optional mapping (dictionary) of key-value-pairs.
447 """
448 if graph is None: 448 ↛ 449line 448 didn't jump to line 449 because the condition on line 448 was never true
449 raise ValueError("Parameter 'graph' is None.")
450 elif not isinstance(graph, Graph): 450 ↛ 451line 450 didn't jump to line 451 because the condition on line 450 was never true
451 ex = TypeError("Parameter 'graph' is not of type 'Graph'.")
452 ex.add_note(f"Got type '{getFullyQualifiedName(graph)}'.")
453 raise ex
455 super().__init__(name, keyValuePairs)
457 self._graph = graph
458 self._vertices = set() if vertices is None else {v for v in vertices}
460 def __del__(self):
461 """
462 .. todo:: GRAPH::BaseWithVertices::del Needs documentation.
464 """
465 try:
466 del self._vertices
467 except AttributeError:
468 pass
470 super().__del__()
472 @readonly
473 def Graph(self) -> 'Graph':
474 """
475 Read-only property to access the graph, this object is associated to (:attr:`_graph`).
477 :returns: The graph this object is associated to.
478 """
479 return self._graph
481 @readonly
482 def Vertices(self) -> Set['Vertex']:
483 """
484 Read-only property to access the vertices in this component (:attr:`_vertices`).
486 :returns: The set of vertices in this component.
487 """
488 return self._vertices
490 @readonly
491 def VertexCount(self) -> int:
492 """
493 Read-only property to access the number of vertices referenced by this object.
495 :returns: The number of vertices this object references.
496 """
497 return len(self._vertices)
500@export
501class Vertex(
502 BaseWithIDValueAndWeight[VertexIDType, VertexValueType, VertexWeightType, VertexDictKeyType, VertexDictValueType],
503 Generic[
504 GraphDictKeyType, GraphDictValueType,
505 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,
506 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,
507 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType
508 ]
509):
510 """
511 A **vertex** can have a unique ID, a value and attached meta information as key-value-pairs. A vertex has references
512 to inbound and outbound edges, thus a graph can be traversed in reverse.
513 """
514 _graph: 'BaseGraph[GraphDictKeyType, GraphDictValueType, VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType, EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType]' #: Field storing a reference to the graph.
515 _subgraph: 'Subgraph[GraphDictKeyType, GraphDictValueType, VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType, EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType]' #: Field storing a reference to the subgraph.
516 _component: 'Component'
517 _views: Dict[Hashable, 'View']
518 _inboundEdges: List['Edge[EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType]'] #: Field storing a list of inbound edges.
519 _outboundEdges: List['Edge[EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType]'] #: Field storing a list of outbound edges.
520 _inboundLinks: List['Link[EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType]'] #: Field storing a list of inbound links.
521 _outboundLinks: List['Link[EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType]'] #: Field storing a list of outbound links.
523 def __init__(
524 self,
525 vertexID: Nullable[VertexIDType] = None,
526 value: Nullable[VertexValueType] = None,
527 weight: Nullable[VertexWeightType] = None,
528 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None,
529 graph: Nullable['Graph'] = None,
530 subgraph: Nullable['Subgraph'] = None
531 ) -> None:
532 """
533 .. todo:: GRAPH::Vertex::init Needs documentation.
535 :param vertexID: The optional ID for the new vertex.
536 :param value: The optional value for the new vertex.
537 :param weight: The optional weight for the new vertex.
538 :param keyValuePairs: The optional mapping (dictionary) of key-value-pairs.
539 :param graph: The optional reference to the graph.
540 :param subgraph: undocumented
541 """
542 if vertexID is not None and not isinstance(vertexID, Hashable): 542 ↛ 543line 542 didn't jump to line 543 because the condition on line 542 was never true
543 ex = TypeError("Parameter 'vertexID' is not of type 'VertexIDType'.")
544 ex.add_note(f"Got type '{getFullyQualifiedName(vertexID)}'.")
545 raise ex
547 super().__init__(vertexID, value, weight, keyValuePairs)
549 if subgraph is None:
550 self._graph = graph if graph is not None else Graph()
551 self._subgraph = None
552 self._component = Component(self._graph, vertices=(self,))
554 if vertexID is None:
555 self._graph._verticesWithoutID.append(self)
556 elif vertexID not in self._graph._verticesWithID:
557 self._graph._verticesWithID[vertexID] = self
558 else:
559 raise DuplicateVertexError(f"Vertex ID '{vertexID}' already exists in this graph.")
560 else:
561 self._graph = subgraph._graph
562 self._subgraph = subgraph
563 self._component = Component(self._graph, vertices=(self,))
565 if vertexID is None:
566 subgraph._verticesWithoutID.append(self)
567 elif vertexID not in subgraph._verticesWithID: 567 ↛ 570line 567 didn't jump to line 570 because the condition on line 567 was always true
568 subgraph._verticesWithID[vertexID] = self
569 else:
570 raise DuplicateVertexError(f"Vertex ID '{vertexID}' already exists in this subgraph.")
572 self._views = {}
573 self._inboundEdges = []
574 self._outboundEdges = []
575 self._inboundLinks = []
576 self._outboundLinks = []
578 def __del__(self):
579 """
580 .. todo:: GRAPH::BaseEdge::del Needs documentation.
582 """
583 try:
584 del self._views
585 del self._inboundEdges
586 del self._outboundEdges
587 del self._inboundLinks
588 del self._outboundLinks
589 except AttributeError:
590 pass
592 super().__del__()
594 def Delete(self) -> None:
595 for edge in self._outboundEdges:
596 edge._destination._inboundEdges.remove(edge)
597 edge._Delete()
598 for edge in self._inboundEdges:
599 edge._source._outboundEdges.remove(edge)
600 edge._Delete()
601 for link in self._outboundLinks:
602 link._destination._inboundLinks.remove(link)
603 link._Delete()
604 for link in self._inboundLinks:
605 link._source._outboundLinks.remove(link)
606 link._Delete()
608 if self._id is None:
609 self._graph._verticesWithoutID.remove(self)
610 else:
611 del self._graph._verticesWithID[self._id]
613 # subgraph
615 # component
617 # views
618 self._views = None
619 self._inboundEdges = None
620 self._outboundEdges = None
621 self._inboundLinks = None
622 self._outboundLinks = None
624 super().Delete()
625 assert getrefcount(self) == 1
627 @readonly
628 def Graph(self) -> 'Graph':
629 """
630 Read-only property to access the graph, this vertex is associated to (:attr:`_graph`).
632 :returns: The graph this vertex is associated to.
633 """
634 return self._graph
636 @readonly
637 def Component(self) -> 'Component':
638 """
639 Read-only property to access the component, this vertex is associated to (:attr:`_component`).
641 :returns: The component this vertex is associated to.
642 """
643 return self._component
645 @readonly
646 def InboundEdges(self) -> Tuple['Edge', ...]:
647 """
648 Read-only property to get a tuple of inbound edges (:attr:`_inboundEdges`).
650 :returns: Tuple of inbound edges.
651 """
652 return tuple(self._inboundEdges)
654 @readonly
655 def OutboundEdges(self) -> Tuple['Edge', ...]:
656 """
657 Read-only property to get a tuple of outbound edges (:attr:`_outboundEdges`).
659 :returns: Tuple of outbound edges.
660 """
661 return tuple(self._outboundEdges)
663 @readonly
664 def InboundLinks(self) -> Tuple['Link', ...]:
665 """
666 Read-only property to get a tuple of inbound links (:attr:`_inboundLinks`).
668 :returns: Tuple of inbound links.
669 """
670 return tuple(self._inboundLinks)
672 @readonly
673 def OutboundLinks(self) -> Tuple['Link', ...]:
674 """
675 Read-only property to get a tuple of outbound links (:attr:`_outboundLinks`).
677 :returns: Tuple of outbound links.
678 """
679 return tuple(self._outboundLinks)
681 @readonly
682 def EdgeCount(self) -> int:
683 """
684 Read-only property to get the number of all edges (inbound and outbound).
686 :returns: Number of inbound and outbound edges.
687 """
688 return len(self._inboundEdges) + len(self._outboundEdges)
690 @readonly
691 def InboundEdgeCount(self) -> int:
692 """
693 Read-only property to get the number of inbound edges.
695 :returns: Number of inbound edges.
696 """
697 return len(self._inboundEdges)
699 @readonly
700 def OutboundEdgeCount(self) -> int:
701 """
702 Read-only property to get the number of outbound edges.
704 :returns: Number of outbound edges.
705 """
706 return len(self._outboundEdges)
708 @readonly
709 def LinkCount(self) -> int:
710 """
711 Read-only property to get the number of all links (inbound and outbound).
713 :returns: Number of inbound and outbound links.
714 """
715 return len(self._inboundLinks) + len(self._outboundLinks)
717 @readonly
718 def InboundLinkCount(self) -> int:
719 """
720 Read-only property to get the number of inbound links.
722 :returns: Number of inbound links.
723 """
724 return len(self._inboundLinks)
726 @readonly
727 def OutboundLinkCount(self) -> int:
728 """
729 Read-only property to get the number of outbound links.
731 :returns: Number of outbound links.
732 """
733 return len(self._outboundLinks)
735 @readonly
736 def IsRoot(self) -> bool:
737 """
738 Read-only property to check if this vertex is a root vertex in the graph.
740 A root has no inbound edges (no predecessor vertices).
742 :returns: ``True``, if this vertex is a root.
744 .. seealso::
746 :meth:`IsLeaf` |br|
747 |rarr| Check if a vertex is a leaf vertex in the graph.
748 :meth:`Graph.IterateRoots <pyTooling.Graph.Graph.IterateRoots>` |br|
749 |rarr| Iterate all roots of a graph.
750 :meth:`Graph.IterateLeafs <pyTooling.Graph.Graph.IterateLeafs>` |br|
751 |rarr| Iterate all leafs of a graph.
752 """
753 return len(self._inboundEdges) == 0
755 @readonly
756 def IsLeaf(self) -> bool:
757 """
758 Read-only property to check if this vertex is a leaf vertex in the graph.
760 A leaf has no outbound edges (no successor vertices).
762 :returns: ``True``, if this vertex is a leaf.
764 .. seealso::
766 :meth:`IsRoot` |br|
767 |rarr| Check if a vertex is a root vertex in the graph.
768 :meth:`Graph.IterateRoots <pyTooling.Graph.Graph.IterateRoots>` |br|
769 |rarr| Iterate all roots of a graph.
770 :meth:`Graph.IterateLeafs <pyTooling.Graph.Graph.IterateLeafs>` |br|
771 |rarr| Iterate all leafs of a graph.
772 """
773 return len(self._outboundEdges) == 0
775 @readonly
776 def Predecessors(self) -> Tuple['Vertex', ...]:
777 """
778 Read-only property to get a tuple of predecessor vertices.
780 :returns: Tuple of predecessor vertices.
781 """
782 return tuple([edge.Source for edge in self._inboundEdges])
784 @readonly
785 def Successors(self) -> Tuple['Vertex', ...]:
786 """
787 Read-only property to get a tuple of successor vertices.
789 :returns: Tuple of successor vertices.
790 """
791 return tuple([edge.Destination for edge in self._outboundEdges])
793 def EdgeToVertex(
794 self,
795 vertex: 'Vertex',
796 edgeID: Nullable[EdgeIDType] = None,
797 edgeWeight: Nullable[EdgeWeightType] = None,
798 edgeValue: Nullable[VertexValueType] = None,
799 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None
800 ) -> 'Edge':
801 """
802 Create an outbound edge from this vertex to the referenced vertex.
804 :param vertex: The vertex to be linked to.
805 :param edgeID: The edge's optional ID for the new edge object.
806 :param edgeWeight: The edge's optional weight for the new edge object.
807 :param edgeValue: The edge's optional value for the new edge object.
808 :param keyValuePairs: An optional mapping (dictionary) of key-value-pairs for the new edge object.
809 :returns: The edge object linking this vertex and the referenced vertex.
811 .. seealso::
813 :meth:`EdgeFromVertex` |br|
814 |rarr| Create an inbound edge from the referenced vertex to this vertex.
815 :meth:`EdgeToNewVertex` |br|
816 |rarr| Create a new vertex and link that vertex by an outbound edge from this vertex.
817 :meth:`EdgeFromNewVertex` |br|
818 |rarr| Create a new vertex and link that vertex by an inbound edge to this vertex.
819 :meth:`LinkToVertex` |br|
820 |rarr| Create an outbound link from this vertex to the referenced vertex.
821 :meth:`LinkFromVertex` |br|
822 |rarr| Create an inbound link from the referenced vertex to this vertex.
824 .. todo:: GRAPH::Vertex::EdgeToVertex Needs possible exceptions to be documented.
825 """
826 if self._subgraph is vertex._subgraph:
827 edge = Edge(self, vertex, edgeID, edgeValue, edgeWeight, keyValuePairs)
829 self._outboundEdges.append(edge)
830 vertex._inboundEdges.append(edge)
832 if self._subgraph is None:
833 # TODO: move into Edge?
834 # TODO: keep _graph pointer in edge and then register edge on graph?
835 if edgeID is None:
836 self._graph._edgesWithoutID.append(edge)
837 elif edgeID not in self._graph._edgesWithID:
838 self._graph._edgesWithID[edgeID] = edge
839 else:
840 raise DuplicateEdgeError(f"Edge ID '{edgeID}' already exists in this graph.")
841 else:
842 # TODO: keep _graph pointer in edge and then register edge on graph?
843 if edgeID is None:
844 self._subgraph._edgesWithoutID.append(edge)
845 elif edgeID not in self._subgraph._edgesWithID:
846 self._subgraph._edgesWithID[edgeID] = edge
847 else:
848 raise DuplicateEdgeError(f"Edge ID '{edgeID}' already exists in this subgraph.")
849 else:
850 # FIXME: needs an error message
851 raise GraphException()
853 return edge
855 def EdgeFromVertex(
856 self,
857 vertex: 'Vertex',
858 edgeID: Nullable[EdgeIDType] = None,
859 edgeWeight: Nullable[EdgeWeightType] = None,
860 edgeValue: Nullable[VertexValueType] = None,
861 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None
862 ) -> 'Edge':
863 """
864 Create an inbound edge from the referenced vertex to this vertex.
866 :param vertex: The vertex to be linked from.
867 :param edgeID: The edge's optional ID for the new edge object.
868 :param edgeWeight: The edge's optional weight for the new edge object.
869 :param edgeValue: The edge's optional value for the new edge object.
870 :param keyValuePairs: An optional mapping (dictionary) of key-value-pairs for the new edge object.
871 :returns: The edge object linking the referenced vertex and this vertex.
873 .. seealso::
875 :meth:`EdgeToVertex` |br|
876 |rarr| Create an outbound edge from this vertex to the referenced vertex.
877 :meth:`EdgeToNewVertex` |br|
878 |rarr| Create a new vertex and link that vertex by an outbound edge from this vertex.
879 :meth:`EdgeFromNewVertex` |br|
880 |rarr| Create a new vertex and link that vertex by an inbound edge to this vertex.
881 :meth:`LinkToVertex` |br|
882 |rarr| Create an outbound link from this vertex to the referenced vertex.
883 :meth:`LinkFromVertex` |br|
884 |rarr| Create an inbound link from the referenced vertex to this vertex.
886 .. todo:: GRAPH::Vertex::EdgeFromVertex Needs possible exceptions to be documented.
887 """
888 if self._subgraph is vertex._subgraph: 888 ↛ 913line 888 didn't jump to line 913 because the condition on line 888 was always true
889 edge = Edge(vertex, self, edgeID, edgeValue, edgeWeight, keyValuePairs)
891 vertex._outboundEdges.append(edge)
892 self._inboundEdges.append(edge)
894 if self._subgraph is None:
895 # TODO: move into Edge?
896 # TODO: keep _graph pointer in edge and then register edge on graph?
897 if edgeID is None:
898 self._graph._edgesWithoutID.append(edge)
899 elif edgeID not in self._graph._edgesWithID:
900 self._graph._edgesWithID[edgeID] = edge
901 else:
902 raise DuplicateEdgeError(f"Edge ID '{edgeID}' already exists in this graph.")
903 else:
904 # TODO: keep _graph pointer in edge and then register edge on graph?
905 if edgeID is None:
906 self._subgraph._edgesWithoutID.append(edge)
907 elif edgeID not in self._graph._edgesWithID:
908 self._subgraph._edgesWithID[edgeID] = edge
909 else:
910 raise DuplicateEdgeError(f"Edge ID '{edgeID}' already exists in this graph.")
911 else:
912 # FIXME: needs an error message
913 raise GraphException()
915 return edge
917 def EdgeToNewVertex(
918 self,
919 vertexID: Nullable[VertexIDType] = None,
920 vertexValue: Nullable[VertexValueType] = None,
921 vertexWeight: Nullable[VertexWeightType] = None,
922 vertexKeyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None,
923 edgeID: Nullable[EdgeIDType] = None,
924 edgeWeight: Nullable[EdgeWeightType] = None,
925 edgeValue: Nullable[VertexValueType] = None,
926 edgeKeyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None
927 ) -> 'Edge':
928 """
929 Create a new vertex and link that vertex by an outbound edge from this vertex.
931 :param vertexID: The new vertex' optional ID.
932 :param vertexValue: The new vertex' optional value.
933 :param vertexWeight: The new vertex' optional weight.
934 :param vertexKeyValuePairs: An optional mapping (dictionary) of key-value-pairs for the new vertex.
935 :param edgeID: The edge's optional ID for the new edge object.
936 :param edgeWeight: The edge's optional weight for the new edge object.
937 :param edgeValue: The edge's optional value for the new edge object.
938 :param edgeKeyValuePairs: An optional mapping (dictionary) of key-value-pairs for the new edge object.
939 :returns: The edge object linking this vertex and the created vertex.
941 .. seealso::
943 :meth:`EdgeToVertex` |br|
944 |rarr| Create an outbound edge from this vertex to the referenced vertex.
945 :meth:`EdgeFromVertex` |br|
946 |rarr| Create an inbound edge from the referenced vertex to this vertex.
947 :meth:`EdgeFromNewVertex` |br|
948 |rarr| Create a new vertex and link that vertex by an inbound edge to this vertex.
949 :meth:`LinkToVertex` |br|
950 |rarr| Create an outbound link from this vertex to the referenced vertex.
951 :meth:`LinkFromVertex` |br|
952 |rarr| Create an inbound link from the referenced vertex to this vertex.
954 .. todo:: GRAPH::Vertex::EdgeToNewVertex Needs possible exceptions to be documented.
955 """
956 vertex = Vertex(vertexID, vertexValue, vertexWeight, vertexKeyValuePairs, graph=self._graph) # , component=self._component)
958 if self._subgraph is vertex._subgraph: 958 ↛ 983line 958 didn't jump to line 983 because the condition on line 958 was always true
959 edge = Edge(self, vertex, edgeID, edgeValue, edgeWeight, edgeKeyValuePairs)
961 self._outboundEdges.append(edge)
962 vertex._inboundEdges.append(edge)
964 if self._subgraph is None: 964 ↛ 975line 964 didn't jump to line 975 because the condition on line 964 was always true
965 # TODO: move into Edge?
966 # TODO: keep _graph pointer in edge and then register edge on graph?
967 if edgeID is None: 967 ↛ 969line 967 didn't jump to line 969 because the condition on line 967 was always true
968 self._graph._edgesWithoutID.append(edge)
969 elif edgeID not in self._graph._edgesWithID:
970 self._graph._edgesWithID[edgeID] = edge
971 else:
972 raise DuplicateEdgeError(f"Edge ID '{edgeID}' already exists in this graph.")
973 else:
974 # TODO: keep _graph pointer in edge and then register edge on graph?
975 if edgeID is None:
976 self._subgraph._edgesWithoutID.append(edge)
977 elif edgeID not in self._graph._edgesWithID:
978 self._subgraph._edgesWithID[edgeID] = edge
979 else:
980 raise DuplicateEdgeError(f"Edge ID '{edgeID}' already exists in this graph.")
981 else:
982 # FIXME: needs an error message
983 raise GraphException()
985 return edge
987 def EdgeFromNewVertex(
988 self,
989 vertexID: Nullable[VertexIDType] = None,
990 vertexValue: Nullable[VertexValueType] = None,
991 vertexWeight: Nullable[VertexWeightType] = None,
992 vertexKeyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None,
993 edgeID: Nullable[EdgeIDType] = None,
994 edgeWeight: Nullable[EdgeWeightType] = None,
995 edgeValue: Nullable[VertexValueType] = None,
996 edgeKeyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None
997 ) -> 'Edge':
998 """
999 Create a new vertex and link that vertex by an inbound edge to this vertex.
1001 :param vertexID: The new vertex' optional ID.
1002 :param vertexValue: The new vertex' optional value.
1003 :param vertexWeight: The new vertex' optional weight.
1004 :param vertexKeyValuePairs: An optional mapping (dictionary) of key-value-pairs for the new vertex.
1005 :param edgeID: The edge's optional ID for the new edge object.
1006 :param edgeWeight: The edge's optional weight for the new edge object.
1007 :param edgeValue: The edge's optional value for the new edge object.
1008 :param edgeKeyValuePairs: An optional mapping (dictionary) of key-value-pairs for the new edge object.
1009 :returns: The edge object linking this vertex and the created vertex.
1011 .. seealso::
1013 :meth:`EdgeToVertex` |br|
1014 |rarr| Create an outbound edge from this vertex to the referenced vertex.
1015 :meth:`EdgeFromVertex` |br|
1016 |rarr| Create an inbound edge from the referenced vertex to this vertex.
1017 :meth:`EdgeToNewVertex` |br|
1018 |rarr| Create a new vertex and link that vertex by an outbound edge from this vertex.
1019 :meth:`LinkToVertex` |br|
1020 |rarr| Create an outbound link from this vertex to the referenced vertex.
1021 :meth:`LinkFromVertex` |br|
1022 |rarr| Create an inbound link from the referenced vertex to this vertex.
1024 .. todo:: GRAPH::Vertex::EdgeFromNewVertex Needs possible exceptions to be documented.
1025 """
1026 vertex = Vertex(vertexID, vertexValue, vertexWeight, vertexKeyValuePairs, graph=self._graph) # , component=self._component)
1028 if self._subgraph is vertex._subgraph: 1028 ↛ 1053line 1028 didn't jump to line 1053 because the condition on line 1028 was always true
1029 edge = Edge(vertex, self, edgeID, edgeValue, edgeWeight, edgeKeyValuePairs)
1031 vertex._outboundEdges.append(edge)
1032 self._inboundEdges.append(edge)
1034 if self._subgraph is None: 1034 ↛ 1045line 1034 didn't jump to line 1045 because the condition on line 1034 was always true
1035 # TODO: move into Edge?
1036 # TODO: keep _graph pointer in edge and then register edge on graph?
1037 if edgeID is None: 1037 ↛ 1039line 1037 didn't jump to line 1039 because the condition on line 1037 was always true
1038 self._graph._edgesWithoutID.append(edge)
1039 elif edgeID not in self._graph._edgesWithID:
1040 self._graph._edgesWithID[edgeID] = edge
1041 else:
1042 raise DuplicateEdgeError(f"Edge ID '{edgeID}' already exists in this graph.")
1043 else:
1044 # TODO: keep _graph pointer in edge and then register edge on graph?
1045 if edgeID is None:
1046 self._subgraph._edgesWithoutID.append(edge)
1047 elif edgeID not in self._graph._edgesWithID:
1048 self._subgraph._edgesWithID[edgeID] = edge
1049 else:
1050 raise DuplicateEdgeError(f"Edge ID '{edgeID}' already exists in this graph.")
1051 else:
1052 # FIXME: needs an error message
1053 raise GraphException()
1055 return edge
1057 def LinkToVertex(
1058 self,
1059 vertex: 'Vertex',
1060 linkID: Nullable[EdgeIDType] = None,
1061 linkWeight: Nullable[EdgeWeightType] = None,
1062 linkValue: Nullable[VertexValueType] = None,
1063 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None,
1064 ) -> 'Link':
1065 """
1066 Create an outbound link from this vertex to the referenced vertex.
1068 :param vertex: The vertex to be linked to.
1069 :param edgeID: The edge's optional ID for the new link object.
1070 :param edgeWeight: The edge's optional weight for the new link object.
1071 :param edgeValue: The edge's optional value for the new link object.
1072 :param keyValuePairs: An optional mapping (dictionary) of key-value-pairs for the new link object.
1073 :returns: The link object linking this vertex and the referenced vertex.
1075 .. seealso::
1077 :meth:`EdgeToVertex` |br|
1078 |rarr| Create an outbound edge from this vertex to the referenced vertex.
1079 :meth:`EdgeFromVertex` |br|
1080 |rarr| Create an inbound edge from the referenced vertex to this vertex.
1081 :meth:`EdgeToNewVertex` |br|
1082 |rarr| Create a new vertex and link that vertex by an outbound edge from this vertex.
1083 :meth:`EdgeFromNewVertex` |br|
1084 |rarr| Create a new vertex and link that vertex by an inbound edge to this vertex.
1085 :meth:`LinkFromVertex` |br|
1086 |rarr| Create an inbound link from the referenced vertex to this vertex.
1088 .. todo:: GRAPH::Vertex::LinkToVertex Needs possible exceptions to be documented.
1089 """
1090 if self._subgraph is vertex._subgraph: 1090 ↛ 1092line 1090 didn't jump to line 1092 because the condition on line 1090 was never true
1091 # FIXME: needs an error message
1092 raise GraphException()
1093 else:
1094 link = Link(self, vertex, linkID, linkValue, linkWeight, keyValuePairs)
1096 self._outboundLinks.append(link)
1097 vertex._inboundLinks.append(link)
1099 if self._subgraph is None:
1100 # TODO: move into Edge?
1101 # TODO: keep _graph pointer in link and then register link on graph?
1102 if linkID is None: 1102 ↛ 1104line 1102 didn't jump to line 1104 because the condition on line 1102 was always true
1103 self._graph._linksWithoutID.append(link)
1104 elif linkID not in self._graph._linksWithID:
1105 self._graph._linksWithID[linkID] = link
1106 else:
1107 raise DuplicateEdgeError(f"Link ID '{linkID}' already exists in this graph.")
1108 else:
1109 # TODO: keep _graph pointer in link and then register link on graph?
1110 if linkID is None: 1110 ↛ 1113line 1110 didn't jump to line 1113 because the condition on line 1110 was always true
1111 self._subgraph._linksWithoutID.append(link)
1112 vertex._subgraph._linksWithoutID.append(link)
1113 elif linkID not in self._graph._linksWithID:
1114 self._subgraph._linksWithID[linkID] = link
1115 vertex._subgraph._linksWithID[linkID] = link
1116 else:
1117 raise DuplicateEdgeError(f"Link ID '{linkID}' already exists in this graph.")
1119 return link
1121 def LinkFromVertex(
1122 self,
1123 vertex: 'Vertex',
1124 linkID: Nullable[EdgeIDType] = None,
1125 linkWeight: Nullable[EdgeWeightType] = None,
1126 linkValue: Nullable[VertexValueType] = None,
1127 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None
1128 ) -> 'Edge':
1129 """
1130 Create an inbound link from the referenced vertex to this vertex.
1132 :param vertex: The vertex to be linked from.
1133 :param edgeID: The edge's optional ID for the new link object.
1134 :param edgeWeight: The edge's optional weight for the new link object.
1135 :param edgeValue: The edge's optional value for the new link object.
1136 :param keyValuePairs: An optional mapping (dictionary) of key-value-pairs for the new link object.
1137 :returns: The link object linking the referenced vertex and this vertex.
1139 .. seealso::
1141 :meth:`EdgeToVertex` |br|
1142 |rarr| Create an outbound edge from this vertex to the referenced vertex.
1143 :meth:`EdgeFromVertex` |br|
1144 |rarr| Create an inbound edge from the referenced vertex to this vertex.
1145 :meth:`EdgeToNewVertex` |br|
1146 |rarr| Create a new vertex and link that vertex by an outbound edge from this vertex.
1147 :meth:`EdgeFromNewVertex` |br|
1148 |rarr| Create a new vertex and link that vertex by an inbound edge to this vertex.
1149 :meth:`LinkToVertex` |br|
1150 |rarr| Create an outbound link from this vertex to the referenced vertex.
1152 .. todo:: GRAPH::Vertex::LinkFromVertex Needs possible exceptions to be documented.
1153 """
1154 if self._subgraph is vertex._subgraph: 1154 ↛ 1156line 1154 didn't jump to line 1156 because the condition on line 1154 was never true
1155 # FIXME: needs an error message
1156 raise GraphException()
1157 else:
1158 link = Link(vertex, self, linkID, linkValue, linkWeight, keyValuePairs)
1160 vertex._outboundLinks.append(link)
1161 self._inboundLinks.append(link)
1163 if self._subgraph is None: 1163 ↛ 1166line 1163 didn't jump to line 1166 because the condition on line 1163 was never true
1164 # TODO: move into Edge?
1165 # TODO: keep _graph pointer in link and then register link on graph?
1166 if linkID is None:
1167 self._graph._linksWithoutID.append(link)
1168 elif linkID not in self._graph._linksWithID:
1169 self._graph._linksWithID[linkID] = link
1170 else:
1171 raise DuplicateEdgeError(f"Link ID '{linkID}' already exists in this graph.")
1172 else:
1173 # TODO: keep _graph pointer in link and then register link on graph?
1174 if linkID is None: 1174 ↛ 1177line 1174 didn't jump to line 1177 because the condition on line 1174 was always true
1175 self._subgraph._linksWithoutID.append(link)
1176 vertex._subgraph._linksWithoutID.append(link)
1177 elif linkID not in self._graph._linksWithID:
1178 self._subgraph._linksWithID[linkID] = link
1179 vertex._subgraph._linksWithID[linkID] = link
1180 else:
1181 raise DuplicateEdgeError(f"Link ID '{linkID}' already exists in this graph.")
1183 return link
1185 def HasEdgeToDestination(self, destination: 'Vertex') -> bool:
1186 """
1187 Check if this vertex is linked to another vertex by any outbound edge.
1189 :param destination: Destination vertex to check.
1190 :returns: ``True``, if the destination vertex is a destination on any outbound edge.
1192 .. seealso::
1194 :meth:`HasEdgeFromSource` |br|
1195 |rarr| Check if this vertex is linked to another vertex by any inbound edge.
1196 :meth:`HasLinkToDestination` |br|
1197 |rarr| Check if this vertex is linked to another vertex by any outbound link.
1198 :meth:`HasLinkFromSource` |br|
1199 |rarr| Check if this vertex is linked to another vertex by any inbound link.
1200 """
1201 for edge in self._outboundEdges:
1202 if destination is edge.Destination: 1202 ↛ 1201line 1202 didn't jump to line 1201 because the condition on line 1202 was always true
1203 return True
1205 return False
1207 def HasEdgeFromSource(self, source: 'Vertex') -> bool:
1208 """
1209 Check if this vertex is linked to another vertex by any inbound edge.
1211 :param source: Source vertex to check.
1212 :returns: ``True``, if the source vertex is a source on any inbound edge.
1214 .. seealso::
1216 :meth:`HasEdgeToDestination` |br|
1217 |rarr| Check if this vertex is linked to another vertex by any outbound edge.
1218 :meth:`HasLinkToDestination` |br|
1219 |rarr| Check if this vertex is linked to another vertex by any outbound link.
1220 :meth:`HasLinkFromSource` |br|
1221 |rarr| Check if this vertex is linked to another vertex by any inbound link.
1222 """
1223 for edge in self._inboundEdges:
1224 if source is edge.Source: 1224 ↛ 1223line 1224 didn't jump to line 1223 because the condition on line 1224 was always true
1225 return True
1227 return False
1229 def HasLinkToDestination(self, destination: 'Vertex') -> bool:
1230 """
1231 Check if this vertex is linked to another vertex by any outbound link.
1233 :param destination: Destination vertex to check.
1234 :returns: ``True``, if the destination vertex is a destination on any outbound link.
1236 .. seealso::
1238 :meth:`HasEdgeToDestination` |br|
1239 |rarr| Check if this vertex is linked to another vertex by any outbound edge.
1240 :meth:`HasEdgeFromSource` |br|
1241 |rarr| Check if this vertex is linked to another vertex by any inbound edge.
1242 :meth:`HasLinkFromSource` |br|
1243 |rarr| Check if this vertex is linked to another vertex by any inbound link.
1244 """
1245 for link in self._outboundLinks:
1246 if destination is link.Destination: 1246 ↛ 1245line 1246 didn't jump to line 1245 because the condition on line 1246 was always true
1247 return True
1249 return False
1251 def HasLinkFromSource(self, source: 'Vertex') -> bool:
1252 """
1253 Check if this vertex is linked to another vertex by any inbound link.
1255 :param source: Source vertex to check.
1256 :returns: ``True``, if the source vertex is a source on any inbound link.
1258 .. seealso::
1260 :meth:`HasEdgeToDestination` |br|
1261 |rarr| Check if this vertex is linked to another vertex by any outbound edge.
1262 :meth:`HasEdgeFromSource` |br|
1263 |rarr| Check if this vertex is linked to another vertex by any inbound edge.
1264 :meth:`HasLinkToDestination` |br|
1265 |rarr| Check if this vertex is linked to another vertex by any outbound link.
1266 """
1267 for link in self._inboundLinks:
1268 if source is link.Source: 1268 ↛ 1267line 1268 didn't jump to line 1267 because the condition on line 1268 was always true
1269 return True
1271 return False
1273 def DeleteEdgeTo(self, destination: 'Vertex'):
1274 for edge in self._outboundEdges: 1274 ↛ 1278line 1274 didn't jump to line 1278 because the loop on line 1274 didn't complete
1275 if edge._destination is destination: 1275 ↛ 1274line 1275 didn't jump to line 1274 because the condition on line 1275 was always true
1276 break
1277 else:
1278 raise GraphException(f"No outbound edge found to '{destination!r}'.")
1280 edge.Delete()
1282 def DeleteEdgeFrom(self, source: 'Vertex'):
1283 for edge in self._inboundEdges:
1284 if edge._source is source:
1285 break
1286 else:
1287 raise GraphException(f"No inbound edge found to '{source!r}'.")
1289 edge.Delete()
1291 def DeleteLinkTo(self, destination: 'Vertex'):
1292 for link in self._outboundLinks:
1293 if link._destination is destination:
1294 break
1295 else:
1296 raise GraphException(f"No outbound link found to '{destination!r}'.")
1298 link.Delete()
1300 def DeleteLinkFrom(self, source: 'Vertex'):
1301 for link in self._inboundLinks:
1302 if link._source is source:
1303 break
1304 else:
1305 raise GraphException(f"No inbound link found to '{source!r}'.")
1307 link.Delete()
1309 def Copy(self, graph: Graph, copyDict: bool = False, linkingKeyToOriginalVertex: Nullable[str] = None, linkingKeyFromOriginalVertex: Nullable[str] = None) -> 'Vertex':
1310 """
1311 Creates a copy of this vertex in another graph.
1313 Optionally, the vertex's attached attributes (key-value-pairs) can be copied and a linkage between both vertices
1314 can be established.
1316 :param graph: The graph, the vertex is created in.
1317 :param copyDict: If ``True``, copy all attached attributes into the new vertex.
1318 :param linkingKeyToOriginalVertex: If not ``None``, add a key-value-pair using this parameter as key from new vertex to the original vertex.
1319 :param linkingKeyFromOriginalVertex: If not ``None``, add a key-value-pair using this parameter as key from original vertex to the new vertex.
1320 :returns: The newly created vertex.
1321 :raises GraphException: If source graph and destination graph are the same.
1322 """
1323 if graph is self._graph:
1324 raise GraphException("Graph to copy this vertex to, is the same graph.")
1326 vertex = Vertex(self._id, self._value, self._weight, graph=graph)
1327 if copyDict:
1328 vertex._dict = self._dict.copy()
1330 if linkingKeyToOriginalVertex is not None:
1331 vertex._dict[linkingKeyToOriginalVertex] = self
1332 if linkingKeyFromOriginalVertex is not None:
1333 self._dict[linkingKeyFromOriginalVertex] = vertex
1335 return vertex
1337 def IterateOutboundEdges(self, predicate: Nullable[Callable[['Edge'], bool]] = None) -> Generator['Edge', None, None]:
1338 """
1339 Iterate all or selected outbound edges of this vertex.
1341 If parameter ``predicate`` is not None, the given filter function is used to skip edges in the generator.
1343 :param predicate: Filter function accepting any edge and returning a boolean.
1344 :returns: A generator to iterate all outbound edges.
1345 """
1346 if predicate is None:
1347 for edge in self._outboundEdges:
1348 yield edge
1349 else:
1350 for edge in self._outboundEdges:
1351 if predicate(edge):
1352 yield edge
1354 def IterateInboundEdges(self, predicate: Nullable[Callable[['Edge'], bool]] = None) -> Generator['Edge', None, None]:
1355 """
1356 Iterate all or selected inbound edges of this vertex.
1358 If parameter ``predicate`` is not None, the given filter function is used to skip edges in the generator.
1360 :param predicate: Filter function accepting any edge and returning a boolean.
1361 :returns: A generator to iterate all inbound edges.
1362 """
1363 if predicate is None:
1364 for edge in self._inboundEdges:
1365 yield edge
1366 else:
1367 for edge in self._inboundEdges:
1368 if predicate(edge):
1369 yield edge
1371 def IterateOutboundLinks(self, predicate: Nullable[Callable[['Link'], bool]] = None) -> Generator['Link', None, None]:
1372 """
1373 Iterate all or selected outbound links of this vertex.
1375 If parameter ``predicate`` is not None, the given filter function is used to skip links in the generator.
1377 :param predicate: Filter function accepting any link and returning a boolean.
1378 :returns: A generator to iterate all outbound links.
1379 """
1380 if predicate is None:
1381 for link in self._outboundLinks:
1382 yield link
1383 else:
1384 for link in self._outboundLinks:
1385 if predicate(link):
1386 yield link
1388 def IterateInboundLinks(self, predicate: Nullable[Callable[['Link'], bool]] = None) -> Generator['Link', None, None]:
1389 """
1390 Iterate all or selected inbound links of this vertex.
1392 If parameter ``predicate`` is not None, the given filter function is used to skip links in the generator.
1394 :param predicate: Filter function accepting any link and returning a boolean.
1395 :returns: A generator to iterate all inbound links.
1396 """
1397 if predicate is None:
1398 for link in self._inboundLinks:
1399 yield link
1400 else:
1401 for link in self._inboundLinks:
1402 if predicate(link):
1403 yield link
1405 def IterateSuccessorVertices(self, predicate: Nullable[Callable[['Edge'], bool]] = None) -> Generator['Vertex', None, None]:
1406 """
1407 Iterate all or selected successor vertices of this vertex.
1409 If parameter ``predicate`` is not None, the given filter function is used to skip successors in the generator.
1411 :param predicate: Filter function accepting any edge and returning a boolean.
1412 :returns: A generator to iterate all successor vertices.
1413 """
1414 if predicate is None:
1415 for edge in self._outboundEdges:
1416 yield edge.Destination
1417 else:
1418 for edge in self._outboundEdges:
1419 if predicate(edge):
1420 yield edge.Destination
1422 def IteratePredecessorVertices(self, predicate: Nullable[Callable[['Edge'], bool]] = None) -> Generator['Vertex', None, None]:
1423 """
1424 Iterate all or selected predecessor vertices of this vertex.
1426 If parameter ``predicate`` is not None, the given filter function is used to skip predecessors in the generator.
1428 :param predicate: Filter function accepting any edge and returning a boolean.
1429 :returns: A generator to iterate all predecessor vertices.
1430 """
1431 if predicate is None:
1432 for edge in self._inboundEdges:
1433 yield edge.Source
1434 else:
1435 for edge in self._inboundEdges:
1436 if predicate(edge):
1437 yield edge.Source
1439 def IterateVerticesBFS(self) -> Generator['Vertex', None, None]:
1440 """
1441 A generator to iterate all reachable vertices starting from this node in breadth-first search (BFS) order.
1443 :returns: A generator to iterate vertices traversed in BFS order.
1445 .. seealso::
1447 :meth:`IterateVerticesDFS` |br|
1448 |rarr| Iterate all reachable vertices **depth-first search** order.
1449 """
1450 visited: Set[Vertex] = set()
1451 queue: Deque[Vertex] = deque()
1453 yield self
1454 visited.add(self)
1455 for edge in self._outboundEdges:
1456 nextVertex = edge.Destination
1457 if nextVertex is not self: 1457 ↛ 1455line 1457 didn't jump to line 1455 because the condition on line 1457 was always true
1458 queue.appendleft(nextVertex)
1459 visited.add(nextVertex)
1461 while queue:
1462 vertex = queue.pop()
1463 yield vertex
1464 for edge in vertex._outboundEdges:
1465 nextVertex = edge.Destination
1466 if nextVertex not in visited:
1467 queue.appendleft(nextVertex)
1468 visited.add(nextVertex)
1470 def IterateVerticesDFS(self) -> Generator['Vertex', None, None]:
1471 """
1472 A generator to iterate all reachable vertices starting from this node in depth-first search (DFS) order.
1474 :returns: A generator to iterate vertices traversed in DFS order.
1476 .. seealso::
1478 :meth:`IterateVerticesBFS` |br|
1479 |rarr| Iterate all reachable vertices **breadth-first search** order.
1481 Wikipedia - https://en.wikipedia.org/wiki/Depth-first_search
1482 """
1483 visited: Set[Vertex] = set()
1484 stack: List[typing_Iterator[Edge]] = list()
1486 yield self
1487 visited.add(self)
1488 stack.append(iter(self._outboundEdges))
1490 while True:
1491 try:
1492 edge = next(stack[-1])
1493 nextVertex = edge._destination
1494 if nextVertex not in visited:
1495 visited.add(nextVertex)
1496 yield nextVertex
1497 if len(nextVertex._outboundEdges) != 0:
1498 stack.append(iter(nextVertex._outboundEdges))
1499 except StopIteration:
1500 stack.pop()
1502 if len(stack) == 0:
1503 return
1505 def IterateAllOutboundPathsAsVertexList(self) -> Generator[Tuple['Vertex', ...], None, None]:
1506 if len(self._outboundEdges) == 0:
1507 yield (self, )
1508 return
1510 visited: Set[Vertex] = set()
1511 vertexStack: List[Vertex] = list()
1512 iteratorStack: List[typing_Iterator[Edge]] = list()
1514 visited.add(self)
1515 vertexStack.append(self)
1516 iteratorStack.append(iter(self._outboundEdges))
1518 while True:
1519 try:
1520 edge = next(iteratorStack[-1])
1521 nextVertex = edge._destination
1522 if nextVertex in visited:
1523 ex = CycleError(f"Loop detected.")
1524 ex.add_note(f"First loop is:")
1525 for i, vertex in enumerate(vertexStack):
1526 ex.add_note(f" {i}: {vertex!r}")
1527 raise ex
1529 vertexStack.append(nextVertex)
1530 if len(nextVertex._outboundEdges) == 0:
1531 yield tuple(vertexStack)
1532 vertexStack.pop()
1533 else:
1534 iteratorStack.append(iter(nextVertex._outboundEdges))
1536 except StopIteration:
1537 vertexStack.pop()
1538 iteratorStack.pop()
1540 if len(vertexStack) == 0:
1541 return
1543 def ShortestPathToByHops(self, destination: 'Vertex') -> Generator['Vertex', None, None]:
1544 """
1545 Compute the shortest path (by hops) between this vertex and the destination vertex.
1547 A generator is return to iterate all vertices along the path including source and destination vertex.
1549 The search algorithm is breadth-first search (BFS) based. The found solution, if any, is not unique but deterministic
1550 as long as the graph was not modified (e.g. ordering of edges on vertices).
1552 :param destination: The destination vertex to reach.
1553 :returns: A generator to iterate all vertices on the path found between this vertex and the destination vertex.
1554 """
1555 # Trivial case if start is destination
1556 if self is destination: 1556 ↛ 1557line 1556 didn't jump to line 1557 because the condition on line 1556 was never true
1557 yield self
1558 return
1560 # Local struct to create multiple linked-lists forming a paths from current node back to the starting point
1561 # (actually a tree). Each node holds a reference to the vertex it represents.
1562 # Hint: slotted classes are faster than '@dataclasses.dataclass'.
1563 class Node(metaclass=ExtendedType, slots=True):
1564 parent: 'Node'
1565 ref: Vertex
1567 def __init__(self, parent: 'Node', ref: Vertex) -> None:
1568 self.parent = parent
1569 self.ref = ref
1571 def __str__(self):
1572 return f"Vertex: {self.ref.ID}"
1574 # Initially add all reachable vertices to a queue if vertices to be processed.
1575 startNode = Node(None, self)
1576 visited: Set[Vertex] = set()
1577 queue: Deque[Node] = deque()
1579 # Add starting vertex and all its children to the processing list.
1580 # If a child is the destination, break immediately else go into 'else' branch and use BFS algorithm.
1581 visited.add(self)
1582 for edge in self._outboundEdges:
1583 nextVertex = edge.Destination
1584 if nextVertex is destination: 1584 ↛ 1586line 1584 didn't jump to line 1586 because the condition on line 1584 was never true
1585 # Child is destination, so construct the last node for path traversal and break from loop.
1586 destinationNode = Node(startNode, nextVertex)
1587 break
1588 if nextVertex is not self: 1588 ↛ 1582line 1588 didn't jump to line 1582 because the condition on line 1588 was always true
1589 # Ignore backward-edges and side-edges.
1590 # Here self-edges, because there is only the starting vertex in the list of visited edges.
1591 visited.add(nextVertex)
1592 queue.appendleft(Node(startNode, nextVertex))
1593 else:
1594 # Process queue until destination is found or no further vertices are reachable.
1595 while queue:
1596 node = queue.pop()
1597 for edge in node.ref._outboundEdges:
1598 nextVertex = edge.Destination
1599 # Next reachable vertex is destination, so construct the last node for path traversal and break from loop.
1600 if nextVertex is destination:
1601 destinationNode = Node(node, nextVertex)
1602 break
1603 # Ignore backward-edges and side-edges.
1604 if nextVertex not in visited:
1605 visited.add(nextVertex)
1606 queue.appendleft(Node(node, nextVertex))
1607 # Next 3 lines realize a double-break if break was called in inner loop, otherwise continue with outer loop.
1608 else:
1609 continue
1610 break
1611 else:
1612 # All reachable vertices have been processed, but destination was not among them.
1613 raise DestinationNotReachable(f"Destination is not reachable.")
1615 # Reverse order of linked list from destinationNode to startNode
1616 currentNode = destinationNode
1617 previousNode = destinationNode.parent
1618 currentNode.parent = None
1619 while previousNode is not None:
1620 node = previousNode.parent
1621 previousNode.parent = currentNode
1622 currentNode = previousNode
1623 previousNode = node
1625 # Scan reversed linked-list and yield referenced vertices
1626 yield startNode.ref
1627 node = startNode.parent
1628 while node is not None:
1629 yield node.ref
1630 node = node.parent
1632 def ShortestPathToByWeight(self, destination: 'Vertex') -> Generator['Vertex', None, None]:
1633 """
1634 Compute the shortest path (by edge weight) between this vertex and the destination vertex.
1636 A generator is return to iterate all vertices along the path including source and destination vertex.
1638 The search algorithm is based on Dijkstra algorithm and using :mod:`heapq`. The found solution, if any, is not
1639 unique but deterministic as long as the graph was not modified (e.g. ordering of edges on vertices).
1641 :param destination: The destination vertex to reach.
1642 :returns: A generator to iterate all vertices on the path found between this vertex and the destination vertex.
1643 """
1644 # Improvements: both-sided Dijkstra (search from start and destination to reduce discovered area.
1646 # Trivial case if start is destination
1647 if self is destination: 1647 ↛ 1648line 1647 didn't jump to line 1648 because the condition on line 1647 was never true
1648 yield self
1649 return
1651 # Local struct to create multiple-linked lists forming a paths from current node back to the starting point
1652 # (actually a tree). Each node holds the overall weight from start to current node and a reference to the vertex it
1653 # represents.
1654 # Hint: slotted classes are faster than '@dataclasses.dataclass'.
1655 class Node(metaclass=ExtendedType, slots=True):
1656 parent: 'Node'
1657 distance: EdgeWeightType
1658 ref: Vertex
1660 def __init__(self, parent: 'Node', distance: EdgeWeightType, ref: Vertex) -> None:
1661 self.parent = parent
1662 self.distance = distance
1663 self.ref = ref
1665 def __lt__(self, other):
1666 return self.distance < other.distance
1668 def __str__(self):
1669 return f"Vertex: {self.ref.ID}"
1671 visited: Set['Vertex'] = set()
1672 startNode = Node(None, 0, self)
1673 priorityQueue = [startNode]
1675 # Add starting vertex and all its children to the processing list.
1676 # If a child is the destination, break immediately else go into 'else' branch and use Dijkstra algorithm.
1677 visited.add(self)
1678 for edge in self._outboundEdges:
1679 nextVertex = edge.Destination
1680 # Child is destination, so construct the last node for path traversal and break from loop.
1681 if nextVertex is destination: 1681 ↛ 1682line 1681 didn't jump to line 1682 because the condition on line 1681 was never true
1682 destinationNode = Node(startNode, edge._weight, nextVertex)
1683 break
1684 # Ignore backward-edges and side-edges.
1685 # Here self-edges, because there is only the starting vertex in the list of visited edges.
1686 if nextVertex is not self: 1686 ↛ 1678line 1686 didn't jump to line 1678 because the condition on line 1686 was always true
1687 visited.add(nextVertex)
1688 heapq.heappush(priorityQueue, Node(startNode, edge._weight, nextVertex))
1689 else:
1690 # Process priority queue until destination is found or no further vertices are reachable.
1691 while priorityQueue: 1691 ↛ 1709line 1691 didn't jump to line 1709 because the condition on line 1691 was always true
1692 node = heapq.heappop(priorityQueue)
1693 for edge in node.ref._outboundEdges:
1694 nextVertex = edge.Destination
1695 # Next reachable vertex is destination, so construct the last node for path traversal and break from loop.
1696 if nextVertex is destination:
1697 destinationNode = Node(node, node.distance + edge._weight, nextVertex)
1698 break
1699 # Ignore backward-edges and side-edges.
1700 if nextVertex not in visited:
1701 visited.add(nextVertex)
1702 heapq.heappush(priorityQueue, Node(node, node.distance + edge._weight, nextVertex))
1703 # Next 3 lines realize a double-break if break was called in inner loop, otherwise continue with outer loop.
1704 else:
1705 continue
1706 break
1707 else:
1708 # All reachable vertices have been processed, but destination was not among them.
1709 raise DestinationNotReachable(f"Destination is not reachable.")
1711 # Reverse order of linked-list from destinationNode to startNode
1712 currentNode = destinationNode
1713 previousNode = destinationNode.parent
1714 currentNode.parent = None
1715 while previousNode is not None:
1716 node = previousNode.parent
1717 previousNode.parent = currentNode
1718 currentNode = previousNode
1719 previousNode = node
1721 # Scan reversed linked-list and yield referenced vertices
1722 yield startNode.ref, startNode.distance
1723 node = startNode.parent
1724 while node is not None:
1725 yield node.ref, node.distance
1726 node = node.parent
1728 # Other possible algorithms:
1729 # * Bellman-Ford
1730 # * Floyd-Warshall
1732 # def PathExistsTo(self, destination: 'Vertex'):
1733 # raise NotImplementedError()
1734 # # DFS
1735 # # Union find
1736 #
1737 # def MaximumFlowTo(self, destination: 'Vertex'):
1738 # raise NotImplementedError()
1739 # # Ford-Fulkerson algorithm
1740 # # Edmons-Karp algorithm
1741 # # Dinic's algorithm
1743 def ConvertToTree(self) -> Node:
1744 """
1745 Converts all reachable vertices from this starting vertex to a tree of :class:`~pyTooling.Tree.Node` instances.
1747 The tree is traversed using depths-first-search.
1749 :returns:
1750 """
1751 visited: Set[Vertex] = set()
1752 stack: List[Tuple[Node, typing_Iterator[Edge]]] = list()
1754 root = Node(nodeID=self._id, value=self._value)
1755 root._dict = self._dict.copy()
1757 visited.add(self)
1758 stack.append((root, iter(self._outboundEdges)))
1760 while True:
1761 try:
1762 edge = next(stack[-1][1])
1763 nextVertex = edge._destination
1764 if nextVertex not in visited: 1764 ↛ 1770line 1764 didn't jump to line 1770 because the condition on line 1764 was always true
1765 node = Node(nextVertex._id, nextVertex._value, parent=stack[-1][0])
1766 visited.add(nextVertex)
1767 if len(nextVertex._outboundEdges) != 0:
1768 stack.append((node, iter(nextVertex._outboundEdges)))
1769 else:
1770 raise NotATreeError(f"The directed subgraph is not a tree.")
1771 # TODO: compute cycle:
1772 # a) branch 1 is described in stack
1773 # b) branch 2 can be found by walking from joint to root in the tree
1774 except StopIteration:
1775 stack.pop()
1777 if len(stack) == 0:
1778 return root
1780 def __repr__(self) -> str:
1781 """
1782 Returns a detailed string representation of the vertex.
1784 :returns: The detailed string representation of the vertex.
1785 """
1786 vertexID = value = ""
1787 sep = ": "
1788 if self._id is not None:
1789 vertexID = f"{sep}vertexID='{self._id}'"
1790 sep = "; "
1791 if self._value is not None: 1791 ↛ 1792line 1791 didn't jump to line 1792 because the condition on line 1791 was never true
1792 value = f"{sep}value='{self._value}'"
1794 return f"<vertex{vertexID}{value}>"
1796 def __str__(self) -> str:
1797 """
1798 Return a string representation of the vertex.
1800 Order of resolution:
1802 1. If :attr:`_value` is not None, return the string representation of :attr:`_value`.
1803 2. If :attr:`_id` is not None, return the string representation of :attr:`_id`.
1804 3. Else, return :meth:`__repr__`.
1806 :returns: The resolved string representation of the vertex.
1807 """
1808 if self._value is not None: 1808 ↛ 1809line 1808 didn't jump to line 1809 because the condition on line 1808 was never true
1809 return str(self._value)
1810 elif self._id is not None: 1810 ↛ 1811line 1810 didn't jump to line 1811 because the condition on line 1810 was never true
1811 return str(self._id)
1812 else:
1813 return self.__repr__()
1816@export
1817class BaseEdge(
1818 BaseWithIDValueAndWeight[EdgeIDType, EdgeValueType, EdgeWeightType, EdgeDictKeyType, EdgeDictValueType],
1819 Generic[EdgeIDType, EdgeValueType, EdgeWeightType, EdgeDictKeyType, EdgeDictValueType]
1820):
1821 """
1822 An **edge** can have a unique ID, a value, a weight and attached meta information as key-value-pairs. All edges are
1823 directed.
1824 """
1825 _source: Vertex
1826 _destination: Vertex
1828 def __init__(
1829 self,
1830 source: Vertex,
1831 destination: Vertex,
1832 edgeID: Nullable[EdgeIDType] = None,
1833 value: Nullable[EdgeValueType] = None,
1834 weight: Nullable[EdgeWeightType] = None,
1835 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None
1836 ) -> None:
1837 """
1838 .. todo:: GRAPH::BaseEdge::init Needs documentation.
1840 :param source: The source of the new edge.
1841 :param destination: The destination of the new edge.
1842 :param edgeID: The optional unique ID for the new edge.
1843 :param value: The optional value for the new edge.
1844 :param weight: The optional weight for the new edge.
1845 :param keyValuePairs: The optional mapping (dictionary) of key-value-pairs.
1846 """
1847 super().__init__(edgeID, value, weight, keyValuePairs)
1849 self._source = source
1850 self._destination = destination
1852 component = source._component
1853 if component is not destination._component:
1854 # TODO: should it be divided into with/without ID?
1855 oldComponent = destination._component
1856 for vertex in oldComponent._vertices:
1857 vertex._component = component
1858 component._vertices.add(vertex)
1859 component._graph._components.remove(oldComponent)
1860 del oldComponent
1862 @readonly
1863 def Source(self) -> Vertex:
1864 """
1865 Read-only property to get the source (:attr:`_source`) of an edge.
1867 :returns: The source of an edge.
1868 """
1869 return self._source
1871 @readonly
1872 def Destination(self) -> Vertex:
1873 """
1874 Read-only property to get the destination (:attr:`_destination`) of an edge.
1876 :returns: The destination of an edge.
1877 """
1878 return self._destination
1880 def Reverse(self) -> None:
1881 """Reverse the direction of this edge."""
1882 swap = self._source
1883 self._source = self._destination
1884 self._destination = swap
1887@export
1888class Edge(
1889 BaseEdge[EdgeIDType, EdgeValueType, EdgeWeightType, EdgeDictKeyType, EdgeDictValueType],
1890 Generic[EdgeIDType, EdgeValueType, EdgeWeightType, EdgeDictKeyType, EdgeDictValueType]
1891):
1892 """
1893 An **edge** can have a unique ID, a value, a weight and attached meta information as key-value-pairs. All edges are
1894 directed.
1895 """
1897 def __init__(
1898 self,
1899 source: Vertex,
1900 destination: Vertex,
1901 edgeID: Nullable[EdgeIDType] = None,
1902 value: Nullable[EdgeValueType] = None,
1903 weight: Nullable[EdgeWeightType] = None,
1904 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None
1905 ) -> None:
1906 """
1907 .. todo:: GRAPH::Edge::init Needs documentation.
1909 :param source: The source of the new edge.
1910 :param destination: The destination of the new edge.
1911 :param edgeID: The optional unique ID for the new edge.
1912 :param value: The optional value for the new edge.
1913 :param weight: The optional weight for the new edge.
1914 :param keyValuePairs: The optional mapping (dictionary) of key-value-pairs.
1915 """
1916 if not isinstance(source, Vertex):
1917 ex = TypeError("Parameter 'source' is not of type 'Vertex'.")
1918 ex.add_note(f"Got type '{getFullyQualifiedName(source)}'.")
1919 raise ex
1920 if not isinstance(destination, Vertex):
1921 ex = TypeError("Parameter 'destination' is not of type 'Vertex'.")
1922 ex.add_note(f"Got type '{getFullyQualifiedName(destination)}'.")
1923 raise ex
1924 if edgeID is not None and not isinstance(edgeID, Hashable):
1925 ex = TypeError("Parameter 'edgeID' is not of type 'EdgeIDType'.")
1926 ex.add_note(f"Got type '{getFullyQualifiedName(edgeID)}'.")
1927 raise ex
1928 # if value is not None and not isinstance(value, Vertex):
1929 # raise TypeError("Parameter 'value' is not of type 'EdgeValueType'.")
1930 if weight is not None and not isinstance(weight, (int, float)):
1931 ex = TypeError("Parameter 'weight' is not of type 'EdgeWeightType'.")
1932 ex.add_note(f"Got type '{getFullyQualifiedName(weight)}'.")
1933 raise ex
1934 if source._graph is not destination._graph:
1935 raise NotInSameGraph(f"Source vertex and destination vertex are not in same graph.")
1937 super().__init__(source, destination, edgeID, value, weight, keyValuePairs)
1939 def Delete(self) -> None:
1940 # Remove from Source and Destination
1941 self._source._outboundEdges.remove(self)
1942 self._destination._inboundEdges.remove(self)
1944 # Remove from Graph and Subgraph
1945 if self._id is None: 1945 ↛ 1950line 1945 didn't jump to line 1950 because the condition on line 1945 was always true
1946 self._source._graph._edgesWithoutID.remove(self)
1947 if self._source._subgraph is not None: 1947 ↛ 1948line 1947 didn't jump to line 1948 because the condition on line 1947 was never true
1948 self._source._subgraph._edgesWithoutID.remove(self)
1949 else:
1950 del self._source._graph._edgesWithID[self._id]
1951 if self._source._subgraph is not None:
1952 del self._source._subgraph._edgesWithID[self]
1954 self._Delete()
1956 def _Delete(self) -> None:
1957 super().Delete()
1959 def Reverse(self) -> None:
1960 """Reverse the direction of this edge."""
1961 self._source._outboundEdges.remove(self)
1962 self._source._inboundEdges.append(self)
1963 self._destination._inboundEdges.remove(self)
1964 self._destination._outboundEdges.append(self)
1966 super().Reverse()
1969@export
1970class Link(
1971 BaseEdge[LinkIDType, LinkValueType, LinkWeightType, LinkDictKeyType, LinkDictValueType],
1972 Generic[LinkIDType, LinkValueType, LinkWeightType, LinkDictKeyType, LinkDictValueType]
1973):
1974 """
1975 A **link** can have a unique ID, a value, a weight and attached meta information as key-value-pairs. All links are
1976 directed.
1977 """
1979 def __init__(
1980 self,
1981 source: Vertex,
1982 destination: Vertex,
1983 linkID: LinkIDType = None,
1984 value: LinkValueType = None,
1985 weight: Nullable[LinkWeightType] = None,
1986 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None
1987 ) -> None:
1988 """
1989 .. todo:: GRAPH::Edge::init Needs documentation.
1991 :param source: The source of the new link.
1992 :param destination: The destination of the new link.
1993 :param linkID: The optional unique ID for the new link.
1994 :param value: The optional value for the new v.
1995 :param weight: The optional weight for the new link.
1996 :param keyValuePairs: The optional mapping (dictionary) of key-value-pairs.
1997 """
1998 if not isinstance(source, Vertex):
1999 ex = TypeError("Parameter 'source' is not of type 'Vertex'.")
2000 ex.add_note(f"Got type '{getFullyQualifiedName(source)}'.")
2001 raise ex
2002 if not isinstance(destination, Vertex):
2003 ex = TypeError("Parameter 'destination' is not of type 'Vertex'.")
2004 ex.add_note(f"Got type '{getFullyQualifiedName(destination)}'.")
2005 raise ex
2006 if linkID is not None and not isinstance(linkID, Hashable):
2007 ex = TypeError("Parameter 'linkID' is not of type 'LinkIDType'.")
2008 ex.add_note(f"Got type '{getFullyQualifiedName(linkID)}'.")
2009 raise ex
2010 # if value is not None and not isinstance(value, Vertex):
2011 # raise TypeError("Parameter 'value' is not of type 'EdgeValueType'.")
2012 if weight is not None and not isinstance(weight, (int, float)):
2013 ex = TypeError("Parameter 'weight' is not of type 'EdgeWeightType'.")
2014 ex.add_note(f"Got type '{getFullyQualifiedName(weight)}'.")
2015 raise ex
2016 if source._graph is not destination._graph:
2017 raise NotInSameGraph(f"Source vertex and destination vertex are not in same graph.")
2019 super().__init__(source, destination, linkID, value, weight, keyValuePairs)
2021 def Delete(self) -> None:
2022 self._source._outboundEdges.remove(self)
2023 self._destination._inboundEdges.remove(self)
2025 if self._id is None:
2026 self._source._graph._linksWithoutID.remove(self)
2027 else:
2028 del self._source._graph._linksWithID[self._id]
2030 self._Delete()
2031 assert getrefcount(self) == 1
2033 def _Delete(self) -> None:
2034 super().Delete()
2036 def Reverse(self) -> None:
2037 """Reverse the direction of this link."""
2038 self._source._outboundEdges.remove(self)
2039 self._source._inboundEdges.append(self)
2040 self._destination._inboundEdges.remove(self)
2041 self._destination._outboundEdges.append(self)
2043 super().Reverse()
2046@export
2047class BaseGraph(
2048 BaseWithName[GraphDictKeyType, GraphDictValueType],
2049 Generic[
2050 GraphDictKeyType, GraphDictValueType,
2051 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,
2052 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,
2053 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType
2054 ]
2055):
2056 """
2057 .. todo:: GRAPH::BaseGraph Needs documentation.
2059 """
2061 _verticesWithID: Dict[VertexIDType, Vertex[GraphDictKeyType, GraphDictValueType, VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType, EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType, LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType]]
2062 _verticesWithoutID: List[Vertex[GraphDictKeyType, GraphDictValueType, VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType, EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType, LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType]]
2063 _edgesWithID: Dict[EdgeIDType, Edge[EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType]]
2064 _edgesWithoutID: List[Edge[EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType]]
2065 _linksWithID: Dict[EdgeIDType, Link[LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType]]
2066 _linksWithoutID: List[Link[LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType]]
2068 def __init__(
2069 self,
2070 name: Nullable[str] = None,
2071 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None
2072 #, vertices: Nullable[Iterable[Vertex]] = None) -> None:
2073 ):
2074 """
2075 .. todo:: GRAPH::BaseGraph::init Needs documentation.
2077 :param name: The optional name of the graph.
2078 :param keyValuePairs: The optional mapping (dictionary) of key-value-pairs.
2079 """
2080 super().__init__(name, keyValuePairs)
2082 self._verticesWithoutID = []
2083 self._verticesWithID = {}
2084 self._edgesWithoutID = []
2085 self._edgesWithID = {}
2086 self._linksWithoutID = []
2087 self._linksWithID = {}
2089 def __del__(self):
2090 """
2091 .. todo:: GRAPH::BaseGraph::del Needs documentation.
2093 """
2094 try:
2095 del self._verticesWithoutID
2096 del self._verticesWithID
2097 del self._edgesWithoutID
2098 del self._edgesWithID
2099 del self._linksWithoutID
2100 del self._linksWithID
2101 except AttributeError:
2102 pass
2104 super().__del__()
2106 @readonly
2107 def VertexCount(self) -> int:
2108 """Read-only property to access the number of vertices in this graph.
2110 :returns: The number of vertices in this graph."""
2111 return len(self._verticesWithoutID) + len(self._verticesWithID)
2113 @readonly
2114 def EdgeCount(self) -> int:
2115 """Read-only property to access the number of edges in this graph.
2117 :returns: The number of edges in this graph."""
2118 return len(self._edgesWithoutID) + len(self._edgesWithID)
2120 @readonly
2121 def LinkCount(self) -> int:
2122 """Read-only property to access the number of links in this graph.
2124 :returns: The number of links in this graph."""
2125 return len(self._linksWithoutID) + len(self._linksWithID)
2127 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]:
2128 """
2129 Iterate all or selected vertices of a graph.
2131 If parameter ``predicate`` is not None, the given filter function is used to skip vertices in the generator.
2133 :param predicate: Filter function accepting any vertex and returning a boolean.
2134 :returns: A generator to iterate all vertices.
2135 """
2136 if predicate is None:
2137 yield from self._verticesWithoutID
2138 yield from self._verticesWithID.values()
2140 else:
2141 for vertex in self._verticesWithoutID:
2142 if predicate(vertex):
2143 yield vertex
2145 for vertex in self._verticesWithID.values():
2146 if predicate(vertex):
2147 yield vertex
2149 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]:
2150 """
2151 Iterate all or selected roots (vertices without inbound edges / without predecessors) of a graph.
2153 If parameter ``predicate`` is not None, the given filter function is used to skip vertices in the generator.
2155 :param predicate: Filter function accepting any vertex and returning a boolean.
2156 :returns: A generator to iterate all vertices without inbound edges.
2158 .. seealso::
2160 :meth:`IterateLeafs` |br|
2161 |rarr| Iterate leafs of a graph.
2162 :meth:`Vertex.IsRoot <pyTooling.Graph.Vertex.IsRoot>` |br|
2163 |rarr| Check if a vertex is a root vertex in the graph.
2164 :meth:`Vertex.IsLeaf <pyTooling.Graph.Vertex.IsLeaf>` |br|
2165 |rarr| Check if a vertex is a leaf vertex in the graph.
2166 """
2167 if predicate is None:
2168 for vertex in self._verticesWithoutID:
2169 if len(vertex._inboundEdges) == 0:
2170 yield vertex
2172 for vertex in self._verticesWithID.values(): 2172 ↛ 2173line 2172 didn't jump to line 2173 because the loop on line 2172 never started
2173 if len(vertex._inboundEdges) == 0:
2174 yield vertex
2175 else:
2176 for vertex in self._verticesWithoutID:
2177 if len(vertex._inboundEdges) == 0 and predicate(vertex):
2178 yield vertex
2180 for vertex in self._verticesWithID.values(): 2180 ↛ 2181line 2180 didn't jump to line 2181 because the loop on line 2180 never started
2181 if len(vertex._inboundEdges) == 0 and predicate(vertex):
2182 yield vertex
2184 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]:
2185 """
2186 Iterate all or selected leafs (vertices without outbound edges / without successors) of a graph.
2188 If parameter ``predicate`` is not None, the given filter function is used to skip vertices in the generator.
2190 :param predicate: Filter function accepting any vertex and returning a boolean.
2191 :returns: A generator to iterate all vertices without outbound edges.
2193 .. seealso::
2195 :meth:`IterateRoots` |br|
2196 |rarr| Iterate roots of a graph.
2197 :meth:`Vertex.IsRoot <pyTooling.Graph.Vertex.IsRoot>` |br|
2198 |rarr| Check if a vertex is a root vertex in the graph.
2199 :meth:`Vertex.IsLeaf <pyTooling.Graph.Vertex.IsLeaf>` |br|
2200 |rarr| Check if a vertex is a leaf vertex in the graph.
2201 """
2202 if predicate is None:
2203 for vertex in self._verticesWithoutID:
2204 if len(vertex._outboundEdges) == 0:
2205 yield vertex
2207 for vertex in self._verticesWithID.values():
2208 if len(vertex._outboundEdges) == 0:
2209 yield vertex
2210 else:
2211 for vertex in self._verticesWithoutID:
2212 if len(vertex._outboundEdges) == 0 and predicate(vertex):
2213 yield vertex
2215 for vertex in self._verticesWithID.values():
2216 if len(vertex._outboundEdges) == 0 and predicate(vertex): 2216 ↛ 2217line 2216 didn't jump to line 2217 because the condition on line 2216 was never true
2217 yield vertex
2219 # 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]:
2220 # raise NotImplementedError()
2221 #
2222 # 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]:
2223 # raise NotImplementedError()
2225 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]:
2226 """
2227 Iterate all or selected vertices in topological order.
2229 If parameter ``predicate`` is not None, the given filter function is used to skip vertices in the generator.
2231 :param predicate: Filter function accepting any vertex and returning a boolean.
2232 :returns: A generator to iterate all vertices in topological order.
2233 :except CycleError: Raised if graph is cyclic, thus topological sorting isn't possible.
2234 """
2235 outboundEdgeCounts = {}
2236 leafVertices = []
2238 for vertex in self._verticesWithoutID:
2239 if (count := len(vertex._outboundEdges)) == 0:
2240 leafVertices.append(vertex)
2241 else:
2242 outboundEdgeCounts[vertex] = count
2244 for vertex in self._verticesWithID.values():
2245 if (count := len(vertex._outboundEdges)) == 0:
2246 leafVertices.append(vertex)
2247 else:
2248 outboundEdgeCounts[vertex] = count
2250 if not leafVertices: 2250 ↛ 2251line 2250 didn't jump to line 2251 because the condition on line 2250 was never true
2251 raise CycleError(f"Graph has no leafs. Thus, no topological sorting exists.")
2253 overallCount = len(outboundEdgeCounts) + len(leafVertices)
2255 def removeVertex(vertex: Vertex):
2256 nonlocal overallCount
2257 overallCount -= 1
2258 for inboundEdge in vertex._inboundEdges:
2259 sourceVertex = inboundEdge.Source
2260 count = outboundEdgeCounts[sourceVertex] - 1
2261 outboundEdgeCounts[sourceVertex] = count
2262 if count == 0:
2263 leafVertices.append(sourceVertex)
2265 if predicate is None:
2266 for vertex in leafVertices:
2267 yield vertex
2269 removeVertex(vertex)
2270 else:
2271 for vertex in leafVertices:
2272 if predicate(vertex):
2273 yield vertex
2275 removeVertex(vertex)
2277 if overallCount == 0: 2277 ↛ 2279line 2277 didn't jump to line 2279 because the condition on line 2277 was always true
2278 return
2279 elif overallCount > 0:
2280 raise CycleError(f"Graph has remaining vertices. Thus, the graph has at least one cycle.")
2282 raise InternalError(f"Graph data structure is corrupted.") # pragma: no cover
2284 def IterateEdges(self, predicate: Nullable[Callable[[Edge], bool]] = None) -> Generator[Edge[EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType], None, None]:
2285 """
2286 Iterate all or selected edges of a graph.
2288 If parameter ``predicate`` is not None, the given filter function is used to skip edges in the generator.
2290 :param predicate: Filter function accepting any edge and returning a boolean.
2291 :returns: A generator to iterate all edges.
2292 """
2293 if predicate is None:
2294 yield from self._edgesWithoutID
2295 yield from self._edgesWithID.values()
2297 else:
2298 for edge in self._edgesWithoutID:
2299 if predicate(edge):
2300 yield edge
2302 for edge in self._edgesWithID.values():
2303 if predicate(edge):
2304 yield edge
2306 def IterateLinks(self, predicate: Nullable[Callable[[Link], bool]] = None) -> Generator[Link[LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType], None, None]:
2307 """
2308 Iterate all or selected links of a graph.
2310 If parameter ``predicate`` is not None, the given filter function is used to skip links in the generator.
2312 :param predicate: Filter function accepting any link and returning a boolean.
2313 :returns: A generator to iterate all links.
2314 """
2315 if predicate is None: 2315 ↛ 2320line 2315 didn't jump to line 2320 because the condition on line 2315 was always true
2316 yield from self._linksWithoutID
2317 yield from self._linksWithID.values()
2319 else:
2320 for link in self._linksWithoutID:
2321 if predicate(link):
2322 yield link
2324 for link in self._linksWithID.values():
2325 if predicate(link):
2326 yield link
2328 def ReverseEdges(self, predicate: Nullable[Callable[[Edge], bool]] = None) -> None:
2329 """
2330 Reverse all or selected edges of a graph.
2332 If parameter ``predicate`` is not None, the given filter function is used to skip edges.
2334 :param predicate: Filter function accepting any edge and returning a boolean.
2335 """
2336 if predicate is None:
2337 for edge in self._edgesWithoutID:
2338 swap = edge._source
2339 edge._source = edge._destination
2340 edge._destination = swap
2342 for edge in self._edgesWithID.values():
2343 swap = edge._source
2344 edge._source = edge._destination
2345 edge._destination = swap
2347 for vertex in self._verticesWithoutID:
2348 swap = vertex._inboundEdges
2349 vertex._inboundEdges = vertex._outboundEdges
2350 vertex._outboundEdges = swap
2352 for vertex in self._verticesWithID.values():
2353 swap = vertex._inboundEdges
2354 vertex._inboundEdges = vertex._outboundEdges
2355 vertex._outboundEdges = swap
2356 else:
2357 for edge in self._edgesWithoutID:
2358 if predicate(edge):
2359 edge.Reverse()
2361 for edge in self._edgesWithID.values():
2362 if predicate(edge):
2363 edge.Reverse()
2365 def ReverseLinks(self, predicate: Nullable[Callable[[Link], bool]] = None) -> None:
2366 """
2367 Reverse all or selected links of a graph.
2369 If parameter ``predicate`` is not None, the given filter function is used to skip links.
2371 :param predicate: Filter function accepting any link and returning a boolean.
2372 """
2373 if predicate is None:
2374 for link in self._linksWithoutID:
2375 swap = link._source
2376 link._source = link._destination
2377 link._destination = swap
2379 for link in self._linksWithID.values():
2380 swap = link._source
2381 link._source = link._destination
2382 link._destination = swap
2384 for vertex in self._verticesWithoutID:
2385 swap = vertex._inboundLinks
2386 vertex._inboundLinks = vertex._outboundLinks
2387 vertex._outboundLinks = swap
2389 for vertex in self._verticesWithID.values():
2390 swap = vertex._inboundLinks
2391 vertex._inboundLinks = vertex._outboundLinks
2392 vertex._outboundLinks = swap
2393 else:
2394 for link in self._linksWithoutID:
2395 if predicate(link):
2396 link.Reverse()
2398 for link in self._linksWithID.values():
2399 if predicate(link):
2400 link.Reverse()
2402 def RemoveEdges(self, predicate: Nullable[Callable[[Edge], bool]] = None):
2403 """
2404 Remove all or selected edges of a graph.
2406 If parameter ``predicate`` is not None, the given filter function is used to skip edges.
2408 :param predicate: Filter function accepting any edge and returning a boolean.
2409 """
2410 if predicate is None:
2411 for edge in self._edgesWithoutID:
2412 edge._Delete()
2414 for edge in self._edgesWithID.values():
2415 edge._Delete()
2417 self._edgesWithoutID = []
2418 self._edgesWithID = {}
2420 for vertex in self._verticesWithoutID:
2421 vertex._inboundEdges = []
2422 vertex._outboundEdges = []
2424 for vertex in self._verticesWithID.values():
2425 vertex._inboundEdges = []
2426 vertex._outboundEdges = []
2428 else:
2429 delEdges = [edge for edge in self._edgesWithID.values() if predicate(edge)]
2430 for edge in delEdges:
2431 del self._edgesWithID[edge._id]
2433 edge._source._outboundEdges.remove(edge)
2434 edge._destination._inboundEdges.remove(edge)
2435 edge._Delete()
2437 for edge in self._edgesWithoutID:
2438 if predicate(edge):
2439 self._edgesWithoutID.remove(edge)
2441 edge._source._outboundEdges.remove(edge)
2442 edge._destination._inboundEdges.remove(edge)
2443 edge._Delete()
2445 def RemoveLinks(self, predicate: Nullable[Callable[[Link], bool]] = None):
2446 """
2447 Remove all or selected links of a graph.
2449 If parameter ``predicate`` is not None, the given filter function is used to skip links.
2451 :param predicate: Filter function accepting any link and returning a boolean.
2452 """
2453 if predicate is None:
2454 for link in self._linksWithoutID:
2455 link._Delete()
2457 for link in self._linksWithID.values():
2458 link._Delete()
2460 self._linksWithoutID = []
2461 self._linksWithID = {}
2463 for vertex in self._verticesWithoutID:
2464 vertex._inboundLinks = []
2465 vertex._outboundLinks = []
2467 for vertex in self._verticesWithID.values():
2468 vertex._inboundLinks = []
2469 vertex._outboundLinks = []
2471 else:
2472 delLinks = [link for link in self._linksWithID.values() if predicate(link)]
2473 for link in delLinks:
2474 del self._linksWithID[link._id]
2476 link._source._outboundLinks.remove(link)
2477 link._destination._inboundLinks.remove(link)
2478 link._Delete()
2480 for link in self._linksWithoutID:
2481 if predicate(link):
2482 self._linksWithoutID.remove(link)
2484 link._source._outboundLinks.remove(link)
2485 link._destination._inboundLinks.remove(link)
2486 link._Delete()
2488 def HasCycle(self) -> bool:
2489 """
2490 .. todo:: GRAPH::BaseGraph::HasCycle Needs documentation.
2492 """
2493 # IsAcyclic ?
2495 # Handle trivial case if graph is empty
2496 if len(self._verticesWithID) + len(self._verticesWithoutID) == 0: 2496 ↛ 2497line 2496 didn't jump to line 2497 because the condition on line 2496 was never true
2497 return False
2499 outboundEdgeCounts = {}
2500 leafVertices = []
2502 for vertex in self._verticesWithoutID:
2503 if (count := len(vertex._outboundEdges)) == 0:
2504 leafVertices.append(vertex)
2505 else:
2506 outboundEdgeCounts[vertex] = count
2508 for vertex in self._verticesWithID.values():
2509 if (count := len(vertex._outboundEdges)) == 0:
2510 leafVertices.append(vertex)
2511 else:
2512 outboundEdgeCounts[vertex] = count
2514 # If there are no leafs, then each vertex has at least one inbound and one outbound edges. Thus, there is a cycle.
2515 if not leafVertices: 2515 ↛ 2516line 2515 didn't jump to line 2516 because the condition on line 2515 was never true
2516 return True
2518 overallCount = len(outboundEdgeCounts) + len(leafVertices)
2520 for vertex in leafVertices:
2521 overallCount -= 1
2522 for inboundEdge in vertex._inboundEdges:
2523 sourceVertex = inboundEdge.Source
2524 count = outboundEdgeCounts[sourceVertex] - 1
2525 outboundEdgeCounts[sourceVertex] = count
2526 if count == 0:
2527 leafVertices.append(sourceVertex)
2529 # If all vertices were processed, no cycle exists.
2530 if overallCount == 0:
2531 return False
2532 # If there are remaining vertices, then a cycle exists.
2533 elif overallCount > 0:
2534 return True
2536 raise InternalError(f"Graph data structure is corrupted.") # pragma: no cover
2539@export
2540class Subgraph(
2541 BaseGraph[
2542 SubgraphDictKeyType, SubgraphDictValueType,
2543 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,
2544 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,
2545 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType
2546 ],
2547 Generic[
2548 SubgraphDictKeyType, SubgraphDictValueType,
2549 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,
2550 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,
2551 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType
2552 ]
2553):
2554 """
2555 .. todo:: GRAPH::Subgraph Needs documentation.
2557 """
2559 _graph: 'Graph'
2561 def __init__(
2562 self,
2563 graph: 'Graph',
2564 name: Nullable[str] = None,
2565 # vertices: Nullable[Iterable[Vertex]] = None,
2566 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None
2567 ) -> None:
2568 """
2569 .. todo:: GRAPH::Subgraph::init Needs documentation.
2571 :param graph: The reference to the graph.
2572 :param name: The optional name of the new sub-graph.
2573 :param keyValuePairs: The optional mapping (dictionary) of key-value-pairs.
2574 """
2575 if graph is None: 2575 ↛ 2576line 2575 didn't jump to line 2576 because the condition on line 2575 was never true
2576 raise ValueError("Parameter 'graph' is None.")
2577 if not isinstance(graph, Graph): 2577 ↛ 2578line 2577 didn't jump to line 2578 because the condition on line 2577 was never true
2578 ex = TypeError("Parameter 'graph' is not of type 'Graph'.")
2579 ex.add_note(f"Got type '{getFullyQualifiedName(graph)}'.")
2580 raise ex
2582 super().__init__(name, keyValuePairs)
2584 graph._subgraphs.add(self)
2586 self._graph = graph
2588 def __del__(self):
2589 """
2590 .. todo:: GRAPH::Subgraph::del Needs documentation.
2592 """
2593 super().__del__()
2595 @readonly
2596 def Graph(self) -> 'Graph':
2597 """
2598 Read-only property to access the graph, this subgraph is associated to (:attr:`_graph`).
2600 :returns: The graph this subgraph is associated to.
2601 """
2602 return self._graph
2604 def __str__(self) -> str:
2605 """
2606 .. todo:: GRAPH::Subgraph::str Needs documentation.
2608 """
2609 return self._name if self._name is not None else "Unnamed subgraph"
2612@export
2613class View(
2614 BaseWithVertices[
2615 ViewDictKeyType, ViewDictValueType,
2616 GraphDictKeyType, GraphDictValueType,
2617 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,
2618 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,
2619 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType
2620 ],
2621 Generic[
2622 ViewDictKeyType, ViewDictValueType,
2623 GraphDictKeyType, GraphDictValueType,
2624 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,
2625 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,
2626 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType
2627 ]
2628):
2629 """
2630 .. todo:: GRAPH::View Needs documentation.
2632 """
2634 def __init__(
2635 self,
2636 graph: 'Graph',
2637 name: Nullable[str] = None,
2638 vertices: Nullable[Iterable[Vertex]] = None,
2639 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None
2640 ) -> None:
2641 """
2642 .. todo:: GRAPH::View::init Needs documentation.
2644 :param graph: The reference to the graph.
2645 :param name: The optional name of the new view.
2646 :param vertices: The optional list of vertices in the new view.
2647 :param keyValuePairs: The optional mapping (dictionary) of key-value-pairs.
2648 """
2649 super().__init__(graph, name, vertices, keyValuePairs)
2651 graph._views.add(self)
2653 def __del__(self):
2654 """
2655 .. todo:: GRAPH::View::del Needs documentation.
2657 """
2658 super().__del__()
2660 def __str__(self) -> str:
2661 """
2662 .. todo:: GRAPH::View::str Needs documentation.
2664 """
2665 return self._name if self._name is not None else "Unnamed view"
2668@export
2669class Component(
2670 BaseWithVertices[
2671 ComponentDictKeyType, ComponentDictValueType,
2672 GraphDictKeyType, GraphDictValueType,
2673 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,
2674 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,
2675 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType
2676 ],
2677 Generic[
2678 ComponentDictKeyType, ComponentDictValueType,
2679 GraphDictKeyType, GraphDictValueType,
2680 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,
2681 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,
2682 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType
2683 ]
2684):
2685 """
2686 .. todo:: GRAPH::Component Needs documentation.
2688 """
2690 def __init__(
2691 self,
2692 graph: 'Graph',
2693 name: Nullable[str] = None,
2694 vertices: Nullable[Iterable[Vertex]] = None,
2695 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None
2696 ) -> None:
2697 """
2698 .. todo:: GRAPH::Component::init Needs documentation.
2700 :param graph: The reference to the graph.
2701 :param name: The optional name of the new component.
2702 :param vertices: The optional list of vertices in the new component.
2703 :param keyValuePairs: The optional mapping (dictionary) of key-value-pairs.
2704 """
2705 super().__init__(graph, name, vertices, keyValuePairs)
2707 graph._components.add(self)
2709 def __del__(self):
2710 """
2711 .. todo:: GRAPH::Component::del Needs documentation.
2713 """
2714 super().__del__()
2716 def __str__(self) -> str:
2717 """
2718 .. todo:: GRAPH::Component::str Needs documentation.
2720 """
2721 return self._name if self._name is not None else "Unnamed component"
2724@export
2725class Graph(
2726 BaseGraph[
2727 GraphDictKeyType, GraphDictValueType,
2728 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,
2729 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,
2730 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType
2731 ],
2732 Generic[
2733 GraphDictKeyType, GraphDictValueType,
2734 ComponentDictKeyType, ComponentDictValueType,
2735 SubgraphDictKeyType, SubgraphDictValueType,
2736 ViewDictKeyType, ViewDictValueType,
2737 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,
2738 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,
2739 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType
2740 ]
2741):
2742 """
2743 A **graph** data structure is represented by an instance of :class:`~pyTooling.Graph.Graph` holding references to
2744 all nodes. Nodes are instances of :class:`~pyTooling.Graph.Vertex` classes and directed links between nodes are
2745 made of :class:`~pyTooling.Graph.Edge` instances. A graph can have attached meta information as key-value-pairs.
2746 """
2747 _subgraphs: Set[Subgraph[SubgraphDictKeyType, SubgraphDictValueType, VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType, EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType, LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType]]
2748 _views: Set[View[ViewDictKeyType, ViewDictValueType, GraphDictKeyType, GraphDictValueType, VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType, EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType, LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType]]
2749 _components: Set[Component[ComponentDictKeyType, ComponentDictValueType, GraphDictKeyType, GraphDictValueType, VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType, EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType, LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType]]
2751 def __init__(
2752 self,
2753 name: Nullable[str] = None,
2754 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None
2755 ) -> None:
2756 """
2757 .. todo:: GRAPH::Graph::init Needs documentation.
2759 :param name: The optional name of the new graph.
2760 :param keyValuePairs: The optional mapping (dictionary) of key-value-pairs.#
2761 """
2762 super().__init__(name, keyValuePairs)
2764 self._subgraphs = set()
2765 self._views = set()
2766 self._components = set()
2768 def __del__(self):
2769 """
2770 .. todo:: GRAPH::Graph::del Needs documentation.
2772 """
2773 try:
2774 del self._subgraphs
2775 del self._views
2776 del self._components
2777 except AttributeError:
2778 pass
2780 super().__del__()
2782 @readonly
2783 def Subgraphs(self) -> Set[Subgraph]:
2784 """Read-only property to access the subgraphs in this graph (:attr:`_subgraphs`).
2786 :returns: The set of subgraphs in this graph."""
2787 return self._subgraphs
2789 @readonly
2790 def Views(self) -> Set[View]:
2791 """Read-only property to access the views in this graph (:attr:`_views`).
2793 :returns: The set of views in this graph."""
2794 return self._views
2796 @readonly
2797 def Components(self) -> Set[Component]:
2798 """Read-only property to access the components in this graph (:attr:`_components`).
2800 :returns: The set of components in this graph."""
2801 return self._components
2803 @readonly
2804 def SubgraphCount(self) -> int:
2805 """Read-only property to access the number of subgraphs in this graph.
2807 :returns: The number of subgraphs in this graph."""
2808 return len(self._subgraphs)
2810 @readonly
2811 def ViewCount(self) -> int:
2812 """Read-only property to access the number of views in this graph.
2814 :returns: The number of views in this graph."""
2815 return len(self._views)
2817 @readonly
2818 def ComponentCount(self) -> int:
2819 """Read-only property to access the number of components in this graph.
2821 :returns: The number of components in this graph."""
2822 return len(self._components)
2824 def __iter__(self) -> typing_Iterator[Vertex[GraphDictKeyType, GraphDictValueType, VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType, EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType, LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType]]:
2825 """
2826 .. todo:: GRAPH::Graph::iter Needs documentation.
2828 """
2829 def gen():
2830 yield from self._verticesWithoutID
2831 yield from self._verticesWithID
2832 return iter(gen())
2834 def HasVertexByID(self, vertexID: Nullable[VertexIDType]) -> bool:
2835 """
2836 .. todo:: GRAPH::Graph::HasVertexByID Needs documentation.
2838 """
2839 if vertexID is None:
2840 return len(self._verticesWithoutID) >= 1
2841 else:
2842 return vertexID in self._verticesWithID
2844 def HasVertexByValue(self, value: Nullable[VertexValueType]) -> bool:
2845 """
2846 .. todo:: GRAPH::Graph::HasVertexByValue Needs documentation.
2848 """
2849 return any(vertex._value == value for vertex in chain(self._verticesWithoutID, self._verticesWithID.values()))
2851 def GetVertexByID(self, vertexID: Nullable[VertexIDType]) -> Vertex:
2852 """
2853 .. todo:: GRAPH::Graph::GetVertexByID Needs documentation.
2855 """
2856 if vertexID is None:
2857 if (l := len(self._verticesWithoutID)) == 1:
2858 return self._verticesWithoutID[0]
2859 elif l == 0:
2860 raise KeyError(f"Found no vertex with ID `None`.")
2861 else:
2862 raise KeyError(f"Found multiple vertices with ID `None`.")
2863 else:
2864 return self._verticesWithID[vertexID]
2866 def GetVertexByValue(self, value: Nullable[VertexValueType]) -> Vertex:
2867 """
2868 .. todo:: GRAPH::Graph::GetVertexByValue Needs documentation.
2870 """
2871 # FIXME: optimize: iterate only until first item is found and check for a second to produce error
2872 vertices = [vertex for vertex in chain(self._verticesWithoutID, self._verticesWithID.values()) if vertex._value == value]
2873 if (l := len(vertices)) == 1:
2874 return vertices[0]
2875 elif l == 0:
2876 raise KeyError(f"Found no vertex with Value == `{value}`.")
2877 else:
2878 raise KeyError(f"Found multiple vertices with Value == `{value}`.")
2880 def CopyGraph(self) -> 'Graph':
2881 raise NotImplementedError()
2883 def CopyVertices(self, predicate: Nullable[Callable[[Vertex], bool]] = None, copyGraphDict: bool = True, copyVertexDict: bool = True) -> 'Graph':
2884 """
2885 Create a new graph and copy all or selected vertices of the original graph.
2887 If parameter ``predicate`` is not None, the given filter function is used to skip vertices.
2889 :param predicate: Filter function accepting any vertex and returning a boolean.
2890 :param copyGraphDict: If ``True``, copy all graph attached attributes into the new graph.
2891 :param copyVertexDict: If ``True``, copy all vertex attached attributes into the new vertices.
2892 """
2893 graph = Graph(self._name)
2894 if copyGraphDict:
2895 graph._dict = self._dict.copy()
2897 if predicate is None:
2898 for vertex in self._verticesWithoutID:
2899 v = Vertex(None, vertex._value, graph=graph)
2900 if copyVertexDict:
2901 v._dict = vertex._dict.copy()
2903 for vertexID, vertex in self._verticesWithID.items():
2904 v = Vertex(vertexID, vertex._value, graph=graph)
2905 if copyVertexDict:
2906 v._dict = vertex._dict.copy()
2907 else:
2908 for vertex in self._verticesWithoutID:
2909 if predicate(vertex):
2910 v = Vertex(None, vertex._value, graph=graph)
2911 if copyVertexDict: 2911 ↛ 2908line 2911 didn't jump to line 2908 because the condition on line 2911 was always true
2912 v._dict = vertex._dict.copy()
2914 for vertexID, vertex in self._verticesWithID.items():
2915 if predicate(vertex):
2916 v = Vertex(vertexID, vertex._value, graph=graph)
2917 if copyVertexDict: 2917 ↛ 2918line 2917 didn't jump to line 2918 because the condition on line 2917 was never true
2918 v._dict = vertex._dict.copy()
2920 return graph
2922 # class Iterator():
2923 # visited = [False for _ in range(self.__len__())]
2925 # def CheckForNegativeCycles(self):
2926 # raise NotImplementedError()
2927 # # Bellman-Ford
2928 # # Floyd-Warshall
2929 #
2930 # def IsStronglyConnected(self):
2931 # raise NotImplementedError()
2932 #
2933 # def GetStronglyConnectedComponents(self):
2934 # raise NotImplementedError()
2935 # # Tarjan's and Kosaraju's algorithm
2936 #
2937 # def TravelingSalesmanProblem(self):
2938 # raise NotImplementedError()
2939 # # Held-Karp
2940 # # branch and bound
2941 #
2942 # def GetBridges(self):
2943 # raise NotImplementedError()
2944 #
2945 # def GetArticulationPoints(self):
2946 # raise NotImplementedError()
2947 #
2948 # def MinimumSpanningTree(self):
2949 # raise NotImplementedError()
2950 # # Kruskal
2951 # # Prim's algorithm
2952 # # Buruvka's algorithm
2954 def __repr__(self) -> str:
2955 """
2956 .. todo:: GRAPH::Graph::repr Needs documentation.
2958 """
2959 statistics = f", vertices: {self.VertexCount}, edges: {self.EdgeCount}"
2960 if self._name is None:
2961 return f"<graph: unnamed graph{statistics}>"
2962 else:
2963 return f"<graph: '{self._name}'{statistics}>"
2965 def __str__(self) -> str:
2966 """
2967 .. todo:: GRAPH::Graph::str Needs documentation.
2969 """
2970 if self._name is None:
2971 return f"Graph: unnamed graph"
2972 else:
2973 return f"Graph: '{self._name}'"