# Functions for "Graphs and their Groups"

Transpositions := function(n)
    # Purpose: Find all transpositions in the symmetric group of degree n
    # Input: n - integer
    # 
    # Output: T - set containing the transpositions
    #
    local k, m, T;
    T := [];
    for k in [1..n] do
        for m in [k+1..n] do
            AddSet(T, (k,m)); 
        od;
    od;
    return T;
end;

RandomSubset := function(S, k)
    # Purpose: Find a random subset of S of size k
    # Input: S - set
    #        k - integer
    # Output: R - random subset
    #
    local R;
    R := [];
    while Size(R) < k do
        AddSet(R, Random(S));
    od;
    return R;
end;

AdjacentVertices := function(Graph, V)
    # Purpose : Find the vertices of Graph that are adjacent to V
    # Input:  Graph - list of transpositions (edge set)
    #         V - integer (vertex)
    # Output: Adj - set of vertices adjacent to V
    # 
    # Note: The edges meeting V are the transpositions which move V
    #       The adjacent edges are the images of V under these 
    #           transpositions
    #
    local Adj;
    Adj := Set(Filtered(Graph, e -> V^e <> V), f -> V^f);
    return Adj;
end;

Aut := function(Graph, n)
    # Purpose: Compute the group of the graph, Graph,  with n vertices
    # Input: G - subset of the transpositions in Sn
    #        n - integer
    # Output: Grp - subgroup of Sn
    #
    local Grp, S;
    Graph := Set(Graph);
    S := SymmetricGroup(n);
    Grp := Filtered(S, g -> Graph = Set(Graph, x -> x^g));
    return Grp;
end;

BlackBox := function(n, k)
    # Purpose : Find a graph on n vertices and k edges.
    # Input : n, k  - integers
    # Output : reps - list of transpositions
    # Note: The probability that the graph comes from a certain
    #       conjugacy class is the same for every conjugacy class.
    #       Further, 
    local T, C, S, Orbs, rep;
    T := Transpositions(n);
    C := Combinations(T, k);
    S := SymmetricGroup(n);
    Orbs := Orbits(S,C,OnSets);
    rep := Random(Random(Orbs));
    return rep;
end;