
#-------------------------------------------------------------------------------
# Module:     optimize.tk
# Activation: Loaded during GOBLET startup
# Scope:      Optimize menu item, bindings, solver dialogs and
#             execution of solver threads
# 
# Updated: 2002/12/12 Fixed up a problem with frozen GUI while tracing
#          2002/12/25 Added configuration parameter for minimum cut method
#-------------------------------------------------------------------------------



proc MakeOptimizeMenu {} {
    global ThisGraph
    
    destroy .mbar.optimize.menu

    menu .mbar.optimize.menu
    if {[$ThisGraph is mip]} {
        # LP solver and integer programming methods
        
        .mbar.optimize.menu add command -label "Solve LP Relaxation"\
            -underline 6 -command LPRelaxation
        .mbar.optimize.menu add command -label "Solve Mixed Integer Problem"\
            -underline 6 -state disabled -command {}
    } else {
        .mbar.optimize.menu add command -label "Spanning Tree Problems..." \
            -underline 9 -command SpanningTrees
        .mbar.optimize.menu add command -label "TSP..." \
            -underline 0 -command TSP
    }

    if {[$ThisGraph is sparse]} {
        .mbar.optimize.menu add command -label "Bipartitions..." \
            -underline 0 -command Bipartitions
        .mbar.optimize.menu add command -label "Graph Partitions..." \
            -underline 0 -command GraphPartitions
        .mbar.optimize.menu add command -label "Connectivity..." \
            -underline 0 -command Connectivity
    }

    if {[$ThisGraph is undirected]} {
        .mbar.optimize.menu add separator
        .mbar.optimize.menu add command -label "Matching Problems..." \
            -underline 0 -command Matchings
    }

    if {[$ThisGraph is directed]} {
        .mbar.optimize.menu add separator
        .mbar.optimize.menu add command -label "Network Flows..." -underline 0 \
            -command NetworkFlows
        .mbar.optimize.menu add command -label "Topological Order" -underline 12 \
            -command TopSort
    }

    if {[$ThisGraph is balanced]} {
        .mbar.optimize.menu add separator
        .mbar.optimize.menu add command -label "Balanced Network Flows..." \
            -underline 2 -command BalancedNetworkFlows
    }

    .mbar.optimize.menu add separator
    .mbar.optimize.menu add command -label "Restart/Stop Solver" \
        -accelerator Ctrl+C -command StartOrStop
    .mbar.optimize.menu add separator
    .mbar.optimize.menu add command -label "Optimization Level..." \
        -accelerator Shift+Ctrl+O -command SourceOptLevel
    .mbar.optimize.menu add command -label "Method Options..." \
        -accelerator Shift+Ctrl+M -command SourceMethOpt
    .mbar.optimize.menu add command -label "Data Structures..." \
        -accelerator Shift+Ctrl+S -command SourceDataOpt
}

proc CallSolver {title command} {
    global StatusInfo

    if {$command==""} {
        set StatusInfo "specify a problem solver"
        return
    }

    if {![goblin solver idle]} {
        set StatusInfo "problem solver is active"
        return
    }

    global StartTime PrevTime TotalTime

    set StatusInfo "computation is running..."
    set PrevTime "running"
    update idletasks
    
    global goblinCommLevel
    if {$goblinCommLevel} {
        global FileName goblinExtension ThisGraph Toolbar c SingleStep \
            goblinMasterEvent Log UpdateCycle TraceLock goblinBreakLevel \
            goblinLogLevel ThisBackup

        set file [open "$FileName.tcl" w]
        puts $file "goblin alias $ThisGraph [$ThisGraph handle]"
        puts $file "set state \[catch \{$command\} result\]"
        puts $file "if \{\$state==0\} \{"
        puts $file "    goblin solver return \$result"
        puts $file "\} else \{"
        puts $file "    goblin solver throw \$result"
        puts $file "\}"
        close $file

        $Toolbar.solve configure -image running_solver
        set TraceLock 1
        set goblinBreakLevel 10000
        if {[info exists c] && [winfo exists $c] && \
                [file exists $FileName.backup$ThisBackup.gob]} {
            TraceObject $FileName.backup$ThisBackup
            set SingleStep 1
        } else {
            set SingleStep 0
        }
        set prevTraceFile $FileName.backup$ThisBackup

        set StartTime [clock seconds]
        set state [catch {goblin solver thread $FileName.tcl} result]
        while {![goblin solver idle]} {
            if {$goblinCommLevel>=2} {
                if {![goblin solver idle]} {
                    if {[info exists Log] && [winfo exists $Log]} {
                        UploadMessages
                    }

                    set retState [catch {goblin messenger filename} traceFile]
                    if {$prevTraceFile==$traceFile} {set retState 1}
                    
                    if {$goblinCommLevel>=3 && ![goblin solver idle] && \
                        $goblinLogLevel<=$goblinBreakLevel} {
                        if {[info exists c] && [winfo exists $c]} {
                            if {!$retState} {
                                TraceObject [file rootname $traceFile]
                                set prevTraceFile $traceFile
                                if {!$SingleStep} {goblin messenger unblock}
                            }
                        } else {
                            set SingleStep 0
                            goblin messenger unblock
                        }
                    }

                    if {$goblinLogLevel<=$goblinBreakLevel && \
                        $SingleStep!=0 && $retState==0} {
                        set StatusInfo "waiting at trace point"
                        while {$TraceLock!=0} {
                            vwait TraceLock
                        }
                        set TraceLock 1
                    } else {
                        set dummyTimer 0
                        after $UpdateCycle set dummyTimer 1
                        vwait dummyTimer
                    }
                }
            } else {
                vwait goblinMasterEvent
            }
        }

        set PrevTime [expr {[clock seconds]-$StartTime}]
        set TotalTime [expr $TotalTime+$PrevTime]
        set state [catch {goblin solver result} result]
        file delete $FileName.tcl
        $Toolbar.solve configure -image start_solver
    } else { #Do not use threads
        set StartTime [clock seconds]
        set state [catch {eval $command} result]
        set PrevTime [expr {[clock seconds]-$StartTime}]
        set TotalTime [expr $TotalTime+$PrevTime]
    }

    global Mode
    set Mode "display object"
    PropagateModifications

    if {$state != 0} {
        global StatusInfo
        set StatusInfo "$result"
        ViewMessenger
    } else {
        global goblinTraceLevel StatusInfo
        if {$result!=""} {
            set StatusInfo "$title - objective value: $result"
        } else {
            set StatusInfo "computation is finished"
        }
        goblin echo "Total execution time: $PrevTime seconds"
        if {[info exists Log] && [winfo exists $Log]} {ViewMessenger}
    }
}

proc LPRelaxation {} {
    global ThisGraph LastCommand
    set LastCommand "$ThisGraph solve lp"
    CallSolver "LP Relaxation" $LastCommand
}

proc SpanningTrees {} {
    global ThisGraph LastCommand GoCommand goblinRoot goblinPredecessors \
        UploadCommand WDInput InternalWindowing \
        MinTreeCommand ShortestPathCommand TreePackingCommand SteinerTreeCommand

    set goblinRoot [$ThisGraph root]

    set MinTreeCommand {
        if {$goblinRoot=="*" || [QualifiedNode $goblinRoot]} {
            $ThisGraph set root $goblinRoot
            set LastCommand "$ThisGraph mintree $goblinRoot"
            set goblinPredecessors 1
            CallSolver "Minimum Spanning $goblinRoot-Tree" $LastCommand
        }
    }
    
    set ShortestPathCommand {
        if {[QualifiedNode $goblinRoot]} {
            $ThisGraph set root $goblinRoot
            set LastCommand "$ThisGraph spath $goblinRoot"
            set goblinPredecessors 1
            CallSolver "Shortest Path $goblinRoot-Tree" $LastCommand
        }
    }
    
    set TreePackingCommand {
        if {[QualifiedNode $goblinRoot]} {
            $ThisGraph set root $goblinRoot
            set LastCommand "$ThisGraph treepacking $goblinRoot"
            set goblinNodeColours 2
            set goblinPredecessors 1
            CallSolver "$goblinRoot-Tree Packing" $LastCommand
        }
    }
    
    set SteinerTreeCommand {
        if {[QualifiedNode $goblinRoot]} {
            $ThisGraph set root $goblinRoot
            set LastCommand "$ThisGraph steiner $goblinRoot"
            set goblinPredecessors 1
            CallSolver "$goblinRoot-Steiner Tree" $LastCommand
        }
    }
    
    set GoCommand $MinTreeCommand
    set UploadCommand {}
    
    DisplayInputDialog "Spanning Trees" "SpanningTrees" "Solve" "Cancel" {
        global MinTreeCommand ShortestPathCommand TreePackingCommand \
            SteinerTreeCommand DefPadX

        frame $WDInput.options
        label $WDInput.options.text -text "Problem Characteristics:" -anchor w
        radiobutton $WDInput.options.minTree -text "Minimum Spanning Tree" \
            -variable GoCommand -value $MinTreeCommand -anchor w
        radiobutton $WDInput.options.shortestPath -text "Shortest Path Tree" \
            -variable GoCommand -value $ShortestPathCommand -anchor w
        radiobutton $WDInput.options.treePacking -text "Maximum Tree Packing" \
            -variable GoCommand -value $TreePackingCommand -anchor w
        radiobutton $WDInput.options.steinerTree -text "Minimum Steiner Tree" \
            -variable GoCommand -value $SteinerTreeCommand -anchor w
        pack $WDInput.options.text $WDInput.options.minTree \
            $WDInput.options.shortestPath $WDInput.options.treePacking \
            $WDInput.options.steinerTree -side top -fill x
        pack $WDInput.options -side top -anchor w \
            -padx $DefPadX -pady 5m
    
        label $WDInput.frame.text -text "Root Node:"
        entry $WDInput.frame.entry -textvariable goblinRoot -bg white -width 5
        pack $WDInput.frame.text -side left
        pack $WDInput.frame.entry -side left -padx 5m
        bind $WDInput.frame.entry <Return> {eval $GoCommand}
    }
    
    focus $WDInput.frame.entry
}

proc Bipartitions {} {
    global ThisGraph LastCommand GoCommand goblinNodeColours \
        UploadCommand WDInput InternalWindowing \
        StableCommand CliqueCommand CoverCommand EdgeCutCommand 

    set StableCommand {
        set LastCommand "$ThisGraph stable"
        set goblinNodeColours 2
        CallSolver "Stable Set" $LastCommand
    }
    
    set CliqueCommand {
        set LastCommand "$ThisGraph clique"
        set goblinNodeColours 2
        CallSolver "Maximum Clique" $LastCommand
    }
    
    set CoverCommand {
        set LastCommand "$ThisGraph vertexcover"
        set goblinNodeColours 2
        CallSolver "Vertex Cover" $LastCommand
    }
    
    set EdgeCutCommand {
        set LastCommand "$ThisGraph maxcut"
        set goblinNodeColours 2
        CallSolver "Maximum Edge Cut" $LastCommand
    }
    
    set GoCommand $StableCommand
    set UploadCommand {}
    
    DisplayInputDialog "Bipartitions" "Bipartitions" "Solve" "Cancel" {
        global StableCommand CliqueCommand CoverCommand EdgeCutCommand DefPadX

        label $WDInput.frame.text -text "Characteristics:" -anchor w
        radiobutton $WDInput.frame.stable -text "Maximum Stable Set" \
            -variable GoCommand -value $StableCommand -anchor w
        radiobutton $WDInput.frame.clique -text "Maximum Clique" \
            -variable GoCommand -value $CliqueCommand -anchor w
        radiobutton $WDInput.frame.cover -text "Minimum Vertex Cover" \
            -variable GoCommand -value $CoverCommand -anchor w
        radiobutton $WDInput.frame.edgecut -text "Maximum Edge Cut" \
            -variable GoCommand -value $EdgeCutCommand -anchor w
        pack $WDInput.frame.text $WDInput.frame.stable $WDInput.frame.clique \
            $WDInput.frame.cover $WDInput.frame.edgecut -side top -fill x
    }
}

proc GraphPartitions {} {
    global ThisGraph LastCommand GoCommand ThisNColours goblinNodeColours \
        UploadCommand WDInput InternalWindowing \
        NodeColourCommand CliquesCommand EdgeColourCommand

    set NodeColourCommand {
        if {$ThisNColours=="" || [QualifiedNode $ThisNColours]} {
            set LastCommand "$ThisGraph colouring $ThisNColours"
            set goblinNodeColours 2
            CallSolver "$ThisNColours-Node Colouring" $LastCommand
        }
    }
    
    set CliquesCommand {
        if {$ThisNColours=="" || [QualifiedNode $ThisNColours]} {
            set LastCommand "$ThisGraph cliques $ThisNColours"
            set goblinNodeColours 2
            CallSolver "$ThisNColours-Clique Cover" $LastCommand
        }
    }
    
    set EdgeColourCommand {
        if {$ThisNColours=="" || [QualifiedNode $ThisNColours]} {
            set LastCommand "$ThisGraph edgecolouring $ThisNColours"
            set goblinNodeColours 2
            CallSolver "$ThisNColours-Edge Colouring" $LastCommand
        }
    }
    
    set GoCommand $NodeColourCommand
    set UploadCommand {}
    
    DisplayInputDialog "Graph Partitions" "GraphPartitions" "Solve" "Cancel" {
        global NodeColourCommand CliquesCommand EdgeColourCommand DefPadX

        frame $WDInput.options
        label $WDInput.options.text -text "Set Characteristics:" -anchor w
        radiobutton $WDInput.options.ncolour -text "Stable Sets (Node Colouring)" \
            -variable GoCommand -value $NodeColourCommand -anchor w
        radiobutton $WDInput.options.clique -text "Node Disjoint Cliques" \
            -variable GoCommand -value $CliquesCommand -anchor w
        radiobutton $WDInput.options.ecolour -text "1-Matchings (Edge Colouring)" \
            -variable GoCommand -value $EdgeColourCommand -anchor w
        pack $WDInput.options.text $WDInput.options.ncolour \
            $WDInput.options.clique $WDInput.options.ecolour -side top -fill x
        pack $WDInput.options -side top -anchor w -padx $DefPadX -pady 5m
    
        frame $WDInput.options2
        label $WDInput.options2.label -text "Colouring Strategy:" -anchor w
        radiobutton $WDInput.options2.stop \
            -text "Stop when Feasible" -variable goblinMethColour \
            -value 0 -anchor w
        radiobutton $WDInput.options2.exhaustive \
            -text "Exhaustive Search" -variable goblinMethColour \
            -value 1 -anchor w
        pack $WDInput.options2.label $WDInput.options2.stop \
            $WDInput.options2.exhaustive -fill x
        pack $WDInput.options2 -side top -anchor w -padx $DefPadX -pady 5m
    
        label $WDInput.frame.text -text "Accepted Index (optional):"
        entry $WDInput.frame.entry -textvariable ThisNColours -bg white -width 5
        pack $WDInput.frame.text -side left
        pack $WDInput.frame.entry -side left -padx 5m
        bind $WDInput.frame.entry <Return> {eval $GoCommand}
    }
    
    focus $WDInput.frame.entry
}

proc Connectivity {} {
    global ThisGraph LastCommand GoCommand ThisDegree goblinNodeColours \
        UploadCommand WDInput InternalWindowing \
        ConnectCommand EdgeConnectCommand StrongCommand StrongEdgeCommand
    
    set ConnectCommand {
        if {[QualifiedNode $ThisDegree]} {
            set LastCommand "$ThisGraph connected $ThisDegree"
            set goblinNodeColours 2
            set goblinSubgraph 5
            CallSolver "$ThisDegree-Vertex Connectivity" $LastCommand
        }
    }
    
    set EdgeConnectCommand {
        if {[QualifiedNode $ThisDegree]} {
            set LastCommand "$ThisGraph econnected $ThisDegree"
            set goblinNodeColours 2
            CallSolver "$ThisDegree-Edge Connectivity" $LastCommand
        }
    }
    
    set StrongCommand {
        if {[QualifiedNode $ThisDegree]} {
            set LastCommand "$ThisGraph sconnected $ThisDegree"
            set goblinNodeColours 2
            set goblinSubgraph 5
            CallSolver "Strong $ThisDegree-Connectivity" $LastCommand
        }
    }
    
    set StrongEdgeCommand {
        if {[QualifiedNode $ThisDegree]} {
            set LastCommand "$ThisGraph seconnected $ThisDegree"
            set goblinNodeColours 2
            CallSolver "Strong $ThisDegree-Edge Connectivity" $LastCommand
        }
    }
    
    set GoCommand $ConnectCommand
    set UploadCommand {}
    
    DisplayInputDialog "Graph Connectivity" "Connectivity" "Solve" "Cancel" {
        global ConnectCommand EdgeConnectCommand StrongCommand \
            StrongEdgeCommand DefPadX ThisGraph

        frame $WDInput.options
        label $WDInput.options.text -text "Characteristics:" -anchor w

        radiobutton $WDInput.options.connect -text "Vertex Connectivity" \
            -variable GoCommand -value $ConnectCommand -anchor w
        radiobutton $WDInput.options.econnect -text "Edge Connectivity" \
            -variable GoCommand -value $EdgeConnectCommand -anchor w
        radiobutton $WDInput.options.strong -text "Strong Connectivity" \
            -variable GoCommand -value $StrongCommand -anchor w
        radiobutton $WDInput.options.estrong -text "Strong Edge Connectivity" \
            -variable GoCommand -value $StrongEdgeCommand -anchor w
        if {[$ThisGraph is undirected]} {
            pack $WDInput.options.text $WDInput.options.connect \
                $WDInput.options.econnect -side top -fill x
        } else {
            pack $WDInput.options.text $WDInput.options.connect \
                $WDInput.options.econnect $WDInput.options.strong \
                $WDInput.options.estrong -side top -fill x
        }
        pack $WDInput.options -side top -anchor w -padx $DefPadX -pady 5m
    
        frame $WDInput.method
        label $WDInput.method.label -text "Min-Cut Method:" -anchor w
        radiobutton $WDInput.method.iterate -text "Reduction to Max-Flow" \
            -variable goblinMethMinCut -value 0 -anchor w
        radiobutton $WDInput.method.fifo -text "Push/Relabel (FIFO)" \
            -variable goblinMethMinCut -value 1 -anchor w
        radiobutton $WDInput.method.highest -text "Push/Relabel (Highest Label)" \
            -variable goblinMethMinCut -value 2 -anchor w
        radiobutton $WDInput.method.identify -text "Node Identification" \
            -variable goblinMethMinCut -value 3 -anchor w
        radiobutton $WDInput.method.random -text "Random Contraction" \
            -variable goblinMethMinCut -value 3 -anchor w
        pack $WDInput.method.label $WDInput.method.iterate \
             $WDInput.method.fifo $WDInput.method.highest \
             $WDInput.method.identify -fill x
        pack $WDInput.method -side top -anchor w -padx $DefPadX -pady 5m
    
        label $WDInput.frame.text -text "Degree of Connectivity:"
        entry $WDInput.frame.entry -textvariable ThisDegree -bg white -width 5
        pack $WDInput.frame.text -side left
        pack $WDInput.frame.entry -side left -padx 5m
        bind $WDInput.frame.entry <Return> {eval $GoCommand}
    }
    
    focus $WDInput.frame.entry
}

proc Matchings {} {
    global ThisGraph LastCommand GoCommand \
        UploadCommand WDInput InternalWindowing \
        MaxMatchCommand MinCMatchCommand TJoinCommand PostmanCommand

    set MaxMatchCommand {
        set LastCommand "$ThisGraph maxmatch"
        CallSolver "Matching Solver" $LastCommand
    }
    
    set MinCMatchCommand {
        set LastCommand "$ThisGraph mincmatch"
        CallSolver "Weighted Matching Solver" $LastCommand
    }
    
    set TJoinCommand {
        set LastCommand "$ThisGraph tjoin"
        CallSolver "T-Join Solver" $LastCommand
    }
    
    set PostmanCommand {
        set LastCommand "$ThisGraph postman"
        CallSolver "Chinese Postman Solver" $LastCommand
    }
    
    set GoCommand $MaxMatchCommand
    set UploadCommand {}
    
    
    DisplayInputDialog "Matching Problems" "Matchings" "Solve" "Cancel" {
        global MaxMatchCommand MinCMatchCommand TJoinCommand PostmanCommand \
            DefPadX

        label $WDInput.frame.text -text "Subgraph Characteristics:" -anchor w
        radiobutton $WDInput.frame.maxmatch -text "Cardinality Matching" \
            -variable GoCommand -value $MaxMatchCommand -anchor w
        radiobutton $WDInput.frame.mincmatch -text "Minimum Cost Perfect Matching" \
            -variable GoCommand -value $MinCMatchCommand -anchor w
        radiobutton $WDInput.frame.tjoin -text "Minimum T-Join" \
            -variable GoCommand -value $TJoinCommand -anchor w
        radiobutton $WDInput.frame.postman -text "Minimum Eulerian Supergraph" \
            -variable GoCommand -value $PostmanCommand -anchor w
        pack $WDInput.frame.text $WDInput.frame.maxmatch $WDInput.frame.mincmatch \
            $WDInput.frame.tjoin $WDInput.frame.postman -side top -fill x
    }
}

proc TSP {} {
    global ThisGraph LastCommand goblinRoot GoCommand \
        UploadCommand WDInput InternalWindowing

    set goblinRoot [$ThisGraph root]

    set GoCommand {
        if {$goblinRoot=="*" || [QualifiedNode $goblinRoot]} {
            $ThisGraph set root $goblinRoot
            set LastCommand "$ThisGraph tsp $goblinRoot"
            set goblinPredecessors 1
            CallSolver "TSP Solver" $LastCommand
        }
    }
    set UploadCommand {}
    
    DisplayInputDialog "TSP Solver" "TSP" "Solve" "Cancel" {
        frame $WDInput.heuristics
        label $WDInput.heuristics.label -text "TSP Heuristics:" -anchor w
        radiobutton $WDInput.heuristics.random -text "Random Tour" \
            -variable goblinMethTSP -value 0 -anchor w
        radiobutton $WDInput.heuristics.insert -text "Farthest Insertion" \
            -variable goblinMethTSP -value 1 -anchor w
        radiobutton $WDInput.heuristics.tree -text "Tree Approximation" \
            -variable goblinMethTSP -value 2 -anchor w
        radiobutton $WDInput.heuristics.christofides -text "Christofides" \
            -variable goblinMethTSP -value 3 -anchor w

        global ThisGraph
        if {[$ThisGraph is undirected]} {
            pack $WDInput.heuristics.label $WDInput.heuristics.random \
                $WDInput.heuristics.insert $WDInput.heuristics.tree \
                $WDInput.heuristics.christofides -fill x
        } else {
            pack $WDInput.heuristics.label $WDInput.heuristics.random \
                $WDInput.heuristics.insert $WDInput.heuristics.tree -fill x
        }
    
        frame $WDInput.relax1
        label $WDInput.relax1.label -text "TSP Initial Bounds:" -anchor w
        radiobutton $WDInput.relax1.tree -text "1-Tree" \
            -variable goblinMethRelaxTSP1 -value 0 -anchor w
        radiobutton $WDInput.relax1.improved -text "Improved Subgradients" \
            -variable goblinMethRelaxTSP1 -value 1 -anchor w
        radiobutton $WDInput.relax1.optimal -text "Optimal Subgradients" \
            -variable goblinMethRelaxTSP1 -value 2 -anchor w
        pack $WDInput.relax1.label $WDInput.relax1.tree \
            $WDInput.relax1.improved $WDInput.relax1.optimal -fill x
    
        frame $WDInput.relax2
        label $WDInput.relax2.label -text "TSP Iterated Bounds:" -anchor w
        radiobutton $WDInput.relax2.tree -text "1-Tree" \
            -variable goblinMethRelaxTSP2 -value 0 -anchor w
        radiobutton $WDInput.relax2.improved -text "Improved Subgradients" \
            -variable goblinMethRelaxTSP2 -value 1 -anchor w
        radiobutton $WDInput.relax2.optimal -text "Optimal Subgradients" \
            -variable goblinMethRelaxTSP2 -value 2 -anchor w
        pack $WDInput.relax2.label $WDInput.relax2.tree \
            $WDInput.relax2.improved $WDInput.relax2.optimal -fill x
    
        pack $WDInput.heuristics $WDInput.relax1 $WDInput.relax2 \
            -side top -anchor w -padx $DefPadX -pady 5m

        label $WDInput.frame.text -text "Root Node (optional):"
        entry $WDInput.frame.entry -textvariable goblinRoot -bg white -width 5
        pack $WDInput.frame.text -side left -pady 1m
        pack $WDInput.frame.entry -side left -padx 5m -pady 1m
        bind $WDInput.frame.entry <Return> {eval $GoCommand}
    }
}

proc NetworkFlows {} {
    global ThisGraph LastCommand GoCommand goblinSource goblinTarget \
        UploadCommand WDInput InternalWindowing PostmanCommand \
        MaxFlowCommand MinCFlowCommand FeasibleCommand MinCCircCommand

    set goblinSource [$ThisGraph source]
    set goblinTarget [$ThisGraph target]

    set MaxFlowCommand {
        if {$goblinSource!="*" && [QualifiedNode $goblinSource] && \
            $goblinTarget!="*" && [QualifiedNode $goblinTarget]} {
            $ThisGraph set source $goblinSource
            $ThisGraph set target $goblinTarget
            set LastCommand "$ThisGraph maxflow $goblinSource $goblinTarget"
            CallSolver "Maximum ($goblinSource,$goblinTarget)-Flow" $LastCommand
        }
    }
    
    set MinCFlowCommand {
        if {$goblinSource!="*" && [QualifiedNode $goblinSource] && \
            $goblinTarget!="*" && [QualifiedNode $goblinTarget]} {
            $ThisGraph set source $goblinSource
            $ThisGraph set target $goblinTarget
            set LastCommand "$ThisGraph mincflow $goblinSource $goblinTarget"
            CallSolver "Min Cost ($goblinSource,$goblinTarget)-Flow" $LastCommand
        }
    }
    
    set FeasibleCommand {
        set LastCommand "$ThisGraph circulation"
        CallSolver "Feasible b-Flow" $LastCommand
    }
    
    set MinCCircCommand {
        set LastCommand "$ThisGraph minccirc"
        CallSolver "Minimum Cost b-Flow" $LastCommand
    }
    
    set PostmanCommand {
        set LastCommand "$ThisGraph postman"
        CallSolver "Chinese Postman Solver" $LastCommand
    }
    
    if {$goblinSource=="*" || $goblinTarget=="*"} {
        set GoCommand $MinCCircCommand
    } else {
        set GoCommand $MaxFlowCommand
    }
    set UploadCommand {}
    
    DisplayInputDialog "Network Flows" "NetworkFlows" "Solve" "Cancel" {
        global PostmanCommand MaxFlowCommand MinCFlowCommand \
            FeasibleCommand MinCCircCommand DefPadX

        frame $WDInput.options
        label $WDInput.options.text -text "Subgraph Characteristics:" -anchor w
        radiobutton $WDInput.options.maxflow -text "Maximum st-Flow" \
            -variable GoCommand -value $MaxFlowCommand -anchor w
        radiobutton $WDInput.options.mincflow -text "Minimum Cost st-Flow" \
            -variable GoCommand -value $MinCFlowCommand -anchor w
        radiobutton $WDInput.options.feasible -text "Feasible b-Flow" \
            -variable GoCommand -value $FeasibleCommand -anchor w
        radiobutton $WDInput.options.minccirc -text "Minimum Cost b-Flow" \
            -variable GoCommand -value $MinCCircCommand -anchor w
        radiobutton $WDInput.options.postman -text "Minimum Eulerian Supergraph" \
            -variable GoCommand -value $PostmanCommand -anchor w
        pack $WDInput.options.text $WDInput.options.maxflow \
            $WDInput.options.mincflow $WDInput.options.feasible \
            $WDInput.options.minccirc $WDInput.options.postman \
            -side top -fill x
        pack $WDInput.options -side top -anchor w -padx $DefPadX -pady 5m
    
        label $WDInput.frame.sourceText -text "Source Node:" -anchor w
        grid $WDInput.frame.sourceText -in $WDInput.frame -row 0 \
            -column 0 -rowspan 1 -columnspan 1 -sticky news -padx 1m -pady 2m
        entry $WDInput.frame.source -textvariable goblinSource -bg white -width 5
        grid $WDInput.frame.source -in $WDInput.frame -row 0 -column 1 \
            -rowspan 1 -columnspan 1 -sticky news -padx 1m -pady 2m
    
        label $WDInput.frame.targetText -text "Target Node:" -anchor w
        grid $WDInput.frame.targetText -in $WDInput.frame -row 1 -column 0 \
            -rowspan 1 -columnspan 1 -sticky news -padx 1m -pady 2m
        entry $WDInput.frame.target -textvariable goblinTarget -bg white -width 5
        grid $WDInput.frame.target -in $WDInput.frame -row 1 -column 1 \
            -rowspan 1 -columnspan 1 -sticky news -padx 1m -pady 1m

        grid rowconfig    $WDInput.frame 0 -weight 1 -minsize 0
        grid columnconfig $WDInput.frame 0 -weight 1 -minsize 0

        bind $WDInput.frame.source <Return> {focus $WDInput.frame.target}
        bind $WDInput.frame.target <Return> {eval $GoCommand}
    }

    focus $WDInput.frame.source
}

proc TopSort {} {
    global ThisGraph LastCommand goblinNodeColours goblinNodeLabels
    set LastCommand "$ThisGraph topsort"
    set goblinNodeColours 0
    set goblinNodeLabels 4
    CallSolver "Topological Order" $LastCommand
}

proc BalancedNetworkFlows {} {
    global ThisGraph LastCommand GoCommand goblinSource \
        UploadCommand WDInput InternalWindowing MaxFlowCommand MinCFlowCommand 

    set goblinSource [$ThisGraph source]

    set MaxFlowCommand {
        if {[QualifiedNode $goblinSource]} {
            $ThisGraph set source $goblinSource
            set LastCommand "$ThisGraph maxbalflow $goblinSource"
            CallSolver "Maximum Balanced $goblinSource-Flow" $LastCommand
        }
    }
    
    set MinCFlowCommand {
        if {[QualifiedNode $goblinSource]} {
            $ThisGraph set source $goblinSource
            set LastCommand "$ThisGraph mincbalflow $goblinSource"
            CallSolver "Min-Cost Balanced $goblinSource-Flow" $LastCommand
        }
    }
    
    set GoCommand $MaxFlowCommand
    set UploadCommand {}
    
    DisplayInputDialog "Balanced Network Flows" "BalancedNetworkFlows" "Solve" "Cancel" {
        global MaxFlowCommand MinCFlowCommand DefPadX

        frame $WDInput.options
        label $WDInput.options.text -text "Subgraph Characteristics:" -anchor w
        radiobutton $WDInput.options.maxflow -text "Maximum st-Flow" \
            -variable GoCommand -value $MaxFlowCommand -anchor w
        radiobutton $WDInput.options.mincflow -text "Minimum Cost st-Flow" \
            -variable GoCommand -value $MinCFlowCommand -anchor w
        pack $WDInput.options.text $WDInput.options.maxflow \
            $WDInput.options.mincflow -side top -fill x
        pack $WDInput.options -side top -anchor w -padx $DefPadX -pady 5m
    
        label $WDInput.frame.sourceText -text "Source Node:" -anchor w
        grid $WDInput.frame.sourceText -in $WDInput.frame -row 0 -column 0 \
            -rowspan 1 -columnspan 1 -sticky news -padx 1m -pady 2m
        entry $WDInput.frame.source -textvariable goblinSource -bg white -width 5
        grid $WDInput.frame.source -in $WDInput.frame -row 0 -column 1 \
            -rowspan 1 -columnspan 1 -sticky news -padx 1m -pady 2m
    
        grid rowconfig    $WDInput.frame 0 -weight 1 -minsize 0
        grid columnconfig $WDInput.frame 0 -weight 1 -minsize 0

        bind $WDInput.frame.source <Return> {eval $GoCommand}
    }

    focus $WDInput.frame.source
}

proc StartOrStop {} {
    global Toolbar2 LastCommand
    if {[goblin solver idle]} {
        CallSolver "Optimization" $LastCommand
    } else {
        goblin solver stop
        $Toolbar2.solve configure -image stopped_solver
    }
}

set LastCommand ""

proc SourceOptLevel {} {
    global GoblinTclPath
    source [file join $GoblinTclPath optlevel.tk]
}

proc SourceMethOpt {} {
    global GoblinTclPath
    source [file join $GoblinTclPath methopt.tk]
}

proc SourceDataOpt {} {
    global GoblinTclPath
    source [file join $GoblinTclPath dataopt.tk]
}

bind . <Control-c> {StartOrStop}
bind . <Control-M> {SourceMethOpt}
bind . <Control-O> {SourceOptLevel}
bind . <Control-S> {SourceDataOpt}
