Arjen Markus In response to a question on the c.l.t. by George Petasis I decided to have a go with plotting an arbitrary simple graph automatically. The idea is that the graph is defined completely by its edges and that the actual plotting can be done by using predefined arrangements of the vertices.
This is an almost trivial exercise - not scalable to hundreds of vertices, I am sure and it does not take into account that certain graphs require an arrangement that reflects their purpose - for instance: a graph representing the flow of data through a program.
So, with all its apparent and less apparent limitations, here is my solution (oh, it is unfinished, in the sense that I have made provisions for much more possibilities, but they are not yet implemented).
(DKF notes that for complex graphs, the BLT extension is the definitive answer. )
AM I meant graphs like the roads between cities or the control flow in a procedure, rather than xy plots and the like. If BLT can do that too, I was unaware of it
Lars H Drawing a graph so that it looks good is a very hard problem; it is pretty much the case any method one can cook up will do a very poor job on almost all graphs!
The usual approach is instead to have one data structure for "abstract graph" (vertices do not have any coordinates) and another data structure for "geometric graph" (where each vertex has been assigned a coordinate in the plane). Only the latter kind of graph can be drawn (but one can of course arrange things so that abstract graphs are automatically converted to geometric if used as such, for example by using a circular arrangement of the vertices). It is then the responsibility of the user to choose or device an arrangement method that is suitable for the type of graph at hand.
It might also be observed that there are many heuristic methods that seek to improve the positions of the vertices in a given geometric graph, to make it more pleasing to the eye. Several of these start with a physical model of the graph and simulate its development over time. One can for example imagine the graph as a mechanical object, where the vertices are masses and the edges are springs; this seeks to find an arrangement where no edge is unnecessarily long or short. A development of that model is to put an positive electric charge at each vertex, so that the vertices won't sit on top of each other. Those fond of Colliding balls and the like might find this just as intrigueing.
# drawgraph.tcl --
# Script to draw graphs (represented as edgelist) in a canvas
#
# DrawGraph --
# Namespace for the commands
#
namespace eval ::DrawGraph:: {
variable draw_vertex "DrawVertex"
variable draw_edge "DrawEdge"
variable curved 0
variable directed 0
namespace export drawGraph drawGraphCentral drawGraphTree drawGraphCircular
}
# CountVertices --
# Count the number of vertices
# Arguments:
# edgelist List of edges
# Result:
# Number of unique vertices in the edge list
#
proc ::DrawGraph::CountVertices { edgelist } {
set vertices {}
foreach edge $edgelist {
foreach {begin end attrib} $edge {break}
if { [lsearch $vertices $begin] < 0 } {
lappend vertices $begin
}
if { [lsearch $vertices $end] < 0 } {
lappend vertices $end
}
}
return [llength $vertices]
}
# DrawGraphGeneral --
# General procedure to draw a graph
# Arguments:
# canvas Canvas to draw in
# edgelist List of edges
# arrange Type of arrangement (-central, -tree, -bycol, -byrow, -circular)
# ncols Number of columns (in case of circular: number of vertices)
# nrows Number of rows
# curved Curved edges or not
# directed Add arrow head or not
# Result:
# Nothing
# Side effect:
# Graph is drawn according to the specifications
# Note:
# Do not use it directly!
#
proc ::DrawGraph::DrawGraphGeneral { canvas edgelist arrange ncols nrows curved directed } {
variable draw_vertex
variable draw_edge
#
# Create a list of cell centres
# - TODO: ordering according to arrangement
#
if { $arrange != "-circular" } {
set dcellx [expr {[$canvas cget -width]/$ncols}]
set dcelly [expr {[$canvas cget -height]/$nrows}]
}
set coords {}
switch -- $arrange {
"-bycol" {
for { set j 0 } { $j < $nrows } { incr j } {
for { set i 0 } { $i < $ncols } { incr i } {
set x [expr {($i+0.5)*$dcellx}]
set y [expr {($j+0.5)*$dcelly}]
lappend coords $x $y
}
}
}
"-byrow" {
for { set i 0 } { $i < $ncols } { incr i } {
for { set j 0 } { $j < $nrows } { incr j } {
set x [expr {($i+0.5)*$dcellx}]
set y [expr {($j+0.5)*$dcelly}]
lappend coords $x $y
}
}
}
"-circular" {
#
# Number of vertices: in ncols
#
set dphi [expr {2.0*3.1415926/$ncols}]
set xcentre [expr {[$canvas cget -width]/2.0}]
set ycentre [expr {[$canvas cget -height]/2.0}]
set rad [expr {0.5*hypot($xcentre,$ycentre)}]
for { set i 0 } { $i < $ncols } { incr i } {
set x [expr {$xcentre+$rad*sin($i*$dphi)}]
set y [expr {$ycentre-$rad*cos($i*$dphi)}]
lappend coords $x $y
}
}
default {
error "Option unknown or not implemented: $arrange"
}
}
set vertices {}
foreach edge $edgelist {
foreach {begin end attrib} $edge {break}
if { [info exists vertex($begin,x)] } {
set xb $vertex($begin,x)
set yb $vertex($begin,y)
} else {
foreach {xb yb} $coords {break}
set coords [lreplace $coords 0 1]
set vertex($begin,x) $xb
set vertex($begin,y) $yb
lappend vertices $begin
}
if { [info exists vertex($end,x)] } {
set xe $vertex($end,x)
set ye $vertex($end,y)
} else {
foreach {xe ye} $coords {break}
set coords [lreplace $coords 0 1]
set vertex($end,x) $xe
set vertex($end,y) $ye
lappend vertices $end
}
$draw_edge $canvas $xb $yb $xe $ye $directed $curved $attrib
}
foreach vtx $vertices {
set xv $vertex($vtx,x)
set yv $vertex($vtx,y)
$draw_vertex $canvas $xv $yv $vtx
}
}
# DrawVertex --
# Default vertex drawing routine
# Arguments:
# canvas Canvas to draw on
# xv X coordinate
# yv Y coordinate
# name Name of the vertex
# Result:
# None
# Side effect:
# Filled circle drawn at vertex
#
proc ::DrawGraph::DrawVertex { canvas xv yv name } {
$canvas create oval [expr {$xv-3}] [expr {$yv-3}] \
[expr {$xv+3}] [expr {$yv+3}] -fill black
}
# DrawEdge --
# Default edge drawing routine
# Arguments:
# canvas Canvas to draw on
# xb X coordinate begin
# yb Y coordinate begin
# xe X coordinate end
# ye Y coordinate end
# curved Draw a curved edge or not
# directed Draw an arrow head or not
# attrib Attribute of the vertex
# Result:
# None
# Side effect:
# Lien from the beginning to the end
#
proc ::DrawGraph::DrawEdge { canvas xb yb xe ye curved directed attrib } {
if { $directed } {
set arrowtype last
} else {
set arrowtype none
}
set dx [expr {$xe-$xb}]
set dy [expr {$ye-$yb}]
if { ! $curved } {
set xc [expr {$xb+0.5*$dx}]
set yc [expr {$yb+0.5*$dy}]
} else {
set xc [expr {$xb+0.5*$dx-0.1*$dy}]
set yc [expr {$yb+0.5*$dy+0.1*$dx}]
}
$canvas create line $xb $yb $xc $yc $xe $ye -fill black \
-arrow $arrowtype -smooth $curved
}
# drawGraph --
# Drawing procedure (driver) for graphs using row or column arrangement
# Arguments:
# canvas Canvas to draw on
# edgelist List of edges
# arrange Arrangement by row (-byrow) or by column (-bycol)
# number Number of rows or columns
# Result:
# None
# Side effect:
# Graph drawn in canvas
#
proc ::DrawGraph::drawGraph { canvas edgelist arrange number } {
variable curved
variable directed
set number_vertices [CountVertices $edgelist]
switch -- $arrange {
"-byrow" { set nrows $number
set ncols [expr {($number_vertices+$nrows-1)/$nrows}]
}
default { set arrange "-bycol"
set ncols $number
set nrows [expr {($number_vertices+$ncols-1)/$ncols}]
}
}
DrawGraphGeneral $canvas $edgelist $arrange $ncols $nrows $curved $directed
}
# drawGraphCircular --
# Drawing procedure (driver) for graphs using circular arrangement
# Arguments:
# canvas Canvas to draw on
# edgelist List of edges
# Result:
# None
# Side effect:
# Graph drawn in canvas
#
proc ::DrawGraph::drawGraphCircular { canvas edgelist } {
variable curved
variable directed
set number_vertices [CountVertices $edgelist]
set arrange "-circular"
DrawGraphGeneral $canvas $edgelist $arrange $number_vertices 0 $curved $directed
}
# main --
# Testing the routines
#
set test 1
if { [file tail $::argv0] == [info script] || $test == 1 } {
namespace import -force ::DrawGraph::*
set edgelist { {A B} {A C} {A D} {A E} {B E} {D F} {C D} {C B} }
canvas .c1 -bg white -width 200 -height 200
canvas .c2 -bg white -width 200 -height 200
canvas .c3 -bg white -width 200 -height 200
canvas .c4 -bg white -width 200 -height 200
grid .c1 .c2
grid .c3 .c4
::DrawGraph::DrawGraphGeneral .c1 $edgelist -bycol 2 3 1 1
::DrawGraph::drawGraph .c2 $edgelist -bycol 3
::DrawGraph::drawGraph .c3 $edgelist -byrow 3
::DrawGraph::drawGraphCircular .c4 $edgelist
}