AffinitiesGraph.java

package prop.g12.common;

import java.util.*;

/**
 * This class represents non-directed weighted graphs without edges connecting nodes with themselves. The weights must
 * be in the [0,1] interval, since they represent affinities between nodes in a normalized scale.
 *
 * This class is optimized for read operations, rather than write operations.
 *
 * It doesn't allow duplicated nodes, uses the `equals` and `hashCode` methods to determine if a new node is a
 * duplicated one or not.
 *
 * @author Andrés Correa Casablanca
 */
public class AffinitiesGraph<T> implements Iterable<T> {

    /**
     * Set of graph's nodes. Useful to know whether a node belongs or not to this graph.
     */
    private HashSet<T> nodes;

    /**
     * Adjacency Matrix, defines weighted edges between nodes.
     */
    private HashMap<ImmutablePair<T,T>, Double> adjMatrix;


    /**
     * Simple constructor
     */
    public AffinitiesGraph() {
        nodes = new HashSet<>();
        adjMatrix = new HashMap<>();
    }

    /**
     * Convenience constructor that pre-allocates memory to store the nodes and edges.
     *
     * @param nodesCapacity The expected number of nodes the graph will have.
     */
    public AffinitiesGraph(int nodesCapacity) {
        nodes = new HashSet<>(nodesCapacity);
        adjMatrix = new HashMap<>(nodesCapacity*nodesCapacity);
    }

    /**
     * Convenience constructor that pre-allocates memory to store the nodes and edges.
     *
     * @param nodesCapacity The expected number of nodes the graph will have.
     * @param edgesCapacity The expected number of edges the graph will have.
     */
    public AffinitiesGraph(int nodesCapacity, int edgesCapacity) {
        nodes = new HashSet<>(nodesCapacity);
        adjMatrix = new HashMap<>(edgesCapacity);
    }


    /**
     * @return The number of nodes belonging to the graph.
     */
    public int numNodes() {
       return nodes.size();
    }

    /**
     * WARNING: this method works well almost all the time, BUT, it could be imprecise under certain very improbable
     * circumstances (many nodes with the same hashCode and not implementing the Comparable interface).
     *
     * This problem isn't fixed because it's easier and faster to implement the Comparable interface in T.
     *
     * @return The number of not null edges belonging to the graph (except the implicit edges between nodes and themselves)
     */
    public int numEdges() {
        return adjMatrix.size();
    }


    /**
     * Adds a node to the graph.
     *
     * @param newNode The node that we want to add to the graph.
     */
    public void addNode(T newNode) {
        if (nodes.contains(newNode)) {
            throw new IllegalArgumentException("Duplicated node");
        }

        nodes.add(newNode);
    }

    /**
     * Convenience method. Adds a node to the graph. Does nothing if the node already exists and checkDuplicated is
     * false, and raises an exception if checkDuplicated is true.
     *
     * @param newNode The node that we want to add to the graph.
     * @param checkDuplicated
     */
    public void addNode(T newNode, boolean checkDuplicated) {
        if (checkDuplicated && nodes.contains(newNode)) {
            throw new IllegalArgumentException("Duplicated node");
        }

        nodes.add(newNode);
    }

    /**
     * "Duplication-Unchecked" bulk nodes addition method.
     */
    public void addNodes(Collection<T> newNodes) {
        nodes.addAll(newNodes);
    }

    /**
     * @param node The node we want to know if belongs to the graph.
     * @return A boolean value telling us if the node exists inside the graph.
     */
    public boolean hasNode(T node) {
        return nodes.contains(node);
    }

    /**
     * Removes a node from the graph.
     * @param node The node we want to remove.
     */
    public void removeNode(T node) {
        if (!nodes.contains(node)) {
            throw new IllegalArgumentException("Trying to remove a node that doesn't belong to the graph.");
        }

        for (T otherNode : nodes) {
            // We can safely compare references, which is faster than using equals.
            if (node == otherNode) {
                continue;
            }

            Double w1 = adjMatrix.get(new ImmutablePair<T, T>(node, otherNode));
            Double w2 = adjMatrix.get(new ImmutablePair<T, T>(otherNode, node));

            if (w1 != null || w2 != null) {
                throw new IllegalArgumentException(
                        "Impossible to remove the node because it has at least one connected edge"
                );
            }
        }

        nodes.remove(node);
    }

    /**
     * @return A copy of the graph's nodes set.
     */
    public HashSet<T> getNodes() {
        return new HashSet<>(nodes);
    }

    /**
     * Adds an edge between node1 and node2.
     *
     * @param node1 source
     * @param node2 destiny
     * @param weight edge's weight. Must be in the [0, 1] interval.
     */
    public void addEdge(T node1, T node2, double weight) {
        if (!nodes.contains(node1) || !nodes.contains(node2)) {
            throw new IllegalArgumentException("At least one of the specified nodes doesn't belong to the graph.");
        }

        if (node1.equals(node2)) {
            throw new IllegalArgumentException("It's not allowed to create edges between one one and itself.");
        }

        if (weight < 0 || weight > 1) {
            throw new IllegalArgumentException("weight must be in the [0, 1] interval.");
        }

        int hash1 = node1.hashCode();
        int hash2 = node2.hashCode();

        Double currentWeight;
        ImmutablePair<T, T> adjMatrixKey = null;

        if (hash1 != hash2) {  // Hopefully, the most common case.
            // A little trick to avoid having to store two references to the edge.
            adjMatrixKey = (hash1 < hash2) ?
                    new ImmutablePair<T, T>(node1, node2) : new ImmutablePair<T, T>(node2, node1);
        } else if (node1 instanceof Comparable) {
            // Another trick to avoid having to store two references to the edge.
            adjMatrixKey = (((Comparable) node1).compareTo(node2) < 0) ?
                    new ImmutablePair<T, T>(node1, node2) : new ImmutablePair<T, T>(node2, node1);
        }

        if (null != adjMatrixKey) {
            currentWeight = adjMatrix.get(adjMatrixKey);

            if (null == currentWeight) {
                if (0 == weight) {
                    // We don't store "null" edges.
                    return;
                }

                adjMatrix.put(adjMatrixKey, weight);
            } else {
                if (0 == weight) {
                    adjMatrix.remove(adjMatrixKey);
                } else {
                    adjMatrix.put(adjMatrixKey, weight);
                }
            }
        } else {
            // In this case, we don't have a natural order for our nodes, so we duplicate the reference to the new edge.

            if (0 == weight) {
                // We don't care if the edges previosly existed, this can be done without problem.
                adjMatrix.remove(new ImmutablePair<T, T>(node1, node2));
                adjMatrix.remove(new ImmutablePair<T, T>(node2, node1));
            } else {
                adjMatrix.put(new ImmutablePair<T, T>(node1, node2), weight);
                adjMatrix.put(new ImmutablePair<T, T>(node2, node1), weight);
            }
        }
    }

    /**
     * WARNING: It's important to note that this method will return true if node1 equals node2.
     *          This works that way because this class represents affinities between nodes.
     *
     * @param node1 edge "start".
     * @param node2 edge "end".
     * @return Returns a boolean value telling us if the specified edge exists or not.
     */
    public boolean hasEdge(T node1, T node2) {
        // We don't check null values because the system will throw an exception the same way we could do. So no more
        // code is needed.

        // We don't have to check zero values because we don't store them.
        return (node1.equals(node2)) || adjMatrix.get(
            (node1.hashCode() < node2.hashCode()) ? new ImmutablePair<>(node1, node2) : new ImmutablePair<>(node2, node1)
        ) != null;
    }

    /**
     * @param node1 edge "start".
     * @param node2 edge "end"
     * @return The weight of the specified edge.
     */
    public double getEdge(T node1, T node2) {
        if (!nodes.contains(node1) || !nodes.contains(node2)) {
            throw new IllegalArgumentException("At least one of the specified nodes doesn't belong to the graph.");
        }

        if (node1.equals(node2)) {
            // We can return this value because we know the graph is storing affinities, so even if we haven't nodes
            // connected to themselves, we know that their "auto-affinity" must be 1.0.
            return 1.0;
        }

        Double tmpResult = adjMatrix.get(
            (node1.hashCode() < node2.hashCode()) ?
                new ImmutablePair<>(node1, node2) : new ImmutablePair<>(node2, node1)
        );

        return (tmpResult != null) ? tmpResult : 0;
    }

    /**
     * Convenience method. This is faster than calling addEdge(node1, node2, 0).
     * It doesn't check if the nodes exist or not because there isn't danger of breaking inner consistency.
     */
    public void removeEdge(T node1, T node2) {
        adjMatrix.remove(new ImmutablePair<T, T>(node1, node2));
        adjMatrix.remove(new ImmutablePair<T, T>(node2, node1));
    }

    /**
     * Removes all nodes and edges from the graph.
     */
    public void clear() {
        nodes.clear();
        adjMatrix.clear();
    }

    /**
     * {@inheritDoc}
     */
    @Override
    public Iterator<T> iterator() {
        return nodes.iterator();
    }
}