Square Sum Solver

GraphMain.java

import org.graphstream.graph.Edge;
import org.graphstream.graph.Graph;
import org.graphstream.graph.Node;
import org.graphstream.graph.implementations.SingleGraph;

import javax.swing.*;
import javax.swing.Timer;
import java.awt.*;
import java.util.*;

/**
 * Created by Samuel Wolfson
 * wolfson@uw.edu
 *
 * Program for creating graphs where nodes are numbers, and edges connect numbers whose sums are perfect squares.
 * Will attempt to find a Hamiltonian path through the graph, therefore an ordering of numbers from 1 to n where
 * each two adjacent numbers have a perfect-square sum.
 *
 * This is the "square sum" problem, inspired by:
 * http://youtube.com/watch?v=G1m7goLCJDY
 */
public class GraphMain {
    private static Graph graph = new SingleGraph("Graph");

    private static int nodeStart = 1;

    private static JButton drawLine;
    private static JFrame window = new JFrame("Controls");

    private static Map<Integer, Stack<Node>> pathMap = new HashMap<>();

    public static void main(String[] args) {
        graph.addAttribute("ui.quality");
        graph.addAttribute("ui.antialias");
        graph.display();

        graph.addAttribute("ui.stylesheet","" +
                "edge.highlight {  " +
                "   fill-color: rgb(200,39,65);\n" +
                "   size: 3px;" +
                "}" +
                "node.marked {" +
                "   fill-color: red;" +
                "}" +
                "node {" +
                "   text-size: 24px;" +
                "   size: 12px;" +
                "}" +
                "edge {" +
                "   size: 2px;" +
                "   fill-color: darkblue;" +
                "}");

        createUI();
    }

    /**
     * Add a node to the graph. Also adds edges between the new node and any existing
     * nodes for which the sum of the values is a perfect square, and tries to find a
     * Hamiltonian Path through the graph.
     * @param n Value of the node to add.
     */
    private static void addNode(int n) {
        Node newNode = graph.addNode(Integer.toString(n));
        newNode.addAttribute("ui.label", newNode.getId());

        // connect new node to all nodes where their values sum to a perfect square
        for (Node other : graph) {
            if (!other.equals(newNode)) {
                int sum = Integer.parseInt(newNode.getId()) + Integer.parseInt(other.getId());
                if (perfectSquare(sum)) {
                    graph.addEdge(newNode.getId() + " " + other.getId(), newNode.getId(), other.getId());
                }
            }
        }

        findPath();
    }

    /**
     * Attempt to find a path through the graph that covers every node.
     * This is the "Hamiltonian Path" problem, and is NP-complete (i.e. there is no polynomial-time solution).
     *
     * We have to start at every single node, and attempt to find a Ham Path beginning at that node,
     * until we're either successful or run out of paths to attempt.
     */
    private static Stack<Node> findPath() {
        int n = graph.getNodeCount();

        if (pathMap.containsKey(n)) {
            drawLine.setEnabled(!pathMap.get(n).isEmpty());
            return pathMap.get(n);
        }

        pathMap.put(n, new Stack<>());
        Stack<Node> path = pathMap.get(n);

        // remove any special highlighting from the last line that we drew
        for (Node node : graph) {
            node.removeAttribute("ui.class");
        }

        for (Edge e : graph.getEdgeSet()) {
            e.removeAttribute("ui.class");
        }

        for (Node node1 : graph) {
            for (Node node2 : graph) {
                node2.removeAttribute("visited");
            }

            path.push(node1);

            node1.setAttribute("visited", "true");

            // try and find a path from each node
            if (backtrack(node1, path)) {
                break;
            } else {
                path.clear();
            }
        }

        // if we found a path, we can draw it!
        drawLine.setEnabled(!path.isEmpty());
        return path;
    }

    /**
     * Draw a path through the graph, pausing between each node.
     */
    private static void drawPath() {
        Collection<Node> path = pathMap.get(graph.getNodeCount());

        if (!path.isEmpty()) {
            Iterator<Node> it = path.iterator();

            Node nodes[] = new Node[2];
            nodes[0] = it.next();
            nodes[0].addAttribute("ui.class", "marked");

            if (it.hasNext())
                nodes[1] = it.next();

            new Timer((5000 / path.size()), e -> {
                if (nodes[1] != null)
                    nodes[1].addAttribute("ui.class", "marked");
                nodes[0].getEdgeBetween(nodes[1]).addAttribute("ui.class", "highlight");

                if (!it.hasNext()) {
                    ((Timer) e.getSource()).stop();
                    JOptionPane.showMessageDialog(window, "Path: " + path);
                    return;
                }

                nodes[0] = nodes[1];
                nodes[1] = it.next();
            }).start();
        }
    }


    /**
     * Try to find a Hamiltonian Path through the graph, starting with
     * the node at the top of path. Assumes that path.size() == 1. At
     * completion of this method, path will either be empty, or will
     * contain each node comprising a Hamiltonian Path through the graph (in order).
     *
     * @param current the current node to search from.
     * @param path a Stack of Nodes which will be either empty or will contain the Ham Path through
     *             all the Nodes in the graph.
     * @return true if a path was found; false otherwise
     */
    private static boolean backtrack(Node current, Stack<Node> path) {
        if (path.size() == nodeStart - 1) {
            return true;
        }

        for (Edge edge : current.getEachEdge()) {
            Node node3 = edge.getOpposite(current);
            if (!Boolean.parseBoolean(node3.getAttribute("visited"))) {
                node3.setAttribute("visited", "true");
                path.push(node3);
                if (backtrack(node3, path)) return true;
                path.pop();
                node3.removeAttribute("visited");
            }
        }
        return false;
    }

    /**
     * Remove a node from the graph, as well as any highlighting.
     * @param n value of node to remove.
     */
    private static void removeNode(int n) {
        graph.removeNode("" + n);
        findPath();
    }

    /**
     * Check whether i is a perfect square.
     * @param i number to check
     * @return true if i is a perfect square; false o.w.
     */
    private static boolean perfectSquare(int i) {
        double sqrt = Math.sqrt(i);
        return Math.round(sqrt) == sqrt;
    }

    private static void createUI() {
        JLabel howMany = new JLabel("    0 nodes");
        JButton newNode = new JButton("Add Node");
        JButton removeNode = new JButton("Remove Node");
        drawLine = new JButton("Draw Path");

        newNode.addActionListener(e -> {
            addNode(nodeStart++);
            howMany.setText(nodeStart - 1 + " nodes");
        });
        removeNode.addActionListener(e -> {
            if (nodeStart > 1) {
                removeNode(--nodeStart);
                howMany.setText(nodeStart - 1 + " nodes");
            }
        });

        drawLine.addActionListener(e -> drawPath());

        window.add(howMany);
        window.add(newNode);
        window.add(removeNode);
        window.add(drawLine);

        window.setDefaultCloseOperation(WindowConstants.EXIT_ON_CLOSE);
        window.setLayout(new FlowLayout());
        window.pack();
        window.setVisible(true);
    }
}