Some Stuff

The previous post mentioned the restricted weak composition (RWC), but didn't expand on it at all! Basically, I found this excellent paper : " Generalized Algorithm for Restricted Weak Composition Generation " by Daniel R. Page. It even gave some java code in an appendix - good stuff :) Anyway, a RWC is a composition (which is a partition where order matters) that is weak  - has zeros in it - and the parts are restricted . So [1, 0, 1, 1] is a weak composition of 3 into 4 parts and lets say we have restricted the parts to {0, 1, 2}. Here is an overview of the scheme: where we take a degree sequence, convert to a multiset and use a RWC to get a particular sub-multiset. This allows us to take some count of some subset of elements from the multiset. Doing this for all sub-multisets at each round should then allow us to list graphs - although not without redundant examples:  This shows all starting points for 3 -> [3, 2, 2, 1, 1] and

So in the last post about listing trees  I outlined a slightly cumbersome method to list trees from degree sequences. Thinking about it a bit more, it would probably be far easier to just list all trees on some number of vertices and filter out by degree sequence. I talked a little about the WROM algorithm in this old post  which is a constant time generator of 'free' (unlabelled) trees. Anyway, that's boring so I was trying out the more complicated approach. It looks like generating a single  tree from a degree sequence is as simple as the Havel-Hakimi method. Connect the largest degree (dn) to the dn next largest degrees.  Also maintain a list of vertices that have already been connected to, and then at the next step connect only to those not already connected to. So, for [3, 3, 2, 1, 1, 1, 1] we get: You might notice that trees a) and c) are isomorphic. Below the trees labelled by degree are the same trees labelled by DFS discovery order, and below that the '

Although stack overflow is generally just an endless source of questions on the lines of "HALP plz give CODES!? ... NOT homeWORK!! - don't close :(" occasionally you get more interesting ones. For example this one  that asks about degree-restricted trees. Also there's some stuff about vertex labelling, but I think I've slightly missed something there. In any case, lets look at the simpler problem : listing non-isomorphic trees with max degree 3. It's a nice small example of a general approach that I've been thinking about. The idea is to: Given N  vertices, partition 2(N - 1) into N parts of at most 3 -> D = {d0, d1, ... } For each d_i in D, connect the degrees in all possible ways that make trees. Filter out duplicates within each set generated by some d_i. Hmm. Sure would be nice to have maths formatting on blogger.... Anyway, look at this example for partitioning 12 into 7 parts: At the top are the partitions, in the middle the trees