Class Graph<V>

java.lang.Object
com.github.yellowstonegames.path.Graph<V>
Type Parameters:
V - the vertex type; often Coord
All Implemented Interfaces:
Externalizable, Serializable
Direct Known Subclasses:
DirectedGraph, UndirectedGraph
public abstract class Graph<V> extends Object implements Externalizable
Abstract superclass of actual Graph types.
See Also:

  • Field Details

    • vertexMap

      protected com.github.tommyettinger.ds.ObjectObjectOrderedMap<V,Node<V>> vertexMap

    • edgeSet

      protected com.github.tommyettinger.ds.ObjectOrderedSet<Connection<V>> edgeSet

  • Constructor Details

    • Graph

      protected Graph()

    • Graph

      protected Graph(Collection<V> vertices)

  • Method Details

    • obtainEdge

      protected abstract Connection<V> obtainEdge()

    • createNew

      protected abstract Graph<V> createNew()

    • algorithms

      public abstract Algorithms<V> algorithms()

    • addVertex

      public boolean addVertex(V v)
      Adds a vertex to the graph.
      Parameters:
      v - the vertex to be added
      Returns:
      true if the vertex was not already in the graph, false otherwise

    • addVertices

      public void addVertices(Collection<V> vertices)
      Adds all the vertices in the collection to the graph.
      Parameters:
      vertices - a collection of vertices to be added

    • addVertices

      @SafeVarargs public final void addVertices(V... vertices)
      Adds all the vertices in the array or varargs to the graph.
      Parameters:
      vertices - an array or varargs of vertices to be added

    • removeVertex

      public boolean removeVertex(V v)
      Removes a vertex from the graph, and any adjacent edges.
      Parameters:
      v - the vertex to be removed
      Returns:
      true if the vertex was in the graph, false otherwise

    • removeVertices

      public void removeVertices(Collection<V> vertices)
      Removes all the vertices in the collection from the graph, and any adjacent edges.
      Parameters:
      vertices - vertices a collection of vertices to be removed

    • removeVertexIf

      public void removeVertexIf(com.github.tommyettinger.function.ObjPredicate<V> predicate)

    • disconnect

      public void disconnect(V v)

    • disconnect

      protected void disconnect(Node<V> node)

    • addEdge

      public Connection<V> addEdge(V v, V w)
      Add an edge to the graph, from v to w. The edge will have a default weight of 1. If there is already an edge between v and w, its weight will be set to 1.
      Parameters:
      v - the source vertex of the edge
      w - the destination vertex of the edge
      Returns:
      the edge

    • addEdge

      public Connection<V> addEdge(V v, V w, float weight)
      Add an edge to the graph, from v to w and with the specified weight. If there is already an edge between v and w, its weight will be set to the specified weight.
      Parameters:
      v - the source vertex of the edge
      w - the destination vertex of the edge
      weight - the weight of the edge
      Returns:
      the edge

    • removeEdge

      public boolean removeEdge(V v, V w)
      Removes the edge from v to w from the graph.
      Parameters:
      v - the source vertex of the edge
      w - the destination vertex of the edge
      Returns:
      the edge if there exists an edge from v to w, or null if there is no edge

    • removeEdge

      public boolean removeEdge(Edge<V> edge)

    • removeEdges

      public void removeEdges(Collection<? extends Edge<V>> edges)

    • removeEdgeIf

      public void removeEdgeIf(com.github.tommyettinger.function.ObjPredicate<Edge<V>> predicate)

    • removeAllEdges

      public void removeAllEdges()
      Removes all edges from the graph.

    • removeAllVertices

      public void removeAllVertices()
      Removes all vertices and edges from the graph.

    • sortVertices

      public void sortVertices(Comparator<V> comparator)
      Sort the vertices using the provided comparator. This is reflected in the iteration order of the collection returned by getVertices(), as well as algorithms which involve iterating over all vertices.
      Parameters:
      comparator - a comparator for comparing vertices

    • sortEdges

      public void sortEdges(Comparator<Connection<V>> comparator)
      Sort the edges using the provided comparator. This is reflected in the iteration order of the collection returned by getEdges(), as well as algorithms which involve iterating over all edges.
      Parameters:
      comparator - a comparator for comparing edges

    • removeNode

      protected void removeNode(Node<V> node)

    • addConnection

      protected Connection<V> addConnection(Node<V> a, Node<V> b)

    • addConnection

      protected Connection<V> addConnection(Node<V> a, Node<V> b, float weight)

    • removeConnection

      protected boolean removeConnection(Node<V> a, Node<V> b)

    • contains

      public boolean contains(V v)
      Check if the graph contains a vertex.
      Parameters:
      v - the vertex with which to check
      Returns:
      true if the graph contains the vertex, false otherwise

    • getEdge

      public Connection<V> getEdge(V v, V w)
      Retrieve the edge which is from v to w.
      Parameters:
      v - the source vertex of the edge
      w - the destination vertex of the edge
      Returns:
      the edge if it is in the graph, otherwise null

    • edgeExists

      public boolean edgeExists(V v, V w)
      Check if the graph contains an edge from v to w.
      Parameters:
      v - the source vertex of the edge
      w - the destination vertex of the edge
      Returns:
      true if the edge is in the graph, false otherwise

    • getEdges

      public List<? extends Connection<V>> getEdges(V v)
      Get a List containing all the edges which have v as a source.
      Parameters:
      v - the source vertex of all the edges
      Returns:
      a List of edges

    • getEdges

      public com.github.tommyettinger.ds.ObjectOrderedSet<? extends Connection<V>> getEdges()
      Get an ObjectOrderedSet containing all the edges in the graph.
      Returns:
      an ObjectOrderedSet of all the edges in the graph

    • getVertices

      public Set<V> getVertices()
      Get a Set containing all the vertices in the graph.
      Returns:
      a Set of all the vertices in the graph

    • isDirected

      public boolean isDirected()
      Check if the graph is directed, that is whether the edges form an ordered pair or a set.
      Returns:
      whether the graph is directed

    • size

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

    • getEdgeCount

      public int getEdgeCount()
      Get the number of edges in the graph.
      Returns:
      the number of edges

    • writeExternal

      public void writeExternal(ObjectOutput out) throws IOException
      Meant for serialization using Fory. If a class overrides this with different behavior, readExternal(ObjectInput) must also be overridden to match that behavior.
      Specified by:
      writeExternal in interface Externalizable
      Parameters:
      out - the stream to write the object to
      Throws:
      IOException - Includes any I/O exceptions that may occur

    • readExternal

      public void readExternal(ObjectInput in) throws IOException, ClassNotFoundException
      Meant for deserialization using Fory. If a class overrides this with different behavior, writeExternal(ObjectOutput) must also be overridden to match that behavior.
      Specified by:
      readExternal in interface Externalizable
      Parameters:
      in - the stream to read data from in order to restore the object
      Throws:
      IOException - if I/O errors occur
      ClassNotFoundException - If the class for an object being restored cannot be found.

    • getNode

      protected Node<V> getNode(V v)

    • getNodes

      protected Collection<Node<V>> getNodes()

    • connectionExists

      protected boolean connectionExists(Node<V> u, Node<V> v)

    • getEdge

      protected Connection<V> getEdge(Node<V> a, Node<V> b)

    • equals

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

    • hashCode

      public int hashCode()
      Overrides:
      hashCode in class Object