
#-------------------------------------------------------------------------------
# Module:     menuOptimize.tk
# Activation: Loaded during GOBLET startup
# Scope:      Optimize menu item, bindings, solver dialogs and
#             execution of solver threads
#-------------------------------------------------------------------------------



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

    menu .mbar.optimize.menu -tearoff false
    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 -command MixedInteger
    } else {
        .mbar.optimize.menu add command -label "Spanning Trees..." \
            -underline 0 -command SpanningTrees

        menu .mbar.optimize.menu.routing -tearoff false
        .mbar.optimize.menu add cascade -label "Routing" \
            -underline 0 -menu .mbar.optimize.menu.routing
        .mbar.optimize.menu.routing add command -label "Eulerian Cycle" \
            -underline 0 -command EulerianCycle

        if {[$ThisGraph is directed]} {
            .mbar.optimize.menu.routing add command -label "Critical Path" \
                -underline 0 -command CriticalPath
        }

        .mbar.optimize.menu.routing add command -label "Travelling Salesman..." \
            -underline 0 -command TSP
    }

    if {![$ThisGraph is mip]} {
        menu .mbar.optimize.menu.bipartition -tearoff false
        .mbar.optimize.menu add cascade -label "Bipartitions" \
            -underline 0 -menu .mbar.optimize.menu.bipartition
        .mbar.optimize.menu.bipartition add command -label "Maximum Edge Cut..." \
            -underline 0 -command SolveMaxCut

        if {[$ThisGraph is sparse]} {
            .mbar.optimize.menu.bipartition add command -label "Maximum Stable Set" \
                -underline 0 -command SolveStableSet
            .mbar.optimize.menu.bipartition add command -label "Minimum Vertex Cover" \
                -underline 0 -command SolveVertexCover
            .mbar.optimize.menu.bipartition add command -label "Maximum Clique" \
                -underline 0 -command SolveClique

            .mbar.optimize.menu add command -label "Graph Partitions..." \
                -underline 0 -command GraphPartitions
            .mbar.optimize.menu add command -label "Connectivity..." \
                -underline 0 -command Connectivity
        }

        menu .mbar.optimize.menu.ordering -tearoff false
        .mbar.optimize.menu add cascade -label "Ordering Problems" \
            -underline 0 -menu .mbar.optimize.menu.ordering
        .mbar.optimize.menu.ordering add command -label "st-Numbering" \
            -underline 0 -command STNumbering

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

    if {[$ThisGraph is undirected]} {
        .mbar.optimize.menu add separator
        menu .mbar.optimize.menu.matching -tearoff false
        .mbar.optimize.menu add cascade -label "Matching Problems" \
            -underline 0 -menu .mbar.optimize.menu.matching
        .mbar.optimize.menu.matching add command -label "Cardinality Matching" \
            -underline 0 -command SolveMaxMatch
        .mbar.optimize.menu.matching add command -label "Weighted Matching" \
            -underline 0 -command SolveMinCMatch
        .mbar.optimize.menu.matching add command -label "Minimum T-Join" \
            -underline 0 -command SolveTJoin
        .mbar.optimize.menu.matching add command -label "Minimum Eulerian Supergraph" \
            -underline 0 -command SolvePostman
    }

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

    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 PrevCommand

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

    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]} {
                    UpdateActiveDialogs
                
                    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"
        }

        if {[info exists Log] && [winfo exists $Log]} {ViewMessenger}
    }
}

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

proc MixedInteger {} {
    global ThisGraph
    CallSolver "Mixed Integer Problem" "$ThisGraph solve mip"
}

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

    set goblinRoot [$ThisGraph root]

    set MinTreeCommand {
        if {$goblinRoot=="*" || [QualifiedNode $goblinRoot]} {
            $ThisGraph set root $goblinRoot
            set goblinPredecessors 1
            CallSolver "Minimum Spanning $goblinRoot-Tree" \
                       "$ThisGraph mintree $goblinRoot"
        }
    }

    set Min1TreeCommand {
        if {$goblinRoot!="*" && [QualifiedNode $goblinRoot]} {
            $ThisGraph set root $goblinRoot
            set goblinPredecessors 1
            CallSolver "Minimum Spanning $goblinRoot-Tree" \
                       "$ThisGraph min1tree $goblinRoot"
        }
    }
    
    set ShortestPathCommand {
        if {[QualifiedNode $goblinRoot]} {
            $ThisGraph set root $goblinRoot
            set goblinPredecessors 1
            CallSolver "Shortest Path $goblinRoot-Tree" \
                       "$ThisGraph spath $goblinRoot"
        }
    }
    
    set TreePackingCommand {
        if {[QualifiedNode $goblinRoot]} {
            $ThisGraph set root $goblinRoot
            set goblinNodeColours 2
            set goblinPredecessors 1
            CallSolver "$goblinRoot-Tree Packing" \
                       "$ThisGraph treepacking $goblinRoot"
        }
    }
    
    set SteinerTreeCommand {
        if {[QualifiedNode $goblinRoot]} {
            $ThisGraph set root $goblinRoot
            set goblinPredecessors 1
            CallSolver "$goblinRoot-Steiner Tree" \
                       "$ThisGraph steiner $goblinRoot"
        }
    }
    
    set GoCommand $MinTreeCommand
    set UploadCommand {}
    
    DisplayInputDialog "Spanning Trees" "SpanningTrees" "Solve" "Cancel" {
        global MinTreeCommand Min1TreeCommand 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.min1Tree -text "Minimum 1-Tree" \
            -variable GoCommand -value $Min1TreeCommand -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.min1Tree $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 SolveStableSet {} {
    global ThisGraph goblinNodeColours
    set goblinNodeColours 2
    CallSolver "Maximum Stable Set" "$ThisGraph stable"
}

proc SolveClique {} {
    global ThisGraph goblinNodeColours
    set goblinNodeColours 2
    CallSolver "Maximum Clique" "$ThisGraph clique"
}

proc SolveVertexCover {} {
    global ThisGraph goblinNodeColours
    set goblinNodeColours 2
    CallSolver "Minimum Vertex Cover" "$ThisGraph vertexcover"
}

proc SolveMaxCut2 {} {
    global ThisGraph goblinNodeColours
    set goblinNodeColours 2
    CallSolver "Maximum Edge Cut" "$ThisGraph maxcut"
}

proc STNumbering {} {
    global ThisGraph goblinNodeLabels
    set goblinNodeLabels 4
    CallSolver "st-Numbering" "$ThisGraph stnumbering"
}

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

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

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

    set GoCommand {
        if {$goblinSource=="*" || [QualifiedNode $goblinSource] && \
            $goblinTarget=="*" || [QualifiedNode $goblinTarget]} {
            $ThisGraph set source $goblinSource
            $ThisGraph set target $goblinTarget
            CallSolver "Maximum ($goblinSource,$goblinTarget)-Cut" \
                       "$ThisGraph maxcut $goblinSource $goblinTarget"
        }
    }

    set UploadCommand {}
    
    DisplayInputDialog "Maximum Cut" "SolveMaxCut" "Solve" "Cancel" {
        global goblinMethMaxCut GoCommand DefPadX

        frame $WDInput.options
        label $WDInput.options.text -text "Construction Method:" -anchor w
        radiobutton $WDInput.options.random -text "Random Heuristic" \
            -variable goblinMethMaxCut -value 0 -anchor w
        radiobutton $WDInput.options.tree -text "Tree Heuristic" \
            -variable goblinMethMaxCut -value 1 -anchor w
        radiobutton $WDInput.options.tjoin -text "Dual T-Join" \
            -variable goblinMethMaxCut -value 2 -anchor w
        pack $WDInput.options.text $WDInput.options.random \
            $WDInput.options.tree $WDInput.options.tjoin \
            -side top -fill x
        pack $WDInput.options -side top -anchor w -padx $DefPadX -pady 5m
    
        label $WDInput.frame.sourceText -text "Left Hand 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 "Right Hand 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 GraphPartitions {} {
    global ThisGraph GoCommand ThisNColours goblinNodeColours \
        UploadCommand WDInput \
        NodeColourCommand CliquesCommand EdgeColourCommand

    set NodeColourCommand {
        if {$ThisNColours=="" || [QualifiedNode $ThisNColours]} {
            set goblinNodeColours 2
            CallSolver "$ThisNColours-Node Colouring" \
                       "$ThisGraph colouring $ThisNColours"
        }
    }
    
    set CliquesCommand {
        if {$ThisNColours=="" || [QualifiedNode $ThisNColours]} {
            set goblinNodeColours 2
            CallSolver "$ThisNColours-Clique Cover" \
                       "$ThisGraph cliques $ThisNColours"
        }
    }
    
    set EdgeColourCommand {
        if {$ThisNColours=="" || [QualifiedNode $ThisNColours]} {
            set goblinNodeColours 2
            CallSolver "$ThisNColours-Edge Colouring" \
                       "$ThisGraph edgecolouring $ThisNColours"
        }
    }
    
    set GoCommand $NodeColourCommand
    set UploadCommand {}
    
    DisplayInputDialog "Graph Partitions" "GraphPartitions" "Solve" "Cancel" {
        global GoCoomand 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 GoCommand ThisDegree goblinNodeColours \
        UploadCommand WDInput \
        ConnectCommand EdgeConnectCommand StrongCommand StrongEdgeCommand
    
    set ConnectCommand {
        if {[QualifiedInt $ThisDegree "*" "*"]} {
            set goblinNodeColours 2
            set goblinSubgraph 5
            CallSolver "$ThisDegree-Vertex Connectivity" \
                       "$ThisGraph connected $ThisDegree"
        }
    }
    
    set EdgeConnectCommand {
        if {[QualifiedInt $ThisDegree "*" "*"]} {
            set goblinNodeColours 2
            CallSolver "$ThisDegree-Edge Connectivity" \
                       "$ThisGraph econnected $ThisDegree"
        }
    }
    
    set StrongCommand {
        if {[QualifiedInt $ThisDegree "*" "*"]} {
            set goblinNodeColours 2
            set goblinSubgraph 5
            CallSolver "Strong $ThisDegree-Connectivity" \
                       "$ThisGraph sconnected $ThisDegree"
        }
    }
    
    set StrongEdgeCommand {
        if {[QualifiedInt $ThisDegree "*" "*"]} {
            set goblinNodeColours 2
            CallSolver "Strong $ThisDegree-Edge Connectivity" \
                       "$ThisGraph seconnected $ThisDegree"
        }
    }
    
    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 SolveMaxMatch {} {
    global ThisGraph
    CallSolver "Cardinality Matching" "$ThisGraph maxmatch"
}

proc SolveMinCMatch {} {
    global ThisGraph
    CallSolver "Weighted Matching" "$ThisGraph mincmatch"
}

proc SolveTJoin {} {
    global ThisGraph
    CallSolver "Minimum T-Join" "$ThisGraph tjoin"
}

proc SolvePostman {} {
    global ThisGraph
    CallSolver "Minimum Eulerian Supergraph" "$ThisGraph postman"
}

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

    set MaxMatchCommand {
        CallSolver "Matching Solver" "$ThisGraph maxmatch"
    }
    
    set MinCMatchCommand {
        CallSolver "Weighted Matching Solver" "$ThisGraph mincmatch"
    }
    
    set TJoinCommand {
        CallSolver "T-Join Solver" "$ThisGraph tjoin"
    }
    
    set PostmanCommand {
        CallSolver "Chinese Postman Solver" "$ThisGraph postman"
    }
    
    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 EulerianCycle {} {
    global ThisGraph
    CallSolver "Euler Cycle" "$ThisGraph eulerian"
}

proc CriticalPath {} {
    global ThisGraph
    CallSolver "Critical Path" "$ThisGraph critical"
}

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

    set goblinRoot [$ThisGraph root]

    set GoCommand {
        if {$goblinRoot=="*" || [QualifiedNode $goblinRoot]} {
            $ThisGraph set root $goblinRoot
            set goblinPredecessors 1
            CallSolver "TSP Solver" "$ThisGraph tsp $goblinRoot"
        }
    }
    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 GoCommand goblinSource goblinTarget \
        UploadCommand WDInput 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
            CallSolver "Maximum ($goblinSource,$goblinTarget)-Flow" \
                       "$ThisGraph maxflow $goblinSource $goblinTarget"
        }
    }
    
    set MinCFlowCommand {
        if {$goblinSource!="*" && [QualifiedNode $goblinSource] && \
            $goblinTarget!="*" && [QualifiedNode $goblinTarget]} {
            $ThisGraph set source $goblinSource
            $ThisGraph set target $goblinTarget
            CallSolver "Min Cost ($goblinSource,$goblinTarget)-Flow" \
                       "$ThisGraph mincflow $goblinSource $goblinTarget"
        }
    }
    
    set FeasibleCommand {
        CallSolver "Feasible b-Flow" "$ThisGraph circulation"
    }
    
    set MinCCircCommand {
        CallSolver "Minimum Cost b-Flow" "$ThisGraph minccirc"
    }
    
    set PostmanCommand {
        CallSolver "Chinese Postman Solver" "$ThisGraph postman"
    }
    
    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 BalancedNetworkFlows {} {
    global ThisGraph GoCommand goblinSource \
        UploadCommand WDInput MaxFlowCommand MinCFlowCommand 

    set goblinSource [$ThisGraph source]

    set MaxFlowCommand {
        if {[QualifiedNode $goblinSource]} {
            $ThisGraph set source $goblinSource
            CallSolver "Maximum Balanced $goblinSource-Flow" \
                       "$ThisGraph maxbalflow $goblinSource"
        }
    }
    
    set MinCFlowCommand {
        if {[QualifiedNode $goblinSource]} {
            $ThisGraph set source $goblinSource
            CallSolver "Min-Cost Balanced $goblinSource-Flow" \
                       "$ThisGraph mincbalflow $goblinSource"
        }
    }
    
    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 Toolbar PrevCommand
    if {[goblin solver idle]} {
        CallSolver "Optimization" $PrevCommand
    } else {
        goblin solver stop
        $Toolbar.solve configure -image stopped_solver
    }
}

set PrevCommand ""

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

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

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

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