Class Graph<V,E>

java.lang.Object
Graph<V,E>
public class Graph<V,E> extends Object
A graph implementation that allows for vertices and edges to hold distinct data entries of different types.

  • Constructor Details

    • Graph

      public Graph()
      Creates an empty graph.

    • Graph

      public Graph(int n)
      Creates a graph with n (data-less) vertices and no edges.
      Parameters:
      n - the number of vertices to create

    • Graph

      public Graph(Collection<? extends Graph.Edge<V,E>> c)
      Uses the specified edges to create a graph.

      This graph does not contain these edges themselves, but rather creates shallow copies of the underyling vertices and edges. This means that modifying the data of the graph created will result in changes to the data of the edges and vertices specified.

      Parameters:
      c - the collection of edges from which to build this graph

  • Method Details

    • getVertices

      public Collection<Graph.Vertex<V,E>> getVertices()
      Returns the collection of vertices that backs this Graph.

      Changing this collection has effects on the Graph; the collection is cloneable, so any changes should probably be applied to a cloned copy of this collection.

      Returns:
      the collection of vertices in this Graph.

    • getEdges

      public Collection<Graph.Edge<V,E>> getEdges()
      Returns the collection of edges that backs this Graph.

      Changing this collection has effects on the Graph; the collection is cloneable, so any changes should probably be applied to a cloned copy of this collection.

      Returns:
      the collection of edges in this Graph.

    • getVertex

      public Graph.Vertex<V,E> getVertex(int index)
      Returns the vertex created at the specified index (so getVertex(0) is the first vertex created, getVertex(1) is the second, etc.).
      Parameters:
      index - the position of the vertex to be returned
      Returns:
      the vertex created at the specified index.

    • getEdge

      public Graph.Edge<V,E> getEdge(int i, int j)
      Returns the edge between the vertices returned by getVertex(i) and getVertex(j), or null if no such edge exists.

      Specifically, an edge will be returned if and only if there is an undirected edge between getVertex(i) and getVertex(j) or a directed edge from getVertex(i) to getVertex(j).

      Parameters:
      i - the position of the first vertex
      j - the position of the second vertex
      Returns:
      the edge between the vertices returned by getVertex(i) and getVertex(j), or null if no such edge exists.

    • getEdge

      public Graph.Edge<V,E> getEdge(Graph.Vertex<V,E> u, Graph.Vertex<V,E> v)
      Returns the edge between the vertices u and v, or null if no such edge exists.

      Specifically, an edge will be returned if and only if there is an undirected edge between u and v or a directed edge from u to v.

      Parameters:
      u - the source vertex
      v - the target vertex
      Returns:
      the edge between the vertices u and v, or null if no such edge exists.

    • addVertex

      public Graph.Vertex<V,E> addVertex()
      Creates a new data-less vertex, adds it to this graph, then returns it.
      Returns:
      a new data-less vertex.

    • addVertex

      public Graph.Vertex<V,E> addVertex(V data)
      Creates, add to the graph, and returns a new vertex with the specified data.
      Parameters:
      data - the associated data of the vertex to be created
      Returns:
      a new vertex with the specified data.

    • addEdge

      public boolean addEdge(Graph.Edge<V,E> edge)
      Adds the specified edge to the graph.

      If this edge already exists in the graph, ie if there is any edge in the graph which equals this edge, does nothing.

      Parameters:
      edge - the edge to be added
      Returns:
      true if this edge did not already exist in the graph.

    • addEdge

      public Graph.Edge<V,E> addEdge(Graph.Vertex<V,E> u, Graph.Vertex<V,E> v)
      Adds an undirected edge with the specified endpoints to the graph.

      If this edge already exists in the graph, ie if there is any edge in the graph which equals this edge, does nothing.

      Parameters:
      u - an endpoint of the edge to be created
      v - an endpoint of the edge to be created
      Returns:
      the edge created, or null if the edge already exists.

    • addEdge

      public Graph.Edge<V,E> addEdge(int i, int j)
      Adds an edge with the specified endpoints and data to the graph. If directed, the resulting edge will be a directed edge, otherwise it is undirected.

      If this edge already exists in the graph, ie if there is any edge in the graph which equals this edge, does nothing.

      Parameters:
      i - a positional endpoint of the edge to be created
      j - a positional endpoint of the edge to be created
      Returns:
      the edge if it doesn't already exist in this graph, otherwise null.

    • addEdge

      public Graph.Edge<V,E> addEdge(Graph.Vertex<V,E> u, Graph.Vertex<V,E> v, boolean directed)
      Adds an edge with the specified endpoints to the graph. If directed, the resulting edge will be a directed edge, otherwise it is undirected.

      If this edge already exists in the graph, ie if there is any edge in the graph which equals this edge, does nothing.

      Parameters:
      u - an endpoint of the edge to be created
      v - an endpoint of the edge to be created
      directed - whether the edge to be created will be directed
      Returns:
      the edge if it doesn't already exist in this graph, otherwise null.

    • addEdge

      public Graph.Edge<V,E> addEdge(int i, int j, boolean directed)
      Adds an edge with the specified endpoints to the graph. If directed, the resulting edge will be a directed edge, otherwise it is undirected.

      If this edge already exists in the graph, ie if there is any edge in the graph which equals this edge, does nothing.

      Parameters:
      i - a positional endpoint of the edge to be created
      j - a positional endpoint of the edge to be created
      directed - whether the edge to be created will be directed
      Returns:
      the edge if it doesn't already exist in this graph, otherwise null.

    • addEdge

      public Graph.Edge<V,E> addEdge(Graph.Vertex<V,E> u, Graph.Vertex<V,E> v, E data)
      Adds an undirected edge with the specified endpoints and data to the graph.

      If this edge already exists in the graph, ie if there is any edge in the graph which equals this edge, does nothing.

      Parameters:
      u - an endpoint of the edge to be created
      v - an endpoint of the edge to be created
      data - the data of the edge to be created
      Returns:
      the edge if it doesn't already exist in this graph, otherwise null.

    • addEdge

      public Graph.Edge<V,E> addEdge(int i, int j, E data)
      Adds an undirected edge with the specified endpoints and data to the graph.

      If this edge already exists in the graph, ie if there is any edge in the graph which equals this edge, does nothing.

      Parameters:
      i - a positional endpoint of the edge to be created
      j - a positional endpoint of the edge to be created
      data - the data of the edge to be created
      Returns:
      the edge if it doesn't already exist in this graph, otherwise null.

    • addEdge

      public Graph.Edge<V,E> addEdge(int i, int j, boolean directed, E data)
      Adds an edge with the specified endpoints and data to the graph. If directed, the resulting edge will be a directed edge, otherwise it is undirected.

      If this edge already exists in the graph, ie if there is any edge in the graph which equals this edge, does nothing.

      Parameters:
      i - a positional endpoint of the edge to be created
      j - a positional endpoint of the edge to be created
      directed - whether the edge to be created will be directed
      data - the data of the edge to be created
      Returns:
      the edge if it doesn't already exist in this graph, otherwise null.

    • addEdge

      public Graph.Edge<V,E> addEdge(Graph.Vertex<V,E> u, Graph.Vertex<V,E> v, boolean directed, E data)
      Adds an edge with the specified endpoints and data to the graph. If directed, the resulting edge will be a directed edge, otherwise it is undirected.

      If this edge already exists in the graph, ie if there is any edge in the graph which equals this edge, does nothing.

      Parameters:
      u - an endpoint of the edge to be created
      v - an endpoint of the edge to be created
      directed - whether the edge to be created will be directed
      data - the data of the edge to be created
      Returns:
      the edge if it doesn't already exist in this graph, otherwise null.

    • addEdge

      public Graph.WeightedEdge<V,E> addEdge(Graph.Vertex<V,E> u, Graph.Vertex<V,E> v, double weight)
      Adds a weighted edge with the specified endpoints, weight and data to the graph. If directed, the resulting edge will be a directed edge, otherwise it is undirected.

      If this edge already exists in the graph, ie if there is any edge in the graph which equals this edge, does nothing.

      Parameters:
      u - an endpoint of the edge to be created
      v - an endpoint of the edge to be created
      weight - the weight of the edge to be created
      Returns:
      the newly created edge, or null if this edge already exists.

    • addEdge

      public Graph.WeightedEdge<V,E> addEdge(int i, int j, double weight)
      Adds a weighted edge with the specified endpoints and weight to the graph.

      If this edge already exists in the graph, ie if there is any edge in the graph which equals this edge, does nothing.

      Parameters:
      i - the position of an endpoint of the edge to be created
      j - the position of an endpoint of the edge to be created
      weight - the weight of the edge to be created
      Returns:
      the newly created edge, or null if this edge already exists.

    • addEdge

      public Graph.WeightedEdge<V,E> addEdge(Graph.Vertex<V,E> u, Graph.Vertex<V,E> v, double weight, boolean directed)
      Adds a weighted edge with the specified endpoints and weight to the graph. If directed, the resulting edge will be a directed edge, otherwise it is undirected.

      If this edge already exists in the graph, ie if there is any edge in the graph which equals this edge, does nothing.

      Parameters:
      u - an endpoint of the edge to be created
      v - an endpoint of the edge to be created
      weight - the weight of the edge to be created
      directed - whether the edge to be created will be directed
      Returns:
      the newly created edge, or null if this edge already exists.

    • addEdge

      public Graph.WeightedEdge<V,E> addEdge(int i, int j, double weight, boolean directed)
      Adds a weighted edge with the specified endpoints and weight to the graph. If directed, the resulting edge will be a directed edge, otherwise it is undirected.

      If this edge already exists in the graph, ie if there is any edge in the graph which equals this edge, does nothing.

      Parameters:
      i - the position of an endpoint of the edge to be created
      j - the position of an endpoint of the edge to be created
      weight - the weight of the edge to be created
      directed - whether the edge to be created will be directed
      Returns:
      the newly created edge, or null if this edge already exists.

    • addEdge

      public Graph.WeightedEdge<V,E> addEdge(Graph.Vertex<V,E> u, Graph.Vertex<V,E> v, double weight, E data)
      Adds a weighted edge with the specified endpoints, weight and data to the graph.

      If this edge already exists in the graph, ie if there is any edge in the graph which equals this edge, does nothing.

      Parameters:
      u - an endpoint of the edge to be created
      v - an endpoint of the edge to be created
      weight - the weight of the edge to be created
      data - the data of the edge to be created
      Returns:
      the newly created edge, or null if this edge already exists.

    • addEdge

      public Graph.WeightedEdge<V,E> addEdge(int i, int j, double weight, E data)
      Adds a weighted edge with the specified endpoints, weight and data to the graph.

      If this edge already exists in the graph, ie if there is any edge in the graph which equals this edge, does nothing.

      Parameters:
      i - the position of an endpoint of the edge to be created
      j - the position of an endpoint of the edge to be created
      weight - the weight of the edge to be created
      data - the data of the edge to be created
      Returns:
      the newly created edge, or null if this edge already exists.

    • addEdge

      public Graph.WeightedEdge<V,E> addEdge(int i, int j, double weight, boolean directed, E data)
      Adds a weighted edge with the specified endpoints, weight and data to the graph. If directed, the resulting edge will be a directed edge, otherwise it is undirected.

      If this edge already exists in the graph, ie if there is any edge in the graph which equals this edge, does nothing.

      Parameters:
      i - the position of an endpoint of the edge to be created
      j - the position of an endpoint of the edge to be created
      weight - the weight of the edge to be created
      directed - whether the edge to be created will be directed
      data - the data of the edge to be created
      Returns:
      the newly created edge, or null if this edge already exists.

    • addEdge

      public Graph.WeightedEdge<V,E> addEdge(Graph.Vertex<V,E> u, Graph.Vertex<V,E> v, double weight, boolean directed, E data)
      Adds a weighted edge with the specified endpoints, weight and data to the graph. If directed, the resulting edge will be a directed edge, otherwise it is undirected.

      If this edge already exists in the graph, ie if there is any edge in the graph which equals this edge, does nothing.

      Parameters:
      u - an endpoint of the edge to be created
      v - an endpoint of the edge to be created
      weight - the weight of the edge to be created
      directed - whether the edge to be created will be directed
      data - the data of the edge to be created
      Returns:
      the newly created edge, or null if this edge already exists.

    • adjacencyMatrix

      public boolean[][] adjacencyMatrix()
      Returns the adjacency matrix of this graph.

      Specifically, returns a boolean matrix M where M[i][j] denotes if there is an edge from getVertex(i) to getVertex(j).

      Returns:
      the adjaceny matrix of this graph.

    • reverse

      public Graph<V,E> reverse()
      Returns a shallow copy of this graph where all edges have been reversed.
      Returns:
      a shallow copy of this graph where all edges have been reversed.

    • toString

      public String toString()
      Overrides:
      toString in class Object