 a/sage/groups/perm_gps/partn_ref/refinement_graphs.pyx
+++ b/sage/groups/perm_gps/partn_ref/refinement_graphs.pyx
@@ 22,17 +22,20 @@
INPUT:
G_in  a Sage graph
partition  a list of lists representing a partition of the vertices
 lab  if True, return the canonical label in addition to the automorphism
 group.
 dig  if True, does not use Lemma 2.25 in [1], and the algorithm is valid
 for digraphs and graphs with loops.
 dict_rep  if True, explain which vertices are which elements of the set
 {1,2,...,n} in the representation of the automorphism group.
 certify  if True, return the relabeling from G to its canonical
 label.
+ lab  if True, compute and return the canonical label in addition to the
+ automorphism group.
+ dig  set to True for digraphs and graphs with loops. If True, does not
+ use optimizations based on Lemma 2.25 in [1] that are valid only for
+ simple graphs.
+ dict_rep  if True, return a dictionary with keys the vertices of the
+ input graph G_in and values elements of the set the permutation group
+ acts on. (The point is that graphs are arbitrarily labelled, often
+ 0..n1, and permutation groups always act on 1..n. This dictionary
+ maps vertex labels (such as 0..n1) to the domain of the permutations.)
+ certify  if True, return the permutation from G to its canonical label.
verbosity  currently ignored
use_indicator_function  option to turn off indicator function
 (False > slower)
+ (True is generally faster)
sparse  whether to use sparse or dense representation of the graph
(ignored if G is already a CGraph  see sage.graphs.base)
base  whether to return the first sequence of split vertices (used in
@@ 314,7 +317,7 @@
return tuple(return_tuple)
cdef int refine_by_degree(PartitionStack *PS, object S, int *cells_to_refine_by, int ctrb_len):
 """
+ r"""
Refines the input partition by checking degrees of vertices to the given
cells.
@@ 325,12 +328,14 @@
question, and some flags.
cells_to_refine_by  a list of pointers to cells to check degrees against
in refining the other cells (updated in place)
 ctrb_len  how many cells in the above
+ ctrb_len  how many cells in cells_to_refine_by
OUTPUT:
 An invariant, such that if the function is called with a permutation of the
 situation (i.e. there is a gamma taking one graph to the other, which also
 takes one partition to the other), the same number is returned.
+
+ An integer invariant under the orbits of $S_n$. That is, if $\gamma$ is a
+ permutation of the vertices, then
+ $$ I(G, PS, cells_to_refine_by) = I( \gamma(G), \gamma(PS), \gamma(cells_to_refine_by) ) .$$
+
"""
cdef GraphStruct GS = S
cdef CGraph G = GS.G
@@ 425,8 +430,12 @@
return 0
cdef int compare_graphs(int *gamma_1, int *gamma_2, object S):
 """
 Compare gamma_1(G) and gamma_2(G), returning 0 iff gamma_1(G) == gamma_2(G).
+ r"""
+ Compare gamma_1(G) and gamma_2(G).
+
+ Return return 1 if gamma_1(G) < gamma_2(G), 0 if gamma_1(G) ==
+ gamma_2(G), 1 if gamma_1(G) > gamma_2(G). (Just like the python
+ \code{cmp}) function.
INPUT:
gamma_1, gamma_2  list permutations (inverse)
@@ 447,9 +456,12 @@
cdef bint all_children_are_equivalent(PartitionStack *PS, object S):
"""
 Returns True if any refinement of the current partition results in the same
 structure. Converse does not hold in general.

+ Return True if every refinement of the current partition results in the
+ same structure.
+
+ WARNING:
+ Converse does not hold in general! See Lemma 2.25 of [1] for details.
+
INPUT:
PS  the partition stack to be checked
S  a graph struct object
@@ 606,8 +618,23 @@
"""
Tests to make sure that C(gamma(G)) == C(G) for random permutations gamma
and random graphs G.

 DOCTEST:
+
+ INPUT:
+ t  run tests for approximately this many seconds
+ n_max  test graphs with at most this many vertices
+ perms_per_graph  test each graph with this many random permutations
+
+ DISCUSSION:
+
+ Until t seconds have elapsed, this code generates a random graph G on at
+ most n_max vertices. The density of edges is chosen randomly between 0
+ and 1.
+
+ For each graph G generated, we uniformly generate perms_per_graph random
+ permutations and verify that the canonical labels of G and the image of G
+ under the generated permutation are equal.
+
+ TESTS:
sage: import sage.groups.perm_gps.partn_ref.refinement_graphs
sage: sage.groups.perm_gps.partn_ref.refinement_graphs.random_tests()
All passed: ... random tests on ... graphs.