# -*- tcl -*-
#Busacker-Gowen algorithm - computing maximum flow in a flow network
#
#


# ------------------------------------------------------------------------------------
# Tests concerning returning right values by algorithm

# ------------------------------------------------------------------------------------
#Test 1.0 
test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-BusackerGowen-1.0 { graph simulation } {
    SETUP_BUSACKERGOWEN_1
    set result [dictsort [struct::graph::op::BusackerGowen mygraph 25 s t]]
    mygraph destroy
    set result
} {{a b} 8 {a c} 10 {b t} 8 {c t} 17 {s a} 18 {s c} 7}

#Test 1.1 - case considering when desired flow is equal to max flow
test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-BusackerGowen-1.1 { graph simulation } {
    SETUP_BUSACKERGOWEN_1
    set result [dictsort [struct::graph::op::BusackerGowen mygraph 31 s t]]
    mygraph destroy
    set result
} {{a b} 14 {b t} 14 {c a} 18 {c t} 17 {s a} 18 {s c} 13}

#Test 1.2 - case considering when desired flow exceeds max flow - algorithm should end when
#there is no more paths between source and sink nodes.
test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-BusackerGowen-1.2 { graph simulation } {
    SETUP_BUSACKERGOWEN_1
    set result [dictsort [struct::graph::op::BusackerGowen mygraph 40 s t]]
    mygraph destroy
    set result
} {{a b} 14 {b t} 14 {c a} 18 {c t} 17 {s a} 18 {s c} 13}

#Test 1.3 - case when the are no paths between source and sink from the beginning
test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-BusackerGowen-1.3 { graph simulation } {
    SETUP_SOURCESINKNOPATHS
    set result [struct::graph::op::BusackerGowen mygraph 1 s t]
    mygraph destroy
    set result
} {}

#Test 1.4 - test for subprocedure that creates Augmenting Network
test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-BusackerGowen-1.4 { createAugmentingNetwork, graph simulation } -setup {
    SETUP_AUGMENTINGNETWORK_1 f path
    set throughputs {}
    set costs {}
} -body {
    set result [struct::graph::op::createAugmentingNetwork mygraph $f $path]
    set throughputs_arcs [$result arcs -key throughput]
    set costs_arcs [$result arcs -key cost]
    foreach t $throughputs_arcs c $costs_arcs {
	dict set throughputs $t [$result arc set $t throughput]
	dict set costs $c [$result arc set $c cost]
    }
    list [dictsort $throughputs] | [dictsort $costs]
} -cleanup {
    unset costs throughputs f costs_arcs throughputs_arcs path t
    mygraph destroy
    $result destroy
} -result {{{a b} 20 {a c} 0 {a s} 15 {b t} 14 {c a} 15 {c b} 12 {c t} 2 {s a} 3 {s c} 20 {t c} 15} | {{a b} 5 {a c} Inf {a s} -3 {b t} 5 {c a} -4 {c b} 8 {c t} 3 {s a} 3 {s c} 8 {t c} -3}}

#Test 1.5 - test for subprocedure that creates Augmenting Network
test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-BusackerGowen-1.5 { createAugmentingNetwork, graph simulation } -setup {
    SETUP_AUGMENTINGNETWORK_2 f path
    set throughputs {}
    set costs {}
} -body {
    set result [struct::graph::op::createAugmentingNetwork mygraph $f $path]
    set throughputs_arcs [$result arcs -key throughput]
    set costs_arcs [$result arcs -key cost]
    foreach t $throughputs_arcs c $costs_arcs {
	dict set throughputs $t [$result arc set $t throughput]
	dict set costs $c [$result arc set $c cost]
    }
    list [dictsort $throughputs] | [dictsort $costs]
} -cleanup {
    unset costs throughputs f costs_arcs throughputs_arcs path t
    mygraph destroy
    $result destroy
} -result {{{a b} 20 {a c} 0 {a s} 15 {b t} 14 {c a} 15 {c b} 12 {c s} 2 {c t} 0 {s a} 3 {s c} 18 {t c} 17} | {{a b} 5 {a c} Inf {a s} -3 {b t} 5 {c a} -4 {c b} 8 {c s} -8 {c t} Inf {s a} 3 {s c} 8 {t c} -3}}

#Test 1.6 - test for subprocedure that creates Augmenting Network
test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-BusackerGowen-1.6 { createAugmentingNetwork, graph simulation } -setup {
    SETUP_AUGMENTINGNETWORK_3 f path
    set throughputs {}
    set costs {}
} -body {
    set result [struct::graph::op::createAugmentingNetwork mygraph $f $path]
    set throughputs_arcs [$result arcs -key throughput]
    set costs_arcs [$result arcs -key cost]
    foreach t $throughputs_arcs c $costs_arcs {
	dict set throughputs $t [$result arc set $t throughput]
	dict set costs $c [$result arc set $c cost]
    }
    list [dictsort $throughputs] | [dictsort $costs]
} -cleanup {
    unset costs throughputs f costs_arcs throughputs_arcs path t
    mygraph destroy
    $result destroy
} -result {{{a b} 17 {a c} 0 {a s} 18 {b a} 3 {b t} 11 {c a} 15 {c b} 12 {c s} 2 {c t} 0 {s a} 0 {s c} 18 {t b} 3 {t c} 17} | {{a b} 5 {a c} Inf {a s} -3 {b a} -5 {b t} 5 {c a} -4 {c b} 8 {c s} -8 {c t} Inf {s a} Inf {s c} 8 {t b} -5 {t c} -3}}

# -------------------------------------------------------------------------
# Wrong # args: Missing, Too many

test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-BusackerGowen-2.0 { BusackerGowen, wrong args, missing } {
    catch {struct::graph::op::BusackerGowen} msg
    set msg
} [tcltest::wrongNumArgs struct::graph::op::BusackerGowen {G desiredFlow s t} 0]

test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-BusackerGowen-2.1 { BusackerGowen, wrong args, missing } {
    catch {struct::graph::op::BusackerGowen G} msg
    set msg
} [tcltest::wrongNumArgs struct::graph::op::BusackerGowen {G desiredFlow s t} 1]

test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-BusackerGowen-2.2 { BusackerGowen, wrong args, missing } {
    catch {struct::graph::op::BusackerGowen G desiredFlow} msg
    set msg
} [tcltest::wrongNumArgs struct::graph::op::BusackerGowen {G desiredFlow s t} 2]

test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-BusackerGowen-2.3 { BusackerGowen, wrong args, too many} {
    catch {struct::graph::op::BusackerGowen G desiredFlow c s t z} msg
    set msg
} [tcltest::tooManyArgs struct::graph::op::BusackerGowen {G desiredFlow s t}]

test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-BusackerGowen-2.4 { BusackerGowen, wrong args, missing } {
    catch {struct::graph::op::BusackerGowen G desiredFlow s} msg
    set msg
} [tcltest::wrongNumArgs struct::graph::op::BusackerGowen {G desiredFlow s t} 3]

# -------------------------------------------------------------------------
# Logical arguments checks and failures

#Test 3.0 - case when sink and source nodes given at input aren't nodes of input graph 
test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-BusackerGowen-3.0 {BusackerGowen, wrong sink or source } {
    SETUP_BUSACKERGOWEN_1
    catch {struct::graph::op::BusackerGowen mygraph 25 x y } result
    mygraph destroy
    set result
} [LackOfSinkOrSource x y]

#Test 3.1 - case when input network has lacking attributes
test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-BusackerGowen-3.1 {BusackerGowen, missing attributes } {
    SETUP_BUSACKERGOWEN_2
    catch {struct::graph::op::BusackerGowen mygraph 25 s t } result
    mygraph destroy
    set result
} [WrongAttributes throughput cost]

#Test 3.2 - case when wrong input value of desired flow is given at input
test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-BusackerGowen-3.2 {BusackerGowen, wrong input, desired flow } {
    SETUP_BUSACKERGOWEN_1
    catch {struct::graph::op::BusackerGowen mygraph 0 s t } result
    mygraph destroy
    set result
} [WrongValueAtInput desiredFlow]