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 typing import TypeVar, Generic, List, Tuple, Dict, Set, Deque, Union, Optional as Nullable

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

61from pyTooling.Decorators import export, readonly

62from pyTooling.MetaClasses import ExtendedType

63from pyTooling.Exceptions import ToolingException

64from pyTooling.Common import getFullyQualifiedName

65from pyTooling.Tree import Node

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

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

71DictValueType = TypeVar("DictValueType")

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

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

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

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

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

80ValueType = TypeVar("ValueType")

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

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

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

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

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

89VertexValueType = TypeVar("VertexValueType")

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

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

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

95VertexDictValueType = TypeVar("VertexDictValueType")

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

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

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

100

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

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

103

104EdgeValueType = TypeVar("EdgeValueType")

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

106

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

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

109

110EdgeDictValueType = TypeVar("EdgeDictValueType")

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

112

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

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

115

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

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

118

119LinkValueType = TypeVar("LinkValueType")

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

121

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

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

124

125LinkDictValueType = TypeVar("LinkDictValueType")

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

127

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

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

130

131ComponentDictValueType = TypeVar("ComponentDictValueType")

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

133

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

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

136

137SubgraphDictValueType = TypeVar("SubgraphDictValueType")

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

139

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

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

142

143ViewDictValueType = TypeVar("ViewDictValueType")

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

145

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

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

148

149GraphDictValueType = TypeVar("GraphDictValueType")

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

151

152

153@export

154class GraphException(ToolingException):

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

156

157

158@export

159class InternalError(GraphException):

160 """

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

162

163 .. danger::

164

165 This exception should never be raised.

166

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

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

169 """

170

171

172@export

173class NotInSameGraph(GraphException):

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

175

176

177@export

178class DuplicateVertexError(GraphException):

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

180

181

182@export

183class DuplicateEdgeError(GraphException):

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

185

186

187@export

188class DestinationNotReachable(GraphException):

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

190

191

192@export

193class NotATreeError(GraphException):

194 """

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

196

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

198 """

199

200

201@export

202class CycleError(GraphException):

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

204

205

206@export

207class Base(

208 Generic[DictKeyType, DictValueType],

209 metaclass=ExtendedType, slots=True

210):

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

212

213 def __init__(

214 self,

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

216 ) -> None:

217 """

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

219

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

221 """

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

223

224 def __del__(self) -> None:

225 """

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

227

228 """

229 try:

230 del self._dict

231 except AttributeError:

232 pass

233

234 def Delete(self) -> None:

235 self._dict = None

236

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

238 """

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

240

241 :param key: The key to look for.

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

243 """

244 return self._dict[key]

245

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

247 """

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

249

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

251

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

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

254 """

255 self._dict[key] = value

256

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

258 """

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

260

261 :param key: The key to remove.

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

263 """

264 del self._dict[key]

265

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

267 """

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

269

270 :param key: The key to check.

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

272 """

273 return key in self._dict

274

275 def __len__(self) -> int:

276 """

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

278

279 :returns: Number of attached attributes.

280 """

281 return len(self._dict)

282

283

284@export

285class BaseWithIDValueAndWeight(

286 Base[DictKeyType, DictValueType],

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

288):

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

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

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

292

293 def __init__(

294 self,

295 identifier: Nullable[IDType] = None,

296 value: Nullable[ValueType] = None,

297 weight: Nullable[WeightType] = None,

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

299 ) -> None:

300 """

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

302

303 :param identifier: The optional unique ID.

304 :param value: The optional value.

305 :param weight: The optional weight.

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

307 """

308 super().__init__(keyValuePairs)

309

310 self._id = identifier

311 self._value = value

312 self._weight = weight

313

314 @readonly

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

316 """

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

318

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

320

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

322 """

323 return self._id

324

325 @property

326 def Value(self) -> ValueType:

327 """

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

329

330 :returns: The value.

331 """

332 return self._value

333

334 @Value.setter

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

336 self._value = value

337

338 @property

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

340 """

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

342

343 :returns: The weight of an edge.

344 """

345 return self._weight

346

347 @Weight.setter

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

349 self._weight = value

350

351

352@export

353class BaseWithName(

354 Base[DictKeyType, DictValueType],

355 Generic[DictKeyType, DictValueType]

356):

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

358

359 def __init__(

360 self,

361 name: Nullable[str] = None,

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

363 ) -> None:

364 """

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

366

367 :param name: The optional name.

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

369 """

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

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

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

373 raise ex

374

375 super().__init__(keyValuePairs)

376

377 self._name = name

378

379 @property

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

381 """

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

383

384 :returns: The value of a component.

385 """

386 return self._name

387

388 @Name.setter

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

390 if not isinstance(value, str):

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

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

393 raise ex

394

395 self._name = value

396

397

398@export

399class BaseWithVertices(

400 BaseWithName[DictKeyType, DictValueType],

401 Generic[

402 DictKeyType, DictValueType,

403 GraphDictKeyType, GraphDictValueType,

404 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,

405 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,

406 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType

407 ]

408):

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

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

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

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

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

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

415 'VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,'

416 'EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,'

417 'LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType'

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

419

420 def __init__(

421 self,

422 graph: 'Graph',

423 name: Nullable[str] = None,

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

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

426 ) -> None:

427 """

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

429

430 :param graph: The reference to the graph.

431 :param name: The optional name.

432 :param vertices: The optional list of vertices.

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

434 """

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

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

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

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

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

440 raise ex

441

442 super().__init__(name, keyValuePairs)

443

444 self._graph = graph

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

446

447 def __del__(self) -> None:

448 """

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

450

451 """

452 try:

453 del self._vertices

454 except AttributeError:

455 pass

456

457 super().__del__()

458

459 @readonly

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

461 """

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

463

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

465 """

466 return self._graph

467

468 @readonly

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

470 """

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

472

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

474 """

475 return self._vertices

476

477 @readonly

478 def VertexCount(self) -> int:

479 """

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

481

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

483 """

484 return len(self._vertices)

485

486

487@export

488class Vertex(

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

490 Generic[

491 GraphDictKeyType, GraphDictValueType,

492 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,

493 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,

494 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType

495 ]

496):

497 """

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

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

500 """

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

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

503 _component: 'Component'

504 _views: Dict[Hashable, 'View']

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

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

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

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

509

510 def __init__(

511 self,

512 vertexID: Nullable[VertexIDType] = None,

513 value: Nullable[VertexValueType] = None,

514 weight: Nullable[VertexWeightType] = None,

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

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

517 subgraph: Nullable['Subgraph'] = None

518 ) -> None:

519 """

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

521

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

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

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

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

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

527 :param subgraph: undocumented

528 """

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

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

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

532 raise ex

533

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

535

536 if subgraph is None:

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

538 self._subgraph = None

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

540

541 if vertexID is None:

542 self._graph._verticesWithoutID.append(self)

543 elif vertexID not in self._graph._verticesWithID:

544 self._graph._verticesWithID[vertexID] = self

545 else:

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

547 else:

548 self._graph = subgraph._graph

549 self._subgraph = subgraph

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

551

552 if vertexID is None:

553 subgraph._verticesWithoutID.append(self)

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

555 subgraph._verticesWithID[vertexID] = self

556 else:

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

558

559 self._views = {}

560 self._inboundEdges = []

561 self._outboundEdges = []

562 self._inboundLinks = []

563 self._outboundLinks = []

564

565 def __del__(self) -> None:

566 """

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

568

569 """

570 try:

571 del self._views

572 del self._inboundEdges

573 del self._outboundEdges

574 del self._inboundLinks

575 del self._outboundLinks

576 except AttributeError:

577 pass

578

579 super().__del__()

580

581 def Delete(self) -> None:

582 for edge in self._outboundEdges:

583 edge._destination._inboundEdges.remove(edge)

584 edge._Delete()

585 for edge in self._inboundEdges:

586 edge._source._outboundEdges.remove(edge)

587 edge._Delete()

588 for link in self._outboundLinks:

589 link._destination._inboundLinks.remove(link)

590 link._Delete()

591 for link in self._inboundLinks:

592 link._source._outboundLinks.remove(link)

593 link._Delete()

594

595 if self._id is None:

596 self._graph._verticesWithoutID.remove(self)

597 else:

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

599

600 # subgraph

601

602 # component

603

604 # views

605 self._views = None

606 self._inboundEdges = None

607 self._outboundEdges = None

608 self._inboundLinks = None

609 self._outboundLinks = None

610

611 super().Delete()

612 assert getrefcount(self) == 1

613

614 @readonly

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

616 """

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

618

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

620 """

621 return self._graph

622

623 @readonly

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

625 """

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

627

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

629 """

630 return self._component

631

632 @readonly

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

634 """

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

636

637 :returns: Tuple of inbound edges.

638 """

639 return tuple(self._inboundEdges)

640

641 @readonly

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

643 """

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

645

646 :returns: Tuple of outbound edges.

647 """

648 return tuple(self._outboundEdges)

649

650 @readonly

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

652 """

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

654

655 :returns: Tuple of inbound links.

656 """

657 return tuple(self._inboundLinks)

658

659 @readonly

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

661 """

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

663

664 :returns: Tuple of outbound links.

665 """

666 return tuple(self._outboundLinks)

667

668 @readonly

669 def EdgeCount(self) -> int:

670 """

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

672

673 :returns: Number of inbound and outbound edges.

674 """

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

676

677 @readonly

678 def InboundEdgeCount(self) -> int:

679 """

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

681

682 :returns: Number of inbound edges.

683 """

684 return len(self._inboundEdges)

685

686 @readonly

687 def OutboundEdgeCount(self) -> int:

688 """

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

690

691 :returns: Number of outbound edges.

692 """

693 return len(self._outboundEdges)

694

695 @readonly

696 def LinkCount(self) -> int:

697 """

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

699

700 :returns: Number of inbound and outbound links.

701 """

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

703

704 @readonly

705 def InboundLinkCount(self) -> int:

706 """

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

708

709 :returns: Number of inbound links.

710 """

711 return len(self._inboundLinks)

712

713 @readonly

714 def OutboundLinkCount(self) -> int:

715 """

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

717

718 :returns: Number of outbound links.

719 """

720 return len(self._outboundLinks)

721

722 @readonly

723 def IsRoot(self) -> bool:

724 """

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

726

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

728

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

730

731 .. seealso::

732

733 :meth:`IsLeaf` |br|

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

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

736 |rarr| Iterate all roots of a graph.

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

738 |rarr| Iterate all leafs of a graph.

739 """

740 return len(self._inboundEdges) == 0

741

742 @readonly

743 def IsLeaf(self) -> bool:

744 """

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

746

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

748

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

750

751 .. seealso::

752

753 :meth:`IsRoot` |br|

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

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

756 |rarr| Iterate all roots of a graph.

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

758 |rarr| Iterate all leafs of a graph.

759 """

760 return len(self._outboundEdges) == 0

761

762 @readonly

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

764 """

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

766

767 :returns: Tuple of predecessor vertices.

768 """

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

770

771 @readonly

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

773 """

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

775

776 :returns: Tuple of successor vertices.

777 """

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

779

780 def EdgeToVertex(

781 self,

782 vertex: 'Vertex',

783 edgeID: Nullable[EdgeIDType] = None,

784 edgeWeight: Nullable[EdgeWeightType] = None,

785 edgeValue: Nullable[VertexValueType] = None,

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

787 ) -> 'Edge':

788 """

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

790

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

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

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

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

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

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

797

798 .. seealso::

799

800 :meth:`EdgeFromVertex` |br|

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

802 :meth:`EdgeToNewVertex` |br|

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

804 :meth:`EdgeFromNewVertex` |br|

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

806 :meth:`LinkToVertex` |br|

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

808 :meth:`LinkFromVertex` |br|

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

810

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

812 """

813 if self._subgraph is vertex._subgraph:

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

815

816 self._outboundEdges.append(edge)

817 vertex._inboundEdges.append(edge)

818

819 if self._subgraph is None:

820 # TODO: move into Edge?

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

822 if edgeID is None:

823 self._graph._edgesWithoutID.append(edge)

824 elif edgeID not in self._graph._edgesWithID:

825 self._graph._edgesWithID[edgeID] = edge

826 else:

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

828 else:

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

830 if edgeID is None:

831 self._subgraph._edgesWithoutID.append(edge)

832 elif edgeID not in self._subgraph._edgesWithID:

833 self._subgraph._edgesWithID[edgeID] = edge

834 else:

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

836 else:

837 # FIXME: needs an error message

838 raise GraphException()

839

840 return edge

841

842 def EdgeFromVertex(

843 self,

844 vertex: 'Vertex',

845 edgeID: Nullable[EdgeIDType] = None,

846 edgeWeight: Nullable[EdgeWeightType] = None,

847 edgeValue: Nullable[VertexValueType] = None,

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

849 ) -> 'Edge':

850 """

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

852

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

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

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

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

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

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

859

860 .. seealso::

861

862 :meth:`EdgeToVertex` |br|

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

864 :meth:`EdgeToNewVertex` |br|

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

866 :meth:`EdgeFromNewVertex` |br|

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

868 :meth:`LinkToVertex` |br|

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

870 :meth:`LinkFromVertex` |br|

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

872

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

874 """

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

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

877

878 vertex._outboundEdges.append(edge)

879 self._inboundEdges.append(edge)

880

881 if self._subgraph is None:

882 # TODO: move into Edge?

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

884 if edgeID is None:

885 self._graph._edgesWithoutID.append(edge)

886 elif edgeID not in self._graph._edgesWithID:

887 self._graph._edgesWithID[edgeID] = edge

888 else:

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

890 else:

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

892 if edgeID is None:

893 self._subgraph._edgesWithoutID.append(edge)

894 elif edgeID not in self._graph._edgesWithID:

895 self._subgraph._edgesWithID[edgeID] = edge

896 else:

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

898 else:

899 # FIXME: needs an error message

900 raise GraphException()

901

902 return edge

903

904 def EdgeToNewVertex(

905 self,

906 vertexID: Nullable[VertexIDType] = None,

907 vertexValue: Nullable[VertexValueType] = None,

908 vertexWeight: Nullable[VertexWeightType] = None,

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

910 edgeID: Nullable[EdgeIDType] = None,

911 edgeWeight: Nullable[EdgeWeightType] = None,

912 edgeValue: Nullable[VertexValueType] = None,

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

914 ) -> 'Edge':

915 """

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

917

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

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

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

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

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

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

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

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

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

927

928 .. seealso::

929

930 :meth:`EdgeToVertex` |br|

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

932 :meth:`EdgeFromVertex` |br|

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

934 :meth:`EdgeFromNewVertex` |br|

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

936 :meth:`LinkToVertex` |br|

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

938 :meth:`LinkFromVertex` |br|

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

940

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

942 """

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

944

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

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

947

948 self._outboundEdges.append(edge)

949 vertex._inboundEdges.append(edge)

950

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

952 # TODO: move into Edge?

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

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

955 self._graph._edgesWithoutID.append(edge)

956 elif edgeID not in self._graph._edgesWithID:

957 self._graph._edgesWithID[edgeID] = edge

958 else:

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

960 else:

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

962 if edgeID is None:

963 self._subgraph._edgesWithoutID.append(edge)

964 elif edgeID not in self._graph._edgesWithID:

965 self._subgraph._edgesWithID[edgeID] = edge

966 else:

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

968 else:

969 # FIXME: needs an error message

970 raise GraphException()

971

972 return edge

973

974 def EdgeFromNewVertex(

975 self,

976 vertexID: Nullable[VertexIDType] = None,

977 vertexValue: Nullable[VertexValueType] = None,

978 vertexWeight: Nullable[VertexWeightType] = None,

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

980 edgeID: Nullable[EdgeIDType] = None,

981 edgeWeight: Nullable[EdgeWeightType] = None,

982 edgeValue: Nullable[VertexValueType] = None,

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

984 ) -> 'Edge':

985 """

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

987

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

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

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

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

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

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

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

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

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

997

998 .. seealso::

999

1000 :meth:`EdgeToVertex` |br|

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

1002 :meth:`EdgeFromVertex` |br|

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

1004 :meth:`EdgeToNewVertex` |br|

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

1006 :meth:`LinkToVertex` |br|

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

1008 :meth:`LinkFromVertex` |br|

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

1010

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

1012 """

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

1014

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

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

1017

1018 vertex._outboundEdges.append(edge)

1019 self._inboundEdges.append(edge)

1020

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

1022 # TODO: move into Edge?

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

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

1025 self._graph._edgesWithoutID.append(edge)

1026 elif edgeID not in self._graph._edgesWithID:

1027 self._graph._edgesWithID[edgeID] = edge

1028 else:

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

1030 else:

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

1032 if edgeID is None:

1033 self._subgraph._edgesWithoutID.append(edge)

1034 elif edgeID not in self._graph._edgesWithID:

1035 self._subgraph._edgesWithID[edgeID] = edge

1036 else:

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

1038 else:

1039 # FIXME: needs an error message

1040 raise GraphException()

1041

1042 return edge

1043

1044 def LinkToVertex(

1045 self,

1046 vertex: 'Vertex',

1047 linkID: Nullable[EdgeIDType] = None,

1048 linkWeight: Nullable[EdgeWeightType] = None,

1049 linkValue: Nullable[VertexValueType] = None,

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

1051 ) -> 'Link':

1052 """

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

1054

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

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

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

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

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

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

1061

1062 .. seealso::

1063

1064 :meth:`EdgeToVertex` |br|

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

1066 :meth:`EdgeFromVertex` |br|

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

1068 :meth:`EdgeToNewVertex` |br|

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

1070 :meth:`EdgeFromNewVertex` |br|

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

1072 :meth:`LinkFromVertex` |br|

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

1074

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

1076 """

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

1078 # FIXME: needs an error message

1079 raise GraphException()

1080 else:

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

1082

1083 self._outboundLinks.append(link)

1084 vertex._inboundLinks.append(link)

1085

1086 if self._subgraph is None:

1087 # TODO: move into Edge?

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

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

1090 self._graph._linksWithoutID.append(link)

1091 elif linkID not in self._graph._linksWithID:

1092 self._graph._linksWithID[linkID] = link

1093 else:

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

1095 else:

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

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

1098 self._subgraph._linksWithoutID.append(link)

1099 vertex._subgraph._linksWithoutID.append(link)

1100 elif linkID not in self._graph._linksWithID:

1101 self._subgraph._linksWithID[linkID] = link

1102 vertex._subgraph._linksWithID[linkID] = link

1103 else:

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

1105

1106 return link

1107

1108 def LinkFromVertex(

1109 self,

1110 vertex: 'Vertex',

1111 linkID: Nullable[EdgeIDType] = None,

1112 linkWeight: Nullable[EdgeWeightType] = None,

1113 linkValue: Nullable[VertexValueType] = None,

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

1115 ) -> 'Edge':

1116 """

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

1118

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

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

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

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

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

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

1125

1126 .. seealso::

1127

1128 :meth:`EdgeToVertex` |br|

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

1130 :meth:`EdgeFromVertex` |br|

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

1132 :meth:`EdgeToNewVertex` |br|

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

1134 :meth:`EdgeFromNewVertex` |br|

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

1136 :meth:`LinkToVertex` |br|

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

1138

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

1140 """

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

1142 # FIXME: needs an error message

1143 raise GraphException()

1144 else:

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

1146

1147 vertex._outboundLinks.append(link)

1148 self._inboundLinks.append(link)

1149

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

1151 # TODO: move into Edge?

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

1153 if linkID is None:

1154 self._graph._linksWithoutID.append(link)

1155 elif linkID not in self._graph._linksWithID:

1156 self._graph._linksWithID[linkID] = link

1157 else:

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

1159 else:

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

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

1162 self._subgraph._linksWithoutID.append(link)

1163 vertex._subgraph._linksWithoutID.append(link)

1164 elif linkID not in self._graph._linksWithID:

1165 self._subgraph._linksWithID[linkID] = link

1166 vertex._subgraph._linksWithID[linkID] = link

1167 else:

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

1169

1170 return link

1171

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

1173 """

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

1175

1176 :param destination: Destination vertex to check.

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

1178

1179 .. seealso::

1180

1181 :meth:`HasEdgeFromSource` |br|

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

1183 :meth:`HasLinkToDestination` |br|

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

1185 :meth:`HasLinkFromSource` |br|

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

1187 """

1188 for edge in self._outboundEdges:

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

1190 return True

1191

1192 return False

1193

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

1195 """

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

1197

1198 :param source: Source vertex to check.

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

1200

1201 .. seealso::

1202

1203 :meth:`HasEdgeToDestination` |br|

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

1205 :meth:`HasLinkToDestination` |br|

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

1207 :meth:`HasLinkFromSource` |br|

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

1209 """

1210 for edge in self._inboundEdges:

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

1212 return True

1213

1214 return False

1215

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

1217 """

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

1219

1220 :param destination: Destination vertex to check.

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

1222

1223 .. seealso::

1224

1225 :meth:`HasEdgeToDestination` |br|

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

1227 :meth:`HasEdgeFromSource` |br|

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

1229 :meth:`HasLinkFromSource` |br|

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

1231 """

1232 for link in self._outboundLinks:

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

1234 return True

1235

1236 return False

1237

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

1239 """

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

1241

1242 :param source: Source vertex to check.

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

1244

1245 .. seealso::

1246

1247 :meth:`HasEdgeToDestination` |br|

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

1249 :meth:`HasEdgeFromSource` |br|

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

1251 :meth:`HasLinkToDestination` |br|

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

1253 """

1254 for link in self._inboundLinks:

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

1256 return True

1257

1258 return False

1259

1260 def DeleteEdgeTo(self, destination: 'Vertex') -> None:

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

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

1263 break

1264 else:

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

1266

1267 edge.Delete()

1268

1269 def DeleteEdgeFrom(self, source: 'Vertex') -> None:

1270 for edge in self._inboundEdges:

1271 if edge._source is source:

1272 break

1273 else:

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

1275

1276 edge.Delete()

1277

1278 def DeleteLinkTo(self, destination: 'Vertex') -> None:

1279 for link in self._outboundLinks:

1280 if link._destination is destination:

1281 break

1282 else:

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

1284

1285 link.Delete()

1286

1287 def DeleteLinkFrom(self, source: 'Vertex') -> None:

1288 for link in self._inboundLinks:

1289 if link._source is source:

1290 break

1291 else:

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

1293

1294 link.Delete()

1295

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

1297 """

1298 Creates a copy of this vertex in another graph.

1299

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

1301 can be established.

1302

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

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

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

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

1307 :returns: The newly created vertex.

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

1309 """

1310 if graph is self._graph:

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

1312

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

1314 if copyDict:

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

1316

1317 if linkingKeyToOriginalVertex is not None:

1318 vertex._dict[linkingKeyToOriginalVertex] = self

1319 if linkingKeyFromOriginalVertex is not None:

1320 self._dict[linkingKeyFromOriginalVertex] = vertex

1321

1322 return vertex

1323

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

1325 """

1326 Iterate all or selected outbound edges of this vertex.

1327

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

1329

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

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

1332 """

1333 if predicate is None:

1334 for edge in self._outboundEdges:

1335 yield edge

1336 else:

1337 for edge in self._outboundEdges:

1338 if predicate(edge):

1339 yield edge

1340

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

1342 """

1343 Iterate all or selected inbound edges of this vertex.

1344

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

1346

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

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

1349 """

1350 if predicate is None:

1351 for edge in self._inboundEdges:

1352 yield edge

1353 else:

1354 for edge in self._inboundEdges:

1355 if predicate(edge):

1356 yield edge

1357

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

1359 """

1360 Iterate all or selected outbound links of this vertex.

1361

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

1363

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

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

1366 """

1367 if predicate is None:

1368 for link in self._outboundLinks:

1369 yield link

1370 else:

1371 for link in self._outboundLinks:

1372 if predicate(link):

1373 yield link

1374

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

1376 """

1377 Iterate all or selected inbound links of this vertex.

1378

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

1380

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

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

1383 """

1384 if predicate is None:

1385 for link in self._inboundLinks:

1386 yield link

1387 else:

1388 for link in self._inboundLinks:

1389 if predicate(link):

1390 yield link

1391

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

1393 """

1394 Iterate all or selected successor vertices of this vertex.

1395

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

1397

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

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

1400 """

1401 if predicate is None:

1402 for edge in self._outboundEdges:

1403 yield edge.Destination

1404 else:

1405 for edge in self._outboundEdges:

1406 if predicate(edge):

1407 yield edge.Destination

1408

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

1410 """

1411 Iterate all or selected predecessor vertices of this vertex.

1412

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

1414

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

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

1417 """

1418 if predicate is None:

1419 for edge in self._inboundEdges:

1420 yield edge.Source

1421 else:

1422 for edge in self._inboundEdges:

1423 if predicate(edge):

1424 yield edge.Source

1425

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

1427 """

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

1429

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

1431

1432 .. seealso::

1433

1434 :meth:`IterateVerticesDFS` |br|

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

1436 """

1437 visited: Set[Vertex] = set()

1438 queue: Deque[Vertex] = deque()

1439

1440 yield self

1441 visited.add(self)

1442 for edge in self._outboundEdges:

1443 nextVertex = edge.Destination

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

1445 queue.appendleft(nextVertex)

1446 visited.add(nextVertex)

1447

1448 while queue:

1449 vertex = queue.pop()

1450 yield vertex

1451 for edge in vertex._outboundEdges:

1452 nextVertex = edge.Destination

1453 if nextVertex not in visited:

1454 queue.appendleft(nextVertex)

1455 visited.add(nextVertex)

1456

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

1458 """

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

1460

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

1462

1463 .. seealso::

1464

1465 :meth:`IterateVerticesBFS` |br|

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

1467

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

1469 """

1470 visited: Set[Vertex] = set()

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

1472

1473 yield self

1474 visited.add(self)

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

1476

1477 while True:

1478 try:

1479 edge = next(stack[-1])

1480 nextVertex = edge._destination

1481 if nextVertex not in visited:

1482 visited.add(nextVertex)

1483 yield nextVertex

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

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

1486 except StopIteration:

1487 stack.pop()

1488

1489 if len(stack) == 0:

1490 return

1491

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

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

1494 yield (self, )

1495 return

1496

1497 visited: Set[Vertex] = set()

1498 vertexStack: List[Vertex] = list()

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

1500

1501 visited.add(self)

1502 vertexStack.append(self)

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

1504

1505 while True:

1506 try:

1507 edge = next(iteratorStack[-1])

1508 nextVertex = edge._destination

1509 if nextVertex in visited:

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

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

1512 for i, vertex in enumerate(vertexStack):

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

1514 raise ex

1515

1516 vertexStack.append(nextVertex)

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

1518 yield tuple(vertexStack)

1519 vertexStack.pop()

1520 else:

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

1522

1523 except StopIteration:

1524 vertexStack.pop()

1525 iteratorStack.pop()

1526

1527 if len(vertexStack) == 0:

1528 return

1529

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

1531 """

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

1533

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

1535

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

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

1538

1539 :param destination: The destination vertex to reach.

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

1541 """

1542 # Trivial case if start is destination

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

1544 yield self

1545 return

1546

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

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

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

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

1551 parent: 'Node'

1552 ref: Vertex

1553

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

1555 self.parent = parent

1556 self.ref = ref

1557

1558 def __str__(self):

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

1560

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

1562 startNode = Node(None, self)

1563 visited: Set[Vertex] = set()

1564 queue: Deque[Node] = deque()

1565

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

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

1568 visited.add(self)

1569 for edge in self._outboundEdges:

1570 nextVertex = edge.Destination

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

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

1573 destinationNode = Node(startNode, nextVertex)

1574 break

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

1576 # Ignore backward-edges and side-edges.

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

1578 visited.add(nextVertex)

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

1580 else:

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

1582 while queue:

1583 node = queue.pop()

1584 for edge in node.ref._outboundEdges:

1585 nextVertex = edge.Destination

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

1587 if nextVertex is destination:

1588 destinationNode = Node(node, nextVertex)

1589 break

1590 # Ignore backward-edges and side-edges.

1591 if nextVertex not in visited:

1592 visited.add(nextVertex)

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

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

1595 else:

1596 continue

1597 break

1598 else:

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

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

1601

1602 # Reverse order of linked list from destinationNode to startNode

1603 currentNode = destinationNode

1604 previousNode = destinationNode.parent

1605 currentNode.parent = None

1606 while previousNode is not None:

1607 node = previousNode.parent

1608 previousNode.parent = currentNode

1609 currentNode = previousNode

1610 previousNode = node

1611

1612 # Scan reversed linked-list and yield referenced vertices

1613 yield startNode.ref

1614 node = startNode.parent

1615 while node is not None:

1616 yield node.ref

1617 node = node.parent

1618

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

1620 """

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

1622

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

1624

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

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

1627

1628 :param destination: The destination vertex to reach.

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

1630 """

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

1632

1633 # Trivial case if start is destination

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

1635 yield self

1636 return

1637

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

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

1640 # represents.

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

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

1643 parent: 'Node'

1644 distance: EdgeWeightType

1645 ref: Vertex

1646

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

1648 self.parent = parent

1649 self.distance = distance

1650 self.ref = ref

1651

1652 def __lt__(self, other):

1653 return self.distance < other.distance

1654

1655 def __str__(self):

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

1657

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

1659 startNode = Node(None, 0, self)

1660 priorityQueue = [startNode]

1661

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

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

1664 visited.add(self)

1665 for edge in self._outboundEdges:

1666 nextVertex = edge.Destination

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

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

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

1670 break

1671 # Ignore backward-edges and side-edges.

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

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

1674 visited.add(nextVertex)

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

1676 else:

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

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

1679 node = heapq.heappop(priorityQueue)

1680 for edge in node.ref._outboundEdges:

1681 nextVertex = edge.Destination

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

1683 if nextVertex is destination:

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

1685 break

1686 # Ignore backward-edges and side-edges.

1687 if nextVertex not in visited:

1688 visited.add(nextVertex)

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

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

1691 else:

1692 continue

1693 break

1694 else:

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

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

1697

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

1699 currentNode = destinationNode

1700 previousNode = destinationNode.parent

1701 currentNode.parent = None

1702 while previousNode is not None:

1703 node = previousNode.parent

1704 previousNode.parent = currentNode

1705 currentNode = previousNode

1706 previousNode = node

1707

1708 # Scan reversed linked-list and yield referenced vertices

1709 yield startNode.ref, startNode.distance

1710 node = startNode.parent

1711 while node is not None:

1712 yield node.ref, node.distance

1713 node = node.parent

1714

1715 # Other possible algorithms:

1716 # * Bellman-Ford

1717 # * Floyd-Warshall

1718

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

1720 # raise NotImplementedError()

1721 # # DFS

1722 # # Union find

1723 #

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

1725 # raise NotImplementedError()

1726 # # Ford-Fulkerson algorithm

1727 # # Edmons-Karp algorithm

1728 # # Dinic's algorithm

1729

1730 def ConvertToTree(self) -> Node:

1731 """

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

1733

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

1735

1736 :returns:

1737 """

1738 visited: Set[Vertex] = set()

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

1740

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

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

1743

1744 visited.add(self)

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

1746

1747 while True:

1748 try:

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

1750 nextVertex = edge._destination

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

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

1753 visited.add(nextVertex)

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

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

1756 else:

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

1758 # TODO: compute cycle:

1759 # a) branch 1 is described in stack

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

1761 except StopIteration:

1762 stack.pop()

1763

1764 if len(stack) == 0:

1765 return root

1766

1767 def __repr__(self) -> str:

1768 """

1769 Returns a detailed string representation of the vertex.

1770

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

1772 """

1773 vertexID = value = ""

1774 sep = ": "

1775 if self._id is not None:

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

1777 sep = "; "

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

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

1780

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

1782

1783 def __str__(self) -> str:

1784 """

1785 Return a string representation of the vertex.

1786

1787 Order of resolution:

1788

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

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

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

1792

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

1794 """

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

1796 return str(self._value)

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

1798 return str(self._id)

1799 else:

1800 return self.__repr__()

1801

1802

1803@export

1804class BaseEdge(

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

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

1807):

1808 """

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

1810 directed.

1811 """

1812 _source: Vertex

1813 _destination: Vertex

1814

1815 def __init__(

1816 self,

1817 source: Vertex,

1818 destination: Vertex,

1819 edgeID: Nullable[EdgeIDType] = None,

1820 value: Nullable[EdgeValueType] = None,

1821 weight: Nullable[EdgeWeightType] = None,

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

1823 ) -> None:

1824 """

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

1826

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

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

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

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

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

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

1833 """

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

1835

1836 self._source = source

1837 self._destination = destination

1838

1839 component = source._component

1840 if component is not destination._component:

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

1842 oldComponent = destination._component

1843 for vertex in oldComponent._vertices:

1844 vertex._component = component

1845 component._vertices.add(vertex)

1846 component._graph._components.remove(oldComponent)

1847 del oldComponent

1848

1849 @readonly

1850 def Source(self) -> Vertex:

1851 """

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

1853

1854 :returns: The source of an edge.

1855 """

1856 return self._source

1857

1858 @readonly

1859 def Destination(self) -> Vertex:

1860 """

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

1862

1863 :returns: The destination of an edge.

1864 """

1865 return self._destination

1866

1867 def Reverse(self) -> None:

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

1869 swap = self._source

1870 self._source = self._destination

1871 self._destination = swap

1872

1873

1874@export

1875class Edge(

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

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

1878):

1879 """

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

1881 directed.

1882 """

1883

1884 def __init__(

1885 self,

1886 source: Vertex,

1887 destination: Vertex,

1888 edgeID: Nullable[EdgeIDType] = None,

1889 value: Nullable[EdgeValueType] = None,

1890 weight: Nullable[EdgeWeightType] = None,

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

1892 ) -> None:

1893 """

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

1895

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

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

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

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

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

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

1902 """

1903 if not isinstance(source, Vertex):

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

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

1906 raise ex

1907 if not isinstance(destination, Vertex):

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

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

1910 raise ex

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

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

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

1914 raise ex

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

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

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

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

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

1920 raise ex

1921 if source._graph is not destination._graph:

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

1923

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

1925

1926 def Delete(self) -> None:

1927 # Remove from Source and Destination

1928 self._source._outboundEdges.remove(self)

1929 self._destination._inboundEdges.remove(self)

1930

1931 # Remove from Graph and Subgraph

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

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

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

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

1936 else:

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

1938 if self._source._subgraph is not None:

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

1940

1941 self._Delete()

1942

1943 def _Delete(self) -> None:

1944 super().Delete()

1945

1946 def Reverse(self) -> None:

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

1948 self._source._outboundEdges.remove(self)

1949 self._source._inboundEdges.append(self)

1950 self._destination._inboundEdges.remove(self)

1951 self._destination._outboundEdges.append(self)

1952

1953 super().Reverse()

1954

1955

1956@export

1957class Link(

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

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

1960):

1961 """

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

1963 directed.

1964 """

1965

1966 def __init__(

1967 self,

1968 source: Vertex,

1969 destination: Vertex,

1970 linkID: LinkIDType = None,

1971 value: LinkValueType = None,

1972 weight: Nullable[LinkWeightType] = None,

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

1974 ) -> None:

1975 """

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

1977

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

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

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

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

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

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

1984 """

1985 if not isinstance(source, Vertex):

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

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

1988 raise ex

1989 if not isinstance(destination, Vertex):

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

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

1992 raise ex

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

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

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

1996 raise ex

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

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

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

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

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

2002 raise ex

2003 if source._graph is not destination._graph:

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

2005

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

2007

2008 def Delete(self) -> None:

2009 self._source._outboundEdges.remove(self)

2010 self._destination._inboundEdges.remove(self)

2011

2012 if self._id is None:

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

2014 else:

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

2016

2017 self._Delete()

2018 assert getrefcount(self) == 1

2019

2020 def _Delete(self) -> None:

2021 super().Delete()

2022

2023 def Reverse(self) -> None:

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

2025 self._source._outboundEdges.remove(self)

2026 self._source._inboundEdges.append(self)

2027 self._destination._inboundEdges.remove(self)

2028 self._destination._outboundEdges.append(self)

2029

2030 super().Reverse()

2031

2032

2033@export

2034class BaseGraph(

2035 BaseWithName[GraphDictKeyType, GraphDictValueType],

2036 Generic[

2037 GraphDictKeyType, GraphDictValueType,

2038 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,

2039 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,

2040 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType

2041 ]

2042):

2043 """

2044 .. todo:: GRAPH::BaseGraph Needs documentation.

2045

2046 """

2047

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

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

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

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

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

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

2054

2055 def __init__(

2056 self,

2057 name: Nullable[str] = None,

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

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

2060 ) -> None:

2061 """

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

2063

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

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

2066 """

2067 super().__init__(name, keyValuePairs)

2068

2069 self._verticesWithoutID = []

2070 self._verticesWithID = {}

2071 self._edgesWithoutID = []

2072 self._edgesWithID = {}

2073 self._linksWithoutID = []

2074 self._linksWithID = {}

2075

2076 def __del__(self) -> None:

2077 """

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

2079

2080 """

2081 try:

2082 del self._verticesWithoutID

2083 del self._verticesWithID

2084 del self._edgesWithoutID

2085 del self._edgesWithID

2086 del self._linksWithoutID

2087 del self._linksWithID

2088 except AttributeError:

2089 pass

2090

2091 super().__del__()

2092

2093 @readonly

2094 def VertexCount(self) -> int:

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

2096

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

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

2099

2100 @readonly

2101 def EdgeCount(self) -> int:

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

2103

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

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

2106

2107 @readonly

2108 def LinkCount(self) -> int:

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

2110

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

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

2113

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

2115 """

2116 Iterate all or selected vertices of a graph.

2117

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

2119

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

2121 :returns: A generator to iterate all vertices.

2122 """

2123 if predicate is None:

2124 yield from self._verticesWithoutID

2125 yield from self._verticesWithID.values()

2126

2127 else:

2128 for vertex in self._verticesWithoutID:

2129 if predicate(vertex):

2130 yield vertex

2131

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

2133 if predicate(vertex):

2134 yield vertex

2135

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

2137 """

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

2139

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

2141

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

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

2144

2145 .. seealso::

2146

2147 :meth:`IterateLeafs` |br|

2148 |rarr| Iterate leafs of a graph.

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

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

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

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

2153 """

2154 if predicate is None:

2155 for vertex in self._verticesWithoutID:

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

2157 yield vertex

2158

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

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

2161 yield vertex

2162 else:

2163 for vertex in self._verticesWithoutID:

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

2165 yield vertex

2166

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

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

2169 yield vertex

2170

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

2172 """

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

2174

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

2176

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

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

2179

2180 .. seealso::

2181

2182 :meth:`IterateRoots` |br|

2183 |rarr| Iterate roots of a graph.

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

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

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

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

2188 """

2189 if predicate is None:

2190 for vertex in self._verticesWithoutID:

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

2192 yield vertex

2193

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

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

2196 yield vertex

2197 else:

2198 for vertex in self._verticesWithoutID:

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

2200 yield vertex

2201

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

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

2204 yield vertex

2205

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

2207 # raise NotImplementedError()

2208 #

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

2210 # raise NotImplementedError()

2211

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

2213 """

2214 Iterate all or selected vertices in topological order.

2215

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

2217

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

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

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

2221 """

2222 outboundEdgeCounts = {}

2223 leafVertices = []

2224

2225 for vertex in self._verticesWithoutID:

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

2227 leafVertices.append(vertex)

2228 else:

2229 outboundEdgeCounts[vertex] = count

2230

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

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

2233 leafVertices.append(vertex)

2234 else:

2235 outboundEdgeCounts[vertex] = count

2236

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

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

2239

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

2241

2242 def removeVertex(vertex: Vertex):

2243 nonlocal overallCount

2244 overallCount -= 1

2245 for inboundEdge in vertex._inboundEdges:

2246 sourceVertex = inboundEdge.Source

2247 count = outboundEdgeCounts[sourceVertex] - 1

2248 outboundEdgeCounts[sourceVertex] = count

2249 if count == 0:

2250 leafVertices.append(sourceVertex)

2251

2252 if predicate is None:

2253 for vertex in leafVertices:

2254 yield vertex

2255

2256 removeVertex(vertex)

2257 else:

2258 for vertex in leafVertices:

2259 if predicate(vertex):

2260 yield vertex

2261

2262 removeVertex(vertex)

2263

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

2265 return

2266 elif overallCount > 0:

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

2268

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

2270

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

2272 """

2273 Iterate all or selected edges of a graph.

2274

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

2276

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

2278 :returns: A generator to iterate all edges.

2279 """

2280 if predicate is None:

2281 yield from self._edgesWithoutID

2282 yield from self._edgesWithID.values()

2283

2284 else:

2285 for edge in self._edgesWithoutID:

2286 if predicate(edge):

2287 yield edge

2288

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

2290 if predicate(edge):

2291 yield edge

2292

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

2294 """

2295 Iterate all or selected links of a graph.

2296

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

2298

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

2300 :returns: A generator to iterate all links.

2301 """

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

2303 yield from self._linksWithoutID

2304 yield from self._linksWithID.values()

2305

2306 else:

2307 for link in self._linksWithoutID:

2308 if predicate(link):

2309 yield link

2310

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

2312 if predicate(link):

2313 yield link

2314

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

2316 """

2317 Reverse all or selected edges of a graph.

2318

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

2320

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

2322 """

2323 if predicate is None:

2324 for edge in self._edgesWithoutID:

2325 swap = edge._source

2326 edge._source = edge._destination

2327 edge._destination = swap

2328

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

2330 swap = edge._source

2331 edge._source = edge._destination

2332 edge._destination = swap

2333

2334 for vertex in self._verticesWithoutID:

2335 swap = vertex._inboundEdges

2336 vertex._inboundEdges = vertex._outboundEdges

2337 vertex._outboundEdges = swap

2338

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

2340 swap = vertex._inboundEdges

2341 vertex._inboundEdges = vertex._outboundEdges

2342 vertex._outboundEdges = swap

2343 else:

2344 for edge in self._edgesWithoutID:

2345 if predicate(edge):

2346 edge.Reverse()

2347

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

2349 if predicate(edge):

2350 edge.Reverse()

2351

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

2353 """

2354 Reverse all or selected links of a graph.

2355

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

2357

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

2359 """

2360 if predicate is None:

2361 for link in self._linksWithoutID:

2362 swap = link._source

2363 link._source = link._destination

2364 link._destination = swap

2365

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

2367 swap = link._source

2368 link._source = link._destination

2369 link._destination = swap

2370

2371 for vertex in self._verticesWithoutID:

2372 swap = vertex._inboundLinks

2373 vertex._inboundLinks = vertex._outboundLinks

2374 vertex._outboundLinks = swap

2375

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

2377 swap = vertex._inboundLinks

2378 vertex._inboundLinks = vertex._outboundLinks

2379 vertex._outboundLinks = swap

2380 else:

2381 for link in self._linksWithoutID:

2382 if predicate(link):

2383 link.Reverse()

2384

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

2386 if predicate(link):

2387 link.Reverse()

2388

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

2390 """

2391 Remove all or selected edges of a graph.

2392

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

2394

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

2396 """

2397 if predicate is None:

2398 for edge in self._edgesWithoutID:

2399 edge._Delete()

2400

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

2402 edge._Delete()

2403

2404 self._edgesWithoutID = []

2405 self._edgesWithID = {}

2406

2407 for vertex in self._verticesWithoutID:

2408 vertex._inboundEdges = []

2409 vertex._outboundEdges = []

2410

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

2412 vertex._inboundEdges = []

2413 vertex._outboundEdges = []

2414

2415 else:

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

2417 for edge in delEdges:

2418 del self._edgesWithID[edge._id]

2419

2420 edge._source._outboundEdges.remove(edge)

2421 edge._destination._inboundEdges.remove(edge)

2422 edge._Delete()

2423

2424 for edge in self._edgesWithoutID:

2425 if predicate(edge):

2426 self._edgesWithoutID.remove(edge)

2427

2428 edge._source._outboundEdges.remove(edge)

2429 edge._destination._inboundEdges.remove(edge)

2430 edge._Delete()

2431

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

2433 """

2434 Remove all or selected links of a graph.

2435

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

2437

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

2439 """

2440 if predicate is None:

2441 for link in self._linksWithoutID:

2442 link._Delete()

2443

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

2445 link._Delete()

2446

2447 self._linksWithoutID = []

2448 self._linksWithID = {}

2449

2450 for vertex in self._verticesWithoutID:

2451 vertex._inboundLinks = []

2452 vertex._outboundLinks = []

2453

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

2455 vertex._inboundLinks = []

2456 vertex._outboundLinks = []

2457

2458 else:

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

2460 for link in delLinks:

2461 del self._linksWithID[link._id]

2462

2463 link._source._outboundLinks.remove(link)

2464 link._destination._inboundLinks.remove(link)

2465 link._Delete()

2466

2467 for link in self._linksWithoutID:

2468 if predicate(link):

2469 self._linksWithoutID.remove(link)

2470

2471 link._source._outboundLinks.remove(link)

2472 link._destination._inboundLinks.remove(link)

2473 link._Delete()

2474

2475 def HasCycle(self) -> bool:

2476 """

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

2478

2479 """

2480 # IsAcyclic ?

2481

2482 # Handle trivial case if graph is empty

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

2484 return False

2485

2486 outboundEdgeCounts = {}

2487 leafVertices = []

2488

2489 for vertex in self._verticesWithoutID:

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

2491 leafVertices.append(vertex)

2492 else:

2493 outboundEdgeCounts[vertex] = count

2494

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

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

2497 leafVertices.append(vertex)

2498 else:

2499 outboundEdgeCounts[vertex] = count

2500

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

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

2503 return True

2504

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

2506

2507 for vertex in leafVertices:

2508 overallCount -= 1

2509 for inboundEdge in vertex._inboundEdges:

2510 sourceVertex = inboundEdge.Source

2511 count = outboundEdgeCounts[sourceVertex] - 1

2512 outboundEdgeCounts[sourceVertex] = count

2513 if count == 0:

2514 leafVertices.append(sourceVertex)

2515

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

2517 if overallCount == 0:

2518 return False

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

2520 elif overallCount > 0:

2521 return True

2522

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

2524

2525

2526@export

2527class Subgraph(

2528 BaseGraph[

2529 SubgraphDictKeyType, SubgraphDictValueType,

2530 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,

2531 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,

2532 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType

2533 ],

2534 Generic[

2535 SubgraphDictKeyType, SubgraphDictValueType,

2536 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,

2537 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,

2538 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType

2539 ]

2540):

2541 """

2542 .. todo:: GRAPH::Subgraph Needs documentation.

2543

2544 """

2545

2546 _graph: 'Graph'

2547

2548 def __init__(

2549 self,

2550 graph: 'Graph',

2551 name: Nullable[str] = None,

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

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

2554 ) -> None:

2555 """

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

2557

2558 :param graph: The reference to the graph.

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

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

2561 """

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

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

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

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

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

2567 raise ex

2568

2569 super().__init__(name, keyValuePairs)

2570

2571 graph._subgraphs.add(self)

2572

2573 self._graph = graph

2574

2575 def __del__(self) -> None:

2576 """

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

2578

2579 """

2580 super().__del__()

2581

2582 @readonly

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

2584 """

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

2586

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

2588 """

2589 return self._graph

2590

2591 def __str__(self) -> str:

2592 """

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

2594

2595 """

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

2597

2598

2599@export

2600class View(

2601 BaseWithVertices[

2602 ViewDictKeyType, ViewDictValueType,

2603 GraphDictKeyType, GraphDictValueType,

2604 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,

2605 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,

2606 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType

2607 ],

2608 Generic[

2609 ViewDictKeyType, ViewDictValueType,

2610 GraphDictKeyType, GraphDictValueType,

2611 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,

2612 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,

2613 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType

2614 ]

2615):

2616 """

2617 .. todo:: GRAPH::View Needs documentation.

2618

2619 """

2620

2621 def __init__(

2622 self,

2623 graph: 'Graph',

2624 name: Nullable[str] = None,

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

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

2627 ) -> None:

2628 """

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

2630

2631 :param graph: The reference to the graph.

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

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

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

2635 """

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

2637

2638 graph._views.add(self)

2639

2640 def __del__(self) -> None:

2641 """

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

2643

2644 """

2645 super().__del__()

2646

2647 def __str__(self) -> str:

2648 """

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

2650

2651 """

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

2653

2654

2655@export

2656class Component(

2657 BaseWithVertices[

2658 ComponentDictKeyType, ComponentDictValueType,

2659 GraphDictKeyType, GraphDictValueType,

2660 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,

2661 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,

2662 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType

2663 ],

2664 Generic[

2665 ComponentDictKeyType, ComponentDictValueType,

2666 GraphDictKeyType, GraphDictValueType,

2667 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,

2668 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,

2669 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType

2670 ]

2671):

2672 """

2673 .. todo:: GRAPH::Component Needs documentation.

2674

2675 """

2676

2677 def __init__(

2678 self,

2679 graph: 'Graph',

2680 name: Nullable[str] = None,

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

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

2683 ) -> None:

2684 """

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

2686

2687 :param graph: The reference to the graph.

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

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

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

2691 """

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

2693

2694 graph._components.add(self)

2695

2696 def __del__(self) -> None:

2697 """

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

2699

2700 """

2701 super().__del__()

2702

2703 def __str__(self) -> str:

2704 """

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

2706

2707 """

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

2709

2710

2711@export

2712class Graph(

2713 BaseGraph[

2714 GraphDictKeyType, GraphDictValueType,

2715 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,

2716 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,

2717 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType

2718 ],

2719 Generic[

2720 GraphDictKeyType, GraphDictValueType,

2721 ComponentDictKeyType, ComponentDictValueType,

2722 SubgraphDictKeyType, SubgraphDictValueType,

2723 ViewDictKeyType, ViewDictValueType,

2724 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,

2725 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,

2726 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType

2727 ]

2728):

2729 """

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

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

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

2733 """

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

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

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

2737

2738 def __init__(

2739 self,

2740 name: Nullable[str] = None,

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

2742 ) -> None:

2743 """

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

2745

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

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

2748 """

2749 super().__init__(name, keyValuePairs)

2750

2751 self._subgraphs = set()

2752 self._views = set()

2753 self._components = set()

2754

2755 def __del__(self) -> None:

2756 """

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

2758

2759 """

2760 try:

2761 del self._subgraphs

2762 del self._views

2763 del self._components

2764 except AttributeError:

2765 pass

2766

2767 super().__del__()

2768

2769 @readonly

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

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

2772

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

2774 return self._subgraphs

2775

2776 @readonly

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

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

2779

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

2781 return self._views

2782

2783 @readonly

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

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

2786

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

2788 return self._components

2789

2790 @readonly

2791 def SubgraphCount(self) -> int:

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

2793

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

2795 return len(self._subgraphs)

2796

2797 @readonly

2798 def ViewCount(self) -> int:

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

2800

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

2802 return len(self._views)

2803

2804 @readonly

2805 def ComponentCount(self) -> int:

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

2807

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

2809 return len(self._components)

2810

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

2812 """

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

2814

2815 """

2816 def gen():

2817 yield from self._verticesWithoutID

2818 yield from self._verticesWithID

2819 return iter(gen())

2820

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

2822 """

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

2824

2825 """

2826 if vertexID is None:

2827 return len(self._verticesWithoutID) >= 1

2828 else:

2829 return vertexID in self._verticesWithID

2830

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

2832 """

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

2834

2835 """

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

2837

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

2839 """

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

2841

2842 """

2843 if vertexID is None:

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

2845 return self._verticesWithoutID[0]

2846 elif l == 0:

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

2848 else:

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

2850 else:

2851 return self._verticesWithID[vertexID]

2852

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

2854 """

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

2856

2857 """

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

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

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

2861 return vertices[0]

2862 elif l == 0:

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

2864 else:

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

2866

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

2868 raise NotImplementedError()

2869

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

2871 """

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

2873

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

2875

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

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

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

2879 """

2880 graph = Graph(self._name)

2881 if copyGraphDict:

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

2883

2884 if predicate is None:

2885 for vertex in self._verticesWithoutID:

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

2887 if copyVertexDict:

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

2889

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

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

2892 if copyVertexDict:

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

2894 else:

2895 for vertex in self._verticesWithoutID:

2896 if predicate(vertex):

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

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

2899 v._dict = vertex._dict.copy()

2900

2901 for vertexID, vertex in self._verticesWithID.items():

2902 if predicate(vertex):

2903 v = Vertex(vertexID, vertex._value, graph=graph)

2904 if copyVertexDict: 2904 ↛ 2905line 2904 didn't jump to line 2905 because the condition on line 2904 was never true

2905 v._dict = vertex._dict.copy()

2906

2907 return graph

2908

2909 # class Iterator():

2910 # visited = [False for _ in range(self.__len__())]

2911

2912 # def CheckForNegativeCycles(self):

2913 # raise NotImplementedError()

2914 # # Bellman-Ford

2915 # # Floyd-Warshall

2916 #

2917 # def IsStronglyConnected(self):

2918 # raise NotImplementedError()

2919 #

2920 # def GetStronglyConnectedComponents(self):

2921 # raise NotImplementedError()

2922 # # Tarjan's and Kosaraju's algorithm

2923 #

2924 # def TravelingSalesmanProblem(self):

2925 # raise NotImplementedError()

2926 # # Held-Karp

2927 # # branch and bound

2928 #

2929 # def GetBridges(self):

2930 # raise NotImplementedError()

2931 #

2932 # def GetArticulationPoints(self):

2933 # raise NotImplementedError()

2934 #

2935 # def MinimumSpanningTree(self):

2936 # raise NotImplementedError()

2937 # # Kruskal

2938 # # Prim's algorithm

2939 # # Buruvka's algorithm

2940

2941 def __repr__(self) -> str:

2942 """

2943 .. todo:: GRAPH::Graph::repr Needs documentation.

2944

2945 """

2946 statistics = f", vertices: {self.VertexCount}, edges: {self.EdgeCount}"

2947 if self._name is None:

2948 return f"<graph: unnamed graph{statistics}>"

2949 else:

2950 return f"<graph: '{self._name}'{statistics}>"

2951

2952 def __str__(self) -> str:

2953 """

2954 .. todo:: GRAPH::Graph::str Needs documentation.

2955

2956 """

2957 if self._name is None:

2958 return f"Graph: unnamed graph"

2959 else:

2960 return f"Graph: '{self._name}'"

Coverage for pyTooling / Graph / init.py: 76%

1210 statements