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 NotInDifferentSubgraphs(GraphException):

179 """

180 The exception is raised when creating a link between two vertices, but these are in the same subgraph.

181

182 A link crosses subgraph boundaries. Two vertices within one subgraph are connected by an edge.

183 """

184

185

186@export

187class DuplicateVertexError(GraphException):

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

189

190

191@export

192class DuplicateEdgeError(GraphException):

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

194

195

196@export

197class DestinationNotReachable(GraphException):

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

199

200

201@export

202class NotATreeError(GraphException):

203 """

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

205

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

207 """

208

209

210@export

211class CycleError(GraphException):

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

213

214

215@export

216class Base(

217 Generic[DictKeyType, DictValueType],

218 metaclass=ExtendedType, slots=True

219):

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

221

222 def __init__(

223 self,

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

225 ) -> None:

226 """

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

228

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

230 """

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

232

233 def __del__(self) -> None:

234 """

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

236

237 """

238 try:

239 del self._dict

240 except AttributeError:

241 pass

242

243 def Delete(self) -> None:

244 self._dict = None

245

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

247 """

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

249

250 :param key: The key to look for.

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

252 """

253 return self._dict[key]

254

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

256 """

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

258

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

260

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

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

263 """

264 self._dict[key] = value

265

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

267 """

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

269

270 :param key: The key to remove.

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

272 """

273 del self._dict[key]

274

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

276 """

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

278

279 :param key: The key to check.

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

281 """

282 return key in self._dict

283

284 def __len__(self) -> int:

285 """

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

287

288 :returns: Number of attached attributes.

289 """

290 return len(self._dict)

291

292

293@export

294class BaseWithIDValueAndWeight(

295 Base[DictKeyType, DictValueType],

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

297):

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

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

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

301

302 def __init__(

303 self,

304 identifier: Nullable[IDType] = None,

305 value: Nullable[ValueType] = None,

306 weight: Nullable[WeightType] = None,

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

308 ) -> None:

309 """

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

311

312 :param identifier: The optional unique ID.

313 :param value: The optional value.

314 :param weight: The optional weight.

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

316 """

317 super().__init__(keyValuePairs)

318

319 self._id = identifier

320 self._value = value

321 self._weight = weight

322

323 @readonly

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

325 """

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

327

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

329

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

331 """

332 return self._id

333

334 @property

335 def Value(self) -> ValueType:

336 """

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

338

339 :returns: The value.

340 """

341 return self._value

342

343 @Value.setter

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

345 self._value = value

346

347 @property

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

349 """

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

351

352 :returns: The weight of an edge.

353 """

354 return self._weight

355

356 @Weight.setter

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

358 self._weight = value

359

360

361@export

362class BaseWithName(

363 Base[DictKeyType, DictValueType],

364 Generic[DictKeyType, DictValueType]

365):

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

367

368 def __init__(

369 self,

370 name: Nullable[str] = None,

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

372 ) -> None:

373 """

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

375

376 :param name: The optional name.

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

378 """

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

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

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

382 raise ex

383

384 super().__init__(keyValuePairs)

385

386 self._name = name

387

388 @property

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

390 """

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

392

393 :returns: The value of a component.

394 """

395 return self._name

396

397 @Name.setter

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

399 if not isinstance(value, str):

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

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

402 raise ex

403

404 self._name = value

405

406

407@export

408class BaseWithVertices(

409 BaseWithName[DictKeyType, DictValueType],

410 Generic[

411 DictKeyType, DictValueType,

412 GraphDictKeyType, GraphDictValueType,

413 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,

414 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,

415 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType

416 ]

417):

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

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

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

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

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

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

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

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

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

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

428

429 def __init__(

430 self,

431 graph: 'Graph',

432 name: Nullable[str] = None,

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

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

435 ) -> None:

436 """

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

438

439 :param graph: The reference to the graph.

440 :param name: The optional name.

441 :param vertices: The optional list of vertices.

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

443 """

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

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

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

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

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

449 raise ex

450

451 super().__init__(name, keyValuePairs)

452

453 self._graph = graph

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

455

456 def __del__(self) -> None:

457 """

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

459

460 """

461 try:

462 del self._vertices

463 except AttributeError:

464 pass

465

466 super().__del__()

467

468 @readonly

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

470 """

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

472

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

474 """

475 return self._graph

476

477 @readonly

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

479 """

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

481

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

483 """

484 return self._vertices

485

486 @readonly

487 def VertexCount(self) -> int:

488 """

489 Read-only property to return the number of vertices referenced by this object.

490

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

492 """

493 return len(self._vertices)

494

495

496@export

497class Vertex(

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

499 Generic[

500 GraphDictKeyType, GraphDictValueType,

501 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,

502 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,

503 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType

504 ]

505):

506 """

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

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

509 """

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

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

512 _component: 'Component'

513 _views: Dict[Hashable, 'View']

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

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

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

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

518

519 def __init__(

520 self,

521 vertexID: Nullable[VertexIDType] = None,

522 value: Nullable[VertexValueType] = None,

523 weight: Nullable[VertexWeightType] = None,

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

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

526 subgraph: Nullable['Subgraph'] = None

527 ) -> None:

528 """

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

530

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

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

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

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

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

536 :param subgraph: undocumented

537 """

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

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

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

541 raise ex

542

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

544

545 if subgraph is None:

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

547 self._subgraph = None

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

549

550 if vertexID is None:

551 self._graph._verticesWithoutID.append(self)

552 elif vertexID not in self._graph._verticesWithID:

553 self._graph._verticesWithID[vertexID] = self

554 else:

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

556 else:

557 self._graph = subgraph._graph

558 self._subgraph = subgraph

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

560

561 if vertexID is None:

562 subgraph._verticesWithoutID.append(self)

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

564 subgraph._verticesWithID[vertexID] = self

565 else:

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

567

568 self._views = {}

569 self._inboundEdges = []

570 self._outboundEdges = []

571 self._inboundLinks = []

572 self._outboundLinks = []

573

574 def __del__(self) -> None:

575 """

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

577

578 """

579 try:

580 del self._views

581 del self._inboundEdges

582 del self._outboundEdges

583 del self._inboundLinks

584 del self._outboundLinks

585 except AttributeError:

586 pass

587

588 super().__del__()

589

590 def Delete(self) -> None:

591 for edge in self._outboundEdges:

592 edge._destination._inboundEdges.remove(edge)

593 edge._Delete()

594 for edge in self._inboundEdges:

595 edge._source._outboundEdges.remove(edge)

596 edge._Delete()

597 for link in self._outboundLinks:

598 link._destination._inboundLinks.remove(link)

599 link._Delete()

600 for link in self._inboundLinks:

601 link._source._outboundLinks.remove(link)

602 link._Delete()

603

604 if self._id is None:

605 self._graph._verticesWithoutID.remove(self)

606 else:

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

608

609 # subgraph

610

611 # component

612

613 # views

614 self._views = None

615 self._inboundEdges = None

616 self._outboundEdges = None

617 self._inboundLinks = None

618 self._outboundLinks = None

619

620 super().Delete()

621 assert getrefcount(self) == 1

622

623 @readonly

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

625 """

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

627

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

629 """

630 return self._graph

631

632 @readonly

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

634 """

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

636

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

638 """

639 return self._component

640

641 @readonly

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

643 """

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

645

646 :returns: Tuple of inbound edges.

647 """

648 return tuple(self._inboundEdges)

649

650 @readonly

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

652 """

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

654

655 :returns: Tuple of outbound edges.

656 """

657 return tuple(self._outboundEdges)

658

659 @readonly

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

661 """

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

663

664 :returns: Tuple of inbound links.

665 """

666 return tuple(self._inboundLinks)

667

668 @readonly

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

670 """

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

672

673 :returns: Tuple of outbound links.

674 """

675 return tuple(self._outboundLinks)

676

677 @readonly

678 def EdgeCount(self) -> int:

679 """

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

681

682 :returns: Number of inbound and outbound edges.

683 """

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

685

686 @readonly

687 def InboundEdgeCount(self) -> int:

688 """

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

690

691 :returns: Number of inbound edges.

692 """

693 return len(self._inboundEdges)

694

695 @readonly

696 def OutboundEdgeCount(self) -> int:

697 """

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

699

700 :returns: Number of outbound edges.

701 """

702 return len(self._outboundEdges)

703

704 @readonly

705 def LinkCount(self) -> int:

706 """

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

708

709 :returns: Number of inbound and outbound links.

710 """

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

712

713 @readonly

714 def InboundLinkCount(self) -> int:

715 """

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

717

718 :returns: Number of inbound links.

719 """

720 return len(self._inboundLinks)

721

722 @readonly

723 def OutboundLinkCount(self) -> int:

724 """

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

726

727 :returns: Number of outbound links.

728 """

729 return len(self._outboundLinks)

730

731 @readonly

732 def IsRoot(self) -> bool:

733 """

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

735

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

737

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

739

740 .. seealso::

741

742 :meth:`IsLeaf` |br|

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

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

745 |rarr| Iterate all roots of a graph.

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

747 |rarr| Iterate all leafs of a graph.

748 """

749 return len(self._inboundEdges) == 0

750

751 @readonly

752 def IsLeaf(self) -> bool:

753 """

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

755

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

757

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

759

760 .. seealso::

761

762 :meth:`IsRoot` |br|

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

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

765 |rarr| Iterate all roots of a graph.

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

767 |rarr| Iterate all leafs of a graph.

768 """

769 return len(self._outboundEdges) == 0

770

771 @readonly

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

773 """

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

775

776 :returns: Tuple of predecessor vertices.

777 """

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

779

780 @readonly

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

782 """

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

784

785 :returns: Tuple of successor vertices.

786 """

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

788

789 def EdgeToVertex(

790 self,

791 vertex: 'Vertex',

792 edgeID: Nullable[EdgeIDType] = None,

793 edgeWeight: Nullable[EdgeWeightType] = None,

794 edgeValue: Nullable[VertexValueType] = None,

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

796 ) -> 'Edge':

797 """

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

799

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

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

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

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

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

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

806

807 .. seealso::

808

809 :meth:`EdgeFromVertex` |br|

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

811 :meth:`EdgeToNewVertex` |br|

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

813 :meth:`EdgeFromNewVertex` |br|

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

815 :meth:`LinkToVertex` |br|

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

817 :meth:`LinkFromVertex` |br|

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

819

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

821 """

822 if self._subgraph is vertex._subgraph:

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

824

825 self._outboundEdges.append(edge)

826 vertex._inboundEdges.append(edge)

827

828 if self._subgraph is None:

829 # TODO: move into Edge?

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

831 if edgeID is None:

832 self._graph._edgesWithoutID.append(edge)

833 elif edgeID not in self._graph._edgesWithID:

834 self._graph._edgesWithID[edgeID] = edge

835 else:

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

837 else:

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

839 if edgeID is None:

840 self._subgraph._edgesWithoutID.append(edge)

841 elif edgeID not in self._subgraph._edgesWithID:

842 self._subgraph._edgesWithID[edgeID] = edge

843 else:

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

845 else:

846 ex = NotInSameGraph(f"Vertex {self!r} and vertex {vertex!r} are not in the same graph or subgraph.")

847 ex.add_note(f"An edge can only connect vertices within the same graph or subgraph.")

848 ex.add_note(f"Use LinkToVertex or LinkFromVertex to connect vertices across subgraph boundaries.")

849 raise ex

850

851 return edge

852

853 def EdgeFromVertex(

854 self,

855 vertex: 'Vertex',

856 edgeID: Nullable[EdgeIDType] = None,

857 edgeWeight: Nullable[EdgeWeightType] = None,

858 edgeValue: Nullable[VertexValueType] = None,

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

860 ) -> 'Edge':

861 """

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

863

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

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

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

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

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

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

870

871 .. seealso::

872

873 :meth:`EdgeToVertex` |br|

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

875 :meth:`EdgeToNewVertex` |br|

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

877 :meth:`EdgeFromNewVertex` |br|

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

879 :meth:`LinkToVertex` |br|

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

881 :meth:`LinkFromVertex` |br|

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

883

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

885 """

886 if self._subgraph is vertex._subgraph:

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

888

889 vertex._outboundEdges.append(edge)

890 self._inboundEdges.append(edge)

891

892 if self._subgraph is None:

893 # TODO: move into Edge?

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

895 if edgeID is None:

896 self._graph._edgesWithoutID.append(edge)

897 elif edgeID not in self._graph._edgesWithID:

898 self._graph._edgesWithID[edgeID] = edge

899 else:

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

901 else:

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

903 if edgeID is None:

904 self._subgraph._edgesWithoutID.append(edge)

905 elif edgeID not in self._graph._edgesWithID:

906 self._subgraph._edgesWithID[edgeID] = edge

907 else:

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

909 else:

910 ex = NotInSameGraph(f"Vertex {self!r} and vertex {vertex!r} are not in the same graph or subgraph.")

911 ex.add_note(f"An edge can only connect vertices within the same graph or subgraph.")

912 ex.add_note(f"Use LinkToVertex or LinkFromVertex to connect vertices across subgraph boundaries.")

913 raise ex

914

915 return edge

916

917 def EdgeToNewVertex(

918 self,

919 vertexID: Nullable[VertexIDType] = None,

920 vertexValue: Nullable[VertexValueType] = None,

921 vertexWeight: Nullable[VertexWeightType] = None,

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

923 edgeID: Nullable[EdgeIDType] = None,

924 edgeWeight: Nullable[EdgeWeightType] = None,

925 edgeValue: Nullable[VertexValueType] = None,

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

927 ) -> 'Edge':

928 """

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

930

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

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

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

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

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

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

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

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

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

940

941 .. seealso::

942

943 :meth:`EdgeToVertex` |br|

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

945 :meth:`EdgeFromVertex` |br|

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

947 :meth:`EdgeFromNewVertex` |br|

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

949 :meth:`LinkToVertex` |br|

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

951 :meth:`LinkFromVertex` |br|

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

953

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

955 """

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

957

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

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

960

961 self._outboundEdges.append(edge)

962 vertex._inboundEdges.append(edge)

963

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

965 # TODO: move into Edge?

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

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

968 self._graph._edgesWithoutID.append(edge)

969 elif edgeID not in self._graph._edgesWithID:

970 self._graph._edgesWithID[edgeID] = edge

971 else:

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

973 else:

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

975 if edgeID is None:

976 self._subgraph._edgesWithoutID.append(edge)

977 elif edgeID not in self._graph._edgesWithID:

978 self._subgraph._edgesWithID[edgeID] = edge

979 else:

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

981 else:

982 ex = NotInSameGraph(f"Vertex {self!r} and vertex {vertex!r} are not in the same graph or subgraph.")

983 ex.add_note(f"An edge can only connect vertices within the same graph or subgraph.")

984 ex.add_note(f"Use LinkToVertex or LinkFromVertex to connect vertices across subgraph boundaries.")

985 raise ex

986

987 return edge

988

989 def EdgeFromNewVertex(

990 self,

991 vertexID: Nullable[VertexIDType] = None,

992 vertexValue: Nullable[VertexValueType] = None,

993 vertexWeight: Nullable[VertexWeightType] = None,

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

995 edgeID: Nullable[EdgeIDType] = None,

996 edgeWeight: Nullable[EdgeWeightType] = None,

997 edgeValue: Nullable[VertexValueType] = None,

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

999 ) -> 'Edge':

1000 """

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

1002

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

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

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

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

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

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

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

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

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

1012

1013 .. seealso::

1014

1015 :meth:`EdgeToVertex` |br|

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

1017 :meth:`EdgeFromVertex` |br|

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

1019 :meth:`EdgeToNewVertex` |br|

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

1021 :meth:`LinkToVertex` |br|

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

1023 :meth:`LinkFromVertex` |br|

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

1025

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

1027 """

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

1029

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

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

1032

1033 vertex._outboundEdges.append(edge)

1034 self._inboundEdges.append(edge)

1035

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

1037 # TODO: move into Edge?

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

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

1040 self._graph._edgesWithoutID.append(edge)

1041 elif edgeID not in self._graph._edgesWithID:

1042 self._graph._edgesWithID[edgeID] = edge

1043 else:

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

1045 else:

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

1047 if edgeID is None:

1048 self._subgraph._edgesWithoutID.append(edge)

1049 elif edgeID not in self._graph._edgesWithID:

1050 self._subgraph._edgesWithID[edgeID] = edge

1051 else:

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

1053 else:

1054 ex = NotInSameGraph(f"Vertex {self!r} and vertex {vertex!r} are not in the same graph or subgraph.")

1055 ex.add_note(f"An edge can only connect vertices within the same graph or subgraph.")

1056 ex.add_note(f"Use LinkToVertex or LinkFromVertex to connect vertices across subgraph boundaries.")

1057 raise ex

1058

1059 return edge

1060

1061 def LinkToVertex(

1062 self,

1063 vertex: 'Vertex',

1064 linkID: Nullable[EdgeIDType] = None,

1065 linkWeight: Nullable[EdgeWeightType] = None,

1066 linkValue: Nullable[VertexValueType] = None,

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

1068 ) -> 'Link':

1069 """

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

1071

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

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

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

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

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

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

1078

1079 .. seealso::

1080

1081 :meth:`EdgeToVertex` |br|

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

1083 :meth:`EdgeFromVertex` |br|

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

1085 :meth:`EdgeToNewVertex` |br|

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

1087 :meth:`EdgeFromNewVertex` |br|

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

1089 :meth:`LinkFromVertex` |br|

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

1091

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

1093 """

1094 if self._subgraph is vertex._subgraph:

1095 ex = NotInDifferentSubgraphs(f"Vertex {self!r} and vertex {vertex!r} are in the same subgraph.")

1096 ex.add_note(f"A link can only connect vertices across subgraph boundaries.")

1097 ex.add_note(f"Use EdgeToVertex or EdgeFromVertex to connect vertices within the same subgraph.")

1098 raise ex

1099 else:

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

1101

1102 self._outboundLinks.append(link)

1103 vertex._inboundLinks.append(link)

1104

1105 if self._subgraph is None:

1106 # TODO: move into Edge?

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

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

1109 self._graph._linksWithoutID.append(link)

1110 elif linkID not in self._graph._linksWithID:

1111 self._graph._linksWithID[linkID] = link

1112 else:

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

1114 else:

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

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

1117 self._subgraph._linksWithoutID.append(link)

1118 vertex._subgraph._linksWithoutID.append(link)

1119 elif linkID not in self._graph._linksWithID:

1120 self._subgraph._linksWithID[linkID] = link

1121 vertex._subgraph._linksWithID[linkID] = link

1122 else:

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

1124

1125 return link

1126

1127 def LinkFromVertex(

1128 self,

1129 vertex: 'Vertex',

1130 linkID: Nullable[EdgeIDType] = None,

1131 linkWeight: Nullable[EdgeWeightType] = None,

1132 linkValue: Nullable[VertexValueType] = None,

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

1134 ) -> 'Edge':

1135 """

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

1137

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

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

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

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

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

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

1144

1145 .. seealso::

1146

1147 :meth:`EdgeToVertex` |br|

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

1149 :meth:`EdgeFromVertex` |br|

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

1151 :meth:`EdgeToNewVertex` |br|

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

1153 :meth:`EdgeFromNewVertex` |br|

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

1155 :meth:`LinkToVertex` |br|

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

1157

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

1159 """

1160 if self._subgraph is vertex._subgraph:

1161 ex = NotInDifferentSubgraphs(f"Vertex {self!r} and vertex {vertex!r} are in the same subgraph.")

1162 ex.add_note(f"A link can only connect vertices across subgraph boundaries.")

1163 ex.add_note(f"Use EdgeToVertex or EdgeFromVertex to connect vertices within the same subgraph.")

1164 raise ex

1165 else:

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

1167

1168 vertex._outboundLinks.append(link)

1169 self._inboundLinks.append(link)

1170

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

1172 # TODO: move into Edge?

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

1174 if linkID is None:

1175 self._graph._linksWithoutID.append(link)

1176 elif linkID not in self._graph._linksWithID:

1177 self._graph._linksWithID[linkID] = link

1178 else:

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

1180 else:

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

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

1183 self._subgraph._linksWithoutID.append(link)

1184 vertex._subgraph._linksWithoutID.append(link)

1185 elif linkID not in self._graph._linksWithID:

1186 self._subgraph._linksWithID[linkID] = link

1187 vertex._subgraph._linksWithID[linkID] = link

1188 else:

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

1190

1191 return link

1192

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

1194 """

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

1196

1197 :param destination: Destination vertex to check.

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

1199

1200 .. seealso::

1201

1202 :meth:`HasEdgeFromSource` |br|

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

1204 :meth:`HasLinkToDestination` |br|

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

1206 :meth:`HasLinkFromSource` |br|

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

1208 """

1209 for edge in self._outboundEdges:

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

1211 return True

1212

1213 return False

1214

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

1216 """

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

1218

1219 :param source: Source vertex to check.

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

1221

1222 .. seealso::

1223

1224 :meth:`HasEdgeToDestination` |br|

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

1226 :meth:`HasLinkToDestination` |br|

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

1228 :meth:`HasLinkFromSource` |br|

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

1230 """

1231 for edge in self._inboundEdges:

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

1233 return True

1234

1235 return False

1236

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

1238 """

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

1240

1241 :param destination: Destination vertex to check.

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

1243

1244 .. seealso::

1245

1246 :meth:`HasEdgeToDestination` |br|

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

1248 :meth:`HasEdgeFromSource` |br|

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

1250 :meth:`HasLinkFromSource` |br|

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

1252 """

1253 for link in self._outboundLinks:

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

1255 return True

1256

1257 return False

1258

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

1260 """

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

1262

1263 :param source: Source vertex to check.

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

1265

1266 .. seealso::

1267

1268 :meth:`HasEdgeToDestination` |br|

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

1270 :meth:`HasEdgeFromSource` |br|

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

1272 :meth:`HasLinkToDestination` |br|

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

1274 """

1275 for link in self._inboundLinks:

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

1277 return True

1278

1279 return False

1280

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

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

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

1284 break

1285 else:

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

1287

1288 edge.Delete()

1289

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

1291 for edge in self._inboundEdges:

1292 if edge._source is source:

1293 break

1294 else:

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

1296

1297 edge.Delete()

1298

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

1300 for link in self._outboundLinks:

1301 if link._destination is destination:

1302 break

1303 else:

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

1305

1306 link.Delete()

1307

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

1309 for link in self._inboundLinks:

1310 if link._source is source:

1311 break

1312 else:

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

1314

1315 link.Delete()

1316

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

1318 """

1319 Creates a copy of this vertex in another graph.

1320

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

1322 can be established.

1323

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

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

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

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

1328 :returns: The newly created vertex.

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

1330 """

1331 if graph is self._graph:

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

1333

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

1335 if copyDict:

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

1337

1338 if linkingKeyToOriginalVertex is not None:

1339 vertex._dict[linkingKeyToOriginalVertex] = self

1340 if linkingKeyFromOriginalVertex is not None:

1341 self._dict[linkingKeyFromOriginalVertex] = vertex

1342

1343 return vertex

1344

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

1346 """

1347 Iterate all or selected outbound edges of this vertex.

1348

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

1350

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

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

1353 """

1354 if predicate is None:

1355 for edge in self._outboundEdges:

1356 yield edge

1357 else:

1358 for edge in self._outboundEdges:

1359 if predicate(edge):

1360 yield edge

1361

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

1363 """

1364 Iterate all or selected inbound edges of this vertex.

1365

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

1367

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

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

1370 """

1371 if predicate is None:

1372 for edge in self._inboundEdges:

1373 yield edge

1374 else:

1375 for edge in self._inboundEdges:

1376 if predicate(edge):

1377 yield edge

1378

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

1380 """

1381 Iterate all or selected outbound links of this vertex.

1382

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

1384

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

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

1387 """

1388 if predicate is None:

1389 for link in self._outboundLinks:

1390 yield link

1391 else:

1392 for link in self._outboundLinks:

1393 if predicate(link):

1394 yield link

1395

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

1397 """

1398 Iterate all or selected inbound links of this vertex.

1399

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

1401

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

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

1404 """

1405 if predicate is None:

1406 for link in self._inboundLinks:

1407 yield link

1408 else:

1409 for link in self._inboundLinks:

1410 if predicate(link):

1411 yield link

1412

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

1414 """

1415 Iterate all or selected successor vertices of this vertex.

1416

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

1418

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

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

1421 """

1422 if predicate is None:

1423 for edge in self._outboundEdges:

1424 yield edge.Destination

1425 else:

1426 for edge in self._outboundEdges:

1427 if predicate(edge):

1428 yield edge.Destination

1429

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

1431 """

1432 Iterate all or selected predecessor vertices of this vertex.

1433

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

1435

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

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

1438 """

1439 if predicate is None:

1440 for edge in self._inboundEdges:

1441 yield edge.Source

1442 else:

1443 for edge in self._inboundEdges:

1444 if predicate(edge):

1445 yield edge.Source

1446

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

1448 """

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

1450

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

1452

1453 .. seealso::

1454

1455 :meth:`IterateVerticesDFS` |br|

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

1457 """

1458 visited: Set[Vertex] = set()

1459 queue: Deque[Vertex] = deque()

1460

1461 yield self

1462 visited.add(self)

1463 for edge in self._outboundEdges:

1464 nextVertex = edge.Destination

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

1466 queue.appendleft(nextVertex)

1467 visited.add(nextVertex)

1468

1469 while queue:

1470 vertex = queue.pop()

1471 yield vertex

1472 for edge in vertex._outboundEdges:

1473 nextVertex = edge.Destination

1474 if nextVertex not in visited:

1475 queue.appendleft(nextVertex)

1476 visited.add(nextVertex)

1477

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

1479 """

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

1481

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

1483

1484 .. seealso::

1485

1486 :meth:`IterateVerticesBFS` |br|

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

1488

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

1490 """

1491 visited: Set[Vertex] = set()

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

1493

1494 yield self

1495 visited.add(self)

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

1497

1498 while True:

1499 try:

1500 edge = next(stack[-1])

1501 nextVertex = edge._destination

1502 if nextVertex not in visited:

1503 visited.add(nextVertex)

1504 yield nextVertex

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

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

1507 except StopIteration:

1508 stack.pop()

1509

1510 if len(stack) == 0:

1511 return

1512

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

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

1515 yield (self, )

1516 return

1517

1518 visited: Set[Vertex] = set()

1519 vertexStack: List[Vertex] = list()

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

1521

1522 visited.add(self)

1523 vertexStack.append(self)

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

1525

1526 while True:

1527 try:

1528 edge = next(iteratorStack[-1])

1529 nextVertex = edge._destination

1530 if nextVertex in visited:

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

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

1533 for i, vertex in enumerate(vertexStack):

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

1535 raise ex

1536

1537 vertexStack.append(nextVertex)

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

1539 yield tuple(vertexStack)

1540 vertexStack.pop()

1541 else:

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

1543

1544 except StopIteration:

1545 vertexStack.pop()

1546 iteratorStack.pop()

1547

1548 if len(vertexStack) == 0:

1549 return

1550

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

1552 """

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

1554

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

1556

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

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

1559

1560 :param destination: The destination vertex to reach.

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

1562 """

1563 # Trivial case if start is destination

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

1565 yield self

1566 return

1567

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

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

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

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

1572 parent: 'Node'

1573 ref: Vertex

1574

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

1576 self.parent = parent

1577 self.ref = ref

1578

1579 def __str__(self):

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

1581

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

1583 startNode = Node(None, self)

1584 visited: Set[Vertex] = set()

1585 queue: Deque[Node] = deque()

1586

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

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

1589 visited.add(self)

1590 for edge in self._outboundEdges:

1591 nextVertex = edge.Destination

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

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

1594 destinationNode = Node(startNode, nextVertex)

1595 break

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

1597 # Ignore backward-edges and side-edges.

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

1599 visited.add(nextVertex)

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

1601 else:

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

1603 while queue:

1604 node = queue.pop()

1605 for edge in node.ref._outboundEdges:

1606 nextVertex = edge.Destination

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

1608 if nextVertex is destination:

1609 destinationNode = Node(node, nextVertex)

1610 break

1611 # Ignore backward-edges and side-edges.

1612 if nextVertex not in visited:

1613 visited.add(nextVertex)

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

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

1616 else:

1617 continue

1618 break

1619 else:

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

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

1622

1623 # Reverse order of linked list from destinationNode to startNode

1624 currentNode = destinationNode

1625 previousNode = destinationNode.parent

1626 currentNode.parent = None

1627 while previousNode is not None:

1628 node = previousNode.parent

1629 previousNode.parent = currentNode

1630 currentNode = previousNode

1631 previousNode = node

1632

1633 # Scan reversed linked-list and yield referenced vertices

1634 yield startNode.ref

1635 node = startNode.parent

1636 while node is not None:

1637 yield node.ref

1638 node = node.parent

1639

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

1641 """

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

1643

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

1645

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

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

1648

1649 :param destination: The destination vertex to reach.

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

1651 """

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

1653

1654 # Trivial case if start is destination

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

1656 yield self

1657 return

1658

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

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

1661 # represents.

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

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

1664 parent: 'Node'

1665 distance: EdgeWeightType

1666 ref: Vertex

1667

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

1669 self.parent = parent

1670 self.distance = distance

1671 self.ref = ref

1672

1673 def __lt__(self, other):

1674 return self.distance < other.distance

1675

1676 def __str__(self):

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

1678

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

1680 startNode = Node(None, 0, self)

1681 priorityQueue = [startNode]

1682

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

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

1685 visited.add(self)

1686 for edge in self._outboundEdges:

1687 nextVertex = edge.Destination

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

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

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

1691 break

1692 # Ignore backward-edges and side-edges.

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

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

1695 visited.add(nextVertex)

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

1697 else:

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

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

1700 node = heapq.heappop(priorityQueue)

1701 for edge in node.ref._outboundEdges:

1702 nextVertex = edge.Destination

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

1704 if nextVertex is destination:

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

1706 break

1707 # Ignore backward-edges and side-edges.

1708 if nextVertex not in visited:

1709 visited.add(nextVertex)

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

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

1712 else:

1713 continue

1714 break

1715 else:

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

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

1718

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

1720 currentNode = destinationNode

1721 previousNode = destinationNode.parent

1722 currentNode.parent = None

1723 while previousNode is not None:

1724 node = previousNode.parent

1725 previousNode.parent = currentNode

1726 currentNode = previousNode

1727 previousNode = node

1728

1729 # Scan reversed linked-list and yield referenced vertices

1730 yield startNode.ref, startNode.distance

1731 node = startNode.parent

1732 while node is not None:

1733 yield node.ref, node.distance

1734 node = node.parent

1735

1736 # Other possible algorithms:

1737 # * Bellman-Ford

1738 # * Floyd-Warshall

1739

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

1741 # raise NotImplementedError()

1742 # # DFS

1743 # # Union find

1744 #

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

1746 # raise NotImplementedError()

1747 # # Ford-Fulkerson algorithm

1748 # # Edmons-Karp algorithm

1749 # # Dinic's algorithm

1750

1751 def ConvertToTree(self) -> Node:

1752 """

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

1754

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

1756

1757 :returns: Root node of the resulting tree, representing this vertex.

1758 """

1759 visited: Set[Vertex] = set()

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

1761

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

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

1764

1765 visited.add(self)

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

1767

1768 while True:

1769 try:

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

1771 nextVertex = edge._destination

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

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

1774 visited.add(nextVertex)

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

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

1777 else:

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

1779 # TODO: compute cycle:

1780 # a) branch 1 is described in stack

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

1782 except StopIteration:

1783 stack.pop()

1784

1785 if len(stack) == 0:

1786 return root

1787

1788 def __repr__(self) -> str:

1789 """

1790 Returns a detailed string representation of the vertex.

1791

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

1793 """

1794 vertexID = value = ""

1795 sep = ": "

1796 if self._id is not None:

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

1798 sep = "; "

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

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

1801

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

1803

1804 def __str__(self) -> str:

1805 """

1806 Return a string representation of the vertex.

1807

1808 Order of resolution:

1809

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

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

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

1813

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

1815 """

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

1817 return str(self._value)

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

1819 return str(self._id)

1820 else:

1821 return self.__repr__()

1822

1823

1824@export

1825class BaseEdge(

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

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

1828):

1829 """

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

1831 directed.

1832 """

1833 _source: Vertex

1834 _destination: Vertex

1835

1836 def __init__(

1837 self,

1838 source: Vertex,

1839 destination: Vertex,

1840 edgeID: Nullable[EdgeIDType] = None,

1841 value: Nullable[EdgeValueType] = None,

1842 weight: Nullable[EdgeWeightType] = None,

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

1844 ) -> None:

1845 """

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

1847

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

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

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

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

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

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

1854 """

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

1856

1857 self._source = source

1858 self._destination = destination

1859

1860 component = source._component

1861 if component is not destination._component:

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

1863 oldComponent = destination._component

1864 for vertex in oldComponent._vertices:

1865 vertex._component = component

1866 component._vertices.add(vertex)

1867 component._graph._components.remove(oldComponent)

1868 del oldComponent

1869

1870 @readonly

1871 def Source(self) -> Vertex:

1872 """

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

1874

1875 :returns: The source of an edge.

1876 """

1877 return self._source

1878

1879 @readonly

1880 def Destination(self) -> Vertex:

1881 """

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

1883

1884 :returns: The destination of an edge.

1885 """

1886 return self._destination

1887

1888 def Reverse(self) -> None:

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

1890 swap = self._source

1891 self._source = self._destination

1892 self._destination = swap

1893

1894

1895@export

1896class Edge(

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

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

1899):

1900 """

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

1902 directed.

1903 """

1904

1905 def __init__(

1906 self,

1907 source: Vertex,

1908 destination: Vertex,

1909 edgeID: Nullable[EdgeIDType] = None,

1910 value: Nullable[EdgeValueType] = None,

1911 weight: Nullable[EdgeWeightType] = None,

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

1913 ) -> None:

1914 """

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

1916

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

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

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

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

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

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

1923 """

1924 if not isinstance(source, Vertex):

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

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

1927 raise ex

1928 if not isinstance(destination, Vertex):

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

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

1931 raise ex

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

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

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

1935 raise ex

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

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

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

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

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

1941 raise ex

1942 if source._graph is not destination._graph:

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

1944

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

1946

1947 def Delete(self) -> None:

1948 # Remove from Source and Destination

1949 self._source._outboundEdges.remove(self)

1950 self._destination._inboundEdges.remove(self)

1951

1952 # Remove from Graph and Subgraph

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

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

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

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

1957 else:

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

1959 if self._source._subgraph is not None:

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

1961

1962 self._Delete()

1963

1964 def _Delete(self) -> None:

1965 super().Delete()

1966

1967 def Reverse(self) -> None:

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

1969 self._source._outboundEdges.remove(self)

1970 self._source._inboundEdges.append(self)

1971 self._destination._inboundEdges.remove(self)

1972 self._destination._outboundEdges.append(self)

1973

1974 super().Reverse()

1975

1976

1977@export

1978class Link(

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

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

1981):

1982 """

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

1984 directed.

1985 """

1986

1987 def __init__(

1988 self,

1989 source: Vertex,

1990 destination: Vertex,

1991 linkID: LinkIDType = None,

1992 value: LinkValueType = None,

1993 weight: Nullable[LinkWeightType] = None,

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

1995 ) -> None:

1996 """

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

1998

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

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

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

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

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

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

2005 """

2006 if not isinstance(source, Vertex):

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

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

2009 raise ex

2010 if not isinstance(destination, Vertex):

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

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

2013 raise ex

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

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

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

2017 raise ex

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

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

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

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

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

2023 raise ex

2024 if source._graph is not destination._graph:

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

2026

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

2028

2029 def Delete(self) -> None:

2030 self._source._outboundEdges.remove(self)

2031 self._destination._inboundEdges.remove(self)

2032

2033 if self._id is None:

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

2035 else:

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

2037

2038 self._Delete()

2039 assert getrefcount(self) == 1

2040

2041 def _Delete(self) -> None:

2042 super().Delete()

2043

2044 def Reverse(self) -> None:

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

2046 self._source._outboundEdges.remove(self)

2047 self._source._inboundEdges.append(self)

2048 self._destination._inboundEdges.remove(self)

2049 self._destination._outboundEdges.append(self)

2050

2051 super().Reverse()

2052

2053

2054@export

2055class BaseGraph(

2056 BaseWithName[GraphDictKeyType, GraphDictValueType],

2057 Generic[

2058 GraphDictKeyType, GraphDictValueType,

2059 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,

2060 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,

2061 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType

2062 ]

2063):

2064 """

2065 .. todo:: GRAPH::BaseGraph Needs documentation.

2066

2067 """

2068

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

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

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

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

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

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

2075

2076 def __init__(

2077 self,

2078 name: Nullable[str] = None,

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

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

2081 ) -> None:

2082 """

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

2084

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

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

2087 """

2088 super().__init__(name, keyValuePairs)

2089

2090 self._verticesWithoutID = []

2091 self._verticesWithID = {}

2092 self._edgesWithoutID = []

2093 self._edgesWithID = {}

2094 self._linksWithoutID = []

2095 self._linksWithID = {}

2096

2097 def __del__(self) -> None:

2098 """

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

2100

2101 """

2102 try:

2103 del self._verticesWithoutID

2104 del self._verticesWithID

2105 del self._edgesWithoutID

2106 del self._edgesWithID

2107 del self._linksWithoutID

2108 del self._linksWithID

2109 except AttributeError:

2110 pass

2111

2112 super().__del__()

2113

2114 @readonly

2115 def VertexCount(self) -> int:

2116 """Read-only property to return the number of vertices in this graph.

2117

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

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

2120

2121 @readonly

2122 def EdgeCount(self) -> int:

2123 """Read-only property to return the number of edges in this graph.

2124

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

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

2127

2128 @readonly

2129 def LinkCount(self) -> int:

2130 """Read-only property to return the number of links in this graph.

2131

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

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

2134

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

2136 """

2137 Iterate all or selected vertices of a graph.

2138

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

2140

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

2142 :returns: A generator to iterate all vertices.

2143 """

2144 if predicate is None:

2145 yield from self._verticesWithoutID

2146 yield from self._verticesWithID.values()

2147

2148 else:

2149 for vertex in self._verticesWithoutID:

2150 if predicate(vertex):

2151 yield vertex

2152

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

2154 if predicate(vertex):

2155 yield vertex

2156

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

2158 """

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

2160

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

2162

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

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

2165

2166 .. seealso::

2167

2168 :meth:`IterateLeafs` |br|

2169 |rarr| Iterate leafs of a graph.

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

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

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

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

2174 """

2175 if predicate is None:

2176 for vertex in self._verticesWithoutID:

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

2178 yield vertex

2179

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

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

2182 yield vertex

2183 else:

2184 for vertex in self._verticesWithoutID:

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

2186 yield vertex

2187

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

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

2190 yield vertex

2191

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

2193 """

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

2195

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

2197

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

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

2200

2201 .. seealso::

2202

2203 :meth:`IterateRoots` |br|

2204 |rarr| Iterate roots of a graph.

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

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

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

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

2209 """

2210 if predicate is None:

2211 for vertex in self._verticesWithoutID:

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

2213 yield vertex

2214

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

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

2217 yield vertex

2218 else:

2219 for vertex in self._verticesWithoutID:

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

2221 yield vertex

2222

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

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

2225 yield vertex

2226

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

2228 # raise NotImplementedError()

2229 #

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

2231 # raise NotImplementedError()

2232

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

2234 """

2235 Iterate all or selected vertices in topological order.

2236

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

2238

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

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

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

2242 """

2243 outboundEdgeCounts = {}

2244 leafVertices = []

2245

2246 for vertex in self._verticesWithoutID:

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

2248 leafVertices.append(vertex)

2249 else:

2250 outboundEdgeCounts[vertex] = count

2251

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

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

2254 leafVertices.append(vertex)

2255 else:

2256 outboundEdgeCounts[vertex] = count

2257

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

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

2260

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

2262

2263 def removeVertex(vertex: Vertex):

2264 nonlocal overallCount

2265 overallCount -= 1

2266 for inboundEdge in vertex._inboundEdges:

2267 sourceVertex = inboundEdge.Source

2268 count = outboundEdgeCounts[sourceVertex] - 1

2269 outboundEdgeCounts[sourceVertex] = count

2270 if count == 0:

2271 leafVertices.append(sourceVertex)

2272

2273 if predicate is None:

2274 for vertex in leafVertices:

2275 yield vertex

2276

2277 removeVertex(vertex)

2278 else:

2279 for vertex in leafVertices:

2280 if predicate(vertex):

2281 yield vertex

2282

2283 removeVertex(vertex)

2284

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

2286 return

2287 elif overallCount > 0:

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

2289

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

2291

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

2293 """

2294 Iterate all or selected edges of a graph.

2295

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

2297

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

2299 :returns: A generator to iterate all edges.

2300 """

2301 if predicate is None:

2302 yield from self._edgesWithoutID

2303 yield from self._edgesWithID.values()

2304

2305 else:

2306 for edge in self._edgesWithoutID:

2307 if predicate(edge):

2308 yield edge

2309

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

2311 if predicate(edge):

2312 yield edge

2313

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

2315 """

2316 Iterate all or selected links of a graph.

2317

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

2319

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

2321 :returns: A generator to iterate all links.

2322 """

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

2324 yield from self._linksWithoutID

2325 yield from self._linksWithID.values()

2326

2327 else:

2328 for link in self._linksWithoutID:

2329 if predicate(link):

2330 yield link

2331

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

2333 if predicate(link):

2334 yield link

2335

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

2337 """

2338 Reverse all or selected edges of a graph.

2339

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

2341

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

2343 """

2344 if predicate is None:

2345 for edge in self._edgesWithoutID:

2346 swap = edge._source

2347 edge._source = edge._destination

2348 edge._destination = swap

2349

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

2351 swap = edge._source

2352 edge._source = edge._destination

2353 edge._destination = swap

2354

2355 for vertex in self._verticesWithoutID:

2356 swap = vertex._inboundEdges

2357 vertex._inboundEdges = vertex._outboundEdges

2358 vertex._outboundEdges = swap

2359

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

2361 swap = vertex._inboundEdges

2362 vertex._inboundEdges = vertex._outboundEdges

2363 vertex._outboundEdges = swap

2364 else:

2365 for edge in self._edgesWithoutID:

2366 if predicate(edge):

2367 edge.Reverse()

2368

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

2370 if predicate(edge):

2371 edge.Reverse()

2372

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

2374 """

2375 Reverse all or selected links of a graph.

2376

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

2378

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

2380 """

2381 if predicate is None:

2382 for link in self._linksWithoutID:

2383 swap = link._source

2384 link._source = link._destination

2385 link._destination = swap

2386

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

2388 swap = link._source

2389 link._source = link._destination

2390 link._destination = swap

2391

2392 for vertex in self._verticesWithoutID:

2393 swap = vertex._inboundLinks

2394 vertex._inboundLinks = vertex._outboundLinks

2395 vertex._outboundLinks = swap

2396

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

2398 swap = vertex._inboundLinks

2399 vertex._inboundLinks = vertex._outboundLinks

2400 vertex._outboundLinks = swap

2401 else:

2402 for link in self._linksWithoutID:

2403 if predicate(link):

2404 link.Reverse()

2405

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

2407 if predicate(link):

2408 link.Reverse()

2409

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

2411 """

2412 Remove all or selected edges of a graph.

2413

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

2415

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

2417 """

2418 if predicate is None:

2419 for edge in self._edgesWithoutID:

2420 edge._Delete()

2421

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

2423 edge._Delete()

2424

2425 self._edgesWithoutID = []

2426 self._edgesWithID = {}

2427

2428 for vertex in self._verticesWithoutID:

2429 vertex._inboundEdges = []

2430 vertex._outboundEdges = []

2431

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

2433 vertex._inboundEdges = []

2434 vertex._outboundEdges = []

2435

2436 else:

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

2438 for edge in delEdges:

2439 del self._edgesWithID[edge._id]

2440

2441 edge._source._outboundEdges.remove(edge)

2442 edge._destination._inboundEdges.remove(edge)

2443 edge._Delete()

2444

2445 for edge in self._edgesWithoutID:

2446 if predicate(edge):

2447 self._edgesWithoutID.remove(edge)

2448

2449 edge._source._outboundEdges.remove(edge)

2450 edge._destination._inboundEdges.remove(edge)

2451 edge._Delete()

2452

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

2454 """

2455 Remove all or selected links of a graph.

2456

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

2458

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

2460 """

2461 if predicate is None:

2462 for link in self._linksWithoutID:

2463 link._Delete()

2464

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

2466 link._Delete()

2467

2468 self._linksWithoutID = []

2469 self._linksWithID = {}

2470

2471 for vertex in self._verticesWithoutID:

2472 vertex._inboundLinks = []

2473 vertex._outboundLinks = []

2474

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

2476 vertex._inboundLinks = []

2477 vertex._outboundLinks = []

2478

2479 else:

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

2481 for link in delLinks:

2482 del self._linksWithID[link._id]

2483

2484 link._source._outboundLinks.remove(link)

2485 link._destination._inboundLinks.remove(link)

2486 link._Delete()

2487

2488 for link in self._linksWithoutID:

2489 if predicate(link):

2490 self._linksWithoutID.remove(link)

2491

2492 link._source._outboundLinks.remove(link)

2493 link._destination._inboundLinks.remove(link)

2494 link._Delete()

2495

2496 def HasCycle(self) -> bool:

2497 """

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

2499

2500 """

2501 # IsAcyclic ?

2502

2503 # Handle trivial case if graph is empty

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

2505 return False

2506

2507 outboundEdgeCounts = {}

2508 leafVertices = []

2509

2510 for vertex in self._verticesWithoutID:

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

2512 leafVertices.append(vertex)

2513 else:

2514 outboundEdgeCounts[vertex] = count

2515

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

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

2518 leafVertices.append(vertex)

2519 else:

2520 outboundEdgeCounts[vertex] = count

2521

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

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

2524 return True

2525

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

2527

2528 for vertex in leafVertices:

2529 overallCount -= 1

2530 for inboundEdge in vertex._inboundEdges:

2531 sourceVertex = inboundEdge.Source

2532 count = outboundEdgeCounts[sourceVertex] - 1

2533 outboundEdgeCounts[sourceVertex] = count

2534 if count == 0:

2535 leafVertices.append(sourceVertex)

2536

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

2538 if overallCount == 0:

2539 return False

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

2541 elif overallCount > 0:

2542 return True

2543

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

2545

2546

2547@export

2548class Subgraph(

2549 BaseGraph[

2550 SubgraphDictKeyType, SubgraphDictValueType,

2551 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,

2552 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,

2553 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType

2554 ],

2555 Generic[

2556 SubgraphDictKeyType, SubgraphDictValueType,

2557 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,

2558 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,

2559 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType

2560 ]

2561):

2562 """

2563 .. todo:: GRAPH::Subgraph Needs documentation.

2564

2565 """

2566

2567 _graph: 'Graph'

2568

2569 def __init__(

2570 self,

2571 graph: 'Graph',

2572 name: Nullable[str] = None,

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

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

2575 ) -> None:

2576 """

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

2578

2579 :param graph: The reference to the graph.

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

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

2582 """

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

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

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

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

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

2588 raise ex

2589

2590 super().__init__(name, keyValuePairs)

2591

2592 graph._subgraphs.add(self)

2593

2594 self._graph = graph

2595

2596 def __del__(self) -> None:

2597 """

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

2599

2600 """

2601 super().__del__()

2602

2603 @readonly

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

2605 """

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

2607

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

2609 """

2610 return self._graph

2611

2612 def __str__(self) -> str:

2613 """

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

2615

2616 """

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

2618

2619

2620@export

2621class View(

2622 BaseWithVertices[

2623 ViewDictKeyType, ViewDictValueType,

2624 GraphDictKeyType, GraphDictValueType,

2625 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,

2626 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,

2627 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType

2628 ],

2629 Generic[

2630 ViewDictKeyType, ViewDictValueType,

2631 GraphDictKeyType, GraphDictValueType,

2632 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,

2633 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,

2634 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType

2635 ]

2636):

2637 """

2638 .. todo:: GRAPH::View Needs documentation.

2639

2640 """

2641

2642 def __init__(

2643 self,

2644 graph: 'Graph',

2645 name: Nullable[str] = None,

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

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

2648 ) -> None:

2649 """

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

2651

2652 :param graph: The reference to the graph.

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

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

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

2656 """

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

2658

2659 graph._views.add(self)

2660

2661 def __del__(self) -> None:

2662 """

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

2664

2665 """

2666 super().__del__()

2667

2668 def __str__(self) -> str:

2669 """

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

2671

2672 """

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

2674

2675

2676@export

2677class Component(

2678 BaseWithVertices[

2679 ComponentDictKeyType, ComponentDictValueType,

2680 GraphDictKeyType, GraphDictValueType,

2681 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,

2682 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,

2683 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType

2684 ],

2685 Generic[

2686 ComponentDictKeyType, ComponentDictValueType,

2687 GraphDictKeyType, GraphDictValueType,

2688 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,

2689 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,

2690 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType

2691 ]

2692):

2693 """

2694 .. todo:: GRAPH::Component Needs documentation.

2695

2696 """

2697

2698 def __init__(

2699 self,

2700 graph: 'Graph',

2701 name: Nullable[str] = None,

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

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

2704 ) -> None:

2705 """

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

2707

2708 :param graph: The reference to the graph.

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

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

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

2712 """

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

2714

2715 graph._components.add(self)

2716

2717 def __del__(self) -> None:

2718 """

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

2720

2721 """

2722 super().__del__()

2723

2724 def __str__(self) -> str:

2725 """

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

2727

2728 """

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

2730

2731

2732@export

2733class Graph(

2734 BaseGraph[

2735 GraphDictKeyType, GraphDictValueType,

2736 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,

2737 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,

2738 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType

2739 ],

2740 Generic[

2741 GraphDictKeyType, GraphDictValueType,

2742 ComponentDictKeyType, ComponentDictValueType,

2743 SubgraphDictKeyType, SubgraphDictValueType,

2744 ViewDictKeyType, ViewDictValueType,

2745 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType,

2746 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType,

2747 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType

2748 ]

2749):

2750 """

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

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

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

2754 """

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

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

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

2758

2759 def __init__(

2760 self,

2761 name: Nullable[str] = None,

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

2763 ) -> None:

2764 """

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

2766

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

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

2769 """

2770 super().__init__(name, keyValuePairs)

2771

2772 self._subgraphs = set()

2773 self._views = set()

2774 self._components = set()

2775

2776 def __del__(self) -> None:

2777 """

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

2779

2780 """

2781 try:

2782 del self._subgraphs

2783 del self._views

2784 del self._components

2785 except AttributeError:

2786 pass

2787

2788 super().__del__()

2789

2790 @readonly

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

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

2793

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

2795 return self._subgraphs

2796

2797 @readonly

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

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

2800

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

2802 return self._views

2803

2804 @readonly

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

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

2807

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

2809 return self._components

2810

2811 @readonly

2812 def SubgraphCount(self) -> int:

2813 """Read-only property to return the number of subgraphs in this graph.

2814

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

2816 return len(self._subgraphs)

2817

2818 @readonly

2819 def ViewCount(self) -> int:

2820 """Read-only property to return the number of views in this graph.

2821

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

2823 return len(self._views)

2824

2825 @readonly

2826 def ComponentCount(self) -> int:

2827 """Read-only property to return the number of components in this graph.

2828

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

2830 return len(self._components)

2831

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

2833 """

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

2835

2836 """

2837 def gen():

2838 yield from self._verticesWithoutID

2839 yield from self._verticesWithID

2840 return iter(gen())

2841

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

2843 """

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

2845

2846 """

2847 if vertexID is None:

2848 return len(self._verticesWithoutID) >= 1

2849 else:

2850 return vertexID in self._verticesWithID

2851

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

2853 """

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

2855

2856 """

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

2858

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

2860 """

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

2862

2863 """

2864 if vertexID is None:

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

2866 return self._verticesWithoutID[0]

2867 elif l == 0:

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

2869 else:

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

2871 else:

2872 return self._verticesWithID[vertexID]

2873

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

2875 """

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

2877

2878 """

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

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

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

2882 return vertices[0]

2883 elif l == 0:

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

2885 else:

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

2887

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

2889 raise NotImplementedError()

2890

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

2892 """

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

2894

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

2896

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

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

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

2900 """

2901 graph = Graph(self._name)

2902 if copyGraphDict:

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

2904

2905 if predicate is None:

2906 for vertex in self._verticesWithoutID:

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

2908 if copyVertexDict:

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

2910

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

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

2913 if copyVertexDict:

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

2915 else:

2916 for vertex in self._verticesWithoutID:

2917 if predicate(vertex):

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

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

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

2921

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

2923 if predicate(vertex):

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

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

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

2927

2928 return graph

2929

2930 # class Iterator():

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

2932

2933 # def CheckForNegativeCycles(self):

2934 # raise NotImplementedError()

2935 # # Bellman-Ford

2936 # # Floyd-Warshall

2937 #

2938 # def IsStronglyConnected(self):

2939 # raise NotImplementedError()

2940 #

2941 # def GetStronglyConnectedComponents(self):

2942 # raise NotImplementedError()

2943 # # Tarjan's and Kosaraju's algorithm

2944 #

2945 # def TravelingSalesmanProblem(self):

2946 # raise NotImplementedError()

2947 # # Held-Karp

2948 # # branch and bound

2949 #

2950 # def GetBridges(self):

2951 # raise NotImplementedError()

2952 #

2953 # def GetArticulationPoints(self):

2954 # raise NotImplementedError()

2955 #

2956 # def MinimumSpanningTree(self):

2957 # raise NotImplementedError()

2958 # # Kruskal

2959 # # Prim's algorithm

2960 # # Buruvka's algorithm

2961

2962 def __repr__(self) -> str:

2963 """

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

2965

2966 """

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

2968 if self._name is None:

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

2970 else:

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

2972

2973 def __str__(self) -> str:

2974 """

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

2976

2977 """

2978 if self._name is None:

2979 return f"Graph: unnamed graph"

2980 else:

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

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

1198 statements