path: root/src/com.example.portfolio3/com/example/portfolio3/GraphAlgorithms.java

package com.example.portfolio3;

// origin: <https://moodle.ruc.dk/course/section.php?id=211877>

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/// foo
public class GraphAlgorithms {

    /// foo
    GraphAlgorithms() { }

    /// Calculates the length of a path or any other collection of edes
    ///
    /// does not require the edges to form a path
    ///
    /// @param edges  foo
    /// @return int
    public static int pathLength(final Collection<Edge> edges) {
        return edges.stream().mapToInt(e -> e.weight()).sum();
    }

    /// checks whether a list of edges form a path so that
    ///
    /// the to-vertex in one edge is the from-vertex of the next
    ///
    /// @param edges  foo
    /// @return       boolean
    public static boolean isPath(final List<Edge> edges) {
        for (int i = 1; i < edges.size(); i++) {
            if (edges.get(i - 1).to() != edges.get(i).from()) {
                return false;
            }
        }

        return true;
    }

    /// Calculates the length of a path vertices in a graph
    ///
    /// return null if vertices are not connected as a path
    ///
    /// @param g     foo
    /// @param path  foo
    /// @return      Integer
    public static Integer pathLength(final Graph g, final List<Vertex> path) {
        int length = 0;
        for (int i = 1; i < path.size(); i++) {
            Integer w = g.getWeight(path.get(i - 1), path.get(i));
            if (w == null) {
                return null;
            }
            length += w;
        }

        return length;
    }

    //------------------------------------------------------------
    //
    // Comparators and sorting methods

    /// Comparator of edges based on weight
    ///
    /// can be used for sorting a list of edges
    ///
    /// @param e1  foo
    /// @param e2  foo
    /// @return    int
    static int cmpEdgeWeight(final Edge e1, final Edge e2) {
        int w1 = e1.weight(), w2 = e2.weight();
        if (w1 != w2) {
            return w1 - w2;
        }
        if (e1.from() != e2.from()) {
            return e1.from().name().compareTo(e2.from().name());
        }

        return e1.to().name().compareTo(e2.to().name());
    }

    /// Comparator of edges based on from-vertex
    ///
    /// can be used for sorting a list of edges
    ///
    /// @param e1  foo
    /// @param e2  foo
    /// @return    int
    static int cmpEdgeFrom(final Edge e1, final Edge e2) {
        if (e1.from() != e2.from()) {
            return e1.from().name().compareTo(e2.from().name());
        }
        int w1 = e1.weight(), w2 = e2.weight();
        if (w1 != w2) {
            return w1 - w2;
        }

        return e1.to().name().compareTo(e2.to().name());
    }

    /// Comparator of edges based on from-vertex
    ///
    /// can be used for sorting a list of edges
    ///
    /// @param e1  foo
    /// @param e2  foo
    /// @return    int
    static int cmpEdgeTo(final Edge e1, final Edge e2) {
        if (e1.to() != e2.to()) {
            return e1.to().name().compareTo(e2.to().name());
        }
        if (e1.from() != e2.from()) {
            return e1.from().name().compareTo(e2.from().name());
        }
        int w1 = e1.weight(), w2 = e2.weight();

        return w1 - w2;
    }

    /// sort a collection of edges based on their weights
    ///
    /// @param edges  foo
    /// @return       List<Edge>
    static List<Edge> sortEdges(final Collection<Edge> edges) {
        ArrayList<Edge> list = new ArrayList<>(edges);
        Collections.sort(list, GraphAlgorithms::cmpEdgeWeight);

        return list;
    }

    /// sort a collection of edges based on from-vertex
    ///
    /// @param edges  foo
    /// @return       List<Edge>
    static List<Edge> sortEdgesFrom(final Collection<Edge> edges) {
        ArrayList<Edge> list = new ArrayList<>(edges);
        Collections.sort(list, GraphAlgorithms::cmpEdgeFrom);

        return list;
    }

    /// sort a collection of edges based on to-vertex
    ///
    /// @param edges  foo
    /// @return       List<Edge>
    static List<Edge> sortEdgesTo(final Collection<Edge> edges) {
        ArrayList<Edge> list = new ArrayList<>(edges);
        Collections.sort(list, GraphAlgorithms::cmpEdgeTo);

        return list;
    }

    /// sort a collection of vertices based on their name
    ///
    /// @param vertices  foo
    /// @return          List<Vertex>
    public static List<Vertex> sortVertex(final Collection<Vertex> vertices) {
        ArrayList<Vertex> list = new ArrayList<>(vertices);
        Collections.sort(list, (Vertex v1, Vertex v2) -> v1.name().compareTo(v2.name()));

        return list;
    }

    //------------------------------------------------------------
    //
    // Algorithms for traverse and minimum spanning tree

    /// traverse a graph depth first from a given vertex
    /// return the set of visited vertices
    ///
    /// @param g  foo
    /// @param v  foo
    /// @return   Set<Vertex>
    public static Set<Vertex> visitBreadthFirst(final Graph g, final Vertex v) {
        HashSet<Vertex> thisLevel = new HashSet<>();
        HashSet<Vertex> nextLevel = new HashSet<>();
        HashSet<Vertex> visited = new HashSet<>();
        thisLevel.add(v);
        while (thisLevel.size() > 0) {
            System.out.println("level " + thisLevel);
            for (Vertex w:thisLevel) {
                //System.out.println("visited " + w);
                visited.add(w);
                Collection<Edge> outedge = g.outEdge(w);
                if (outedge == null) {
                    continue;
                }
                for (Edge e: outedge) {
                    if (visited.contains(e.to())) {
                        continue;
                    }
                    if (thisLevel.contains(e.to())) {
                        continue;
                    }
                    nextLevel.add(e.to());
                }
            }
            thisLevel = nextLevel;
            nextLevel = new HashSet<Vertex>();
        }

        return visited;
    }

    /// traverse a graph depth first from a given vertex
    /// return the set of visited vertices
    ///
    /// @param g  foo
    /// @param v  foo
    /// @return   Set<Vertex>
    public static Set<Vertex> visitDepthFirst(final Graph g, final Vertex v) {
        HashSet<Vertex> visit = new HashSet<>();
        visitDepthFirst(g, v, visit);

        return visit;
    }

    /// foo
    ///
    /// @param g        foo
    /// @param v        foo
    /// @param visited  foo
    private static void visitDepthFirst(final Graph g, final Vertex v, final Set<Vertex> visited) {
        if (visited.contains(v)) {
            return;
        }
        //System.out.println("visited "+v);
        visited.add(v);
        for (Edge e: g.outEdge(v)) {
            visitDepthFirst(g, e.to(), visited);
        }
    }

    /// an implementation of Prim's algorithm
    ///
    /// naive implementation without priorityqueue
    ///
    /// @param g  foo
    /// @return   Set<Edge>
    public static Set<Edge> minimumSpanningTree(final Graph g) {
        Collection<Edge> edges = g.edges();
        HashSet<Edge> mst = new HashSet<>();
        HashSet<Vertex> frontier = new HashSet<>();
        for (Edge e:edges) {
            frontier.add(e.from());
            break;
        }
        while (true) {
            Edge nearest = null;
            for (Edge e: edges) {
                if (!frontier.contains(e.from())) {
                    continue;
                }
                if (frontier.contains(e.to())) {
                    continue;
                }
                if (nearest == null || nearest.weight() > e.weight()) {
                    nearest = e;
                }
            }
            if (nearest == null) {
                break;
            }
            mst.add(nearest);
            frontier.add(nearest.to());
        }

        return mst;
    }

    /// returns the tree of shortest paths
    /// from start to all vertices in the graph
    ///
    /// naive implementation without a prorityqueue
    ///
    /// @param g      foo
    /// @param start  foo
    /// @return       Set<Edge>
    public static Set<Edge> dijkstra(final Graph g, final Vertex start) {

        // create table for done, prev and weight from start
        int maxint = Integer.MAX_VALUE;
        HashSet<Vertex> done = new HashSet<>();
        HashMap<Vertex, Edge> prev = new HashMap<>();
        HashMap<Vertex, Integer> weight = new HashMap<>();
        for (Vertex w: g.vertices()) {
            weight.put(w, maxint);
        }

        // start node is done, distance 0 from start
        weight.put(start, 0);
        done.add(start);

        while (true) {

            // find nearest from a done vertex
            Vertex nearest = null;
            int neardist = maxint;
            Edge done2near = null;
            for (Vertex w1:done) {
                for (Edge e :g.outEdge(w1)) {
                    Vertex w2 = e.to();
                    if (done.contains(w2)) {
                        continue;
                    }
                    if ((weight.get(w1) + e.weight()) < neardist) {
                        nearest = e.to();
                        neardist = weight.get(w1) + e.weight();
                        done2near = e;
                    }
                }
            }

            // System.out.println("find nearest "+done2near);
            // if no more, then we are done
            if (nearest == null) {
                break;
            }

            // update distance from this node to other nodes
            for (Edge e1 : g.outEdge(nearest)) {
                Vertex w3 = e1.to();
                int wght = e1.weight();
                if (weight.get(w3) > (neardist + wght)) {
                    weight.put(w3, neardist + wght);
                }
            }
            done.add(nearest);
            prev.put(nearest, done2near);
            weight.put(nearest, neardist);
        }

        return new HashSet<Edge>(prev.values());
    }

    //------------------------------------------------------------
    //
    // IO operations

    /// read a comma-separated file
    /// in the format <vertex> , <vertex> , <weight>
    ///
    /// stores file as bidirectional graph
    ///
    /// @param g     foo
    /// @param file  foo
    public static void readGraph(final Graph g, final String file) {
        try {
            BufferedReader in = new BufferedReader(new FileReader(file));
            for (String line = in.readLine(); line != null; line = in.readLine()) {
                if (line.length() == 0) {
                    continue;
                }
                String[] arr = line.split(",");
                if (arr.length != 3) {
                    throw new RuntimeException("CSV file format error: " + line);
                }
                g.insertEdge(arr[0].trim(), arr[1].trim(), Integer.parseInt(arr[2].trim()));
                g.insertEdge(arr[1].trim(), arr[0].trim(), Integer.parseInt(arr[2].trim()));
            }
            in.close();
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }

    /// foo
    ///
    /// @param g  foo
    public static void printGraph(final Graph g) {
        for (Vertex v: sortVertex(g.vertices())) {
            System.out.println(v.toString());
            for (Edge e: sortEdgesTo(g.outEdge(v))) {
                System.out.println("  " + e.toString());
            }
        }
    }

    /// store a list of lines as a file
    ///
    /// @param list  foo
    /// @param f     foo
    public static void storeStrings(final List<String> list, final String f) {
        try {
            PrintWriter out = new PrintWriter(new FileWriter(f));
            for (String s: list) {
                out.println(s);
            }
            out.close();
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }

    /// read a file a returns a list of lines
    ///
    /// @param f  foo
    /// @return   ArrayList
    public static ArrayList<String> loadStrings(final String f) {
        ArrayList<String> list = new ArrayList<>();
        try {
            BufferedReader in = new BufferedReader(new FileReader(f));
            while (true) {
                String s = in.readLine();
                if (s == null) {
                    break;
                }
                list.add(s);
            }
            in.close();
        } catch (IOException e) {
            throw new RuntimeException(e);
        }

        return list;
    }
}