CS2 - Unnamed repository; edit this file 'description' to name the repository.

path: root/src/com.example.portfolio2/com/example/portfolio2

diff options

Diffstat (limited to 'src/com.example.portfolio2/com/example/portfolio2')

0 files changed, 0 insertions, 0 deletions

.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

///


context:
space:
mode: