<commit_before>/*
 * Copyright 2019 <NAME>
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *   http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 *
 */

package org.nlpub.watset.graph;

import org.jgrapht.Graph;
import org.nlpub.watset.util.Neighbors;

import java.util.*;
import java.util.function.Function;
import java.util.stream.Collectors;

import static java.util.Objects.requireNonNull;
import static org.nlpub.watset.util.Maximizer.argmax;

/**
 * Implementation of the Chinese Whispers algorithm.
 *
 * @see <a href="http://dl.acm.org/citation.cfm?id=1654774">Biemann (TextGraphs-1)</a>
 */
public class ChineseWhispers<V, E> implements Clustering<V> {
    public static <V, E> Function<Graph<V, E>, Clustering<V>> provider(NodeWeighting<V, E> weighting) {
        return graph -> new ChineseWhispers<>(graph, weighting);
    }

    public static <V, E> Function<Graph<V, E>, Clustering<V>> provider(NodeWeighting<V, E> weighting, int iterations, Random random) {
        return graph -> new ChineseWhispers<>(graph, weighting, iterations, random);
    }

    public static final int ITERATIONS = 20;

    protected final Graph<V, E> graph;
    protected final NodeWeighting<V, E> weighting;
    protected final int iterations;
    protected final Random random;
    protected Map<V, Integer> labels;

    protected int steps;

    public ChineseWhispers(Graph<V, E> graph, NodeWeighting<V, E> weighting, int iterations, Random random) {
        this.graph = requireNonNull(graph);
        this.weighting = requireNonNull(weighting);
        this.iterations = iterations;
        this.random = requireNonNull(random);
    }

    public ChineseWhispers(Graph<V, E> graph, NodeWeighting<V, E> weighting) {
        this(graph, weighting, ITERATIONS, new Random());
    }

    /**
     * {@inheritDoc}
     */
    @Override
    public Clustering<V> fit() {
        final List<V> nodes = new ArrayList<>(graph.vertexSet());

        labels = new HashMap<>(nodes.size());

        int i = 0;

        for (final V node : graph.vertexSet()) {
            labels.put(node, i++);
        }

        for (steps = 0; steps < iterations; steps++) {
            Collections.shuffle(nodes, random);

            if (!step(nodes)) break;
        }

        return this;
    }

    /**
     * Performs one iteration of the algorithm.
     *
     * @param nodes node list
     * @return whether the labels changed or not.
     */
    protected boolean step(List<V> nodes) {
        boolean changed = false;

        for (final V node : nodes) {
            final Map<Integer, Double> scores = score(graph, labels, weighting, node);

            final Optional<Map.Entry<Integer, Double>> label = argmax(scores.entrySet().iterator(), Map.Entry::getValue);

            final int updated = label.isPresent() ? label.get().getKey() : labels.get(node);

            // labels.put() never returns null for a known node
            @SuppressWarnings("ConstantConditions") final int previous = labels.put(node, updated);
            changed = changed || (previous != updated);
        }

        return changed;
    }

    /**
     * {@inheritDoc}
     */
    @Override
    public Collection<Collection<V>> getClusters() {
        final Map<Integer, List<Map.Entry<V, Integer>>> groups = labels.entrySet().stream().
                collect(Collectors.groupingBy(Map.Entry::getValue));

        final List<Collection<V>> clusters = new ArrayList<>(groups.size());

        for (final List<Map.Entry<V, Integer>> cluster : groups.values()) {
            clusters.add(cluster.stream().map(Map.Entry::getKey).collect(Collectors.toSet()));
        }

        return clusters;
    }

    /**
     * This label selector selects the label class having the maximal total weight in the neighborhood.
     *
     * @param graph     the graph.
     * @param labels    node labels.
     * @param weighting edge weighting.
     * @param node      the target node.
     * @return label-weight map.
     */
    protected Map<Integer, Double> score(Graph<V, E> graph, Map<V, Integer> labels, NodeWeighting<V, E> weighting, V node) {
        final Map<Integer, Double> weights = new HashMap<>();

        final Iterator<V> neighbors = Neighbors.neighborIterator(graph, node);

        neighbors.forEachRemaining(neighbor -> {
            final int label = labels.get(neighbor);
            weights.merge(label, weighting.apply(graph, labels, node, neighbor), Double::sum);
        });

        return weights;
    }

    @SuppressWarnings("unused")
    public int getSteps() {
        return steps;
    }
}
<commit_msg>Count the number of changed labels in Chinese Whispers<commit_after>/*
 * Copyright 2019 <NAME>
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *   http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 *
 */

package org.nlpub.watset.graph;

import org.jgrapht.Graph;
import org.nlpub.watset.util.Neighbors;

import java.util.*;
import java.util.function.Function;
import java.util.stream.Collectors;

import static java.util.Objects.requireNonNull;
import static org.nlpub.watset.util.Maximizer.argmax;

/**
 * Implementation of the Chinese Whispers algorithm.
 *
 * @see <a href="http://dl.acm.org/citation.cfm?id=1654774">Biemann (TextGraphs-1)</a>
 */
public class ChineseWhispers<V, E> implements Clustering<V> {
    public static <V, E> Function<Graph<V, E>, Clustering<V>> provider(NodeWeighting<V, E> weighting) {
        return graph -> new ChineseWhispers<>(graph, weighting);
    }

    public static <V, E> Function<Graph<V, E>, Clustering<V>> provider(NodeWeighting<V, E> weighting, int iterations, Random random) {
        return graph -> new ChineseWhispers<>(graph, weighting, iterations, random);
    }

    public static final int ITERATIONS = 20;

    protected final Graph<V, E> graph;
    protected final NodeWeighting<V, E> weighting;
    protected final int iterations;
    protected final Random random;
    protected Map<V, Integer> labels;

    protected int steps;

    public ChineseWhispers(Graph<V, E> graph, NodeWeighting<V, E> weighting, int iterations, Random random) {
        this.graph = requireNonNull(graph);
        this.weighting = requireNonNull(weighting);
        this.iterations = iterations;
        this.random = requireNonNull(random);
    }

    public ChineseWhispers(Graph<V, E> graph, NodeWeighting<V, E> weighting) {
        this(graph, weighting, ITERATIONS, new Random());
    }

    /**
     * {@inheritDoc}
     */
    @Override
    public Clustering<V> fit() {
        final List<V> nodes = new ArrayList<>(graph.vertexSet());

        labels = new HashMap<>(nodes.size());

        int i = 0;

        for (final V node : graph.vertexSet()) {
            labels.put(node, i++);
        }

        for (steps = 0; steps < iterations; steps++) {
            Collections.shuffle(nodes, random);

            if (step(nodes) == 0) break;
        }

        return this;
    }

    /**
     * Performs one iteration of the algorithm.
     *
     * @param nodes node list
     * @return whether the labels changed or not.
     */
    protected int step(List<V> nodes) {
        int changed = 0;

        for (final V node : nodes) {
            final Map<Integer, Double> scores = score(graph, labels, weighting, node);

            final Optional<Map.Entry<Integer, Double>> label = argmax(scores.entrySet().iterator(), Map.Entry::getValue);

            final int updated = label.isPresent() ? label.get().getKey() : labels.get(node);

            // labels.put() never returns null for a known node
            @SuppressWarnings("ConstantConditions") final int previous = labels.put(node, updated);

            if (previous != updated) {
                changed++;
            }
        }

        return changed;
    }

    /**
     * {@inheritDoc}
     */
    @Override
    public Collection<Collection<V>> getClusters() {
        final Map<Integer, List<Map.Entry<V, Integer>>> groups = labels.entrySet().stream().
                collect(Collectors.groupingBy(Map.Entry::getValue));

        final List<Collection<V>> clusters = new ArrayList<>(groups.size());

        for (final List<Map.Entry<V, Integer>> cluster : groups.values()) {
            clusters.add(cluster.stream().map(Map.Entry::getKey).collect(Collectors.toSet()));
        }

        return clusters;
    }

    /**
     * This label selector selects the label class having the maximal total weight in the neighborhood.
     *
     * @param graph     the graph.
     * @param labels    node labels.
     * @param weighting edge weighting.
     * @param node      the target node.
     * @return label-weight map.
     */
    protected Map<Integer, Double> score(Graph<V, E> graph, Map<V, Integer> labels, NodeWeighting<V, E> weighting, V node) {
        final Map<Integer, Double> weights = new HashMap<>();

        final Iterator<V> neighbors = Neighbors.neighborIterator(graph, node);

        neighbors.forEachRemaining(neighbor -> {
            final int label = labels.get(neighbor);
            weights.merge(label, weighting.apply(graph, labels, node, neighbor), Double::sum);
        });

        return weights;
    }

    @SuppressWarnings("unused")
    public int getSteps() {
        return steps;
    }
}

{'fraction_non_alphanumeric': 0.11895837443282699, 'fraction_numerical': 0.004142828960347208, 'mean_word_length': 2.791697830964847, 'pattern_counts': {'":': 0, '<': 103, '<?xml version=': 0, '>': 107, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, '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': '134573', 'n_tokens_mistral': 2931, 'n_tokens_neox': 2808, 'n_words': 857}