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

1212 statements  

« prev     ^ index     » next       coverage.py v7.11.0, created at 2025-10-19 06:41 +0000

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

2# _____ _ _ ____ _ # 

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

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

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

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

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

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

9# Authors: # 

10# Patrick Lehmann # 

11# # 

12# License: # 

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

14# Copyright 2017-2025 Patrick Lehmann - Bötzingen, Germany # 

15# # 

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

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

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

19# # 

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

21# # 

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

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

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

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

26# limitations under the License. # 

27# # 

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

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

30# 

31""" 

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

33 

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. 

36 

37.. admonition:: Example Graph 

38 

39 .. mermaid:: 

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

41 

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) 

45 

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 

52 

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

54""" 

55import heapq 

56from collections import deque 

57from itertools import chain 

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

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

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

61 

62try: 

63 from pyTooling.Decorators import export, readonly 

64 from pyTooling.MetaClasses import ExtendedType 

65 from pyTooling.Exceptions import ToolingException 

66 from pyTooling.Common import getFullyQualifiedName 

67 from pyTooling.Tree import Node 

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

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

70 

71 try: 

72 from Decorators import export, readonly 

73 from MetaClasses import ExtendedType, mixin 

74 from Exceptions import ToolingException 

75 from Common import getFullyQualifiedName 

76 from Tree import Node 

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

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

79 raise ex 

80 

81 

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

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

84 

85DictValueType = TypeVar("DictValueType") 

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

87 

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

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

90 

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

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

93 

94ValueType = TypeVar("ValueType") 

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

96 

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

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

99 

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

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

102 

103VertexValueType = TypeVar("VertexValueType") 

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

105 

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

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

108 

109VertexDictValueType = TypeVar("VertexDictValueType") 

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

111 

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

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

114 

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

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

117 

118EdgeValueType = TypeVar("EdgeValueType") 

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

120 

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

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

123 

124EdgeDictValueType = TypeVar("EdgeDictValueType") 

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

126 

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

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

129 

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

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

132 

133LinkValueType = TypeVar("LinkValueType") 

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

135 

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

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

138 

139LinkDictValueType = TypeVar("LinkDictValueType") 

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

141 

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

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

144 

145ComponentDictValueType = TypeVar("ComponentDictValueType") 

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

147 

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

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

150 

151SubgraphDictValueType = TypeVar("SubgraphDictValueType") 

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

153 

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

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

156 

157ViewDictValueType = TypeVar("ViewDictValueType") 

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

159 

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

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

162 

163GraphDictValueType = TypeVar("GraphDictValueType") 

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

165 

166 

167@export 

168class GraphException(ToolingException): 

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

170 

171 

172@export 

173class InternalError(GraphException): 

174 """ 

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

176 

177 .. danger:: 

178 

179 This exception should never be raised. 

180 

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

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

183 """ 

184 

185 

186@export 

187class NotInSameGraph(GraphException): 

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

189 

190 

191@export 

192class DuplicateVertexError(GraphException): 

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

194 

195 

196@export 

197class DuplicateEdgeError(GraphException): 

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

199 

200 

201@export 

202class DestinationNotReachable(GraphException): 

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

204 

205 

206@export 

207class NotATreeError(GraphException): 

208 """ 

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

210 

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

212 """ 

213 

214 

215@export 

216class CycleError(GraphException): 

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

218 

219 

220@export 

221class Base( 

222 Generic[DictKeyType, DictValueType], 

223 metaclass=ExtendedType, slots=True 

224): 

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

226 

227 def __init__( 

228 self, 

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

230 ) -> None: 

231 """ 

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

233 

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

235 """ 

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

237 

238 def __del__(self): 

239 """ 

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

241 

242 """ 

243 try: 

244 del self._dict 

245 except AttributeError: 

246 pass 

247 

248 def Delete(self) -> None: 

249 self._dict = None 

250 

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

252 """ 

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

254 

255 :param key: The key to look for. 

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

257 """ 

258 return self._dict[key] 

259 

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

261 """ 

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

263 

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

265 

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

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

268 """ 

269 self._dict[key] = value 

270 

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

272 """ 

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

274 

275 :param key: The key to remove. 

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

277 """ 

278 del self._dict[key] 

279 

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

281 """ 

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

283 

284 :param key: The key to check. 

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

286 """ 

287 return key in self._dict 

288 

289 def __len__(self) -> int: 

290 """ 

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

292 

293 :returns: Number of attached attributes. 

294 """ 

295 return len(self._dict) 

296 

297 

298@export 

299class BaseWithIDValueAndWeight( 

300 Base[DictKeyType, DictValueType], 

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

302): 

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

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

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

306 

307 def __init__( 

308 self, 

309 identifier: Nullable[IDType] = None, 

310 value: Nullable[ValueType] = None, 

311 weight: Nullable[WeightType] = None, 

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

313 ) -> None: 

314 """ 

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

316 

317 :param identifier: The optional unique ID. 

318 :param value: The optional value. 

319 :param weight: The optional weight. 

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

321 """ 

322 super().__init__(keyValuePairs) 

323 

324 self._id = identifier 

325 self._value = value 

326 self._weight = weight 

327 

328 @readonly 

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

330 """ 

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

332 

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

334 

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

336 """ 

337 return self._id 

338 

339 @property 

340 def Value(self) -> ValueType: 

341 """ 

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

343 

344 :returns: The value. 

345 """ 

346 return self._value 

347 

348 @Value.setter 

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

350 self._value = value 

351 

352 @property 

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

354 """ 

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

356 

357 :returns: The weight of an edge. 

358 """ 

359 return self._weight 

360 

361 @Weight.setter 

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

363 self._weight = value 

364 

365 

366@export 

367class BaseWithName( 

368 Base[DictKeyType, DictValueType], 

369 Generic[DictKeyType, DictValueType] 

370): 

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

372 

373 def __init__( 

374 self, 

375 name: Nullable[str] = None, 

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

377 ) -> None: 

378 """ 

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

380 

381 :param name: The optional name. 

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

383 """ 

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

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

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

387 raise ex 

388 

389 super().__init__(keyValuePairs) 

390 

391 self._name = name 

392 

393 @property 

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

395 """ 

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

397 

398 :returns: The value of a component. 

399 """ 

400 return self._name 

401 

402 @Name.setter 

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

404 if not isinstance(value, str): 

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

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

407 raise ex 

408 

409 self._name = value 

410 

411 

412@export 

413class BaseWithVertices( 

414 BaseWithName[DictKeyType, DictValueType], 

415 Generic[ 

416 DictKeyType, DictValueType, 

417 GraphDictKeyType, GraphDictValueType, 

418 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType, 

419 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType, 

420 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType 

421 ] 

422): 

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

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

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

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

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

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

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

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

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

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

433 

434 def __init__( 

435 self, 

436 graph: 'Graph', 

437 name: Nullable[str] = None, 

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

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

440 ) -> None: 

441 """ 

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

443 

444 :param graph: The reference to the graph. 

445 :param name: The optional name. 

446 :param vertices: The optional list of vertices. 

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

448 """ 

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

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

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

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

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

454 raise ex 

455 

456 super().__init__(name, keyValuePairs) 

457 

458 self._graph = graph 

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

460 

461 def __del__(self): 

462 """ 

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

464 

465 """ 

466 try: 

467 del self._vertices 

468 except AttributeError: 

469 pass 

470 

471 super().__del__() 

472 

473 @readonly 

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

475 """ 

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

477 

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

479 """ 

480 return self._graph 

481 

482 @readonly 

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

484 """ 

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

486 

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

488 """ 

489 return self._vertices 

490 

491 @readonly 

492 def VertexCount(self) -> int: 

493 """ 

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

495 

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

497 """ 

498 return len(self._vertices) 

499 

500 

501@export 

502class Vertex( 

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

504 Generic[ 

505 GraphDictKeyType, GraphDictValueType, 

506 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType, 

507 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType, 

508 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType 

509 ] 

510): 

511 """ 

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

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

514 """ 

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

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

517 _component: 'Component' 

518 _views: Dict[Hashable, 'View'] 

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

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

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

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

523 

524 def __init__( 

525 self, 

526 vertexID: Nullable[VertexIDType] = None, 

527 value: Nullable[VertexValueType] = None, 

528 weight: Nullable[VertexWeightType] = None, 

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

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

531 subgraph: Nullable['Subgraph'] = None 

532 ) -> None: 

533 """ 

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

535 

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

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

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

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

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

541 :param subgraph: undocumented 

542 """ 

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

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

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

546 raise ex 

547 

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

549 

550 if subgraph is None: 

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

552 self._subgraph = None 

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

554 

555 if vertexID is None: 

556 self._graph._verticesWithoutID.append(self) 

557 elif vertexID not in self._graph._verticesWithID: 

558 self._graph._verticesWithID[vertexID] = self 

559 else: 

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

561 else: 

562 self._graph = subgraph._graph 

563 self._subgraph = subgraph 

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

565 

566 if vertexID is None: 

567 subgraph._verticesWithoutID.append(self) 

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

569 subgraph._verticesWithID[vertexID] = self 

570 else: 

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

572 

573 self._views = {} 

574 self._inboundEdges = [] 

575 self._outboundEdges = [] 

576 self._inboundLinks = [] 

577 self._outboundLinks = [] 

578 

579 def __del__(self): 

580 """ 

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

582 

583 """ 

584 try: 

585 del self._views 

586 del self._inboundEdges 

587 del self._outboundEdges 

588 del self._inboundLinks 

589 del self._outboundLinks 

590 except AttributeError: 

591 pass 

592 

593 super().__del__() 

594 

595 def Delete(self) -> None: 

596 for edge in self._outboundEdges: 

597 edge._destination._inboundEdges.remove(edge) 

598 edge._Delete() 

599 for edge in self._inboundEdges: 

600 edge._source._outboundEdges.remove(edge) 

601 edge._Delete() 

602 for link in self._outboundLinks: 

603 link._destination._inboundLinks.remove(link) 

604 link._Delete() 

605 for link in self._inboundLinks: 

606 link._source._outboundLinks.remove(link) 

607 link._Delete() 

608 

609 if self._id is None: 

610 self._graph._verticesWithoutID.remove(self) 

611 else: 

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

613 

614 # subgraph 

615 

616 # component 

617 

618 # views 

619 self._views = None 

620 self._inboundEdges = None 

621 self._outboundEdges = None 

622 self._inboundLinks = None 

623 self._outboundLinks = None 

624 

625 super().Delete() 

626 assert getrefcount(self) == 1 

627 

628 @readonly 

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

630 """ 

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

632 

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

634 """ 

635 return self._graph 

636 

637 @readonly 

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

639 """ 

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

641 

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

643 """ 

644 return self._component 

645 

646 @readonly 

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

648 """ 

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

650 

651 :returns: Tuple of inbound edges. 

652 """ 

653 return tuple(self._inboundEdges) 

654 

655 @readonly 

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

657 """ 

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

659 

660 :returns: Tuple of outbound edges. 

661 """ 

662 return tuple(self._outboundEdges) 

663 

664 @readonly 

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

666 """ 

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

668 

669 :returns: Tuple of inbound links. 

670 """ 

671 return tuple(self._inboundLinks) 

672 

673 @readonly 

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

675 """ 

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

677 

678 :returns: Tuple of outbound links. 

679 """ 

680 return tuple(self._outboundLinks) 

681 

682 @readonly 

683 def EdgeCount(self) -> int: 

684 """ 

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

686 

687 :returns: Number of inbound and outbound edges. 

688 """ 

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

690 

691 @readonly 

692 def InboundEdgeCount(self) -> int: 

693 """ 

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

695 

696 :returns: Number of inbound edges. 

697 """ 

698 return len(self._inboundEdges) 

699 

700 @readonly 

701 def OutboundEdgeCount(self) -> int: 

702 """ 

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

704 

705 :returns: Number of outbound edges. 

706 """ 

707 return len(self._outboundEdges) 

708 

709 @readonly 

710 def LinkCount(self) -> int: 

711 """ 

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

713 

714 :returns: Number of inbound and outbound links. 

715 """ 

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

717 

718 @readonly 

719 def InboundLinkCount(self) -> int: 

720 """ 

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

722 

723 :returns: Number of inbound links. 

724 """ 

725 return len(self._inboundLinks) 

726 

727 @readonly 

728 def OutboundLinkCount(self) -> int: 

729 """ 

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

731 

732 :returns: Number of outbound links. 

733 """ 

734 return len(self._outboundLinks) 

735 

736 @readonly 

737 def IsRoot(self) -> bool: 

738 """ 

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

740 

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

742 

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

744 

745 .. seealso:: 

746 

747 :meth:`IsLeaf` |br| 

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

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

750 |rarr| Iterate all roots of a graph. 

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

752 |rarr| Iterate all leafs of a graph. 

753 """ 

754 return len(self._inboundEdges) == 0 

755 

756 @readonly 

757 def IsLeaf(self) -> bool: 

758 """ 

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

760 

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

762 

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

764 

765 .. seealso:: 

766 

767 :meth:`IsRoot` |br| 

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

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

770 |rarr| Iterate all roots of a graph. 

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

772 |rarr| Iterate all leafs of a graph. 

773 """ 

774 return len(self._outboundEdges) == 0 

775 

776 @readonly 

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

778 """ 

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

780 

781 :returns: Tuple of predecessor vertices. 

782 """ 

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

784 

785 @readonly 

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

787 """ 

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

789 

790 :returns: Tuple of successor vertices. 

791 """ 

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

793 

794 def EdgeToVertex( 

795 self, 

796 vertex: 'Vertex', 

797 edgeID: Nullable[EdgeIDType] = None, 

798 edgeWeight: Nullable[EdgeWeightType] = None, 

799 edgeValue: Nullable[VertexValueType] = None, 

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

801 ) -> 'Edge': 

802 """ 

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

804 

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

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

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

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

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

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

811 

812 .. seealso:: 

813 

814 :meth:`EdgeFromVertex` |br| 

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

816 :meth:`EdgeToNewVertex` |br| 

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

818 :meth:`EdgeFromNewVertex` |br| 

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

820 :meth:`LinkToVertex` |br| 

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

822 :meth:`LinkFromVertex` |br| 

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

824 

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

826 """ 

827 if self._subgraph is vertex._subgraph: 

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

829 

830 self._outboundEdges.append(edge) 

831 vertex._inboundEdges.append(edge) 

832 

833 if self._subgraph is None: 

834 # TODO: move into Edge? 

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

836 if edgeID is None: 

837 self._graph._edgesWithoutID.append(edge) 

838 elif edgeID not in self._graph._edgesWithID: 

839 self._graph._edgesWithID[edgeID] = edge 

840 else: 

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

842 else: 

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

844 if edgeID is None: 

845 self._subgraph._edgesWithoutID.append(edge) 

846 elif edgeID not in self._subgraph._edgesWithID: 

847 self._subgraph._edgesWithID[edgeID] = edge 

848 else: 

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

850 else: 

851 # FIXME: needs an error message 

852 raise GraphException() 

853 

854 return edge 

855 

856 def EdgeFromVertex( 

857 self, 

858 vertex: 'Vertex', 

859 edgeID: Nullable[EdgeIDType] = None, 

860 edgeWeight: Nullable[EdgeWeightType] = None, 

861 edgeValue: Nullable[VertexValueType] = None, 

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

863 ) -> 'Edge': 

864 """ 

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

866 

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

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

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

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

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

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

873 

874 .. seealso:: 

875 

876 :meth:`EdgeToVertex` |br| 

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

878 :meth:`EdgeToNewVertex` |br| 

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

880 :meth:`EdgeFromNewVertex` |br| 

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

882 :meth:`LinkToVertex` |br| 

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

884 :meth:`LinkFromVertex` |br| 

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

886 

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

888 """ 

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

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

891 

892 vertex._outboundEdges.append(edge) 

893 self._inboundEdges.append(edge) 

894 

895 if self._subgraph is None: 

896 # TODO: move into Edge? 

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

898 if edgeID is None: 

899 self._graph._edgesWithoutID.append(edge) 

900 elif edgeID not in self._graph._edgesWithID: 

901 self._graph._edgesWithID[edgeID] = edge 

902 else: 

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

904 else: 

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

906 if edgeID is None: 

907 self._subgraph._edgesWithoutID.append(edge) 

908 elif edgeID not in self._graph._edgesWithID: 

909 self._subgraph._edgesWithID[edgeID] = edge 

910 else: 

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

912 else: 

913 # FIXME: needs an error message 

914 raise GraphException() 

915 

916 return edge 

917 

918 def EdgeToNewVertex( 

919 self, 

920 vertexID: Nullable[VertexIDType] = None, 

921 vertexValue: Nullable[VertexValueType] = None, 

922 vertexWeight: Nullable[VertexWeightType] = None, 

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

924 edgeID: Nullable[EdgeIDType] = None, 

925 edgeWeight: Nullable[EdgeWeightType] = None, 

926 edgeValue: Nullable[VertexValueType] = None, 

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

928 ) -> 'Edge': 

929 """ 

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

931 

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

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

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

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

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

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

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

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

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

941 

942 .. seealso:: 

943 

944 :meth:`EdgeToVertex` |br| 

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

946 :meth:`EdgeFromVertex` |br| 

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

948 :meth:`EdgeFromNewVertex` |br| 

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

950 :meth:`LinkToVertex` |br| 

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

952 :meth:`LinkFromVertex` |br| 

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

954 

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

956 """ 

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

958 

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

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

961 

962 self._outboundEdges.append(edge) 

963 vertex._inboundEdges.append(edge) 

964 

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

966 # TODO: move into Edge? 

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

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

969 self._graph._edgesWithoutID.append(edge) 

970 elif edgeID not in self._graph._edgesWithID: 

971 self._graph._edgesWithID[edgeID] = edge 

972 else: 

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

974 else: 

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

976 if edgeID is None: 

977 self._subgraph._edgesWithoutID.append(edge) 

978 elif edgeID not in self._graph._edgesWithID: 

979 self._subgraph._edgesWithID[edgeID] = edge 

980 else: 

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

982 else: 

983 # FIXME: needs an error message 

984 raise GraphException() 

985 

986 return edge 

987 

988 def EdgeFromNewVertex( 

989 self, 

990 vertexID: Nullable[VertexIDType] = None, 

991 vertexValue: Nullable[VertexValueType] = None, 

992 vertexWeight: Nullable[VertexWeightType] = None, 

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

994 edgeID: Nullable[EdgeIDType] = None, 

995 edgeWeight: Nullable[EdgeWeightType] = None, 

996 edgeValue: Nullable[VertexValueType] = None, 

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

998 ) -> 'Edge': 

999 """ 

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

1001 

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

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

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

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

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

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

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

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

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

1011 

1012 .. seealso:: 

1013 

1014 :meth:`EdgeToVertex` |br| 

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

1016 :meth:`EdgeFromVertex` |br| 

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

1018 :meth:`EdgeToNewVertex` |br| 

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

1020 :meth:`LinkToVertex` |br| 

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

1022 :meth:`LinkFromVertex` |br| 

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

1024 

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

1026 """ 

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

1028 

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

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

1031 

1032 vertex._outboundEdges.append(edge) 

1033 self._inboundEdges.append(edge) 

1034 

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

1036 # TODO: move into Edge? 

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

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

1039 self._graph._edgesWithoutID.append(edge) 

1040 elif edgeID not in self._graph._edgesWithID: 

1041 self._graph._edgesWithID[edgeID] = edge 

1042 else: 

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

1044 else: 

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

1046 if edgeID is None: 

1047 self._subgraph._edgesWithoutID.append(edge) 

1048 elif edgeID not in self._graph._edgesWithID: 

1049 self._subgraph._edgesWithID[edgeID] = edge 

1050 else: 

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

1052 else: 

1053 # FIXME: needs an error message 

1054 raise GraphException() 

1055 

1056 return edge 

1057 

1058 def LinkToVertex( 

1059 self, 

1060 vertex: 'Vertex', 

1061 linkID: Nullable[EdgeIDType] = None, 

1062 linkWeight: Nullable[EdgeWeightType] = None, 

1063 linkValue: Nullable[VertexValueType] = None, 

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

1065 ) -> 'Link': 

1066 """ 

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

1068 

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

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

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

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

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

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

1075 

1076 .. seealso:: 

1077 

1078 :meth:`EdgeToVertex` |br| 

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

1080 :meth:`EdgeFromVertex` |br| 

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

1082 :meth:`EdgeToNewVertex` |br| 

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

1084 :meth:`EdgeFromNewVertex` |br| 

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

1086 :meth:`LinkFromVertex` |br| 

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

1088 

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

1090 """ 

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

1092 # FIXME: needs an error message 

1093 raise GraphException() 

1094 else: 

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

1096 

1097 self._outboundLinks.append(link) 

1098 vertex._inboundLinks.append(link) 

1099 

1100 if self._subgraph is None: 

1101 # TODO: move into Edge? 

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

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

1104 self._graph._linksWithoutID.append(link) 

1105 elif linkID not in self._graph._linksWithID: 

1106 self._graph._linksWithID[linkID] = link 

1107 else: 

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

1109 else: 

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

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

1112 self._subgraph._linksWithoutID.append(link) 

1113 vertex._subgraph._linksWithoutID.append(link) 

1114 elif linkID not in self._graph._linksWithID: 

1115 self._subgraph._linksWithID[linkID] = link 

1116 vertex._subgraph._linksWithID[linkID] = link 

1117 else: 

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

1119 

1120 return link 

1121 

1122 def LinkFromVertex( 

1123 self, 

1124 vertex: 'Vertex', 

1125 linkID: Nullable[EdgeIDType] = None, 

1126 linkWeight: Nullable[EdgeWeightType] = None, 

1127 linkValue: Nullable[VertexValueType] = None, 

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

1129 ) -> 'Edge': 

1130 """ 

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

1132 

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

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

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

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

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

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

1139 

1140 .. seealso:: 

1141 

1142 :meth:`EdgeToVertex` |br| 

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

1144 :meth:`EdgeFromVertex` |br| 

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

1146 :meth:`EdgeToNewVertex` |br| 

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

1148 :meth:`EdgeFromNewVertex` |br| 

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

1150 :meth:`LinkToVertex` |br| 

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

1152 

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

1154 """ 

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

1156 # FIXME: needs an error message 

1157 raise GraphException() 

1158 else: 

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

1160 

1161 vertex._outboundLinks.append(link) 

1162 self._inboundLinks.append(link) 

1163 

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

1165 # TODO: move into Edge? 

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

1167 if linkID is None: 

1168 self._graph._linksWithoutID.append(link) 

1169 elif linkID not in self._graph._linksWithID: 

1170 self._graph._linksWithID[linkID] = link 

1171 else: 

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

1173 else: 

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

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

1176 self._subgraph._linksWithoutID.append(link) 

1177 vertex._subgraph._linksWithoutID.append(link) 

1178 elif linkID not in self._graph._linksWithID: 

1179 self._subgraph._linksWithID[linkID] = link 

1180 vertex._subgraph._linksWithID[linkID] = link 

1181 else: 

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

1183 

1184 return link 

1185 

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

1187 """ 

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

1189 

1190 :param destination: Destination vertex to check. 

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

1192 

1193 .. seealso:: 

1194 

1195 :meth:`HasEdgeFromSource` |br| 

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

1197 :meth:`HasLinkToDestination` |br| 

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

1199 :meth:`HasLinkFromSource` |br| 

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

1201 """ 

1202 for edge in self._outboundEdges: 

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

1204 return True 

1205 

1206 return False 

1207 

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

1209 """ 

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

1211 

1212 :param source: Source vertex to check. 

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

1214 

1215 .. seealso:: 

1216 

1217 :meth:`HasEdgeToDestination` |br| 

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

1219 :meth:`HasLinkToDestination` |br| 

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

1221 :meth:`HasLinkFromSource` |br| 

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

1223 """ 

1224 for edge in self._inboundEdges: 

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

1226 return True 

1227 

1228 return False 

1229 

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

1231 """ 

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

1233 

1234 :param destination: Destination vertex to check. 

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

1236 

1237 .. seealso:: 

1238 

1239 :meth:`HasEdgeToDestination` |br| 

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

1241 :meth:`HasEdgeFromSource` |br| 

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

1243 :meth:`HasLinkFromSource` |br| 

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

1245 """ 

1246 for link in self._outboundLinks: 

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

1248 return True 

1249 

1250 return False 

1251 

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

1253 """ 

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

1255 

1256 :param source: Source vertex to check. 

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

1258 

1259 .. seealso:: 

1260 

1261 :meth:`HasEdgeToDestination` |br| 

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

1263 :meth:`HasEdgeFromSource` |br| 

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

1265 :meth:`HasLinkToDestination` |br| 

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

1267 """ 

1268 for link in self._inboundLinks: 

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

1270 return True 

1271 

1272 return False 

1273 

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

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

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

1277 break 

1278 else: 

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

1280 

1281 edge.Delete() 

1282 

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

1284 for edge in self._inboundEdges: 

1285 if edge._source is source: 

1286 break 

1287 else: 

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

1289 

1290 edge.Delete() 

1291 

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

1293 for link in self._outboundLinks: 

1294 if link._destination is destination: 

1295 break 

1296 else: 

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

1298 

1299 link.Delete() 

1300 

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

1302 for link in self._inboundLinks: 

1303 if link._source is source: 

1304 break 

1305 else: 

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

1307 

1308 link.Delete() 

1309 

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

1311 """ 

1312 Creates a copy of this vertex in another graph. 

1313 

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

1315 can be established. 

1316 

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

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

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

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

1321 :returns: The newly created vertex. 

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

1323 """ 

1324 if graph is self._graph: 

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

1326 

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

1328 if copyDict: 

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

1330 

1331 if linkingKeyToOriginalVertex is not None: 

1332 vertex._dict[linkingKeyToOriginalVertex] = self 

1333 if linkingKeyFromOriginalVertex is not None: 

1334 self._dict[linkingKeyFromOriginalVertex] = vertex 

1335 

1336 return vertex 

1337 

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

1339 """ 

1340 Iterate all or selected outbound edges of this vertex. 

1341 

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

1343 

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

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

1346 """ 

1347 if predicate is None: 

1348 for edge in self._outboundEdges: 

1349 yield edge 

1350 else: 

1351 for edge in self._outboundEdges: 

1352 if predicate(edge): 

1353 yield edge 

1354 

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

1356 """ 

1357 Iterate all or selected inbound edges of this vertex. 

1358 

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

1360 

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

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

1363 """ 

1364 if predicate is None: 

1365 for edge in self._inboundEdges: 

1366 yield edge 

1367 else: 

1368 for edge in self._inboundEdges: 

1369 if predicate(edge): 

1370 yield edge 

1371 

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

1373 """ 

1374 Iterate all or selected outbound links of this vertex. 

1375 

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

1377 

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

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

1380 """ 

1381 if predicate is None: 

1382 for link in self._outboundLinks: 

1383 yield link 

1384 else: 

1385 for link in self._outboundLinks: 

1386 if predicate(link): 

1387 yield link 

1388 

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

1390 """ 

1391 Iterate all or selected inbound links of this vertex. 

1392 

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

1394 

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

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

1397 """ 

1398 if predicate is None: 

1399 for link in self._inboundLinks: 

1400 yield link 

1401 else: 

1402 for link in self._inboundLinks: 

1403 if predicate(link): 

1404 yield link 

1405 

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

1407 """ 

1408 Iterate all or selected successor vertices of this vertex. 

1409 

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

1411 

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

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

1414 """ 

1415 if predicate is None: 

1416 for edge in self._outboundEdges: 

1417 yield edge.Destination 

1418 else: 

1419 for edge in self._outboundEdges: 

1420 if predicate(edge): 

1421 yield edge.Destination 

1422 

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

1424 """ 

1425 Iterate all or selected predecessor vertices of this vertex. 

1426 

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

1428 

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

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

1431 """ 

1432 if predicate is None: 

1433 for edge in self._inboundEdges: 

1434 yield edge.Source 

1435 else: 

1436 for edge in self._inboundEdges: 

1437 if predicate(edge): 

1438 yield edge.Source 

1439 

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

1441 """ 

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

1443 

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

1445 

1446 .. seealso:: 

1447 

1448 :meth:`IterateVerticesDFS` |br| 

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

1450 """ 

1451 visited: Set[Vertex] = set() 

1452 queue: Deque[Vertex] = deque() 

1453 

1454 yield self 

1455 visited.add(self) 

1456 for edge in self._outboundEdges: 

1457 nextVertex = edge.Destination 

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

1459 queue.appendleft(nextVertex) 

1460 visited.add(nextVertex) 

1461 

1462 while queue: 

1463 vertex = queue.pop() 

1464 yield vertex 

1465 for edge in vertex._outboundEdges: 

1466 nextVertex = edge.Destination 

1467 if nextVertex not in visited: 

1468 queue.appendleft(nextVertex) 

1469 visited.add(nextVertex) 

1470 

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

1472 """ 

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

1474 

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

1476 

1477 .. seealso:: 

1478 

1479 :meth:`IterateVerticesBFS` |br| 

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

1481 

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

1483 """ 

1484 visited: Set[Vertex] = set() 

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

1486 

1487 yield self 

1488 visited.add(self) 

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

1490 

1491 while True: 

1492 try: 

1493 edge = next(stack[-1]) 

1494 nextVertex = edge._destination 

1495 if nextVertex not in visited: 

1496 visited.add(nextVertex) 

1497 yield nextVertex 

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

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

1500 except StopIteration: 

1501 stack.pop() 

1502 

1503 if len(stack) == 0: 

1504 return 

1505 

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

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

1508 yield (self, ) 

1509 return 

1510 

1511 visited: Set[Vertex] = set() 

1512 vertexStack: List[Vertex] = list() 

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

1514 

1515 visited.add(self) 

1516 vertexStack.append(self) 

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

1518 

1519 while True: 

1520 try: 

1521 edge = next(iteratorStack[-1]) 

1522 nextVertex = edge._destination 

1523 if nextVertex in visited: 

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

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

1526 for i, vertex in enumerate(vertexStack): 

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

1528 raise ex 

1529 

1530 vertexStack.append(nextVertex) 

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

1532 yield tuple(vertexStack) 

1533 vertexStack.pop() 

1534 else: 

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

1536 

1537 except StopIteration: 

1538 vertexStack.pop() 

1539 iteratorStack.pop() 

1540 

1541 if len(vertexStack) == 0: 

1542 return 

1543 

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

1545 """ 

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

1547 

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

1549 

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

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

1552 

1553 :param destination: The destination vertex to reach. 

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

1555 """ 

1556 # Trivial case if start is destination 

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

1558 yield self 

1559 return 

1560 

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

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

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

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

1565 parent: 'Node' 

1566 ref: Vertex 

1567 

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

1569 self.parent = parent 

1570 self.ref = ref 

1571 

1572 def __str__(self): 

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

1574 

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

1576 startNode = Node(None, self) 

1577 visited: Set[Vertex] = set() 

1578 queue: Deque[Node] = deque() 

1579 

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

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

1582 visited.add(self) 

1583 for edge in self._outboundEdges: 

1584 nextVertex = edge.Destination 

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

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

1587 destinationNode = Node(startNode, nextVertex) 

1588 break 

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

1590 # Ignore backward-edges and side-edges. 

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

1592 visited.add(nextVertex) 

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

1594 else: 

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

1596 while queue: 

1597 node = queue.pop() 

1598 for edge in node.ref._outboundEdges: 

1599 nextVertex = edge.Destination 

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

1601 if nextVertex is destination: 

1602 destinationNode = Node(node, nextVertex) 

1603 break 

1604 # Ignore backward-edges and side-edges. 

1605 if nextVertex not in visited: 

1606 visited.add(nextVertex) 

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

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

1609 else: 

1610 continue 

1611 break 

1612 else: 

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

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

1615 

1616 # Reverse order of linked list from destinationNode to startNode 

1617 currentNode = destinationNode 

1618 previousNode = destinationNode.parent 

1619 currentNode.parent = None 

1620 while previousNode is not None: 

1621 node = previousNode.parent 

1622 previousNode.parent = currentNode 

1623 currentNode = previousNode 

1624 previousNode = node 

1625 

1626 # Scan reversed linked-list and yield referenced vertices 

1627 yield startNode.ref 

1628 node = startNode.parent 

1629 while node is not None: 

1630 yield node.ref 

1631 node = node.parent 

1632 

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

1634 """ 

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

1636 

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

1638 

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

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

1641 

1642 :param destination: The destination vertex to reach. 

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

1644 """ 

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

1646 

1647 # Trivial case if start is destination 

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

1649 yield self 

1650 return 

1651 

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

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

1654 # represents. 

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

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

1657 parent: 'Node' 

1658 distance: EdgeWeightType 

1659 ref: Vertex 

1660 

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

1662 self.parent = parent 

1663 self.distance = distance 

1664 self.ref = ref 

1665 

1666 def __lt__(self, other): 

1667 return self.distance < other.distance 

1668 

1669 def __str__(self): 

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

1671 

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

1673 startNode = Node(None, 0, self) 

1674 priorityQueue = [startNode] 

1675 

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

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

1678 visited.add(self) 

1679 for edge in self._outboundEdges: 

1680 nextVertex = edge.Destination 

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

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

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

1684 break 

1685 # Ignore backward-edges and side-edges. 

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

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

1688 visited.add(nextVertex) 

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

1690 else: 

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

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

1693 node = heapq.heappop(priorityQueue) 

1694 for edge in node.ref._outboundEdges: 

1695 nextVertex = edge.Destination 

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

1697 if nextVertex is destination: 

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

1699 break 

1700 # Ignore backward-edges and side-edges. 

1701 if nextVertex not in visited: 

1702 visited.add(nextVertex) 

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

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

1705 else: 

1706 continue 

1707 break 

1708 else: 

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

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

1711 

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

1713 currentNode = destinationNode 

1714 previousNode = destinationNode.parent 

1715 currentNode.parent = None 

1716 while previousNode is not None: 

1717 node = previousNode.parent 

1718 previousNode.parent = currentNode 

1719 currentNode = previousNode 

1720 previousNode = node 

1721 

1722 # Scan reversed linked-list and yield referenced vertices 

1723 yield startNode.ref, startNode.distance 

1724 node = startNode.parent 

1725 while node is not None: 

1726 yield node.ref, node.distance 

1727 node = node.parent 

1728 

1729 # Other possible algorithms: 

1730 # * Bellman-Ford 

1731 # * Floyd-Warshall 

1732 

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

1734 # raise NotImplementedError() 

1735 # # DFS 

1736 # # Union find 

1737 # 

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

1739 # raise NotImplementedError() 

1740 # # Ford-Fulkerson algorithm 

1741 # # Edmons-Karp algorithm 

1742 # # Dinic's algorithm 

1743 

1744 def ConvertToTree(self) -> Node: 

1745 """ 

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

1747 

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

1749 

1750 :returns: 

1751 """ 

1752 visited: Set[Vertex] = set() 

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

1754 

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

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

1757 

1758 visited.add(self) 

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

1760 

1761 while True: 

1762 try: 

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

1764 nextVertex = edge._destination 

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

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

1767 visited.add(nextVertex) 

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

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

1770 else: 

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

1772 # TODO: compute cycle: 

1773 # a) branch 1 is described in stack 

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

1775 except StopIteration: 

1776 stack.pop() 

1777 

1778 if len(stack) == 0: 

1779 return root 

1780 

1781 def __repr__(self) -> str: 

1782 """ 

1783 Returns a detailed string representation of the vertex. 

1784 

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

1786 """ 

1787 vertexID = value = "" 

1788 sep = ": " 

1789 if self._id is not None: 

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

1791 sep = "; " 

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

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

1794 

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

1796 

1797 def __str__(self) -> str: 

1798 """ 

1799 Return a string representation of the vertex. 

1800 

1801 Order of resolution: 

1802 

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

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

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

1806 

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

1808 """ 

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

1810 return str(self._value) 

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

1812 return str(self._id) 

1813 else: 

1814 return self.__repr__() 

1815 

1816 

1817@export 

1818class BaseEdge( 

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

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

1821): 

1822 """ 

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

1824 directed. 

1825 """ 

1826 _source: Vertex 

1827 _destination: Vertex 

1828 

1829 def __init__( 

1830 self, 

1831 source: Vertex, 

1832 destination: Vertex, 

1833 edgeID: Nullable[EdgeIDType] = None, 

1834 value: Nullable[EdgeValueType] = None, 

1835 weight: Nullable[EdgeWeightType] = None, 

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

1837 ) -> None: 

1838 """ 

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

1840 

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

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

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

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

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

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

1847 """ 

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

1849 

1850 self._source = source 

1851 self._destination = destination 

1852 

1853 component = source._component 

1854 if component is not destination._component: 

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

1856 oldComponent = destination._component 

1857 for vertex in oldComponent._vertices: 

1858 vertex._component = component 

1859 component._vertices.add(vertex) 

1860 component._graph._components.remove(oldComponent) 

1861 del oldComponent 

1862 

1863 @readonly 

1864 def Source(self) -> Vertex: 

1865 """ 

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

1867 

1868 :returns: The source of an edge. 

1869 """ 

1870 return self._source 

1871 

1872 @readonly 

1873 def Destination(self) -> Vertex: 

1874 """ 

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

1876 

1877 :returns: The destination of an edge. 

1878 """ 

1879 return self._destination 

1880 

1881 def Reverse(self) -> None: 

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

1883 swap = self._source 

1884 self._source = self._destination 

1885 self._destination = swap 

1886 

1887 

1888@export 

1889class Edge( 

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

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

1892): 

1893 """ 

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

1895 directed. 

1896 """ 

1897 

1898 def __init__( 

1899 self, 

1900 source: Vertex, 

1901 destination: Vertex, 

1902 edgeID: Nullable[EdgeIDType] = None, 

1903 value: Nullable[EdgeValueType] = None, 

1904 weight: Nullable[EdgeWeightType] = None, 

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

1906 ) -> None: 

1907 """ 

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

1909 

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

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

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

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

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

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

1916 """ 

1917 if not isinstance(source, Vertex): 

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

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

1920 raise ex 

1921 if not isinstance(destination, Vertex): 

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

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

1924 raise ex 

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

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

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

1928 raise ex 

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

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

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

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

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

1934 raise ex 

1935 if source._graph is not destination._graph: 

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

1937 

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

1939 

1940 def Delete(self) -> None: 

1941 # Remove from Source and Destination 

1942 self._source._outboundEdges.remove(self) 

1943 self._destination._inboundEdges.remove(self) 

1944 

1945 # Remove from Graph and Subgraph 

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

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

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

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

1950 else: 

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

1952 if self._source._subgraph is not None: 

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

1954 

1955 self._Delete() 

1956 

1957 def _Delete(self) -> None: 

1958 super().Delete() 

1959 

1960 def Reverse(self) -> None: 

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

1962 self._source._outboundEdges.remove(self) 

1963 self._source._inboundEdges.append(self) 

1964 self._destination._inboundEdges.remove(self) 

1965 self._destination._outboundEdges.append(self) 

1966 

1967 super().Reverse() 

1968 

1969 

1970@export 

1971class Link( 

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

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

1974): 

1975 """ 

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

1977 directed. 

1978 """ 

1979 

1980 def __init__( 

1981 self, 

1982 source: Vertex, 

1983 destination: Vertex, 

1984 linkID: LinkIDType = None, 

1985 value: LinkValueType = None, 

1986 weight: Nullable[LinkWeightType] = None, 

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

1988 ) -> None: 

1989 """ 

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

1991 

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

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

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

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

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

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

1998 """ 

1999 if not isinstance(source, Vertex): 

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

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

2002 raise ex 

2003 if not isinstance(destination, Vertex): 

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

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

2006 raise ex 

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

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

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

2010 raise ex 

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

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

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

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

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

2016 raise ex 

2017 if source._graph is not destination._graph: 

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

2019 

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

2021 

2022 def Delete(self) -> None: 

2023 self._source._outboundEdges.remove(self) 

2024 self._destination._inboundEdges.remove(self) 

2025 

2026 if self._id is None: 

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

2028 else: 

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

2030 

2031 self._Delete() 

2032 assert getrefcount(self) == 1 

2033 

2034 def _Delete(self) -> None: 

2035 super().Delete() 

2036 

2037 def Reverse(self) -> None: 

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

2039 self._source._outboundEdges.remove(self) 

2040 self._source._inboundEdges.append(self) 

2041 self._destination._inboundEdges.remove(self) 

2042 self._destination._outboundEdges.append(self) 

2043 

2044 super().Reverse() 

2045 

2046 

2047@export 

2048class BaseGraph( 

2049 BaseWithName[GraphDictKeyType, GraphDictValueType], 

2050 Generic[ 

2051 GraphDictKeyType, GraphDictValueType, 

2052 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType, 

2053 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType, 

2054 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType 

2055 ] 

2056): 

2057 """ 

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

2059 

2060 """ 

2061 

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

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

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

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

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

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

2068 

2069 def __init__( 

2070 self, 

2071 name: Nullable[str] = None, 

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

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

2074 ): 

2075 """ 

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

2077 

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

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

2080 """ 

2081 super().__init__(name, keyValuePairs) 

2082 

2083 self._verticesWithoutID = [] 

2084 self._verticesWithID = {} 

2085 self._edgesWithoutID = [] 

2086 self._edgesWithID = {} 

2087 self._linksWithoutID = [] 

2088 self._linksWithID = {} 

2089 

2090 def __del__(self): 

2091 """ 

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

2093 

2094 """ 

2095 try: 

2096 del self._verticesWithoutID 

2097 del self._verticesWithID 

2098 del self._edgesWithoutID 

2099 del self._edgesWithID 

2100 del self._linksWithoutID 

2101 del self._linksWithID 

2102 except AttributeError: 

2103 pass 

2104 

2105 super().__del__() 

2106 

2107 @readonly 

2108 def VertexCount(self) -> int: 

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

2110 

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

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

2113 

2114 @readonly 

2115 def EdgeCount(self) -> int: 

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

2117 

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

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

2120 

2121 @readonly 

2122 def LinkCount(self) -> int: 

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

2124 

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

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

2127 

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

2129 """ 

2130 Iterate all or selected vertices of a graph. 

2131 

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

2133 

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

2135 :returns: A generator to iterate all vertices. 

2136 """ 

2137 if predicate is None: 

2138 yield from self._verticesWithoutID 

2139 yield from self._verticesWithID.values() 

2140 

2141 else: 

2142 for vertex in self._verticesWithoutID: 

2143 if predicate(vertex): 

2144 yield vertex 

2145 

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

2147 if predicate(vertex): 

2148 yield vertex 

2149 

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

2151 """ 

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

2153 

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

2155 

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

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

2158 

2159 .. seealso:: 

2160 

2161 :meth:`IterateLeafs` |br| 

2162 |rarr| Iterate leafs of a graph. 

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

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

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

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

2167 """ 

2168 if predicate is None: 

2169 for vertex in self._verticesWithoutID: 

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

2171 yield vertex 

2172 

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

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

2175 yield vertex 

2176 else: 

2177 for vertex in self._verticesWithoutID: 

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

2179 yield vertex 

2180 

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

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

2183 yield vertex 

2184 

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

2186 """ 

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

2188 

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

2190 

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

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

2193 

2194 .. seealso:: 

2195 

2196 :meth:`IterateRoots` |br| 

2197 |rarr| Iterate roots of a graph. 

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

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

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

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

2202 """ 

2203 if predicate is None: 

2204 for vertex in self._verticesWithoutID: 

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

2206 yield vertex 

2207 

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

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

2210 yield vertex 

2211 else: 

2212 for vertex in self._verticesWithoutID: 

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

2214 yield vertex 

2215 

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

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

2218 yield vertex 

2219 

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

2221 # raise NotImplementedError() 

2222 # 

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

2224 # raise NotImplementedError() 

2225 

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

2227 """ 

2228 Iterate all or selected vertices in topological order. 

2229 

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

2231 

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

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

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

2235 """ 

2236 outboundEdgeCounts = {} 

2237 leafVertices = [] 

2238 

2239 for vertex in self._verticesWithoutID: 

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

2241 leafVertices.append(vertex) 

2242 else: 

2243 outboundEdgeCounts[vertex] = count 

2244 

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

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

2247 leafVertices.append(vertex) 

2248 else: 

2249 outboundEdgeCounts[vertex] = count 

2250 

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

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

2253 

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

2255 

2256 def removeVertex(vertex: Vertex): 

2257 nonlocal overallCount 

2258 overallCount -= 1 

2259 for inboundEdge in vertex._inboundEdges: 

2260 sourceVertex = inboundEdge.Source 

2261 count = outboundEdgeCounts[sourceVertex] - 1 

2262 outboundEdgeCounts[sourceVertex] = count 

2263 if count == 0: 

2264 leafVertices.append(sourceVertex) 

2265 

2266 if predicate is None: 

2267 for vertex in leafVertices: 

2268 yield vertex 

2269 

2270 removeVertex(vertex) 

2271 else: 

2272 for vertex in leafVertices: 

2273 if predicate(vertex): 

2274 yield vertex 

2275 

2276 removeVertex(vertex) 

2277 

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

2279 return 

2280 elif overallCount > 0: 

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

2282 

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

2284 

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

2286 """ 

2287 Iterate all or selected edges of a graph. 

2288 

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

2290 

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

2292 :returns: A generator to iterate all edges. 

2293 """ 

2294 if predicate is None: 

2295 yield from self._edgesWithoutID 

2296 yield from self._edgesWithID.values() 

2297 

2298 else: 

2299 for edge in self._edgesWithoutID: 

2300 if predicate(edge): 

2301 yield edge 

2302 

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

2304 if predicate(edge): 

2305 yield edge 

2306 

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

2308 """ 

2309 Iterate all or selected links of a graph. 

2310 

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

2312 

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

2314 :returns: A generator to iterate all links. 

2315 """ 

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

2317 yield from self._linksWithoutID 

2318 yield from self._linksWithID.values() 

2319 

2320 else: 

2321 for link in self._linksWithoutID: 

2322 if predicate(link): 

2323 yield link 

2324 

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

2326 if predicate(link): 

2327 yield link 

2328 

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

2330 """ 

2331 Reverse all or selected edges of a graph. 

2332 

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

2334 

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

2336 """ 

2337 if predicate is None: 

2338 for edge in self._edgesWithoutID: 

2339 swap = edge._source 

2340 edge._source = edge._destination 

2341 edge._destination = swap 

2342 

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

2344 swap = edge._source 

2345 edge._source = edge._destination 

2346 edge._destination = swap 

2347 

2348 for vertex in self._verticesWithoutID: 

2349 swap = vertex._inboundEdges 

2350 vertex._inboundEdges = vertex._outboundEdges 

2351 vertex._outboundEdges = swap 

2352 

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

2354 swap = vertex._inboundEdges 

2355 vertex._inboundEdges = vertex._outboundEdges 

2356 vertex._outboundEdges = swap 

2357 else: 

2358 for edge in self._edgesWithoutID: 

2359 if predicate(edge): 

2360 edge.Reverse() 

2361 

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

2363 if predicate(edge): 

2364 edge.Reverse() 

2365 

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

2367 """ 

2368 Reverse all or selected links of a graph. 

2369 

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

2371 

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

2373 """ 

2374 if predicate is None: 

2375 for link in self._linksWithoutID: 

2376 swap = link._source 

2377 link._source = link._destination 

2378 link._destination = swap 

2379 

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

2381 swap = link._source 

2382 link._source = link._destination 

2383 link._destination = swap 

2384 

2385 for vertex in self._verticesWithoutID: 

2386 swap = vertex._inboundLinks 

2387 vertex._inboundLinks = vertex._outboundLinks 

2388 vertex._outboundLinks = swap 

2389 

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

2391 swap = vertex._inboundLinks 

2392 vertex._inboundLinks = vertex._outboundLinks 

2393 vertex._outboundLinks = swap 

2394 else: 

2395 for link in self._linksWithoutID: 

2396 if predicate(link): 

2397 link.Reverse() 

2398 

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

2400 if predicate(link): 

2401 link.Reverse() 

2402 

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

2404 """ 

2405 Remove all or selected edges of a graph. 

2406 

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

2408 

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

2410 """ 

2411 if predicate is None: 

2412 for edge in self._edgesWithoutID: 

2413 edge._Delete() 

2414 

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

2416 edge._Delete() 

2417 

2418 self._edgesWithoutID = [] 

2419 self._edgesWithID = {} 

2420 

2421 for vertex in self._verticesWithoutID: 

2422 vertex._inboundEdges = [] 

2423 vertex._outboundEdges = [] 

2424 

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

2426 vertex._inboundEdges = [] 

2427 vertex._outboundEdges = [] 

2428 

2429 else: 

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

2431 for edge in delEdges: 

2432 del self._edgesWithID[edge._id] 

2433 

2434 edge._source._outboundEdges.remove(edge) 

2435 edge._destination._inboundEdges.remove(edge) 

2436 edge._Delete() 

2437 

2438 for edge in self._edgesWithoutID: 

2439 if predicate(edge): 

2440 self._edgesWithoutID.remove(edge) 

2441 

2442 edge._source._outboundEdges.remove(edge) 

2443 edge._destination._inboundEdges.remove(edge) 

2444 edge._Delete() 

2445 

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

2447 """ 

2448 Remove all or selected links of a graph. 

2449 

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

2451 

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

2453 """ 

2454 if predicate is None: 

2455 for link in self._linksWithoutID: 

2456 link._Delete() 

2457 

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

2459 link._Delete() 

2460 

2461 self._linksWithoutID = [] 

2462 self._linksWithID = {} 

2463 

2464 for vertex in self._verticesWithoutID: 

2465 vertex._inboundLinks = [] 

2466 vertex._outboundLinks = [] 

2467 

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

2469 vertex._inboundLinks = [] 

2470 vertex._outboundLinks = [] 

2471 

2472 else: 

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

2474 for link in delLinks: 

2475 del self._linksWithID[link._id] 

2476 

2477 link._source._outboundLinks.remove(link) 

2478 link._destination._inboundLinks.remove(link) 

2479 link._Delete() 

2480 

2481 for link in self._linksWithoutID: 

2482 if predicate(link): 

2483 self._linksWithoutID.remove(link) 

2484 

2485 link._source._outboundLinks.remove(link) 

2486 link._destination._inboundLinks.remove(link) 

2487 link._Delete() 

2488 

2489 def HasCycle(self) -> bool: 

2490 """ 

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

2492 

2493 """ 

2494 # IsAcyclic ? 

2495 

2496 # Handle trivial case if graph is empty 

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

2498 return False 

2499 

2500 outboundEdgeCounts = {} 

2501 leafVertices = [] 

2502 

2503 for vertex in self._verticesWithoutID: 

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

2505 leafVertices.append(vertex) 

2506 else: 

2507 outboundEdgeCounts[vertex] = count 

2508 

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

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

2511 leafVertices.append(vertex) 

2512 else: 

2513 outboundEdgeCounts[vertex] = count 

2514 

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

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

2517 return True 

2518 

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

2520 

2521 for vertex in leafVertices: 

2522 overallCount -= 1 

2523 for inboundEdge in vertex._inboundEdges: 

2524 sourceVertex = inboundEdge.Source 

2525 count = outboundEdgeCounts[sourceVertex] - 1 

2526 outboundEdgeCounts[sourceVertex] = count 

2527 if count == 0: 

2528 leafVertices.append(sourceVertex) 

2529 

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

2531 if overallCount == 0: 

2532 return False 

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

2534 elif overallCount > 0: 

2535 return True 

2536 

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

2538 

2539 

2540@export 

2541class Subgraph( 

2542 BaseGraph[ 

2543 SubgraphDictKeyType, SubgraphDictValueType, 

2544 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType, 

2545 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType, 

2546 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType 

2547 ], 

2548 Generic[ 

2549 SubgraphDictKeyType, SubgraphDictValueType, 

2550 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType, 

2551 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType, 

2552 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType 

2553 ] 

2554): 

2555 """ 

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

2557 

2558 """ 

2559 

2560 _graph: 'Graph' 

2561 

2562 def __init__( 

2563 self, 

2564 graph: 'Graph', 

2565 name: Nullable[str] = None, 

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

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

2568 ) -> None: 

2569 """ 

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

2571 

2572 :param graph: The reference to the graph. 

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

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

2575 """ 

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

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

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

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

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

2581 raise ex 

2582 

2583 super().__init__(name, keyValuePairs) 

2584 

2585 graph._subgraphs.add(self) 

2586 

2587 self._graph = graph 

2588 

2589 def __del__(self): 

2590 """ 

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

2592 

2593 """ 

2594 super().__del__() 

2595 

2596 @readonly 

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

2598 """ 

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

2600 

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

2602 """ 

2603 return self._graph 

2604 

2605 def __str__(self) -> str: 

2606 """ 

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

2608 

2609 """ 

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

2611 

2612 

2613@export 

2614class View( 

2615 BaseWithVertices[ 

2616 ViewDictKeyType, ViewDictValueType, 

2617 GraphDictKeyType, GraphDictValueType, 

2618 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType, 

2619 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType, 

2620 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType 

2621 ], 

2622 Generic[ 

2623 ViewDictKeyType, ViewDictValueType, 

2624 GraphDictKeyType, GraphDictValueType, 

2625 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType, 

2626 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType, 

2627 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType 

2628 ] 

2629): 

2630 """ 

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

2632 

2633 """ 

2634 

2635 def __init__( 

2636 self, 

2637 graph: 'Graph', 

2638 name: Nullable[str] = None, 

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

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

2641 ) -> None: 

2642 """ 

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

2644 

2645 :param graph: The reference to the graph. 

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

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

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

2649 """ 

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

2651 

2652 graph._views.add(self) 

2653 

2654 def __del__(self): 

2655 """ 

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

2657 

2658 """ 

2659 super().__del__() 

2660 

2661 def __str__(self) -> str: 

2662 """ 

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

2664 

2665 """ 

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

2667 

2668 

2669@export 

2670class Component( 

2671 BaseWithVertices[ 

2672 ComponentDictKeyType, ComponentDictValueType, 

2673 GraphDictKeyType, GraphDictValueType, 

2674 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType, 

2675 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType, 

2676 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType 

2677 ], 

2678 Generic[ 

2679 ComponentDictKeyType, ComponentDictValueType, 

2680 GraphDictKeyType, GraphDictValueType, 

2681 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType, 

2682 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType, 

2683 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType 

2684 ] 

2685): 

2686 """ 

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

2688 

2689 """ 

2690 

2691 def __init__( 

2692 self, 

2693 graph: 'Graph', 

2694 name: Nullable[str] = None, 

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

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

2697 ) -> None: 

2698 """ 

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

2700 

2701 :param graph: The reference to the graph. 

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

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

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

2705 """ 

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

2707 

2708 graph._components.add(self) 

2709 

2710 def __del__(self): 

2711 """ 

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

2713 

2714 """ 

2715 super().__del__() 

2716 

2717 def __str__(self) -> str: 

2718 """ 

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

2720 

2721 """ 

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

2723 

2724 

2725@export 

2726class Graph( 

2727 BaseGraph[ 

2728 GraphDictKeyType, GraphDictValueType, 

2729 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType, 

2730 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType, 

2731 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType 

2732 ], 

2733 Generic[ 

2734 GraphDictKeyType, GraphDictValueType, 

2735 ComponentDictKeyType, ComponentDictValueType, 

2736 SubgraphDictKeyType, SubgraphDictValueType, 

2737 ViewDictKeyType, ViewDictValueType, 

2738 VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType, 

2739 EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType, 

2740 LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType 

2741 ] 

2742): 

2743 """ 

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

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

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

2747 """ 

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

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

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

2751 

2752 def __init__( 

2753 self, 

2754 name: Nullable[str] = None, 

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

2756 ) -> None: 

2757 """ 

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

2759 

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

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

2762 """ 

2763 super().__init__(name, keyValuePairs) 

2764 

2765 self._subgraphs = set() 

2766 self._views = set() 

2767 self._components = set() 

2768 

2769 def __del__(self): 

2770 """ 

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

2772 

2773 """ 

2774 try: 

2775 del self._subgraphs 

2776 del self._views 

2777 del self._components 

2778 except AttributeError: 

2779 pass 

2780 

2781 super().__del__() 

2782 

2783 @readonly 

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

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

2786 

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

2788 return self._subgraphs 

2789 

2790 @readonly 

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

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

2793 

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

2795 return self._views 

2796 

2797 @readonly 

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

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

2800 

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

2802 return self._components 

2803 

2804 @readonly 

2805 def SubgraphCount(self) -> int: 

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

2807 

2808 :returns: The number of subgraphs in this graph.""" 

2809 return len(self._subgraphs) 

2810 

2811 @readonly 

2812 def ViewCount(self) -> int: 

2813 """Read-only property to access the number of views in this graph. 

2814 

2815 :returns: The number of views in this graph.""" 

2816 return len(self._views) 

2817 

2818 @readonly 

2819 def ComponentCount(self) -> int: 

2820 """Read-only property to access the number of components in this graph. 

2821 

2822 :returns: The number of components in this graph.""" 

2823 return len(self._components) 

2824 

2825 def __iter__(self) -> typing_Iterator[Vertex[GraphDictKeyType, GraphDictValueType, VertexIDType, VertexWeightType, VertexValueType, VertexDictKeyType, VertexDictValueType, EdgeIDType, EdgeWeightType, EdgeValueType, EdgeDictKeyType, EdgeDictValueType, LinkIDType, LinkWeightType, LinkValueType, LinkDictKeyType, LinkDictValueType]]: 

2826 """ 

2827 .. todo:: GRAPH::Graph::iter Needs documentation. 

2828 

2829 """ 

2830 def gen(): 

2831 yield from self._verticesWithoutID 

2832 yield from self._verticesWithID 

2833 return iter(gen()) 

2834 

2835 def HasVertexByID(self, vertexID: Nullable[VertexIDType]) -> bool: 

2836 """ 

2837 .. todo:: GRAPH::Graph::HasVertexByID Needs documentation. 

2838 

2839 """ 

2840 if vertexID is None: 

2841 return len(self._verticesWithoutID) >= 1 

2842 else: 

2843 return vertexID in self._verticesWithID 

2844 

2845 def HasVertexByValue(self, value: Nullable[VertexValueType]) -> bool: 

2846 """ 

2847 .. todo:: GRAPH::Graph::HasVertexByValue Needs documentation. 

2848 

2849 """ 

2850 return any(vertex._value == value for vertex in chain(self._verticesWithoutID, self._verticesWithID.values())) 

2851 

2852 def GetVertexByID(self, vertexID: Nullable[VertexIDType]) -> Vertex: 

2853 """ 

2854 .. todo:: GRAPH::Graph::GetVertexByID Needs documentation. 

2855 

2856 """ 

2857 if vertexID is None: 

2858 if (l := len(self._verticesWithoutID)) == 1: 

2859 return self._verticesWithoutID[0] 

2860 elif l == 0: 

2861 raise KeyError(f"Found no vertex with ID `None`.") 

2862 else: 

2863 raise KeyError(f"Found multiple vertices with ID `None`.") 

2864 else: 

2865 return self._verticesWithID[vertexID] 

2866 

2867 def GetVertexByValue(self, value: Nullable[VertexValueType]) -> Vertex: 

2868 """ 

2869 .. todo:: GRAPH::Graph::GetVertexByValue Needs documentation. 

2870 

2871 """ 

2872 # FIXME: optimize: iterate only until first item is found and check for a second to produce error 

2873 vertices = [vertex for vertex in chain(self._verticesWithoutID, self._verticesWithID.values()) if vertex._value == value] 

2874 if (l := len(vertices)) == 1: 

2875 return vertices[0] 

2876 elif l == 0: 

2877 raise KeyError(f"Found no vertex with Value == `{value}`.") 

2878 else: 

2879 raise KeyError(f"Found multiple vertices with Value == `{value}`.") 

2880 

2881 def CopyGraph(self) -> 'Graph': 

2882 raise NotImplementedError() 

2883 

2884 def CopyVertices(self, predicate: Nullable[Callable[[Vertex], bool]] = None, copyGraphDict: bool = True, copyVertexDict: bool = True) -> 'Graph': 

2885 """ 

2886 Create a new graph and copy all or selected vertices of the original graph. 

2887 

2888 If parameter ``predicate`` is not None, the given filter function is used to skip vertices. 

2889 

2890 :param predicate: Filter function accepting any vertex and returning a boolean. 

2891 :param copyGraphDict: If ``True``, copy all graph attached attributes into the new graph. 

2892 :param copyVertexDict: If ``True``, copy all vertex attached attributes into the new vertices. 

2893 """ 

2894 graph = Graph(self._name) 

2895 if copyGraphDict: 

2896 graph._dict = self._dict.copy() 

2897 

2898 if predicate is None: 

2899 for vertex in self._verticesWithoutID: 

2900 v = Vertex(None, vertex._value, graph=graph) 

2901 if copyVertexDict: 

2902 v._dict = vertex._dict.copy() 

2903 

2904 for vertexID, vertex in self._verticesWithID.items(): 

2905 v = Vertex(vertexID, vertex._value, graph=graph) 

2906 if copyVertexDict: 

2907 v._dict = vertex._dict.copy() 

2908 else: 

2909 for vertex in self._verticesWithoutID: 

2910 if predicate(vertex): 

2911 v = Vertex(None, vertex._value, graph=graph) 

2912 if copyVertexDict: 2912 ↛ 2909line 2912 didn't jump to line 2909 because the condition on line 2912 was always true

2913 v._dict = vertex._dict.copy() 

2914 

2915 for vertexID, vertex in self._verticesWithID.items(): 

2916 if predicate(vertex): 

2917 v = Vertex(vertexID, vertex._value, graph=graph) 

2918 if copyVertexDict: 2918 ↛ 2919line 2918 didn't jump to line 2919 because the condition on line 2918 was never true

2919 v._dict = vertex._dict.copy() 

2920 

2921 return graph 

2922 

2923 # class Iterator(): 

2924 # visited = [False for _ in range(self.__len__())] 

2925 

2926 # def CheckForNegativeCycles(self): 

2927 # raise NotImplementedError() 

2928 # # Bellman-Ford 

2929 # # Floyd-Warshall 

2930 # 

2931 # def IsStronglyConnected(self): 

2932 # raise NotImplementedError() 

2933 # 

2934 # def GetStronglyConnectedComponents(self): 

2935 # raise NotImplementedError() 

2936 # # Tarjan's and Kosaraju's algorithm 

2937 # 

2938 # def TravelingSalesmanProblem(self): 

2939 # raise NotImplementedError() 

2940 # # Held-Karp 

2941 # # branch and bound 

2942 # 

2943 # def GetBridges(self): 

2944 # raise NotImplementedError() 

2945 # 

2946 # def GetArticulationPoints(self): 

2947 # raise NotImplementedError() 

2948 # 

2949 # def MinimumSpanningTree(self): 

2950 # raise NotImplementedError() 

2951 # # Kruskal 

2952 # # Prim's algorithm 

2953 # # Buruvka's algorithm 

2954 

2955 def __repr__(self) -> str: 

2956 """ 

2957 .. todo:: GRAPH::Graph::repr Needs documentation. 

2958 

2959 """ 

2960 statistics = f", vertices: {self.VertexCount}, edges: {self.EdgeCount}" 

2961 if self._name is None: 

2962 return f"<graph: unnamed graph{statistics}>" 

2963 else: 

2964 return f"<graph: '{self._name}'{statistics}>" 

2965 

2966 def __str__(self) -> str: 

2967 """ 

2968 .. todo:: GRAPH::Graph::str Needs documentation. 

2969 

2970 """ 

2971 if self._name is None: 

2972 return f"Graph: unnamed graph" 

2973 else: 

2974 return f"Graph: '{self._name}'"