The code for random mate connectivity in NESL is included below. Here are some slides describing the algorithm and code using the same example graph. The argument L is the initial labeling for the graph, which needs to be the sequence [0, 1, ..., n-1], and the argument E is a sequence of edges each represented as its two enpoints, and each edge has to be represented in each direction. The output is returned as a rooted spanning tree for each component, i.e., every vertex points to a parent in the tree.
The example consists of a single component, and an answer such as:
it = [1, 2, 2, 6, 6, 6, 1]
is valid since it represents a tree rooted at vertex 2 (3, 4 and 5 point to 6, 6 and 0 point to 1, and 1 and 2 point to 2). Feel free to change the inputs: for example changing all 0s to 1s in E will disconnect the vertex 0.