See:
Combinatorial algorithms: an update,
Herbert S. Wilf, Albert Nijenhuis
SIAM, 1989. Chapter 8: Generating Random Graphs.
The chapter gives an algorithm for producing an undirected graph uniformly over all graphs of size $n$. It is based on Polya counting. Computing the enumerating polynomial depends on some group theory that is time consuming (I don't know the complexity class, but I'll just conjecture it is most likely exponential space on $n$). But it is a guarantee of uniform distribution. Unfortunately I don't know of a way (I haven't heard of a way) to derandomize this to create an unranking algorithm (to give a mapping from the naturals to the set of unlabeled graphs).
The algorithm presented in your link (by de Wet) is cute (I mean that in the sense that it is cleverly simple, does not lie, but doesn't really give the meat of it, what it means to have a list of non-isomorphic graphs). The graphs created there have a very particular structure (two paths with an arbitrary subset of edges between the paths, plus some small widgets on one end of each path to break symmetry. All subsets is a good trick but having two paths is pretty uncommon and $sqrt{T_n}over T_n$ goes to 0 as $n$ grows.
As to practicality, in addition to the suggestions of nauty and Sage, there's also Mathematica (commercial) which has a list (that you can manipulate) of graphs up to size 11.
No comments:
Post a Comment