Created
March 5, 2018 22:49
-
-
Save terabyte128/39b6d56f7321e0bc8cb70287ab0d2501 to your computer and use it in GitHub Desktop.
Square Sum Solver
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment