Coverage for pyTooling/Graph/__init_

1# ==================================================================================================================== #

2# _____ _ _ ____ _ #

3# _ __ _ |_ _|__ ___ | (_)_ __ __ _ / ___|_ __ __ _ _ __ | |__ #

4# | '_ \| | | || |/ _ \ / _ \| | | '_ \ / _` || | _| '__/ _` | '_ \| '_ \ #

5# | |_) | |_| || | (_) | (_) | | | | | | (_| || |_| | | | (_| | |_) | | | | #

6# | .__/ \__, ||_|\___/ \___/|_|_|_| |_|\__, (_)____|_| \__,_| .__/|_| |_| #

7# |_| |___/ |___/ |_| #

8# ==================================================================================================================== #

9# Authors: #

10# Patrick Lehmann #

11# #

12# License: #

13# ==================================================================================================================== #

15# #

16# Licensed under the Apache License, Version 2.0 (the "License"); #

17# you may not use this file except in compliance with the License. #

18# You may obtain a copy of the License at #

19# #

20# http://www.apache.org/licenses/LICENSE-2.0 #

21# #

22# Unless required by applicable law or agreed to in writing, software #

23# distributed under the License is distributed on an "AS IS" BASIS, #

24# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. #

25# See the License for the specific language governing permissions and #

26# limitations under the License. #

27# #

28# SPDX-License-Identifier: Apache-2.0 #

29# ==================================================================================================================== #

30#

31"""

32A powerful **graph** data structure for Python.

34Graph algorithms using all vertices are provided as methods on the graph instance. Whereas graph algorithms based on a

35starting vertex are provided as methods on a vertex.

37.. admonition:: Example Graph

39 .. mermaid::

40 :caption: A directed graph with backward-edges denoted by dotted vertex relations.

42 %%{init: { "flowchart": { "nodeSpacing": 15, "rankSpacing": 30, "curve": "linear", "useMaxWidth": false } } }%%

43 graph LR

44 A(A); B(B); C(C); D(D); E(E); F(F) ; G(G); H(H); I(I)

46 A --> B --> E

47 G --> F

48 A --> C --> G --> H --> D

49 D -.-> A

50 D & F -.-> B

51 I ---> E --> F --> D

53 classDef node fill:#eee,stroke:#777,font-size:smaller;

54"""

55import heapq

56from collections import deque

57from itertools import chain

58from sys import version_info # needed for versions before Python 3.11

59from typing import TypeVar, Generic, List, Tuple, Dict, Set, Deque, Union, Optional as Nullable

60from typing import Callable, Iterator as typing_Iterator, Generator, Iterable, Mapping, Hashable

62try:

63 from pyTooling.Decorators import export, readonly

64 from pyTooling.MetaClasses import ExtendedType

65 from pyTooling.Exceptions import ToolingException

66 from pyTooling.Common import getFullyQualifiedName

67 from pyTooling.Tree import Node

68except (ImportError, ModuleNotFoundError): # pragma: no cover

69 print("[pyTooling.Graph] Could not import from 'pyTooling.*'!")

71 try:

72 from Decorators import export, readonly

73 from MetaClasses import ExtendedType, mixin

74 from Exceptions import ToolingException

75 from Common import getFullyQualifiedName

76 from Tree import Node

77 except (ImportError, ModuleNotFoundError) as ex: # pragma: no cover

78 print("[pyTooling.Graph] Could not import directly!")

79 raise ex

82DictKeyType = TypeVar("DictKeyType", bound=Hashable)

83"""A type variable for dictionary keys."""

85DictValueType = TypeVar("DictValueType")

86"""A type variable for dictionary values."""

88IDType = TypeVar("IDType", bound=Hashable)

89"""A type variable for an ID."""

91WeightType = TypeVar("WeightType", bound=Union[int, float])

92"""A type variable for a weight."""

94ValueType = TypeVar("ValueType")

95"""A type variable for a value."""

97VertexIDType = TypeVar("VertexIDType", bound=Hashable)

98"""A type variable for a vertex's ID."""

100VertexWeightType = TypeVar("VertexWeightType", bound=Union[int, float])

101"""A type variable for a vertex's weight."""

102

103VertexValueType = TypeVar("VertexValueType")

104"""A type variable for a vertex's value."""

105

106VertexDictKeyType = TypeVar("VertexDictKeyType", bound=Hashable)

107"""A type variable for a vertex's dictionary keys."""

108

109VertexDictValueType = TypeVar("VertexDictValueType")

110"""A type variable for a vertex's dictionary values."""

111

112EdgeIDType = TypeVar("EdgeIDType", bound=Hashable)

113"""A type variable for an edge's ID."""

114

115EdgeWeightType = TypeVar("EdgeWeightType", bound=Union[int, float])

116"""A type variable for an edge's weight."""

117

118EdgeValueType = TypeVar("EdgeValueType")

119"""A type variable for an edge's value."""

120

121EdgeDictKeyType = TypeVar("EdgeDictKeyType", bound=Hashable)

122"""A type variable for an edge's dictionary keys."""

123

124EdgeDictValueType = TypeVar("EdgeDictValueType")

125"""A type variable for an edge's dictionary values."""

126

127LinkIDType = TypeVar("LinkIDType", bound=Hashable)

128"""A type variable for an link's ID."""

129

130LinkWeightType = TypeVar("LinkWeightType", bound=Union[int, float])

131"""A type variable for an link's weight."""

132

133LinkValueType = TypeVar("LinkValueType")

134"""A type variable for an link's value."""

135

136LinkDictKeyType = TypeVar("LinkDictKeyType", bound=Hashable)

137"""A type variable for an link's dictionary keys."""

138

139LinkDictValueType = TypeVar("LinkDictValueType")

140"""A type variable for an link's dictionary values."""

141

142ComponentDictKeyType = TypeVar("ComponentDictKeyType", bound=Hashable)

143"""A type variable for a component's dictionary keys."""

144

145ComponentDictValueType = TypeVar("ComponentDictValueType")

146"""A type variable for a component's dictionary values."""

147

148SubgraphDictKeyType = TypeVar("SubgraphDictKeyType", bound=Hashable)

149"""A type variable for a component's dictionary keys."""

150

151SubgraphDictValueType = TypeVar("SubgraphDictValueType")

152"""A type variable for a component's dictionary values."""

153

154ViewDictKeyType = TypeVar("ViewDictKeyType", bound=Hashable)

155"""A type variable for a component's dictionary keys."""

156

157ViewDictValueType = TypeVar("ViewDictValueType")

158"""A type variable for a component's dictionary values."""

159

160GraphDictKeyType = TypeVar("GraphDictKeyType", bound=Hashable)

161"""A type variable for a graph's dictionary keys."""

162

163GraphDictValueType = TypeVar("GraphDictValueType")

164"""A type variable for a graph's dictionary values."""

165

166

167@export

168class GraphException(ToolingException):

169 """Base exception of all exceptions raised by :mod:`pyTooling.Graph`."""

170

171

172@export

173class InternalError(GraphException):

174 """

175 The exception is raised when a data structure corruption is detected.

176

177 .. danger::

178

179 This exception should never be raised.

180

181 If so, please create an issue at GitHub so the data structure corruption can be investigated and fixed. |br|

182 `⇒ Bug Tracker at GitHub <https://github.com/pyTooling/pyTooling/issues>`__

183 """

184

185

186@export

187class NotInSameGraph(GraphException):

188 """The exception is raised when creating an edge between two vertices, but these are not in the same graph."""

189

190

191@export

192class DuplicateVertexError(GraphException):

193 """The exception is raised when the vertex already exists in the graph."""

194

195

196@export

197class DuplicateEdgeError(GraphException):

198 """The exception is raised when the edge already exists in the graph."""

199

200

201@export

202class DestinationNotReachable(GraphException):

203 """The exception is raised when a destination vertex is not reachable."""

204

205

206@export

207class NotATreeError(GraphException):

208 """

209 The exception is raised when a subgraph is not a tree.

210

211 Either the subgraph has a cycle (backward edge) or links between branches (cross-edge).

212 """

213

214

215@export

216class CycleError(GraphException):

217 """The exception is raised when a not permitted cycle is found."""

218

219

220@export

221class Base(

222 Generic[DictKeyType, DictValueType],

223 metaclass=ExtendedType, slots=True

224):

225 _dict: Dict[DictKeyType, DictValueType] #: A dictionary to store arbitrary key-value-pairs.

226

227 def __init__(

228 self,

229 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None

230 ) -> None:

231 """

232 .. todo:: GRAPH::Base::init Needs documentation.

233

234 :param keyValuePairs: The optional mapping (dictionary) of key-value-pairs.

235 """

236 self._dict = {key: value for key, value in keyValuePairs.items()} if keyValuePairs is not None else {}

237

238 def __del__(self):

239 """

240 .. todo:: GRAPH::Base::del Needs documentation.

241

242 """

243 try:

244 del self._dict

245 except AttributeError:

246 pass

247

248 def Delete(self) -> None:

249 self._dict = None

250

251 def __getitem__(self, key: DictKeyType) -> DictValueType:

252 """

253 Read a vertex's attached attributes (key-value-pairs) by key.

254

255 :param key: The key to look for.

256 :returns: The value associated to the given key.

257 """

258 return self._dict[key]

259

260 def __setitem__(self, key: DictKeyType, value: DictValueType) -> None:

261 """

262 Create or update a vertex's attached attributes (key-value-pairs) by key.

263

264 If a key doesn't exist yet, a new key-value-pair is created.

265

266 :param key: The key to create or update.

267 :param value: The value to associate to the given key.

268 """

269 self._dict[key] = value

270

271 def __delitem__(self, key: DictKeyType) -> None:

272 """

273 Remove an entry from vertex's attached attributes (key-value-pairs) by key.

274

275 :param key: The key to remove.

276 :raises KeyError: If key doesn't exist in the vertex's attributes.

277 """

278 del self._dict[key]

279

280 def __contains__(self, key: DictKeyType) -> bool:

281 """

282 Returns if the key is an attached attribute (key-value-pairs) on this vertex.

283

284 :param key: The key to check.

285 :returns: ``True``, if the key is an attached attribute.

286 """

287 return key in self._dict

288

289 def __len__(self) -> int:

290 """

291 Returns the number of attached attributes (key-value-pairs) on this vertex.

292

293 :returns: Number of attached attributes.

294 """

295 return len(self._dict)

296

297

298@export

299class BaseWithIDValueAndWeight(

300 Base[DictKeyType, DictValueType],

301 Generic[IDType, ValueType, WeightType, DictKeyType, DictValueType]

302):

303 _id: Nullable[IDType] #: Field storing the object's Identifier.

304 _value: Nullable[ValueType] #: Field storing the object's value of any type.

305 _weight: Nullable[WeightType] #: Field storing the object's weight.

306

307 def __init__(

308 self,

309 identifier: Nullable[IDType] = None,

310 value: Nullable[ValueType] = None,

311 weight: Nullable[WeightType] = None,

312 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None

313 ) -> None:

314 """

315 .. todo:: GRAPH::Vertex::init Needs documentation.

316

317 :param identifier: The optional unique ID.

318 :param value: The optional value.

319 :param weight: The optional weight.

320 :param keyValuePairs: The optional mapping (dictionary) of key-value-pairs.

321 """

322 super().__init__(keyValuePairs)

323

324 self._id = identifier

325 self._value = value

326 self._weight = weight

327

328 @readonly

329 def ID(self) -> Nullable[IDType]:

330 """

331 Read-only property to access the unique ID (:attr:`_id`).

332

333 If no ID was given at creation time, ID returns ``None``.

334

335 :returns: Unique ID, if ID was given at creation time, else ``None``.

336 """

337 return self._id

338

339 @property

340 def Value(self) -> ValueType:

341 """

342 Property to get and set the value (:attr:`_value`).

343

344 :returns: The value.

345 """

346 return self._value

347

348 @Value.setter

349 def Value(self, value: ValueType) -> None:

350 self._value = value

351

352 @property

353 def Weight(self) -> Nullable[EdgeWeightType]:

354 """

355 Property to get and set the weight (:attr:`_weight`) of an edge.

356

357 :returns: The weight of an edge.

358 """

359 return self._weight

360

361 @Weight.setter

362 def Weight(self, value: Nullable[EdgeWeightType]) -> None:

363 self._weight = value

364

365

366@export

367class BaseWithName(

368 Base[DictKeyType, DictValueType],

369 Generic[DictKeyType, DictValueType]

370):

371 _name: Nullable[str] #: Field storing the object's name.

372

373 def __init__(

374 self,

375 name: Nullable[str] = None,

376 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None,

377 ) -> None:

378 """

379 .. todo:: GRAPH::BaseWithName::init Needs documentation.

380

381 :param name: The optional name.

382 :param keyValuePairs: The optional mapping (dictionary) of key-value-pairs.

383 """

384 if name is not None and not isinstance(name, str):

385 ex = TypeError("Parameter 'name' is not of type 'str'.")

386 if version_info >= (3, 11): # pragma: no cover

387 ex.add_note(f"Got type '{getFullyQualifiedName(name)}'.")

388 raise ex

389

390 super().__init__(keyValuePairs)

391

392 self._name = name

393

394 @property

395 def Name(self) -> Nullable[str]:

396 """

397 Property to get and set the name (:attr:`_name`).

398

399 :returns: The value of a component.

400 """

401 return self._name

402

403 @Name.setter

404 def Name(self, value: str) -> None:

405 if not isinstance(value, str):

406 ex = TypeError("Name is not of type 'str'.")

407 if version_info >= (3, 11): # pragma: no cover

408 ex.add_note(f"Got type '{getFullyQualifiedName(value)}'.")

409 raise ex

410

411 self._name = value

412

413

414@export

415class BaseWithVertices(

416 BaseWithName[DictKeyType, DictValueType],

417 Generic[

418 DictKeyType, DictValueType,

419 GraphDictKeyType, GraphDictValueType,

420 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,

421 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,

422 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType

423 ]

424):

425 _graph: 'Graph[GraphDictKeyType, GraphDictValueType,' \

426 'VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,' \

427 'EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,' \

428 'LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType' \

429 ']' #: Field storing a reference to the graph.

430 _vertices: Set['Vertex[GraphDictKeyType, GraphDictValueType,'

431 'VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,'

432 'EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,'

433 'LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType'

434 ']'] #: Field storing a set of vertices.

435

436 def __init__(

437 self,

438 graph: 'Graph',

439 name: Nullable[str] = None,

440 vertices: Nullable[Iterable['Vertex']] = None,

441 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None

442 ) -> None:

443 """

444 .. todo:: GRAPH::Component::init Needs documentation.

445

446 :param graph: The reference to the graph.

447 :param name: The optional name.

448 :param vertices: The optional list of vertices.

449 :param keyValuePairs: The optional mapping (dictionary) of key-value-pairs.

450 """

451 if graph is None: 451 ↛ 452line 451 didn't jump to line 452 because the condition on line 451 was never true

452 raise ValueError("Parameter 'graph' is None.")

453 elif not isinstance(graph, Graph): 453 ↛ 454line 453 didn't jump to line 454 because the condition on line 453 was never true

454 ex = TypeError("Parameter 'graph' is not of type 'Graph'.")

455 if version_info >= (3, 11): # pragma: no cover

456 ex.add_note(f"Got type '{getFullyQualifiedName(graph)}'.")

457 raise ex

458

459 super().__init__(name, keyValuePairs)

460

461 self._graph = graph

462 self._vertices = set() if vertices is None else {v for v in vertices}

463

464 def __del__(self):

465 """

466 .. todo:: GRAPH::BaseWithVertices::del Needs documentation.

467

468 """

469 try:

470 del self._vertices

471 except AttributeError:

472 pass

473

474 super().__del__()

475

476 @readonly

477 def Graph(self) -> 'Graph':

478 """

479 Read-only property to access the graph, this object is associated to (:attr:`_graph`).

480

481 :returns: The graph this object is associated to.

482 """

483 return self._graph

484

485 @readonly

486 def Vertices(self) -> Set['Vertex']:

487 """

488 Read-only property to access the vertices in this component (:attr:`_vertices`).

489

490 :returns: The set of vertices in this component.

491 """

492 return self._vertices

493

494 @readonly

495 def VertexCount(self) -> int:

496 """

497 Read-only property to access the number of vertices referenced by this object.

498

499 :returns: The number of vertices this object references.

500 """

501 return len(self._vertices)

502

503

504@export

505class Vertex(

506 BaseWithIDValueAndWeight[VertexIDType, VertexValueType, VertexWeightType, VertexDictKeyType, VertexDictValueType],

507 Generic[

508 GraphDictKeyType, GraphDictValueType,

509 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,

510 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,

511 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType

512 ]

513):

514 """

515 A **vertex** can have a unique ID, a value and attached meta information as key-value-pairs. A vertex has references

516 to inbound and outbound edges, thus a graph can be traversed in reverse.

517 """

518 _graph: 'BaseGraph[GraphDictKeyType, GraphDictValueType, VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType, EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType]' #: Field storing a reference to the graph.

519 _subgraph: 'Subgraph[GraphDictKeyType, GraphDictValueType, VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType, EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType]' #: Field storing a reference to the subgraph.

520 _component: 'Component'

521 _views: Dict[Hashable, 'View']

522 _inboundEdges: List['Edge[EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType]'] #: Field storing a list of inbound edges.

523 _outboundEdges: List['Edge[EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType]'] #: Field storing a list of outbound edges.

524 _inboundLinks: List['Link[EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType]'] #: Field storing a list of inbound links.

525 _outboundLinks: List['Link[EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType]'] #: Field storing a list of outbound links.

526

527 def __init__(

528 self,

529 vertexID: Nullable[VertexIDType] = None,

530 value: Nullable[VertexValueType] = None,

531 weight: Nullable[VertexWeightType] = None,

532 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None,

533 graph: Nullable['Graph'] = None,

534 subgraph: Nullable['Subgraph'] = None

535 ) -> None:

536 """

537 .. todo:: GRAPH::Vertex::init Needs documentation.

538

539 :param vertexID: The optional ID for the new vertex.

540 :param value: The optional value for the new vertex.

541 :param weight: The optional weight for the new vertex.

542 :param keyValuePairs: The optional mapping (dictionary) of key-value-pairs.

543 :param graph: The optional reference to the graph.

544 :param subgraph: undocumented

545 """

546 if vertexID is not None and not isinstance(vertexID, Hashable): 546 ↛ 547line 546 didn't jump to line 547 because the condition on line 546 was never true

547 ex = TypeError("Parameter 'vertexID' is not of type 'VertexIDType'.")

548 if version_info >= (3, 11): # pragma: no cover

549 ex.add_note(f"Got type '{getFullyQualifiedName(vertexID)}'.")

550 raise ex

551

552 super().__init__(vertexID, value, weight, keyValuePairs)

553

554 if subgraph is None:

555 self._graph = graph if graph is not None else Graph()

556 self._subgraph = None

557 self._component = Component(self._graph, vertices=(self,))

558

559 if vertexID is None:

560 self._graph._verticesWithoutID.append(self)

561 elif vertexID not in self._graph._verticesWithID:

562 self._graph._verticesWithID[vertexID] = self

563 else:

564 raise DuplicateVertexError(f"Vertex ID '{vertexID}' already exists in this graph.")

565 else:

566 self._graph = subgraph._graph

567 self._subgraph = subgraph

568 self._component = Component(self._graph, vertices=(self,))

569

570 if vertexID is None:

571 subgraph._verticesWithoutID.append(self)

572 elif vertexID not in subgraph._verticesWithID: 572 ↛ 575line 572 didn't jump to line 575 because the condition on line 572 was always true

573 subgraph._verticesWithID[vertexID] = self

574 else:

575 raise DuplicateVertexError(f"Vertex ID '{vertexID}' already exists in this subgraph.")

576

577 self._views = {}

578 self._inboundEdges = []

579 self._outboundEdges = []

580 self._inboundLinks = []

581 self._outboundLinks = []

582

583 def __del__(self):

584 """

585 .. todo:: GRAPH::BaseEdge::del Needs documentation.

586

587 """

588 try:

589 del self._views

590 del self._inboundEdges

591 del self._outboundEdges

592 del self._inboundLinks

593 del self._outboundLinks

594 except AttributeError:

595 pass

596

597 super().__del__()

598

599 def Delete(self) -> None:

600 for edge in self._outboundEdges:

601 edge._destination._inboundEdges.remove(edge)

602 edge._Delete()

603 for edge in self._inboundEdges:

604 edge._source._outboundEdges.remove(edge)

605 edge._Delete()

606 for link in self._outboundLinks:

607 link._destination._inboundLinks.remove(link)

608 link._Delete()

609 for link in self._inboundLinks:

610 link._source._outboundLinks.remove(link)

611 link._Delete()

612

613 if self._id is None:

614 self._graph._verticesWithoutID.remove(self)

615 else:

616 del self._graph._verticesWithID[self._id]

617

618 # subgraph

619

620 # component

621

622 # views

623 self._views = None

624 self._inboundEdges = None

625 self._outboundEdges = None

626 self._inboundLinks = None

627 self._outboundLinks = None

628

629 super().Delete()

630 assert getrefcount(self) == 1

631

632 @readonly

633 def Graph(self) -> 'Graph':

634 """

635 Read-only property to access the graph, this vertex is associated to (:attr:`_graph`).

636

637 :returns: The graph this vertex is associated to.

638 """

639 return self._graph

640

641 @readonly

642 def Component(self) -> 'Component':

643 """

644 Read-only property to access the component, this vertex is associated to (:attr:`_component`).

645

646 :returns: The component this vertex is associated to.

647 """

648 return self._component

649

650 @readonly

651 def InboundEdges(self) -> Tuple['Edge', ...]:

652 """

653 Read-only property to get a tuple of inbound edges (:attr:`_inboundEdges`).

654

655 :returns: Tuple of inbound edges.

656 """

657 return tuple(self._inboundEdges)

658

659 @readonly

660 def OutboundEdges(self) -> Tuple['Edge', ...]:

661 """

662 Read-only property to get a tuple of outbound edges (:attr:`_outboundEdges`).

663

664 :returns: Tuple of outbound edges.

665 """

666 return tuple(self._outboundEdges)

667

668 @readonly

669 def InboundLinks(self) -> Tuple['Link', ...]:

670 """

671 Read-only property to get a tuple of inbound links (:attr:`_inboundLinks`).

672

673 :returns: Tuple of inbound links.

674 """

675 return tuple(self._inboundLinks)

676

677 @readonly

678 def OutboundLinks(self) -> Tuple['Link', ...]:

679 """

680 Read-only property to get a tuple of outbound links (:attr:`_outboundLinks`).

681

682 :returns: Tuple of outbound links.

683 """

684 return tuple(self._outboundLinks)

685

686 @readonly

687 def EdgeCount(self) -> int:

688 """

689 Read-only property to get the number of all edges (inbound and outbound).

690

691 :returns: Number of inbound and outbound edges.

692 """

693 return len(self._inboundEdges) + len(self._outboundEdges)

694

695 @readonly

696 def InboundEdgeCount(self) -> int:

697 """

698 Read-only property to get the number of inbound edges.

699

700 :returns: Number of inbound edges.

701 """

702 return len(self._inboundEdges)

703

704 @readonly

705 def OutboundEdgeCount(self) -> int:

706 """

707 Read-only property to get the number of outbound edges.

708

709 :returns: Number of outbound edges.

710 """

711 return len(self._outboundEdges)

712

713 @readonly

714 def LinkCount(self) -> int:

715 """

716 Read-only property to get the number of all links (inbound and outbound).

717

718 :returns: Number of inbound and outbound links.

719 """

720 return len(self._inboundLinks) + len(self._outboundLinks)

721

722 @readonly

723 def InboundLinkCount(self) -> int:

724 """

725 Read-only property to get the number of inbound links.

726

727 :returns: Number of inbound links.

728 """

729 return len(self._inboundLinks)

730

731 @readonly

732 def OutboundLinkCount(self) -> int:

733 """

734 Read-only property to get the number of outbound links.

735

736 :returns: Number of outbound links.

737 """

738 return len(self._outboundLinks)

739

740 @readonly

741 def IsRoot(self) -> bool:

742 """

743 Read-only property to check if this vertex is a root vertex in the graph.

744

745 A root has no inbound edges (no predecessor vertices).

746

747 :returns: ``True``, if this vertex is a root.

748

749 .. seealso::

750

751 :meth:`IsLeaf` |br|

752 |rarr| Check if a vertex is a leaf vertex in the graph.

753 :meth:`Graph.IterateRoots <pyTooling.Graph.Graph.IterateRoots>` |br|

754 |rarr| Iterate all roots of a graph.

755 :meth:`Graph.IterateLeafs <pyTooling.Graph.Graph.IterateLeafs>` |br|

756 |rarr| Iterate all leafs of a graph.

757 """

758 return len(self._inboundEdges) == 0

759

760 @readonly

761 def IsLeaf(self) -> bool:

762 """

763 Read-only property to check if this vertex is a leaf vertex in the graph.

764

765 A leaf has no outbound edges (no successor vertices).

766

767 :returns: ``True``, if this vertex is a leaf.

768

769 .. seealso::

770

771 :meth:`IsRoot` |br|

772 |rarr| Check if a vertex is a root vertex in the graph.

773 :meth:`Graph.IterateRoots <pyTooling.Graph.Graph.IterateRoots>` |br|

774 |rarr| Iterate all roots of a graph.

775 :meth:`Graph.IterateLeafs <pyTooling.Graph.Graph.IterateLeafs>` |br|

776 |rarr| Iterate all leafs of a graph.

777 """

778 return len(self._outboundEdges) == 0

779

780 @readonly

781 def Predecessors(self) -> Tuple['Vertex', ...]:

782 """

783 Read-only property to get a tuple of predecessor vertices.

784

785 :returns: Tuple of predecessor vertices.

786 """

787 return tuple([edge.Source for edge in self._inboundEdges])

788

789 @readonly

790 def Successors(self) -> Tuple['Vertex', ...]:

791 """

792 Read-only property to get a tuple of successor vertices.

793

794 :returns: Tuple of successor vertices.

795 """

796 return tuple([edge.Destination for edge in self._outboundEdges])

797

798 def EdgeToVertex(

799 self,

800 vertex: 'Vertex',

801 edgeID: Nullable[EdgeIDType] = None,

802 edgeWeight: Nullable[EdgeWeightType] = None,

803 edgeValue: Nullable[VertexValueType] = None,

804 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None

805 ) -> 'Edge':

806 """

807 Create an outbound edge from this vertex to the referenced vertex.

808

809 :param vertex: The vertex to be linked to.

810 :param edgeID: The edge's optional ID for the new edge object.

811 :param edgeWeight: The edge's optional weight for the new edge object.

812 :param edgeValue: The edge's optional value for the new edge object.

813 :param keyValuePairs: An optional mapping (dictionary) of key-value-pairs for the new edge object.

814 :returns: The edge object linking this vertex and the referenced vertex.

815

816 .. seealso::

817

818 :meth:`EdgeFromVertex` |br|

819 |rarr| Create an inbound edge from the referenced vertex to this vertex.

820 :meth:`EdgeToNewVertex` |br|

821 |rarr| Create a new vertex and link that vertex by an outbound edge from this vertex.

822 :meth:`EdgeFromNewVertex` |br|

823 |rarr| Create a new vertex and link that vertex by an inbound edge to this vertex.

824 :meth:`LinkToVertex` |br|

825 |rarr| Create an outbound link from this vertex to the referenced vertex.

826 :meth:`LinkFromVertex` |br|

827 |rarr| Create an inbound link from the referenced vertex to this vertex.

828

829 .. todo:: GRAPH::Vertex::EdgeToVertex Needs possible exceptions to be documented.

830 """

831 if self._subgraph is vertex._subgraph:

832 edge = Edge(self, vertex, edgeID, edgeValue, edgeWeight, keyValuePairs)

833

834 self._outboundEdges.append(edge)

835 vertex._inboundEdges.append(edge)

836

837 if self._subgraph is None:

838 # TODO: move into Edge?

839 # TODO: keep _graph pointer in edge and then register edge on graph?

840 if edgeID is None:

841 self._graph._edgesWithoutID.append(edge)

842 elif edgeID not in self._graph._edgesWithID:

843 self._graph._edgesWithID[edgeID] = edge

844 else:

845 raise DuplicateEdgeError(f"Edge ID '{edgeID}' already exists in this graph.")

846 else:

847 # TODO: keep _graph pointer in edge and then register edge on graph?

848 if edgeID is None:

849 self._subgraph._edgesWithoutID.append(edge)

850 elif edgeID not in self._subgraph._edgesWithID:

851 self._subgraph._edgesWithID[edgeID] = edge

852 else:

853 raise DuplicateEdgeError(f"Edge ID '{edgeID}' already exists in this subgraph.")

854 else:

855 # FIXME: needs an error message

856 raise GraphException()

857

858 return edge

859

860 def EdgeFromVertex(

861 self,

862 vertex: 'Vertex',

863 edgeID: Nullable[EdgeIDType] = None,

864 edgeWeight: Nullable[EdgeWeightType] = None,

865 edgeValue: Nullable[VertexValueType] = None,

866 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None

867 ) -> 'Edge':

868 """

869 Create an inbound edge from the referenced vertex to this vertex.

870

871 :param vertex: The vertex to be linked from.

872 :param edgeID: The edge's optional ID for the new edge object.

873 :param edgeWeight: The edge's optional weight for the new edge object.

874 :param edgeValue: The edge's optional value for the new edge object.

875 :param keyValuePairs: An optional mapping (dictionary) of key-value-pairs for the new edge object.

876 :returns: The edge object linking the referenced vertex and this vertex.

877

878 .. seealso::

879

880 :meth:`EdgeToVertex` |br|

881 |rarr| Create an outbound edge from this vertex to the referenced vertex.

882 :meth:`EdgeToNewVertex` |br|

883 |rarr| Create a new vertex and link that vertex by an outbound edge from this vertex.

884 :meth:`EdgeFromNewVertex` |br|

885 |rarr| Create a new vertex and link that vertex by an inbound edge to this vertex.

886 :meth:`LinkToVertex` |br|

887 |rarr| Create an outbound link from this vertex to the referenced vertex.

888 :meth:`LinkFromVertex` |br|

889 |rarr| Create an inbound link from the referenced vertex to this vertex.

890

891 .. todo:: GRAPH::Vertex::EdgeFromVertex Needs possible exceptions to be documented.

892 """

893 if self._subgraph is vertex._subgraph: 893 ↛ 918line 893 didn't jump to line 918 because the condition on line 893 was always true

894 edge = Edge(vertex, self, edgeID, edgeValue, edgeWeight, keyValuePairs)

895

896 vertex._outboundEdges.append(edge)

897 self._inboundEdges.append(edge)

898

899 if self._subgraph is None:

900 # TODO: move into Edge?

901 # TODO: keep _graph pointer in edge and then register edge on graph?

902 if edgeID is None:

903 self._graph._edgesWithoutID.append(edge)

904 elif edgeID not in self._graph._edgesWithID:

905 self._graph._edgesWithID[edgeID] = edge

906 else:

907 raise DuplicateEdgeError(f"Edge ID '{edgeID}' already exists in this graph.")

908 else:

909 # TODO: keep _graph pointer in edge and then register edge on graph?

910 if edgeID is None:

911 self._subgraph._edgesWithoutID.append(edge)

912 elif edgeID not in self._graph._edgesWithID:

913 self._subgraph._edgesWithID[edgeID] = edge

914 else:

915 raise DuplicateEdgeError(f"Edge ID '{edgeID}' already exists in this graph.")

916 else:

917 # FIXME: needs an error message

918 raise GraphException()

919

920 return edge

921

922 def EdgeToNewVertex(

923 self,

924 vertexID: Nullable[VertexIDType] = None,

925 vertexValue: Nullable[VertexValueType] = None,

926 vertexWeight: Nullable[VertexWeightType] = None,

927 vertexKeyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None,

928 edgeID: Nullable[EdgeIDType] = None,

929 edgeWeight: Nullable[EdgeWeightType] = None,

930 edgeValue: Nullable[VertexValueType] = None,

931 edgeKeyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None

932 ) -> 'Edge':

933 """

934 Create a new vertex and link that vertex by an outbound edge from this vertex.

935

936 :param vertexID: The new vertex' optional ID.

937 :param vertexValue: The new vertex' optional value.

938 :param vertexWeight: The new vertex' optional weight.

939 :param vertexKeyValuePairs: An optional mapping (dictionary) of key-value-pairs for the new vertex.

940 :param edgeID: The edge's optional ID for the new edge object.

941 :param edgeWeight: The edge's optional weight for the new edge object.

942 :param edgeValue: The edge's optional value for the new edge object.

943 :param edgeKeyValuePairs: An optional mapping (dictionary) of key-value-pairs for the new edge object.

944 :returns: The edge object linking this vertex and the created vertex.

945

946 .. seealso::

947

948 :meth:`EdgeToVertex` |br|

949 |rarr| Create an outbound edge from this vertex to the referenced vertex.

950 :meth:`EdgeFromVertex` |br|

951 |rarr| Create an inbound edge from the referenced vertex to this vertex.

952 :meth:`EdgeFromNewVertex` |br|

953 |rarr| Create a new vertex and link that vertex by an inbound edge to this vertex.

954 :meth:`LinkToVertex` |br|

955 |rarr| Create an outbound link from this vertex to the referenced vertex.

956 :meth:`LinkFromVertex` |br|

957 |rarr| Create an inbound link from the referenced vertex to this vertex.

958

959 .. todo:: GRAPH::Vertex::EdgeToNewVertex Needs possible exceptions to be documented.

960 """

961 vertex = Vertex(vertexID, vertexValue, vertexWeight, vertexKeyValuePairs, graph=self._graph) # , component=self._component)

962

963 if self._subgraph is vertex._subgraph: 963 ↛ 988line 963 didn't jump to line 988 because the condition on line 963 was always true

964 edge = Edge(self, vertex, edgeID, edgeValue, edgeWeight, edgeKeyValuePairs)

965

966 self._outboundEdges.append(edge)

967 vertex._inboundEdges.append(edge)

968

969 if self._subgraph is None: 969 ↛ 980line 969 didn't jump to line 980 because the condition on line 969 was always true

970 # TODO: move into Edge?

971 # TODO: keep _graph pointer in edge and then register edge on graph?

972 if edgeID is None: 972 ↛ 974line 972 didn't jump to line 974 because the condition on line 972 was always true

973 self._graph._edgesWithoutID.append(edge)

974 elif edgeID not in self._graph._edgesWithID:

975 self._graph._edgesWithID[edgeID] = edge

976 else:

977 raise DuplicateEdgeError(f"Edge ID '{edgeID}' already exists in this graph.")

978 else:

979 # TODO: keep _graph pointer in edge and then register edge on graph?

980 if edgeID is None:

981 self._subgraph._edgesWithoutID.append(edge)

982 elif edgeID not in self._graph._edgesWithID:

983 self._subgraph._edgesWithID[edgeID] = edge

984 else:

985 raise DuplicateEdgeError(f"Edge ID '{edgeID}' already exists in this graph.")

986 else:

987 # FIXME: needs an error message

988 raise GraphException()

989

990 return edge

991

992 def EdgeFromNewVertex(

993 self,

994 vertexID: Nullable[VertexIDType] = None,

995 vertexValue: Nullable[VertexValueType] = None,

996 vertexWeight: Nullable[VertexWeightType] = None,

997 vertexKeyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None,

998 edgeID: Nullable[EdgeIDType] = None,

999 edgeWeight: Nullable[EdgeWeightType] = None,

1000 edgeValue: Nullable[VertexValueType] = None,

1001 edgeKeyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None

1002 ) -> 'Edge':

1003 """

1004 Create a new vertex and link that vertex by an inbound edge to this vertex.

1005

1006 :param vertexID: The new vertex' optional ID.

1007 :param vertexValue: The new vertex' optional value.

1008 :param vertexWeight: The new vertex' optional weight.

1009 :param vertexKeyValuePairs: An optional mapping (dictionary) of key-value-pairs for the new vertex.

1010 :param edgeID: The edge's optional ID for the new edge object.

1011 :param edgeWeight: The edge's optional weight for the new edge object.

1012 :param edgeValue: The edge's optional value for the new edge object.

1013 :param edgeKeyValuePairs: An optional mapping (dictionary) of key-value-pairs for the new edge object.

1014 :returns: The edge object linking this vertex and the created vertex.

1015

1016 .. seealso::

1017

1018 :meth:`EdgeToVertex` |br|

1019 |rarr| Create an outbound edge from this vertex to the referenced vertex.

1020 :meth:`EdgeFromVertex` |br|

1021 |rarr| Create an inbound edge from the referenced vertex to this vertex.

1022 :meth:`EdgeToNewVertex` |br|

1023 |rarr| Create a new vertex and link that vertex by an outbound edge from this vertex.

1024 :meth:`LinkToVertex` |br|

1025 |rarr| Create an outbound link from this vertex to the referenced vertex.

1026 :meth:`LinkFromVertex` |br|

1027 |rarr| Create an inbound link from the referenced vertex to this vertex.

1028

1029 .. todo:: GRAPH::Vertex::EdgeFromNewVertex Needs possible exceptions to be documented.

1030 """

1031 vertex = Vertex(vertexID, vertexValue, vertexWeight, vertexKeyValuePairs, graph=self._graph) # , component=self._component)

1032

1033 if self._subgraph is vertex._subgraph: 1033 ↛ 1058line 1033 didn't jump to line 1058 because the condition on line 1033 was always true

1034 edge = Edge(vertex, self, edgeID, edgeValue, edgeWeight, edgeKeyValuePairs)

1035

1036 vertex._outboundEdges.append(edge)

1037 self._inboundEdges.append(edge)

1038

1039 if self._subgraph is None: 1039 ↛ 1050line 1039 didn't jump to line 1050 because the condition on line 1039 was always true

1040 # TODO: move into Edge?

1041 # TODO: keep _graph pointer in edge and then register edge on graph?

1042 if edgeID is None: 1042 ↛ 1044line 1042 didn't jump to line 1044 because the condition on line 1042 was always true

1043 self._graph._edgesWithoutID.append(edge)

1044 elif edgeID not in self._graph._edgesWithID:

1045 self._graph._edgesWithID[edgeID] = edge

1046 else:

1047 raise DuplicateEdgeError(f"Edge ID '{edgeID}' already exists in this graph.")

1048 else:

1049 # TODO: keep _graph pointer in edge and then register edge on graph?

1050 if edgeID is None:

1051 self._subgraph._edgesWithoutID.append(edge)

1052 elif edgeID not in self._graph._edgesWithID:

1053 self._subgraph._edgesWithID[edgeID] = edge

1054 else:

1055 raise DuplicateEdgeError(f"Edge ID '{edgeID}' already exists in this graph.")

1056 else:

1057 # FIXME: needs an error message

1058 raise GraphException()

1059

1060 return edge

1061

1062 def LinkToVertex(

1063 self,

1064 vertex: 'Vertex',

1065 linkID: Nullable[EdgeIDType] = None,

1066 linkWeight: Nullable[EdgeWeightType] = None,

1067 linkValue: Nullable[VertexValueType] = None,

1068 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None,

1069 ) -> 'Link':

1070 """

1071 Create an outbound link from this vertex to the referenced vertex.

1072

1073 :param vertex: The vertex to be linked to.

1074 :param edgeID: The edge's optional ID for the new link object.

1075 :param edgeWeight: The edge's optional weight for the new link object.

1076 :param edgeValue: The edge's optional value for the new link object.

1077 :param keyValuePairs: An optional mapping (dictionary) of key-value-pairs for the new link object.

1078 :returns: The link object linking this vertex and the referenced vertex.

1079

1080 .. seealso::

1081

1082 :meth:`EdgeToVertex` |br|

1083 |rarr| Create an outbound edge from this vertex to the referenced vertex.

1084 :meth:`EdgeFromVertex` |br|

1085 |rarr| Create an inbound edge from the referenced vertex to this vertex.

1086 :meth:`EdgeToNewVertex` |br|

1087 |rarr| Create a new vertex and link that vertex by an outbound edge from this vertex.

1088 :meth:`EdgeFromNewVertex` |br|

1089 |rarr| Create a new vertex and link that vertex by an inbound edge to this vertex.

1090 :meth:`LinkFromVertex` |br|

1091 |rarr| Create an inbound link from the referenced vertex to this vertex.

1092

1093 .. todo:: GRAPH::Vertex::LinkToVertex Needs possible exceptions to be documented.

1094 """

1095 if self._subgraph is vertex._subgraph: 1095 ↛ 1097line 1095 didn't jump to line 1097 because the condition on line 1095 was never true

1096 # FIXME: needs an error message

1097 raise GraphException()

1098 else:

1099 link = Link(self, vertex, linkID, linkValue, linkWeight, keyValuePairs)

1100

1101 self._outboundLinks.append(link)

1102 vertex._inboundLinks.append(link)

1103

1104 if self._subgraph is None:

1105 # TODO: move into Edge?

1106 # TODO: keep _graph pointer in link and then register link on graph?

1107 if linkID is None: 1107 ↛ 1109line 1107 didn't jump to line 1109 because the condition on line 1107 was always true

1108 self._graph._linksWithoutID.append(link)

1109 elif linkID not in self._graph._linksWithID:

1110 self._graph._linksWithID[linkID] = link

1111 else:

1112 raise DuplicateEdgeError(f"Link ID '{linkID}' already exists in this graph.")

1113 else:

1114 # TODO: keep _graph pointer in link and then register link on graph?

1115 if linkID is None: 1115 ↛ 1118line 1115 didn't jump to line 1118 because the condition on line 1115 was always true

1116 self._subgraph._linksWithoutID.append(link)

1117 vertex._subgraph._linksWithoutID.append(link)

1118 elif linkID not in self._graph._linksWithID:

1119 self._subgraph._linksWithID[linkID] = link

1120 vertex._subgraph._linksWithID[linkID] = link

1121 else:

1122 raise DuplicateEdgeError(f"Link ID '{linkID}' already exists in this graph.")

1123

1124 return link

1125

1126 def LinkFromVertex(

1127 self,

1128 vertex: 'Vertex',

1129 linkID: Nullable[EdgeIDType] = None,

1130 linkWeight: Nullable[EdgeWeightType] = None,

1131 linkValue: Nullable[VertexValueType] = None,

1132 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None

1133 ) -> 'Edge':

1134 """

1135 Create an inbound link from the referenced vertex to this vertex.

1136

1137 :param vertex: The vertex to be linked from.

1138 :param edgeID: The edge's optional ID for the new link object.

1139 :param edgeWeight: The edge's optional weight for the new link object.

1140 :param edgeValue: The edge's optional value for the new link object.

1141 :param keyValuePairs: An optional mapping (dictionary) of key-value-pairs for the new link object.

1142 :returns: The link object linking the referenced vertex and this vertex.

1143

1144 .. seealso::

1145

1146 :meth:`EdgeToVertex` |br|

1147 |rarr| Create an outbound edge from this vertex to the referenced vertex.

1148 :meth:`EdgeFromVertex` |br|

1149 |rarr| Create an inbound edge from the referenced vertex to this vertex.

1150 :meth:`EdgeToNewVertex` |br|

1151 |rarr| Create a new vertex and link that vertex by an outbound edge from this vertex.

1152 :meth:`EdgeFromNewVertex` |br|

1153 |rarr| Create a new vertex and link that vertex by an inbound edge to this vertex.

1154 :meth:`LinkToVertex` |br|

1155 |rarr| Create an outbound link from this vertex to the referenced vertex.

1156

1157 .. todo:: GRAPH::Vertex::LinkFromVertex Needs possible exceptions to be documented.

1158 """

1159 if self._subgraph is vertex._subgraph: 1159 ↛ 1161line 1159 didn't jump to line 1161 because the condition on line 1159 was never true

1160 # FIXME: needs an error message

1161 raise GraphException()

1162 else:

1163 link = Link(vertex, self, linkID, linkValue, linkWeight, keyValuePairs)

1164

1165 vertex._outboundLinks.append(link)

1166 self._inboundLinks.append(link)

1167

1168 if self._subgraph is None: 1168 ↛ 1171line 1168 didn't jump to line 1171 because the condition on line 1168 was never true

1169 # TODO: move into Edge?

1170 # TODO: keep _graph pointer in link and then register link on graph?

1171 if linkID is None:

1172 self._graph._linksWithoutID.append(link)

1173 elif linkID not in self._graph._linksWithID:

1174 self._graph._linksWithID[linkID] = link

1175 else:

1176 raise DuplicateEdgeError(f"Link ID '{linkID}' already exists in this graph.")

1177 else:

1178 # TODO: keep _graph pointer in link and then register link on graph?

1179 if linkID is None: 1179 ↛ 1182line 1179 didn't jump to line 1182 because the condition on line 1179 was always true

1180 self._subgraph._linksWithoutID.append(link)

1181 vertex._subgraph._linksWithoutID.append(link)

1182 elif linkID not in self._graph._linksWithID:

1183 self._subgraph._linksWithID[linkID] = link

1184 vertex._subgraph._linksWithID[linkID] = link

1185 else:

1186 raise DuplicateEdgeError(f"Link ID '{linkID}' already exists in this graph.")

1187

1188 return link

1189

1190 def HasEdgeToDestination(self, destination: 'Vertex') -> bool:

1191 """

1192 Check if this vertex is linked to another vertex by any outbound edge.

1193

1194 :param destination: Destination vertex to check.

1195 :returns: ``True``, if the destination vertex is a destination on any outbound edge.

1196

1197 .. seealso::

1198

1199 :meth:`HasEdgeFromSource` |br|

1200 |rarr| Check if this vertex is linked to another vertex by any inbound edge.

1201 :meth:`HasLinkToDestination` |br|

1202 |rarr| Check if this vertex is linked to another vertex by any outbound link.

1203 :meth:`HasLinkFromSource` |br|

1204 |rarr| Check if this vertex is linked to another vertex by any inbound link.

1205 """

1206 for edge in self._outboundEdges:

1207 if destination is edge.Destination: 1207 ↛ 1206line 1207 didn't jump to line 1206 because the condition on line 1207 was always true

1208 return True

1209

1210 return False

1211

1212 def HasEdgeFromSource(self, source: 'Vertex') -> bool:

1213 """

1214 Check if this vertex is linked to another vertex by any inbound edge.

1215

1216 :param source: Source vertex to check.

1217 :returns: ``True``, if the source vertex is a source on any inbound edge.

1218

1219 .. seealso::

1220

1221 :meth:`HasEdgeToDestination` |br|

1222 |rarr| Check if this vertex is linked to another vertex by any outbound edge.

1223 :meth:`HasLinkToDestination` |br|

1224 |rarr| Check if this vertex is linked to another vertex by any outbound link.

1225 :meth:`HasLinkFromSource` |br|

1226 |rarr| Check if this vertex is linked to another vertex by any inbound link.

1227 """

1228 for edge in self._inboundEdges:

1229 if source is edge.Source: 1229 ↛ 1228line 1229 didn't jump to line 1228 because the condition on line 1229 was always true

1230 return True

1231

1232 return False

1233

1234 def HasLinkToDestination(self, destination: 'Vertex') -> bool:

1235 """

1236 Check if this vertex is linked to another vertex by any outbound link.

1237

1238 :param destination: Destination vertex to check.

1239 :returns: ``True``, if the destination vertex is a destination on any outbound link.

1240

1241 .. seealso::

1242

1243 :meth:`HasEdgeToDestination` |br|

1244 |rarr| Check if this vertex is linked to another vertex by any outbound edge.

1245 :meth:`HasEdgeFromSource` |br|

1246 |rarr| Check if this vertex is linked to another vertex by any inbound edge.

1247 :meth:`HasLinkFromSource` |br|

1248 |rarr| Check if this vertex is linked to another vertex by any inbound link.

1249 """

1250 for link in self._outboundLinks:

1251 if destination is link.Destination: 1251 ↛ 1250line 1251 didn't jump to line 1250 because the condition on line 1251 was always true

1252 return True

1253

1254 return False

1255

1256 def HasLinkFromSource(self, source: 'Vertex') -> bool:

1257 """

1258 Check if this vertex is linked to another vertex by any inbound link.

1259

1260 :param source: Source vertex to check.

1261 :returns: ``True``, if the source vertex is a source on any inbound link.

1262

1263 .. seealso::

1264

1265 :meth:`HasEdgeToDestination` |br|

1266 |rarr| Check if this vertex is linked to another vertex by any outbound edge.

1267 :meth:`HasEdgeFromSource` |br|

1268 |rarr| Check if this vertex is linked to another vertex by any inbound edge.

1269 :meth:`HasLinkToDestination` |br|

1270 |rarr| Check if this vertex is linked to another vertex by any outbound link.

1271 """

1272 for link in self._inboundLinks:

1273 if source is link.Source: 1273 ↛ 1272line 1273 didn't jump to line 1272 because the condition on line 1273 was always true

1274 return True

1275

1276 return False

1277

1278 def DeleteEdgeTo(self, destination: 'Vertex'):

1279 for edge in self._outboundEdges: 1279 ↛ 1283line 1279 didn't jump to line 1283 because the loop on line 1279 didn't complete

1280 if edge._destination is destination: 1280 ↛ 1279line 1280 didn't jump to line 1279 because the condition on line 1280 was always true

1281 break

1282 else:

1283 raise GraphException(f"No outbound edge found to '{destination!r}'.")

1284

1285 edge.Delete()

1286

1287 def DeleteEdgeFrom(self, source: 'Vertex'):

1288 for edge in self._inboundEdges:

1289 if edge._source is source:

1290 break

1291 else:

1292 raise GraphException(f"No inbound edge found to '{source!r}'.")

1293

1294 edge.Delete()

1295

1296 def DeleteLinkTo(self, destination: 'Vertex'):

1297 for link in self._outboundLinks:

1298 if link._destination is destination:

1299 break

1300 else:

1301 raise GraphException(f"No outbound link found to '{destination!r}'.")

1302

1303 link.Delete()

1304

1305 def DeleteLinkFrom(self, source: 'Vertex'):

1306 for link in self._inboundLinks:

1307 if link._source is source:

1308 break

1309 else:

1310 raise GraphException(f"No inbound link found to '{source!r}'.")

1311

1312 link.Delete()

1313

1314 def Copy(self, graph: Graph, copyDict: bool = False, linkingKeyToOriginalVertex: Nullable[str] = None, linkingKeyFromOriginalVertex: Nullable[str] = None) -> 'Vertex':

1315 """

1316 Creates a copy of this vertex in another graph.

1317

1318 Optionally, the vertex's attached attributes (key-value-pairs) can be copied and a linkage between both vertices

1319 can be established.

1320

1321 :param graph: The graph, the vertex is created in.

1322 :param copyDict: If ``True``, copy all attached attributes into the new vertex.

1323 :param linkingKeyToOriginalVertex: If not ``None``, add a key-value-pair using this parameter as key from new vertex to the original vertex.

1324 :param linkingKeyFromOriginalVertex: If not ``None``, add a key-value-pair using this parameter as key from original vertex to the new vertex.

1325 :returns: The newly created vertex.

1326 :raises GraphException: If source graph and destination graph are the same.

1327 """

1328 if graph is self._graph:

1329 raise GraphException("Graph to copy this vertex to, is the same graph.")

1330

1331 vertex = Vertex(self._id, self._value, self._weight, graph=graph)

1332 if copyDict:

1333 vertex._dict = self._dict.copy()

1334

1335 if linkingKeyToOriginalVertex is not None:

1336 vertex._dict[linkingKeyToOriginalVertex] = self

1337 if linkingKeyFromOriginalVertex is not None:

1338 self._dict[linkingKeyFromOriginalVertex] = vertex

1339

1340 return vertex

1341

1342 def IterateOutboundEdges(self, predicate: Nullable[Callable[['Edge'], bool]] = None) -> Generator['Edge', None, None]:

1343 """

1344 Iterate all or selected outbound edges of this vertex.

1345

1346 If parameter ``predicate`` is not None, the given filter function is used to skip edges in the generator.

1347

1348 :param predicate: Filter function accepting any edge and returning a boolean.

1349 :returns: A generator to iterate all outbound edges.

1350 """

1351 if predicate is None:

1352 for edge in self._outboundEdges:

1353 yield edge

1354 else:

1355 for edge in self._outboundEdges:

1356 if predicate(edge):

1357 yield edge

1358

1359 def IterateInboundEdges(self, predicate: Nullable[Callable[['Edge'], bool]] = None) -> Generator['Edge', None, None]:

1360 """

1361 Iterate all or selected inbound edges of this vertex.

1362

1363 If parameter ``predicate`` is not None, the given filter function is used to skip edges in the generator.

1364

1365 :param predicate: Filter function accepting any edge and returning a boolean.

1366 :returns: A generator to iterate all inbound edges.

1367 """

1368 if predicate is None:

1369 for edge in self._inboundEdges:

1370 yield edge

1371 else:

1372 for edge in self._inboundEdges:

1373 if predicate(edge):

1374 yield edge

1375

1376 def IterateOutboundLinks(self, predicate: Nullable[Callable[['Link'], bool]] = None) -> Generator['Link', None, None]:

1377 """

1378 Iterate all or selected outbound links of this vertex.

1379

1380 If parameter ``predicate`` is not None, the given filter function is used to skip links in the generator.

1381

1382 :param predicate: Filter function accepting any link and returning a boolean.

1383 :returns: A generator to iterate all outbound links.

1384 """

1385 if predicate is None:

1386 for link in self._outboundLinks:

1387 yield link

1388 else:

1389 for link in self._outboundLinks:

1390 if predicate(link):

1391 yield link

1392

1393 def IterateInboundLinks(self, predicate: Nullable[Callable[['Link'], bool]] = None) -> Generator['Link', None, None]:

1394 """

1395 Iterate all or selected inbound links of this vertex.

1396

1397 If parameter ``predicate`` is not None, the given filter function is used to skip links in the generator.

1398

1399 :param predicate: Filter function accepting any link and returning a boolean.

1400 :returns: A generator to iterate all inbound links.

1401 """

1402 if predicate is None:

1403 for link in self._inboundLinks:

1404 yield link

1405 else:

1406 for link in self._inboundLinks:

1407 if predicate(link):

1408 yield link

1409

1410 def IterateSuccessorVertices(self, predicate: Nullable[Callable[['Edge'], bool]] = None) -> Generator['Vertex', None, None]:

1411 """

1412 Iterate all or selected successor vertices of this vertex.

1413

1414 If parameter ``predicate`` is not None, the given filter function is used to skip successors in the generator.

1415

1416 :param predicate: Filter function accepting any edge and returning a boolean.

1417 :returns: A generator to iterate all successor vertices.

1418 """

1419 if predicate is None:

1420 for edge in self._outboundEdges:

1421 yield edge.Destination

1422 else:

1423 for edge in self._outboundEdges:

1424 if predicate(edge):

1425 yield edge.Destination

1426

1427 def IteratePredecessorVertices(self, predicate: Nullable[Callable[['Edge'], bool]] = None) -> Generator['Vertex', None, None]:

1428 """

1429 Iterate all or selected predecessor vertices of this vertex.

1430

1431 If parameter ``predicate`` is not None, the given filter function is used to skip predecessors in the generator.

1432

1433 :param predicate: Filter function accepting any edge and returning a boolean.

1434 :returns: A generator to iterate all predecessor vertices.

1435 """

1436 if predicate is None:

1437 for edge in self._inboundEdges:

1438 yield edge.Source

1439 else:

1440 for edge in self._inboundEdges:

1441 if predicate(edge):

1442 yield edge.Source

1443

1444 def IterateVerticesBFS(self) -> Generator['Vertex', None, None]:

1445 """

1446 A generator to iterate all reachable vertices starting from this node in breadth-first search (BFS) order.

1447

1448 :returns: A generator to iterate vertices traversed in BFS order.

1449

1450 .. seealso::

1451

1452 :meth:`IterateVerticesDFS` |br|

1453 |rarr| Iterate all reachable vertices **depth-first search** order.

1454 """

1455 visited: Set[Vertex] = set()

1456 queue: Deque[Vertex] = deque()

1457

1458 yield self

1459 visited.add(self)

1460 for edge in self._outboundEdges:

1461 nextVertex = edge.Destination

1462 if nextVertex is not self: 1462 ↛ 1460line 1462 didn't jump to line 1460 because the condition on line 1462 was always true

1463 queue.appendleft(nextVertex)

1464 visited.add(nextVertex)

1465

1466 while queue:

1467 vertex = queue.pop()

1468 yield vertex

1469 for edge in vertex._outboundEdges:

1470 nextVertex = edge.Destination

1471 if nextVertex not in visited:

1472 queue.appendleft(nextVertex)

1473 visited.add(nextVertex)

1474

1475 def IterateVerticesDFS(self) -> Generator['Vertex', None, None]:

1476 """

1477 A generator to iterate all reachable vertices starting from this node in depth-first search (DFS) order.

1478

1479 :returns: A generator to iterate vertices traversed in DFS order.

1480

1481 .. seealso::

1482

1483 :meth:`IterateVerticesBFS` |br|

1484 |rarr| Iterate all reachable vertices **breadth-first search** order.

1485

1486 Wikipedia - https://en.wikipedia.org/wiki/Depth-first_search

1487 """

1488 visited: Set[Vertex] = set()

1489 stack: List[typing_Iterator[Edge]] = list()

1490

1491 yield self

1492 visited.add(self)

1493 stack.append(iter(self._outboundEdges))

1494

1495 while True:

1496 try:

1497 edge = next(stack[-1])

1498 nextVertex = edge._destination

1499 if nextVertex not in visited:

1500 visited.add(nextVertex)

1501 yield nextVertex

1502 if len(nextVertex._outboundEdges) != 0:

1503 stack.append(iter(nextVertex._outboundEdges))

1504 except StopIteration:

1505 stack.pop()

1506

1507 if len(stack) == 0:

1508 return

1509

1510 def IterateAllOutboundPathsAsVertexList(self) -> Generator[Tuple['Vertex', ...], None, None]:

1511 if len(self._outboundEdges) == 0:

1512 yield (self, )

1513 return

1514

1515 visited: Set[Vertex] = set()

1516 vertexStack: List[Vertex] = list()

1517 iteratorStack: List[typing_Iterator[Edge]] = list()

1518

1519 visited.add(self)

1520 vertexStack.append(self)

1521 iteratorStack.append(iter(self._outboundEdges))

1522

1523 while True:

1524 try:

1525 edge = next(iteratorStack[-1])

1526 nextVertex = edge._destination

1527 if nextVertex in visited:

1528 ex = CycleError(f"Loop detected.")

1529 ex.add_note(f"First loop is:")

1530 for i, vertex in enumerate(vertexStack):

1531 ex.add_note(f" {i}: {vertex!r}")

1532 raise ex

1533

1534 vertexStack.append(nextVertex)

1535 if len(nextVertex._outboundEdges) == 0:

1536 yield tuple(vertexStack)

1537 vertexStack.pop()

1538 else:

1539 iteratorStack.append(iter(nextVertex._outboundEdges))

1540

1541 except StopIteration:

1542 vertexStack.pop()

1543 iteratorStack.pop()

1544

1545 if len(vertexStack) == 0:

1546 return

1547

1548 def ShortestPathToByHops(self, destination: 'Vertex') -> Generator['Vertex', None, None]:

1549 """

1550 Compute the shortest path (by hops) between this vertex and the destination vertex.

1551

1552 A generator is return to iterate all vertices along the path including source and destination vertex.

1553

1554 The search algorithm is breadth-first search (BFS) based. The found solution, if any, is not unique but deterministic

1555 as long as the graph was not modified (e.g. ordering of edges on vertices).

1556

1557 :param destination: The destination vertex to reach.

1558 :returns: A generator to iterate all vertices on the path found between this vertex and the destination vertex.

1559 """

1560 # Trivial case if start is destination

1561 if self is destination: 1561 ↛ 1562line 1561 didn't jump to line 1562 because the condition on line 1561 was never true

1562 yield self

1563 return

1564

1565 # Local struct to create multiple linked-lists forming a paths from current node back to the starting point

1566 # (actually a tree). Each node holds a reference to the vertex it represents.

1567 # Hint: slotted classes are faster than '@dataclasses.dataclass'.

1568 class Node(metaclass=ExtendedType, slots=True):

1569 parent: 'Node'

1570 ref: Vertex

1571

1572 def __init__(self, parent: 'Node', ref: Vertex) -> None:

1573 self.parent = parent

1574 self.ref = ref

1575

1576 def __str__(self):

1577 return f"Vertex: {self.ref.ID}"

1578

1579 # Initially add all reachable vertices to a queue if vertices to be processed.

1580 startNode = Node(None, self)

1581 visited: Set[Vertex] = set()

1582 queue: Deque[Node] = deque()

1583

1584 # Add starting vertex and all its children to the processing list.

1585 # If a child is the destination, break immediately else go into 'else' branch and use BFS algorithm.

1586 visited.add(self)

1587 for edge in self._outboundEdges:

1588 nextVertex = edge.Destination

1589 if nextVertex is destination: 1589 ↛ 1591line 1589 didn't jump to line 1591 because the condition on line 1589 was never true

1590 # Child is destination, so construct the last node for path traversal and break from loop.

1591 destinationNode = Node(startNode, nextVertex)

1592 break

1593 if nextVertex is not self: 1593 ↛ 1587line 1593 didn't jump to line 1587 because the condition on line 1593 was always true

1594 # Ignore backward-edges and side-edges.

1595 # Here self-edges, because there is only the starting vertex in the list of visited edges.

1596 visited.add(nextVertex)

1597 queue.appendleft(Node(startNode, nextVertex))

1598 else:

1599 # Process queue until destination is found or no further vertices are reachable.

1600 while queue:

1601 node = queue.pop()

1602 for edge in node.ref._outboundEdges:

1603 nextVertex = edge.Destination

1604 # Next reachable vertex is destination, so construct the last node for path traversal and break from loop.

1605 if nextVertex is destination:

1606 destinationNode = Node(node, nextVertex)

1607 break

1608 # Ignore backward-edges and side-edges.

1609 if nextVertex not in visited:

1610 visited.add(nextVertex)

1611 queue.appendleft(Node(node, nextVertex))

1612 # Next 3 lines realize a double-break if break was called in inner loop, otherwise continue with outer loop.

1613 else:

1614 continue

1615 break

1616 else:

1617 # All reachable vertices have been processed, but destination was not among them.

1618 raise DestinationNotReachable(f"Destination is not reachable.")

1619

1620 # Reverse order of linked list from destinationNode to startNode

1621 currentNode = destinationNode

1622 previousNode = destinationNode.parent

1623 currentNode.parent = None

1624 while previousNode is not None:

1625 node = previousNode.parent

1626 previousNode.parent = currentNode

1627 currentNode = previousNode

1628 previousNode = node

1629

1630 # Scan reversed linked-list and yield referenced vertices

1631 yield startNode.ref

1632 node = startNode.parent

1633 while node is not None:

1634 yield node.ref

1635 node = node.parent

1636

1637 def ShortestPathToByWeight(self, destination: 'Vertex') -> Generator['Vertex', None, None]:

1638 """

1639 Compute the shortest path (by edge weight) between this vertex and the destination vertex.

1640

1641 A generator is return to iterate all vertices along the path including source and destination vertex.

1642

1643 The search algorithm is based on Dijkstra algorithm and using :mod:`heapq`. The found solution, if any, is not

1644 unique but deterministic as long as the graph was not modified (e.g. ordering of edges on vertices).

1645

1646 :param destination: The destination vertex to reach.

1647 :returns: A generator to iterate all vertices on the path found between this vertex and the destination vertex.

1648 """

1649 # Improvements: both-sided Dijkstra (search from start and destination to reduce discovered area.

1650

1651 # Trivial case if start is destination

1652 if self is destination: 1652 ↛ 1653line 1652 didn't jump to line 1653 because the condition on line 1652 was never true

1653 yield self

1654 return

1655

1656 # Local struct to create multiple-linked lists forming a paths from current node back to the starting point

1657 # (actually a tree). Each node holds the overall weight from start to current node and a reference to the vertex it

1658 # represents.

1659 # Hint: slotted classes are faster than '@dataclasses.dataclass'.

1660 class Node(metaclass=ExtendedType, slots=True):

1661 parent: 'Node'

1662 distance: EdgeWeightType

1663 ref: Vertex

1664

1665 def __init__(self, parent: 'Node', distance: EdgeWeightType, ref: Vertex) -> None:

1666 self.parent = parent

1667 self.distance = distance

1668 self.ref = ref

1669

1670 def __lt__(self, other):

1671 return self.distance < other.distance

1672

1673 def __str__(self):

1674 return f"Vertex: {self.ref.ID}"

1675

1676 visited: Set['Vertex'] = set()

1677 startNode = Node(None, 0, self)

1678 priorityQueue = [startNode]

1679

1680 # Add starting vertex and all its children to the processing list.

1681 # If a child is the destination, break immediately else go into 'else' branch and use Dijkstra algorithm.

1682 visited.add(self)

1683 for edge in self._outboundEdges:

1684 nextVertex = edge.Destination

1685 # Child is destination, so construct the last node for path traversal and break from loop.

1686 if nextVertex is destination: 1686 ↛ 1687line 1686 didn't jump to line 1687 because the condition on line 1686 was never true

1687 destinationNode = Node(startNode, edge._weight, nextVertex)

1688 break

1689 # Ignore backward-edges and side-edges.

1690 # Here self-edges, because there is only the starting vertex in the list of visited edges.

1691 if nextVertex is not self: 1691 ↛ 1683line 1691 didn't jump to line 1683 because the condition on line 1691 was always true

1692 visited.add(nextVertex)

1693 heapq.heappush(priorityQueue, Node(startNode, edge._weight, nextVertex))

1694 else:

1695 # Process priority queue until destination is found or no further vertices are reachable.

1696 while priorityQueue: 1696 ↛ 1714line 1696 didn't jump to line 1714 because the condition on line 1696 was always true

1697 node = heapq.heappop(priorityQueue)

1698 for edge in node.ref._outboundEdges:

1699 nextVertex = edge.Destination

1700 # Next reachable vertex is destination, so construct the last node for path traversal and break from loop.

1701 if nextVertex is destination:

1702 destinationNode = Node(node, node.distance + edge._weight, nextVertex)

1703 break

1704 # Ignore backward-edges and side-edges.

1705 if nextVertex not in visited:

1706 visited.add(nextVertex)

1707 heapq.heappush(priorityQueue, Node(node, node.distance + edge._weight, nextVertex))

1708 # Next 3 lines realize a double-break if break was called in inner loop, otherwise continue with outer loop.

1709 else:

1710 continue

1711 break

1712 else:

1713 # All reachable vertices have been processed, but destination was not among them.

1714 raise DestinationNotReachable(f"Destination is not reachable.")

1715

1716 # Reverse order of linked-list from destinationNode to startNode

1717 currentNode = destinationNode

1718 previousNode = destinationNode.parent

1719 currentNode.parent = None

1720 while previousNode is not None:

1721 node = previousNode.parent

1722 previousNode.parent = currentNode

1723 currentNode = previousNode

1724 previousNode = node

1725

1726 # Scan reversed linked-list and yield referenced vertices

1727 yield startNode.ref, startNode.distance

1728 node = startNode.parent

1729 while node is not None:

1730 yield node.ref, node.distance

1731 node = node.parent

1732

1733 # Other possible algorithms:

1734 # * Bellman-Ford

1735 # * Floyd-Warshall

1736

1737 # def PathExistsTo(self, destination: 'Vertex'):

1738 # raise NotImplementedError()

1739 # # DFS

1740 # # Union find

1741 #

1742 # def MaximumFlowTo(self, destination: 'Vertex'):

1743 # raise NotImplementedError()

1744 # # Ford-Fulkerson algorithm

1745 # # Edmons-Karp algorithm

1746 # # Dinic's algorithm

1747

1748 def ConvertToTree(self) -> Node:

1749 """

1750 Converts all reachable vertices from this starting vertex to a tree of :class:`~pyTooling.Tree.Node` instances.

1751

1752 The tree is traversed using depths-first-search.

1753

1754 :returns:

1755 """

1756 visited: Set[Vertex] = set()

1757 stack: List[Tuple[Node, typing_Iterator[Edge]]] = list()

1758

1759 root = Node(nodeID=self._id, value=self._value)

1760 root._dict = self._dict.copy()

1761

1762 visited.add(self)

1763 stack.append((root, iter(self._outboundEdges)))

1764

1765 while True:

1766 try:

1767 edge = next(stack[-1][1])

1768 nextVertex = edge._destination

1769 if nextVertex not in visited: 1769 ↛ 1775line 1769 didn't jump to line 1775 because the condition on line 1769 was always true

1770 node = Node(nextVertex._id, nextVertex._value, parent=stack[-1][0])

1771 visited.add(nextVertex)

1772 if len(nextVertex._outboundEdges) != 0:

1773 stack.append((node, iter(nextVertex._outboundEdges)))

1774 else:

1775 raise NotATreeError(f"The directed subgraph is not a tree.")

1776 # TODO: compute cycle:

1777 # a) branch 1 is described in stack

1778 # b) branch 2 can be found by walking from joint to root in the tree

1779 except StopIteration:

1780 stack.pop()

1781

1782 if len(stack) == 0:

1783 return root

1784

1785 def __repr__(self) -> str:

1786 """

1787 Returns a detailed string representation of the vertex.

1788

1789 :returns: The detailed string representation of the vertex.

1790 """

1791 vertexID = value = ""

1792 sep = ": "

1793 if self._id is not None:

1794 vertexID = f"{sep}vertexID='{self._id}'"

1795 sep = "; "

1796 if self._value is not None: 1796 ↛ 1797line 1796 didn't jump to line 1797 because the condition on line 1796 was never true

1797 value = f"{sep}value='{self._value}'"

1798

1799 return f"<vertex{vertexID}{value}>"

1800

1801 def __str__(self) -> str:

1802 """

1803 Return a string representation of the vertex.

1804

1805 Order of resolution:

1806

1807 1. If :attr:`_value` is not None, return the string representation of :attr:`_value`.

1808 2. If :attr:`_id` is not None, return the string representation of :attr:`_id`.

1809 3. Else, return :meth:`__repr__`.

1810

1811 :returns: The resolved string representation of the vertex.

1812 """

1813 if self._value is not None: 1813 ↛ 1814line 1813 didn't jump to line 1814 because the condition on line 1813 was never true

1814 return str(self._value)

1815 elif self._id is not None: 1815 ↛ 1816line 1815 didn't jump to line 1816 because the condition on line 1815 was never true

1816 return str(self._id)

1817 else:

1818 return self.__repr__()

1819

1820

1821@export

1822class BaseEdge(

1823 BaseWithIDValueAndWeight[EdgeIDType, EdgeValueType, EdgeWeightType, EdgeDictKeyType, EdgeDictValueType],

1824 Generic[EdgeIDType, EdgeValueType, EdgeWeightType, EdgeDictKeyType, EdgeDictValueType]

1825):

1826 """

1827 An **edge** can have a unique ID, a value, a weight and attached meta information as key-value-pairs. All edges are

1828 directed.

1829 """

1830 _source: Vertex

1831 _destination: Vertex

1832

1833 def __init__(

1834 self,

1835 source: Vertex,

1836 destination: Vertex,

1837 edgeID: Nullable[EdgeIDType] = None,

1838 value: Nullable[EdgeValueType] = None,

1839 weight: Nullable[EdgeWeightType] = None,

1840 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None

1841 ) -> None:

1842 """

1843 .. todo:: GRAPH::BaseEdge::init Needs documentation.

1844

1845 :param source: The source of the new edge.

1846 :param destination: The destination of the new edge.

1847 :param edgeID: The optional unique ID for the new edge.

1848 :param value: The optional value for the new edge.

1849 :param weight: The optional weight for the new edge.

1850 :param keyValuePairs: The optional mapping (dictionary) of key-value-pairs.

1851 """

1852 super().__init__(edgeID, value, weight, keyValuePairs)

1853

1854 self._source = source

1855 self._destination = destination

1856

1857 component = source._component

1858 if component is not destination._component:

1859 # TODO: should it be divided into with/without ID?

1860 oldComponent = destination._component

1861 for vertex in oldComponent._vertices:

1862 vertex._component = component

1863 component._vertices.add(vertex)

1864 component._graph._components.remove(oldComponent)

1865 del oldComponent

1866

1867 @readonly

1868 def Source(self) -> Vertex:

1869 """

1870 Read-only property to get the source (:attr:`_source`) of an edge.

1871

1872 :returns: The source of an edge.

1873 """

1874 return self._source

1875

1876 @readonly

1877 def Destination(self) -> Vertex:

1878 """

1879 Read-only property to get the destination (:attr:`_destination`) of an edge.

1880

1881 :returns: The destination of an edge.

1882 """

1883 return self._destination

1884

1885 def Reverse(self) -> None:

1886 """Reverse the direction of this edge."""

1887 swap = self._source

1888 self._source = self._destination

1889 self._destination = swap

1890

1891

1892@export

1893class Edge(

1894 BaseEdge[EdgeIDType, EdgeValueType, EdgeWeightType, EdgeDictKeyType, EdgeDictValueType],

1895 Generic[EdgeIDType, EdgeValueType, EdgeWeightType, EdgeDictKeyType, EdgeDictValueType]

1896):

1897 """

1898 An **edge** can have a unique ID, a value, a weight and attached meta information as key-value-pairs. All edges are

1899 directed.

1900 """

1901

1902 def __init__(

1903 self,

1904 source: Vertex,

1905 destination: Vertex,

1906 edgeID: Nullable[EdgeIDType] = None,

1907 value: Nullable[EdgeValueType] = None,

1908 weight: Nullable[EdgeWeightType] = None,

1909 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None

1910 ) -> None:

1911 """

1912 .. todo:: GRAPH::Edge::init Needs documentation.

1913

1914 :param source: The source of the new edge.

1915 :param destination: The destination of the new edge.

1916 :param edgeID: The optional unique ID for the new edge.

1917 :param value: The optional value for the new edge.

1918 :param weight: The optional weight for the new edge.

1919 :param keyValuePairs: The optional mapping (dictionary) of key-value-pairs.

1920 """

1921 if not isinstance(source, Vertex):

1922 ex = TypeError("Parameter 'source' is not of type 'Vertex'.")

1923 if version_info >= (3, 11): # pragma: no cover

1924 ex.add_note(f"Got type '{getFullyQualifiedName(source)}'.")

1925 raise ex

1926 if not isinstance(destination, Vertex):

1927 ex = TypeError("Parameter 'destination' is not of type 'Vertex'.")

1928 if version_info >= (3, 11): # pragma: no cover

1929 ex.add_note(f"Got type '{getFullyQualifiedName(destination)}'.")

1930 raise ex

1931 if edgeID is not None and not isinstance(edgeID, Hashable):

1932 ex = TypeError("Parameter 'edgeID' is not of type 'EdgeIDType'.")

1933 if version_info >= (3, 11): # pragma: no cover

1934 ex.add_note(f"Got type '{getFullyQualifiedName(edgeID)}'.")

1935 raise ex

1936 # if value is not None and not isinstance(value, Vertex):

1937 # raise TypeError("Parameter 'value' is not of type 'EdgeValueType'.")

1938 if weight is not None and not isinstance(weight, (int, float)):

1939 ex = TypeError("Parameter 'weight' is not of type 'EdgeWeightType'.")

1940 if version_info >= (3, 11): # pragma: no cover

1941 ex.add_note(f"Got type '{getFullyQualifiedName(weight)}'.")

1942 raise ex

1943 if source._graph is not destination._graph:

1944 raise NotInSameGraph(f"Source vertex and destination vertex are not in same graph.")

1945

1946 super().__init__(source, destination, edgeID, value, weight, keyValuePairs)

1947

1948 def Delete(self) -> None:

1949 # Remove from Source and Destination

1950 self._source._outboundEdges.remove(self)

1951 self._destination._inboundEdges.remove(self)

1952

1953 # Remove from Graph and Subgraph

1954 if self._id is None: 1954 ↛ 1959line 1954 didn't jump to line 1959 because the condition on line 1954 was always true

1955 self._source._graph._edgesWithoutID.remove(self)

1956 if self._source._subgraph is not None: 1956 ↛ 1957line 1956 didn't jump to line 1957 because the condition on line 1956 was never true

1957 self._source._subgraph._edgesWithoutID.remove(self)

1958 else:

1959 del self._source._graph._edgesWithID[self._id]

1960 if self._source._subgraph is not None:

1961 del self._source._subgraph._edgesWithID[self]

1962

1963 self._Delete()

1964

1965 def _Delete(self) -> None:

1966 super().Delete()

1967

1968 def Reverse(self) -> None:

1969 """Reverse the direction of this edge."""

1970 self._source._outboundEdges.remove(self)

1971 self._source._inboundEdges.append(self)

1972 self._destination._inboundEdges.remove(self)

1973 self._destination._outboundEdges.append(self)

1974

1975 super().Reverse()

1976

1977

1978@export

1979class Link(

1980 BaseEdge[LinkIDType, LinkValueType, LinkWeightType, LinkDictKeyType, LinkDictValueType],

1981 Generic[LinkIDType, LinkValueType, LinkWeightType, LinkDictKeyType, LinkDictValueType]

1982):

1983 """

1984 A **link** can have a unique ID, a value, a weight and attached meta information as key-value-pairs. All links are

1985 directed.

1986 """

1987

1988 def __init__(

1989 self,

1990 source: Vertex,

1991 destination: Vertex,

1992 linkID: LinkIDType = None,

1993 value: LinkValueType = None,

1994 weight: Nullable[LinkWeightType] = None,

1995 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None

1996 ) -> None:

1997 """

1998 .. todo:: GRAPH::Edge::init Needs documentation.

1999

2000 :param source: The source of the new link.

2001 :param destination: The destination of the new link.

2002 :param linkID: The optional unique ID for the new link.

2003 :param value: The optional value for the new v.

2004 :param weight: The optional weight for the new link.

2005 :param keyValuePairs: The optional mapping (dictionary) of key-value-pairs.

2006 """

2007 if not isinstance(source, Vertex):

2008 ex = TypeError("Parameter 'source' is not of type 'Vertex'.")

2009 if version_info >= (3, 11): # pragma: no cover

2010 ex.add_note(f"Got type '{getFullyQualifiedName(source)}'.")

2011 raise ex

2012 if not isinstance(destination, Vertex):

2013 ex = TypeError("Parameter 'destination' is not of type 'Vertex'.")

2014 if version_info >= (3, 11): # pragma: no cover

2015 ex.add_note(f"Got type '{getFullyQualifiedName(destination)}'.")

2016 raise ex

2017 if linkID is not None and not isinstance(linkID, Hashable):

2018 ex = TypeError("Parameter 'linkID' is not of type 'LinkIDType'.")

2019 if version_info >= (3, 11): # pragma: no cover

2020 ex.add_note(f"Got type '{getFullyQualifiedName(linkID)}'.")

2021 raise ex

2022 # if value is not None and not isinstance(value, Vertex):

2023 # raise TypeError("Parameter 'value' is not of type 'EdgeValueType'.")

2024 if weight is not None and not isinstance(weight, (int, float)):

2025 ex = TypeError("Parameter 'weight' is not of type 'EdgeWeightType'.")

2026 if version_info >= (3, 11): # pragma: no cover

2027 ex.add_note(f"Got type '{getFullyQualifiedName(weight)}'.")

2028 raise ex

2029 if source._graph is not destination._graph:

2030 raise NotInSameGraph(f"Source vertex and destination vertex are not in same graph.")

2031

2032 super().__init__(source, destination, linkID, value, weight, keyValuePairs)

2033

2034 def Delete(self) -> None:

2035 self._source._outboundEdges.remove(self)

2036 self._destination._inboundEdges.remove(self)

2037

2038 if self._id is None:

2039 self._source._graph._linksWithoutID.remove(self)

2040 else:

2041 del self._source._graph._linksWithID[self._id]

2042

2043 self._Delete()

2044 assert getrefcount(self) == 1

2045

2046 def _Delete(self) -> None:

2047 super().Delete()

2048

2049 def Reverse(self) -> None:

2050 """Reverse the direction of this link."""

2051 self._source._outboundEdges.remove(self)

2052 self._source._inboundEdges.append(self)

2053 self._destination._inboundEdges.remove(self)

2054 self._destination._outboundEdges.append(self)

2055

2056 super().Reverse()

2057

2058

2059@export

2060class BaseGraph(

2061 BaseWithName[GraphDictKeyType, GraphDictValueType],

2062 Generic[

2063 GraphDictKeyType, GraphDictValueType,

2064 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,

2065 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,

2066 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType

2067 ]

2068):

2069 """

2070 .. todo:: GRAPH::BaseGraph Needs documentation.

2071

2072 """

2073

2074 _verticesWithID: Dict[VertexIDType, Vertex[GraphDictKeyType, GraphDictValueType, VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType, EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType, LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType]]

2075 _verticesWithoutID: List[Vertex[GraphDictKeyType, GraphDictValueType, VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType, EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType, LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType]]

2076 _edgesWithID: Dict[EdgeIDType, Edge[EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType]]

2077 _edgesWithoutID: List[Edge[EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType]]

2078 _linksWithID: Dict[EdgeIDType, Link[LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType]]

2079 _linksWithoutID: List[Link[LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType]]

2080

2081 def __init__(

2082 self,

2083 name: Nullable[str] = None,

2084 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None

2085 #, vertices: Nullable[Iterable[Vertex]] = None) -> None:

2086 ):

2087 """

2088 .. todo:: GRAPH::BaseGraph::init Needs documentation.

2089

2090 :param name: The optional name of the graph.

2091 :param keyValuePairs: The optional mapping (dictionary) of key-value-pairs.

2092 """

2093 super().__init__(name, keyValuePairs)

2094

2095 self._verticesWithoutID = []

2096 self._verticesWithID = {}

2097 self._edgesWithoutID = []

2098 self._edgesWithID = {}

2099 self._linksWithoutID = []

2100 self._linksWithID = {}

2101

2102 def __del__(self):

2103 """

2104 .. todo:: GRAPH::BaseGraph::del Needs documentation.

2105

2106 """

2107 try:

2108 del self._verticesWithoutID

2109 del self._verticesWithID

2110 del self._edgesWithoutID

2111 del self._edgesWithID

2112 del self._linksWithoutID

2113 del self._linksWithID

2114 except AttributeError:

2115 pass

2116

2117 super().__del__()

2118

2119 @readonly

2120 def VertexCount(self) -> int:

2121 """Read-only property to access the number of vertices in this graph.

2122

2123 :returns: The number of vertices in this graph."""

2124 return len(self._verticesWithoutID) + len(self._verticesWithID)

2125

2126 @readonly

2127 def EdgeCount(self) -> int:

2128 """Read-only property to access the number of edges in this graph.

2129

2130 :returns: The number of edges in this graph."""

2131 return len(self._edgesWithoutID) + len(self._edgesWithID)

2132

2133 @readonly

2134 def LinkCount(self) -> int:

2135 """Read-only property to access the number of links in this graph.

2136

2137 :returns: The number of links in this graph."""

2138 return len(self._linksWithoutID) + len(self._linksWithID)

2139

2140 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]:

2141 """

2142 Iterate all or selected vertices of a graph.

2143

2144 If parameter ``predicate`` is not None, the given filter function is used to skip vertices in the generator.

2145

2146 :param predicate: Filter function accepting any vertex and returning a boolean.

2147 :returns: A generator to iterate all vertices.

2148 """

2149 if predicate is None:

2150 yield from self._verticesWithoutID

2151 yield from self._verticesWithID.values()

2152

2153 else:

2154 for vertex in self._verticesWithoutID:

2155 if predicate(vertex):

2156 yield vertex

2157

2158 for vertex in self._verticesWithID.values():

2159 if predicate(vertex):

2160 yield vertex

2161

2162 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]:

2163 """

2164 Iterate all or selected roots (vertices without inbound edges / without predecessors) of a graph.

2165

2166 If parameter ``predicate`` is not None, the given filter function is used to skip vertices in the generator.

2167

2168 :param predicate: Filter function accepting any vertex and returning a boolean.

2169 :returns: A generator to iterate all vertices without inbound edges.

2170

2171 .. seealso::

2172

2173 :meth:`IterateLeafs` |br|

2174 |rarr| Iterate leafs of a graph.

2175 :meth:`Vertex.IsRoot <pyTooling.Graph.Vertex.IsRoot>` |br|

2176 |rarr| Check if a vertex is a root vertex in the graph.

2177 :meth:`Vertex.IsLeaf <pyTooling.Graph.Vertex.IsLeaf>` |br|

2178 |rarr| Check if a vertex is a leaf vertex in the graph.

2179 """

2180 if predicate is None:

2181 for vertex in self._verticesWithoutID:

2182 if len(vertex._inboundEdges) == 0:

2183 yield vertex

2184

2185 for vertex in self._verticesWithID.values(): 2185 ↛ 2186line 2185 didn't jump to line 2186 because the loop on line 2185 never started

2186 if len(vertex._inboundEdges) == 0:

2187 yield vertex

2188 else:

2189 for vertex in self._verticesWithoutID:

2190 if len(vertex._inboundEdges) == 0 and predicate(vertex):

2191 yield vertex

2192

2193 for vertex in self._verticesWithID.values(): 2193 ↛ 2194line 2193 didn't jump to line 2194 because the loop on line 2193 never started

2194 if len(vertex._inboundEdges) == 0 and predicate(vertex):

2195 yield vertex

2196

2197 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]:

2198 """

2199 Iterate all or selected leafs (vertices without outbound edges / without successors) of a graph.

2200

2201 If parameter ``predicate`` is not None, the given filter function is used to skip vertices in the generator.

2202

2203 :param predicate: Filter function accepting any vertex and returning a boolean.

2204 :returns: A generator to iterate all vertices without outbound edges.

2205

2206 .. seealso::

2207

2208 :meth:`IterateRoots` |br|

2209 |rarr| Iterate roots of a graph.

2210 :meth:`Vertex.IsRoot <pyTooling.Graph.Vertex.IsRoot>` |br|

2211 |rarr| Check if a vertex is a root vertex in the graph.

2212 :meth:`Vertex.IsLeaf <pyTooling.Graph.Vertex.IsLeaf>` |br|

2213 |rarr| Check if a vertex is a leaf vertex in the graph.

2214 """

2215 if predicate is None:

2216 for vertex in self._verticesWithoutID:

2217 if len(vertex._outboundEdges) == 0:

2218 yield vertex

2219

2220 for vertex in self._verticesWithID.values():

2221 if len(vertex._outboundEdges) == 0:

2222 yield vertex

2223 else:

2224 for vertex in self._verticesWithoutID:

2225 if len(vertex._outboundEdges) == 0 and predicate(vertex):

2226 yield vertex

2227

2228 for vertex in self._verticesWithID.values():

2229 if len(vertex._outboundEdges) == 0 and predicate(vertex): 2229 ↛ 2230line 2229 didn't jump to line 2230 because the condition on line 2229 was never true

2230 yield vertex

2231

2232 # 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]:

2233 # raise NotImplementedError()

2234 #

2235 # 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]:

2236 # raise NotImplementedError()

2237

2238 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]:

2239 """

2240 Iterate all or selected vertices in topological order.

2241

2242 If parameter ``predicate`` is not None, the given filter function is used to skip vertices in the generator.

2243

2244 :param predicate: Filter function accepting any vertex and returning a boolean.

2245 :returns: A generator to iterate all vertices in topological order.

2246 :except CycleError: Raised if graph is cyclic, thus topological sorting isn't possible.

2247 """

2248 outboundEdgeCounts = {}

2249 leafVertices = []

2250

2251 for vertex in self._verticesWithoutID:

2252 if (count := len(vertex._outboundEdges)) == 0:

2253 leafVertices.append(vertex)

2254 else:

2255 outboundEdgeCounts[vertex] = count

2256

2257 for vertex in self._verticesWithID.values():

2258 if (count := len(vertex._outboundEdges)) == 0:

2259 leafVertices.append(vertex)

2260 else:

2261 outboundEdgeCounts[vertex] = count

2262

2263 if not leafVertices: 2263 ↛ 2264line 2263 didn't jump to line 2264 because the condition on line 2263 was never true

2264 raise CycleError(f"Graph has no leafs. Thus, no topological sorting exists.")

2265

2266 overallCount = len(outboundEdgeCounts) + len(leafVertices)

2267

2268 def removeVertex(vertex: Vertex):

2269 nonlocal overallCount

2270 overallCount -= 1

2271 for inboundEdge in vertex._inboundEdges:

2272 sourceVertex = inboundEdge.Source

2273 count = outboundEdgeCounts[sourceVertex] - 1

2274 outboundEdgeCounts[sourceVertex] = count

2275 if count == 0:

2276 leafVertices.append(sourceVertex)

2277

2278 if predicate is None:

2279 for vertex in leafVertices:

2280 yield vertex

2281

2282 removeVertex(vertex)

2283 else:

2284 for vertex in leafVertices:

2285 if predicate(vertex):

2286 yield vertex

2287

2288 removeVertex(vertex)

2289

2290 if overallCount == 0: 2290 ↛ 2292line 2290 didn't jump to line 2292 because the condition on line 2290 was always true

2291 return

2292 elif overallCount > 0:

2293 raise CycleError(f"Graph has remaining vertices. Thus, the graph has at least one cycle.")

2294

2295 raise InternalError(f"Graph data structure is corrupted.") # pragma: no cover

2296

2297 def IterateEdges(self, predicate: Nullable[Callable[[Edge], bool]] = None) -> Generator[Edge[EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType], None, None]:

2298 """

2299 Iterate all or selected edges of a graph.

2300

2301 If parameter ``predicate`` is not None, the given filter function is used to skip edges in the generator.

2302

2303 :param predicate: Filter function accepting any edge and returning a boolean.

2304 :returns: A generator to iterate all edges.

2305 """

2306 if predicate is None:

2307 yield from self._edgesWithoutID

2308 yield from self._edgesWithID.values()

2309

2310 else:

2311 for edge in self._edgesWithoutID:

2312 if predicate(edge):

2313 yield edge

2314

2315 for edge in self._edgesWithID.values():

2316 if predicate(edge):

2317 yield edge

2318

2319 def IterateLinks(self, predicate: Nullable[Callable[[Link], bool]] = None) -> Generator[Link[LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType], None, None]:

2320 """

2321 Iterate all or selected links of a graph.

2322

2323 If parameter ``predicate`` is not None, the given filter function is used to skip links in the generator.

2324

2325 :param predicate: Filter function accepting any link and returning a boolean.

2326 :returns: A generator to iterate all links.

2327 """

2328 if predicate is None: 2328 ↛ 2333line 2328 didn't jump to line 2333 because the condition on line 2328 was always true

2329 yield from self._linksWithoutID

2330 yield from self._linksWithID.values()

2331

2332 else:

2333 for link in self._linksWithoutID:

2334 if predicate(link):

2335 yield link

2336

2337 for link in self._linksWithID.values():

2338 if predicate(link):

2339 yield link

2340

2341 def ReverseEdges(self, predicate: Nullable[Callable[[Edge], bool]] = None) -> None:

2342 """

2343 Reverse all or selected edges of a graph.

2344

2345 If parameter ``predicate`` is not None, the given filter function is used to skip edges.

2346

2347 :param predicate: Filter function accepting any edge and returning a boolean.

2348 """

2349 if predicate is None:

2350 for edge in self._edgesWithoutID:

2351 swap = edge._source

2352 edge._source = edge._destination

2353 edge._destination = swap

2354

2355 for edge in self._edgesWithID.values():

2356 swap = edge._source

2357 edge._source = edge._destination

2358 edge._destination = swap

2359

2360 for vertex in self._verticesWithoutID:

2361 swap = vertex._inboundEdges

2362 vertex._inboundEdges = vertex._outboundEdges

2363 vertex._outboundEdges = swap

2364

2365 for vertex in self._verticesWithID.values():

2366 swap = vertex._inboundEdges

2367 vertex._inboundEdges = vertex._outboundEdges

2368 vertex._outboundEdges = swap

2369 else:

2370 for edge in self._edgesWithoutID:

2371 if predicate(edge):

2372 edge.Reverse()

2373

2374 for edge in self._edgesWithID.values():

2375 if predicate(edge):

2376 edge.Reverse()

2377

2378 def ReverseLinks(self, predicate: Nullable[Callable[[Link], bool]] = None) -> None:

2379 """

2380 Reverse all or selected links of a graph.

2381

2382 If parameter ``predicate`` is not None, the given filter function is used to skip links.

2383

2384 :param predicate: Filter function accepting any link and returning a boolean.

2385 """

2386 if predicate is None:

2387 for link in self._linksWithoutID:

2388 swap = link._source

2389 link._source = link._destination

2390 link._destination = swap

2391

2392 for link in self._linksWithID.values():

2393 swap = link._source

2394 link._source = link._destination

2395 link._destination = swap

2396

2397 for vertex in self._verticesWithoutID:

2398 swap = vertex._inboundLinks

2399 vertex._inboundLinks = vertex._outboundLinks

2400 vertex._outboundLinks = swap

2401

2402 for vertex in self._verticesWithID.values():

2403 swap = vertex._inboundLinks

2404 vertex._inboundLinks = vertex._outboundLinks

2405 vertex._outboundLinks = swap

2406 else:

2407 for link in self._linksWithoutID:

2408 if predicate(link):

2409 link.Reverse()

2410

2411 for link in self._linksWithID.values():

2412 if predicate(link):

2413 link.Reverse()

2414

2415 def RemoveEdges(self, predicate: Nullable[Callable[[Edge], bool]] = None):

2416 """

2417 Remove all or selected edges of a graph.

2418

2419 If parameter ``predicate`` is not None, the given filter function is used to skip edges.

2420

2421 :param predicate: Filter function accepting any edge and returning a boolean.

2422 """

2423 if predicate is None:

2424 for edge in self._edgesWithoutID:

2425 edge._Delete()

2426

2427 for edge in self._edgesWithID.values():

2428 edge._Delete()

2429

2430 self._edgesWithoutID = []

2431 self._edgesWithID = {}

2432

2433 for vertex in self._verticesWithoutID:

2434 vertex._inboundEdges = []

2435 vertex._outboundEdges = []

2436

2437 for vertex in self._verticesWithID.values():

2438 vertex._inboundEdges = []

2439 vertex._outboundEdges = []

2440

2441 else:

2442 delEdges = [edge for edge in self._edgesWithID.values() if predicate(edge)]

2443 for edge in delEdges:

2444 del self._edgesWithID[edge._id]

2445

2446 edge._source._outboundEdges.remove(edge)

2447 edge._destination._inboundEdges.remove(edge)

2448 edge._Delete()

2449

2450 for edge in self._edgesWithoutID:

2451 if predicate(edge):

2452 self._edgesWithoutID.remove(edge)

2453

2454 edge._source._outboundEdges.remove(edge)

2455 edge._destination._inboundEdges.remove(edge)

2456 edge._Delete()

2457

2458 def RemoveLinks(self, predicate: Nullable[Callable[[Link], bool]] = None):

2459 """

2460 Remove all or selected links of a graph.

2461

2462 If parameter ``predicate`` is not None, the given filter function is used to skip links.

2463

2464 :param predicate: Filter function accepting any link and returning a boolean.

2465 """

2466 if predicate is None:

2467 for link in self._linksWithoutID:

2468 link._Delete()

2469

2470 for link in self._linksWithID.values():

2471 link._Delete()

2472

2473 self._linksWithoutID = []

2474 self._linksWithID = {}

2475

2476 for vertex in self._verticesWithoutID:

2477 vertex._inboundLinks = []

2478 vertex._outboundLinks = []

2479

2480 for vertex in self._verticesWithID.values():

2481 vertex._inboundLinks = []

2482 vertex._outboundLinks = []

2483

2484 else:

2485 delLinks = [link for link in self._linksWithID.values() if predicate(link)]

2486 for link in delLinks:

2487 del self._linksWithID[link._id]

2488

2489 link._source._outboundLinks.remove(link)

2490 link._destination._inboundLinks.remove(link)

2491 link._Delete()

2492

2493 for link in self._linksWithoutID:

2494 if predicate(link):

2495 self._linksWithoutID.remove(link)

2496

2497 link._source._outboundLinks.remove(link)

2498 link._destination._inboundLinks.remove(link)

2499 link._Delete()

2500

2501 def HasCycle(self) -> bool:

2502 """

2503 .. todo:: GRAPH::BaseGraph::HasCycle Needs documentation.

2504

2505 """

2506 # IsAcyclic ?

2507

2508 # Handle trivial case if graph is empty

2509 if len(self._verticesWithID) + len(self._verticesWithoutID) == 0: 2509 ↛ 2510line 2509 didn't jump to line 2510 because the condition on line 2509 was never true

2510 return False

2511

2512 outboundEdgeCounts = {}

2513 leafVertices = []

2514

2515 for vertex in self._verticesWithoutID:

2516 if (count := len(vertex._outboundEdges)) == 0:

2517 leafVertices.append(vertex)

2518 else:

2519 outboundEdgeCounts[vertex] = count

2520

2521 for vertex in self._verticesWithID.values():

2522 if (count := len(vertex._outboundEdges)) == 0:

2523 leafVertices.append(vertex)

2524 else:

2525 outboundEdgeCounts[vertex] = count

2526

2527 # If there are no leafs, then each vertex has at least one inbound and one outbound edges. Thus, there is a cycle.

2528 if not leafVertices: 2528 ↛ 2529line 2528 didn't jump to line 2529 because the condition on line 2528 was never true

2529 return True

2530

2531 overallCount = len(outboundEdgeCounts) + len(leafVertices)

2532

2533 for vertex in leafVertices:

2534 overallCount -= 1

2535 for inboundEdge in vertex._inboundEdges:

2536 sourceVertex = inboundEdge.Source

2537 count = outboundEdgeCounts[sourceVertex] - 1

2538 outboundEdgeCounts[sourceVertex] = count

2539 if count == 0:

2540 leafVertices.append(sourceVertex)

2541

2542 # If all vertices were processed, no cycle exists.

2543 if overallCount == 0:

2544 return False

2545 # If there are remaining vertices, then a cycle exists.

2546 elif overallCount > 0:

2547 return True

2548

2549 raise InternalError(f"Graph data structure is corrupted.") # pragma: no cover

2550

2551

2552@export

2553class Subgraph(

2554 BaseGraph[

2555 SubgraphDictKeyType, SubgraphDictValueType,

2556 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,

2557 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,

2558 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType

2559 ],

2560 Generic[

2561 SubgraphDictKeyType, SubgraphDictValueType,

2562 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,

2563 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,

2564 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType

2565 ]

2566):

2567 """

2568 .. todo:: GRAPH::Subgraph Needs documentation.

2569

2570 """

2571

2572 _graph: 'Graph'

2573

2574 def __init__(

2575 self,

2576 graph: 'Graph',

2577 name: Nullable[str] = None,

2578 # vertices: Nullable[Iterable[Vertex]] = None,

2579 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None

2580 ) -> None:

2581 """

2582 .. todo:: GRAPH::Subgraph::init Needs documentation.

2583

2584 :param graph: The reference to the graph.

2585 :param name: The optional name of the new sub-graph.

2586 :param keyValuePairs: The optional mapping (dictionary) of key-value-pairs.

2587 """

2588 if graph is None: 2588 ↛ 2589line 2588 didn't jump to line 2589 because the condition on line 2588 was never true

2589 raise ValueError("Parameter 'graph' is None.")

2590 if not isinstance(graph, Graph): 2590 ↛ 2591line 2590 didn't jump to line 2591 because the condition on line 2590 was never true

2591 ex = TypeError("Parameter 'graph' is not of type 'Graph'.")

2592 if version_info >= (3, 11): # pragma: no cover

2593 ex.add_note(f"Got type '{getFullyQualifiedName(graph)}'.")

2594 raise ex

2595

2596 super().__init__(name, keyValuePairs)

2597

2598 graph._subgraphs.add(self)

2599

2600 self._graph = graph

2601

2602 def __del__(self):

2603 """

2604 .. todo:: GRAPH::Subgraph::del Needs documentation.

2605

2606 """

2607 super().__del__()

2608

2609 @readonly

2610 def Graph(self) -> 'Graph':

2611 """

2612 Read-only property to access the graph, this subgraph is associated to (:attr:`_graph`).

2613

2614 :returns: The graph this subgraph is associated to.

2615 """

2616 return self._graph

2617

2618 def __str__(self) -> str:

2619 """

2620 .. todo:: GRAPH::Subgraph::str Needs documentation.

2621

2622 """

2623 return self._name if self._name is not None else "Unnamed subgraph"

2624

2625

2626@export

2627class View(

2628 BaseWithVertices[

2629 ViewDictKeyType, ViewDictValueType,

2630 GraphDictKeyType, GraphDictValueType,

2631 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,

2632 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,

2633 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType

2634 ],

2635 Generic[

2636 ViewDictKeyType, ViewDictValueType,

2637 GraphDictKeyType, GraphDictValueType,

2638 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,

2639 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,

2640 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType

2641 ]

2642):

2643 """

2644 .. todo:: GRAPH::View Needs documentation.

2645

2646 """

2647

2648 def __init__(

2649 self,

2650 graph: 'Graph',

2651 name: Nullable[str] = None,

2652 vertices: Nullable[Iterable[Vertex]] = None,

2653 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None

2654 ) -> None:

2655 """

2656 .. todo:: GRAPH::View::init Needs documentation.

2657

2658 :param graph: The reference to the graph.

2659 :param name: The optional name of the new view.

2660 :param vertices: The optional list of vertices in the new view.

2661 :param keyValuePairs: The optional mapping (dictionary) of key-value-pairs.

2662 """

2663 super().__init__(graph, name, vertices, keyValuePairs)

2664

2665 graph._views.add(self)

2666

2667 def __del__(self):

2668 """

2669 .. todo:: GRAPH::View::del Needs documentation.

2670

2671 """

2672 super().__del__()

2673

2674 def __str__(self) -> str:

2675 """

2676 .. todo:: GRAPH::View::str Needs documentation.

2677

2678 """

2679 return self._name if self._name is not None else "Unnamed view"

2680

2681

2682@export

2683class Component(

2684 BaseWithVertices[

2685 ComponentDictKeyType, ComponentDictValueType,

2686 GraphDictKeyType, GraphDictValueType,

2687 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,

2688 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,

2689 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType

2690 ],

2691 Generic[

2692 ComponentDictKeyType, ComponentDictValueType,

2693 GraphDictKeyType, GraphDictValueType,

2694 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,

2695 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,

2696 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType

2697 ]

2698):

2699 """

2700 .. todo:: GRAPH::Component Needs documentation.

2701

2702 """

2703

2704 def __init__(

2705 self,

2706 graph: 'Graph',

2707 name: Nullable[str] = None,

2708 vertices: Nullable[Iterable[Vertex]] = None,

2709 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None

2710 ) -> None:

2711 """

2712 .. todo:: GRAPH::Component::init Needs documentation.

2713

2714 :param graph: The reference to the graph.

2715 :param name: The optional name of the new component.

2716 :param vertices: The optional list of vertices in the new component.

2717 :param keyValuePairs: The optional mapping (dictionary) of key-value-pairs.

2718 """

2719 super().__init__(graph, name, vertices, keyValuePairs)

2720

2721 graph._components.add(self)

2722

2723 def __del__(self):

2724 """

2725 .. todo:: GRAPH::Component::del Needs documentation.

2726

2727 """

2728 super().__del__()

2729

2730 def __str__(self) -> str:

2731 """

2732 .. todo:: GRAPH::Component::str Needs documentation.

2733

2734 """

2735 return self._name if self._name is not None else "Unnamed component"

2736

2737

2738@export

2739class Graph(

2740 BaseGraph[

2741 GraphDictKeyType, GraphDictValueType,

2742 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,

2743 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,

2744 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType

2745 ],

2746 Generic[

2747 GraphDictKeyType, GraphDictValueType,

2748 ComponentDictKeyType, ComponentDictValueType,

2749 SubgraphDictKeyType, SubgraphDictValueType,

2750 ViewDictKeyType, ViewDictValueType,

2751 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,

2752 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,

2753 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType

2754 ]

2755):

2756 """

2757 A **graph** data structure is represented by an instance of :class:`~pyTooling.Graph.Graph` holding references to

2758 all nodes. Nodes are instances of :class:`~pyTooling.Graph.Vertex` classes and directed links between nodes are

2759 made of :class:`~pyTooling.Graph.Edge` instances. A graph can have attached meta information as key-value-pairs.

2760 """

2761 _subgraphs: Set[Subgraph[SubgraphDictKeyType, SubgraphDictValueType, VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType, EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType, LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType]]

2762 _views: Set[View[ViewDictKeyType, ViewDictValueType, GraphDictKeyType, GraphDictValueType, VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType, EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType, LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType]]

2763 _components: Set[Component[ComponentDictKeyType, ComponentDictValueType, GraphDictKeyType, GraphDictValueType, VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType, EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType, LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType]]

2764

2765 def __init__(

2766 self,

2767 name: Nullable[str] = None,

2768 keyValuePairs: Nullable[Mapping[DictKeyType, DictValueType]] = None

2769 ) -> None:

2770 """

2771 .. todo:: GRAPH::Graph::init Needs documentation.

2772

2773 :param name: The optional name of the new graph.

2774 :param keyValuePairs: The optional mapping (dictionary) of key-value-pairs.#

2775 """

2776 super().__init__(name, keyValuePairs)

2777

2778 self._subgraphs = set()

2779 self._views = set()

2780 self._components = set()

2781

2782 def __del__(self):

2783 """

2784 .. todo:: GRAPH::Graph::del Needs documentation.

2785

2786 """

2787 try:

2788 del self._subgraphs

2789 del self._views

2790 del self._components

2791 except AttributeError:

2792 pass

2793

2794 super().__del__()

2795

2796 @readonly

2797 def Subgraphs(self) -> Set[Subgraph]:

2798 """Read-only property to access the subgraphs in this graph (:attr:`_subgraphs`).

2799

2800 :returns: The set of subgraphs in this graph."""

2801 return self._subgraphs

2802

2803 @readonly

2804 def Views(self) -> Set[View]:

2805 """Read-only property to access the views in this graph (:attr:`_views`).

2806

2807 :returns: The set of views in this graph."""

2808 return self._views

2809

2810 @readonly

2811 def Components(self) -> Set[Component]:

2812 """Read-only property to access the components in this graph (:attr:`_components`).

2813

2814 :returns: The set of components in this graph."""

2815 return self._components

2816

2817 @readonly

2818 def SubgraphCount(self) -> int:

2819 """Read-only property to access the number of subgraphs in this graph.

2820

2821 :returns: The number of subgraphs in this graph."""

2822 return len(self._subgraphs)

2823

2824 @readonly

2825 def ViewCount(self) -> int:

2826 """Read-only property to access the number of views in this graph.

2827

2828 :returns: The number of views in this graph."""

2829 return len(self._views)

2830

2831 @readonly

2832 def ComponentCount(self) -> int:

2833 """Read-only property to access the number of components in this graph.

2834

2835 :returns: The number of components in this graph."""

2836 return len(self._components)

2837

2838 def __iter__(self) -> typing_Iterator[Vertex[GraphDictKeyType, GraphDictValueType, VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType, EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType, LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType]]:

2839 """

2840 .. todo:: GRAPH::Graph::iter Needs documentation.

2841

2842 """

2843 def gen():

2844 yield from self._verticesWithoutID

2845 yield from self._verticesWithID

2846 return iter(gen())

2847

2848 def HasVertexByID(self, vertexID: Nullable[VertexIDType]) -> bool:

2849 """

2850 .. todo:: GRAPH::Graph::HasVertexByID Needs documentation.

2851

2852 """

2853 if vertexID is None:

2854 return len(self._verticesWithoutID) >= 1

2855 else:

2856 return vertexID in self._verticesWithID

2857

2858 def HasVertexByValue(self, value: Nullable[VertexValueType]) -> bool:

2859 """

2860 .. todo:: GRAPH::Graph::HasVertexByValue Needs documentation.

2861

2862 """

2863 return any(vertex._value == value for vertex in chain(self._verticesWithoutID, self._verticesWithID.values()))

2864

2865 def GetVertexByID(self, vertexID: Nullable[VertexIDType]) -> Vertex:

2866 """

2867 .. todo:: GRAPH::Graph::GetVertexByID Needs documentation.

2868

2869 """

2870 if vertexID is None:

2871 if (l := len(self._verticesWithoutID)) == 1:

2872 return self._verticesWithoutID[0]

2873 elif l == 0:

2874 raise KeyError(f"Found no vertex with ID `None`.")

2875 else:

2876 raise KeyError(f"Found multiple vertices with ID `None`.")

2877 else:

2878 return self._verticesWithID[vertexID]

2879

2880 def GetVertexByValue(self, value: Nullable[VertexValueType]) -> Vertex:

2881 """

2882 .. todo:: GRAPH::Graph::GetVertexByValue Needs documentation.

2883

2884 """

2885 # FIXME: optimize: iterate only until first item is found and check for a second to produce error

2886 vertices = [vertex for vertex in chain(self._verticesWithoutID, self._verticesWithID.values()) if vertex._value == value]

2887 if (l := len(vertices)) == 1:

2888 return vertices[0]

2889 elif l == 0:

2890 raise KeyError(f"Found no vertex with Value == `{value}`.")

2891 else:

2892 raise KeyError(f"Found multiple vertices with Value == `{value}`.")

2893

2894 def CopyGraph(self) -> 'Graph':

2895 raise NotImplementedError()

2896

2897 def CopyVertices(self, predicate: Nullable[Callable[[Vertex], bool]] = None, copyGraphDict: bool = True, copyVertexDict: bool = True) -> 'Graph':

2898 """

2899 Create a new graph and copy all or selected vertices of the original graph.

2900

2901 If parameter ``predicate`` is not None, the given filter function is used to skip vertices.

2902

2903 :param predicate: Filter function accepting any vertex and returning a boolean.

2904 :param copyGraphDict: If ``True``, copy all graph attached attributes into the new graph.

2905 :param copyVertexDict: If ``True``, copy all vertex attached attributes into the new vertices.

2906 """

2907 graph = Graph(self._name)

2908 if copyGraphDict:

2909 graph._dict = self._dict.copy()

2910

2911 if predicate is None:

2912 for vertex in self._verticesWithoutID:

2913 v = Vertex(None, vertex._value, graph=graph)

2914 if copyVertexDict:

2915 v._dict = vertex._dict.copy()

2916

2917 for vertexID, vertex in self._verticesWithID.items():

2918 v = Vertex(vertexID, vertex._value, graph=graph)

2919 if copyVertexDict:

2920 v._dict = vertex._dict.copy()

2921 else:

2922 for vertex in self._verticesWithoutID:

2923 if predicate(vertex):

2924 v = Vertex(None, vertex._value, graph=graph)

2925 if copyVertexDict: 2925 ↛ 2922line 2925 didn't jump to line 2922 because the condition on line 2925 was always true

2926 v._dict = vertex._dict.copy()

2927

2928 for vertexID, vertex in self._verticesWithID.items():

2929 if predicate(vertex):

2930 v = Vertex(vertexID, vertex._value, graph=graph)

2931 if copyVertexDict: 2931 ↛ 2932line 2931 didn't jump to line 2932 because the condition on line 2931 was never true

2932 v._dict = vertex._dict.copy()

2933

2934 return graph

2935

2936 # class Iterator():

2937 # visited = [False for _ in range(self.__len__())]

2938

2939 # def CheckForNegativeCycles(self):

2940 # raise NotImplementedError()

2941 # # Bellman-Ford

2942 # # Floyd-Warshall

2943 #

2944 # def IsStronglyConnected(self):

2945 # raise NotImplementedError()

2946 #

2947 # def GetStronglyConnectedComponents(self):

2948 # raise NotImplementedError()

2949 # # Tarjan's and Kosaraju's algorithm

2950 #

2951 # def TravelingSalesmanProblem(self):

2952 # raise NotImplementedError()

2953 # # Held-Karp

2954 # # branch and bound

2955 #

2956 # def GetBridges(self):

2957 # raise NotImplementedError()

2958 #

2959 # def GetArticulationPoints(self):

2960 # raise NotImplementedError()

2961 #

2962 # def MinimumSpanningTree(self):

2963 # raise NotImplementedError()

2964 # # Kruskal

2965 # # Prim's algorithm

2966 # # Buruvka's algorithm

2967

2968 def __repr__(self) -> str:

2969 """

2970 .. todo:: GRAPH::Graph::repr Needs documentation.

2971

2972 """

2973 statistics = f", vertices: {self.VertexCount}, edges: {self.EdgeCount}"

2974 if self._name is None:

2975 return f"<graph: unnamed graph{statistics}>"

2976 else:

2977 return f"<graph: '{self._name}'{statistics}>"

2978

2979 def __str__(self) -> str:

2980 """

2981 .. todo:: GRAPH::Graph::str Needs documentation.

2982

2983 """

2984 if self._name is None:

2985 return f"Graph: unnamed graph"

2986 else:

2987 return f"Graph: '{self._name}'"

Coverage for pyTooling/Graph/init.py: 76%

1199 statements