path: root/Practical1/src/nl/camilstaps/cs/graphs/Graph.java

package nl.camilstaps.cs.graphs;

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

/**
 * A Graph is a list of Nodes.
 *
 * @author Camil Staps
 */
public class Graph<T> {
    private final List<Node<T>> nodes;
    // When removing nodes, it's possible to create restore points to add them back later on.
    private final Stack<List<Node<T>>> restorePoints = new Stack<>();

    public Graph() {
        this.nodes = new ArrayList<>();
        restorePoint();
    }

    public Graph(List<Node<T>> nodes) {
        this.nodes = nodes;
        restorePoint();
    }

    /**
     * Computes the size of the maximum independent set using Robson's algorithm.
     *
     * @see #maximumIndependentSetSizeWith1From(Node, Node)
     * @see #maximumIndependentSetSizeWith2From(Collection)
     *
     * @return the size of the maximum independent set
     */
    public int maximumIndependentSetSize() {
        if (nodes.size() <= 1)
            return nodes.size();

        int miss;
        restorePoint();

        Graph<T> stronglyConnectedComponent = findStronglyConnectedComponent();
        if (stronglyConnectedComponent.size() == size()) {
            // Case: connected graph. Pick a nice Node A (low degree) and a neighbour B with high degree.
            Collections.sort(nodes);
            Node<T> A = nodes.get(0);
            Collections.sort(A.getNeighbourhood(), Collections.reverseOrder());
            Node<T> B = A.getNeighbourhood().get(0);

            int try_1, try_2;
            switch (A.getDegree()) {
                case 1:
                    // One neighbour; pick A and continue with the rest of the Graph.
                    removeNodes(A.getInclusiveNeighbourhood());
                    miss = 1 + maximumIndependentSetSize();
                    break;
                case 2:
                    // Two neighbours: if they are connected pick A and continue with the rest of the Graph. If not,
                    // try both picking the neighbours and picking A with two of its second order neighbours.
                    Node<T> B_ = A.getNeighbourhood().get(1);
                    if (B.getNeighbourhood().contains(B_)) {
                        removeNodes(A.getInclusiveNeighbourhood());
                        miss = 1 + maximumIndependentSetSize();
                    } else {
                        restorePoint();
                        removeNodes(B.getInclusiveNeighbourhood());
                        removeNodes(B_.getInclusiveNeighbourhood());
                        try_1 = 2 + maximumIndependentSetSize();
                        restore();
                        removeNodes(A.getInclusiveNeighbourhood());
                        try_2 = 1 + maximumIndependentSetSizeWith2From(A.getSecondNeighbourhood());
                        miss = Math.max(try_1, try_2);
                    }
                    break;
                case 3:
                    // Three neighbours: either we pick two of the neighbours, or we pick A.
                    removeNode(A);
                    try_1 = maximumIndependentSetSizeWith2From(A.getNeighbourhood());
                    removeNodes(A.getNeighbourhood());
                    try_2 = 1 + maximumIndependentSetSize();
                    miss = Math.max(try_1, try_2);
                    break;
                default:
                    // If A dominates his neighbour we may safely remove that neighbour. Otherwise, we try both with
                    // and without the neighbour.
                    if (A.dominates(B)) {
                        removeNode(B);
                        miss = maximumIndependentSetSize();
                    } else {
                        removeNode(B);
                        try_1 = maximumIndependentSetSize();
                        removeNodes(B.getNeighbourhood());
                        try_2 = 1 + maximumIndependentSetSize();
                        miss = Math.max(try_1, try_2);
                    }
                    break;
            }
        } else {
            // Case: at least two strongly connected components. Compute for the first component, and for the rest.
            miss = stronglyConnectedComponent.maximumIndependentSetSize();
            removeNodes(stronglyConnectedComponent.nodes);
            miss += maximumIndependentSetSize();
        }

        restore();
        return miss;
    }

    /**
     * Compute the maximum independent set size if it should contain (at least) one of two nodes.
     *
     * This is a helper function for {@link #maximumIndependentSetSizeWith2From(Collection)}, which is a helper
     * function for {@link #maximumIndependentSetSize()}, which uses Robson's algorithm.
     *
     * @param s_1 The first node
     * @param s_2 The second node
     * @return the maximum independent set size
     */
    private int maximumIndependentSetSizeWith1From(Node<T> s_1, Node<T> s_2) {
        assert s_1.getDegree() <= s_2.getDegree();

        int miss;
        restorePoint();

        if (s_1.getDegree() <= 1) {
            miss = maximumIndependentSetSize();
        } else if (s_1.getNeighbourhood().contains(s_2)) {
            if (s_1.getDegree() <= 3) {
                miss = maximumIndependentSetSize();
            } else {
                int try_1, try_2;
                restorePoint();
                removeNodes(s_1.getInclusiveNeighbourhood());
                try_1 = maximumIndependentSetSize();
                restore();
                removeNodes(s_2.getInclusiveNeighbourhood());
                try_2 = maximumIndependentSetSize();
                miss = Math.max(try_1, try_2) + 1;
            }
        } else if (!s_1.neighbourhoodsDisjoint(s_2)) {
            removeNodes(s_1.neighbourhoodIntersection(s_2));
            miss = maximumIndependentSetSizeWith1From(s_1, s_2);
        } else if (s_2.getDegree() == 2) {
            Node<T> E = s_1.getNeighbourhood().get(0), F = s_1.getNeighbourhood().get(1);
            if (E.getNeighbourhood().contains(F)) {
                removeNodes(s_1.getInclusiveNeighbourhood());
                miss = 1 + maximumIndependentSetSize();
            } else {
                boolean subset = true;
                for (Node n : E.getNeighbourhood())
                    if (n != s_1 && !s_2.getNeighbourhood().contains(n))
                        subset = false;
                for (Node n : F.getNeighbourhood())
                    if (n != s_1 && !s_2.getNeighbourhood().contains(n))
                        subset = false;
                if (subset) {
                    removeNodes(s_1.getInclusiveNeighbourhood());
                    removeNodes(s_2.getInclusiveNeighbourhood());
                    miss = 3 + maximumIndependentSetSize();
                } else {
                    int try_1, try_2;
                    removeNodes(s_1.getInclusiveNeighbourhood());
                    try_1 = 1 + maximumIndependentSetSize();
                    removeNodes(E.getInclusiveNeighbourhood());
                    removeNodes(F.getInclusiveNeighbourhood());
                    removeNodes(s_2.getInclusiveNeighbourhood());
                    try_2 = 3 + maximumIndependentSetSize();
                    miss = Math.max(try_1, try_2);
                }
            }
        } else {
            int try_1, try_2;
            restorePoint();
            removeNodes(s_2.getInclusiveNeighbourhood());
            try_1 = maximumIndependentSetSize();
            restore();
            removeNodes(s_1.getInclusiveNeighbourhood());
            removeNode(s_2);
            try_2 = maximumIndependentSetSizeWith2From(s_2.getNeighbourhood());
            miss = Math.max(try_1, try_2);
        }

        restore();
        return miss;
    }

    /**
     * Compute the maximum independent set size if at least two Nodes of some set should be in it.
     *
     * This is a helper function for {@link #maximumIndependentSetSize()}, which uses Robson's algorithm.
     *
     * @see #maximumIndependentSetSizeWith1From(Node, Node)
     *
     * @param Scol the set of which two Nodes should be in the maximum independent set
     * @return the size of the maximum independent set
     */
    private int maximumIndependentSetSizeWith2From(Collection<Node<T>> Scol) {
        List<Node<T>> S = new ArrayList<>(Scol);
        int miss;
        restorePoint();

        if (S.size() < 2) {
            // Less than two Nodes to pick from; this is impossible
            miss = 0;
        } else if (S.size() == 2) {
            // Two Nodes to pick from; try to pick both and fail otherwise.
            if (S.get(0).getNeighbourhood().contains(S.get(1)))
                miss = 0;
            else {
                removeNodes(S.get(0).getInclusiveNeighbourhood());
                removeNodes(S.get(1).getInclusiveNeighbourhood());
                miss = 2 + maximumIndependentSetSize();
            }
        } else if (S.size() == 3) {
            // Three Nodes to pick from. An ugly case distinction.
            Node<T> s_1 = S.get(0), s_2 = S.get(1), s_3 = S.get(2);

            // If there is a Node with degree 0, we add it to the independent set and choose 1 Node from the other two
            if (s_1.getDegree() == 0) {
                removeNode(s_1);
                miss = 1 + maximumIndependentSetSizeWith1From(s_2, s_3);
            } else if (s_2.getDegree() == 0) {
                removeNode(s_2);
                miss = 1 + maximumIndependentSetSizeWith1From(s_1, s_3);
            } else if (s_3.getDegree() == 0) {
                removeNode(s_3);
                miss = 1 + maximumIndependentSetSizeWith1From(s_1, s_2);
            }
            // If the Nodes are connected we can't choose two in an independent set.
            else if (s_1.getNeighbourhood().contains(s_2) &&
                    s_2.getNeighbourhood().contains(s_3) &&
                    s_3.getNeighbourhood().contains(s_1)) {
                miss = 0;
            }
            // If there is at least one edge from s_1
            else if (s_1.getNeighbourhood().contains(s_2) || s_1.getNeighbourhood().contains(s_3)){
                Node<T> s_i, s_j, s_k;
                s_i = s_j = s_k = null;

                // If there are two edges among S, say si-sj-sk, we pick si and sk.
                if (s_1.getNeighbourhood().contains(s_2) && s_1.getNeighbourhood().contains(s_3)) {
                    s_i = s_1; s_j = s_2; s_k = s_3;
                } else if (s_2.getNeighbourhood().contains(s_1) && s_2.getNeighbourhood().contains(s_3)) {
                    s_i = s_2; s_j = s_1; s_k = s_3;
                }  else if (s_3.getNeighbourhood().contains(s_1) && s_3.getNeighbourhood().contains(s_2)) {
                    s_i = s_3; s_j = s_1; s_k = s_2;
                }

                // Check if we managed to find two edges. If not, there must be at least one edge, say si-sj. We then
                // choose sk and either si or sj. These are the cases that s_1 != sk.
                if (s_i != null) {                                      // Case two edges
                    removeNodes(s_j.getInclusiveNeighbourhood());
                    removeNodes(s_k.getInclusiveNeighbourhood());
                    miss = 2 + maximumIndependentSetSize();
                } else if (s_1.getNeighbourhood().contains(s_2)) {      // Case one edge; s_1 - s_2
                    removeNodes(s_3.getInclusiveNeighbourhood());
                    miss = 1 + maximumIndependentSetSizeWith1From(s_1, s_2);
                } else {                                                // Case one edge; s_1 - s_3 (implicit)
                    removeNodes(s_2.getInclusiveNeighbourhood());
                    miss = 1 + maximumIndependentSetSizeWith1From(s_1, s_3);
                }
            }
            // Final case with one edge; between s_2 and s_3: pick s_1 and either s_2 or s_3.
            else if (s_2.getNeighbourhood().contains(s_3)) {
                removeNodes(s_1.getInclusiveNeighbourhood());
                miss = 1 + maximumIndependentSetSizeWith1From(s_2, s_3);
            }
            // When two neighbourhoods of two nodes si, sj aren't disjoint, we can remove the intersection, because
            // either si or sj is in the independent set and so the intersection is not. The intersection has at most
            // one member.
            else if (!s_1.neighbourhoodsDisjoint(s_2)) {
                removeNode(s_1.neighbourhoodIntersection(s_2).get(0));
                miss = maximumIndependentSetSizeWith2From(Scol);
            } else if (!s_1.neighbourhoodsDisjoint(s_3)) {
                removeNode(s_1.neighbourhoodIntersection(s_3).get(0));
                miss = maximumIndependentSetSizeWith2From(Scol);
            } else if (!s_2.neighbourhoodsDisjoint(s_3)) {
                removeNode(s_2.neighbourhoodIntersection(s_3).get(0));
                miss = maximumIndependentSetSizeWith2From(Scol);
            }
            // If s_1 has degree 1, we pick it and either s_2 or s_3
            else if (s_1.getDegree() == 1) {
                removeNodes(s_1.getInclusiveNeighbourhood());
                miss = 1 + maximumIndependentSetSizeWith1From(s_2, s_3);
            }
            // If all else fails, we try both picking s_1 with either s_2 or s_3, and picking s_1 and s_2 and at least
            // one neighbour of s_1 (Note: Robson has forgotten to add 2 for s_2 and s_3 in this step).
            else {
                int try_1, try_2;
                restorePoint();
                removeNodes(s_1.getInclusiveNeighbourhood());
                try_1 = 1 + maximumIndependentSetSizeWith1From(s_2, s_3);
                restore();
                removeNodes(s_2.getInclusiveNeighbourhood());
                removeNodes(s_3.getInclusiveNeighbourhood());
                removeNode(s_1);
                try_2 = 2 + maximumIndependentSetSizeWith2From(s_1.getNeighbourhood());
                miss = Math.max(try_1, try_2);
            }
        } else if (S.size() == 4) {
            // Four Nodes to pick from. If there's a node with degree <= 3 in the Graph, it's more efficient to just
            // compute normally. If not, we try recursively both with and without the first Node in S.
            Collections.sort(nodes);
            if (nodes.get(0).getDegree() <= 3) {
                miss = maximumIndependentSetSize();
            } else {
                Node<T> s_1 = S.get(0);
                int try_1, try_2;
                removeNode(s_1);
                S.remove(s_1);
                try_1 = maximumIndependentSetSizeWith2From(S);
                removeNodes(s_1.getNeighbourhood());
                try_2 = 1 + maximumIndependentSetSize();
                miss = Math.max(try_1, try_2);
            }
        } else {
            miss = maximumIndependentSetSize();
        }

        restore();
        return miss;
    }

    /**
     * Find a strongly connected component of the graph. This may return itself, if the graph is empty or connected.
     * It is not guaranteed that the smallest / largest strongly connected component is returned. The method simply
     * returns the one that contains the first node (if it exists).
     *
     * @return some strongly connected component
     */
    private Graph<T> findStronglyConnectedComponent() {
        if (nodes.isEmpty())
            return this;

        List<Node<T>> seen = new ArrayList<>();
        Queue<Node<T>> queue = new LinkedList<>();
        queue.add(nodes.get(0));
        while (!queue.isEmpty()) {
            Node<T> n = queue.remove();
            queue.addAll(n.getNeighbourhood().stream().filter(x -> !seen.contains(x)).collect(Collectors.toList()));
            seen.add(n);
        }

        return new Graph<>(seen);
    }

    /**
     * Add a Node, and update its neighbours to include it as a neighbour.
     * @param node the Node to add
     */
    public void addNode(Node<T> node) {
        this.nodes.add(node);
        node.getNeighbourhood().stream()
                .filter(nodes::contains)
                .filter(n -> !n.getNeighbourhood().contains(node))
                .forEach(n -> n.getNeighbourhood().add(node));
        restorePoints.peek().remove(node);
    }

    /**
     * Get a Node by its index. Note: some internal methods may reorder the list; only use this directly after adding
     * nodes.
     * @param i the index in the list
     * @return the Node
     */
    public Node<T> getNode(int i) {
        return this.nodes.get(i);
    }

    /**
     * Remove a node, and remove its reference from its neighbours that are still in the graph
     *
     * @see #removeNodes(Collection)
     *
     * @param node the Node
     */
    private void removeNode(Node<T> node) {
        nodes.remove(node);
        node.getNeighbourhood().stream()
                .filter(nodes::contains)
                .forEach(n -> n.getNeighbourhood().remove(node));
        restorePoints.peek().add(node);
    }

    /**
     * Remove a list of nodes, and update all references
     *
     * @see #removeNode(Node)
     *
     * @param ns the Nodes to remove
     */
    private void removeNodes(Collection<Node<T>> ns) {
        nodes.removeAll(ns);
        for (Node<T> n : nodes)
            n.getNeighbourhood().removeAll(ns);
        restorePoints.peek().addAll(ns);
    }

    /**
     * Create a restore point to return back to after removing some Nodes.
     *
     * @see #restore()
     * @see #restorePoints
     */
    private void restorePoint() {
        restorePoints.push(new ArrayList<>());
    }

    /**
     * Go back to the last restore point, re-adding all Nodes that were removed since then.
     *
     * @see #restorePoint()
     * @see #restorePoints
     */
    private void restore() {
        List<Node<T>> removed = restorePoints.pop();
        Collections.reverse(removed);
        for (Node<T> node : removed) {
            this.nodes.add(node);
            node.getNeighbourhood().stream()
                    .filter(nodes::contains)
                    .filter(n -> !n.getNeighbourhood().contains(node))
                    .forEach(n -> n.getNeighbourhood().add(node));
        }
        removed.clear();
    }

    /**
     * The size of the graph is the number of Nodes.
     * @return the number of Nodes.
     */
    public int size() {
        return nodes.size();
    }

    /**
     * Represent the Graph as a String
     * @return a String representation of the Graph
     */
    public String toString() {
        StringBuilder sb = new StringBuilder("Graph:");
        for (Node n : nodes) {
            sb.append("\n  ").append(n).append(":   ");
            for (Object n2 : n.getNeighbourhood()) sb.append(" - ").append(n2);
        }
        return sb.toString();
    }
}