# -*- tcl -*-
# Graph tests - nodes
# Copyright (c) 2006 Andreas Kupries <andreas_kupries@users.sourceforge.net>
# All rights reserved.
# RCS: @(#) $Id: nodes.test,v 1.3 2008/03/23 19:08:26 andreas_kupries Exp $

# Syntax: graph nodes
# (1)     graph nodes -key KEY
#         graph nodes -key KEY -value VALUE
# (2)     graph nodes -filter CMDPREFIX
# (3)     graph nodes -in       NODE...
#         graph nodes -out      NODE...
#         graph nodes -adj      NODE...
#         graph nodes -inner    NODE...
#         graph nodes -embedded NODE...

# We can use one in each group (1,2,3)

# Note: node names may have a leading dash ('-').

# Heuristics: Unknown options after (3) are considered node names
# until we reach a valid option.

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

# Cannot have missing arguments (zero is fine),
# except when switches are in use. That however
# is tested with the switches. Ditto for too many
# arguments.

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

test graph-${impl}-${setimpl}-nodes-1.0 {nodes, bad switch} {
    SETUP
    catch {mygraph nodes -foo} msg
    mygraph destroy
    set msg
} {bad restriction "-foo": must be -adj, -embedding, -filter, -in, -inner, -key, -out, or -value}

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

test graph-${impl}-${setimpl}-nodes-2.0 {nodes, empty graph} {
    SETUP
    set result [mygraph nodes]
    mygraph destroy
    set result
} {}

test graph-${impl}-${setimpl}-nodes-2.1 {nodes} {
    SETUP
    mygraph node insert 0 1 2 3 4 5
    set result [lsort [mygraph nodes]]
    mygraph destroy
    set result
} {0 1 2 3 4 5}

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

# (1) -key, -value
# -------------------------------------------------------------------------
# Wrong # args: Missing, Too many

test graph-${impl}-${setimpl}-nodes-key-1.0 {nodes, wrong#args, missing} {
    SETUP
    catch {mygraph nodes -key} msg
    mygraph destroy
    set msg
} "wrong # args: should be \"$MY nodes ?-key key? ?-value value? ?-filter cmd? ?-in|-out|-adj|-inner|-embedding node node...?\""

test graph-${impl}-${setimpl}-nodes-key-1.1 {nodes, wrong#args, missing} {
    SETUP
    catch {mygraph nodes -value} msg
    mygraph destroy
    set msg
} "wrong # args: should be \"$MY nodes ?-key key? ?-value value? ?-filter cmd? ?-in|-out|-adj|-inner|-embedding node node...?\""

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

test graph-${impl}-${setimpl}-nodes-key-2.0 {nodes, multiple -key} {
    SETUP
    catch {mygraph nodes -key foobar -value 1 -key foo} msg
    mygraph destroy
    set msg
} {invalid restriction: illegal multiple use of "-key"}

test graph-${impl}-${setimpl}-nodes-key-2.1 {nodes, multiple -value} {
    SETUP
    catch {mygraph nodes -key foobar -value 1 -value foo} msg
    mygraph destroy
    set msg
} {invalid restriction: illegal multiple use of "-value"}

test graph-${impl}-${setimpl}-nodes-key-2.2 {nodes, -value without -key} {
    SETUP
    catch {mygraph nodes -value 1} msg
    mygraph destroy
    set msg
} {invalid restriction: use of "-value" without "-key"}

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

test graph-${impl}-${setimpl}-nodes-key-3.0 {nodes, -key} {
    SETUP
    mygraph node insert n0 n1
    mygraph node set n0 foobar  1
    mygraph node set n1 blubber 2

    catch {mygraph nodes -key foobar} msg
    mygraph destroy
    set msg
} n0

test graph-${impl}-${setimpl}-nodes-key-3.1 {nodes, -key, -value} {
    SETUP
    mygraph node insert n0 n1
    mygraph node set n0 foobar 1
    mygraph node set n1 foobar 2

    catch {mygraph nodes -key foobar -value 1} msg
    mygraph destroy
    set msg
} n0

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

# (2) -filter
# -------------------------------------------------------------------------
# Wrong # args: Missing, Too many

test graph-${impl}-${setimpl}-nodes-filter-1.0 {nodes, wrong#args, missing} {
    SETUP
    catch {mygraph nodes -filter} msg
    mygraph destroy
    set msg
} "wrong # args: should be \"$MY nodes ?-key key? ?-value value? ?-filter cmd? ?-in|-out|-adj|-inner|-embedding node node...?\""

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

test graph-${impl}-${setimpl}-nodes-filter-2.0 {nodes, multiple -filter} {
    SETUP
    catch {mygraph nodes -filter foobar -filter foo} msg
    mygraph destroy
    set msg
} {invalid restriction: illegal multiple use of "-filter"}

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

test graph-${impl}-${setimpl}-nodes-filter-3.0 {nodes, -filter} {
    SETUP

    mygraph node insert 1 2 3 4 5 6
    mygraph node set 1 volume 30
    mygraph node set 3 volume 50

    proc vol {g n} {
	$g node keyexists $n volume
    }

    set result [lsort [mygraph nodes -filter vol]]
    mygraph destroy
    rename vol {}

    set result
} {1 3}

test graph-${impl}-${setimpl}-nodes-filter-3.1 {nodes, -filter} {
    SETUP

    mygraph node insert 1 2 3 4 5 6
    mygraph node set 1 volume 30
    mygraph node set 3 volume 50

    proc vol {g n} {
	if {![$g node keyexists $n volume]} {return 0}
	expr {[$g node get $n volume] > 40}
    }

    set result [mygraph nodes -filter vol]
    mygraph destroy
    rename vol {}

    set result
} 3

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

# (3) -in, -out, -adj, -inner, -embedding
# -------------------------------------------------------------------------
# Wrong # args: Missing, Too many

set n 0
foreach switch {-in -out -adj -inner -embedding} {

    test graph-${impl}-${setimpl}-nodes-ioaie-1.$n "nodes, $switch, wrong#args, missing" {
	SETUP
	catch {mygraph nodes $switch} msg
	mygraph destroy
	set msg
    } "wrong # args: should be \"$MY nodes ?-key key? ?-value value? ?-filter cmd? ?-in|-out|-adj|-inner|-embedding node node...?\"" ; # {}

    incr n
}

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

set n 0
foreach switch {-in -out -adj -inner -embedding} {

    test graph-${impl}-${setimpl}-nodes-ioaie-2.$n "nodes, $switch, missing node" {
	SETUP
	catch {mygraph nodes $switch x} msg
	mygraph destroy
	set msg
    } [MissingNode $MY x] ; # {}

    incr n

    foreach switchB {-in -out -adj -inner -embedding} {

	test graph-${impl}-${setimpl}-nodes-ioaie-2.$n "nodes, $switch, $switchB together" {
	    SETUP
	    catch {mygraph nodes $switch $switchB x} msg
	    mygraph destroy
	    set msg
	} {invalid restriction: illegal multiple use of "-in"|"-out"|"-adj"|"-inner"|"-embedding"} ; # {}

	incr n
    }
}

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

set n 0
foreach {switch nodes expected} {
    -in        {1 2 3} {-1 1 2 3 4 5 6} -in        {4 5 6} {}
    -out       {1 2 3} {1 2 3}          -out       {4 5 6} {1 2 3}
    -adj       {1 2 3} {-1 1 2 3 4 5 6} -adj       {4 5 6} {1 2 3}
    -inner     {1 2 3} {1 2 3}          -inner     {4 5 6} {}
    -embedding {1 2 3} {-1 4 5 6}       -embedding {4 5 6} {1 2 3}
    -in        {1 2}   {-1 1 3 4 5}     -in        {4 5}   {}
    -out       {1 2}   {2 3}            -out       {4 5}   {1 2}
    -adj       {1 2}   {-1 1 2 3 4 5}   -adj       {4 5}   {1 2}
    -inner     {1 2}   {1 2}            -inner     {4 5}   {}
    -embedding {1 2}   {-1 3 4 5}       -embedding {4 5}   {1 2}
    -in        {1}     {3 4}            -in        {4}     {}
    -out       {1}     {2}              -out       {4}     {1}
    -adj       {1}     {2 3 4}          -adj       {4}     {1}
    -inner     {1}     {}               -inner     {4}     {}
    -embedding {1}     {2 3 4}          -embedding {4}     {1}
    -in        {1 4}   {3 4}            -in        {4 2}   {-1 1 5}
    -out       {1 4}   {1 2}            -out       {4 2}   {1 3}
    -adj       {1 4}   {1 2 3 4}        -adj       {4 2}   {-1 1 3 5}
    -inner     {1 4}   {1 4}            -inner     {4 2}   {}
    -embedding {1 4}   {2 3}            -embedding {4 2}   {-1 1 3 5}
    -in        {1 -1}  {3 4}
    -out       {1 -1}  2
    -adj       {1 -1}  {2 3 4}
    -inner     {1 -1}  {}
    -embedding {1 -1}  {2 3 4}
} {
    lappend expected $switch $nodes

    test graph-${impl}-${setimpl}-nodes-ioaie-3.$n "nodes, $switch ($nodes)" {
	SETUP
	# Nodes (digits -1,1-6) and arcs (letters A-G), no direction
	#        4
	#        |A
	#        1     -1
	#      D/ \   /G
	#      /   \E/
	#     3 --- 2
	#   C/  F    \B
	#   6         5
	
	mygraph node insert 1 2 3 4 5 6 -1
	mygraph arc  insert 4 1 A
	mygraph arc  insert 5 2 B
	mygraph arc  insert 6 3 C
	mygraph arc  insert 3 1 D
	mygraph arc  insert 1 2 E
	mygraph arc  insert 2 3 F
	mygraph arc  insert -1 2 G

	set result [lsort [eval [linsert $nodes 0 mygraph nodes $switch]]]
	mygraph destroy
	lappend result $switch $nodes
	set result
    } $expected ; # {}

    incr n
}
unset n

# ---------------------------------------------------
# Test with many parallel arcs, beyond the number of nodes, i.e. lots
# of duplicated sources and destinations, to check that the dup
# removal works correctly. See bug [SF 1923685].

set n 0
foreach {switch nodes expected} {
    -in        2       1
    -out       2       3
    -adj       2       {1 3}
    -inner     {1 2 3} {1 2 3}
    -embedding 2       {1 3}
} {
    lappend expected $switch $nodes

    test graph-${impl}-${setimpl}-nodes-parallel-ioaie-bug1923685-4.$n "nodes, $switch, parallel arcs, bug 1923685" {
	SETUP

	mygraph node insert 1 2 3 4
	mygraph arc  insert 1 2 A ; mygraph arc  insert 2 3 A.
	mygraph arc  insert 1 2 B ; mygraph arc  insert 2 3 B.
	mygraph arc  insert 1 2 C ; mygraph arc  insert 2 3 C.
	mygraph arc  insert 1 2 D ; mygraph arc  insert 2 3 D.
	mygraph arc  insert 1 2 E ; mygraph arc  insert 2 3 E.
	mygraph arc  insert 1 2 F ; mygraph arc  insert 2 3 F.
	mygraph arc  insert 1 2 G ; mygraph arc  insert 2 3 G.
	mygraph arc  insert 1 2 H ; mygraph arc  insert 2 3 H.

	set result [lsort [eval [linsert $nodes 0 mygraph nodes $switch]]]
	mygraph destroy
	lappend result $switch $nodes
	set result
    } $expected ; # {}

    incr n
}
unset n

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