Animation of graph algorithms:
	Dijkstra method for the shortest path problem,
	Kruskal and Prim methods for the minimum spanning tree problem.

NOTE: C compiler and Tcl/Tk should be installed.
NOTE: dijkstra.c is removed from this directory for educational reasons.
NOTE: dijkstra_jikken.c and dp_jikken.c are provided for Suuri-Kogaku Jikken.

dijkstra_jikken.c: Dijkstra method (without heap).
dp_jikken.c:       Simple DP method for the shortest path problem.

drawgraph.tcl:	draw graph (developed by using Tcl/Tk8.0.3)
gengraph.c:	generate instances
dijkstra.c:	Dijkstra method (output in drawgraph.tcl format)
		modified from dijkstra_org.c
dijkstra_org.c:	Dijkstra method coded by T. Ibaraki
kruskal.c:	Kruskal method (output in drawgraph.tcl format)
		modified from kruskal_org.c
kruskal_org.c:	Kruskal method coded by T. Ibaraki
prim.c:		Prim method (output in drawgraph.tcl format)
		modified from prim_org.c
prim_org.c:	Prim method coded by T. Ibaraki
makefile:	compile gengraph.c, dijkstra.c, kruskal.c and prim.c
samplegraph0.dat: sample data for drawgraph.tcl with comments
instruction.txt: details of drawgraph.tcl

Usage ------------------------

Type

	make

then dijkstra, kruskal, prim and gengraph are made. Then type, e.g.,

	gengraph <node_number> <random_seed> | dijkstra > graphdata.dat
	drawgraph.tcl graphdata.dat

then you can see the animation for the Dijkstra method. The usage of
kruskal and prim are similar.

I/O format -------------------

The output format of gengraph is as follows.

 "width of the grid graph"
 "number of nodes"
 "number of edges"
 for each edge:
   "weight" "end node 1" "end node 2"

This format corresponds to the input format of dijkstra.c, kruskal.c and
prim.c.

The input format for drawgraph.tcl is explained in instruction.txt in
Japanese, and an example is given in samplegraph0.dat.

---
Mutsunori YAGIURA   y a g i u r a ＠ i . k y o t o - u . a c . j p