## A graph generator

Richard Suchenwirth - As another part of Graph theory in Tcl, here's a routine that produces a graph description (list of edges like x,y, where x and y are the adjacent vertices; edges are labeled here as increasing integers) for complete r-partite graphs. You specify the number of partitions (what is written as exponent to K in textbooks) and optionally the size of each partition (conventionally subscript to K, defaults to 1):

``` proc graphK {nPartitions {sizeOfPartition 1}} {
set partitions {}
set no 0
for {set i 0} {\$i<\$nPartitions} {incr i} {
set partition {}
for {set j 0} {\$j<\$sizeOfPartition} {incr j} {
lappend partition [incr no]
}
lappend partitions \$partition
}
foreach p \$partitions {
foreach p2 \$partitions {
if {\$p==\$p2} continue ;# no edges inside a partition
foreach vertex \$p {
foreach v2 \$p2 {
if {\$vertex>\$v2} break
lappend res \$vertex,\$v2
}
}
}
}
set res
}```

Now testing with the two minimal non-planar graphs, that cannot be drawn on a flat surface without crossing edges:

``` 0 % graphK 5   ;# pentagram in a pentagon
1,2 1,3 1,4 1,5 2,3 2,4 2,5 3,4 3,5 4,5
0 % graphK 2 3 ;# "Gas-Water-Electricity" graph
1,4 1,5 1,6 2,4 2,5 2,6 3,4 3,5 3,6```

What is so different about Tcl that it that I enjoy writing such algorithms at breakfast? - One of these weekends I will of course pipe the graph generator's output into a graph layouter - that's what these seemingly academic exercises are really aiming at...

 Category Graph theory Arts and Crafts of Tcl-Tk Programming Category Mathematics