Package util

Class CompleteWeightedGraph<V,​W extends java.lang.Comparable<W>>

java.lang.Object
util.CompleteWeightedGraph<V,​W>
public class CompleteWeightedGraph<V,​W extends java.lang.Comparable<W>>
extends java.lang.Object
This class represents a complete weighted graph and provides an interface to add vertices and extract the edge with minimal weight.

  • Nested Class Summary

    Nested Classes
    Modifier and Type Class Description
    class  CompleteWeightedGraph.Edge
    This class represents a weighted edge of the graph.

  • Constructor Summary

    Constructors
    Constructor Description
    CompleteWeightedGraph​(java.lang.Iterable<V> vertices, java.util.function.BiFunction<V,​V,​W> getWeight)
    Construct a complete weighted graph with the given vertices and the given function which calculates the weights between them.
    CompleteWeightedGraph​(java.util.function.BiFunction<V,​V,​W> getWeight)
    Construct a complete weighted graph which uses the given function to compute weghts of edges between vertices.

  • Method Summary

    Modifier and Type Method Description
    void add​(V vertex)
    Add a vertex to the complete graph, adding an edge to each existing vertex and calculating the weight of each of these.
    CompleteWeightedGraph.Edge extract()
    Remove the edge with the minimum weight and return it.
    int size()
    Get the size of the graph

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Constructor Details

    • CompleteWeightedGraph

      public CompleteWeightedGraph​(java.util.function.BiFunction<V,​V,​W> getWeight)
      Construct a complete weighted graph which uses the given function to compute weghts of edges between vertices.
      Parameters:
      getWeight - A function which computes the weight between two given vertices.

    • CompleteWeightedGraph

      public CompleteWeightedGraph​(java.lang.Iterable<V> vertices, java.util.function.BiFunction<V,​V,​W> getWeight)
      Construct a complete weighted graph with the given vertices and the given function which calculates the weights between them.
      Parameters:
      vertices - The vertices to add to the graph.
      getWeight - A function which computes the weight between two given vertices.

  • Method Details

    • add

      public void add​(V vertex)
      Add a vertex to the complete graph, adding an edge to each existing vertex and calculating the weight of each of these.
      Parameters:
      vertex - The vertex to add to the graph.

    • extract

      public CompleteWeightedGraph.Edge extract()
      Remove the edge with the minimum weight and return it. Assumes queue is not empty.
      Returns:
      The minumum weighted edge.
      Throws:
      java.util.NoSuchElementException - if the graph has no edges, i.e. when it has less than 2 vertices.

    • size

      public int size()
      Get the size of the graph
      Returns:
      the number of vertices in the graph