package require struct::graph 2
# Resolving reference dependecies for tcldb tables
#
# Create a dependency graph first,
# then walk from leaves to the root
#
proc createGraph {tableObjs} {
set g [::struct::graph ]
foreach table $tableObjs {
set tablename [$table cget -table]
set fields [$table fieldlist 0 1 1]
$g set $tablename $table
if {![$g node exists $tablename]} {
$g node insert $tablename
}
puts "Table: $tablename"
foreach {field type param} $fields {
puts "$field"
puts "$type"
puts $param
array unset finfo
set finfo(reference) ""
$g node set $tablename $field [list $type $param]
array set finfo $param
if {$finfo(reference) eq ""} {continue}
set reftable [lindex $finfo(reference) 0]
if {![$g node exists $reftable]} {
$g node insert $reftable
}
$g arc insert $tablename $reftable
}
}
return $g
}
proc filterIsolated {g n} {
if {[llength [$g arcs -out $n]]} {
return 0
} else {
return 1
}
}
proc findOrder {graph} {
set g [::struct::graph tempGraph = $graph]
set order [list]
set old [llength [$g nodes]]
while {[llength [$g nodes]]} {
set isolated [$g nodes -filter [namespace current]::filterIsolated]
if {[llength $isolated]} {
foreach node $isolated {
lappend order [list $node [$g set $node]]
$g node delete $node
}
} else {
break
}
}
if {[llength [$g nodes]]} {
return -code error "Could not resolve reference conflicts, objects left [$g nodes]"
}
$g destroy
return $order
}To use it, put all your tcldb::table objects into a list, then call:set g [createGraph $tablelist] puts [findOrder $g]This returns the creation order for your table as a list of lists, each sublist is a tablename tableobject pair.
escargo 16 Dec 2005 - In terms of dependencies, would determining the order via a topological sort work as well? Can the dependency graph be relied upon to have no cycles?
schlenk 16 Dec 2005 - I think a topological sort would work as well. If the dependency graph for this use case (sql table relations) would have cycles, this would be a clear indication that some database normalization could be a good idea.
