Are there *practical* ways to construct the [Szemerédi partitions](http://en.wikipedia.org/wiki/Szemer%C3%A9di_regularity_lemma) of a given graph (on a computer)? I found [this algorithmic version](http://en.wikipedia.org/wiki/Algorithmic_version_for_Szemer%C3%A9di_regularity_partition) of the lemma (also see the references within), but I was unable to find any implementations, so I am wondering if these algorithms are practical at all.


Please note that I am not a mathematician and I am very new to this topic. I am trying to find out if it this will be useful for me. I was hoping that someone familiar with the field will be able to provide some guidance and help avoid a likely blind alley.


Also, can partitioning the graph like this recursively be used to define/compute a vertex ordering (ordering = labelling by natural numbers), so that the vertices in the same partition will be adjacent in the ordering?



Constructing Szemerédi partitions on a computer
Most of this information is apparently available through links from Wikipedia, so my apologies if this is not helpful (or useful enough to warrant being an answer).


I highly doubt this can be done in a practical way. The algorithm of Frieze and Kannan requires $O\left(\varepsilon^{-45}\right)$ steps, most of which require a nontrivial amount of work (specifically, step 4 requires $O(n)$ time, where $n$ is the number of vertices in your graph.


I think a larger problem is the size of the graphs required to apply the regularity lemma. [This paper by Gowers](http://www.springerlink.com/content/xndpevxb8p10awxb/) shows a lower bound on M similar to a tower of 2's of height $\log\left(\varepsilon^{-5}\right)$. Since, say, a tower of five 2's is far larger than the number of bits available to a computer for memory, there will be considerable trouble representing a graph with this many vertices in the first place.


