Class HashGraph<V,E>

java.lang.Object
rgu.transport.algorithms.collections.HashGraph<V,E>
Type Parameters:
V - the vertex type
E - the edge type
All Implemented Interfaces:
Explorable<V,E>, Graph<V,E>
public final class HashGraph<V,E> extends Object implements Graph<V,E>
A mathematical graph which uses an underling hashed representation of vertices. HashGraph is immutable and safe for concurrent use, however, HashGraph.Builder returned by builder() is not safe for concurrent use.
Author:
Lee A. Christie

  • Method Details

    • builder

      public static <V,E> HashGraph.Builder<V,E> builder()
      Returns a new builder for HashGraph. Builder is not safe for concurrent use.
      Type Parameters:
      V - the vertex type
      E - the edge type
      Returns:
      a builder

    • vertices

      public Set<V> vertices()
      The set of vertices in the graph.
      Specified by:
      vertices in interface Graph<V,E>
      Returns:
      the set of vertices

    • containsVertex

      public boolean containsVertex(V vertex)
      Checks whether the graph contains the specified vertex.
      Specified by:
      containsVertex in interface Graph<V,E>
      Parameters:
      vertex - the vertex, not null
      Returns:
      true if contained, false otherwise

    • edge

      public E edge(V from, V to)
      returns the edge between the specified pair of vertices.
      Specified by:
      edge in interface Explorable<V,E>
      Parameters:
      from - the vertex for which this will be an out-edge, not null
      to - the vertex for which this will be an in-edge, not null
      Returns:
      the edge
      Throws:
      NoSuchElementException - if the edge does not exist between from and to

    • containsEdge

      public boolean containsEdge(V from, V to)
      Checks whether the graph contains an edge from one specified source to another.
      Specified by:
      containsEdge in interface Graph<V,E>
      Parameters:
      from - the vertex for which this is an out-edge, not null
      to - the vertex for which this is an in-edge, not null
      Returns:
      if the edge exists, false otherwise
      Throws:
      NoSuchElementException - if either vertex does not exist

    • neighbours

      public Set<V> neighbours(V vertex)
      The vertices for which there is an out-edge from the specified vertex to that vertex.
      Specified by:
      neighbours in interface Explorable<V,E>
      Parameters:
      vertex - the specified vertex, not null
      Returns:
      the set of neighbours

    • reverse

      public Graph<V,E> reverse()
      Description copied from interface: Graph
      Returns a view of the graph with all edges reversed.
      Specified by:
      reverse in interface Graph<V,E>
      Returns:
      a view of the graph

    • reverseNeighbours

      public Set<V> reverseNeighbours(V vertex)
      The vertices for which there is an in-edge to the specified vertex from that vertex.
      Parameters:
      vertex - the specified vertex, not null
      Returns:
      the set of reverse neighbours

    • symmetricConnectedComponents

      public List<Graph<V,E>> symmetricConnectedComponents()
      Finds the connected components of the graph, assuming that the graph is symmetric in structure. This requires that at least that for every edge (A, B) there exists an edge (B, A), even if the value of the edge is different.
      Specified by:
      symmetricConnectedComponents in interface Graph<V,E>
      Returns:
      a list of fully-connected sub graphs ordered from largest to smallest

    • toSymmetricStructure

      public Graph<V,E> toSymmetricStructure(Function<Graph.Edge<V,E>, E> edgeMap)
      Returns a graph which is equal to this graph but symmetric. The provided callback function is called for each one-way edge, and must return null to indicate that the edge should be removed, or a non-null value to indicate that the reverse edge should be added with the returned value.
      Specified by:
      toSymmetricStructure in interface Graph<V,E>
      Parameters:
      edgeMap - mapping for how to handle each one-way edge, not null
      Returns:
      a symmetric graph

    • applyToEdges

      public Graph<V,E> applyToEdges(Function<Graph.Edge<V,E>, E> edgeMap)
      Returns a graph which is equal to this graph but with the specified transformation applied to all edges. The provided callback function is called for each edge, and must return null to indicate that the edge should be removed, or a non-null value to indicate that the edge should become equal to the given edge value. Identity mapping will preserve the same edge.
      Specified by:
      applyToEdges in interface Graph<V,E>
      Parameters:
      edgeMap - mapping a transformation of edges, not null
      Returns:
      a graph
      Throws:
      UnsupportedOperationException - if the graph implementation does not support applyToEdges

    • forEachEdge

      public void forEachEdge(Consumer<Graph.Edge<V,E>> consumer)
      Iterates over edges, calling the given callback function for each edge in the graph.
      Specified by:
      forEachEdge in interface Graph<V,E>
      Parameters:
      consumer - a consumer of edges, not null
      Throws:
      UnsupportedOperationException - if the graph implementation does not support this operation

    • preserveVertices

      public Graph<V,E> preserveVertices(Predicate<V> preserve)
      Returns a graph which is equal to this graph but with only the vertices matching the specified predicate. The provided callback function is called for each vertex, and must return false to indicate that the edge should be removed, true value to indicate that the edge should be preserved. If a vertex is deleted, connected in or out edges for that vertex are also deleted.
      Specified by:
      preserveVertices in interface Graph<V,E>
      Parameters:
      preserve - predicate indicating which vertices to preserve, not null
      Returns:
      a graph
      Throws:
      UnsupportedOperationException - if the graph implementation does not support preserveVertices

    • hashCode

      public int hashCode()
      Overrides:
      hashCode in class Object

    • equals

      public boolean equals(Object obj)
      Overrides:
      equals in class Object

    • toString

      public String toString()
      An incomplete summary string representation of the graph.
      Overrides:
      toString in class Object
      Returns:
      string representation