Visualize the progress of the algorithm

Question

I am trying to visually show some algorithms in processing (but in fact this question applies to any language with a graphical interface). My question is: a program with a drawing cycle that is updated based on frames per second, how do you execute the algorithm and update its visual display?

An example is if I display an array of random values ​​as a histogram. I want to sort this array using different types (bubble sort, quicksort, merge sort). How to display each step of the algorithm, showing each swap in a new frame of animation?

Or another example is the search for paths. I want to show the steps of BFS, DFS, A *, and not just the final solution path (all search queries).

Examples of visual affect I'm looking for can be found in Wikipedia articles about these algorithms:

http://en.wikipedia.org/wiki/Quicksort

http://en.wikipedia.org/wiki/File:Astar_progress_animation.gif

The problem is at the time of completion of the algorithm, the drawing cycle only loops once, so the user does not see progress.

The only thing I can think of is to have a "State" object that contains the corresponding values ​​for each step of the algorithm. When it ends, scroll through each state and visually show it. Is there a better way?

Answer 1

import java.awt.*; import java.awt.event.*; import javax.swing.*; /** * A panel that can show a demonstration of Quicksort in action. The items to be * sorted are the hues of a set of vertical bars. When sorted, the bars form a * spectrum from red to violet. Initially, the bars are sorted. There is a Start * button. When the user clicks this button, the order of the bars is randomized * and then Quicksort is applied. During the sort, a black bar marks the * location of an empty space from which the "pivot" element has been removed. * The user can abort the sort by clicking the button again. * <p> * The main point of this program is to demonstrate threads, with very simple * inter-thread communication. The recursive Quicksort algorithm is run in a * separate thread. The abort operation is implemented by setting the value of a * volatile variable that is checked periodically by the thread. When the user * aborts the sort before it finishes, the value of the variable changes; the * thread sees the change and exits. * <p> * This class contains a main() routine that allows the demo to be run as a * stand-alone application. */ public class QuicksortThreadDemo extends JPanel { /** * This main routine just shows a panel of type QuicksortThreadDemo. */ public static void main(String[] args) { JFrame window = new JFrame("Demo: Recursion in a Thread"); QuicksortThreadDemo content = new QuicksortThreadDemo(); window.setContentPane(content); window.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); window.pack(); Dimension screenSize = Toolkit.getDefaultToolkit().getScreenSize(); window.setLocation((screenSize.width - window.getWidth()) / 2, (screenSize.height - window.getHeight()) / 2); window.setVisible(true); } private final static int ARRAY_SIZE = 150; // The number of colored bars. private int[] hue = new int[ARRAY_SIZE]; // The array that will be sorted. private Color[] palette = new Color[ARRAY_SIZE]; // Colors in spectral // order. private Display display; // The panel that displays the colored bars. private JButton startButton; // The button that starts and stops the demo. private Runner runner; // The thread that runs the recursion. private volatile boolean running; // Set to true while recursion is running; // This is set to true as a signal to // the // thread to abort. /** * When the user aborts the recursion before it finishes, an exception of * this type is thrown to end the recursion cleanly. */ private class ThreadTerminationException extends RuntimeException { } /** * A subpanel of type Display shows the colored bars that are being sorted. * The current pivot, if any, is shown in black. A 3-pixel gray border is * left around the bars. */ private class Display extends JPanel { Display() { setPreferredSize(new Dimension(606, 206)); setBackground(Color.GRAY); } protected void paintComponent(Graphics g) { super.paintComponent(g); double barWidth = (double) (getWidth() - 6) / hue.length; int h = getHeight() - 6; for (int i = 0; i < hue.length; i++) { int x1 = 3 + (int) (i * barWidth + 0.49); int x2 = 3 + (int) ((i + 1) * barWidth + 0.49); int w = x2 - x1; if (hue[i] == -1) g.setColor(Color.BLACK); else g.setColor(palette[hue[i]]); g.fillRect(x1, 3, w, h); } } } /** * The constructor sets up the panel, containing the Display and the Start * button below it. */ public QuicksortThreadDemo() { for (int i = 0; i < ARRAY_SIZE; i++) { palette[i] = Color.getHSBColor((i * 230) / (ARRAY_SIZE * 255.0F), 1, 1); hue[i] = i; } setLayout(new BorderLayout()); display = new Display(); add(display, BorderLayout.CENTER); startButton = new JButton("Start"); JPanel bottom = new JPanel(); bottom.add(startButton); bottom.setBackground(Color.WHITE); add(bottom, BorderLayout.SOUTH); startButton.addActionListener(new ActionListener() { public void actionPerformed(ActionEvent e) { if (running) stop(); else start(); } }); } /** * This method is called when the user clicks the Start button, while no * thread is running. It starts a new thread and sets the signaling * variable, running, to true; Also changes the text on the Start button to * "Finish". */ private void start() { startButton.setText("Finish"); runner = new Runner(); running = true; // Set the signal before starting the thread! runner.start(); } /** * This method is called when the user clicks the button while a thread is * running. A signal is sent to the thread to terminate, by setting the * value of the signaling variable, running, to false. */ private void stop() { /* * Set the value of the signaling variable to false as a signal to the * thread to terminate. */ running = false; /* * Wake the thread, in case it is sleeping, to get a more immediate * reaction to the signal. */ runner.interrupt(); /* * Wait for the thread to stop before setting runner = null. One second * should be plenty of time for this to happen, but in case something * goes wrong, it better not to */ try { runner.join(1000); // Wait for thread to stop. One second should be // plenty of time. } catch (InterruptedException e) { } runner = null; } /** * This method is called frequently by the thread that is running the * recursion, in order to insert delays. It calls the repaint() method of * the display to allow the user to see what is going on; the delay will * give the system a chance to actually update the display. Since this * method is called regularly while the recursion is in progress, it is also * used as a convenient place to check the value of the signaling variable, * running. If the value of running has been set to false, this method * throws an exception of type ThreadTerminatedException. This exception * will cause all active levels of the recursion to be terminated. It is * caught in the run() method of the thread. * * @param millis * The number of milliseconds to sleep. */ private void delay(int millis) { if (!running) throw new ThreadTerminationException(); display.repaint(); try { Thread.sleep(millis); } catch (InterruptedException e) { } if (!running) throw new ThreadTerminationException(); } /** * The basic non-recursive QuickSortStep algorithm, which uses hue[lo] as a * "pivot" and rearranges elements of the hue array from positions lo * through hi so that positions the pivot value is in its correct location, * with smaller items to the left and bigger items to the right. The * position of the pivot is returned. In this version, we conceptually * remove the pivot from the array, leaving an empty space. The space is * marked by a -1, and it moves around as the algorithm proceeds. It is * shown as a black bar in the display. Every time a change is made, the * delay() method is called to insert a 1/10 second delay to let the user * see the change. */ private int quickSortStep(int lo, int hi) { int pivot = hue[lo]; // Save pivot item. hue[lo] = -1; // Mark location lo as empty. delay(100); while (true) { while (hi > lo && hue[hi] > pivot) hi--; if (hi == lo) break; hue[lo] = hue[hi]; // Move hue[hi] into empty space. hue[hi] = -1; // Mark location hi as empty. delay(100); while (lo < hi && hue[lo] < pivot) lo++; if (hi == lo) break; hue[hi] = hue[lo]; // Move hue[lo] into empty space. hue[lo] = -1; // Mark location lo as empty. delay(100); } hue[lo] = pivot; // Move pivot item into the empty space. delay(100); return lo; } /** * The recursive quickSort algorithm, for sorting the hue array from * positions lo through hi into increasing order. Most of the actual work is * done in quickSortStep(). */ private void quickSort(int lo, int hi) { if (hi <= lo) return; int mid = quickSortStep(lo, hi); quickSort(lo, mid - 1); quickSort(mid + 1, hi); } /** * This class defines the treads that run the recursive QuickSort algorithm. * The thread begins by randomizing the array. It then calls quickSort() to * sort the entire array. If quickSort() is aborted by a * ThreadTerminationExcpetion, which would be caused by the user clicking * the Finish button, then the thread will restore the array to sorted order * before terminating, so that whether or not the quickSort is aborted, the * array ends up sorted. */ private class Runner extends Thread { public void run() { try { for (int i = hue.length - 1; i > 0; i--) { // Randomize array. int r = (int) ((i + 1) * Math.random()); int temp = hue[r]; hue[r] = hue[i]; hue[i] = temp; } delay(1000); // Wait one second before starting the sort. quickSort(0, hue.length - 1); // Sort the whole array. } catch (ThreadTerminationException e) { // User aborted quickSort. for (int i = 0; i < hue.length; i++) hue[i] = i; } finally {// Make sure running is false and button label is // correct. running = false; startButton.setText("Start"); display.repaint(); } } } } // end QuicksortThreadDemo 

`

Answer 2

I think the way to do this (but maybe not the best way) is to write code for the individual steps, and then use sikuli or some other graphical interfaces to exit automatically.

Or just write the code in a MATLAB script, then use the + and - button to see the next iteration.

Answer 3

Here are two approaches you can take:

Rewrite your algorithm so that it can be increased using a variable. Then increase each iteration of the loop in the draw. Here is an example of someone trying to apply this approach to processing.

http://www.processing.org/discourse/alpha/board_Programs_action_display_num_1059766998.html

Write to the buffer off-screen and save each frame / iteration of the loop, and then display them later. I left the bubble sorting algorithm from the above example and methods for drawing per frame so you can see how I changed the structure to use the buffer.

 int[] myArray; PGraphics pg; ArrayList<PImage> frameBufferList; void setup() { size(400, 400); frameRate(15); frameBufferList = new ArrayList<PImage>(); myArray = randomArray(20); bubbleSortSaveFrame(myArray); } void draw() { background(127); image(frameBufferList.get(frameCount % frameBufferList.size()), 0, 0); } int[] randomArray(int numOfElements) { int[] returnArray = new int[numOfElements]; for (int i = 0; i < returnArray.length; i++) { returnArray[i] = floor(random(0, height)); } return returnArray; } void displayArray(int[] arrToDisplay) { float step = float(width) / float(arrToDisplay.length); for (int i = 0; i < arrToDisplay.length; i++) { rectMode(CORNERS); rect(i*step, height, (i+1)*step, height-arrToDisplay[i]); } } void displayArrayBuffer(int[] arrToDisplay) { pg = createGraphics(width, height, P2D); // setup buffer pg.beginDraw(); // start buffer pg.background(127); float step = float(width) / float(arrToDisplay.length); for (int i = 0; i < arrToDisplay.length; i++) { pg.rectMode(CORNERS); pg.rect(i*step, height, (i+1)*step, height-arrToDisplay[i]); } pg.endDraw(); // end buffer frameBufferList.add(pg); } void bubbleSort(int array[]) { int i, j; boolean sorted = false; // while the array isn't sorted while (!sorted) { sorted = true; // loop through array for (i=0;i<array.length-1;i++) { if (array[i] > array[i+1]) { // swap values j = array[i]; array[i] = array[i+1]; array[i+1] = j; //println(array); // trigger been hit, array isn't sorted. sorted = false; } } } } void bubbleSortSaveFrame(int array[]) { int i, j; boolean sorted = false; // while the array isn't sorted while (!sorted) { sorted = true; // loop through array for (i=0;i<array.length-1;i++) { displayArrayBuffer(array); // save the frame if (array[i] > array[i+1]) { // swap values j = array[i]; array[i] = array[i+1]; array[i+1] = j; //println(array); // trigger been hit, array isn't sorted. sorted = false; } } } } 

Note. Usually you use one buffer for each frame, in this case we create a buffer for each saved image so that you can run out of memory if you create thousands of images. Dose, who has another solution for using PGraphics / buffer without getting into memory?

Answer 4

There is no general answer to your question (gr8 btw question). It depends on the algorithm. Take the bubble view as an example. This algorithm has a finite number of steps until it completes (i.e. you can make an assumption about its worst case).

Stolen from Wikipedia:

  procedure bubbleSort( A : list of sortable items ) repeat swapped = false for i = 1 to length(A) - 1 inclusive do: /* if this pair is out of order */ if A[i-1] > A[i] then /* swap them and remember something changed */ swap( A[i-1], A[i] ) swapped = true end if end for until not swapped end procedure 

You know that you will have (in the worst case) n loops for a repeat loop and n loops for a loop for (n square complexity). The loops are in quick access mode, and you do not need to update the status bar for each cycle (the user will not see progress, and even the graphical interface is not fast enough to update all the statuses in for). So your step by step will be n / 100. At the end of each while loop, update the status bar with this move, and after completion of repeat, update to 100%.
You will need to analyze each algorithm and find such a solution for each of them. As I said, there is no general magic solution.