[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...

<<categories>> Graph Theory | Arts and crafts of Tcl-Tk programming | Mathematics