Tornado Reference : Tornado Tools

vxColor

NAME

vxColor - graph coloring demo for Tornado

SYNOPSIS

vxColor targetServer [-V.erbose]

DESCRIPTION

This command launches the vxColor demo Graphical User Interface. The vxColor demo is based on a self-stabilizing algorithm for coloring a planar graph. Given a planar graph (a 2D graph with no intersecting arc) and given 6 colors, the aim of the algorithm is to assign each region of the graph a color so that no pair of connected regions (regions sharing a least one arc) can have the same color. The main tasks in the demo are the "controller" task and some number of "region" tasks.

The GUI can be invoked from the command line on the host shell. The following parameter is required and a verbose option is available:

targetServer

A living target server connected to the target to be used.

-V

Turn on verbose mode, which displays important steps of the interaction between host and target.

NOTE

The vxColor demo is based on WTX and a TK-capable interpreter.

LAUNCHING THE DEMO

(1)

Switch on your target system (booting with VxWorks).

(2)

Launch a target server for this target.

(3)

Type the command line. For example, with a Motorola MVME162 board, assuming you named your target server demo162, enter:

    vxColor demo162 

After executing the above steps, your screen should display a window named "Tornado Graph Coloring Demo". The window displays three buttons:

(1)

a toggle that switches debug mode on or off

(2)

a menu button that allows you to select a predefined graph to run the demo with

(3)

a quit button

Debug mode should be turned on to debug the target side of the VxColor demonstration with CrossWind. Turning on debug mode makes the stack size for the graph coloring tasks bigger in order to accomodate the extra space needed by local variable when the code is compiled with the debug option (-g) turned on. The header file of the demo ($WIND_BASE/target/src/demo/color/vxColor.h) contains defines for different target types of the stack sizes of the controller and region tasks, in debug or normal mode. Normal mode demands the least memory and should be used when running the demo on boards with little memory capacity. You can adjust the stack size by editing the header file. Whichever mode you select, remember that you can watch the stack usage with the Tornado browser and that a stack overflow can lead to a severe system crash.

When a graph has been selected, the main window displays this graph as a set of colored regions separated with border lines. The window displays a new set of buttons which are contextual controls.

The following gives a description of the contextual controls:

START		Starts a coloring session
COLOR EDIT		Menu for changing region colors:
	- RANDOM	randomly initializes each region's color
	- UNIFORM	uniformly initializes all regions' colors
	- LOCAL	allows editing an individual region's color
NEIGHBORHOOD		Displays each region neighbors (following cursor)
QUIT		Exits the demo

During a coloring session, the contextual controls are:

STOP	Breaks a coloring session
PAUSE	Temporarily halts a coloring session

During a PAUSE, the only contextual control is:

CONTINUE	Resumes a coloring session after a pause

If you press the START button, you can see region colors changing until a steady state is reached. What does all this activity mean and what does the steady state represent?

Actually, each region in the graph has a color attribute and is controlled by a task running on the target. The existing neighborhood relationships within the graph are represented on the target as communication channels between tasks. Thus, the target is populated with a set of tasks that have exchanges between each other. The purpose of these exchanges is to honor a simple rule which says that no neighboring regions can have the same color and that only six (6) different colors are available. This scheme has been proven to be always possible. See "A Self_stabilizing algorithm for Coloring a Planar Graph," by S. Gosh and M.H. Karaata in Distributed Computing (1993) 7:55-59.

When a solution is found, region colors freeze. You can then break this stabilized status by changing some colors using the COLOR EDIT menu. If you select LOCAL mode, choose a new color for any region by clicking on the desired region as many time as necessary (one out of the 6 possible colors will be selected in a ring fashion). When you are satisfied with your changes, press the START button to compute a new coloring scheme.

While coloring is in progress, you can use the STOP and PAUSE buttons. The STOP button lets you break the target's coloring activity; the PAUSE button temporarily suspends this activity so that you can observe the tasks of the demo with various Tornado tools. When PAUSE is on, the only available action is CONTINUE, which resumes the coloring activity.

RECOMPILING THE TARGET MODULE

The demo's target-side building technology uses a simple makefile that requires two parameters settings: one for CPU and the second for TOOL. The CPU and TOOL parameters must be set to a supported architecture value and to a supported toolchain value (the default value of TOOL is "gnu" when omitted).

Examples

To recompile the demo's target module for the listed architectures, enter the following, in the directory target/src/demo/color:

Motorola 68040 board:

    make CPU=MC68040

Solaris simulator:

    make CPU=SIMSPARCSOLARIS

Intel i960CA board:

    make CPU=I960CA 

To produce debugging information:

(1)

Recompile the demo's target module (as described here above).

(2)

Edit the command line produced in (1) to change the optimization flag to -g.

(3)

Execute this modified command line.

ENVIRONMENT VARIABLES

WIND_BASE

root location of the Tornado tree.

WIND_REGISTRY

host on which the Tornado Registry daemon runs (see wtxregd).

FILES

The following files are required by the vxColor demo:

$WIND_BASE/host/WIND_HOST_TYPE/bin/wtxwish

WTX protocol capable TK interpreter.

$WIND_BASE/host/WIND_HOST_TYPE/bin/vxColor

shell script invoking wtxwish to interpret demoHost.tk.

$WIND_BASE/host/src/demo/color/demoHost.tk

demo host GUI.

$WIND_BASE/host/src/demo/color/United-States

a planar graph representing the border states of the USA.

$WIND_BASE/host/src/demo/color/FranceRegions

a planar graph representing the border regions of France.

$WIND_BASE/host/src/demo/color/Wheel

a simple planar graph.

$WIND_BASE/target/lib/objCPUTOOLtest/vxColor.o

a CPU specific demo object module.

BUGS

If the NumLock key is on, the demo will hang.

SEE ALSO

vxColor, tgtsvr, Tornado User's Guide: Whirlwind Tour