GraphProperties.java

package heima10;

import edu.princeton.cs.algs4.Graph;
import edu.princeton.cs.algs4.SymbolGraph;
import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.BreadthFirstPaths;

public class GraphProperties {

    private Graph g;
    // fjöldi hnúta í grafinu
    private int fjoldi;
    // allar stystu leiðir fyrir hvern hnút
    private int[] ecc;

    GraphProperties(Graph g) {
        /*
        Upphafsstillir klasa sem reiknar út nokkra eiginleika netsins <g>.
        Netið <g> skal vera samanhangandi. Þessi aðferð veldur villu sé svo ekki.
         */

        // Hér þarf að skrifa kóða!
        this.g = g;
        fjoldi = g.V();
        ecc = new int[fjoldi];
        // finnum stystu leiðirnar:
        for (int i=0; i<fjoldi; i++) {
            ecc[i] = eccentricity(i);
        }
    }

    public int eccentricity(int v) {
        /*
        Skilar lengd stystu leiðar frá hnútnum <v> í <this.g> til þess hnúts sem lengst er frá honum.
         */

        int max = 0;
        // finnur styrstu leið fŕá völdum hnúti til allra annarra hnúta í grafinu
        BreadthFirstPaths bfp = new BreadthFirstPaths(g, v);

        for (int i=0; i<fjoldi; i++) {
            // tékkum hvort það sé til leið
            if (bfp.hasPathTo(i)) {
                // ef lengsta leiðin hingað til
                if (bfp.distTo(i) > max) max = bfp.distTo(i);
            }
        }
        // skilum lengstu leiðinni
        return max;
    }

    public int diameter() {
        /*
        Skilar hæsta eccentricity meðal allra hnúta í <this.g>.
         */

        int max = Integer.MIN_VALUE;
        // finnum hæsta gildið í eccentricity fylkinu okkar
        for (int i : ecc) {
            if (i > max) max = i;
        }
        return max;
    }

    public int radius() {
        /*
        Skilar lægsta eccentricity meðal allra hnúta í <this.g>.
         */

        int min = Integer.MAX_VALUE;
        // finnum hæsta gildið í eccentricity fylkinu okkar
        for (int i : ecc) {
            if (i < min) min = i;
        }
        return min;
    }

    public int center() {
        /*
        Skilar númeri hnúts í <this.g> sem hefur eccentricity = this.radius().
         */

        int center = -1;
        int r = this.radius();
        // finnum nr hnútsins
        for (int i : ecc) {
            if (i == r) {
                center = i;
                break;
            }
        }
        return center;
    }

    public static void main(String[] args) {
        SymbolGraph sg = new SymbolGraph("heima10/routes.txt", " ");
        GraphProperties gp = new GraphProperties(sg.graph());

        StdOut.println("Eiginleikar leiðanetsins:");
        StdOut.println("");
        StdOut.println("Þvermál:   " + gp.diameter());
        StdOut.println("Radíus:    " + gp.radius());
        StdOut.println("Miðhnútur: " + sg.nameOf(gp.center()));
        StdOut.println("");
        StdOut.println(" Völlur frávik ");
        StdOut.println("===============");
        for (int v = 0; v < sg.graph().V(); v++) {
            StdOut.println(String.format("  %-5s   %-4d", sg.nameOf(v), gp.eccentricity(v)));
        }
    }

}