# -*- tcl -*-
# Graph ops tests - Node distances, Dijkstra's algorithm
# Copyright (c) 2008 Andreas Kupries <andreas_kupries@users.sourceforge.net>
# All rights reserved.
# RCS: @(#) $Id: dijkstra.test,v 1.3 2009/09/15 19:24:12 andreas_kupries Exp $

# Syntax: struct::graph::op::dijkstra G N ?-arcmode undirected|directed? ?-outputformat tree/distances?

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

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

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

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

test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-dijkstra-2.0 {dijkstra, bad node} {
    SETUP
    catch {struct::graph::op::dijkstra mygraph foo} result
    mygraph destroy
    set result
} {node "foo" does not exist in graph "mygraph"}

test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-dijkstra-2.1 {dijkstra, bad option} {
    SETUPx
    catch {struct::graph::op::dijkstra mygraph %0 -foo bar} result
    mygraph destroy
    set result
} {Bad option "-foo", expected one of "-arcmode" or "-outputformat"}

test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-dijkstra-2.2 {dijkstra, bad option value} {
    SETUPx
    catch {struct::graph::op::dijkstra mygraph %0 -arcmode bar} result
    mygraph destroy
    set result
} {Bad value for -arcmode, expected one of "directed" or "undirected"}

test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-dijkstra-2.3 {dijkstra, bad option value} {
    SETUPx
    catch {struct::graph::op::dijkstra mygraph %0 -outputformat bar} result
    mygraph destroy
    set result
} {Bad value for -outputformat, expected one of "distances" or "tree"}

test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-dijkstra-2.4 {dijkstra, bad option value} {
    SETUP_A2
    catch {struct::graph::op::dijkstra mygraph 'node0'} result
    mygraph destroy
    set result
} {Operation invalid for graph with unweighted arcs.}

# -------------------------------------------------------------------------
# Ok arguments.

set n 0
foreach {setup start distances tree undistances untree} {
    SETUP_A 'node0'
    {'node0' 0 'node1' 2 'node2' 3 'node3' 1 'node4' 3 'node5' 6 'node6' 5}
    {'node0' 'node0' 'node1' 'node0' 'node2' {'node3' 'node0'} 'node3' 'node0' 'node4' {'node3' 'node0'} 'node5' {'node6' 'node3' 'node0'} 'node6' {'node3' 'node0'}}
    {'node0' 0 'node1' 2 'node2' 3 'node3' 1 'node4' 3 'node5' 6 'node6' 5}
    {'node0' 'node0' 'node1' 'node0' 'node2' {'node3' 'node0'} 'node3' 'node0' 'node4' {'node3' 'node0'} 'node5' {'node6' 'node3' 'node0'} 'node6' {'node3' 'node0'}}
    SETUP_A 'node6'
    {'node0' Inf 'node1' Inf 'node2' Inf 'node3' Inf 'node4' Inf 'node5' 1 'node6' 0}
    {'node5' 'node6' 'node6' 'node6'}
    {'node0' 5 'node1' 7 'node2' 6 'node3' 4 'node4' 6 'node5' 1 'node6' 0}
    {'node0' {'node3' 'node6'} 'node1' {'node3' 'node6'} 'node2' {'node5' 'node6'} 'node3' 'node6' 'node4' 'node6' 'node5' 'node6' 'node6' 'node6'}
} {
    test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-dijkstra-3.$n "dijkstra, $setup/$start, distances/directed" {
	$setup
	set result [dictsort [struct::graph::op::dijkstra mygraph $start -arcmode directed -outputformat distances]]
	mygraph destroy
	set result
    } $distances

    test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-dijkstra-4.$n "dijkstra, $setup/$start, tree/directed" {
	$setup
	set result [dictsort [struct::graph::op::dijkstra mygraph $start -arcmode directed -outputformat tree]]
	mygraph destroy
	set result
    } $tree

    test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-dijkstra-5.$n "dijkstra, $setup/$start, distances/undirected" {
	$setup
	set result [dictsort [struct::graph::op::dijkstra mygraph $start -arcmode undirected -outputformat distances]]
	mygraph destroy
	set result
    } $undistances

    test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-dijkstra-6.$n "dijkstra, $setup/$start, tree/undirected" {
	$setup
	set result [dictsort [struct::graph::op::dijkstra mygraph $start -arcmode undirected -outputformat tree]]
	mygraph destroy
	set result
    } $untree

    incr n
}

# ---------------------------------------------------