Tcl Library Source Code

View Ticket
Login
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