[Tcllib-devel] struct::graph API functional groups

[Lars H. <Lar...@re...>]

The struct::graph::op manpage says

    Despite being a companion the package is not directly
    dependent on struct::graph, only on the API defined by
    that package. I.e. the operations of this package can be
    applied to any and all graph objects which provide the
    same API as the objects created through struct::graph.

Now, I suppose this is meant to cover things like cgraph, i.e., C 
reimplementations of struct::graph, but one could also consider 
applying it to things which provide a struct::graph-ish interface even 
though they don't implement all of it. Such a development could be 
furthered if the struct::graph API was split up in smaller pieces, 
since providing all of it is quite a mouthful, and few (if any) 
struct::graph::op commands are likely to exercise all of it.

One basic division that can be made is into broad areas of functionality:

   * Graph structure
   * Attributes, which can be futher split up into:
        - arc attributes
        - node attributes
        - overall graph attributes
   * Weight (which has a separate API, although it is mostly
             like an arc attribute)
   * Object nature (assign, reverse assign, etc.)

A second division which I find it useful to make is that between 
mutating and functional operations, i.e., operations that change the 
graph object versus those that don't, since many graph-ish objects 
would really be images of something else, and thus not necessarily 
support being modified at the graph level. For example, a (partial) 
latin square can be viewed as a (partial) edge-colouring of a bipartite 
graph, but adding an edge between two vertices in the same partition 
doesn't correspond to any operation that can be performed on the latin 
square, so there's no sensible way for a latin square to support the 
"arc insert" operation.

According to these categories, the struct::graph API divides as follows:


Graph structure:
================

Functional:
-----------
graphName arc exists arc
graphName arc source arc
graphName arc target arc
graphName arcs  ? -filter cmdprefix ?   ? 
-in|-out|-adj|-inner|-embedding node node... ?
graphName node degree  ? -in|-out ?  node
graphName node exists node
graphName node opposite node arc
graphName nodes  ? -filter cmdprefix ?   ? 
-in|-out|-adj|-inner|-embedding node node... ?
graphName walk node  ? -order order ?   ? -type type ?   ? -dir 
direction ?  -command cmd

Mutating:
---------
graphName arc delete arc  ? arc ... ?
graphName arc flip arc
graphName arc insert start end  ? child ?
graphName arc rename arc newname
graphName arc move-source arc newsource
graphName arc move-target arc newtarget
graphName arc move arc newsource newtarget
graphName node delete node  ? node... ?
graphName node insert  ? node... ?
graphName node rename node newname
graphName swap node1 node2


Arc attributes:
===============

Functional:
-----------
graphName arc attr key
graphName arc attr key -arcs list
graphName arc attr key -glob globpattern
graphName arc attr key -regexp repattern
graphName arc get arc key
graphName arc getall arc  ? pattern ?
graphName arc keys arc  ? pattern ?
graphName arc keyexists arc key
graphName arcs  ? -key key ?   ? -value value ?

Mutating:
---------
graphName arc append arc key value
graphName arc lappend arc key value
graphName arc set arc key  ? value ?
graphName arc unset arc key


Node attributes:
================

Functional:
-----------
graphName node attr key
graphName node attr key -nodes list
graphName node attr key -glob globpattern
graphName node attr key -regexp repattern
graphName node get node key
graphName node getall node  ? pattern ?
graphName node keys node  ? pattern ?
graphName node keyexists node key
graphName nodes  ? -key key ?   ? -value value ?

Mutating:
---------
graphName node append node key value
graphName node lappend node key value
graphName node set node key  ? value ?
graphName node unset node key


Graph attributes:
=================

Functional:
-----------
graphName get key
graphName getall  ? pattern ?
graphName keys  ? pattern ?
graphName keyexists key

Mutating:
---------
graphName append key value
graphName lappend key value
graphName set key  ? value ?
graphName unset key


Weights:
========

Functional:
-----------
graphName arc getunweighted
graphName arc getweight arc
graphName arc hasweight arc
graphName arc weights

Mutating:
---------
graphName arc setunweighted  ? weight ?
graphName arc setweight arc weight
graphName arc unsetweight arc


Object:
=======

Functional:
-----------
graphName serialize  ? node... ?

Mutating:
---------
graphName = sourcegraph
graphName --> destgraph
graphName deserialize serialization
graphName destroy


As stated above, quite a mouthful! There are however ways to reduce the 
burden.

One thing that can be observed is that attribute management is mostly 
orthogonal to the graph structure; each node or arc is a key to some 
dictionary of attributes, but it matters very little that this key is 
something in the graph. Hence it would be possible to define e.g. a 
snit::type A that adds attribute functionality to a "naked" 
(attribute-less) graph G it owns as a component; methods that care 
about attributes would be handled in A, whereas methods targeting the 
graph structure would be delegated to G.

As an example of such a "naked" graph, here is an ensemble implementing 
(most of) the functional graph structure group for the Petersen graph 
(with 2-subsets of {1,2,3,4,5} as nodes, and pairs of nodes as arcs, 
two nodes being adjacent iff they are disjoint as sets):


namespace eval Petersen {
     namespace export {[a-z]*}
     namespace ensemble create

     namespace eval node {
         namespace export {[a-z]*}
         namespace ensemble create

         proc exists {name} {
             expr {[string match {[1-5] [1-5]} $name] &&\
               [lindex $name 0] < [lindex $name 1]}
         }
         proc degree {args} {
             expr {[llength $args]==1 ? 6 : 3}
         }
         proc opposite {node arc} {
             lindex $arc [expr {[lindex $arc 0] eq $node}]
         }
     }

     proc Disjoint {L1 L2} {
         expr {[llength $L1] + [llength $L2] ==\
           [llength [lsort -unique [concat $L1 $L2]]]}
     }

     proc arc {op name} {
         switch -- $op "source" {
             lindex $name 0
         } "target" {
             lindex $name 1
         } "exists" {
             expr {
                 [string match {{[1-5] [1-5]} {[1-5] [1-5]}} $name] &&
                 [lindex $name 0 0]<[lindex $name 0 1] &&
                 [lindex $name 1 0]<[lindex $name 1 1] &&
                 [Disjoint {*}$name]
             }
         }
     }

     proc nodes {args} {
         if {[llength $args]} then {
             return -code error\
               "Option \"[lindex $args 0]\" not implemented (sorry)"
         }
         set res {}
         foreach i {1 2 3 4 5} {
             foreach j {1 2 3 4 5} {
                 if {$i<$j} then {lappend res [list $i $j]}
             }
         }
         return $res
     }

     proc arcs {args} {
         if {[llength $args]} then {
             switch -- [lindex $args 0] "-in" {
                 set fromL [nodes]
                 set toL [lrange $args 1 end]
             } "-out" {
                 set fromL [lrange $args 1 end]
                 set toL [nodes]
             } "-inner" {
                 set fromL [lrange $args 1 end]
                 set toL [lrange $args 1 end]
             } default {
                 return -code error\
                   "Option \"[lindex $args 0]\" not implemented (sorry)"
             }
         } else {
             set fromL [nodes]
             set toL $fromL
         }
         set res {}
         foreach u $fromL {
             foreach v $toL {
                 if {[Disjoint $u $v]} then {
                     lappend res [list $u $v]
                 }
             }
         }
         return $res
     }
}


Missing here is only the "walk" method and some options on the "nodes" 
and "arcs" methods, since dotting all the i's would take us too far 
astray (also, one can make a similar argument about having a wrapper 
provide those). Additionally missing are the mutating parts of the API, 
but that's kind of implicit, since once you start modifying the 
Petersen graph it won't be the Petersen graph anymore!


So where am I going with this?

Well, I was thinking that /if/ a partition of the struct::graph API was 
made /and/ it was documented for each command of struct::graph::op 
which parts it needed /then/ chances would be better that something 
merely struct::graph-ish (like the [Petersen] above) could make use of 
these commands. I have, at times, toyed with an idea for constructing a 
layout that at each step would involve a strongly connected components 
computation -- said components would then be in a graph implicitly 
constructed from the data structure representing a partial layout, and 
thus not sensibly supporting the whole struct::graph API, but the graph 
would change several times as the layout was being filled in -- so in 
order to rely on [struct::graph:op::tarjan] I would have had to know 
(preferably from documentation rather than source-diving) that it could 
make do with the methods I can provide.

OTOH, it can probably be argued that pretty much any struct::graph::op 
command has complexity at least O(V)+O(E), so an initial step copying 
the entire graph into a [struct::graph] wouldn't be dominant anyway. 
But it's not always the asymptotically dominant term that hurts you...

Lars Hellström