head	1.13;
access;
symbols
	tcllib-1-13:1.13
	tcllib-1-12:1.13
	tklib-0-5:1.8
	tcllib-1-11-1:1.8;
locks; strict;
comment	@# @;


1.13
date	2009.11.03.17.38.30;	author andreas_kupries;	state Exp;
branches;
next	1.12;

1.12
date	2009.09.24.19.30.11;	author andreas_kupries;	state Exp;
branches;
next	1.11;

1.11
date	2009.09.22.20.30.53;	author andreas_kupries;	state Exp;
branches;
next	1.10;

1.10
date	2009.09.21.23.48.03;	author andreas_kupries;	state Exp;
branches;
next	1.9;

1.9
date	2009.09.15.19.24.12;	author andreas_kupries;	state Exp;
branches;
next	1.8;

1.8
date	2008.11.19.07.39.33;	author andreas_kupries;	state Exp;
branches;
next	1.7;

1.7
date	2008.11.18.03.49.57;	author andreas_kupries;	state Exp;
branches;
next	1.6;

1.6
date	2008.11.14.04.13.16;	author andreas_kupries;	state Exp;
branches;
next	1.5;

1.5
date	2008.11.13.05.36.53;	author andreas_kupries;	state Exp;
branches;
next	1.4;

1.4
date	2008.11.08.09.57.32;	author andreas_kupries;	state Exp;
branches;
next	1.3;

1.3
date	2008.11.08.06.43.18;	author andreas_kupries;	state Exp;
branches;
next	1.2;

1.2
date	2008.11.07.03.47.33;	author andreas_kupries;	state Exp;
branches;
next	1.1;

1.1
date	2008.11.05.07.28.53;	author andreas_kupries;	state Exp;
branches;
next	;


desc
@@


1.13
log
@
	* graph/tests/XOpsSetup: [Bug 2811747]: Removed the import of
	* graph/tests/Xsetup: command struct::graph into the global
	* graph/tests/Xsupport: namespace in the testsuite, and updated
	* graph/tests/arcs.test: all users. This prevents the masking
	* graph/tests/command.test: of scope errors in the graph::op
	* graph1.test: package when its testsuite is run.
@
text
@# -*- tcl -*-
# graphops.testsuite.setup:  Setting up implementation specific definitions.
#
# Copyright (c) 2008 Andreas Kupries <andreas_kupries@@users.sourceforge.net>
# All rights reserved.
#
# RCS: @@(#) $Id: XOpsSetup,v 1.12 2009/09/24 19:30:11 andreas_kupries Exp $

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

# Place holder for future setup / helper actions.


proc SETUP_A {} {
    # Used by kruskal, prim tests

    struct::graph mygraph
    mygraph node insert 'node0'
    mygraph node insert 'node1'
    mygraph node insert 'node2'
    mygraph node insert 'node3'
    mygraph node insert 'node4'
    mygraph node insert 'node5'
    mygraph node insert 'node6'

    mygraph arc insert 'node0' 'node1' 'arc0_1'
    mygraph arc insert 'node0' 'node3' 'arc0_3'
    mygraph arc insert 'node1' 'node3' 'arc1_3' 
    mygraph arc insert 'node1' 'node4' 'arc1_4'
    mygraph arc insert 'node2' 'node0' 'arc2_0'
    mygraph arc insert 'node2' 'node5' 'arc2_5'
    mygraph arc insert 'node3' 'node4' 'arc3_4'
    mygraph arc insert 'node3' 'node6' 'arc3_6'
    mygraph arc insert 'node3' 'node2' 'arc3_2'
    mygraph arc insert 'node3' 'node5' 'arc3_5'
    mygraph arc insert 'node4' 'node6' 'arc4_6'
    mygraph arc insert 'node6' 'node5' 'arc6_5'

    mygraph arc setweight 'arc0_1' 2
    mygraph arc setweight 'arc0_3' 1
    mygraph arc setweight 'arc1_3' 3
    mygraph arc setweight 'arc1_4' 10
    mygraph arc setweight 'arc2_0' 4
    mygraph arc setweight 'arc2_5' 5
    mygraph arc setweight 'arc3_4' 2
    mygraph arc setweight 'arc3_6' 4
    mygraph arc setweight 'arc3_2' 2
    mygraph arc setweight 'arc3_5' 8
    mygraph arc setweight 'arc4_6' 6
    mygraph arc setweight 'arc6_5' 1

    # 2 --/4/--> 0 --/2/--> 1
    # |^         |         /|
    # - \        -        / -
    # 5  -|2|-   1   -/3/-  10
    # -       \  -  /       -
    # |        \ | /        |
    # V         \VV         V
    # 5 <--/8/-- 3 --/2/--> 4
    #  ^         |         /
    #   \        -        /
    #    -|1|-   4   -/6/-
    #         \  -  /
    #          \ | /
    #           \VV
    #            6

    return
}

proc SETUP_A2 {} {
    SETUP_A
    mygraph arc insert 'node0' 'node2' 'arc0_2'
    mygraph arc insert 'node0' 'node4' 'arc0_4'
    return
}

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

proc SETUP_B {} {
    # Predefined Graph for testing on:
    # - isConnected?
    # - connectedComponents
    # - prim
    # - isEulerian?
    # Author: Alejandro Eduardo Cruz Paz
    # 28 August 2008

    struct::graph mygraph
    # Graph's nodes definition
    mygraph node insert S
    mygraph node insert A
    mygraph node insert B
    mygraph node insert C
    mygraph node insert D
    mygraph node insert E
    
    # setup arcs and it's weights
    mygraph arc insert S A S_A ;	mygraph arc setweight S_A 3
    mygraph arc insert A C A_C ;	mygraph arc setweight A_C 2
    mygraph arc insert S B S_B ;	mygraph arc setweight S_B 1
    mygraph arc insert A B A_B ;	mygraph arc setweight A_B 1
    mygraph arc insert B C B_C ;	mygraph arc setweight B_C 3
    mygraph arc insert B D B_D ;	mygraph arc setweight B_D 5
    mygraph arc insert C D C_D ;	mygraph arc setweight C_D 1
    mygraph arc insert D E D_E ;	mygraph arc setweight D_E 1
    mygraph arc insert C E C_E ;	mygraph arc setweight C_E 3

    # S --/3/--> A --/2/--> C --/3/--> E
    #  \         |        /^|        /-^
    #   \        -       /  -       /
    #    -|1|    1  -|3|-   1  -|1|-
    #        \   - /        - /
    #         \  V/         V/
    #          > B --/5/--> D
    #

    return
}

proc SETUP_B2 {} {
    struct::graph mygraph

    mygraph node insert A B C D E F G

    mygraph arc insert A B
    mygraph arc insert A E
    mygraph arc insert B D
    mygraph arc insert B F
    mygraph arc insert C A
    mygraph arc insert D C
    mygraph arc insert E B
    mygraph arc insert E F
    mygraph arc insert F A
    mygraph arc insert F G
    mygraph arc insert G E
    return
}

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

proc SETUP_C {} {
    # Predefined Graph for testing on:
    # - isConnected? 
    # - isEulerian?
    # - isBipartite?
    # Author: Alejandro Eduardo Cruz Paz
    # 28 August 2008

    struct::graph mygraph
    mygraph node insert A
    mygraph node insert B
    mygraph node insert C
    mygraph node insert D
    mygraph node insert E
    mygraph node insert F

    mygraph arc insert A B A_B 
    mygraph arc insert B D B_D
    mygraph arc insert D C D_C
    mygraph arc insert C A C_A
    mygraph arc insert A E A_E
    mygraph arc insert E F E_F

    mygraph arc setweight A_B 9
    mygraph arc setweight B_D 10
    mygraph arc setweight D_C 4
    mygraph arc setweight C_A 3
    return
}

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

proc SETUP_D {} {
    # Predefined Graph for testing on:
    # - isConnected?
    # - isEulerian?
    # - isBipartite?
    # Author: Alejandro Eduardo Cruz Paz
    # 28 August 2008

    struct::graph mygraph
    mygraph node insert a
    mygraph node insert b
    mygraph node insert c
    mygraph node insert d
    
    mygraph node insert f
    mygraph node insert g
    mygraph node insert h
    
    mygraph node insert i
    mygraph node insert j
    
    mygraph arc insert d f
    mygraph arc insert h j
    mygraph arc insert i j
    mygraph arc insert f g
    mygraph arc insert g h
    mygraph arc insert h f
    mygraph arc insert a b
    mygraph arc insert b c
    mygraph arc insert c d
    mygraph arc insert d a
    return
}

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

proc SETUP_E {} {
    # Predefined Graph for testing on:
    #  - isBipartite?
    #  - maxMatching
    # - isEulerian?
    # Author: Alejandro Eduardo Cruz Paz
    # 28 August 2008

    struct::graph mygraph	
    mygraph node insert 1w
    mygraph node insert 1b
    mygraph node insert 2w
    mygraph node insert 2b
    mygraph node insert 3w
    mygraph node insert 3b
    mygraph node insert 4w
    mygraph node insert 4b
    mygraph node insert 5w
    mygraph node insert 5b
    mygraph node insert 6w
    mygraph node insert 6b
    mygraph node insert 7w
    mygraph node insert 7b
    mygraph node insert 8w
    mygraph node insert 8b
    
    mygraph arc insert 1b 1w
    mygraph arc insert 1b 2w
    mygraph arc insert 2b 1w
    mygraph arc insert 2b 2w
    mygraph arc insert 2b 3w
    mygraph arc insert 2b 4w
    mygraph arc insert 3b 2w
    mygraph arc insert 3b 3w
    mygraph arc insert 3b 5w
    mygraph arc insert 3w 4b
    mygraph arc insert 4b 3w
    mygraph arc insert 4b 4w
    mygraph arc insert 4b 6w
    mygraph arc insert 4w 5b
    mygraph arc insert 4w 7b
    mygraph arc insert 5b 5w
    mygraph arc insert 5b 6w
    mygraph arc insert 5w 6b
    mygraph arc insert 6b 6w
    mygraph arc insert 6w 7b
    mygraph arc insert 6w 8b
    mygraph arc insert 7b 7w 
    mygraph arc insert 7w 8b
    mygraph arc insert 8b 8w
    mygraph arc insert 8w 7b
    return
}

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

proc SETUP_F {} {
    # Predefined Graph for testing on:
    #  - isBipartite?
    #  - maxMatching
    # Author: Alejandro Eduardo Cruz Paz
    # 28 August 2008
    struct::graph mygraph
    
    mygraph node insert 1w
    mygraph node insert 1b
    mygraph node insert 2w
    mygraph node insert 2b
    mygraph node insert 3w
    mygraph node insert 3b
    mygraph node insert 4w
    mygraph node insert 4b
    
    mygraph arc insert 1b 2w
    mygraph arc insert 1b 3w
    mygraph arc insert 1b 4w
    mygraph arc insert 1w 3b
    mygraph arc insert 2b 1w
    mygraph arc insert 2b 3w
    mygraph arc insert 3b 2w
    mygraph arc insert 3w 4b
    mygraph arc insert 4b 1w
    mygraph arc insert 4b 2w
    mygraph arc insert 4w 2b
    mygraph arc insert 4w 3b
    return
}

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

proc SETUP_G {} {
    # Predefined Graph for testing on:
    #  - isBipartite?
    #  - maxMatching 
    #  - isBridge?
    # Author: Alejandro Eduardo Cruz Paz
    # 28 August 2008

    struct::graph mygraph
    
    mygraph node insert 1w
    mygraph node insert 1b
    mygraph node insert 2w
    mygraph node insert 2b
    mygraph node insert 3w
    mygraph node insert 3b
    mygraph node insert 4w
    mygraph node insert 4b
    mygraph node insert 5w
    mygraph node insert 5b
    
    mygraph arc insert 1b 5w bridge1
    mygraph arc insert 2b 4w
    mygraph arc insert 2w 4b
    mygraph arc insert 2w 5b
    mygraph arc insert 3b 4w
    mygraph arc insert 3w 4b
    mygraph arc insert 3w 5b
    mygraph arc insert 4b 4w bridge2
    mygraph arc insert 5b 1w bridge3
    mygraph arc insert 5w 2b
    mygraph arc insert 5w 3b nobridge
    return
}

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

proc SETUP_H {} {
    # Predefined Graph for testing on:
    # - isConnected?
    # - isEulerian?
    # Author: Alejandro Eduardo Cruz Paz
    # 28 August 2008

    struct::graph mygraph
    mygraph node insert A
    mygraph node insert B
    mygraph node insert C
    mygraph node insert D
    mygraph node insert E

    mygraph arc insert A B A_B ;    mygraph arc setweight A_B 10
    mygraph arc insert B C B_C ;    mygraph arc setweight B_C 8
    mygraph arc insert D C D_C ;    mygraph arc setweight D_C 2
    mygraph arc insert B D B_D ;    mygraph arc setweight B_D 7
    mygraph arc insert C D C_D ;    mygraph arc setweight C_D 1
    mygraph arc insert D E D_E ;    mygraph arc setweight D_E 6
    mygraph arc insert E A E_A ;    mygraph arc setweight E_A 4
    return
}

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

proc SETUP_I {} {
    # Predefined Graph for testing on:
    # isConnected?
    # isEulerian?
    # Author: Alejandro Eduardo Cruz Paz
    # 28 August 2008

    struct::graph mygraph
    
    mygraph node insert N1 
    mygraph node insert N2
    mygraph node insert N3
    mygraph node insert N4
    mygraph node insert N5
    
    mygraph arc insert N1 N5 N1_N5
    mygraph arc insert N2 N5 N2_N5
    mygraph arc insert N3 N5 N3_N5
    mygraph arc insert N4 N5 N4_N5
    return
}

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

proc SETUP_J {} {
    # Predefined Graph for testing on:
    # isConnected?
    # Author: Alejandro Eduardo Cruz Paz
    # 28 August 2008

    struct::graph mygraph
    
    mygraph node insert 1
    mygraph node insert 2
    mygraph node insert 3
    mygraph node insert 4
    mygraph node insert 5
    mygraph node insert 6
    mygraph node insert 7
    
    mygraph arc insert 7 6
    mygraph arc insert 6 7
    mygraph arc insert 1 4
    mygraph arc insert 4 5
    return
}

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

proc SETUP_K {} {
    # Predefined Graph for testing on:
    # isConnected?
    # Author: Alejandro Eduardo Cruz Paz
    # 28 August 2008

    struct::graph mygraph
    
    mygraph node insert No1
    mygraph node insert No2
    mygraph node insert No3
    mygraph node insert No4
    mygraph node insert No5
    
    mygraph arc insert No1 No2 a
    mygraph arc insert No2 No3 b
    mygraph arc insert No3 No4 c
    mygraph arc insert No4 No2 d
    
    mygraph arc insert No5 No5 e
    return
}

proc SETUP_K2 {} {
    SETUP_K
    mygraph arc insert No5 No1 f
    mygraph arc insert No5 No2 g
    return
}

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

proc SETUP_L {} {
    # Koenigsberg.

    struct::graph mygraph
    mygraph node insert a b c d
    mygraph arc  insert a c
    mygraph arc  insert a d
    mygraph arc  insert b a
    mygraph arc  insert b c
    mygraph arc  insert c a
    mygraph arc  insert d a
    mygraph arc  insert d b
    return
}    

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

proc SETUP_M {} {
    # penta-hex-something

    struct::graph mygraph
    mygraph node insert 1 2 3 4 5 6
    mygraph arc  insert 1 2
    mygraph arc  insert 2 3
    mygraph arc  insert 3 4
    mygraph arc  insert 4 5
    mygraph arc  insert 5 1
    mygraph arc  insert 1 6
    mygraph arc  insert 6 2
    mygraph arc  insert 2 5
    mygraph arc  insert 5 6
    mygraph arc  insert 6 3
    mygraph arc  insert 3 1
    return
}    

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

proc SETUP_N {} {
    # Predefined Graph for testing on:
    # isConnected?
    # Author: Alejandro Eduardo Cruz Paz
    # 28 August 2008

    struct::graph mygraph
    
    mygraph node insert 0 1 2 a b c d e f
    mygraph arc insert 0 1
    mygraph arc insert 1 2
    mygraph arc insert 2 0

    mygraph arc insert a b
    mygraph arc insert b 0
    mygraph arc insert 0 a

    mygraph arc insert c d
    mygraph arc insert d 1
    mygraph arc insert 1 c

    mygraph arc insert e f
    mygraph arc insert f 2
    mygraph arc insert 2 e
    return
}

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

proc SETUP_BELLMANFORD_1 {} {
    #Graph for testing Bellman's Ford algorithm (and also other pathfinding algorithms)
    #Used for:
    #Bellman's-Ford
    #Floyd-Warshall's
    #Basic test
    
    struct::graph mygraph
    
    mygraph node insert node1 node2 node3 node4
    mygraph arc insert node1 node2 edge12
    mygraph arc insert node2 node3 edge23
    mygraph arc insert node3 node4 edge34
    mygraph arc insert node4 node1 edge41
    
    mygraph arc setunweighted 1
    return
}

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

proc SETUP_BELLMANFORD_2 {} {
    #Graph for testing Bellman-Ford's Algorithm
    #More complex test case
    #Used by:
    #Bellman-Ford's Algorithm
    #Floyd-Warshall's Algorithm
    #Shortest Pathfinding by BFS algorithm
    #BFS Algorithm
    
    struct::graph mygraph
    
    mygraph node insert node1 node2 node3 node4 node5 node6
    
    mygraph arc insert node1 node2 edge12
    mygraph arc setweight edge12 8
    mygraph arc insert node1 node3 edge13
    mygraph arc setweight edge13 6
    mygraph arc insert node2 node4 edge24
    mygraph arc setweight edge24 -1
    mygraph arc insert node3 node2 edge32
    mygraph arc setweight edge32 3
    mygraph arc insert node3 node5 edge35
    mygraph arc setweight edge35 -2
    mygraph arc insert node4 node3 edge43
    mygraph arc setweight edge43 -2
    mygraph arc insert node4 node6 edge46
    mygraph arc setweight edge46 3
    mygraph arc insert node5 node6 edge56
    mygraph arc setweight edge56 2
    
    return
}

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

proc SETUP_POSITIVEWEIGHTED_K4 {} {
    SETUP_UNWEIGHTED_K4
    mygraph arc setunweighted 2
    return
}

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

proc SETUP_NEGATIVECYCLE_1 {} {
    #Graph containing cycle with negative sum of weights
    #Used for testing:
    #Bellman-Ford's Algorithm
    #Johnson's Algorithm
    #Floyd-Warshall's Algorithm
    
    struct::graph mygraph
    
    mygraph node insert node1 node2 node3
    mygraph arc insert node1 node2 edge12
    mygraph arc setweight edge12 -1
    mygraph arc insert node2 node3 edge23
    mygraph arc setweight edge23 -2
    mygraph arc insert node3 node1 edge31
    mygraph arc setweight edge31 -3
    
    return
}

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

proc SETUP_NEGATIVECYCLE_2 {} {
    #Graph containing cycle with negative sum of weights
    #Used for testing:
    #Bellman-Ford's Algorithm
    #Johnson's Algorithm
    #Floyd-Warshall's Algorithm
    
    struct::graph mygraph
    
    mygraph node insert node1 node2 node3 node4 node5 node6
    mygraph arc insert node1 node6
    mygraph arc insert node6 node5
    mygraph arc insert node5 node4
    mygraph arc insert node4 node3
    mygraph arc insert node3 node2
    mygraph arc insert node2 node1
    mygraph arc insert node6 node2 edge62
    mygraph arc setweight edge62 -5
    mygraph arc setunweighted 1
    
    return 
    
}

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

proc SETUP_NEGATIVECYCLE_3 {} {
    #Graph containing cycle with negative sum of weights
    #Used for testing:
    #Bellman-Ford's Algorithm
    #Johnson's Algorithm
    #Floyd-Warshall's Algorithm
    
    struct::graph mygraph
    
    mygraph node insert node1 node2 node3 node4 node5
    mygraph arc insert node1 node2 edge12
    mygraph arc setweight edge12 6
    mygraph arc insert node1 node5 edge15
    mygraph arc setweight edge15 7
    mygraph arc insert node2 node4 edge24
    mygraph arc setweight edge24 -4
    mygraph arc insert node2 node5 edge25
    mygraph arc setweight edge25 2
    mygraph arc insert node3 node2 edge32
    mygraph arc setweight edge32 -2
    mygraph arc insert node4 node3 edge43
    mygraph arc setweight edge43 7
    mygraph arc insert node4 node1 edge41
    mygraph arc setweight edge41 2
    mygraph arc insert node5 node3 edge53
    mygraph arc setweight edge53 -3
    mygraph arc insert node5 node4 edge54
    mygraph arc setweight edge54 9
    
    return
}

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

proc SETUP_K4 {} {
    #Complete graph with 4 nodes
    #Here without one edge - test for directed graphs
    #Used by:
    #For distance searches: Johnson's and Bellman-Ford's
    #Vertices Cover
    
    struct::graph mygraph
    
    mygraph node insert node1 node2 node3 node4

    mygraph arc insert node1 node2 edge12
    mygraph arc setweight edge12 1
    mygraph arc insert node1 node3 edge13
    mygraph arc setweight edge13 1
    mygraph arc insert node1 node4 edge14
    mygraph arc setweight edge14 1

    mygraph arc insert node2 node1 edge21
    mygraph arc setweight edge21 1
    mygraph arc insert node2 node3 edge23
    mygraph arc setweight edge23 1
    mygraph arc insert node2 node4 edge24
    mygraph arc setweight edge24 1

    mygraph arc insert node3 node1 edge31
    mygraph arc setweight edge31 1
    mygraph arc insert node3 node2 edge32
    mygraph arc setweight edge32 1
    mygraph arc insert node3 node4 edge34
    mygraph arc setweight edge34 1

    mygraph arc insert node4 node1 edge41
    mygraph arc setweight edge41 2
    mygraph arc insert node4 node2 edge42
    mygraph arc setweight edge42 2
    
    return
}

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

proc SETUP_PARTIALLYCONNECTED_1 {} {

    #Graph where their does not exists a path between each pair of vertices
    #Used for testing:
    #Bellman-Ford's Algorithm (Causes appearing of Inf values as a result)
    #Johnson's Algorithm (Causes appearing of Inf values as a result)
    #Metric Travelling Salesman 2-approximation algorithm
    
    struct::graph mygraph
    
    mygraph node insert node1 node2 node3 node4 node5
    
    mygraph arc insert node1 node5
    mygraph arc insert node2 node5
    mygraph arc insert node3 node5
    mygraph arc insert node4 node5
    
    mygraph arc setunweighted 1
    
    return
}

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

proc SETUP_JOHNSONS_1 {} {
    #Graph for testing Johnson's Algorithm
    #Used by:
    #Johnson's Algorithm
    #Floyd-Warshall's Algorithm
    #
    
    struct::graph mygraph
    
    mygraph node insert node1 node2 node3 node4 node5
    
    mygraph arc insert node1 node3 edge13
    mygraph arc setweight edge13 1
    mygraph arc insert node1 node4 edge14
    mygraph arc setweight edge14 7

    mygraph arc insert node2 node1 edge21
    mygraph arc setweight edge21 4

    mygraph arc insert node3 node2 edge32
    mygraph arc setweight edge32 -5
    mygraph arc insert node3 node5 edge35
    mygraph arc setweight edge35 2

    mygraph arc insert node4 node3 edge43
    mygraph arc setweight edge43 6

    mygraph arc insert node5 node1 edge51
    mygraph arc setweight edge51 3
    mygraph arc insert node5 node2 edge52
    mygraph arc setweight edge52 8
    mygraph arc insert node5 node4 edge54
    mygraph arc setweight edge54 -4
    
    return
}

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

proc SETUP_JOHNSONS_2 {} {
    #Graph for testing Johnson's Algorithm
    #Used by:
    #Johnson's Algorithm
    #Floyd-Warshall's Algorithm
    
    struct::graph mygraph
    
    mygraph node insert node1 node2 node3 node4 node5 node6
    
    mygraph arc insert node1 node2 edge12
    mygraph arc setweight edge12 8
    mygraph arc insert node1 node6 edge16
    mygraph arc setweight edge16 6
    mygraph arc insert node2 node3 edge23
    mygraph arc setweight edge23 -1
    mygraph arc insert node3 node4 edge34
    mygraph arc setweight edge34 3
    mygraph arc insert node3 node6 edge36
    mygraph arc setweight edge36 -2
    mygraph arc insert node5 node4 edge54
    mygraph arc setweight edge54 2
    mygraph arc insert node6 node2 edge62
    mygraph arc setweight edge62 3
    mygraph arc insert node6 node5 edge65
    mygraph arc setweight edge65 -2
    
    return
}

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

proc SETUP_UNWEIGHTED_K4 {} {
    #Unweighted directed complete graph K4
    #Used by:
    #Bellman's-Ford
    #Johnson's Algorithm
    #Floyd-Warshall's Algorithm
    #Metric Travelling Salesman 2-approximation algorithm
    #Christofides Algorithm
    #Greedy Maximum Independent Set algorithm
    #Unweighted k-center 2-approximation algorithm
    #Weighted k-center 3-approximation algorithm
    #Greedy Weighted Maximum Independent Set algorithm
    
    struct::graph mygraph
    
    mygraph node insert node1 node2 node3 node4
    
    mygraph arc insert node1 node2
    mygraph arc insert node1 node3
    mygraph arc insert node1 node4
    mygraph arc insert node2 node3
    mygraph arc insert node2 node4
    mygraph arc insert node2 node1
    mygraph arc insert node3 node1
    mygraph arc insert node3 node2
    mygraph arc insert node3 node4
    mygraph arc insert node4 node1
    mygraph arc insert node4 node2
    mygraph arc insert node4 node3
    
    return
}

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

proc SETUP_UNDIRECTED_K4 {} {
    #Undirected complete graph K4
    #Used by:
    #Metric Travelling Salesman 2-approximation algorithm
    #Vertices Cover
    
    struct::graph mygraph
    
    mygraph node insert node1 node2 node3 node4
    
    mygraph arc insert node1 node2 edge12
    mygraph arc insert node1 node3 edge13
    mygraph arc insert node1 node4 edge14
    mygraph arc insert node2 node3 edge23
    mygraph arc insert node2 node4 edge24
    mygraph arc insert node3 node4 edge34
    
    return
}

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

proc SETUP_PARTIALLYWEIGHTED_K4 {} {
    #complete graph K4 with some weights set on edges
    #Used by:
    #Bellman's-Ford
    #Johnson's Algorithm
    SETUP_UNWEIGHTED_K4
    
    mygraph arc setweight arc1 1
    mygraph arc setweight arc2 2
    mygraph arc setweight arc3 3
    
    return
}

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

proc SETUP_NOEDGES_1 {} {
    #Graph containing only nodes
    #Used by:
    #Johnson's Algorithm
    #Floyd-Warshall's Algorithm
    #Metric Travelling Salesman 2-approximation algorithm
    #Christofides Algorithm
    #Max Cut 2-approximation algorithm
    
    struct::graph mygraph 
    
    mygraph node insert node1 node2 node3 node4
    
    return
}

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

proc SETUP_ZEROWEIGHTED_K4 {} {
    #K4 graph with all edge's weights set to 0
    #Used by:
    #Bellman's-Ford
    #Johnson's Algorithm
    #Floyd-Warshall's Algorithm
    
    SETUP_UNWEIGHTED_K4
    mygraph arc setunweighted
    
    return
}

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

proc SETUP_PARTIALLYZEROWEIGHTED {} {
    #graph with some weights of edges set to 0 (others set to 1)
    #Used by:
    #Bellman's-Ford
    #Johnson's Algorithm
    #Floyd-Warshall's Algorithm
    
    SETUP_BELLMANFORD_1
    
    mygraph arc setweight edge12 0
    mygraph arc setweight edge23 0
    
    return
}

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

proc SETUP_PARTIALLYZEROWEIGHTED_K4 {} {
    #K4 graph with some weights of edges set to 0
    #Used by:
    #Bellman's-Ford
    #Johnson's Algorithm
    #Floyd-Warshall's Algorithm
    
    SETUP_ZEROWEIGHTED_K4
    
    mygraph arc setweight arc1 1
    mygraph arc setweight arc2 2
    
    return
}

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

proc SETUP_ADJACENCYLIST_K4 {} {
    #special undirected K4 case where we have two arcs between two nodes
    #with different sources and targets
    struct::graph mygraph
    
    mygraph node insert node1 node2 node3 node4
    
    mygraph arc insert node1 node2
    mygraph arc insert node1 node3
    mygraph arc insert node1 node4 edge14
    mygraph arc insert node2 node3
    mygraph arc insert node3 node4
    mygraph arc insert node4 node1 edge41
    
    return
}
# -------------------------------------------------------------------------

proc SETUP_ADJACENCYLIST_K4_WEIGHTED {} {
    #weighted version of upper graph
    SETUP_ADJACENCYLIST_K4
    
    mygraph arc setunweighted 1
    
    return
}

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

proc SETUP_ADJACENCYLIST_K4_WEIGHTED_DIRECTED {} {
    #directed case, with mixed weights at crucial edges
    SETUP_ADJACENCYLIST_K4_WEIGHTED
    
    mygraph arc setweight edge14 2
    mygraph arc setweight edge41 3
    
    return
}

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

proc SETUP_ADJACENCYLIST_1 {} {
    #undirected and unweighted graph for Adjacency List Testing
    struct::graph mygraph
    
    mygraph node insert node1 node2 node3 node4 node5 node6
    mygraph arc insert node1 node2
    mygraph arc insert node1 node6
    mygraph arc insert node2 node3
    mygraph arc insert node3 node6
    mygraph arc insert node4 node5
    mygraph arc insert node4 node6
    
    return
}

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

proc SETUP_TSP_1 {} {

    #Graph object for Metric Travelling Salesman problems testing
    #Used by:
    #Metric Travelling Salesman 2-approximation algorithm
    
    struct::graph mygraph

    mygraph node insert node1 node2 node3 node4 node5 node6
    mygraph arc insert node1 node2 
    mygraph arc insert node2 node3
    mygraph arc insert node3 node4
    mygraph arc insert node4 node5
    mygraph arc insert node5 node1
    mygraph arc insert node6 node1
    mygraph arc insert node6 node2
    mygraph arc insert node6 node3
    mygraph arc insert node6 node4
    mygraph arc insert node6 node5
    mygraph arc setunweighted 1
    mygraph arc insert node1 node3
    mygraph arc insert node1 node4
    mygraph arc insert node2 node4
    mygraph arc insert node2 node5
    mygraph arc insert node3 node5
    mygraph arc setunweighted 2
    
    return
}

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

proc SETUP_TSP_2 {} {
    
    #Graph object for Metric Travelling Salesman problems testing
    #Used by:
    #Metric Travelling Salesman 2-approximation algorithm
    
    struct::graph mygraph 
    
    mygraph node insert node1 node2 node3 node4 node5
    mygraph arc insert node1 node2
    mygraph arc insert node2 node3
    mygraph arc insert node3 node4
    mygraph arc insert node4 node1
    mygraph arc insert node5 node1
    mygraph arc insert node5 node2
    mygraph arc insert node5 node3
    mygraph arc insert node5 node4
    mygraph arc setunweighted 1
    mygraph arc insert node2 node4
    mygraph arc insert node1 node3
    mygraph arc setunweighted 2
    
    return
}

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

proc SETUP_TSP_3 {} {

    #Graph object for Metric Travelling Salesman problems testing
    #Used by:
    #Metric Travelling Salesman 2-approximation algorithm
    
    struct::graph mygraph
    
    mygraph node insert node1 node2 node3 node4
    mygraph arc insert node1 node2 
    mygraph arc insert node3 node2 
    mygraph arc insert node3 node4 
    mygraph arc insert node4 node1
    mygraph arc insert node2 node1 edge21
    mygraph arc insert node2 node3 edge23
    mygraph arc insert node4 node3 edge43
    mygraph arc insert node1 node4 edge14
    mygraph arc setunweighted 1
    mygraph arc insert node1 node3
    mygraph arc insert node2 node4
    mygraph arc setunweighted 3
    mygraph arc setweight edge23 5
    mygraph arc setweight edge21 4
    mygraph arc setweight edge43 6
    mygraph arc setweight edge14 7
    
    return
}


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

proc SETUP_MAXCUT_1 {} {
    #Graph representing Tight Example for Maximum Cut problem
    #In this case algorithm should find right solution.
    #Used by:
    #Max Cut 2-approximation algorithm
    
    struct::graph mygraph
    
    mygraph node insert node1 node2 node3 node4
    mygraph arc insert node1 node2 edge12
    mygraph arc insert node1 node4 edge14
    mygraph arc insert node2 node3 edge23
    mygraph arc insert node3 node4 edge34
    
    return
}

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

proc SETUP_MAXCUT_2 {} {
    #Graph representing Tight Example for Maximum Cut problem
    #In this case algorithm should find solution, with maximum aproximation factor : ALG = 2 * OPT
    #Used by:
    #Max Cut 2-approximation algorithm
    
    struct::graph mygraph
    
    mygraph node insert node1 node2 node3 node4
    mygraph arc insert node1 node3 edge13
    mygraph arc insert node1 node4 edge14
    mygraph arc insert node2 node3 edge23
    mygraph arc insert node2 node4 edge24
    
    return
}

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

proc SETUP_MAXCUT_3 {} {

    #Used by:
    #Max Cut 2-approximation algorithm
    
    struct::graph mygraph
    
    mygraph node insert node1 node2 node3 node4 node5 node6
    mygraph arc insert node1 node3
    mygraph arc insert node1 node6
    mygraph arc insert node2 node4
    mygraph arc insert node2 node5
    mygraph arc insert node3 node4
    mygraph arc insert node3 node5
    mygraph arc insert node4 node6
    
    return
}

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

proc SETUP_MAXCUT_4 {} {

    #Used by:
    #Max Cut 2-approximation algorithm
    
    struct::graph mygraph
    
    mygraph node insert node1 node2 node3 node4 node5 node6
    mygraph arc insert node1 node2 edge12
    mygraph arc insert node2 node1 edge21
    mygraph arc insert node2 node3 edge23
    mygraph arc insert node3 node2 edge32
    mygraph arc insert node1 node4 edge14
    mygraph arc insert node4 node5 edge45
    mygraph arc insert node5 node4 edge54
    mygraph arc insert node5 node6 edge56
    mygraph arc insert node6 node5 edge65
    
    return
}

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

proc SETUP_MAXCUT_5 {} {

    #Used by:
    #Max Cut 2-approximation algorithm
    
    struct::graph mygraph
    
    mygraph node insert node1 node2 node3 node4 node5 node6
    mygraph arc insert node1 node2 
    mygraph arc insert node1 node3
    mygraph arc insert node3 node1
    mygraph arc insert node4 node2
    mygraph arc insert node2 node4
    mygraph arc insert node4 node6
    mygraph arc insert node6 node4
    mygraph arc insert node5 node3
    mygraph arc insert node3 node5
    
    return
}

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

proc SETUP_COUNTEDGES_1 {U V} {

    #Used by:
    #Max Cut 2-approximation algorithm (subprocedure)
    
    upvar 1 U varU V varV
    struct::graph mygraph
    
    mygraph node insert node1 node2 node3 node4
    mygraph arc insert node1 node3
    mygraph arc insert node1 node4
    mygraph arc insert node4 node1
    mygraph arc insert node3 node2
    
    set varU "node1 node2"
    set varV "node3 node4"
    return
}

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

proc SETUP_COUNTEDGES_2 {U V} {

    #Used by:
    #Max Cut 2-approximation algorithm (subprocedure)
    
    upvar 1 U varU V varV
    struct::graph mygraph
    
    mygraph node insert node1 node2 node3 node4
    mygraph arc insert node1 node3
    mygraph arc insert node1 node4
    mygraph arc insert node4 node1
    mygraph arc insert node3 node2
    mygraph arc insert node1 node1
    mygraph arc insert node1 node2
    mygraph arc insert node4 node3
    
    set varU "node1 node2"
    set varV "node3 node4"
    return
}
# -------------------------------------------------------------------------

proc SETUP_COUNTEDGES_3 {U V} {

    #Used by:
    #Max Cut 2-approximation algorithm (subprocedure)
    
    upvar 1 U varU V varV
    struct::graph mygraph
    
    mygraph node insert node1 node2 node3 node4
    mygraph arc insert node1 node1
    mygraph arc insert node1 node2
    mygraph arc insert node4 node3
    
    set varU "node1 node2"
    set varV "node3 node4"
    return
}

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

proc SETUP_COUNTEDGES_4 {U V} {
    
    #Used by:
    #Max Cut 2-approximation algorithm (subprocedure)
    
    upvar 1 U varU V varV
    SETUP_COUNTEDGES_2 varU varV
    
    set varU "node1 node3"
    set varV "node2 node4"
    
    return
}

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

proc SETUP_CUT_1 {U V param} {

    #Used by:
    #Max Cut 2-approximation algorithm (subprocedure)
    
    upvar 1 U varU V varV param varParam
    SETUP_MAXCUT_3
    
    set varU "node1 node5 node4"
    set varV "node2 node3 node6"
    set varParam 7
    
    return
}

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

proc SETUP_CUT_2 {U V param} {

    #Used by:
    #Max Cut 2-approximation algorithm (subprocedure)
    
    upvar 1 U varU V varV param varParam
    SETUP_CUT_1 varU varV varParam
    
    set varU "node1 node3 node5"
    set varV "node2 node4 node6"
    set varParam 3
    
    return
}

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

proc SETUP_CREATETGRAPH_1 {E} {

    #Graph object for Metric Travelling Salesman problems testing
    #Used by:
    #Metric Travelling Salesman 2-approximation algorithm
    
    upvar 1 E edges
    struct::graph mygraph
    
    mygraph node insert node1 node2 node3 node4
    mygraph arc insert node1 node2 edge12
    mygraph arc setweight edge12 1
    mygraph arc insert node1 node3 edge13
    mygraph arc setweight edge13 2
    mygraph arc insert node1 node4 edge14
    mygraph arc setweight edge14 3
    mygraph arc insert node4 node1 edge41
    mygraph arc setweight edge41 4
    
    set edges "edge12 edge14"
    return
    
}

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

proc SETUP_CREATETGRAPH_2 {E} {

    #Graph object for Metric Travelling Salesman problems testing
    #Used by:
    #Metric Travelling Salesman 2-approximation algorithm
    
    SETUP_NOEDGES_1
    upvar 1 E edges
    
    set edges "edge1 edge2"
    return
}

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

proc SETUP_CREATETGRAPH_3 {E} {

    #Graph object for Metric Travelling Salesman problems testing
    #Used by:
    #Metric Travelling Salesman 2-approximation algorithm
    
    upvar 1 E edges
    struct::graph mygraph
    
    mygraph node insert node1 node2 node3 node4
    mygraph arc insert node1 node2 edge12
    mygraph arc setweight edge12 1
    mygraph arc insert node1 node3 edge13
    mygraph arc setweight edge13 2
    mygraph arc insert node1 node4 edge14
    mygraph arc setweight edge14 3
    mygraph arc insert node4 node1 edge41
    mygraph arc setweight edge41 4
    
    set edges {edge14 edge41 edge13}
    return
    
}

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

proc SETUP_CHRISTO_1 {} {

    #Used by:
    #Christofides Algorithm (Tight Example)

    struct::graph mygraph
    
    mygraph node insert node1 node2 node3 node4 node5 node6 node7
    mygraph arc insert node1 node2 edge12
    mygraph arc insert node1 node3 edge13
    mygraph arc insert node2 node3 edge23
    mygraph arc insert node2 node4 edge24
    mygraph arc insert node3 node4 edge34
    mygraph arc insert node3 node5 edge35
    mygraph arc insert node4 node5 edge45
    mygraph arc insert node4 node6 edge46
    mygraph arc insert node5 node6 edge56
    mygraph arc insert node5 node7 edge57
    mygraph arc insert node6 node7 edge67
    mygraph arc setunweighted 1
    mygraph arc insert node7 node1 edge71
    mygraph arc setunweighted 3
    
    return
}

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

proc SETUP_VC_1 {} {
    
    #Used by:
    #Vertices Cover
    
    struct::graph mygraph
    
    mygraph node insert node1 node2 node3 node4 node5 node6
    mygraph arc insert node1 node2 edge12
    mygraph arc insert node1 node3 edge13
    mygraph arc insert node2 node3 edge23
    mygraph arc insert node3 node4 edge34
    mygraph arc insert node3 node5 edge35
    mygraph arc insert node3 node6 edge36
    
    return
}

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

proc SETUP_VC_1_2 {} {

    #Used by:
    #Vertices Cover
    
    SETUP_VC_1
    
    mygraph arc insert node2 node1 edge21
    mygraph arc insert node3 node1 edge31
    mygraph arc insert node3 node2 edge32
    mygraph arc insert node4 node3 edge43
    mygraph arc insert node5 node3 edge53
    mygraph arc insert node6 node3 edge63
    
    return
}

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

proc SETUP_VC_1_3 {} {

    #Used by:
    #Vertices Cover
    
    SETUP_VC_1
    
    mygraph arc insert node2 node1 edge21
    mygraph arc insert node3 node1 edge31
    mygraph arc insert node3 node2 edge32
    mygraph arc insert node4 node3 edge43
    
    return
}
# -------------------------------------------------------------------------

proc SETUP_VC_2 {} {
    
    #Used by:
    #Vertices Cover
    
    struct::graph mygraph
    
    mygraph node insert node1 node2 node3 node4 node5 node6
    mygraph arc insert node1 node2 edge12
    mygraph arc insert node1 node3 edge13
    mygraph arc insert node2 node3 edge23
    mygraph arc insert node2 node4 edge24
    mygraph arc insert node3 node5 edge35
    mygraph arc insert node4 node5 edge45
    mygraph arc insert node4 node6 edge46
    
    return
}

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

proc SETUP_C5 {} {

    #Cycle with 5 edges - C5
    #Used by:
    #Greedy Maximum Independent Set algorithm
    #Greedy Weighted Maximum Independent Set algorithm
    #Vertices Cover
    
    struct::graph mygraph
    
    mygraph node insert node1 node2 node3 node4 node5
    mygraph arc insert node1 node2
    mygraph arc insert node2 node3
    mygraph arc insert node3 node4
    mygraph arc insert node4 node5
    mygraph arc insert node5 node1
    
    return
}

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

proc SETUP_INDEPENDENTSET_1 {} {
    
    #graph containing 24 nodes for independent set testing
    #Reference: http://en.wikipedia.org/wiki/Independent_set_(graph_theory)#Maximal_independent_set
    #Used by:
    #Greedy Maximum Independent Set algorithm
    #Greedy Weighted Maximum Independent Set algorithm
    
    struct::graph mygraph
    
    #adding 24 nodes: node1 - node24
    for {set i 1} {$i<=24} {incr i} {
	mygraph node insert node$i
    }

    #adding external edges: node1 node2, node2 node3....
    for {set i 1} {$i<=12} {incr i} {
	set j [ expr { $i%12 } ]
	incr j
	mygraph arc insert node$i node$j ;#[list node$i node$j]
    }

    #adding edges connecting internal nodes with external nodes
    for {set i 1} {$i<=12} {incr i} {
	mygraph arc insert node$i node[expr {$i+12}] ;#[list node$i node[expr {$i+12}]]
    }

    #adding edges between internal nodes
    for {set i 13} {$i<=24} {incr i} {
	set u [ expr {($i+4)%24} ]
	set v [ expr {($i-4)%24} ]
	if { $u < 13 } {
	    if {$u == 0} {
		set u 24
	    } else {
		set u [expr {$u+12}]
	    }
	}
	if { $v < 13} {
	    if {$v == 0} {
		set v 24
	    } else {
		set v [expr {$v+12}]
	    }
	}
	
	if { ![mygraph arc exists [list node$u node$i]] } {
	    mygraph arc insert node$i node$u [list node$i node$u]
	}
	if { ![mygraph arc exists [list node$v node$i]] } {
	    mygraph arc insert node$i node$v [list node$i node$v]
	}
    }
    
    return
}

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

proc SETUP_KCENTER_1 {} {
    #Tight Example for unweighted version of K-Center problem
    #Used by:
    #Unweighted k-center 2-approximation algorithm
    #Weighted k-center 3-approximation algorithm
    
    struct::graph mygraph
    mygraph node insert node1 node2 node3 node4 node5 node6 node7
    mygraph arc insert node1 node7 [list node1 node7]
    mygraph arc insert node2 node7 [list node2 node7]
    mygraph arc insert node3 node7 [list node3 node7]
    mygraph arc insert node4 node7 [list node4 node7]
    mygraph arc insert node5 node7 [list node5 node7]
    mygraph arc insert node6 node7 [list node6 node7]
    mygraph arc setunweighted 1

    for {set i 1} {$i < 7 } { incr i } {
	# i in 1..6	
	if { ($i+1) < 7 } {
	    # i in 1..5
	    mygraph arc insert node$i node[ expr { $i+1 } ] [list node$i node[ expr { $i+1 } ]]
	} elseif { ![mygraph arc exists [list node6 node1]] } {
	    mygraph arc insert node6 node1 [list node6 node1]
	}
	
	if { ($i+2) < 7 } {
	    # i in 1..4
	    mygraph arc insert node$i node[ expr { $i+2 } ] [list node$i node[ expr { $i+2 } ]]
	} elseif { ![mygraph arc exists [list node6 node2]] } {
	    mygraph arc insert node6 node2 [list node6 node2]
	}
    }
    mygraph arc insert node1 node5 [list node1 node5]
    mygraph arc setunweighted 2
    
    return
}

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

proc SETUP_KCENTER_2 {} {
    
    #Used by:
    #Unweighted k-center 2-approximation algorithm
    
    struct::graph mygraph 
    
    mygraph node insert node1 node2 node3 node4 node5 node6 node7 node8
    
    foreach v [mygraph nodes] {
	foreach u [mygraph nodes] {
	    if { ($u!=$v) && ![mygraph arc exists [list $u $v]] } {
		mygraph arc insert $v $u [list $v $u]
	    }
	}
    }
    foreach x [mygraph nodes -adj node1] {
	if { [mygraph arc exists [list $x node1]] } {
	    mygraph arc setweight [list $x node1] 1
	} else {
	    mygraph arc setweight [list node1 $x] 1
	}
    }
    foreach x [mygraph nodes -adj node2] {
	if { [mygraph arc exists [list $x node2]] } {
	    mygraph arc setweight [list $x node2] 1
	} else {
	    mygraph arc setweight [list node2 $x] 1
	}
    }
    
    mygraph arc setunweighted 2
    return
}

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

proc SETUP_TWOSQUARED_1 {} {
    
    #Used by:
    #createSquaredGraph procedure
    #Unweighted k-center 2-approximation algorithm (subprocedure that extends two-squared graphs)
    
    struct::graph mygraph
    
    mygraph node insert node1 node2 node3 node4 node5 node6 node7 node8
    mygraph arc insert node1 node2 "node1 node2"
    mygraph arc insert node2 node3 "node2 node3"
    mygraph arc insert node2 node4 "node2 node4"
    mygraph arc insert node3 node4 "node3 node4"
    mygraph arc insert node3 node5 "node3 node5"
    mygraph arc insert node5 node6 "node5 node6"
    mygraph arc insert node5 node7 "node5 node7"
    mygraph arc insert node7 node8 "node7 node8"
    
    return
}

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

proc SETUP_TWOSQUARED_2 {} {
    
    #Used by:
    #createSquaredGraph procedure
    #Unweighted k-center 2-approximation algorithm (subprocedure that extends two-squared graphs)
    
    struct::graph mygraph
    
    mygraph node insert node1 node2 node3 node4 node5
    mygraph arc insert node1 node2 "node1 node2"
    mygraph arc insert node2 node3 "node2 node3"
    mygraph arc insert node3 node4 "node3 node4"
    mygraph arc insert node4 node5 "node4 node5"
    
    return
}

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

proc SETUP_TWOSQUARED_3 {} {

    #Used by:
    #Unweighted k-center 2-approximation algorithm (subprocedure that extends two-squared graphs)
    
    struct::graph mygraph2
    
    mygraph2 node insert node1 node2 node3 node4 node5
    mygraph2 arc insert node1 node2 "node1 node2"
    mygraph2 arc insert node2 node3 "node2 node3"
    mygraph2 arc insert node3 node4 "node3 node4"
    mygraph2 arc insert node1 node3 "node1 node3"
    mygraph2 arc insert node2 node4 "node2 node4"
    
    return
}

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

proc SETUP_TWOSQUARED_4 {} {

    #Used by:
    #Unweighted k-center 2-approximation algorithm (subprocedure that extends two-squared graphs)
    
    struct::graph mygraph2
    
    mygraph2 node insert node1 node2 node3 node4 node5 node6 node7 node8
    
    mygraph2 arc insert node1 node2 "node1 node2"
    mygraph2 arc insert node1 node3 "node1 node3"
    mygraph2 arc insert node1 node4 "node1 node4"
    mygraph2 arc insert node2 node3 "node2 node3"
    mygraph2 arc insert node2 node4 "node2 node4"
    mygraph2 arc insert node3 node4 "node3 node4"
    
    mygraph2 arc insert node5 node6 "node5 node6"
    mygraph2 arc insert node5 node7 "node5 node7"
    mygraph2 arc insert node5 node8 "node5 node8"
    mygraph2 arc insert node6 node7 "node6 node7"
    mygraph2 arc insert node7 node8 "node7 node8"
    
    return
}

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

proc SETUP_WEIGHTEDKCENTER_1 {nodeWeights} {

    #Used by:
    #Weighted k-center 3-approximation algorithm
    
    upvar 1 nodeWeights nW
    struct::graph mygraph
    
    mygraph node insert node1 node2 node3 node4 node5 node6 node7 node8
    mygraph arc insert node1 node2
    mygraph arc insert node2 node3
    mygraph arc insert node3 node4
    mygraph arc setunweighted 1
    mygraph arc insert node4 node5
    mygraph arc insert node4 node6
    mygraph arc insert node4 node7
    mygraph arc insert node4 node8
    mygraph arc setunweighted 1.5
    
    set nW {{node1 2} {node2 2} {node3 2} {node4 1} {node5 Inf} {node6 Inf} {node7 Inf} {node8 Inf}}
    
    return
}

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

proc SETUP_WEIGHTEDKCENTER_2 {nodeWeights} {

    #Used by:
    #Weighted k-center 3-approximation algorithm
    
    upvar 1 nodeWeights nW
    
    struct::graph mygraph
    
    mygraph node insert node1 node2 node3 node4 node5 node6
    mygraph arc insert node1 node6
    mygraph arc insert node2 node6
    mygraph arc insert node3 node6
    
    mygraph arc insert node5 node6
    mygraph arc insert node1 node5
    mygraph arc insert node2 node5
    mygraph arc insert node3 node5
    mygraph arc setunweighted 1
        
    mygraph arc insert node4 node5
    mygraph arc setunweighted 3
    mygraph arc insert node4 node6
    mygraph arc setunweighted 2
    
    set nW {{node1 2} {node2 2} {node3 2} {node4 3} {node5 2} {node6 1}}
    
    return
}

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

proc SETUP_WEIGHTEDKCENTER_3 {nodeWeights} {
    
    #Used by:
    #Weighted k-center 3-approximation algorithm
    
    SETUP_WEIGHTEDKCENTER_2 n
    
    upvar 1 nodeWeights nW
    
    set nW {{node1 1} {node2 1} {node3 1} {node4 1} {node5 1} {node6 3}}
    
    return
}

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

proc SETUP_FORDFULKERSON_1 {} {

    #The flow network with througputs set for each existing (non-zero) link
    #Used by:
    #Edmond's Karp algorithm
    #Create Residual Graph procedure (subprocedure of Edmond's Karp)
    #Dinic's Algorithm for maximum flow computation
    #Subprocedures of above: MKM and Dinic's algorithms for blocking flow finding
    
    struct::graph mygraph
    
    mygraph node insert s v1 v2 v3 v4 t
    
    mygraph arc insert s v1 {s v1}
    mygraph arc set {s v1} throughput 16
    
    mygraph arc insert s v2 {s v2}
    mygraph arc set {s v2} throughput 13
    
    mygraph arc insert v1 v2 {v1 v2}
    mygraph arc set {v1 v2} throughput 10
    
    mygraph arc insert v2 v1 {v2 v1}
    mygraph arc set {v2 v1} throughput 4
    
    mygraph arc insert v1 v3 {v1 v3}
    mygraph arc set {v1 v3} throughput 12
    
    mygraph arc insert v2 v4 {v2 v4}
    mygraph arc set {v2 v4} throughput 14
    
    mygraph arc insert v3 v2 {v3 v2}
    mygraph arc set {v3 v2} throughput 9
    
    mygraph arc insert v3 t {v3 t}
    mygraph arc set {v3 t} throughput 20
    
    mygraph arc insert v4 v3 {v4 v3}
    mygraph arc set {v4 v3} throughput 7
    
    mygraph arc insert v4 t {v4 t}
    mygraph arc set {v4 t} throughput 4

    return
    
}

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

proc SETUP_FORDFULKERSON_2 {} {

    #The flow network with througputs set for each existing (non-zero) link
    #Used by:
    #Edmond's Karp algorithm (Tight Example)
    #Dinic's Algorithm for maximum flow computation
    #Subprocedures of above: MKM and Dinic's algorithms for blocking flow finding
    
    struct::graph mygraph
    
    mygraph node insert a b c d
    
    mygraph arc insert a b ab
    mygraph arc set ab throughput 1000000
    mygraph arc insert a c ac
    mygraph arc set ac throughput 1000000
    mygraph arc insert b d bd
    mygraph arc set bd throughput 1000000
    mygraph arc insert c d cd
    mygraph arc set cd throughput 1000000
    mygraph arc insert b c bc 
    mygraph arc set bc throughput 1
    
    return

}

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

proc SETUP_FORDFULKERSON_3 {} {

    #The flow network with througputs set for each existing (non-zero) link
    #Used by:
    #Edmond's Karp algorithm
    #Dinic's Algorithm for maximum flow computation
    #Subprocedures of above: MKM and Dinic's algorithms for blocking flow finding
    
    struct::graph mygraph
    
    mygraph node insert s v1 v2 v3 t
    
    mygraph arc insert s v1 sv1
    mygraph arc set sv1 throughput 10
    
    mygraph arc insert s v2 sv2
    mygraph arc set sv2 throughput 5
    
    mygraph arc insert s v3 sv3
    mygraph arc set sv3 throughput 3
    
    mygraph arc insert v1 v2 v1v2
    mygraph arc set v1v2 throughput 4
    
    mygraph arc insert v2 v1 v2v1
    mygraph arc set v2v1 throughput 2
    
    mygraph arc insert v2 v2 v2v3
    mygraph arc set v2v3 throughput 2
    
    mygraph arc insert v3 v2 v3v2
    mygraph arc set v3v2 throughput 4
    
    mygraph arc insert v1 t v1t
    mygraph arc set v1t throughput 3
    
    mygraph arc insert v2 t v2t
    mygraph arc set v2t throughput 8
    
    mygraph arc insert v3 t v3t
    mygraph arc set v3t throughput 10
    
    return
}

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

proc SETUP_FORDFULKERSON_4 {} {

    #The flow network with througputs set for each existing (non-zero) link
    #Used by:
    #Edmond's Karp algorithm
    #Dinic's Algorithm for maximum flow computation
    #Subprocedures of above: MKM and Dinic's algorithms for blocking flow finding
    
    SETUP_FORDFULKERSON_3
    
    mygraph arc set v1v2 throughput 1
    mygraph arc set v2v1 throughput 1
    mygraph arc set v2v3 throughput 1
    mygraph arc set v3v2 throughput 1
    
    return
}

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

proc SETUP_FORDFULKERSON_5 {} {
    #The flow network with througputs set for each existing (non-zero) link
    #Used by:
    #Edmond's Karp algorithm
    #Dinic's Algorithm for maximum flow computation
    #Subprocedures of above: MKM and Dinic's algorithms for blocking flow finding
    
    SETUP_FORDFULKERSON_3
    
    mygraph arc setweight sv1 10.5
    mygraph arc set sv1 throughput 10.5
    mygraph arc set sv2 throughput 5.5
    mygraph arc set sv3 throughput 3.5
    mygraph arc set v1v2 throughput 4.5
    mygraph arc set v2v1 throughput 2.5
    mygraph arc set v2v3 throughput 2.3
    mygraph arc set v3v2 throughput 4.2
    mygraph arc set v1t throughput 3.1
    mygraph arc set v2t throughput 8.9
    mygraph arc set v3t throughput 10.1
    
    return
}

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

proc SETUP_FLOWS_0 {mygraph} {
    
    #Used by:
    #Create Residual Graph procedure (subprocedure of Edmond's Karp)
    
    foreach arc [$mygraph arcs] {
	set u [$mygraph arc source $arc]
	set v [$mygraph arc target $arc]
	dict set f [list $u $v] 0
	dict set f [list $v $u] 0
    }
    
    return $f
}

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

proc SETUP_FLOWS_1 {mygraph} {

    #Used by:
    #Create Residual Graph procedure (subprocedure of Edmond's Karp)
    
    set f [SETUP_FLOWS_0 $mygraph]
    
    dict set f [list s v1] 4
    dict set f [list v1 v3] 4
    dict set f [list v3 v2] 4
    dict set f [list v2 v4] 4
    dict set f [list v4 t] 4
    
    return $f
}

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

proc SETUP_FLOWS_2 {mygraph} {

    #Used by:
    #Create Residual Graph procedure (subprocedure of Edmond's Karp)
    
    set f [SETUP_FLOWS_0 $mygraph]
    
    dict set f [list s v1] 11
    dict set f [list v1 v3] 4
    dict set f [list v3 v2] 4
    dict set f [list v2 v4] 11
    dict set f [list v4 t] 4
    
    dict set f [list v1 v2] 7
    dict set f [list v4 v3] 7
    dict set f [list v3 t] 7
    
    
    return $f
}

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

proc SETUP_FLOWS_3 {mygraph} {
    
    #Used by:
    #Create Residual Graph procedure (subprocedure of Edmond's Karp)
    
    set f [SETUP_FLOWS_0 $mygraph]
    
    dict set f [list s v1] 11
    dict set f [list s v2] 8
    dict set f [list v2 v1] 1
    dict set f [list v1 v3] 12
    dict set f [list v2 v4] 11
    dict set f [list v3 v2] 4
    dict set f [list v4 v3] 7
    dict set f [list v3 t] 15
    dict set f [list v4 t] 4
    
    return $f
}

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

proc SETUP_FLOWS_4 {mygraph} {

    #Used by:
    #Create Residual Graph procedure (subprocedure of Edmond's Karp)
    
    set f [SETUP_FLOWS_0 $mygraph]
    
    dict set f [list s v1] 11
    dict set f [list s v2] 12
    dict set f [list v2 v1] 1
    dict set f [list v1 v3] 12
    dict set f [list v2 v4] 11
    dict set f [list v4 v3] 7
    dict set f [list v3 t] 19
    dict set f [list v4 t] 4
    
    return $f
}

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

proc SETUP_AUGMENTINGNETWORK_1 {_f _path} {
    
    #Used by:
    #Create Augmenting Network procedure (subprocedure of Busacker-Gowen's Algorithm)
    
    upvar 1 $_f f $_path path
    
    struct::graph mygraph 
    
    mygraph node insert s a b c t
    
    mygraph arc insert s a [list s a]
    mygraph arc set [list s a] throughput 18
    mygraph arc set [list s a] cost 3
    
    mygraph arc insert s c [list s c]
    mygraph arc set [list s c] throughput 20
    mygraph arc set [list s c] cost 8
    
    mygraph arc insert a b [list a b]
    mygraph arc set [list a b] throughput 20
    mygraph arc set [list a b] cost 5
    
    mygraph arc insert a c [list a c]
    mygraph arc set [list a c] throughput 15
    mygraph arc set [list a c] cost 4
    
    mygraph arc insert c b [list c b]
    mygraph arc set [list c b] throughput 12
    mygraph arc set [list c b] cost 8
    
    mygraph arc insert b t [list b t]
    mygraph arc set [list b t] throughput 14
    mygraph arc set [list b t] cost 5
    
    mygraph arc insert c t [list c t]
    mygraph arc set [list c t] throughput 17
    mygraph arc set [list c t] cost 3
    
    set path {}
    lappend path s a c t
    
    foreach e [mygraph arcs] {
	set u [mygraph arc source $e]
	set v [mygraph arc target $e]
	dict set f [list $u $v] 0
	dict set f [list $v $u] 0
    }
    
    dict set f [list s a] 15
    dict set f [list a c] 15
    dict set f [list c t] 15
    
    return	
}

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

proc SETUP_AUGMENTINGNETWORK_2 {_f _path} {
    
    #Used by:
    #Create Augmenting Network procedure (subprocedure of Busacker-Gowen's Algorithm)
    
    upvar 1 $_f f $_path path
    
    SETUP_AUGMENTINGNETWORK_1 f path
    
    #mygraph arc insert s a [list s a]
    mygraph arc set [list s a] throughput 3
    mygraph arc set [list s a] cost 3
    
    mygraph arc insert a s [list a s]
    mygraph arc set [list a s] throughput 15
    mygraph arc set [list a s] cost -3
    
    mygraph arc insert c a [list c a]
    mygraph arc set [list c a] throughput 15
    mygraph arc set [list c a] cost -4
    
    mygraph arc set [list a c] throughput 0
    mygraph arc set [list a c] cost Inf
    
    #mygraph arc insert c t [list c t]
    mygraph arc set [list c t] throughput 2
    mygraph arc set [list c t] cost 3
    
    mygraph arc insert t c [list t c]
    mygraph arc set [list t c] throughput 15
    mygraph arc set [list t c] cost -3
    
    set path {}
    lappend path s c t
    
    dict set f [list s a] 15
    dict set f [list a c] 15
    dict set f [list c t] 17
    dict set f [list s c] 2
    
    return	
}

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

proc SETUP_AUGMENTINGNETWORK_3 {_f _path} {
    
    #Used by:
    #Create Augmenting Network procedure (subprocedure of Busacker-Gowen's Algorithm)
    
    upvar 1 $_f f $_path path
    
    SETUP_AUGMENTINGNETWORK_2 f path
    
    mygraph arc set [list c t] throughput 0
    mygraph arc set [list c t] cost Inf
    
    mygraph arc set [list t c] throughput 17
    mygraph arc set [list t c] cost -3
    
    mygraph arc set [list s c] throughput 18
    mygraph arc set [list s c] cost 8
    
    mygraph arc insert c s [list c s]
    mygraph arc set [list c s] throughput 2
    mygraph arc set [list c s] cost -8
    
    set path {}
    lappend path s a b t
    
    dict set f [list s a] 18
    dict set f [list a c] 15
    dict set f [list c t] 17
    dict set f [list s c] 2
    dict set f [list a b] 3
    dict set f [list b t] 3
    
    return	
}

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

proc SETUP_BUSACKERGOWEN_1 {} {

    #Used by:
    #Busacker Gowen Algorithm
    
    struct::graph mygraph
    
    mygraph node insert s a b c t
    
    mygraph arc insert s a sa
    mygraph arc setweight sa 3
    mygraph arc set sa cost 3
    mygraph arc set sa throughput 18
    
    mygraph arc insert s c sc
    mygraph arc setweight sc 8
    mygraph arc set sc cost 8
    mygraph arc set sc throughput 20
    
    mygraph arc insert a b ab
    mygraph arc setweight ab 5
    mygraph arc set ab cost 5
    mygraph arc set ab throughput 20
    
    mygraph arc insert a c ac
    mygraph arc setweight ac 4
    mygraph arc set ac cost 4
    mygraph arc set ac throughput 15
    
    mygraph arc insert c b cb
    mygraph arc setweight cb 8
    mygraph arc set cb cost 8
    mygraph arc set cb throughput 12
    
    mygraph arc insert b t bt
    mygraph arc setweight bt 5
    mygraph arc set bt cost 5
    mygraph arc set bt throughput 14
    
    mygraph arc insert c t ct
    mygraph arc setweight ct 3	
    mygraph arc set ct cost 3
    mygraph arc set ct throughput 17

    return
}

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

proc SETUP_BUSACKERGOWEN_2 {} {
    #graph with not all attributes set
    
    #Used by:
    #Busacker Gowen Algorithm
    #Edmond's Karp Algorithm
    
    struct::graph mygraph
    
    mygraph node insert s v1 v2 t
    mygraph arc insert v1 s v1s
    
    mygraph arc insert v2 s v2s
    mygraph arc insert v1 t v1t
    mygraph arc set v1t throughput 20
    mygraph arc set v1t cost 5
    mygraph arc insert v2 t v2t
    mygraph arc set v2t throughput 20
    mygraph arc set v2t cost 5

    return
}
# -------------------------------------------------------------------------

proc SETUP_SOURCESINKNOPATHS {} {
    #graph where from the start path between source node s and 
    #sink node t doesn't exist
    #Used by Busacker - Gowen
    
    struct::graph mygraph
    
    mygraph node insert s v1 v2 t
    mygraph arc insert v1 s v1s
    mygraph arc set v1s throughput 20
    mygraph arc set v1s cost 5
    mygraph arc insert v2 s v2s
    mygraph arc set v2s throughput 20
    mygraph arc set v2s cost 5
    mygraph arc insert v1 t v1t
    mygraph arc set v1t throughput 20
    mygraph arc set v1t cost 5
    mygraph arc insert v2 t v2t
    mygraph arc set v2t throughput 20
    mygraph arc set v2t cost 5
    
    return
}

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

proc SETUP_MDST_1 {} {

    #Used by:
    #Minimum Diameter Spanning Tree Algorithm
    #BFS algorithm
    
    struct::graph mygraph
    
    mygraph node insert a b c d e f g h i j

    mygraph arc insert a b
    mygraph arc insert b c
    mygraph arc insert c d
    mygraph arc insert d e
    mygraph arc insert e f
    mygraph arc insert b h
    mygraph arc insert c g
    mygraph arc insert d h
    mygraph arc insert e g
    mygraph arc insert g i
    mygraph arc insert h j

    return
}

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

proc SETUP_MDST_2 {} {

    #Used by:
    #Minimum Degree Spanning Tree Tests
    
    struct::graph mygraph
    
    mygraph node insert v1 v2 v3 v4 v5 v6 v7 v8
    mygraph arc insert v1 v2 12
    mygraph arc insert v1 v3 13
    mygraph arc insert v2 v4 24
    mygraph arc insert v3 v4 34
    mygraph arc insert v3 v5 35
    mygraph arc insert v4 v5 45
    mygraph arc insert v5 v6 56
    mygraph arc insert v5 v7 57
    mygraph arc insert v7 v8 78
    mygraph arc insert v6 v8 68
    
    return
}

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

proc SETUP_MDST_3 {} {

    #Used by:
    #Minimum Diameter Spanning Tree Algorithm
    
    struct::graph mygraph
    
    mygraph node insert a b c d e
    mygraph arc insert a b ab
    mygraph arc insert b c bc
    mygraph arc insert c d cd
    mygraph arc insert d e de
    
    return
}

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

proc SETUP_MDST_4 {} {

    #Used by:
    #Minimum Diameter Spanning Tree Algorithm
    
    SETUP_MDST_3
    
    mygraph node insert f g
    mygraph arc insert e f ef
    mygraph arc insert f g fg
    mygraph arc insert d g dg
    
    return
}

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

proc SETUP_MDST_5 {} {

    #Used by:
    #Minimum Diameter Spanning Tree Algorithm
    
    struct::graph mygraph
    mygraph node insert a b c d e
    mygraph arc insert a b ab
    mygraph arc insert b c bc
    mygraph arc insert c d cd
    mygraph arc insert d e de
    mygraph arc insert a c ac
    mygraph arc insert b d bd
    mygraph arc insert c e ce
    
    return
}

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

proc SETUP_MDST_6 {} {

    #Used by:
    #Minimum Degree Spanning Tree Tests
    
    struct::graph mygraph
    
    mygraph node insert a b c d e f g
    mygraph arc insert a b ab
    mygraph arc insert b c bc
    mygraph arc insert c d cd
    mygraph arc insert d e de
    mygraph arc insert e f ef
    mygraph arc insert f a fa
    mygraph arc insert g a ga
    mygraph arc insert g b gb
    mygraph arc insert g c gc
    mygraph arc insert g d gd
    mygraph arc insert g e ge
    mygraph arc insert g f gf
    
    return	
}

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

proc SETUP_MDST_7 {} {
    
    #Used by:
    #Minimum Degree Spanning Tree Tests
    
    struct::graph mygraph
    
    mygraph node insert a b c d e f
    mygraph arc insert a b ab
    mygraph arc insert a c ac
    mygraph arc insert b d bd
    mygraph arc insert c e ce
    mygraph arc insert d f df
    mygraph arc insert e f ef
    mygraph arc insert b e be
    mygraph arc insert c d cd
    mygraph arc insert a f af
    mygraph arc insert f a fa
    mygraph arc insert b c bc
    mygraph arc insert d e de
    
    return
}

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

proc SETUP_BLOCKINGFLOW_1 {} {

    #Residual graph for blocking flow testing
    #Used by:
    #Dinic's Blocking Flow Algorithm
    #MKM (3 Hindu) Blocking Flow Algorithm
    
    struct::graph mygraph
    
    mygraph node insert s v1 v2 v3 v4 v5 v6 v7 t

    mygraph arc insert s v1 sv1
    mygraph arc set sv1 throughput 4
    mygraph arc insert s v3 sv3
    mygraph arc set sv3 throughput 2
    mygraph arc insert v1 v2 v1v2
    mygraph arc set v1v2 throughput 3
    mygraph arc insert v1 v4 v1v4
    mygraph arc set v1v4 throughput 1
    mygraph arc insert v2 v5 v2v5
    mygraph arc set v2v5 throughput 2
    mygraph arc insert v3 v4 v3v4
    mygraph arc set v3v4 throughput 1
    mygraph arc insert v3 v6 v3v6
    mygraph arc set v3v6 throughput 3
    mygraph arc insert v4 v1 v4v1
    mygraph arc set v4v1 throughput 1
    mygraph arc insert v4 v5 v4v5
    mygraph arc set v4v5 throughput 2
    mygraph arc insert v4 v7 v4v7
    mygraph arc set v4v7 throughput 2
    mygraph arc insert v4 v6 v4v6
    mygraph arc set v4v6 throughput 1
    mygraph arc insert v5 v1 v5v1
    mygraph arc set v5v1 throughput 3
    mygraph arc insert v5 t v5t
    mygraph arc set v5t throughput 3
    mygraph arc insert v6 v4 v6v4
    mygraph arc set v6v4 throughput 3
    mygraph arc insert v6 v7 v6v7
    mygraph arc set v6v7 throughput 4
    mygraph arc insert v7 t v7t
    mygraph arc set v7t throughput 2
    mygraph arc insert t v7 tv7
    mygraph arc set tv7 throughput 3

    return
}

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

proc SETUP_BLOCKINGFLOW_2 {} {
    
    #residual graph for blocking flow testing
    #Used by:
    #Dinic's Blocking Flow Algorithm
    #MKM (3 Hindu) Blocking Flow Algorithm
    
    struct::graph mygraph 
    
    mygraph node insert s v1 v2 v3 v4 t
    
    mygraph arc insert s v2 sv2
    mygraph arc set sv2 throughput 6
    mygraph arc insert v2 s v2s
    mygraph arc set v2s throughput 4
    mygraph arc insert v1 s v1s
    mygraph arc set v1s throughput 10
    mygraph arc insert v1 v2 v1v2
    mygraph arc set v1v2 throughput 2
    mygraph arc insert v1 v4 v1v4 
    mygraph arc set v1v4 throughput 2
    mygraph arc insert v2 v4 v2v4
    mygraph arc set v2v4 throughput 5
    mygraph arc insert v3 v1 v3v1
    mygraph arc set v3v1 throughput 4
    mygraph arc insert v3 t v3t
    mygraph arc set v3t throughput 6
    mygraph arc insert v4 v1 v4v1
    mygraph arc set v4v1 throughput 6
    mygraph arc insert v4 v2 v4v2
    mygraph arc set v4v2 throughput 4
    mygraph arc insert v4 v3 v4v3
    mygraph arc set v4v3 throughput 6
    mygraph arc insert t v4 tv4
    mygraph arc set tv4 throughput 10
    mygraph arc insert t v3 tv3
    mygraph arc set tv3 throughput 4
    
    return
}

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

proc SETUP_BLOCKINGFLOW_3 {} {
    
    #residual graph for blocking flow testing
    #Used by:
    #Dinic's Blocking Flow Algorithm
    #MKM (3 Hindu) Blocking Flow Algorithm
    
    struct::graph mygraph 
    
    mygraph node insert s v1 v2 v3 v4 t
    
    mygraph arc insert v2 s v2s
    mygraph arc set v2s throughput 10
    mygraph arc insert v1 s v1s
    mygraph arc set v1s throughput 10
    mygraph arc insert v1 v2 v1v2
    mygraph arc set v1v2 throughput 2
    mygraph arc insert v1 v4 v1v4 
    mygraph arc set v1v4 throughput 2
    mygraph arc insert v3 v1 v3v1
    mygraph arc set v3v1 throughput 4
    mygraph arc insert v3 t v3t
    mygraph arc set v3t throughput 1
    mygraph arc insert v3 v4 v3v4
    mygraph arc set v3v4 throughput 5
    mygraph arc insert v4 v1 v4v1
    mygraph arc set v4v1 throughput 6
    mygraph arc insert v4 v2 v4v2
    mygraph arc set v4v2 throughput 9
    mygraph arc insert v4 v3 v4v3
    mygraph arc set v4v3 throughput 1
    mygraph arc insert t v4 tv4
    mygraph arc set tv4 throughput 10
    mygraph arc insert t v3 tv3
    mygraph arc set tv3 throughput 9
    
    return
}

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

proc SETUP_MAXIMUMFLOW_1 {} {

    #Flow network for maximum flow computation problems and generally flow problems.
    #Used by:
    #Dinic's Maximum Flow Algorithm
    #Dinic's Blocking Flow Algorithm
    #MKM (3 Hindu) Blocking Flow Algorithm
    
    struct::graph mygraph
    
    mygraph node insert s v1 v2 v3 v4 t

    mygraph arc insert s v1 sv1
    mygraph arc set sv1 throughput 10
    mygraph arc insert s v2 sv2
    mygraph arc set sv2 throughput 10
    mygraph arc insert v1 v2 v1v2
    mygraph arc set v1v2 throughput 2
    mygraph arc insert v2 v4 v2v4
    mygraph arc set v2v4 throughput 9
    mygraph arc insert v1 v4 v1v4
    mygraph arc set v1v4 throughput 8
    mygraph arc insert v1 v3 v1v3
    mygraph arc set v1v3 throughput 4
    mygraph arc insert v4 v3 v4v3
    mygraph arc set v4v3 throughput 6
    mygraph arc insert v3 t v3t
    mygraph arc set v3t throughput 10
    mygraph arc insert v4 t v4t
    mygraph arc set v4t throughput 10
    
    return
}

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

proc SETUP_BFS_1 {} {
    
    #Used by:
    #BFS algorithm
    #Shortest Pathfinding by BFS algorithm
    
    struct::graph mygraph
    mygraph node insert s a b c d x

    mygraph arc insert s a sa
    mygraph arc setweight sa 4
    mygraph arc insert s x sx
    mygraph arc setweight sx 5
    mygraph arc insert a b ab
    mygraph arc setweight ab 5
    mygraph arc insert x d xd
    mygraph arc setweight xd 7
    mygraph arc insert x a xa
    mygraph arc setweight xa -3
    mygraph arc insert b d bd
    mygraph arc setweight bd 2
    mygraph arc insert b c bc
    mygraph arc setweight bc 6

    return
}

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

proc SETUP_BFS_2 {} {

    #Used by:
    #BFS algorithm
    #Shortest Pathfinding by BFS algorithm
    
    struct::graph mygraph
    mygraph node insert s a b c d t
    
    mygraph arc insert s d sd
    mygraph arc setweight sd 9
    mygraph arc insert s a sa
    mygraph arc setweight sa 15
    mygraph arc insert a c ac
    mygraph arc setweight ac 3
    mygraph arc insert a b ab
    mygraph arc setweight ab 35
    mygraph arc insert b a ba
    mygraph arc setweight ba 16
    mygraph arc insert b c bc
    mygraph arc setweight bc 6
    mygraph arc insert b t bt
    mygraph arc setweight bt 21
    mygraph arc insert c t ct
    mygraph arc setweight ct 7
    mygraph arc insert c d cd
    mygraph arc setweight cd 2
    mygraph arc insert d c dc
    mygraph arc setweight dc 2
    mygraph arc insert d a da
    mygraph arc setweight da 4
    mygraph arc insert t b tb 
    mygraph arc setweight tb 5
    
    return
}

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

proc SETUP_TSPHEURISTIC_1 {C} {

    #Used by:
    #TSP heuristics of local searching - 2 approximation algorithm
    upvar $C _C
    
    struct::graph mygraph
    mygraph node insert a b c d e

    mygraph arc insert a b ab
    mygraph arc set ab weight 11
    mygraph arc insert a c ac
    mygraph arc set ac weight 16
    mygraph arc insert a d ad
    mygraph arc set ad weight 28
    mygraph arc insert a e ae
    mygraph arc set ae weight 42
    mygraph arc insert b c bc
    mygraph arc set bc weight 44
    mygraph arc insert b d bd
    mygraph arc set bd weight 31
    mygraph arc insert b e be
    mygraph arc set be weight 27
    mygraph arc insert c d cd
    mygraph arc set cd weight 6
    mygraph arc insert c e ce
    mygraph arc set ce weight 15
    mygraph arc insert d e de
    mygraph arc set de weight 21

    set _C {ab bc cd de ae}
    
    return
}

# -------------------------------------------------------------------------
# Generators for various error messages generated
# by the implementations.

proc NegativeCycleOccurance { g } { return "Error. Given graph \"mygraph\" contains cycle with negative sum of weights." }
proc UnweightedArcOccurance { } { return "Operation invalid for graph with unweighted arcs." }
proc LackOfEdgesOccurance {G e} { return "Edge \"$e\" doesn't exist in graph \"mygraph\". Set the proper set of edges." }
proc UnconnectedGraphOccurance {G} { return "Error. Given graph \"mygraph\" is not a connected graph." }
proc WrongValueAtInput {x} { return "The \"$x\" value must be an positive integer." }
proc LackOfSinkOrSource {s t} { return "Nodes \"$s\" and \"$t\" should be contained in graph's G set of nodes" }
proc WrongAttributes {args} {
    set    message "The input network doesn't have all attributes set correctly... Please, check again attributes: "
    append message "\"[join $args "\" and \""]\""
    return "$message for input graph."
}
@


1.12
log
@
	* graphops.tcl (::struct::graph::op::WeightedKCenter): Fixed
	* graphops.man: object leak. Added the missing release of the
	* pkgIndex.tcl: Gi(SQ) in error case (no solution). Bumped
	* graphops.test: version to 0.11.3. Tweaked comment in testsuite
	  regarding repetition.

	* graph/tests/XOpsControl: Added testsuite for weighted k-center.
	* graph/tests/ops/weightedkcenter.test: Testsuite for weighted k-center.
	  Changes compared to GSoC result:
	  - Test names extended with 'treeimpl'.
	  - Indentation, line-endings
	  - Several tests demonstrates how the result is influenced by
	    node/arc ordering. Extended to accept the variations.
	  This passes the testsuite for both tcl and critcl
	  implementations of struct::graph.
	* graph/tests/ops/kcenter.test: Moved the custom matcher/verifier for
	* graph/tests/XOpsSupport: max-independent-set to shared file.
	* graph/tests/XOpsSetup: Simplified some setup procedures a bit.
@
text
@d7 1
a7 1
# RCS: @@(#) $Id: XOpsSetup,v 1.11 2009/09/22 20:30:53 andreas_kupries Exp $
d17 1
a17 1
    graph mygraph
d89 1
a89 1
    graph mygraph
d122 1
a122 1
    graph mygraph
d150 1
a150 1
    graph mygraph
d182 1
a182 1
    graph mygraph
d218 1
a218 1
    graph mygraph	
d272 1
a272 1
    graph mygraph
d308 1
a308 1
    graph mygraph
d344 1
a344 1
    graph mygraph
d370 1
a370 1
    graph mygraph
d393 1
a393 1
    graph mygraph
d418 1
a418 1
    graph mygraph
d447 1
a447 1
    graph mygraph
d464 1
a464 1
    graph mygraph
d488 1
a488 1
    graph mygraph
d518 1
a518 1
    graph mygraph
d541 1
a541 1
    graph mygraph
d582 1
a582 1
    graph mygraph
d604 1
a604 1
    graph mygraph
d630 1
a630 1
    graph mygraph
d664 1
a664 1
    graph mygraph
d707 1
a707 1
    graph mygraph
d730 1
a730 1
    graph mygraph
d768 1
a768 1
    graph mygraph
d807 1
a807 1
    graph mygraph
d835 1
a835 1
    graph mygraph
d876 1
a876 1
    graph mygraph 
d937 1
a937 1
    graph mygraph
d977 1
a977 1
    graph mygraph
d998 1
a998 1
    graph mygraph
d1030 1
a1030 1
    graph mygraph 
d1057 1
a1057 1
    graph mygraph
d1089 1
a1089 1
    graph mygraph
d1108 1
a1108 1
    graph mygraph
d1126 1
a1126 1
    graph mygraph
d1147 1
a1147 1
    graph mygraph
d1170 1
a1170 1
    graph mygraph
d1194 1
a1194 1
    graph mygraph
d1215 1
a1215 1
    graph mygraph
d1238 1
a1238 1
    graph mygraph
d1309 1
a1309 1
    graph mygraph
d1350 1
a1350 1
    graph mygraph
d1374 1
a1374 1
    graph mygraph
d1402 1
a1402 1
    graph mygraph
d1457 1
a1457 1
    graph mygraph
d1481 1
a1481 1
    graph mygraph
d1503 1
a1503 1
    graph mygraph
d1560 1
a1560 1
    graph mygraph
d1599 1
a1599 1
    graph mygraph 
d1637 1
a1637 1
    graph mygraph
d1660 1
a1660 1
    graph mygraph
d1678 1
a1678 1
    graph mygraph2
d1697 1
a1697 1
    graph mygraph2
d1725 1
a1725 1
    graph mygraph
d1752 1
a1752 1
    graph mygraph
d1802 1
a1802 1
    graph mygraph
d1850 1
a1850 1
    graph mygraph
d1879 1
a1879 1
    graph mygraph
d2072 1
a2072 1
    graph mygraph 
d2210 1
a2210 1
    graph mygraph
d2261 1
a2261 1
    graph mygraph
d2283 1
a2283 1
    graph mygraph
d2310 1
a2310 1
    graph mygraph
d2336 1
a2336 1
    graph mygraph
d2360 1
a2360 1
    graph mygraph
d2395 1
a2395 1
    graph mygraph
d2415 1
a2415 1
    graph mygraph
d2441 1
a2441 1
    graph mygraph
d2469 1
a2469 1
    graph mygraph
d2520 1
a2520 1
    graph mygraph 
d2563 1
a2563 1
    graph mygraph 
d2605 1
a2605 1
    graph mygraph
d2639 1
a2639 1
    graph mygraph
d2668 1
a2668 1
    graph mygraph
d2707 1
a2707 1
    graph mygraph
@


1.11
log
@
	* graph/tests/XOpsControl: Added testsuite for k-center.
	* graph/tests/ops/kcenter.test: Testsuite for k-center.
	  Changes compared to GSoC result:
	  - Test names extended with 'treeimpl'.
	  - Indentation, line-endings
	  - Several tests demonstrates how the result is influenced by
	    node ordering. Extended to accept the variations.
	  - Custom matcher/verifier for max-independent-set.
	  Note: SETUP_KCENTER_1 is not creating a complete graph,
	  violating the pre-conditions of the algorithm. This affects test
	  cases 1.3 - 1.6, it is not clear if their results are correct in
	  general.
	  This passes the testsuite for both tcl and critcl
	  implementations of struct::graph.
	* graph/tests/XOpsSetup: Re-indented, some notes added, loop
	  conditions tweaked.
@
text
@d7 1
a7 1
# RCS: @@(#) $Id: XOpsSetup,v 1.10 2009/09/21 23:48:03 andreas_kupries Exp $
d1738 1
a1738 2
    set nW {}
    lappend nW {node1 2} {node2 2} {node3 2} {node4 1} {node5 Inf} {node6 Inf} {node7 Inf} {node8 Inf}
d1764 1
a1764 2
    
    
d1770 1
a1770 3
    
    set nW {}
    lappend nW {node1 2} {node2 2} {node3 2} {node4 3} {node5 2} {node6 1}
d1786 1
a1786 2
    set nW {}
    lappend nW {node1 1} {node2 1} {node3 1} {node4 1} {node5 1} {node6 3}
d1806 2
a1807 2
    mygraph arc insert s v1 [list s v1]
    mygraph arc set [list s v1] throughput 16
d1809 2
a1810 2
    mygraph arc insert s v2 [list s v2]
    mygraph arc set [list s v2] throughput 13
d1812 2
a1813 2
    mygraph arc insert v1 v2 [list v1 v2]
    mygraph arc set [list v1 v2] throughput 10
d1815 2
a1816 2
    mygraph arc insert v2 v1 [list v2 v1]
    mygraph arc set [list v2 v1] throughput 4
d1818 2
a1819 2
    mygraph arc insert v1 v3 [list v1 v3]
    mygraph arc set [list v1 v3] throughput 12
d1821 2
a1822 2
    mygraph arc insert v2 v4 [list v2 v4]
    mygraph arc set [list v2 v4] throughput 14
d1824 2
a1825 2
    mygraph arc insert v3 v2 [list v3 v2]
    mygraph arc set [list v3 v2] throughput 9
d1827 2
a1828 2
    mygraph arc insert v3 t [list v3 t]
    mygraph arc set [list v3 t] throughput 20
d1830 2
a1831 2
    mygraph arc insert v4 v3 [list v4 v3]
    mygraph arc set [list v4 v3] throughput 7
d1833 2
a1834 2
    mygraph arc insert v4 t [list v4 t]
    mygraph arc set [list v4 t] throughput 4
@


1.10
log
@
	* graph/tests/XOpsControl: Added the testsuites for metrictsp,
	  christofides and tspheuristics.
	* graph/tests/ops/metrictsp.test: Testsuite for metrictsp.
	* graph/tests/ops/christofides.test: Testsuite for christofides.
	* graph/tests/ops/tspheuristics.test: Testsuite for tspheuristics.
	  Changes compared to GSoC result:
	  - Test names extended with 'treeimpl'.
	  - Indentation, line-endings
	  - Conversion to v2 syntax, and cleanup of resource handling.
	  - Updated results for different implementations, sorting.

	* graph/tests/XOpsSetup (SETUP_TSPHEURISTIC_1): Fixed growing
	  cycle list throwing of repeated execution of the same test.

	* graph/tests/Xsupport: Added helper commands for the test cases
	  of the various metric tsp commands (canonical tours, ...).

	* graph/tests/Xsetup (tmSE): Added result selection based on
	  implementation of struct::set.

	* graphops.tcl (::struct::graph::op::MetricTravellingSalesman):
	  Fixed problem in algorithm for asymmetric TSP, selecting the
	  tour in the wrong (higher-weight) direction. The Fleury
	  underneath does not care about arc direction.
	  (::struct::graph::op::Christofides): Dropped superfluous
	  variable and fixed M+T operation. The matching does not care
	  about arc direction, and we have insert anti-parallel arcs to
	  avoid any existing.
	  (::struct::graph::op::isEulerian?): Extended API to return
	  tour start. Computable from the arcs, but not easy. Better to get
	  it from the algorithm which knows by definition.
	  (::struct::graph::op::findHamiltonCycle): Get tour start from
	  isEulerian, and drop bogus computation from the tour arcs.
	  (::struct::graph::op::createTGraph): Moved graph creation after
	  error check to avoid a leak when the check fails.
	* graphops.man: Bumped version to 0.11
	* pkgIndex.tcl: (isEulerian API extension, plus bugfixes).
@
text
@d7 1
a7 1
# RCS: @@(#) $Id: XOpsSetup,v 1.9 2009/09/15 19:24:12 andreas_kupries Exp $
d97 1
a97 1
        
d512 16
a527 16
	#Graph for testing Bellman's Ford algorithm (and also other pathfinding algorithms)
	#Used for:
	#Bellman's-Ford
	#Floyd-Warshall's
	#Basic test
	
	graph mygraph
	
	mygraph node insert node1 node2 node3 node4
	mygraph arc insert node1 node2 edge12
	mygraph arc insert node2 node3 edge23
	mygraph arc insert node3 node4 edge34
	mygraph arc insert node4 node1 edge41
	
	mygraph arc setunweighted 1
	return
d533 30
a562 30
	#Graph for testing Bellman-Ford's Algorithm
	#More complex test case
	#Used by:
	#Bellman-Ford's Algorithm
	#Floyd-Warshall's Algorithm
	#Shortest Pathfinding by BFS algorithm
	#BFS Algorithm
	
	graph mygraph
	
	mygraph node insert node1 node2 node3 node4 node5 node6
	
	mygraph arc insert node1 node2 edge12
	mygraph arc setweight edge12 8
	mygraph arc insert node1 node3 edge13
	mygraph arc setweight edge13 6
	mygraph arc insert node2 node4 edge24
	mygraph arc setweight edge24 -1
	mygraph arc insert node3 node2 edge32
	mygraph arc setweight edge32 3
	mygraph arc insert node3 node5 edge35
	mygraph arc setweight edge35 -2
	mygraph arc insert node4 node3 edge43
	mygraph arc setweight edge43 -2
	mygraph arc insert node4 node6 edge46
	mygraph arc setweight edge46 3
	mygraph arc insert node5 node6 edge56
	mygraph arc setweight edge56 2
	
	return
d568 3
a570 3
	SETUP_UNWEIGHTED_K4
	mygraph arc setunweighted 2
	return
d576 17
a592 17
	#Graph containing cycle with negative sum of weights
	#Used for testing:
	#Bellman-Ford's Algorithm
	#Johnson's Algorithm
	#Floyd-Warshall's Algorithm
	
	graph mygraph
	
	mygraph node insert node1 node2 node3
	mygraph arc insert node1 node2 edge12
	mygraph arc setweight edge12 -1
	mygraph arc insert node2 node3 edge23
	mygraph arc setweight edge23 -2
	mygraph arc insert node3 node1 edge31
	mygraph arc setweight edge31 -3
	
	return
d598 21
a618 21
	#Graph containing cycle with negative sum of weights
	#Used for testing:
	#Bellman-Ford's Algorithm
	#Johnson's Algorithm
	#Floyd-Warshall's Algorithm
	
	graph mygraph
	
	mygraph node insert node1 node2 node3 node4 node5 node6
	mygraph arc insert node1 node6
	mygraph arc insert node6 node5
	mygraph arc insert node5 node4
	mygraph arc insert node4 node3
	mygraph arc insert node3 node2
	mygraph arc insert node2 node1
	mygraph arc insert node6 node2 edge62
	mygraph arc setweight edge62 -5
	mygraph arc setunweighted 1
	
	return 
	
d624 29
a652 29
	#Graph containing cycle with negative sum of weights
	#Used for testing:
	#Bellman-Ford's Algorithm
	#Johnson's Algorithm
	#Floyd-Warshall's Algorithm
	
	graph mygraph
	
	mygraph node insert node1 node2 node3 node4 node5
	mygraph arc insert node1 node2 edge12
	mygraph arc setweight edge12 6
	mygraph arc insert node1 node5 edge15
	mygraph arc setweight edge15 7
	mygraph arc insert node2 node4 edge24
	mygraph arc setweight edge24 -4
	mygraph arc insert node2 node5 edge25
	mygraph arc setweight edge25 2
	mygraph arc insert node3 node2 edge32
	mygraph arc setweight edge32 -2
	mygraph arc insert node4 node3 edge43
	mygraph arc setweight edge43 7
	mygraph arc insert node4 node1 edge41
	mygraph arc setweight edge41 2
	mygraph arc insert node5 node3 edge53
	mygraph arc setweight edge53 -3
	mygraph arc insert node5 node4 edge54
	mygraph arc setweight edge54 9
	
	return
d658 9
a666 9
	#Complete graph with 4 nodes
	#Here without one edge - test for directed graphs
	#Used by:
	#For distance searches: Johnson's and Bellman-Ford's
	#Vertices Cover
	
	graph mygraph
	
	mygraph node insert node1 node2 node3 node4
d668 27
a694 27
	mygraph arc insert node1 node2 edge12
	mygraph arc setweight edge12 1
	mygraph arc insert node1 node3 edge13
	mygraph arc setweight edge13 1
	mygraph arc insert node1 node4 edge14
	mygraph arc setweight edge14 1

	mygraph arc insert node2 node1 edge21
	mygraph arc setweight edge21 1
	mygraph arc insert node2 node3 edge23
	mygraph arc setweight edge23 1
	mygraph arc insert node2 node4 edge24
	mygraph arc setweight edge24 1

	mygraph arc insert node3 node1 edge31
	mygraph arc setweight edge31 1
	mygraph arc insert node3 node2 edge32
	mygraph arc setweight edge32 1
	mygraph arc insert node3 node4 edge34
	mygraph arc setweight edge34 1

	mygraph arc insert node4 node1 edge41
	mygraph arc setweight edge41 2
	mygraph arc insert node4 node2 edge42
	mygraph arc setweight edge42 2
		
	return
d701 18
a718 18
	#Graph where their does not exists a path between each pair of vertices
	#Used for testing:
	#Bellman-Ford's Algorithm (Causes appearing of Inf values as a result)
	#Johnson's Algorithm (Causes appearing of Inf values as a result)
	#Metric Travelling Salesman 2-approximation algorithm
	
	graph mygraph
	
	mygraph node insert node1 node2 node3 node4 node5
	
	mygraph arc insert node1 node5
	mygraph arc insert node2 node5
	mygraph arc insert node3 node5
	mygraph arc insert node4 node5
	
	mygraph arc setunweighted 1
	
	return
d724 34
a757 34
	#Graph for testing Johnson's Algorithm
	#Used by:
	#Johnson's Algorithm
	#Floyd-Warshall's Algorithm
	#
	
	graph mygraph
	
	mygraph node insert node1 node2 node3 node4 node5
	
	mygraph arc insert node1 node3 edge13
	mygraph arc setweight edge13 1
	mygraph arc insert node1 node4 edge14
	mygraph arc setweight edge14 7

	mygraph arc insert node2 node1 edge21
	mygraph arc setweight edge21 4

	mygraph arc insert node3 node2 edge32
	mygraph arc setweight edge32 -5
	mygraph arc insert node3 node5 edge35
	mygraph arc setweight edge35 2

	mygraph arc insert node4 node3 edge43
	mygraph arc setweight edge43 6

	mygraph arc insert node5 node1 edge51
	mygraph arc setweight edge51 3
	mygraph arc insert node5 node2 edge52
	mygraph arc setweight edge52 8
	mygraph arc insert node5 node4 edge54
	mygraph arc setweight edge54 -4
	
	return
d763 27
a789 27
	#Graph for testing Johnson's Algorithm
	#Used by:
	#Johnson's Algorithm
	#Floyd-Warshall's Algorithm
	
	graph mygraph
	
	mygraph node insert node1 node2 node3 node4 node5 node6
	
	mygraph arc insert node1 node2 edge12
	mygraph arc setweight edge12 8
	mygraph arc insert node1 node6 edge16
	mygraph arc setweight edge16 6
	mygraph arc insert node2 node3 edge23
	mygraph arc setweight edge23 -1
	mygraph arc insert node3 node4 edge34
	mygraph arc setweight edge34 3
	mygraph arc insert node3 node6 edge36
	mygraph arc setweight edge36 -2
	mygraph arc insert node5 node4 edge54
	mygraph arc setweight edge54 2
	mygraph arc insert node6 node2 edge62
	mygraph arc setweight edge62 3
	mygraph arc insert node6 node5 edge65
	mygraph arc setweight edge65 -2
	
	return
d795 30
a824 30
	#Unweighted directed complete graph K4
	#Used by:
	#Bellman's-Ford
	#Johnson's Algorithm
	#Floyd-Warshall's Algorithm
	#Metric Travelling Salesman 2-approximation algorithm
	#Christofides Algorithm
	#Greedy Maximum Independent Set algorithm
	#Unweighted k-center 2-approximation algorithm
	#Weighted k-center 3-approximation algorithm
	#Greedy Weighted Maximum Independent Set algorithm
	
	graph mygraph
	
	mygraph node insert node1 node2 node3 node4
	
	mygraph arc insert node1 node2
	mygraph arc insert node1 node3
	mygraph arc insert node1 node4
	mygraph arc insert node2 node3
	mygraph arc insert node2 node4
	mygraph arc insert node2 node1
	mygraph arc insert node3 node1
	mygraph arc insert node3 node2
	mygraph arc insert node3 node4
	mygraph arc insert node4 node1
	mygraph arc insert node4 node2
	mygraph arc insert node4 node3
	
	return
d830 17
a846 17
	#Undirected complete graph K4
	#Used by:
	#Metric Travelling Salesman 2-approximation algorithm
	#Vertices Cover
	
	graph mygraph
	
	mygraph node insert node1 node2 node3 node4
	
	mygraph arc insert node1 node2 edge12
	mygraph arc insert node1 node3 edge13
	mygraph arc insert node1 node4 edge14
	mygraph arc insert node2 node3 edge23
	mygraph arc insert node2 node4 edge24
	mygraph arc insert node3 node4 edge34
	
	return
d852 11
a862 11
	#complete graph K4 with some weights set on edges
	#Used by:
	#Bellman's-Ford
	#Johnson's Algorithm
	SETUP_UNWEIGHTED_K4
	
	mygraph arc setweight arc1 1
	mygraph arc setweight arc2 2
	mygraph arc setweight arc3 3
	
	return
d868 13
a880 13
	#Graph containing only nodes
	#Used by:
	#Johnson's Algorithm
	#Floyd-Warshall's Algorithm
	#Metric Travelling Salesman 2-approximation algorithm
	#Christofides Algorithm
	#Max Cut 2-approximation algorithm
	
	graph mygraph 
	
	mygraph node insert node1 node2 node3 node4
	
	return
d886 10
a895 10
	#K4 graph with all edge's weights set to 0
	#Used by:
	#Bellman's-Ford
	#Johnson's Algorithm
	#Floyd-Warshall's Algorithm
	
	SETUP_UNWEIGHTED_K4
	mygraph arc setunweighted
	
	return
d901 12
a912 12
	#graph with some weights of edges set to 0 (others set to 1)
	#Used by:
	#Bellman's-Ford
	#Johnson's Algorithm
	#Floyd-Warshall's Algorithm
	
	SETUP_BELLMANFORD_1
	
	mygraph arc setweight edge12 0
	mygraph arc setweight edge23 0
	
	return
d918 12
a929 12
	#K4 graph with some weights of edges set to 0
	#Used by:
	#Bellman's-Ford
	#Johnson's Algorithm
	#Floyd-Warshall's Algorithm
	
	SETUP_ZEROWEIGHTED_K4
	
	mygraph arc setweight arc1 1
	mygraph arc setweight arc2 2
	
	return
d935 14
a948 14
	#special undirected K4 case where we have two arcs between two nodes
	#with different sources and targets
	graph mygraph
	
	mygraph node insert node1 node2 node3 node4
	
	mygraph arc insert node1 node2
	mygraph arc insert node1 node3
	mygraph arc insert node1 node4 edge14
	mygraph arc insert node2 node3
	mygraph arc insert node3 node4
	mygraph arc insert node4 node1 edge41
	
	return
d953 6
a958 6
	#weighted version of upper graph
	SETUP_ADJACENCYLIST_K4
	
	mygraph arc setunweighted 1
	
	return
d964 7
a970 7
	#directed case, with mixed weights at crucial edges
	SETUP_ADJACENCYLIST_K4_WEIGHTED
	
	mygraph arc setweight edge14 2
	mygraph arc setweight edge41 3
	
	return
d976 12
a987 12
	#undirected and unweighted graph for Adjacency List Testing
	graph mygraph
	
	mygraph node insert node1 node2 node3 node4 node5 node6
	mygraph arc insert node1 node2
	mygraph arc insert node1 node6
	mygraph arc insert node2 node3
	mygraph arc insert node3 node6
	mygraph arc insert node4 node5
	mygraph arc insert node4 node6
		
	return
d994 5
a998 5
	#Graph object for Metric Travelling Salesman problems testing
	#Used by:
	#Metric Travelling Salesman 2-approximation algorithm
	
	graph mygraph
d1000 20
a1019 20
	mygraph node insert node1 node2 node3 node4 node5 node6
	mygraph arc insert node1 node2 
	mygraph arc insert node2 node3
	mygraph arc insert node3 node4
	mygraph arc insert node4 node5
	mygraph arc insert node5 node1
	mygraph arc insert node6 node1
	mygraph arc insert node6 node2
	mygraph arc insert node6 node3
	mygraph arc insert node6 node4
	mygraph arc insert node6 node5
	mygraph arc setunweighted 1
	mygraph arc insert node1 node3
	mygraph arc insert node1 node4
	mygraph arc insert node2 node4
	mygraph arc insert node2 node5
	mygraph arc insert node3 node5
	mygraph arc setunweighted 2
	
	return
d1025 22
a1046 22
	
	#Graph object for Metric Travelling Salesman problems testing
	#Used by:
	#Metric Travelling Salesman 2-approximation algorithm
	
	graph mygraph 
	
	mygraph node insert node1 node2 node3 node4 node5
	mygraph arc insert node1 node2
	mygraph arc insert node2 node3
	mygraph arc insert node3 node4
	mygraph arc insert node4 node1
	mygraph arc insert node5 node1
	mygraph arc insert node5 node2
	mygraph arc insert node5 node3
	mygraph arc insert node5 node4
	mygraph arc setunweighted 1
	mygraph arc insert node2 node4
	mygraph arc insert node1 node3
	mygraph arc setunweighted 2
	
	return
d1048 1
a1048 1
 
d1053 25
a1077 25
	#Graph object for Metric Travelling Salesman problems testing
	#Used by:
	#Metric Travelling Salesman 2-approximation algorithm
	
	graph mygraph
	
	mygraph node insert node1 node2 node3 node4
	mygraph arc insert node1 node2 
	mygraph arc insert node3 node2 
	mygraph arc insert node3 node4 
	mygraph arc insert node4 node1
	mygraph arc insert node2 node1 edge21
	mygraph arc insert node2 node3 edge23
	mygraph arc insert node4 node3 edge43
	mygraph arc insert node1 node4 edge14
	mygraph arc setunweighted 1
	mygraph arc insert node1 node3
	mygraph arc insert node2 node4
	mygraph arc setunweighted 3
	mygraph arc setweight edge23 5
	mygraph arc setweight edge21 4
	mygraph arc setweight edge43 6
	mygraph arc setweight edge14 7
	
	return
d1084 14
a1097 14
	#Graph representing Tight Example for Maximum Cut problem
	#In this case algorithm should find right solution.
	#Used by:
	#Max Cut 2-approximation algorithm
	
	graph mygraph
	
	mygraph node insert node1 node2 node3 node4
	mygraph arc insert node1 node2 edge12
	mygraph arc insert node1 node4 edge14
	mygraph arc insert node2 node3 edge23
	mygraph arc insert node3 node4 edge34
	
	return
d1103 14
a1116 14
	#Graph representing Tight Example for Maximum Cut problem
	#In this case algorithm should find solution, with maximum aproximation factor : ALG = 2 * OPT
	#Used by:
	#Max Cut 2-approximation algorithm
	
	graph mygraph
	
	mygraph node insert node1 node2 node3 node4
	mygraph arc insert node1 node3 edge13
	mygraph arc insert node1 node4 edge14
	mygraph arc insert node2 node3 edge23
	mygraph arc insert node2 node4 edge24
	
	return
d1123 15
a1137 15
	#Used by:
	#Max Cut 2-approximation algorithm
	
	graph mygraph
	
	mygraph node insert node1 node2 node3 node4 node5 node6
	mygraph arc insert node1 node3
	mygraph arc insert node1 node6
	mygraph arc insert node2 node4
	mygraph arc insert node2 node5
	mygraph arc insert node3 node4
	mygraph arc insert node3 node5
	mygraph arc insert node4 node6
	
	return
d1144 17
a1160 17
	#Used by:
	#Max Cut 2-approximation algorithm
	
	graph mygraph
	
	mygraph node insert node1 node2 node3 node4 node5 node6
	mygraph arc insert node1 node2 edge12
	mygraph arc insert node2 node1 edge21
	mygraph arc insert node2 node3 edge23
	mygraph arc insert node3 node2 edge32
	mygraph arc insert node1 node4 edge14
	mygraph arc insert node4 node5 edge45
	mygraph arc insert node5 node4 edge54
	mygraph arc insert node5 node6 edge56
	mygraph arc insert node6 node5 edge65
	
	return
d1167 17
a1183 17
	#Used by:
	#Max Cut 2-approximation algorithm
	
	graph mygraph
	
	mygraph node insert node1 node2 node3 node4 node5 node6
	mygraph arc insert node1 node2 
	mygraph arc insert node1 node3
	mygraph arc insert node3 node1
	mygraph arc insert node4 node2
	mygraph arc insert node2 node4
	mygraph arc insert node4 node6
	mygraph arc insert node6 node4
	mygraph arc insert node5 node3
	mygraph arc insert node3 node5
	
	return
d1190 15
a1204 15
	#Used by:
	#Max Cut 2-approximation algorithm (subprocedure)
	
	upvar 1 U varU V varV
	graph mygraph
	
	mygraph node insert node1 node2 node3 node4
	mygraph arc insert node1 node3
	mygraph arc insert node1 node4
	mygraph arc insert node4 node1
	mygraph arc insert node3 node2
	
	set varU "node1 node2"
	set varV "node3 node4"
	return
d1211 18
a1228 18
	#Used by:
	#Max Cut 2-approximation algorithm (subprocedure)
	
	upvar 1 U varU V varV
	graph mygraph
	
	mygraph node insert node1 node2 node3 node4
	mygraph arc insert node1 node3
	mygraph arc insert node1 node4
	mygraph arc insert node4 node1
	mygraph arc insert node3 node2
	mygraph arc insert node1 node1
	mygraph arc insert node1 node2
	mygraph arc insert node4 node3
	
	set varU "node1 node2"
	set varV "node3 node4"
	return
d1234 14
a1247 14
	#Used by:
	#Max Cut 2-approximation algorithm (subprocedure)
	
	upvar 1 U varU V varV
	graph mygraph
	
	mygraph node insert node1 node2 node3 node4
	mygraph arc insert node1 node1
	mygraph arc insert node1 node2
	mygraph arc insert node4 node3
	
	set varU "node1 node2"
	set varV "node3 node4"
	return
d1253 11
a1263 11
	
	#Used by:
	#Max Cut 2-approximation algorithm (subprocedure)
	
	upvar 1 U varU V varV
	SETUP_COUNTEDGES_2 varU varV
	
	set varU "node1 node3"
	set varV "node2 node4"
		
	return
d1270 11
a1280 11
	#Used by:
	#Max Cut 2-approximation algorithm (subprocedure)
	
	upvar 1 U varU V varV param varParam
	SETUP_MAXCUT_3
	
	set varU "node1 node5 node4"
	set varV "node2 node3 node6"
	set varParam 7
	
	return
d1287 11
a1297 11
	#Used by:
	#Max Cut 2-approximation algorithm (subprocedure)
	
	upvar 1 U varU V varV param varParam
	SETUP_CUT_1 varU varV varParam
	
	set varU "node1 node3 node5"
	set varV "node2 node4 node6"
	set varParam 3
	
	return
d1304 20
a1323 20
	#Graph object for Metric Travelling Salesman problems testing
	#Used by:
	#Metric Travelling Salesman 2-approximation algorithm
	
	upvar 1 E edges
	graph mygraph
	
	mygraph node insert node1 node2 node3 node4
	mygraph arc insert node1 node2 edge12
	mygraph arc setweight edge12 1
	mygraph arc insert node1 node3 edge13
	mygraph arc setweight edge13 2
	mygraph arc insert node1 node4 edge14
	mygraph arc setweight edge14 3
	mygraph arc insert node4 node1 edge41
	mygraph arc setweight edge41 4
	
	set edges "edge12 edge14"
	return
	
d1330 9
a1338 9
	#Graph object for Metric Travelling Salesman problems testing
	#Used by:
	#Metric Travelling Salesman 2-approximation algorithm
	
	SETUP_NOEDGES_1
	upvar 1 E edges
	
	set edges "edge1 edge2"
	return
d1345 20
a1364 20
	#Graph object for Metric Travelling Salesman problems testing
	#Used by:
	#Metric Travelling Salesman 2-approximation algorithm
	
	upvar 1 E edges
	graph mygraph
	
	mygraph node insert node1 node2 node3 node4
	mygraph arc insert node1 node2 edge12
	mygraph arc setweight edge12 1
	mygraph arc insert node1 node3 edge13
	mygraph arc setweight edge13 2
	mygraph arc insert node1 node4 edge14
	mygraph arc setweight edge14 3
	mygraph arc insert node4 node1 edge41
	mygraph arc setweight edge41 4
	
	set edges {edge14 edge41 edge13}
	return
	
d1371 2
a1372 2
	#Used by:
	#Christofides Algorithm (Tight Example)
d1374 19
a1392 19
	graph mygraph
	
	mygraph node insert node1 node2 node3 node4 node5 node6 node7
	mygraph arc insert node1 node2 edge12
	mygraph arc insert node1 node3 edge13
	mygraph arc insert node2 node3 edge23
	mygraph arc insert node2 node4 edge24
	mygraph arc insert node3 node4 edge34
	mygraph arc insert node3 node5 edge35
	mygraph arc insert node4 node5 edge45
	mygraph arc insert node4 node6 edge46
	mygraph arc insert node5 node6 edge56
	mygraph arc insert node5 node7 edge57
	mygraph arc insert node6 node7 edge67
	mygraph arc setunweighted 1
	mygraph arc insert node7 node1 edge71
	mygraph arc setunweighted 3
	
	return
d1398 15
a1412 15
	
	#Used by:
	#Vertices Cover
	
	graph mygraph
	
	mygraph node insert node1 node2 node3 node4 node5 node6
	mygraph arc insert node1 node2 edge12
	mygraph arc insert node1 node3 edge13
	mygraph arc insert node2 node3 edge23
	mygraph arc insert node3 node4 edge34
	mygraph arc insert node3 node5 edge35
	mygraph arc insert node3 node6 edge36
	
	return
d1419 13
a1431 13
	#Used by:
	#Vertices Cover
	
	SETUP_VC_1
	
	mygraph arc insert node2 node1 edge21
	mygraph arc insert node3 node1 edge31
	mygraph arc insert node3 node2 edge32
	mygraph arc insert node4 node3 edge43
	mygraph arc insert node5 node3 edge53
	mygraph arc insert node6 node3 edge63
	
	return
d1438 11
a1448 11
	#Used by:
	#Vertices Cover
	
	SETUP_VC_1
	
	mygraph arc insert node2 node1 edge21
	mygraph arc insert node3 node1 edge31
	mygraph arc insert node3 node2 edge32
	mygraph arc insert node4 node3 edge43
		
	return
d1453 16
a1468 16
	
	#Used by:
	#Vertices Cover
	
	graph mygraph
	
	mygraph node insert node1 node2 node3 node4 node5 node6
	mygraph arc insert node1 node2 edge12
	mygraph arc insert node1 node3 edge13
	mygraph arc insert node2 node3 edge23
	mygraph arc insert node2 node4 edge24
	mygraph arc insert node3 node5 edge35
	mygraph arc insert node4 node5 edge45
	mygraph arc insert node4 node6 edge46
	
	return
d1475 16
a1490 16
	#Cycle with 5 edges - C5
	#Used by:
	#Greedy Maximum Independent Set algorithm
	#Greedy Weighted Maximum Independent Set algorithm
	#Vertices Cover
	
	graph mygraph
	
	mygraph node insert node1 node2 node3 node4 node5
	mygraph arc insert node1 node2
	mygraph arc insert node2 node3
	mygraph arc insert node3 node4
	mygraph arc insert node4 node5
	mygraph arc insert node5 node1
	
	return
d1496 36
a1531 12
	
	#graph containing 24 nodes for independent set testing
	#Reference: http://en.wikipedia.org/wiki/Independent_set_(graph_theory)#Maximal_independent_set
	#Used by:
	#Greedy Maximum Independent Set algorithm
	#Greedy Weighted Maximum Independent Set algorithm
	
	graph mygraph
	
	#adding 24 nodes: node1 - node24
	for {set i 1} {$i<25} {incr i} {
		mygraph node insert node$i
d1533 6
a1538 6

	#adding external edges: node1 node2, node2 node3....
	for {set i 1} {$i<13} {incr i} {
		set j [ expr { $i%12 } ]
		incr j
		mygraph arc insert node$i node$j ;#[list node$i node$j]
d1540 3
a1542 4

	#adding edges connecting internal nodes with external nodes
	for {set i 1} {$i<13} {incr i} {
		mygraph arc insert node$i node[expr {$i+12}] ;#[list node$i node[expr {$i+12}]]
d1544 2
a1545 26

	#adding edges between internal nodes
	for {set i 13} {$i<25} {incr i} {
		set u [ expr {($i+4)%24} ]
		set v [ expr {($i-4)%24} ]
		if { $u < 13 } {
			if {$u == 0} {
				set u 24
			} else {
				set u [expr {$u+12}]
			}
		}
		if { $v < 13} {
			if {$v == 0} {
				set v 24
			} else {
				set v [expr {$v+12}]
			}
		}
	
		if { ![mygraph arc exists [list node$u node$i]] } {
			mygraph arc insert node$i node$u [list node$i node$u]
		}
		if { ![mygraph arc exists [list node$v node$i]] } {
			mygraph arc insert node$i node$v [list node$i node$v]
		}
d1547 3
a1549 2
	
	return
d1555 23
a1577 16
	#Tight Example for unweighted version of K-Center problem
	#Used by:
	#Unweighted k-center 2-approximation algorithm
	#Weighted k-center 3-approximation algorithm
	
	graph mygraph
	mygraph node insert node1 node2 node3 node4 node5 node6 node7
	mygraph arc insert node1 node7 [list node1 node7]
	mygraph arc insert node2 node7 [list node2 node7]
	mygraph arc insert node3 node7 [list node3 node7]
	mygraph arc insert node4 node7 [list node4 node7]
	mygraph arc insert node5 node7 [list node5 node7]
	mygraph arc insert node6 node7 [list node6 node7]
	mygraph arc setunweighted 1

	for {set i 1} {$i < 7 } { incr i } {
d1579 5
a1583 15
		if { [ expr { $i+1 } ] < 7 } {
			mygraph arc insert node$i node[ expr { $i+1 } ] [list node$i node[ expr { $i+1 } ]]
		} else {
			if { ![mygraph arc exists [list node6 node1]] } {
				mygraph arc insert node6 node1 [list node6 node1]
			}
		}
	
		if { [ expr { $i+2 } ] < 7 } {
			mygraph arc insert node$i node[ expr { $i+2 } ] [list node$i node[ expr { $i+2 } ]]
		} else {
			if { ![mygraph arc exists [list node6 node2]] } {
				mygraph arc insert node6 node2 [list node6 node2]
			}
		}
d1585 5
a1589 4
	mygraph arc insert node1 node5 [list node1 node5]
	mygraph arc setunweighted 2
	
	return
d1595 13
a1607 14
	
	#Used by:
	#Unweighted k-center 2-approximation algorithm
	
	graph mygraph 
	
	mygraph node insert node1 node2 node3 node4 node5 node6 node7 node8
	
	foreach v [mygraph nodes] {
		foreach u [mygraph nodes] {
			if { ($u!=$v) && ![mygraph arc exists [list $u $v]] } {
				mygraph arc insert $v $u [list $v $u]
			}
		}
d1609 6
a1614 6
	foreach x [mygraph nodes -adj node1] {
		if { [mygraph arc exists [list $x node1]] } {
			mygraph arc setweight [list $x node1] 1
		} else {
			mygraph arc setweight [list node1 $x] 1
		}
d1616 6
a1621 6
	foreach x [mygraph nodes -adj node2] {
		if { [mygraph arc exists [list $x node2]] } {
			mygraph arc setweight [list $x node2] 1
		} else {
			mygraph arc setweight [list node2 $x] 1
		}
d1623 4
a1626 3
	
	mygraph arc setunweighted 2
	return
d1632 18
a1649 18
	
	#Used by:
	#createSquaredGraph procedure
	#Unweighted k-center 2-approximation algorithm (subprocedure that extends two-squared graphs)
	
	graph mygraph
	
	mygraph node insert node1 node2 node3 node4 node5 node6 node7 node8
	mygraph arc insert node1 node2 "node1 node2"
	mygraph arc insert node2 node3 "node2 node3"
	mygraph arc insert node2 node4 "node2 node4"
	mygraph arc insert node3 node4 "node3 node4"
	mygraph arc insert node3 node5 "node3 node5"
	mygraph arc insert node5 node6 "node5 node6"
	mygraph arc insert node5 node7 "node5 node7"
	mygraph arc insert node7 node8 "node7 node8"
	
	return
d1655 14
a1668 14
	
	#Used by:
	#createSquaredGraph procedure
	#Unweighted k-center 2-approximation algorithm (subprocedure that extends two-squared graphs)
	
	graph mygraph
	
	mygraph node insert node1 node2 node3 node4 node5
	mygraph arc insert node1 node2 "node1 node2"
	mygraph arc insert node2 node3 "node2 node3"
	mygraph arc insert node3 node4 "node3 node4"
	mygraph arc insert node4 node5 "node4 node5"
	
	return
d1675 13
a1687 13
	#Used by:
	#Unweighted k-center 2-approximation algorithm (subprocedure that extends two-squared graphs)
	
	graph mygraph2
	
	mygraph2 node insert node1 node2 node3 node4 node5
	mygraph2 arc insert node1 node2 "node1 node2"
	mygraph2 arc insert node2 node3 "node2 node3"
	mygraph2 arc insert node3 node4 "node3 node4"
	mygraph2 arc insert node1 node3 "node1 node3"
	mygraph2 arc insert node2 node4 "node2 node4"
		
	return
d1694 21
a1714 21
	#Used by:
	#Unweighted k-center 2-approximation algorithm (subprocedure that extends two-squared graphs)
	
	graph mygraph2
	
	mygraph2 node insert node1 node2 node3 node4 node5 node6 node7 node8
	
	mygraph2 arc insert node1 node2 "node1 node2"
	mygraph2 arc insert node1 node3 "node1 node3"
	mygraph2 arc insert node1 node4 "node1 node4"
	mygraph2 arc insert node2 node3 "node2 node3"
	mygraph2 arc insert node2 node4 "node2 node4"
	mygraph2 arc insert node3 node4 "node3 node4"
	
	mygraph2 arc insert node5 node6 "node5 node6"
	mygraph2 arc insert node5 node7 "node5 node7"
	mygraph2 arc insert node5 node8 "node5 node8"
	mygraph2 arc insert node6 node7 "node6 node7"
	mygraph2 arc insert node7 node8 "node7 node8"
	
	return
d1721 21
a1741 21
	#Used by:
	#Weighted k-center 3-approximation algorithm
	
	upvar 1 nodeWeights nW
	graph mygraph
	
	mygraph node insert node1 node2 node3 node4 node5 node6 node7 node8
	mygraph arc insert node1 node2
	mygraph arc insert node2 node3
	mygraph arc insert node3 node4
	mygraph arc setunweighted 1
	mygraph arc insert node4 node5
	mygraph arc insert node4 node6
	mygraph arc insert node4 node7
	mygraph arc insert node4 node8
	mygraph arc setunweighted 1.5
	
	set nW {}
	lappend nW {node1 2} {node2 2} {node3 2} {node4 1} {node5 Inf} {node6 Inf} {node7 Inf} {node8 Inf}
	
	return
d1748 29
a1776 29
	#Used by:
	#Weighted k-center 3-approximation algorithm
	
	upvar 1 nodeWeights nW
	
	graph mygraph
	
	mygraph node insert node1 node2 node3 node4 node5 node6
	mygraph arc insert node1 node6
	mygraph arc insert node2 node6
	mygraph arc insert node3 node6
	
	mygraph arc insert node5 node6
	mygraph arc insert node1 node5
	mygraph arc insert node2 node5
	mygraph arc insert node3 node5
	mygraph arc setunweighted 1
	
	
	mygraph arc insert node4 node5
	mygraph arc setunweighted 3
	mygraph arc insert node4 node6
	mygraph arc setunweighted 2
	
	
	set nW {}
	lappend nW {node1 2} {node2 2} {node3 2} {node4 3} {node5 2} {node6 1}
	
	return
d1782 12
a1793 12
	
	#Used by:
	#Weighted k-center 3-approximation algorithm
	
	SETUP_WEIGHTEDKCENTER_2 n
	
	upvar 1 nodeWeights nW
	
	set nW {}
	lappend nW {node1 1} {node2 1} {node3 1} {node4 1} {node5 1} {node6 3}
	
	return
d1800 40
a1839 40
	#The flow network with througputs set for each existing (non-zero) link
	#Used by:
	#Edmond's Karp algorithm
	#Create Residual Graph procedure (subprocedure of Edmond's Karp)
	#Dinic's Algorithm for maximum flow computation
	#Subprocedures of above: MKM and Dinic's algorithms for blocking flow finding
	
	graph mygraph
	
	mygraph node insert s v1 v2 v3 v4 t
	
	mygraph arc insert s v1 [list s v1]
	mygraph arc set [list s v1] throughput 16
	
	mygraph arc insert s v2 [list s v2]
	mygraph arc set [list s v2] throughput 13
	
	mygraph arc insert v1 v2 [list v1 v2]
	mygraph arc set [list v1 v2] throughput 10
	
	mygraph arc insert v2 v1 [list v2 v1]
	mygraph arc set [list v2 v1] throughput 4
	
	mygraph arc insert v1 v3 [list v1 v3]
	mygraph arc set [list v1 v3] throughput 12
	
	mygraph arc insert v2 v4 [list v2 v4]
	mygraph arc set [list v2 v4] throughput 14
	
	mygraph arc insert v3 v2 [list v3 v2]
	mygraph arc set [list v3 v2] throughput 9
	
	mygraph arc insert v3 t [list v3 t]
	mygraph arc set [list v3 t] throughput 20
	
	mygraph arc insert v4 v3 [list v4 v3]
	mygraph arc set [list v4 v3] throughput 7
	
	mygraph arc insert v4 t [list v4 t]
	mygraph arc set [list v4 t] throughput 4
d1841 2
a1842 2
	return
	
d1849 22
a1870 22
	#The flow network with througputs set for each existing (non-zero) link
	#Used by:
	#Edmond's Karp algorithm (Tight Example)
	#Dinic's Algorithm for maximum flow computation
	#Subprocedures of above: MKM and Dinic's algorithms for blocking flow finding
	
	graph mygraph
	
	mygraph node insert a b c d
	
	mygraph arc insert a b ab
	mygraph arc set ab throughput 1000000
	mygraph arc insert a c ac
	mygraph arc set ac throughput 1000000
	mygraph arc insert b d bd
	mygraph arc set bd throughput 1000000
	mygraph arc insert c d cd
	mygraph arc set cd throughput 1000000
	mygraph arc insert b c bc 
	mygraph arc set bc throughput 1
	
	return
d1878 41
a1918 41
	#The flow network with througputs set for each existing (non-zero) link
	#Used by:
	#Edmond's Karp algorithm
	#Dinic's Algorithm for maximum flow computation
	#Subprocedures of above: MKM and Dinic's algorithms for blocking flow finding
	
	graph mygraph
	
	mygraph node insert s v1 v2 v3 t
	
	mygraph arc insert s v1 sv1
	mygraph arc set sv1 throughput 10
	
	mygraph arc insert s v2 sv2
	mygraph arc set sv2 throughput 5
	
	mygraph arc insert s v3 sv3
	mygraph arc set sv3 throughput 3
	
	mygraph arc insert v1 v2 v1v2
	mygraph arc set v1v2 throughput 4
	
	mygraph arc insert v2 v1 v2v1
	mygraph arc set v2v1 throughput 2
	
	mygraph arc insert v2 v2 v2v3
	mygraph arc set v2v3 throughput 2
	
	mygraph arc insert v3 v2 v3v2
	mygraph arc set v3v2 throughput 4
	
	mygraph arc insert v1 t v1t
	mygraph arc set v1t throughput 3
	
	mygraph arc insert v2 t v2t
	mygraph arc set v2t throughput 8
	
	mygraph arc insert v3 t v3t
	mygraph arc set v3t throughput 10
	
	return
d1925 14
a1938 14
	#The flow network with througputs set for each existing (non-zero) link
	#Used by:
	#Edmond's Karp algorithm
	#Dinic's Algorithm for maximum flow computation
	#Subprocedures of above: MKM and Dinic's algorithms for blocking flow finding
	
	SETUP_FORDFULKERSON_3
		
	mygraph arc set v1v2 throughput 1
	mygraph arc set v2v1 throughput 1
	mygraph arc set v2v3 throughput 1
	mygraph arc set v3v2 throughput 1
	
	return
d1944 21
a1964 21
	#The flow network with througputs set for each existing (non-zero) link
	#Used by:
	#Edmond's Karp algorithm
	#Dinic's Algorithm for maximum flow computation
	#Subprocedures of above: MKM and Dinic's algorithms for blocking flow finding
	
	SETUP_FORDFULKERSON_3
		
	mygraph arc setweight sv1 10.5
	mygraph arc set sv1 throughput 10.5
	mygraph arc set sv2 throughput 5.5
	mygraph arc set sv3 throughput 3.5
	mygraph arc set v1v2 throughput 4.5
	mygraph arc set v2v1 throughput 2.5
	mygraph arc set v2v3 throughput 2.3
	mygraph arc set v3v2 throughput 4.2
	mygraph arc set v1t throughput 3.1
	mygraph arc set v2t throughput 8.9
	mygraph arc set v3t throughput 10.1
	
	return
d1970 12
a1981 12
	
	#Used by:
	#Create Residual Graph procedure (subprocedure of Edmond's Karp)
	
	foreach arc [$mygraph arcs] {
		set u [$mygraph arc source $arc]
		set v [$mygraph arc target $arc]
		dict set f [list $u $v] 0
		dict set f [list $v $u] 0
	}
	
	return $f
d1986 14
a1999 14
proc SETUP_FLOWS_1 {mygraph} {

	#Used by:
	#Create Residual Graph procedure (subprocedure of Edmond's Karp)
	
	set f [SETUP_FLOWS_0 $mygraph]
	
	dict set f [list s v1] 4
	dict set f [list v1 v3] 4
	dict set f [list v3 v2] 4
	dict set f [list v2 v4] 4
	dict set f [list v4 t] 4
	
	return $f
d2006 17
a2022 17
	#Used by:
	#Create Residual Graph procedure (subprocedure of Edmond's Karp)
	
	set f [SETUP_FLOWS_0 $mygraph]
	
	dict set f [list s v1] 11
	dict set f [list v1 v3] 4
	dict set f [list v3 v2] 4
	dict set f [list v2 v4] 11
	dict set f [list v4 t] 4
	
	dict set f [list v1 v2] 7
	dict set f [list v4 v3] 7
	dict set f [list v3 t] 7
	
	
	return $f
d2028 17
a2044 17
	
	#Used by:
	#Create Residual Graph procedure (subprocedure of Edmond's Karp)
	
	set f [SETUP_FLOWS_0 $mygraph]
	
	dict set f [list s v1] 11
	dict set f [list s v2] 8
	dict set f [list v2 v1] 1
	dict set f [list v1 v3] 12
	dict set f [list v2 v4] 11
	dict set f [list v3 v2] 4
	dict set f [list v4 v3] 7
	dict set f [list v3 t] 15
	dict set f [list v4 t] 4
	
	return $f
d2051 15
a2065 15
	#Used by:
	#Create Residual Graph procedure (subprocedure of Edmond's Karp)
	
	set f [SETUP_FLOWS_0 $mygraph]
	
	dict set f [list s v1] 11
	dict set f [list s v2] 12
	dict set f [list v2 v1] 1
	dict set f [list v1 v3] 12
	dict set f [list v2 v4] 11
	dict set f [list v4 v3] 7
	dict set f [list v3 t] 19
	dict set f [list v4 t] 4
	
	return $f
d2071 53
a2123 53
	
	#Used by:
	#Create Augmenting Network procedure (subprocedure of Busacker-Gowen's Algorithm)
	
	upvar 1 $_f f $_path path
	
	graph mygraph 
	
	mygraph node insert s a b c t
	
	mygraph arc insert s a [list s a]
	mygraph arc set [list s a] throughput 18
	mygraph arc set [list s a] cost 3
	
	mygraph arc insert s c [list s c]
	mygraph arc set [list s c] throughput 20
	mygraph arc set [list s c] cost 8
	
	mygraph arc insert a b [list a b]
	mygraph arc set [list a b] throughput 20
	mygraph arc set [list a b] cost 5
	
	mygraph arc insert a c [list a c]
	mygraph arc set [list a c] throughput 15
	mygraph arc set [list a c] cost 4
	
	mygraph arc insert c b [list c b]
	mygraph arc set [list c b] throughput 12
	mygraph arc set [list c b] cost 8
	
	mygraph arc insert b t [list b t]
	mygraph arc set [list b t] throughput 14
	mygraph arc set [list b t] cost 5
	
	mygraph arc insert c t [list c t]
	mygraph arc set [list c t] throughput 17
	mygraph arc set [list c t] cost 3
	
	set path {}
	lappend path s a c t
	
	foreach e [mygraph arcs] {
		set u [mygraph arc source $e]
		set v [mygraph arc target $e]
		dict set f [list $u $v] 0
		dict set f [list $v $u] 0
	}
	
	dict set f [list s a] 15
	dict set f [list a c] 15
	dict set f [list c t] 15
	
	return	
d2129 40
a2168 40
	
	#Used by:
	#Create Augmenting Network procedure (subprocedure of Busacker-Gowen's Algorithm)
	
	upvar 1 $_f f $_path path
	
	SETUP_AUGMENTINGNETWORK_1 f path
	
	#mygraph arc insert s a [list s a]
	mygraph arc set [list s a] throughput 3
	mygraph arc set [list s a] cost 3
	
	mygraph arc insert a s [list a s]
	mygraph arc set [list a s] throughput 15
	mygraph arc set [list a s] cost -3
	
	mygraph arc insert c a [list c a]
	mygraph arc set [list c a] throughput 15
	mygraph arc set [list c a] cost -4
	
	mygraph arc set [list a c] throughput 0
	mygraph arc set [list a c] cost Inf
	
	#mygraph arc insert c t [list c t]
	mygraph arc set [list c t] throughput 2
	mygraph arc set [list c t] cost 3
	
	mygraph arc insert t c [list t c]
	mygraph arc set [list t c] throughput 15
	mygraph arc set [list t c] cost -3
	
	set path {}
	lappend path s c t
	
	dict set f [list s a] 15
	dict set f [list a c] 15
	dict set f [list c t] 17
	dict set f [list s c] 2
	
	return	
d2174 32
a2205 32
	
	#Used by:
	#Create Augmenting Network procedure (subprocedure of Busacker-Gowen's Algorithm)
	
	upvar 1 $_f f $_path path
	
	SETUP_AUGMENTINGNETWORK_2 f path
	
	mygraph arc set [list c t] throughput 0
	mygraph arc set [list c t] cost Inf
	
	mygraph arc set [list t c] throughput 17
	mygraph arc set [list t c] cost -3
	
	mygraph arc set [list s c] throughput 18
	mygraph arc set [list s c] cost 8
	
	mygraph arc insert c s [list c s]
	mygraph arc set [list c s] throughput 2
	mygraph arc set [list c s] cost -8
	
	set path {}
	lappend path s a b t
	
	dict set f [list s a] 18
	dict set f [list a c] 15
	dict set f [list c t] 17
	dict set f [list s c] 2
	dict set f [list a b] 3
	dict set f [list b t] 3
	
	return	
d2212 41
a2252 41
	#Used by:
	#Busacker Gowen Algorithm
	
	graph mygraph
	
	mygraph node insert s a b c t
	
	mygraph arc insert s a sa
	mygraph arc setweight sa 3
	mygraph arc set sa cost 3
	mygraph arc set sa throughput 18
	
	mygraph arc insert s c sc
	mygraph arc setweight sc 8
	mygraph arc set sc cost 8
	mygraph arc set sc throughput 20
	
	mygraph arc insert a b ab
	mygraph arc setweight ab 5
	mygraph arc set ab cost 5
	mygraph arc set ab throughput 20
	
	mygraph arc insert a c ac
	mygraph arc setweight ac 4
	mygraph arc set ac cost 4
	mygraph arc set ac throughput 15
	
	mygraph arc insert c b cb
	mygraph arc setweight cb 8
	mygraph arc set cb cost 8
	mygraph arc set cb throughput 12
	
	mygraph arc insert b t bt
	mygraph arc setweight bt 5
	mygraph arc set bt cost 5
	mygraph arc set bt throughput 14
	
	mygraph arc insert c t ct
	mygraph arc setweight ct 3	
	mygraph arc set ct cost 3
	mygraph arc set ct throughput 17
d2254 1
a2254 1
	return
d2260 18
a2277 18
	#graph with not all attributes set
	
	#Used by:
	#Busacker Gowen Algorithm
	#Edmond's Karp Algorithm
	
	graph mygraph
	
	mygraph node insert s v1 v2 t
	mygraph arc insert v1 s v1s
	
	mygraph arc insert v2 s v2s
	mygraph arc insert v1 t v1t
	mygraph arc set v1t throughput 20
	mygraph arc set v1t cost 5
	mygraph arc insert v2 t v2t
	mygraph arc set v2t throughput 20
	mygraph arc set v2t cost 5
d2279 1
a2279 1
	return
d2284 21
a2304 21
	#graph where from the start path between source node s and 
	#sink node t doesn't exist
	#Used by Busacker - Gowen
	
	graph mygraph
	
	mygraph node insert s v1 v2 t
	mygraph arc insert v1 s v1s
	mygraph arc set v1s throughput 20
	mygraph arc set v1s cost 5
	mygraph arc insert v2 s v2s
	mygraph arc set v2s throughput 20
	mygraph arc set v2s cost 5
	mygraph arc insert v1 t v1t
	mygraph arc set v1t throughput 20
	mygraph arc set v1t cost 5
	mygraph arc insert v2 t v2t
	mygraph arc set v2t throughput 20
	mygraph arc set v2t cost 5
		
	return
d2311 7
a2317 7
	#Used by:
	#Minimum Diameter Spanning Tree Algorithm
	#BFS algorithm
	
	graph mygraph
	
	mygraph node insert a b c d e f g h i j
d2319 11
a2329 11
	mygraph arc insert a b
	mygraph arc insert b c
	mygraph arc insert c d
	mygraph arc insert d e
	mygraph arc insert e f
	mygraph arc insert b h
	mygraph arc insert c g
	mygraph arc insert d h
	mygraph arc insert e g
	mygraph arc insert g i
	mygraph arc insert h j
d2331 1
a2331 1
	return
d2338 18
a2355 18
	#Used by:
	#Minimum Degree Spanning Tree Tests
	
	graph mygraph
	
	mygraph node insert v1 v2 v3 v4 v5 v6 v7 v8
	mygraph arc insert v1 v2 12
	mygraph arc insert v1 v3 13
	mygraph arc insert v2 v4 24
	mygraph arc insert v3 v4 34
	mygraph arc insert v3 v5 35
	mygraph arc insert v4 v5 45
	mygraph arc insert v5 v6 56
	mygraph arc insert v5 v7 57
	mygraph arc insert v7 v8 78
	mygraph arc insert v6 v8 68
	
	return
d2362 12
a2373 12
	#Used by:
	#Minimum Diameter Spanning Tree Algorithm
	
	graph mygraph
	
	mygraph node insert a b c d e
	mygraph arc insert a b ab
	mygraph arc insert b c bc
	mygraph arc insert c d cd
	mygraph arc insert d e de
	
	return
d2380 11
a2390 11
	#Used by:
	#Minimum Diameter Spanning Tree Algorithm
	
	SETUP_MDST_3
	
	mygraph node insert f g
	mygraph arc insert e f ef
	mygraph arc insert f g fg
	mygraph arc insert d g dg
	
	return
d2397 14
a2410 14
	#Used by:
	#Minimum Diameter Spanning Tree Algorithm
	
	graph mygraph
	mygraph node insert a b c d e
	mygraph arc insert a b ab
	mygraph arc insert b c bc
	mygraph arc insert c d cd
	mygraph arc insert d e de
	mygraph arc insert a c ac
	mygraph arc insert b d bd
	mygraph arc insert c e ce
	
	return
d2417 20
a2436 20
	#Used by:
	#Minimum Degree Spanning Tree Tests
	
	graph mygraph
	
	mygraph node insert a b c d e f g
	mygraph arc insert a b ab
	mygraph arc insert b c bc
	mygraph arc insert c d cd
	mygraph arc insert d e de
	mygraph arc insert e f ef
	mygraph arc insert f a fa
	mygraph arc insert g a ga
	mygraph arc insert g b gb
	mygraph arc insert g c gc
	mygraph arc insert g d gd
	mygraph arc insert g e ge
	mygraph arc insert g f gf
	
	return	
d2442 21
a2462 21
	
	#Used by:
	#Minimum Degree Spanning Tree Tests
	
	graph mygraph
	
	mygraph node insert a b c d e f
	mygraph arc insert a b ab
	mygraph arc insert a c ac
	mygraph arc insert b d bd
	mygraph arc insert c e ce
	mygraph arc insert d f df
	mygraph arc insert e f ef
	mygraph arc insert b e be
	mygraph arc insert c d cd
	mygraph arc insert a f af
	mygraph arc insert f a fa
	mygraph arc insert b c bc
	mygraph arc insert d e de
	
	return
d2469 8
a2476 8
	#Residual graph for blocking flow testing
	#Used by:
	#Dinic's Blocking Flow Algorithm
	#MKM (3 Hindu) Blocking Flow Algorithm
	
	graph mygraph
	
	mygraph node insert s v1 v2 v3 v4 v5 v6 v7 t
d2478 34
a2511 34
	mygraph arc insert s v1 sv1
	mygraph arc set sv1 throughput 4
	mygraph arc insert s v3 sv3
	mygraph arc set sv3 throughput 2
	mygraph arc insert v1 v2 v1v2
	mygraph arc set v1v2 throughput 3
	mygraph arc insert v1 v4 v1v4
	mygraph arc set v1v4 throughput 1
	mygraph arc insert v2 v5 v2v5
	mygraph arc set v2v5 throughput 2
	mygraph arc insert v3 v4 v3v4
	mygraph arc set v3v4 throughput 1
	mygraph arc insert v3 v6 v3v6
	mygraph arc set v3v6 throughput 3
	mygraph arc insert v4 v1 v4v1
	mygraph arc set v4v1 throughput 1
	mygraph arc insert v4 v5 v4v5
	mygraph arc set v4v5 throughput 2
	mygraph arc insert v4 v7 v4v7
	mygraph arc set v4v7 throughput 2
	mygraph arc insert v4 v6 v4v6
	mygraph arc set v4v6 throughput 1
	mygraph arc insert v5 v1 v5v1
	mygraph arc set v5v1 throughput 3
	mygraph arc insert v5 t v5t
	mygraph arc set v5t throughput 3
	mygraph arc insert v6 v4 v6v4
	mygraph arc set v6v4 throughput 3
	mygraph arc insert v6 v7 v6v7
	mygraph arc set v6v7 throughput 4
	mygraph arc insert v7 t v7t
	mygraph arc set v7t throughput 2
	mygraph arc insert t v7 tv7
	mygraph arc set tv7 throughput 3
d2513 1
a2513 1
	return
d2519 38
a2556 38
	
	#residual graph for blocking flow testing
	#Used by:
	#Dinic's Blocking Flow Algorithm
	#MKM (3 Hindu) Blocking Flow Algorithm
	
	graph mygraph 
	
	mygraph node insert s v1 v2 v3 v4 t
	
	mygraph arc insert s v2 sv2
	mygraph arc set sv2 throughput 6
	mygraph arc insert v2 s v2s
	mygraph arc set v2s throughput 4
	mygraph arc insert v1 s v1s
	mygraph arc set v1s throughput 10
	mygraph arc insert v1 v2 v1v2
	mygraph arc set v1v2 throughput 2
	mygraph arc insert v1 v4 v1v4 
	mygraph arc set v1v4 throughput 2
	mygraph arc insert v2 v4 v2v4
	mygraph arc set v2v4 throughput 5
	mygraph arc insert v3 v1 v3v1
	mygraph arc set v3v1 throughput 4
	mygraph arc insert v3 t v3t
	mygraph arc set v3t throughput 6
	mygraph arc insert v4 v1 v4v1
	mygraph arc set v4v1 throughput 6
	mygraph arc insert v4 v2 v4v2
	mygraph arc set v4v2 throughput 4
	mygraph arc insert v4 v3 v4v3
	mygraph arc set v4v3 throughput 6
	mygraph arc insert t v4 tv4
	mygraph arc set tv4 throughput 10
	mygraph arc insert t v3 tv3
	mygraph arc set tv3 throughput 4
	
	return
d2562 36
a2597 36
	
	#residual graph for blocking flow testing
	#Used by:
	#Dinic's Blocking Flow Algorithm
	#MKM (3 Hindu) Blocking Flow Algorithm
	
	graph mygraph 
	
	mygraph node insert s v1 v2 v3 v4 t
	
	mygraph arc insert v2 s v2s
	mygraph arc set v2s throughput 10
	mygraph arc insert v1 s v1s
	mygraph arc set v1s throughput 10
	mygraph arc insert v1 v2 v1v2
	mygraph arc set v1v2 throughput 2
	mygraph arc insert v1 v4 v1v4 
	mygraph arc set v1v4 throughput 2
	mygraph arc insert v3 v1 v3v1
	mygraph arc set v3v1 throughput 4
	mygraph arc insert v3 t v3t
	mygraph arc set v3t throughput 1
	mygraph arc insert v3 v4 v3v4
	mygraph arc set v3v4 throughput 5
	mygraph arc insert v4 v1 v4v1
	mygraph arc set v4v1 throughput 6
	mygraph arc insert v4 v2 v4v2
	mygraph arc set v4v2 throughput 9
	mygraph arc insert v4 v3 v4v3
	mygraph arc set v4v3 throughput 1
	mygraph arc insert t v4 tv4
	mygraph arc set tv4 throughput 10
	mygraph arc insert t v3 tv3
	mygraph arc set tv3 throughput 9
	
	return
d2604 9
a2612 9
	#Flow network for maximum flow computation problems and generally flow problems.
	#Used by:
	#Dinic's Maximum Flow Algorithm
	#Dinic's Blocking Flow Algorithm
	#MKM (3 Hindu) Blocking Flow Algorithm
	
	graph mygraph
	
	mygraph node insert s v1 v2 v3 v4 t
d2614 20
a2633 20
	mygraph arc insert s v1 sv1
	mygraph arc set sv1 throughput 10
	mygraph arc insert s v2 sv2
	mygraph arc set sv2 throughput 10
	mygraph arc insert v1 v2 v1v2
	mygraph arc set v1v2 throughput 2
	mygraph arc insert v2 v4 v2v4
	mygraph arc set v2v4 throughput 9
	mygraph arc insert v1 v4 v1v4
	mygraph arc set v1v4 throughput 8
	mygraph arc insert v1 v3 v1v3
	mygraph arc set v1v3 throughput 4
	mygraph arc insert v4 v3 v4v3
	mygraph arc set v4v3 throughput 6
	mygraph arc insert v3 t v3t
	mygraph arc set v3t throughput 10
	mygraph arc insert v4 t v4t
	mygraph arc set v4t throughput 10
	
	return
d2639 7
a2645 7
	
	#Used by:
	#BFS algorithm
	#Shortest Pathfinding by BFS algorithm
	
	graph mygraph
	mygraph node insert s a b c d x
d2647 14
a2660 14
	mygraph arc insert s a sa
	mygraph arc setweight sa 4
	mygraph arc insert s x sx
	mygraph arc setweight sx 5
	mygraph arc insert a b ab
	mygraph arc setweight ab 5
	mygraph arc insert x d xd
	mygraph arc setweight xd 7
	mygraph arc insert x a xa
	mygraph arc setweight xa -3
	mygraph arc insert b d bd
	mygraph arc setweight bd 2
	mygraph arc insert b c bc
	mygraph arc setweight bc 6
d2662 1
a2662 1
	return
d2669 33
a2701 33
	#Used by:
	#BFS algorithm
	#Shortest Pathfinding by BFS algorithm
	
	graph mygraph
	mygraph node insert s a b c d t
	
	mygraph arc insert s d sd
	mygraph arc setweight sd 9
	mygraph arc insert s a sa
	mygraph arc setweight sa 15
	mygraph arc insert a c ac
	mygraph arc setweight ac 3
	mygraph arc insert a b ab
	mygraph arc setweight ab 35
	mygraph arc insert b a ba
	mygraph arc setweight ba 16
	mygraph arc insert b c bc
	mygraph arc setweight bc 6
	mygraph arc insert b t bt
	mygraph arc setweight bt 21
	mygraph arc insert c t ct
	mygraph arc setweight ct 7
	mygraph arc insert c d cd
	mygraph arc setweight cd 2
	mygraph arc insert d c dc
	mygraph arc setweight dc 2
	mygraph arc insert d a da
	mygraph arc setweight da 4
	mygraph arc insert t b tb 
	mygraph arc setweight tb 5
	
	return
d2708 6
a2713 6
	#Used by:
	#TSP heuristics of local searching - 2 approximation algorithm
	upvar $C _C
	
	graph mygraph
	mygraph node insert a b c d e
d2715 20
a2734 20
	mygraph arc insert a b ab
	mygraph arc set ab weight 11
	mygraph arc insert a c ac
	mygraph arc set ac weight 16
	mygraph arc insert a d ad
	mygraph arc set ad weight 28
	mygraph arc insert a e ae
	mygraph arc set ae weight 42
	mygraph arc insert b c bc
	mygraph arc set bc weight 44
	mygraph arc insert b d bd
	mygraph arc set bd weight 31
	mygraph arc insert b e be
	mygraph arc set be weight 27
	mygraph arc insert c d cd
	mygraph arc set cd weight 6
	mygraph arc insert c e ce
	mygraph arc set ce weight 15
	mygraph arc insert d e de
	mygraph arc set de weight 21
d2736 3
a2738 3
	set _C {ab bc cd de ae}
	
	return
d2752 3
a2754 5
	set message "The input network doesn't have all attributes set correctly... Please, check again attributes: "
	
	append message "\"[join $args "\" and \""]\""
	
	return "$message for input graph."
@


1.9
log
@
	* graphops.tcl: Starting on the integration of Michal
	* graphops.man: Antoniewski's (<antoniewsli@@gmail.com>) work on
	* graphops.test: graph operations for GSoC 2009. Added all
	* graphops.man: operations, and their documentation. Version
	* graphops.tcl: bumped to 0.10. The graphops package now requires
	* graphops.test: Tcl 8.5. The testsuite requires tcltest v2.
	* pkgIndex.tcl: Extended setup commands for upcoming new tests.
	* graph/tests/XOpsSetup: The package and tests now require
	* graph/tests/ops/adjmatrix.test: struct::tree, another package
	* graph/tests/ops/bipartite.test: with acceleration via critcl.
	* graph/tests/ops/bridge.test: Testsuite updated to switch its
	* graph/tests/ops/componentof.test: implementations well. The
	* graph/tests/ops/components.test: testsuites for the new
	* graph/tests/ops/connected.test: commands will be added
	* graph/tests/ops/cutvertex.test: incrementally over the next
	* graph/tests/ops/diameter.test: days.
	* graph/tests/ops/dijkstra.test:
	* graph/tests/ops/distance.test:
	* graph/tests/ops/eccentricity.test:
	* graph/tests/ops/eulerpath.test:
	* graph/tests/ops/eulertour.test:
	* graph/tests/ops/kruskal.test:
	* graph/tests/ops/maxmatching.test:
	* graph/tests/ops/prim.test:
	* graph/tests/ops/radius.test:
	* graph/tests/ops/tarjan.test:
@
text
@d7 1
a7 1
# RCS: @@(#) $Id: XOpsSetup,v 1.8 2008/11/19 07:39:33 andreas_kupries Exp $
d1362 1
a1362 1
	set edges "edge14 edge41 edge13"
d2738 1
a2738 1
	lappend _C ab bc cd de ae
@


1.8
log
@
	* graphops.tcl: Continued integration of graph algorithms. Node
	* graphops.man: distances, dijkstra's algorithm. Bumped the
	* graph/tests/ops/disjkstra.test: package version to 0.8.
	* graph/tests/XOpsControl:
	* graph/tests/XOpsSetup:
	* pkgIndex.tcl:
@
text
@d7 1
a7 1
# RCS: @@(#) $Id: XOpsSetup,v 1.7 2008/11/18 03:49:57 andreas_kupries Exp $
d510 2250
@


1.7
log
@
	* graphops.tcl: Continued integration of graph algorithms. Euler
	* graphops.man: paths and tours. Bumped the package version
	* graph/tests/ops/eulertour.test: to 0.7.
	* graph/tests/ops/eulerpath.test:
	* graph/tests/XOpsControl:
	* graph/tests/XOpsSetup:
	* graph/tests/XOpsSupport:
	* pkgIndex.tcl:
@
text
@d7 1
a7 1
# RCS: @@(#) $Id: XOpsSetup,v 1.6 2008/11/14 04:13:16 andreas_kupries Exp $
d72 1
a72 1
    SETUP-A
@


1.6
log
@
	* graphops.tcl: Continued integration of graph algorithms.
	* graphops.man: Connected components. Bumped package version
	* graph/tests/ops/components.test: to 0.5.
	* graph/tests/ops/componentof.test:
	* graph/tests/XOpsControl:
	* graph/tests/XOpsSetup:
	* graph/tests/XOpsSupport:
	* pkgIndex.tcl:
@
text
@d7 1
a7 1
# RCS: @@(#) $Id: XOpsSetup,v 1.5 2008/11/13 05:36:53 andreas_kupries Exp $
d121 19
d426 63
a488 4
    mygraph arc insert No1 No2
    mygraph arc insert No2 No3
    mygraph arc insert No3 No4
    mygraph arc insert No4 No2
d490 16
a505 1
    mygraph arc insert No5 No5
@


1.5
log
@
	* graphops.tcl: Continued integration of graph algorithms.
	* graphops.man: SCCs via Tarjan. Placeholder for max matching.
	* graph/tests/ops/tarjan.test: Bumped version to 0.4.
	* graph/tests/ops/maxmatching.test:
	* graph/tests/XOpsControl:
	* graph/tests/XOpsSetup:
	* graph/tests/XOpsSupport:
	* pkgIndex.tcl:
@
text
@d7 1
a7 1
# RCS: @@(#) $Id: XOpsSetup,v 1.4 2008/11/08 09:57:32 andreas_kupries Exp $
d317 100
@


1.4
log
@
	* graphops.tcl: Continued integration of graph algorithms.
	* graphops.man: Test for bipartite graph. Bumped version
	* graph/tests/ops/bipartite.test: to 0.3
	* graph/tests/XOpsControl:
	* graph/tests/XOpsSetup:
	* graph/tests/XOpsSupport:
	* pkgIndex.tcl:
@
text
@d7 1
a7 1
# RCS: @@(#) $Id: XOpsSetup,v 1.3 2008/11/08 06:43:18 andreas_kupries Exp $
d218 1
a219 1
    mygraph arc insert 1b 2w
d223 1
d225 1
a226 2
    mygraph arc insert 3b 2w
    mygraph arc insert 3b 5w
d264 1
a265 1
    mygraph arc insert 1b 2w
d267 2
a268 2
    mygraph arc insert 4w 2b
    mygraph arc insert 4w 3b
d270 1
a270 1
    mygraph arc insert 2b 1w
a272 2
    mygraph arc insert 1w 3b
    mygraph arc insert 3b 2w
d274 2
a302 2
    mygraph arc insert 5w 3b nobridge
    mygraph arc insert 5w 2b
d304 2
a306 2
    mygraph arc insert 4b 4w bridge2
    mygraph arc insert 2w 4b
a307 1
    mygraph arc insert 2w 5b
d309 1
d311 2
@


1.3
log
@
	* graphops.tcl: Continued integration of graph algorithms.
	* graphops.man: Minimum spanning tree/forest as per Prim.
	* graph/tests/ops/prim.test: Bumped version to 0.2
	* graph/tests/XOpsControl:
	* graph/tests/XOpsSetup:
	* pkgIndex.tcl:
@
text
@d7 1
a7 1
# RCS: @@(#) $Id: XOpsSetup,v 1.2 2008/11/07 03:47:33 andreas_kupries Exp $
d122 195
@


1.2
log
@
	* graphops.tcl: Continued integration of graph algorithms.
	* graphops.man: Minimum spanning tree/forest as per Kruskal.
	* graph/tests/ops/kruskal.test:
	* graph/tests/XOpsControl:
	* graph/tests/XOpsSetup:
@
text
@d7 1
a7 1
# RCS: @@(#) $Id: XOpsSetup,v 1.1 2008/11/05 07:28:53 andreas_kupries Exp $
d15 2
d79 42
@


1.1
log
@
	* graphops.tcl: Starting on the integration of Alejandro Paz's
	* graphops.man: (<vidriloco@@gmail.com>) work on graph operations
	* graphops.test: for GSoC 2008. First operation: Adjacency matrix.
	* pkgIndex.tcl:
	* graph/test/XOpsControl:
	* graph/test/XOpsSetup:
	* graph/test/XOpsSupport:
	* graph/test/ops/adjmatrix.test:
@
text
@d7 1
a7 1
# RCS: @@(#) $Id: Xsetup,v 1.2 2008/03/07 06:51:36 andreas_kupries Exp $
d13 63
@

