|
2005-10-01
| ||
| 02:31 | • Ticket [724730ffff] Behaviour of struct::graph walk status still Open with 1 other change artifact: 704fa536f8 user: andreas_kupries | |
|
2003-08-07
| ||
| 03:57 | • Ticket [724730ffff]: 1 change artifact: 39ec1e0d3c user: andreas_kupries | |
|
2003-04-20
| ||
| 20:15 | • New ticket [724730ffff]. artifact: d714c9be5d user: nobody | |
| Ticket UUID: | 724730 | |||
| Title: | Behaviour of struct::graph walk | |||
| Type: | RFE | Version: | None | |
| Submitter: | nobody | Created on: | 2003-04-20 20:15:49 | |
| Subsystem: | struct :: graph | Assigned To: | andreas_kupries | |
| Priority: | 7 High | Severity: | ||
| Status: | Open | Last Modified: | 2005-10-01 02:31:34 | |
| Resolution: | Closed By: | |||
| Closed on: | ||||
| Description: |
The current implementation (tcllib1.3) of ::struct::graph: :_walk with options -order both -type dfs create a forest of disjunct predecessor subgraph trees [1] . [2] Says that if G is a graph G=(V,E) then we can do one of three possibilities: 1. No restrictions (walk) 2. Each edge E of G traversed at most once. (trail) 3. Each vertex V visited at most once (path) In tcllib a vertex is a node and an edge is an arc. I think the current implementation of walk is actually a path as each node is visited only once. In order to implement a walk as defined in [2] an extra line 1834 array unset visited $node could be inserted. See http://mini.net/tcl/8787 for more info. Could the walk proc be extended to cover all three cases? [1] Cormen, Leiserson, Rivest: Introduction to Algorithms, p477 [2] Kreystig, Advanced Engineering Mathematics, Sixth Edition, p1139 | |||
