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 Checks 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 ex.add_note(f"Got type '{getFullyQualifiedName(name)}'.")

387 raise ex

388

389 super().__init__(keyValuePairs)

390

391 self._name = name

392

393 @property

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

395 """

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

397

398 :returns: The value of a component.

399 """

400 return self._name

401

402 @Name.setter

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

404 if not isinstance(value, str):

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

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

407 raise ex

408

409 self._name = value

410

411

412@export

413class BaseWithVertices(

414 BaseWithName[DictKeyType, DictValueType],

415 Generic[

416 DictKeyType, DictValueType,

417 GraphDictKeyType, GraphDictValueType,

418 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,

419 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,

420 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType

421 ]

422):

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

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

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

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

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

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

429 'VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,'

430 'EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,'

431 'LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType'

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

433

434 def __init__(

435 self,

436 graph: 'Graph',

437 name: Nullable[str] = None,

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

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

440 ) -> None:

441 """

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

443

444 :param graph: The reference to the graph.

445 :param name: The optional name.

446 :param vertices: The optional list of vertices.

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

448 """

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

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

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

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

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

454 raise ex

455

456 super().__init__(name, keyValuePairs)

457

458 self._graph = graph

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

460

461 def __del__(self):

462 """

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

464

465 """

466 try:

467 del self._vertices

468 except AttributeError:

469 pass

470

471 super().__del__()

472

473 @readonly

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

475 """

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

477

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

479 """

480 return self._graph

481

482 @readonly

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

484 """

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

486

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

488 """

489 return self._vertices

490

491 @readonly

492 def VertexCount(self) -> int:

493 """

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

495

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

497 """

498 return len(self._vertices)

499

500

501@export

502class Vertex(

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

504 Generic[

505 GraphDictKeyType, GraphDictValueType,

506 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,

507 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,

508 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType

509 ]

510):

511 """

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

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

514 """

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

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

517 _component: 'Component'

518 _views: Dict[Hashable, 'View']

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

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

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

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

523

524 def __init__(

525 self,

526 vertexID: Nullable[VertexIDType] = None,

527 value: Nullable[VertexValueType] = None,

528 weight: Nullable[VertexWeightType] = None,

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

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

531 subgraph: Nullable['Subgraph'] = None

532 ) -> None:

533 """

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

535

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

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

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

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

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

541 :param subgraph: undocumented

542 """

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

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

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

546 raise ex

547

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

549

550 if subgraph is None:

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

552 self._subgraph = None

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

554

555 if vertexID is None:

556 self._graph._verticesWithoutID.append(self)

557 elif vertexID not in self._graph._verticesWithID:

558 self._graph._verticesWithID[vertexID] = self

559 else:

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

561 else:

562 self._graph = subgraph._graph

563 self._subgraph = subgraph

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

565

566 if vertexID is None:

567 subgraph._verticesWithoutID.append(self)

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

569 subgraph._verticesWithID[vertexID] = self

570 else:

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

572

573 self._views = {}

574 self._inboundEdges = []

575 self._outboundEdges = []

576 self._inboundLinks = []

577 self._outboundLinks = []

578

579 def __del__(self):

580 """

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

582

583 """

584 try:

585 del self._views

586 del self._inboundEdges

587 del self._outboundEdges

588 del self._inboundLinks

589 del self._outboundLinks

590 except AttributeError:

591 pass

592

593 super().__del__()

594

595 def Delete(self) -> None:

596 for edge in self._outboundEdges:

597 edge._destination._inboundEdges.remove(edge)

598 edge._Delete()

599 for edge in self._inboundEdges:

600 edge._source._outboundEdges.remove(edge)

601 edge._Delete()

602 for link in self._outboundLinks:

603 link._destination._inboundLinks.remove(link)

604 link._Delete()

605 for link in self._inboundLinks:

606 link._source._outboundLinks.remove(link)

607 link._Delete()

608

609 if self._id is None:

610 self._graph._verticesWithoutID.remove(self)

611 else:

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

613

614 # subgraph

615

616 # component

617

618 # views

619 self._views = None

620 self._inboundEdges = None

621 self._outboundEdges = None

622 self._inboundLinks = None

623 self._outboundLinks = None

624

625 super().Delete()

626 assert getrefcount(self) == 1

627

628 @readonly

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

630 """

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

632

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

634 """

635 return self._graph

636

637 @readonly

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

639 """

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

641

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

643 """

644 return self._component

645

646 @readonly

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

648 """

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

650

651 :returns: Tuple of inbound edges.

652 """

653 return tuple(self._inboundEdges)

654

655 @readonly

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

657 """

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

659

660 :returns: Tuple of outbound edges.

661 """

662 return tuple(self._outboundEdges)

663

664 @readonly

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

666 """

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

668

669 :returns: Tuple of inbound links.

670 """

671 return tuple(self._inboundLinks)

672

673 @readonly

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

675 """

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

677

678 :returns: Tuple of outbound links.

679 """

680 return tuple(self._outboundLinks)

681

682 @readonly

683 def EdgeCount(self) -> int:

684 """

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

686

687 :returns: Number of inbound and outbound edges.

688 """

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

690

691 @readonly

692 def InboundEdgeCount(self) -> int:

693 """

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

695

696 :returns: Number of inbound edges.

697 """

698 return len(self._inboundEdges)

699

700 @readonly

701 def OutboundEdgeCount(self) -> int:

702 """

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

704

705 :returns: Number of outbound edges.

706 """

707 return len(self._outboundEdges)

708

709 @readonly

710 def LinkCount(self) -> int:

711 """

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

713

714 :returns: Number of inbound and outbound links.

715 """

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

717

718 @readonly

719 def InboundLinkCount(self) -> int:

720 """

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

722

723 :returns: Number of inbound links.

724 """

725 return len(self._inboundLinks)

726

727 @readonly

728 def OutboundLinkCount(self) -> int:

729 """

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

731

732 :returns: Number of outbound links.

733 """

734 return len(self._outboundLinks)

735

736 @readonly

737 def IsRoot(self) -> bool:

738 """

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

740

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

742

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

744

745 .. seealso::

746

747 :meth:`IsLeaf` |br|

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

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

750 |rarr| Iterate all roots of a graph.

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

752 |rarr| Iterate all leafs of a graph.

753 """

754 return len(self._inboundEdges) == 0

755

756 @readonly

757 def IsLeaf(self) -> bool:

758 """

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

760

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

762

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

764

765 .. seealso::

766

767 :meth:`IsRoot` |br|

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

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

770 |rarr| Iterate all roots of a graph.

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

772 |rarr| Iterate all leafs of a graph.

773 """

774 return len(self._outboundEdges) == 0

775

776 @readonly

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

778 """

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

780

781 :returns: Tuple of predecessor vertices.

782 """

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

784

785 @readonly

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

787 """

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

789

790 :returns: Tuple of successor vertices.

791 """

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

793

794 def EdgeToVertex(

795 self,

796 vertex: 'Vertex',

797 edgeID: Nullable[EdgeIDType] = None,

798 edgeWeight: Nullable[EdgeWeightType] = None,

799 edgeValue: Nullable[VertexValueType] = None,

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

801 ) -> 'Edge':

802 """

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

804

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

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

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

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

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

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

811

812 .. seealso::

813

814 :meth:`EdgeFromVertex` |br|

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

816 :meth:`EdgeToNewVertex` |br|

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

818 :meth:`EdgeFromNewVertex` |br|

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

820 :meth:`LinkToVertex` |br|

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

822 :meth:`LinkFromVertex` |br|

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

824

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

826 """

827 if self._subgraph is vertex._subgraph:

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

829

830 self._outboundEdges.append(edge)

831 vertex._inboundEdges.append(edge)

832

833 if self._subgraph is None:

834 # TODO: move into Edge?

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

836 if edgeID is None:

837 self._graph._edgesWithoutID.append(edge)

838 elif edgeID not in self._graph._edgesWithID:

839 self._graph._edgesWithID[edgeID] = edge

840 else:

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

842 else:

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

844 if edgeID is None:

845 self._subgraph._edgesWithoutID.append(edge)

846 elif edgeID not in self._subgraph._edgesWithID:

847 self._subgraph._edgesWithID[edgeID] = edge

848 else:

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

850 else:

851 # FIXME: needs an error message

852 raise GraphException()

853

854 return edge

855

856 def EdgeFromVertex(

857 self,

858 vertex: 'Vertex',

859 edgeID: Nullable[EdgeIDType] = None,

860 edgeWeight: Nullable[EdgeWeightType] = None,

861 edgeValue: Nullable[VertexValueType] = None,

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

863 ) -> 'Edge':

864 """

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

866

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

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

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

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

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

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

873

874 .. seealso::

875

876 :meth:`EdgeToVertex` |br|

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

878 :meth:`EdgeToNewVertex` |br|

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

880 :meth:`EdgeFromNewVertex` |br|

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

882 :meth:`LinkToVertex` |br|

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

884 :meth:`LinkFromVertex` |br|

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

886

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

888 """

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

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

891

892 vertex._outboundEdges.append(edge)

893 self._inboundEdges.append(edge)

894

895 if self._subgraph is None:

896 # TODO: move into Edge?

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

898 if edgeID is None:

899 self._graph._edgesWithoutID.append(edge)

900 elif edgeID not in self._graph._edgesWithID:

901 self._graph._edgesWithID[edgeID] = edge

902 else:

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

904 else:

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

906 if edgeID is None:

907 self._subgraph._edgesWithoutID.append(edge)

908 elif edgeID not in self._graph._edgesWithID:

909 self._subgraph._edgesWithID[edgeID] = edge

910 else:

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

912 else:

913 # FIXME: needs an error message

914 raise GraphException()

915

916 return edge

917

918 def EdgeToNewVertex(

919 self,

920 vertexID: Nullable[VertexIDType] = None,

921 vertexValue: Nullable[VertexValueType] = None,

922 vertexWeight: Nullable[VertexWeightType] = None,

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

924 edgeID: Nullable[EdgeIDType] = None,

925 edgeWeight: Nullable[EdgeWeightType] = None,

926 edgeValue: Nullable[VertexValueType] = None,

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

928 ) -> 'Edge':

929 """

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

931

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

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

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

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

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

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

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

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

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

941

942 .. seealso::

943

944 :meth:`EdgeToVertex` |br|

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

946 :meth:`EdgeFromVertex` |br|

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

948 :meth:`EdgeFromNewVertex` |br|

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

950 :meth:`LinkToVertex` |br|

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

952 :meth:`LinkFromVertex` |br|

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

954

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

956 """

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

958

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

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

961

962 self._outboundEdges.append(edge)

963 vertex._inboundEdges.append(edge)

964

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

966 # TODO: move into Edge?

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

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

969 self._graph._edgesWithoutID.append(edge)

970 elif edgeID not in self._graph._edgesWithID:

971 self._graph._edgesWithID[edgeID] = edge

972 else:

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

974 else:

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

976 if edgeID is None:

977 self._subgraph._edgesWithoutID.append(edge)

978 elif edgeID not in self._graph._edgesWithID:

979 self._subgraph._edgesWithID[edgeID] = edge

980 else:

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

982 else:

983 # FIXME: needs an error message

984 raise GraphException()

985

986 return edge

987

988 def EdgeFromNewVertex(

989 self,

990 vertexID: Nullable[VertexIDType] = None,

991 vertexValue: Nullable[VertexValueType] = None,

992 vertexWeight: Nullable[VertexWeightType] = None,

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

994 edgeID: Nullable[EdgeIDType] = None,

995 edgeWeight: Nullable[EdgeWeightType] = None,

996 edgeValue: Nullable[VertexValueType] = None,

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

998 ) -> 'Edge':

999 """

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

1001

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

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

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

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

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

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

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

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

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

1011

1012 .. seealso::

1013

1014 :meth:`EdgeToVertex` |br|

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

1016 :meth:`EdgeFromVertex` |br|

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

1018 :meth:`EdgeToNewVertex` |br|

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

1020 :meth:`LinkToVertex` |br|

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

1022 :meth:`LinkFromVertex` |br|

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

1024

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

1026 """

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

1028

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

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

1031

1032 vertex._outboundEdges.append(edge)

1033 self._inboundEdges.append(edge)

1034

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

1036 # TODO: move into Edge?

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

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

1039 self._graph._edgesWithoutID.append(edge)

1040 elif edgeID not in self._graph._edgesWithID:

1041 self._graph._edgesWithID[edgeID] = edge

1042 else:

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

1044 else:

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

1046 if edgeID is None:

1047 self._subgraph._edgesWithoutID.append(edge)

1048 elif edgeID not in self._graph._edgesWithID:

1049 self._subgraph._edgesWithID[edgeID] = edge

1050 else:

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

1052 else:

1053 # FIXME: needs an error message

1054 raise GraphException()

1055

1056 return edge

1057

1058 def LinkToVertex(

1059 self,

1060 vertex: 'Vertex',

1061 linkID: Nullable[EdgeIDType] = None,

1062 linkWeight: Nullable[EdgeWeightType] = None,

1063 linkValue: Nullable[VertexValueType] = None,

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

1065 ) -> 'Link':

1066 """

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

1068

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

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

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

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

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

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

1075

1076 .. seealso::

1077

1078 :meth:`EdgeToVertex` |br|

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

1080 :meth:`EdgeFromVertex` |br|

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

1082 :meth:`EdgeToNewVertex` |br|

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

1084 :meth:`EdgeFromNewVertex` |br|

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

1086 :meth:`LinkFromVertex` |br|

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

1088

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

1090 """

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

1092 # FIXME: needs an error message

1093 raise GraphException()

1094 else:

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

1096

1097 self._outboundLinks.append(link)

1098 vertex._inboundLinks.append(link)

1099

1100 if self._subgraph is None:

1101 # TODO: move into Edge?

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

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

1104 self._graph._linksWithoutID.append(link)

1105 elif linkID not in self._graph._linksWithID:

1106 self._graph._linksWithID[linkID] = link

1107 else:

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

1109 else:

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

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

1112 self._subgraph._linksWithoutID.append(link)

1113 vertex._subgraph._linksWithoutID.append(link)

1114 elif linkID not in self._graph._linksWithID:

1115 self._subgraph._linksWithID[linkID] = link

1116 vertex._subgraph._linksWithID[linkID] = link

1117 else:

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

1119

1120 return link

1121

1122 def LinkFromVertex(

1123 self,

1124 vertex: 'Vertex',

1125 linkID: Nullable[EdgeIDType] = None,

1126 linkWeight: Nullable[EdgeWeightType] = None,

1127 linkValue: Nullable[VertexValueType] = None,

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

1129 ) -> 'Edge':

1130 """

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

1132

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

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

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

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

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

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

1139

1140 .. seealso::

1141

1142 :meth:`EdgeToVertex` |br|

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

1144 :meth:`EdgeFromVertex` |br|

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

1146 :meth:`EdgeToNewVertex` |br|

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

1148 :meth:`EdgeFromNewVertex` |br|

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

1150 :meth:`LinkToVertex` |br|

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

1152

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

1154 """

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

1156 # FIXME: needs an error message

1157 raise GraphException()

1158 else:

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

1160

1161 vertex._outboundLinks.append(link)

1162 self._inboundLinks.append(link)

1163

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

1165 # TODO: move into Edge?

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

1167 if linkID is None:

1168 self._graph._linksWithoutID.append(link)

1169 elif linkID not in self._graph._linksWithID:

1170 self._graph._linksWithID[linkID] = link

1171 else:

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

1173 else:

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

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

1176 self._subgraph._linksWithoutID.append(link)

1177 vertex._subgraph._linksWithoutID.append(link)

1178 elif linkID not in self._graph._linksWithID:

1179 self._subgraph._linksWithID[linkID] = link

1180 vertex._subgraph._linksWithID[linkID] = link

1181 else:

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

1183

1184 return link

1185

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

1187 """

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

1189

1190 :param destination: Destination vertex to check.

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

1192

1193 .. seealso::

1194

1195 :meth:`HasEdgeFromSource` |br|

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

1197 :meth:`HasLinkToDestination` |br|

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

1199 :meth:`HasLinkFromSource` |br|

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

1201 """

1202 for edge in self._outboundEdges:

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

1204 return True

1205

1206 return False

1207

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

1209 """

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

1211

1212 :param source: Source vertex to check.

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

1214

1215 .. seealso::

1216

1217 :meth:`HasEdgeToDestination` |br|

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

1219 :meth:`HasLinkToDestination` |br|

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

1221 :meth:`HasLinkFromSource` |br|

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

1223 """

1224 for edge in self._inboundEdges:

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

1226 return True

1227

1228 return False

1229

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

1231 """

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

1233

1234 :param destination: Destination vertex to check.

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

1236

1237 .. seealso::

1238

1239 :meth:`HasEdgeToDestination` |br|

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

1241 :meth:`HasEdgeFromSource` |br|

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

1243 :meth:`HasLinkFromSource` |br|

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

1245 """

1246 for link in self._outboundLinks:

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

1248 return True

1249

1250 return False

1251

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

1253 """

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

1255

1256 :param source: Source vertex to check.

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

1258

1259 .. seealso::

1260

1261 :meth:`HasEdgeToDestination` |br|

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

1263 :meth:`HasEdgeFromSource` |br|

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

1265 :meth:`HasLinkToDestination` |br|

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

1267 """

1268 for link in self._inboundLinks:

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

1270 return True

1271

1272 return False

1273

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

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

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

1277 break

1278 else:

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

1280

1281 edge.Delete()

1282

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

1284 for edge in self._inboundEdges:

1285 if edge._source is source:

1286 break

1287 else:

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

1289

1290 edge.Delete()

1291

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

1293 for link in self._outboundLinks:

1294 if link._destination is destination:

1295 break

1296 else:

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

1298

1299 link.Delete()

1300

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

1302 for link in self._inboundLinks:

1303 if link._source is source:

1304 break

1305 else:

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

1307

1308 link.Delete()

1309

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

1311 """

1312 Creates a copy of this vertex in another graph.

1313

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

1315 can be established.

1316

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

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

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

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

1321 :returns: The newly created vertex.

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

1323 """

1324 if graph is self._graph:

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

1326

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

1328 if copyDict:

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

1330

1331 if linkingKeyToOriginalVertex is not None:

1332 vertex._dict[linkingKeyToOriginalVertex] = self

1333 if linkingKeyFromOriginalVertex is not None:

1334 self._dict[linkingKeyFromOriginalVertex] = vertex

1335

1336 return vertex

1337

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

1339 """

1340 Iterate all or selected outbound edges of this vertex.

1341

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

1343

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

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

1346 """

1347 if predicate is None:

1348 for edge in self._outboundEdges:

1349 yield edge

1350 else:

1351 for edge in self._outboundEdges:

1352 if predicate(edge):

1353 yield edge

1354

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

1356 """

1357 Iterate all or selected inbound edges of this vertex.

1358

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

1360

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

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

1363 """

1364 if predicate is None:

1365 for edge in self._inboundEdges:

1366 yield edge

1367 else:

1368 for edge in self._inboundEdges:

1369 if predicate(edge):

1370 yield edge

1371

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

1373 """

1374 Iterate all or selected outbound links of this vertex.

1375

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

1377

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

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

1380 """

1381 if predicate is None:

1382 for link in self._outboundLinks:

1383 yield link

1384 else:

1385 for link in self._outboundLinks:

1386 if predicate(link):

1387 yield link

1388

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

1390 """

1391 Iterate all or selected inbound links of this vertex.

1392

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

1394

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

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

1397 """

1398 if predicate is None:

1399 for link in self._inboundLinks:

1400 yield link

1401 else:

1402 for link in self._inboundLinks:

1403 if predicate(link):

1404 yield link

1405

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

1407 """

1408 Iterate all or selected successor vertices of this vertex.

1409

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

1411

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

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

1414 """

1415 if predicate is None:

1416 for edge in self._outboundEdges:

1417 yield edge.Destination

1418 else:

1419 for edge in self._outboundEdges:

1420 if predicate(edge):

1421 yield edge.Destination

1422

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

1424 """

1425 Iterate all or selected predecessor vertices of this vertex.

1426

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

1428

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

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

1431 """

1432 if predicate is None:

1433 for edge in self._inboundEdges:

1434 yield edge.Source

1435 else:

1436 for edge in self._inboundEdges:

1437 if predicate(edge):

1438 yield edge.Source

1439

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

1441 """

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

1443

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

1445

1446 .. seealso::

1447

1448 :meth:`IterateVerticesDFS` |br|

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

1450 """

1451 visited: Set[Vertex] = set()

1452 queue: Deque[Vertex] = deque()

1453

1454 yield self

1455 visited.add(self)

1456 for edge in self._outboundEdges:

1457 nextVertex = edge.Destination

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

1459 queue.appendleft(nextVertex)

1460 visited.add(nextVertex)

1461

1462 while queue:

1463 vertex = queue.pop()

1464 yield vertex

1465 for edge in vertex._outboundEdges:

1466 nextVertex = edge.Destination

1467 if nextVertex not in visited:

1468 queue.appendleft(nextVertex)

1469 visited.add(nextVertex)

1470

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

1472 """

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

1474

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

1476

1477 .. seealso::

1478

1479 :meth:`IterateVerticesBFS` |br|

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

1481

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

1483 """

1484 visited: Set[Vertex] = set()

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

1486

1487 yield self

1488 visited.add(self)

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

1490

1491 while True:

1492 try:

1493 edge = next(stack[-1])

1494 nextVertex = edge._destination

1495 if nextVertex not in visited:

1496 visited.add(nextVertex)

1497 yield nextVertex

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

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

1500 except StopIteration:

1501 stack.pop()

1502

1503 if len(stack) == 0:

1504 return

1505

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

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

1508 yield (self, )

1509 return

1510

1511 visited: Set[Vertex] = set()

1512 vertexStack: List[Vertex] = list()

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

1514

1515 visited.add(self)

1516 vertexStack.append(self)

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

1518

1519 while True:

1520 try:

1521 edge = next(iteratorStack[-1])

1522 nextVertex = edge._destination

1523 if nextVertex in visited:

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

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

1526 for i, vertex in enumerate(vertexStack):

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

1528 raise ex

1529

1530 vertexStack.append(nextVertex)

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

1532 yield tuple(vertexStack)

1533 vertexStack.pop()

1534 else:

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

1536

1537 except StopIteration:

1538 vertexStack.pop()

1539 iteratorStack.pop()

1540

1541 if len(vertexStack) == 0:

1542 return

1543

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

1545 """

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

1547

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

1549

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

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

1552

1553 :param destination: The destination vertex to reach.

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

1555 """

1556 # Trivial case if start is destination

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

1558 yield self

1559 return

1560

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

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

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

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

1565 parent: 'Node'

1566 ref: Vertex

1567

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

1569 self.parent = parent

1570 self.ref = ref

1571

1572 def __str__(self):

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

1574

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

1576 startNode = Node(None, self)

1577 visited: Set[Vertex] = set()

1578 queue: Deque[Node] = deque()

1579

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

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

1582 visited.add(self)

1583 for edge in self._outboundEdges:

1584 nextVertex = edge.Destination

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

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

1587 destinationNode = Node(startNode, nextVertex)

1588 break

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

1590 # Ignore backward-edges and side-edges.

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

1592 visited.add(nextVertex)

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

1594 else:

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

1596 while queue:

1597 node = queue.pop()

1598 for edge in node.ref._outboundEdges:

1599 nextVertex = edge.Destination

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

1601 if nextVertex is destination:

1602 destinationNode = Node(node, nextVertex)

1603 break

1604 # Ignore backward-edges and side-edges.

1605 if nextVertex not in visited:

1606 visited.add(nextVertex)

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

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

1609 else:

1610 continue

1611 break

1612 else:

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

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

1615

1616 # Reverse order of linked list from destinationNode to startNode

1617 currentNode = destinationNode

1618 previousNode = destinationNode.parent

1619 currentNode.parent = None

1620 while previousNode is not None:

1621 node = previousNode.parent

1622 previousNode.parent = currentNode

1623 currentNode = previousNode

1624 previousNode = node

1625

1626 # Scan reversed linked-list and yield referenced vertices

1627 yield startNode.ref

1628 node = startNode.parent

1629 while node is not None:

1630 yield node.ref

1631 node = node.parent

1632

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

1634 """

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

1636

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

1638

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

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

1641

1642 :param destination: The destination vertex to reach.

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

1644 """

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

1646

1647 # Trivial case if start is destination

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

1649 yield self

1650 return

1651

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

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

1654 # represents.

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

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

1657 parent: 'Node'

1658 distance: EdgeWeightType

1659 ref: Vertex

1660

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

1662 self.parent = parent

1663 self.distance = distance

1664 self.ref = ref

1665

1666 def __lt__(self, other):

1667 return self.distance < other.distance

1668

1669 def __str__(self):

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

1671

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

1673 startNode = Node(None, 0, self)

1674 priorityQueue = [startNode]

1675

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

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

1678 visited.add(self)

1679 for edge in self._outboundEdges:

1680 nextVertex = edge.Destination

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

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

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

1684 break

1685 # Ignore backward-edges and side-edges.

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

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

1688 visited.add(nextVertex)

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

1690 else:

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

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

1693 node = heapq.heappop(priorityQueue)

1694 for edge in node.ref._outboundEdges:

1695 nextVertex = edge.Destination

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

1697 if nextVertex is destination:

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

1699 break

1700 # Ignore backward-edges and side-edges.

1701 if nextVertex not in visited:

1702 visited.add(nextVertex)

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

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

1705 else:

1706 continue

1707 break

1708 else:

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

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

1711

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

1713 currentNode = destinationNode

1714 previousNode = destinationNode.parent

1715 currentNode.parent = None

1716 while previousNode is not None:

1717 node = previousNode.parent

1718 previousNode.parent = currentNode

1719 currentNode = previousNode

1720 previousNode = node

1721

1722 # Scan reversed linked-list and yield referenced vertices

1723 yield startNode.ref, startNode.distance

1724 node = startNode.parent

1725 while node is not None:

1726 yield node.ref, node.distance

1727 node = node.parent

1728

1729 # Other possible algorithms:

1730 # * Bellman-Ford

1731 # * Floyd-Warshall

1732

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

1734 # raise NotImplementedError()

1735 # # DFS

1736 # # Union find

1737 #

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

1739 # raise NotImplementedError()

1740 # # Ford-Fulkerson algorithm

1741 # # Edmons-Karp algorithm

1742 # # Dinic's algorithm

1743

1744 def ConvertToTree(self) -> Node:

1745 """

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

1747

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

1749

1750 :returns:

1751 """

1752 visited: Set[Vertex] = set()

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

1754

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

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

1757

1758 visited.add(self)

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

1760

1761 while True:

1762 try:

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

1764 nextVertex = edge._destination

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

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

1767 visited.add(nextVertex)

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

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

1770 else:

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

1772 # TODO: compute cycle:

1773 # a) branch 1 is described in stack

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

1775 except StopIteration:

1776 stack.pop()

1777

1778 if len(stack) == 0:

1779 return root

1780

1781 def __repr__(self) -> str:

1782 """

1783 Returns a detailed string representation of the vertex.

1784

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

1786 """

1787 vertexID = value = ""

1788 sep = ": "

1789 if self._id is not None:

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

1791 sep = "; "

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

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

1794

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

1796

1797 def __str__(self) -> str:

1798 """

1799 Return a string representation of the vertex.

1800

1801 Order of resolution:

1802

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

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

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

1806

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

1808 """

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

1810 return str(self._value)

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

1812 return str(self._id)

1813 else:

1814 return self.__repr__()

1815

1816

1817@export

1818class BaseEdge(

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

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

1821):

1822 """

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

1824 directed.

1825 """

1826 _source: Vertex

1827 _destination: Vertex

1828

1829 def __init__(

1830 self,

1831 source: Vertex,

1832 destination: Vertex,

1833 edgeID: Nullable[EdgeIDType] = None,

1834 value: Nullable[EdgeValueType] = None,

1835 weight: Nullable[EdgeWeightType] = None,

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

1837 ) -> None:

1838 """

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

1840

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

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

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

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

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

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

1847 """

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

1849

1850 self._source = source

1851 self._destination = destination

1852

1853 component = source._component

1854 if component is not destination._component:

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

1856 oldComponent = destination._component

1857 for vertex in oldComponent._vertices:

1858 vertex._component = component

1859 component._vertices.add(vertex)

1860 component._graph._components.remove(oldComponent)

1861 del oldComponent

1862

1863 @readonly

1864 def Source(self) -> Vertex:

1865 """

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

1867

1868 :returns: The source of an edge.

1869 """

1870 return self._source

1871

1872 @readonly

1873 def Destination(self) -> Vertex:

1874 """

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

1876

1877 :returns: The destination of an edge.

1878 """

1879 return self._destination

1880

1881 def Reverse(self) -> None:

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

1883 swap = self._source

1884 self._source = self._destination

1885 self._destination = swap

1886

1887

1888@export

1889class Edge(

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

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

1892):

1893 """

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

1895 directed.

1896 """

1897

1898 def __init__(

1899 self,

1900 source: Vertex,

1901 destination: Vertex,

1902 edgeID: Nullable[EdgeIDType] = None,

1903 value: Nullable[EdgeValueType] = None,

1904 weight: Nullable[EdgeWeightType] = None,

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

1906 ) -> None:

1907 """

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

1909

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

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

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

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

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

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

1916 """

1917 if not isinstance(source, Vertex):

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

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

1920 raise ex

1921 if not isinstance(destination, Vertex):

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

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

1924 raise ex

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

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

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

1928 raise ex

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

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

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

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

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

1934 raise ex

1935 if source._graph is not destination._graph:

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

1937

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

1939

1940 def Delete(self) -> None:

1941 # Remove from Source and Destination

1942 self._source._outboundEdges.remove(self)

1943 self._destination._inboundEdges.remove(self)

1944

1945 # Remove from Graph and Subgraph

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

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

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

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

1950 else:

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

1952 if self._source._subgraph is not None:

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

1954

1955 self._Delete()

1956

1957 def _Delete(self) -> None:

1958 super().Delete()

1959

1960 def Reverse(self) -> None:

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

1962 self._source._outboundEdges.remove(self)

1963 self._source._inboundEdges.append(self)

1964 self._destination._inboundEdges.remove(self)

1965 self._destination._outboundEdges.append(self)

1966

1967 super().Reverse()

1968

1969

1970@export

1971class Link(

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

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

1974):

1975 """

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

1977 directed.

1978 """

1979

1980 def __init__(

1981 self,

1982 source: Vertex,

1983 destination: Vertex,

1984 linkID: LinkIDType = None,

1985 value: LinkValueType = None,

1986 weight: Nullable[LinkWeightType] = None,

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

1988 ) -> None:

1989 """

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

1991

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

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

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

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

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

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

1998 """

1999 if not isinstance(source, Vertex):

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

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

2002 raise ex

2003 if not isinstance(destination, Vertex):

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

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

2006 raise ex

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

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

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

2010 raise ex

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

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

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

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

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

2016 raise ex

2017 if source._graph is not destination._graph:

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

2019

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

2021

2022 def Delete(self) -> None:

2023 self._source._outboundEdges.remove(self)

2024 self._destination._inboundEdges.remove(self)

2025

2026 if self._id is None:

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

2028 else:

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

2030

2031 self._Delete()

2032 assert getrefcount(self) == 1

2033

2034 def _Delete(self) -> None:

2035 super().Delete()

2036

2037 def Reverse(self) -> None:

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

2039 self._source._outboundEdges.remove(self)

2040 self._source._inboundEdges.append(self)

2041 self._destination._inboundEdges.remove(self)

2042 self._destination._outboundEdges.append(self)

2043

2044 super().Reverse()

2045

2046

2047@export

2048class BaseGraph(

2049 BaseWithName[GraphDictKeyType, GraphDictValueType],

2050 Generic[

2051 GraphDictKeyType, GraphDictValueType,

2052 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,

2053 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,

2054 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType

2055 ]

2056):

2057 """

2058 .. todo:: GRAPH::BaseGraph Needs documentation.

2059

2060 """

2061

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

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

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

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

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

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

2068

2069 def __init__(

2070 self,

2071 name: Nullable[str] = None,

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

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

2074 ):

2075 """

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

2077

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

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

2080 """

2081 super().__init__(name, keyValuePairs)

2082

2083 self._verticesWithoutID = []

2084 self._verticesWithID = {}

2085 self._edgesWithoutID = []

2086 self._edgesWithID = {}

2087 self._linksWithoutID = []

2088 self._linksWithID = {}

2089

2090 def __del__(self):

2091 """

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

2093

2094 """

2095 try:

2096 del self._verticesWithoutID

2097 del self._verticesWithID

2098 del self._edgesWithoutID

2099 del self._edgesWithID

2100 del self._linksWithoutID

2101 del self._linksWithID

2102 except AttributeError:

2103 pass

2104

2105 super().__del__()

2106

2107 @readonly

2108 def VertexCount(self) -> int:

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

2110

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

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

2113

2114 @readonly

2115 def EdgeCount(self) -> int:

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

2117

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

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

2120

2121 @readonly

2122 def LinkCount(self) -> int:

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

2124

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

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

2127

2128 def IterateVertices(self, predicate: Nullable[Callable[[Vertex], bool]] = None) -> Generator[Vertex[GraphDictKeyType, GraphDictValueType, VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType, EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType, LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType], None, None]:

2129 """

2130 Iterate all or selected vertices of a graph.

2131

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

2133

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

2135 :returns: A generator to iterate all vertices.

2136 """

2137 if predicate is None:

2138 yield from self._verticesWithoutID

2139 yield from self._verticesWithID.values()

2140

2141 else:

2142 for vertex in self._verticesWithoutID:

2143 if predicate(vertex):

2144 yield vertex

2145

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

2147 if predicate(vertex):

2148 yield vertex

2149

2150 def IterateRoots(self, predicate: Nullable[Callable[[Vertex], bool]] = None) -> Generator[Vertex[GraphDictKeyType, GraphDictValueType, VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType, EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType, LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType], None, None]:

2151 """

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

2153

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

2155

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

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

2158

2159 .. seealso::

2160

2161 :meth:`IterateLeafs` |br|

2162 |rarr| Iterate leafs of a graph.

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

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

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

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

2167 """

2168 if predicate is None:

2169 for vertex in self._verticesWithoutID:

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

2171 yield vertex

2172

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

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

2175 yield vertex

2176 else:

2177 for vertex in self._verticesWithoutID:

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

2179 yield vertex

2180

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

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

2183 yield vertex

2184

2185 def IterateLeafs(self, predicate: Nullable[Callable[[Vertex], bool]] = None) -> Generator[Vertex[GraphDictKeyType, GraphDictValueType, VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType, EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType, LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType], None, None]:

2186 """

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

2188

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

2190

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

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

2193

2194 .. seealso::

2195

2196 :meth:`IterateRoots` |br|

2197 |rarr| Iterate roots of a graph.

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

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

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

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

2202 """

2203 if predicate is None:

2204 for vertex in self._verticesWithoutID:

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

2206 yield vertex

2207

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

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

2210 yield vertex

2211 else:

2212 for vertex in self._verticesWithoutID:

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

2214 yield vertex

2215

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

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

2218 yield vertex

2219

2220 # def IterateBFS(self, predicate: Nullable[Callable[[Vertex], bool]] = None) -> Generator[Vertex[GraphDictKeyType, GraphDictValueType, VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType, EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType, LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType], None, None]:

2221 # raise NotImplementedError()

2222 #

2223 # def IterateDFS(self, predicate: Nullable[Callable[[Vertex], bool]] = None) -> Generator[Vertex[GraphDictKeyType, GraphDictValueType, VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType, EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType, LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType], None, None]:

2224 # raise NotImplementedError()

2225

2226 def IterateTopologically(self, predicate: Nullable[Callable[[Vertex], bool]] = None) -> Generator[Vertex[GraphDictKeyType, GraphDictValueType, VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType, EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType, LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType], None, None]:

2227 """

2228 Iterate all or selected vertices in topological order.

2229

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

2231

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

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

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

2235 """

2236 outboundEdgeCounts = {}

2237 leafVertices = []

2238

2239 for vertex in self._verticesWithoutID:

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

2241 leafVertices.append(vertex)

2242 else:

2243 outboundEdgeCounts[vertex] = count

2244

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

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

2247 leafVertices.append(vertex)

2248 else:

2249 outboundEdgeCounts[vertex] = count

2250

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

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

2253

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

2255

2256 def removeVertex(vertex: Vertex):

2257 nonlocal overallCount

2258 overallCount -= 1

2259 for inboundEdge in vertex._inboundEdges:

2260 sourceVertex = inboundEdge.Source

2261 count = outboundEdgeCounts[sourceVertex] - 1

2262 outboundEdgeCounts[sourceVertex] = count

2263 if count == 0:

2264 leafVertices.append(sourceVertex)

2265

2266 if predicate is None:

2267 for vertex in leafVertices:

2268 yield vertex

2269

2270 removeVertex(vertex)

2271 else:

2272 for vertex in leafVertices:

2273 if predicate(vertex):

2274 yield vertex

2275

2276 removeVertex(vertex)

2277

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

2279 return

2280 elif overallCount > 0:

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

2282

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

2284

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

2286 """

2287 Iterate all or selected edges of a graph.

2288

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

2290

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

2292 :returns: A generator to iterate all edges.

2293 """

2294 if predicate is None:

2295 yield from self._edgesWithoutID

2296 yield from self._edgesWithID.values()

2297

2298 else:

2299 for edge in self._edgesWithoutID:

2300 if predicate(edge):

2301 yield edge

2302

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

2304 if predicate(edge):

2305 yield edge

2306

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

2308 """

2309 Iterate all or selected links of a graph.

2310

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

2312

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

2314 :returns: A generator to iterate all links.

2315 """

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

2317 yield from self._linksWithoutID

2318 yield from self._linksWithID.values()

2319

2320 else:

2321 for link in self._linksWithoutID:

2322 if predicate(link):

2323 yield link

2324

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

2326 if predicate(link):

2327 yield link

2328

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

2330 """

2331 Reverse all or selected edges of a graph.

2332

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

2334

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

2336 """

2337 if predicate is None:

2338 for edge in self._edgesWithoutID:

2339 swap = edge._source

2340 edge._source = edge._destination

2341 edge._destination = swap

2342

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

2344 swap = edge._source

2345 edge._source = edge._destination

2346 edge._destination = swap

2347

2348 for vertex in self._verticesWithoutID:

2349 swap = vertex._inboundEdges

2350 vertex._inboundEdges = vertex._outboundEdges

2351 vertex._outboundEdges = swap

2352

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

2354 swap = vertex._inboundEdges

2355 vertex._inboundEdges = vertex._outboundEdges

2356 vertex._outboundEdges = swap

2357 else:

2358 for edge in self._edgesWithoutID:

2359 if predicate(edge):

2360 edge.Reverse()

2361

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

2363 if predicate(edge):

2364 edge.Reverse()

2365

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

2367 """

2368 Reverse all or selected links of a graph.

2369

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

2371

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

2373 """

2374 if predicate is None:

2375 for link in self._linksWithoutID:

2376 swap = link._source

2377 link._source = link._destination

2378 link._destination = swap

2379

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

2381 swap = link._source

2382 link._source = link._destination

2383 link._destination = swap

2384

2385 for vertex in self._verticesWithoutID:

2386 swap = vertex._inboundLinks

2387 vertex._inboundLinks = vertex._outboundLinks

2388 vertex._outboundLinks = swap

2389

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

2391 swap = vertex._inboundLinks

2392 vertex._inboundLinks = vertex._outboundLinks

2393 vertex._outboundLinks = swap

2394 else:

2395 for link in self._linksWithoutID:

2396 if predicate(link):

2397 link.Reverse()

2398

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

2400 if predicate(link):

2401 link.Reverse()

2402

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

2404 """

2405 Remove all or selected edges of a graph.

2406

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

2408

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

2410 """

2411 if predicate is None:

2412 for edge in self._edgesWithoutID:

2413 edge._Delete()

2414

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

2416 edge._Delete()

2417

2418 self._edgesWithoutID = []

2419 self._edgesWithID = {}

2420

2421 for vertex in self._verticesWithoutID:

2422 vertex._inboundEdges = []

2423 vertex._outboundEdges = []

2424

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

2426 vertex._inboundEdges = []

2427 vertex._outboundEdges = []

2428

2429 else:

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

2431 for edge in delEdges:

2432 del self._edgesWithID[edge._id]

2433

2434 edge._source._outboundEdges.remove(edge)

2435 edge._destination._inboundEdges.remove(edge)

2436 edge._Delete()

2437

2438 for edge in self._edgesWithoutID:

2439 if predicate(edge):

2440 self._edgesWithoutID.remove(edge)

2441

2442 edge._source._outboundEdges.remove(edge)

2443 edge._destination._inboundEdges.remove(edge)

2444 edge._Delete()

2445

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

2447 """

2448 Remove all or selected links of a graph.

2449

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

2451

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

2453 """

2454 if predicate is None:

2455 for link in self._linksWithoutID:

2456 link._Delete()

2457

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

2459 link._Delete()

2460

2461 self._linksWithoutID = []

2462 self._linksWithID = {}

2463

2464 for vertex in self._verticesWithoutID:

2465 vertex._inboundLinks = []

2466 vertex._outboundLinks = []

2467

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

2469 vertex._inboundLinks = []

2470 vertex._outboundLinks = []

2471

2472 else:

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

2474 for link in delLinks:

2475 del self._linksWithID[link._id]

2476

2477 link._source._outboundLinks.remove(link)

2478 link._destination._inboundLinks.remove(link)

2479 link._Delete()

2480

2481 for link in self._linksWithoutID:

2482 if predicate(link):

2483 self._linksWithoutID.remove(link)

2484

2485 link._source._outboundLinks.remove(link)

2486 link._destination._inboundLinks.remove(link)

2487 link._Delete()

2488

2489 def HasCycle(self) -> bool:

2490 """

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

2492

2493 """

2494 # IsAcyclic ?

2495

2496 # Handle trivial case if graph is empty

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

2498 return False

2499

2500 outboundEdgeCounts = {}

2501 leafVertices = []

2502

2503 for vertex in self._verticesWithoutID:

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

2505 leafVertices.append(vertex)

2506 else:

2507 outboundEdgeCounts[vertex] = count

2508

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

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

2511 leafVertices.append(vertex)

2512 else:

2513 outboundEdgeCounts[vertex] = count

2514

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

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

2517 return True

2518

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

2520

2521 for vertex in leafVertices:

2522 overallCount -= 1

2523 for inboundEdge in vertex._inboundEdges:

2524 sourceVertex = inboundEdge.Source

2525 count = outboundEdgeCounts[sourceVertex] - 1

2526 outboundEdgeCounts[sourceVertex] = count

2527 if count == 0:

2528 leafVertices.append(sourceVertex)

2529

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

2531 if overallCount == 0:

2532 return False

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

2534 elif overallCount > 0:

2535 return True

2536

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

2538

2539

2540@export

2541class Subgraph(

2542 BaseGraph[

2543 SubgraphDictKeyType, SubgraphDictValueType,

2544 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,

2545 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,

2546 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType

2547 ],

2548 Generic[

2549 SubgraphDictKeyType, SubgraphDictValueType,

2550 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,

2551 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,

2552 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType

2553 ]

2554):

2555 """

2556 .. todo:: GRAPH::Subgraph Needs documentation.

2557

2558 """

2559

2560 _graph: 'Graph'

2561

2562 def __init__(

2563 self,

2564 graph: 'Graph',

2565 name: Nullable[str] = None,

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

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

2568 ) -> None:

2569 """

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

2571

2572 :param graph: The reference to the graph.

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

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

2575 """

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

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

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

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

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

2581 raise ex

2582

2583 super().__init__(name, keyValuePairs)

2584

2585 graph._subgraphs.add(self)

2586

2587 self._graph = graph

2588

2589 def __del__(self):

2590 """

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

2592

2593 """

2594 super().__del__()

2595

2596 @readonly

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

2598 """

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

2600

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

2602 """

2603 return self._graph

2604

2605 def __str__(self) -> str:

2606 """

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

2608

2609 """

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

2611

2612

2613@export

2614class View(

2615 BaseWithVertices[

2616 ViewDictKeyType, ViewDictValueType,

2617 GraphDictKeyType, GraphDictValueType,

2618 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,

2619 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,

2620 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType

2621 ],

2622 Generic[

2623 ViewDictKeyType, ViewDictValueType,

2624 GraphDictKeyType, GraphDictValueType,

2625 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,

2626 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,

2627 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType

2628 ]

2629):

2630 """

2631 .. todo:: GRAPH::View Needs documentation.

2632

2633 """

2634

2635 def __init__(

2636 self,

2637 graph: 'Graph',

2638 name: Nullable[str] = None,

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

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

2641 ) -> None:

2642 """

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

2644

2645 :param graph: The reference to the graph.

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

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

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

2649 """

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

2651

2652 graph._views.add(self)

2653

2654 def __del__(self):

2655 """

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

2657

2658 """

2659 super().__del__()

2660

2661 def __str__(self) -> str:

2662 """

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

2664

2665 """

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

2667

2668

2669@export

2670class Component(

2671 BaseWithVertices[

2672 ComponentDictKeyType, ComponentDictValueType,

2673 GraphDictKeyType, GraphDictValueType,

2674 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,

2675 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,

2676 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType

2677 ],

2678 Generic[

2679 ComponentDictKeyType, ComponentDictValueType,

2680 GraphDictKeyType, GraphDictValueType,

2681 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,

2682 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,

2683 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType

2684 ]

2685):

2686 """

2687 .. todo:: GRAPH::Component Needs documentation.

2688

2689 """

2690

2691 def __init__(

2692 self,

2693 graph: 'Graph',

2694 name: Nullable[str] = None,

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

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

2697 ) -> None:

2698 """

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

2700

2701 :param graph: The reference to the graph.

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

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

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

2705 """

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

2707

2708 graph._components.add(self)

2709

2710 def __del__(self):

2711 """

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

2713

2714 """

2715 super().__del__()

2716

2717 def __str__(self) -> str:

2718 """

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

2720

2721 """

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

2723

2724

2725@export

2726class Graph(

2727 BaseGraph[

2728 GraphDictKeyType, GraphDictValueType,

2729 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,

2730 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,

2731 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType

2732 ],

2733 Generic[

2734 GraphDictKeyType, GraphDictValueType,

2735 ComponentDictKeyType, ComponentDictValueType,

2736 SubgraphDictKeyType, SubgraphDictValueType,

2737 ViewDictKeyType, ViewDictValueType,

2738 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,

2739 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,

2740 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType

2741 ]

2742):

2743 """

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

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

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

2747 """

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

2749 _views: Set[View[ViewDictKeyType, ViewDictValueType, GraphDictKeyType, GraphDictValueType, VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType, EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType, LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType]]

2750 _components: Set[Component[ComponentDictKeyType, ComponentDictValueType, GraphDictKeyType, GraphDictValueType, VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType, EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType, LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType]]

2751

2752 def __init__(

2753 self,

2754 name: Nullable[str] = None,

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

2756 ) -> None:

2757 """

2758 .. todo:: GRAPH::Graph::init Needs documentation.

2759

2760 :param name: The optional name of the new graph.

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

2762 """

2763 super().__init__(name, keyValuePairs)

2764

2765 self._subgraphs = set()

2766 self._views = set()

2767 self._components = set()

2768

2769 def __del__(self):

2770 """

2771 .. todo:: GRAPH::Graph::del Needs documentation.

2772

2773 """

2774 try:

2775 del self._subgraphs

2776 del self._views

2777 del self._components

2778 except AttributeError:

2779 pass

2780

2781 super().__del__()

2782

2783 @readonly

2784 def Subgraphs(self) -> Set[Subgraph]:

2785 """Read-only property to access the subgraphs in this graph (:attr:`_subgraphs`).

2786

2787 :returns: The set of subgraphs in this graph."""

2788 return self._subgraphs

2789

2790 @readonly

2791 def Views(self) -> Set[View]:

2792 """Read-only property to access the views in this graph (:attr:`_views`).

2793

2794 :returns: The set of views in this graph."""

2795 return self._views

2796

2797 @readonly

2798 def Components(self) -> Set[Component]:

2799 """Read-only property to access the components in this graph (:attr:`_components`).

2800

2801 :returns: The set of components in this graph."""

2802 return self._components

2803

2804 @readonly

2805 def SubgraphCount(self) -> int:

2806 """Read-only property to access the number of subgraphs in this graph.

2807

2808 :returns: The number of subgraphs in this graph."""

2809 return len(self._subgraphs)

2810

2811 @readonly

2812 def ViewCount(self) -> int:

2813 """Read-only property to access the number of views in this graph.

2814

2815 :returns: The number of views in this graph."""

2816 return len(self._views)

2817

2818 @readonly

2819 def ComponentCount(self) -> int:

2820 """Read-only property to access the number of components in this graph.

2821

2822 :returns: The number of components in this graph."""

2823 return len(self._components)

2824

2825 def __iter__(self) -> typing_Iterator[Vertex[GraphDictKeyType, GraphDictValueType, VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType, EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType, LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType]]:

2826 """

2827 .. todo:: GRAPH::Graph::iter Needs documentation.

2828

2829 """

2830 def gen():

2831 yield from self._verticesWithoutID

2832 yield from self._verticesWithID

2833 return iter(gen())

2834

2835 def HasVertexByID(self, vertexID: Nullable[VertexIDType]) -> bool:

2836 """

2837 .. todo:: GRAPH::Graph::HasVertexByID Needs documentation.

2838

2839 """

2840 if vertexID is None:

2841 return len(self._verticesWithoutID) >= 1

2842 else:

2843 return vertexID in self._verticesWithID

2844

2845 def HasVertexByValue(self, value: Nullable[VertexValueType]) -> bool:

2846 """

2847 .. todo:: GRAPH::Graph::HasVertexByValue Needs documentation.

2848

2849 """

2850 return any(vertex._value == value for vertex in chain(self._verticesWithoutID, self._verticesWithID.values()))

2851

2852 def GetVertexByID(self, vertexID: Nullable[VertexIDType]) -> Vertex:

2853 """

2854 .. todo:: GRAPH::Graph::GetVertexByID Needs documentation.

2855

2856 """

2857 if vertexID is None:

2858 if (l := len(self._verticesWithoutID)) == 1:

2859 return self._verticesWithoutID[0]

2860 elif l == 0:

2861 raise KeyError(f"Found no vertex with ID `None`.")

2862 else:

2863 raise KeyError(f"Found multiple vertices with ID `None`.")

2864 else:

2865 return self._verticesWithID[vertexID]

2866

2867 def GetVertexByValue(self, value: Nullable[VertexValueType]) -> Vertex:

2868 """

2869 .. todo:: GRAPH::Graph::GetVertexByValue Needs documentation.

2870

2871 """

2872 # FIXME: optimize: iterate only until first item is found and check for a second to produce error

2873 vertices = [vertex for vertex in chain(self._verticesWithoutID, self._verticesWithID.values()) if vertex._value == value]

2874 if (l := len(vertices)) == 1:

2875 return vertices[0]

2876 elif l == 0:

2877 raise KeyError(f"Found no vertex with Value == `{value}`.")

2878 else:

2879 raise KeyError(f"Found multiple vertices with Value == `{value}`.")

2880

2881 def CopyGraph(self) -> 'Graph':

2882 raise NotImplementedError()

2883

2884 def CopyVertices(self, predicate: Nullable[Callable[[Vertex], bool]] = None, copyGraphDict: bool = True, copyVertexDict: bool = True) -> 'Graph':

2885 """

2886 Create a new graph and copy all or selected vertices of the original graph.

2887

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

2889

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

2891 :param copyGraphDict: If ``True``, copy all graph attached attributes into the new graph.

2892 :param copyVertexDict: If ``True``, copy all vertex attached attributes into the new vertices.

2893 """

2894 graph = Graph(self._name)

2895 if copyGraphDict:

2896 graph._dict = self._dict.copy()

2897

2898 if predicate is None:

2899 for vertex in self._verticesWithoutID:

2900 v = Vertex(None, vertex._value, graph=graph)

2901 if copyVertexDict:

2902 v._dict = vertex._dict.copy()

2903

2904 for vertexID, vertex in self._verticesWithID.items():

2905 v = Vertex(vertexID, vertex._value, graph=graph)

2906 if copyVertexDict:

2907 v._dict = vertex._dict.copy()

2908 else:

2909 for vertex in self._verticesWithoutID:

2910 if predicate(vertex):

2911 v = Vertex(None, vertex._value, graph=graph)

2912 if copyVertexDict: 2912 ↛ 2909line 2912 didn't jump to line 2909 because the condition on line 2912 was always true

2913 v._dict = vertex._dict.copy()

2914

2915 for vertexID, vertex in self._verticesWithID.items():

2916 if predicate(vertex):

2917 v = Vertex(vertexID, vertex._value, graph=graph)

2918 if copyVertexDict: 2918 ↛ 2919line 2918 didn't jump to line 2919 because the condition on line 2918 was never true

2919 v._dict = vertex._dict.copy()

2920

2921 return graph

2922

2923 # class Iterator():

2924 # visited = [False for _ in range(self.__len__())]

2925

2926 # def CheckForNegativeCycles(self):

2927 # raise NotImplementedError()

2928 # # Bellman-Ford

2929 # # Floyd-Warshall

2930 #

2931 # def IsStronglyConnected(self):

2932 # raise NotImplementedError()

2933 #

2934 # def GetStronglyConnectedComponents(self):

2935 # raise NotImplementedError()

2936 # # Tarjan's and Kosaraju's algorithm

2937 #

2938 # def TravelingSalesmanProblem(self):

2939 # raise NotImplementedError()

2940 # # Held-Karp

2941 # # branch and bound

2942 #

2943 # def GetBridges(self):

2944 # raise NotImplementedError()

2945 #

2946 # def GetArticulationPoints(self):

2947 # raise NotImplementedError()

2948 #

2949 # def MinimumSpanningTree(self):

2950 # raise NotImplementedError()

2951 # # Kruskal

2952 # # Prim's algorithm

2953 # # Buruvka's algorithm

2954

2955 def __repr__(self) -> str:

2956 """

2957 .. todo:: GRAPH::Graph::repr Needs documentation.

2958

2959 """

2960 statistics = f", vertices: {self.VertexCount}, edges: {self.EdgeCount}"

2961 if self._name is None:

2962 return f"<graph: unnamed graph{statistics}>"

2963 else:

2964 return f"<graph: '{self._name}'{statistics}>"

2965

2966 def __str__(self) -> str:

2967 """

2968 .. todo:: GRAPH::Graph::str Needs documentation.

2969

2970 """

2971 if self._name is None:

2972 return f"Graph: unnamed graph"

2973 else:

2974 return f"Graph: '{self._name}'"

Coverage for pyTooling/Graph/init.py: 76%

1212 statements