Learn how easy it is to sync an existing GitHub or Google Code repo to a SourceForge project! See Demo

Close

#312 struct::graph:op::toAdjacencyMatrix issues

open
5
2009-06-03
2009-06-03
Lars Hellström
No

Things that strike me as wrong with [struct::graph:op::toAdjacencyMatrix], just from reading the documentation:

1. The return value is a matrix which mixes two element interpretations: node name and arc existence. Better would be to return a pair where the first element is the pure adjacency matrix and the second is the list of node names. Also, it is often useful to force an order of nodes, rather than work with what one is given; there should be an option which takes a list of node names as value which has the effect that it will be a prefix of the returned list of all node names.

2. Matrix elements are documented as being "True" or "False". The canonical boolean string representations 1 or 0 would be more useful.

3. The command ignores arc direction and multiplicity. This should rather be controlled through options, as several important applications of the adjacency matrix (e.g. counting walks of given length) requires that one takes them into account.

4. Indeed, as there are many ways of combinig parallel arcs, one could even consider an option which takes as value a command prefix for this. A suitable syntax for this command prefix could be

{*}$prefix $graph $arclist

where the $arclist is the list of names of arcs that are to be combined, and the return value will be the adjacency matrix element. The multiplicity-counting prefix could then be

{::apply {{G arclist} (llength $arclist}}}

whereas one that calculates the combined capacities could be

{::apply {{attr G arclist} (
set res 0
foreach arc $arclist {
set res [expr {$res + [$G arc get $arc $attr]}]
}
return $res
}}} capacity

All in all, this is so much that maybe it is better to make a completely new adjacency matrix command.

Discussion