<commit_before>package graph.util;

import graph.RegularGraph;
import graph.RegularGraphFactory;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;

/**
 * Created by <NAME> on 04.01.17.
 *
 * This code contains algorithms implementations from
 * <NAME> and <NAME>d article available at
 * http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.55.7124&rep=rep1&type=pdf
 */
public class RegularGraphGenerator {
    public enum ALGORITHMS { ALG_1, ALG_2 }

    private static final String INVALID_DEGREE = "Vertex degree cannot be less than 1.";
    private static final String INVALID_VERTICES_NUMBER = "Number of vertices cannot be less than 0.";
    private static final String INVALID_VERTICES_DEGREE = "Number of vertices times degree must be even.";
    private static final String INVALID_DEGREE_CEILING = "Degree must be at least 1 less than number of vertices";

    private static RegularGraphGenerator instance = new RegularGraphGenerator();

    protected RegularGraphGenerator() {}

    /**
     * Get singleton class instance
     */
    public static RegularGraphGenerator getInstance() { return instance; }

    /**
     * Build random graph with given parameters.
     *
     * @param degree vertices degree
     * @param verticesNumber number of vertices
     * @throws IllegalArgumentException if graph from given parameters cannot be constructed
     */
    public <G extends RegularGraph> G getRandomGraph(Class<G> clazz, int verticesNumber, int degree) throws IllegalArgumentException {
        return getRandomGraph(clazz, verticesNumber, degree, ALGORITHMS.ALG_1);
    }

    /**
     * Build random graph with given parameters.
     *
     * @param degree vertices degree
     * @param verticesNumber number of vertices
     * @param algorithmType which algorithm
     * @throws IllegalArgumentException if graph from given parameters cannot be constructed
     */
    public <G extends RegularGraph> G getRandomGraph(Class<G> clazz,
                                                     int verticesNumber, int degree, ALGORITHMS algorithmType) throws IllegalArgumentException {
        G g;
        if (degree < 1) {
            throw new IllegalArgumentException(INVALID_DEGREE);
        }
        if (verticesNumber < 0) {
            throw new IllegalArgumentException(INVALID_VERTICES_NUMBER);
        }
        if (!(verticesNumber % 2 == 0 || degree % 2 == 0)) {
            throw new IllegalArgumentException(INVALID_VERTICES_DEGREE);
        }
        if (degree > verticesNumber - 1) {
            throw new IllegalArgumentException(INVALID_DEGREE_CEILING);
        }


        switch (algorithmType) {
            case ALG_1:
                g =  getGraphA1(clazz, verticesNumber, degree);
                break;
            case ALG_2:
                g = getGraphA2(clazz, verticesNumber, degree);
                break;
            default:
                return null;
        }

        return g;

    }

    protected <G extends RegularGraph> G getGraphA1(Class<G> clazz, int verticesNumber, int degree) {
        G g;
        do {
            g = RegularGraphFactory.getInstance(clazz, verticesNumber, degree);
            /*
             * Start with nd points {1, 2, ..., nd} (nd even) in verticesNumber groups.
             * Put points = {1, 2, ..., nd} (points denotes the set of unpaired points.)
             */
            Random rand = new Random();
            List<Integer> pairs = new ArrayList<>(verticesNumber * degree +1);
            pairs.add(0);
            List<Integer> points = new LinkedList<>();
            for (int i = 1, nd = verticesNumber * degree; i <= nd; i++) {
                points.add(i);
                pairs.add(0);
            }

            /*
             * Repeat the following until no suitable pair can be found:
             * Choose two random points i and j in points,
             * and if they are suitable, pair i with j and delete i and j from points.
             */
            int i, j, iIndex, jIndex;
            while (existsSuitable(points, pairs, verticesNumber, degree)) {
                iIndex = rand.nextInt(points.size());
                jIndex = rand.nextInt(points.size());
                i = points.get(iIndex);
                j = points.get(jIndex);
                if (areSuitable(i, j, pairs, verticesNumber, degree)) {
                    pairs.set(i, j);
                    pairs.set(j, i);
                    if (iIndex > jIndex) {
                        points.remove(iIndex);
                        points.remove(jIndex);
                    }
                    else {
                        points.remove(jIndex);
                        points.remove(iIndex);
                    }
                }
            }

            /*
             * Create a graph G with edge from vertex r to vertex s if and only if there is a pair
             * containing points in the r'th and s'th groups. If G is degree-regular, output it, otherwise
             * return to Step 1.
             */
            for (int a = 1, nd = verticesNumber * degree + 1; a < nd; a++) {
                if (pairs.get(a) != 0) {
                    g.addEdge(getPointGroup(pairs.get(a), verticesNumber), getPointGroup(a, verticesNumber));
                    pairs.set(pairs.get(a), 0);
                }
            }
        } while (!g.isRegular(degree));

        return g;
    }

    protected boolean existsSuitable(List<Integer> points, List<Integer> pairs, int verticesNumber, int degree) {
        if (points.size() == 0) {
            return false;
        }

        for (int i = 0; i < points.size(); i++) {
            for (int j = 0; j < points.size(); j++) {
                if (areSuitable(points.get(i), points.get(j), pairs, verticesNumber, degree)) {
                    return true;
                }
            }
        }

        return false;
    }

    protected int getPointGroup(int point, int verticesNumber) {
        return point % verticesNumber;
    }

    protected boolean areSuitable(int a, int b, List<Integer> pairs, int verticesNumber, int degree) {
        /*
         * First, we define two points to be suitable
         * if they lie in different groups and no currently existing pair<commit_msg>Improve performance.<commit_after>package graph.util;

import graph.RegularGraph;
import graph.RegularGraphFactory;

import java.util.*;

/**
 * Created by <NAME> on 04.01.17.
 *
 * This code contains algorithms implementations from
 * <NAME> and <NAME>d article available at
 * http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.55.7124&rep=rep1&type=pdf
 */
public class RegularGraphGenerator {
    public enum ALGORITHMS { ALG_1, ALG_2 }

    private static final String INVALID_DEGREE = "Vertex degree cannot be less than 1.";
    private static final String INVALID_VERTICES_NUMBER = "Number of vertices cannot be less than 0.";
    private static final String INVALID_VERTICES_DEGREE = "Number of vertices times degree must be even.";
    private static final String INVALID_DEGREE_CEILING = "Degree must be at least 1 less than number of vertices";

    /**
     * Build random graph with given parameters.
     *
     * @param degree vertices degree
     * @param verticesNumber number of vertices
     * @throws IllegalArgumentException if graph from given parameters cannot be constructed
     */
    public <G extends RegularGraph> G getRandomGraph(Class<G> clazz, int verticesNumber, int degree) throws IllegalArgumentException {
        return getRandomGraph(clazz, verticesNumber, degree, ALGORITHMS.ALG_1);
    }

    /**
     * Build random graph with given parameters.
     *
     * @param degree vertices degree
     * @param verticesNumber number of vertices
     * @param algorithmType which algorithm
     * @throws IllegalArgumentException if graph from given parameters cannot be constructed
     */
    public <G extends RegularGraph> G getRandomGraph(Class<G> clazz,
                                                     int verticesNumber, int degree, ALGORITHMS algorithmType) throws IllegalArgumentException {
        G g;
        if (degree < 1) {
            throw new IllegalArgumentException(INVALID_DEGREE);
        }
        if (verticesNumber < 0) {
            throw new IllegalArgumentException(INVALID_VERTICES_NUMBER);
        }
        if (!(verticesNumber % 2 == 0 || degree % 2 == 0)) {
            throw new IllegalArgumentException(INVALID_VERTICES_DEGREE);
        }
        if (degree > verticesNumber - 1) {
            throw new IllegalArgumentException(INVALID_DEGREE_CEILING);
        }


        switch (algorithmType) {
            case ALG_1:
                g =  getGraphA1(clazz, verticesNumber, degree);
                break;
            case ALG_2:
                g = getGraphA2(clazz, verticesNumber, degree);
                break;
            default:
                return null;
        }

        return g;

    }

    protected <G extends RegularGraph> G getGraphA1(Class<G> clazz, int verticesNumber, int degree) {
        G g;
        do {
            g = RegularGraphFactory.getInstance(clazz, verticesNumber, degree);
            /*
             * Start with nd points {1, 2, ..., nd} (nd even) in verticesNumber groups.
             * Put points = {1, 2, ..., nd} (points denotes the set of unpaired points.)
             */
            Random rand = new Random();
            List<Integer> pairs = new ArrayList<>(verticesNumber * degree +1);
            pairs.add(0);
            List<Integer> points = new LinkedList<>();
            for (int i = 1, nd = verticesNumber * degree; i <= nd; i++) {
                points.add(i);
                pairs.add(0);
            }

            /*
             * Repeat the following until no suitable pair can be found:
             * Choose two random points i and j in points,
             * and if they are suitable, pair i with j and delete i and j from points.
             */
            Integer i, j;
            while (existsSuitable(points, pairs, verticesNumber, degree)) {
                i = getFirstPoint(rand, points, pairs, verticesNumber, degree);
                j = getSecondPoint(rand, points, pairs, verticesNumber, degree);
                System.out.print("v: " + getPointGroup(i, verticesNumber) + ", u: " + getPointGroup(j, verticesNumber));
                if (areSuitable(i, j, pairs, verticesNumber, degree)) {
                    System.out.print(" are suitable.");
                    pairs.set(i, j);
                    pairs.set(j, i);
                    points.remove(i);
                    points.remove(j);
                }

                System.out.println();
            }

            System.out.println("Suitable doesn't exist.");

            /*
             * Create a graph G with edge from vertex r to vertex s if and only if there is a pair
             * containing points in the r'th and s'th groups. If G is degree-regular, output it, otherwise
             * return to Step 1.
             */
            for (int a = 1, nd = verticesNumber * degree + 1; a < nd; a++) {
                if (pairs.get(a) != 0) {
                    g.addEdge(getPointGroup(pairs.get(a), verticesNumber), getPointGroup(a, verticesNumber));
                    pairs.set(pairs.get(a), 0);
                }
            }
        } while (!g.isRegular(degree));

        return g;
    }

    protected Integer getFirstPoint(Random rand, List<Integer> points, List<Integer> pairs, int verticesNumber, int degree) {
        return points.get(rand.nextInt(points.size()));
    }

    protected Integer getSecondPoint(Random rand, List<Integer> points, List<Integer> pairs, int verticesNumber, int degree) {
        return points.get(rand.nextInt(points.size()));
    }




    protected boolean existsSuitable(List<Integer> points, List<Integer> pairs, int verticesNumber, int degree) {
        if (points.size() == 0) {
            return false;
        }

        for (int i = 0; i < points.size(); i++) {
            for (int j = 0; j < points.size(); j++) {
                if (areSuitable(points.get(i), points.get(j), pairs, verticesNumber, degree)) {
                    return true;
                }
            }
        }

        return false;
    }

    protected int getPointGroup(int point, int verticesNumber) {
        return point % verticesNumber;
    }

    protected boolean areSuitable(int a, int b, List<Integer> pairs, int verticesNumber, int degree) {
        /*
         * First, we define two points to be suitable
         * if they lie in different groups and no currently existing pair
{'fraction_non_alphanumeric': 0.0923951670220327, 'fraction_numerical': 0.008054963278843875, 'mean_word_length': 1.930124942156409, 'pattern_counts': {'":': 0, '<': 51, '<?xml version=': 0, '>': 42, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 2, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 6, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '920852', 'n_tokens_mistral': 3401, 'n_tokens_neox': 3221, 'n_words': 1087}