Implement vertical graph from matrix builder

1 files changed, 80 insertions, 2 deletions

diff --git a/src/main/java/Seam.java b/src/main/java/Seam.java
index d74dff7..d3ffa8e 100644
--- a/src/main/java/Seam.java
+++ b/src/main/java/Seam.java
@@ -40,6 +40,70 @@ public final class Seam {
     }
 
     /**
+     * Build the vertical predecessors graph of a matrix, plus an entry and an exit vertex
+     *
+     * @param width  width of the matrix
+     * @param height height of the matrix
+     * @return an oriented predecessors graph of the size (width * height + 2)
+     */
+    private static int[][] buildPredecessorsGraph(int width, int height) {
+        int matrixSize = width * height;
+        int[][] graph = new int[matrixSize + 2][];
+
+        for (int row = 0; row < height - 1; ++row) {
+            int shift = (row + 1) * width;
+
+            graph[row * height] = new int[]{
+                    shift,
+                    shift + 1,
+            };
+
+            graph[row * height + (width - 1)] = new int[]{
+                    shift + (width - 2),
+                    shift + (width - 1),
+            };
+
+            for (int col = 1; col < width - 1; ++col)
+                graph[row * height + col] = new int[]{
+                        shift + (col - 1),
+                        shift + (col),
+                        shift + (col + 1),
+                };
+        }
+
+        graph[(matrixSize)] = new int[width];
+        for (int col = 0; col < width; ++col) graph[matrixSize][col] = col;
+
+        graph[matrixSize + 1] = new int[0];
+        for (int col = 0; col < width; ++col) graph[(height - 1) * width + col] = new int[]{matrixSize + 1};
+
+        return graph;
+    }
+
+    /**
+     * Build a sequence of vertex costs from a cost matrix, with nil-cost entry and exit vertices
+     *
+     * @param energy the cost matrix
+     * @return a sequence of costs of the size (width * height + 2)
+     */
+    private static float[] buildVerticesCostSequence(float[][] energy) {
+        int width = energy[0].length;
+        int height = energy.length;
+        int matrixSize = width * height;
+
+        float[] costs = new float[matrixSize + 2];
+
+        for (int row = 0; row < height; ++row)
+            for (int col = 0; col < width; ++col)
+                costs[row * width + col] = energy[row][col];
+
+        costs[matrixSize] = 0;
+        costs[matrixSize + 1] = 0;
+
+        return costs;
+    }
+
+    /**
      * Compute shortest path between {@code from} and {@code to}
      *
      * @param successors adjacency list for all vertices
@@ -76,8 +140,22 @@ public final class Seam {
      * @return a sequence of x-coordinates (the y-coordinate is the index)
      */
     public static int[] find(float[][] energy) {
-        // TODO find
-        return null;
+        int width = energy[0].length;
+        int height = energy.length;
+        int matrixSize = width * height;
+
+        int[][] predecessors = Seam.buildPredecessorsGraph(width, height);
+        float[] costs = Seam.buildVerticesCostSequence(energy);
+
+        int[] path = Seam.path(predecessors, costs, matrixSize, matrixSize + 1);
+
+        if (path == null) return null;
+
+        int[] coordinates = new int[path.length - 2]; // ignore added beginning and ending vertices
+        for (int x = 0; x < path.length - 2; ++x)
+            coordinates[x] = path[x + 1] - x * width; // retrieve the y-coordinate
+
+        return coordinates;
     }
 
     /**