Class WeightedGraph<V,E>

java.lang.Object
com.phasmidsoftware.gryphon.java.Graph<V>
com.phasmidsoftware.gryphon.java.WeightedGraph<V,E>
Type Parameters:
V - the vertex type. Must implement equals and hashCode.
E - the edge attribute (weight) type.

public class WeightedGraph<V,E> extends Graph<V>
A mutable, lazily-materialised façade over Gryphon's purely functional graph types, with a typed edge attribute E.

WeightedGraph<V, E> extends Graph<V> by enforcing that all edges carry an attribute of type E. This gives the compiler (and the algorithm façades) a typed handle on edge weights, eliminating the runtime casts required when using plain Graph<V> with WeightedEdge<V, E>.

Directionality is fixed at construction time via the factory methods Graph.directed() and Graph.undirected().

Plain BFS and DFS are inherited from Graph<V> and work identically — edge weights are ignored for traversal purposes.

Weighted algorithms (ShortestPaths, MinimumSpanningTree) accept a WeightedGraph<V, E> directly, removing the need for runtime casts and making the weight type visible to the compiler.

Usage example:


 WeightedGraph<Building, TunnelProperties> g = WeightedGraph.undirected();
 g.addEdge(new WeightedEdge<>(b1, b2, tunnelProperties));

 Map<Building, WeightedEdge<Building, TunnelProperties>> mst =
     MinimumSpanningTree.prim(g, start,
         Comparator.comparingInt(tp -> tp.cost));
 
  • Method Details

    • directedWeighted

      public static <V, E> WeightedGraph<V,E> directedWeighted()
      Creates an empty directed weighted graph.
      Type Parameters:
      V - the vertex type.
      E - the edge attribute type.
      Returns:
      a new empty directed WeightedGraph.
    • undirectedWeighted

      public static <V, E> WeightedGraph<V,E> undirectedWeighted()
      Creates an empty undirected weighted graph.
      Type Parameters:
      V - the vertex type.
      E - the edge attribute type.
      Returns:
      a new empty undirected WeightedGraph.
    • undirectedFromResource

      public static WeightedGraph<Integer,Double> undirectedFromResource(String resourceName)
      Reads an undirected weighted graph with Integer vertices and Double edge weights from a classpath resource.
      Parameters:
      resourceName - the classpath resource name (e.g. "prim.graph").
      Returns:
      a populated undirected WeightedGraph<Integer, Double>.
      Throws:
      RuntimeException - if the resource is not found or cannot be parsed.
    • directedFromResource

      public static WeightedGraph<Integer,Double> directedFromResource(String resourceName)
      Reads a directed weighted graph with Integer vertices and Double edge weights from a classpath resource.
      Parameters:
      resourceName - the classpath resource name (e.g. "routes.graph").
      Returns:
      a populated directed WeightedGraph<Integer, Double>.
      Throws:
      RuntimeException - if the resource is not found or cannot be parsed.
    • undirectedFromResource

      public static <V, E> WeightedGraph<V,E> undirectedFromResource(String resourceName, Function<String,V> vertexParser, Function<String,E> edgeParser)
      Reads an undirected weighted graph from a classpath resource using custom vertex and edge parsers.

      Use this variant when your vertices or edges are not plain Integer/Double — for example, building names or composite tunnel properties.

      Type Parameters:
      V - the vertex type.
      E - the edge attribute type.
      Parameters:
      resourceName - the classpath resource name.
      vertexParser - parses a single token into a V.
      edgeParser - parses a single token into an E.
      Returns:
      a populated undirected WeightedGraph<V, E>.
      Throws:
      RuntimeException - if the resource is not found or cannot be parsed.
    • directedFromResource

      public static <V, E> WeightedGraph<V,E> directedFromResource(String resourceName, Function<String,V> vertexParser, Function<String,E> edgeParser)
      Reads a directed weighted graph from a classpath resource using custom vertex and edge parsers.
      Type Parameters:
      V - the vertex type.
      E - the edge attribute type.
      Parameters:
      resourceName - the classpath resource name.
      vertexParser - parses a single token into a V.
      edgeParser - parses a single token into an E.
      Returns:
      a populated directed WeightedGraph<V, E>.
      Throws:
      RuntimeException - if the resource is not found or cannot be parsed.
    • addEdge

      public void addEdge(WeightedEdge<V,E> edge)
      Adds a typed weighted edge to this graph.

      Both endpoint vertices are added automatically if not already present. For undirected graphs the reverse edge is also recorded internally.

      NOTE that the present design results in maintaining two edge lists. Clearly, we could easily improve the implementation but for pedagogical purposes, this is acceptable.

      Parameters:
      edge - the weighted edge to add.
    • addEdge

      public void addEdge(Edge<V> edge)
      Adds an unweighted edge.

      Overrides Graph.addEdge(Edge) to throw IllegalArgumentException if the edge is not a WeightedEdge — a WeightedGraph requires all edges to carry an attribute.

      Overrides:
      addEdge in class Graph<V>
      Parameters:
      edge - the edge to add; must be a WeightedEdge.
      Throws:
      IllegalArgumentException - if edge is not a WeightedEdge.
    • weightedEdges

      public List<WeightedEdge<V,E>> weightedEdges()
      Returns the typed weighted edge list — each edge stored once, as originally added, with full type information preserved.

      This is the method used by the algorithm bridge to materialise the Scala graph without runtime casts.

      Returns:
      an unmodifiable list of typed weighted edges.
    • toString

      public String toString()
      Overrides:
      toString in class Graph<V>