EuclideanMST.java

package heima11;

import java.util.ArrayList;

import edu.princeton.cs.algs4.*;

public class EuclideanMST {

    // Fastar sem skilgreina mörk kortsins sem á að teikna.
    private double xMin = Double.POSITIVE_INFINITY;
    private double xMax = Double.NEGATIVE_INFINITY;
    private double yMin = Double.POSITIVE_INFINITY;
    private double yMax = Double.NEGATIVE_INFINITY;

    private ArrayList<Point2D> points; // Skilgreinið þessa breytu í smiðnum.
    private EdgeWeightedGraph G;
    private KruskalMST mst; // Skilgreinið þessa breytu í smiðnum. Hér mætti líka nota PrimMST.

    private double max = 0;

    public EuclideanMST(In in) {
        /*
         * Les hnit úr inntaksstraumnum <in> og upphafsstillir tilviksbreyturnar <this.mst> og <this.points>.
         */

        points = new ArrayList<>();
        fillPoints(in); // fyllum arraylistann

        G = new EdgeWeightedGraph((int) max+1);
        fillGraph(in); // fyllum í grafið

        mst = new KruskalMST(G); // finnum stysta spanntréð
    }

    /**
     * Sér um að bæta við punktum úr skránni í arraylist
     * @param in Textaskráin okkar
     */
    private void fillPoints(In in) {
        while (!in.isEmpty()) {
            String[] a = in.readLine().split(" ");
            for (int i=1; i<a.length; i++) {
                Point2D point = new Point2D(Double.valueOf(a[2]), Double.valueOf(a[1]));
                if (!points.contains(point))
                    points.add(point);
                if (Double.valueOf(a[1]) > max) max = Double.valueOf(a[1]);
            }
        }
    }

    /*
     * Fillum EdgeWeightedGraph af öllum mögulegum leggjum á milli hnúta (fyrir utan lykkjur)
     */
    private void fillGraph(In in) {
        for (int i=0; i<points.size(); i++) {
            Point2D p = points.get(i);

            for (int j=0; j<points.size(); j++) {
                Double d = p.distanceTo(points.get(j));
                if (i!=j) {
                    Edge e = new Edge(i, j, d);
                    G.addEdge(e);
                }
            }
        }
    }

    private void drawMST() {
        /*
         * Teiknar spanntréð í tilviksbreytunni <this.mst> með hnitin <this.points>.
         * Gerir ráð fyrir að <this.xMax>, <this.xMin>, <this.yMax> og <this.yMin> séu upphafsstillt.
         */
        for (Edge e : mst.edges()) {
            int x = e.either(); // annarhvor endi leggsins
            int y = e.other(x); // hinn endinn
            double x0 = points.get(x).x();
            double y0 = points.get(x).y();
            double x1 = points.get(y).x();
            double y1 = points.get(y).y();
            StdDraw.line(x0-xMin, y0-yMin, x1-xMin, y1-yMin); // teikum línu
        }

        StdDraw.save("mst.jpg");
    }

    public void drawPoints() {
        /*
         * Teiknar hnitin í <this.points> á striga.
         * Gerir ráð fyrir að <this.xMin> og <this.yMin> hafi verið upphafsstillt. Sjá initializeCanvas().
         *
         */
        for (Point2D p : points) {
            StdDraw.point(p.x() - xMin, p.y() - yMin);
        }

        StdDraw.save("punktar.jpg");
    }

    public void initializeCanvas() {
        /*
         * Upphafsstillir striga út frá gögnunum í <this.points>.
         * Setur vitræn gildi á <this.xMax>, <this.xMin>, <this.yMax> og <this.yMin>.
         */

        // Útgildin fundin
        for (Point2D point : points) {
            if (point.x() < xMin) {
                xMin = point.x();
            }
            if (xMax < point.x()) {
                xMax = point.x();
            }
            if (point.y() < yMin) {
                yMin = point.y();
            }
            if (yMax < point.y()) {
                yMax = point.y();
            }
        }
        // Ramminn stækkaður aðeins svo allir punktar geti sést
        double xDiff = xMax - xMin;
        double yDiff = yMax - yMin;
        double padding = 0.1; // Stillir hlutfallslega stærð hvíta rýmisins í kringum punktana
        xMin = xMin - xDiff * padding / 2;
        xMax = xMax + xDiff * padding / 2;
        yMin = yMin - yDiff * padding / 2;
        yMax = yMax + yDiff * padding / 2;

        // Striginn sjálfur upphafsstilltur
        StdDraw.setCanvasSize((int) (xMax - xMin), (int) (yMax - yMin));
        StdDraw.setXscale(0, (int) (xMax - xMin));
        StdDraw.setYscale(0, (int) (yMax - yMin));
        StdDraw.setPenRadius(0.01);
    }

    public double getWeight() {
        /*
        Sækir þyngd undirliggjandi spanntrés
         */
        return this.mst.weight();
    }

    public static void main(String[] args) {
        // ATH: Þetta hrynur við keyrslu þar til points og mst tilviksbreyturnar hafa verið skilgreindar.
        EuclideanMST euclideanMST = new EuclideanMST(new In("/heima11/luxembourg.txt"));

        StdOut.println(euclideanMST.getWeight());

        euclideanMST.initializeCanvas();
        euclideanMST.drawPoints();
        euclideanMST.drawMST();
    }

}