<commit_before>package Alg.Kernelization;

import org.jgrapht.Graphs;
import org.jgrapht.graph.DefaultEdge;
import org.jgrapht.graph.Multigraph;

import java.util.*;

/**
 * Created on 5/24/2016.
 *
 * Instead of using brute force to go through an enormous search space,
 * we used simple observations to reduce the search space to a manageable size.
 * This algorithmic technique, using reduction rules to decrease the size
 * of the instance, is called kernelization,
 */

/*
//==================//
// Reduction Rules: //
//==================//

// Rule 0: The Degree-Zero Rule. (unconnected vertices)
If v is a vertex of degree 0 in G, then delete v.
The parameter k is unchanged.

// Rule 1: The Degree-One Rule. (leafs)
If v is a vertex of degree 1 in G, then delete v.
The parameter k is unchanged.

// Rule 2: The Degree-Two Rule.
If v is a vertex of degree 2 in G, with neighbors a and b
(allowing possibly a = b), then modify G by replacing v and its
two incident edges with a single edge between a and b
(or a loop on a = b, in which case Rule 3 will remove it).
The parameter k is unchanged.

// Rule 3: The Loop Rule. (self-loops)
If there is a loop on a vertex v then take v into the solution set,
and reduce to the instance (G − v, k − 1).

// Rule 4: Multiedge Reduction.
If there are more than two edges between u and v then delete all
but two of these.
The parameter k is unchanged.


(From the paper: A 4k^2 kernel for feedback vertex set]

// Rule 5 Center of flower Paths
If there exists an x-flower F of order p and a set of
q pairwise disjoint cycles which are moreover disjoint
from F such that p + q ≥ k + 1, we reduce to G^n := G \ x
and k' := k − 1.

// Rule 6 ??
If there is a set of vertices X, a vertex x ∈ V \ X and a set
of connected components C of G \ (X ∪ x) [not necessarily all
the connected components] such that:
• There is exactly one edge between x and every C ∈ C.
• Every C ∈ C induces a tree.
• For every subset Z ⊆ X, the number of components of C having
some neighbor in Z is at least 2|Z|.
Then one can form a graph G0 by joining x to every vertex of X
by double edges, and removing the edges between x and the
components of C. We then reduce to G' and k' := k
*/

    /* return ReductionSolution:
    boolean stillPossible;
    ArrayList<Integer> verticesToRemoved;
    int reducedK;
    Multigraph reducedGraph;
    */

public class Kernelization {

    public static ReductionSolution kernelize(Multigraph<Integer, DefaultEdge> graph, int k) {
        return kernelize(graph, k, true);
    }

    /**
     * Applies Rule 0 and 1 to the graph. Mainly meant for outside usage.
     *
     * @param solution
     * @param graph
     * @return
     */
    public static boolean rule0and1(ReductionSolution solution, Multigraph<Integer, DefaultEdge> graph)
    {
        Integer[] vertices = (graph.vertexSet()).toArray(new Integer[graph.vertexSet().size()]);
        return Kernelization.rule0and1(solution, graph, vertices);

    }

    /**
     * Fast application of rule 0 and 1 to the graph, where the set of verties is already extracted. Is faster than
     * the other rule0and1 method therefore
     */
    public static boolean rule0and1(ReductionSolution solution, Multigraph<Integer, DefaultEdge> graph, Integer[] vertices)
    {
        boolean changed = false;
        for (int v:vertices) {        //Returns the degree of the specified vertex.
            int degree = graph.degreeOf(v); // swap vertex "v" with actual vertex identifier

            // Rule 0 & Rule 1
            if (degree <= 1) {
                Kernelization.removeVertex(solution, v, false);
                changed = true;
            }
        }
        return changed;
    }

    public static boolean rule2(ReductionSolution solution, Multigraph<Integer, DefaultEdge> graph)
    {
        Integer[] vertices = (graph.vertexSet()).toArray(new Integer[graph.vertexSet().size()]);
        return Kernelization.rule2(solution, graph, vertices);

    }

    /**
     * Fast application of rule 2
     *
     * @param solution
     * @param graph
     * @param vertices
     * @return
     */
    public static boolean rule2(ReductionSolution solution, Multigraph<Integer, DefaultEdge> graph, Integer[] vertices){
        boolean changed = false;
        for (int v:vertices) {
            int degree = graph.degreeOf(v);
            // Rule 2
            if (degree == 2) {
                //Returns a list of vertices which are adjacent to a specified vertex.
                List<Integer> neighbors = Graphs.neighborListOf(graph, v); // get neighbors a and b of vertex v (allowing possibly a = b)
                int a = neighbors.get(0);
                int b = neighbors.get(1);

                // If the new edge that is places introduces a self loop, then it can be removed,
                if (a == b) {
                    Kernelization.removeVertex(solution, v, true);
                } else {
                    //Creates a new edge in this graph, going from the source vertex to the target vertex, and returns the created edge.
                    graph.addEdge(a, b); // a = sourceVertex, b = targetVertex
                    Kernelization.removeVertex(solution, v, false);
                }

                changed = true;
            }
        }<commit_msg>If removing a vertex creates a self-loop, then the self-loop vertex should be removed from the reduced graph and be added to the solution set, not the other vertex. (In total, both should be removed)<commit_after>package Alg.Kernelization;

import org.jgrapht.Graphs;
import org.jgrapht.graph.DefaultEdge;
import org.jgrapht.graph.Multigraph;

import java.util.*;

/**
 * Created on 5/24/2016.
 *
 * Instead of using brute force to go through an enormous search space,
 * we used simple observations to reduce the search space to a manageable size.
 * This algorithmic technique, using reduction rules to decrease the size
 * of the instance, is called kernelization,
 */

/*
//==================//
// Reduction Rules: //
//==================//

// Rule 0: The Degree-Zero Rule. (unconnected vertices)
If v is a vertex of degree 0 in G, then delete v.
The parameter k is unchanged.

// Rule 1: The Degree-One Rule. (leafs)
If v is a vertex of degree 1 in G, then delete v.
The parameter k is unchanged.

// Rule 2: The Degree-Two Rule.
If v is a vertex of degree 2 in G, with neighbors a and b
(allowing possibly a = b), then modify G by replacing v and its
two incident edges with a single edge between a and b
(or a loop on a = b, in which case Rule 3 will remove it).
The parameter k is unchanged.

// Rule 3: The Loop Rule. (self-loops)
If there is a loop on a vertex v then take v into the solution set,
and reduce to the instance (G − v, k − 1).

// Rule 4: Multiedge Reduction.
If there are more than two edges between u and v then delete all
but two of these.
The parameter k is unchanged.


(From the paper: A 4k^2 kernel for feedback vertex set]

// Rule 5 Center of flower Paths
If there exists an x-flower F of order p and a set of
q pairwise disjoint cycles which are moreover disjoint
from F such that p + q ≥ k + 1, we reduce to G^n := G \ x
and k' := k − 1.

// Rule 6 ??
If there is a set of vertices X, a vertex x ∈ V \ X and a set
of connected components C of G \ (X ∪ x) [not necessarily all
the connected components] such that:
• There is exactly one edge between x and every C ∈ C.
• Every C ∈ C induces a tree.
• For every subset Z ⊆ X, the number of components of C having
some neighbor in Z is at least 2|Z|.
Then one can form a graph G0 by joining x to every vertex of X
by double edges, and removing the edges between x and the
components of C. We then reduce to G' and k' := k
*/

    /* return ReductionSolution:
    boolean stillPossible;
    ArrayList<Integer> verticesToRemoved;
    int reducedK;
    Multigraph reducedGraph;
    */

public class Kernelization {

    public static ReductionSolution kernelize(Multigraph<Integer, DefaultEdge> graph, int k) {
        return kernelize(graph, k, true);
    }

    /**
     * Applies Rule 0 and 1 to the graph. Mainly meant for outside usage.
     *
     * @param solution
     * @param graph
     * @return
     */
    public static boolean rule0and1(ReductionSolution solution, Multigraph<Integer, DefaultEdge> graph)
    {
        Integer[] vertices = (graph.vertexSet()).toArray(new Integer[graph.vertexSet().size()]);
        return Kernelization.rule0and1(solution, graph, vertices);

    }

    /**
     * Fast application of rule 0 and 1 to the graph, where the set of verties is already extracted. Is faster than
     * the other rule0and1 method therefore
     */
    public static boolean rule0and1(ReductionSolution solution, Multigraph<Integer, DefaultEdge> graph, Integer[] vertices)
    {
        boolean changed = false;
        for (int v:vertices) {        //Returns the degree of the specified vertex.
            int degree = graph.degreeOf(v); // swap vertex "v" with actual vertex identifier

            // Rule 0 & Rule 1
            if (degree <= 1) {
                Kernelization.removeVertex(solution, v, false);
                changed = true;
            }
        }
        return changed;
    }

    public static boolean rule2(ReductionSolution solution, Multigraph<Integer, DefaultEdge> graph)
    {
        Integer[] vertices = (graph.vertexSet()).toArray(new Integer[graph.vertexSet().size()]);
        return Kernelization.rule2(solution, graph, vertices);

    }

    /**
     * Fast application of rule 2
     *
     * @param solution
     * @param graph
     * @param vertices
     * @return
     */
    public static boolean rule2(ReductionSolution solution, Multigraph<Integer, DefaultEdge> graph, Integer[] vertices){
        boolean changed = false;
        for (int v:vertices) {
            int degree = graph.degreeOf(v);
            // Rule 2
            if (degree == 2) {
                //Returns a list of vertices which are adjacent to a specified vertex.
                List<Integer> neighbors = Graphs.neighborListOf(graph, v); // get neighbors a and b of vertex v (allowing possibly a = b)
                int a = neighbors.get(0);
                int b = neighbors.get(1);

                // If the new edge that is places introduces a self loop, then it can be removed,
                // also remove the "self-loop vertex" and add it to the solution
                if (a == b) {
                    Kernelization.removeVertex(solution, v, false);
                    Kernelization.removeVertex(solution, a, true);
                } else {
                    //Creates a new edge in this graph, going from the source vertex to the target vertex, and returns the created edge.
                    graph.addEdge(a, b); // a = sourceVertex, b = targetVertex
                    Kernelization.removeVertex(solution, v, false);
                }

                changed = true;
            }
        }
{'fraction_non_alphanumeric': 0.08893154190658989, 'fraction_numerical': 0.008774335069920482, 'mean_word_length': 2.4397988054071047, 'pattern_counts': {'":': 0, '<': 19, '<?xml version=': 0, '>': 17, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3299872', 'n_tokens_mistral': 3125, 'n_tokens_neox': 2908, 'n_words': 1394}