Package com.graphs.struct

Class Graph<T>

java.lang.Object
com.graphs.struct.Graph<T>
Type Parameters:
T - the bounding type stored in this graph in its vertices.
public class Graph<T> extends Object
This class implements undirected unweighted graphs. Adding loops and multiple edges is not supported. Adding a vertex with a neither negative nor duplicated index is not supported. A graph can store values in each vertex. 
 Minimal size: 0 (no vertices)
 Theoretical maximal size: Integer.MAX_VALUE
Since:
1.0-beta
Version:
JDK 1.7
Author:
Łukasz Malara

  • Field Details

    • itsVertices

      private final List<Graph<T>.Vertex<T>> itsVertices
      This field represents all vertices of this graph. 
        Minimal size: 0 (empty)
  Theoretical maximal size: Integer.MAX_VALUE
      Since:
      1.0-beta

  • Constructor Details

    • Graph

      public Graph(@NotNull @NotNull String fileSource) throws NegativeVertexIndexException
      This constructor creates a graph based on a strictly defined pattern provided in a text file. Path to file is given as a String parameter. The graph is created only if the algorithm ends successfully.
      Parameters:
      fileSource - absolute or relative path to a file required to create a graph.
      Throws:
      NegativeVertexIndexException - if negative number was provided in a file.
      Since:
      1.0-beta

  • Method Details

    • complete

      public Graph<T> complete(int startIndex, int size) throws NegativeVertexIndexException
      This method creates a complete graph sized of a number given as a second parameter int. Vertex indexing begins from a value of first int parameter.

      Default value for vertex indexing starts with 0 - if any index will exceed Integer.MAX_VALUE.

      Parameters:
      startIndex - numerical index of first vertex of graph.
      size - number of vertices to create in a graph.
      Returns:
      complete graph.
      Throws:
      NegativeVertexIndexException - if first parameter type int < 0.
      Since:
      1.0
      See Also:

    • generateCompleteIfEmpty

      private Graph<T> generateCompleteIfEmpty(int startIndex, int size) throws NegativeVertexIndexException

      This method should be used only on empty graphs.

      It generates a complete graph sized of a number given as a second parameter int. Vertex indexing begins from value of first int parameter.

      Default value for vertex indexing starts with 0 if any index would exceed Integer.MAX_VALUE.

      Parameters:
      startIndex - numerical index of first vertex of graph
      size - number of vertices to generate for a graph.
      Returns:
      complete graph if graph was empty, the same graph otherwise.
      Throws:
      NegativeVertexIndexException - if first parameter type int < 0.
      Since:
      1.0
      See Also:

    • mapToComplete

      public void mapToComplete()
      This method connects required vertices in order to make a graph complete.
      Since:
      1.0

    • canBeMappedToComplete

      private boolean canBeMappedToComplete()
      This method checks whether this graph can be mapped to complete.
      Returns:
      true if this graph can be mapped to complete, false otherwise.
      Since:
      1.1

    • getVertex

      @NotNull private Graph<T>.@NotNull Vertex<T> getVertex(int index) throws NegativeVertexIndexException, NoSuchVertexIndexException
      This method returns vertex with given int index.
      Parameters:
      index - numerical index of vertex.
      Returns:
      vertex by given index.
      Throws:
      NegativeVertexIndexException - if parameter type int < 0.
      NoSuchVertexIndexException - if this graph does not contain vertex with given int index.
      Since:
      1.0-beta
      See Also:

    • getVertices

      @NotNull public final @NotNull @UnmodifiableView Set<Integer> getVertices()
      This method returns an unmodifiable sorted set of vertices of this graph. Returned SortedSet of Integer corresponds to user-friendly representation of vertices of Graph.
      Returns:
      unmodifiable sorted set of vertices of this graph.
      Since:
      1.0-beta
      See Also:

    • getVertexData

      public final @UnmodifiableView T getVertexData(int index) throws NegativeVertexIndexException, NoSuchVertexIndexException
      This method returns unmodifiable data stored in a vertex by given index.
      Parameters:
      index - numerical index of vertex.
      Returns:
      data stored in vertex by given index.
      Throws:
      NegativeVertexIndexException - if parameter type int < 0.
      NoSuchVertexIndexException - if this graph does not contain vertex with given int index.
      Since:
      2.0

    • setVertexData

      public void setVertexData(int index, T data) throws NegativeVertexIndexException, NoSuchVertexIndexException
      This method set the data stored in a vertex by given index.
      Parameters:
      index - numerical index of vertex
      data - data to store in a vertex by given index.
      Throws:
      NegativeVertexIndexException - if parameter type int < 0.
      NoSuchVertexIndexException - if this graph does not contain vertex with given int index.
      Since:
      2.0

    • getVertexNeighbourhood

      @NotNull public final @NotNull @Unmodifiable Set<Integer> getVertexNeighbourhood(int index) throws NegativeVertexIndexException, NoSuchVertexIndexException
      This method returns an unmodifiable sorted set of neighbours of vertex given by int index.
      Parameters:
      index - numerical index of a vertex.
      Returns:
      unmodifiable sorted set of neighbours of a vertex given by int index.
      Throws:
      NegativeVertexIndexException - if parameter type int < 0.
      NoSuchVertexIndexException - if this graph does not contain vertex with given int index.
      Since:
      1.0

    • isVertexOfGraph

      public boolean isVertexOfGraph(int index) throws NegativeVertexIndexException
      This method checks whether this graph contains a vertex with given int index.
      Parameters:
      index - numerical index of vertex.
      Returns:
      true if this graph contains vertex with given index, false otherwise.
      Throws:
      NegativeVertexIndexException - if parameter type int < 0.
      Since:
      1.0-beta
      See Also:

    • isVertexOfSubGraph

      private boolean isVertexOfSubGraph(@NotNull @NotNull Collection<Graph<T>.Vertex<T>> vertices, int index) throws NegativeVertexIndexException
      This method checks whether given subset contains a vertex with given int index.
      Parameters:
      vertices - vertices subset of graph.
      index - numerical index of vertex.
      Returns:
      true if given subset contains vertex with given index, false otherwise.
      Throws:
      NegativeVertexIndexException - if parameter type int < 0.
      Since:
      1.1

    • isVertexOfSubGraph

      @Contract(pure=true) private boolean isVertexOfSubGraph(@NotNull @NotNull Collection<Graph<T>.Vertex<T>> vertices, Graph<T>.Vertex<T> vertex)
      This method checks whether a given subset contains a given vertex.
      Parameters:
      vertices - vertices subset of graph.
      vertex - a vertex to check if it is in the subset.
      Returns:
      true if given subset contains given vertex, false otherwise.
      Since:
      1.1

    • areVerticesOfGraph

      public boolean areVerticesOfGraph(@NotNull @NotNull Collection<Integer> subset) throws NegativeVertexIndexException
      This method checks whether given Collection is a subset of vertices of this graph.
      Parameters:
      subset - Collection containing indexes of vertices to check if they are in this graph.
      Returns:
      true if given Collection is a subset of vertices of this graph, false otherwise.
      Throws:
      NegativeVertexIndexException - if given Collection contains negative number(s).
      Since:
      1.0

    • addNewVertex

      public boolean addNewVertex(int index) throws NegativeVertexIndexException
      This method adds a new vertex to this graph. The vertex is added only if the graph does not contain it already.
      Parameters:
      index - numerical index of vertex.
      Returns:
      true if vertex with given int index was added, false otherwise.
      Throws:
      NegativeVertexIndexException - if parameter type int < 0.
      Since:
      1.0-beta
      See Also:

    • addNewVertex

      public boolean addNewVertex(int index, T data) throws NegativeVertexIndexException
      This method adds a new vertex with given data to store in it to this graph. The vertex is added only if the graph does not contain it already.
      Parameters:
      index - numerical index of vertex.
      data - data to store in added vertex.
      Returns:
      true if vertex with given int index was added, false otherwise.
      Throws:
      NegativeVertexIndexException - if parameter type int < 0.
      Since:
      2.0

    • addNewVertices

      public boolean addNewVertices(@NotNull @NotNull Collection<Integer> verticesToAdd) throws NegativeVertexIndexException
      This method adds new vertices to this graph. A vertex is added only if the graph does not already contain it.

      Adding a vertex is stopped once there is an occurrence of negative number in given Collection.

      Parameters:
      verticesToAdd - Collection containing indexes of vertices to add.
      Returns:
      true if each vertex from Collection has been added to this graph, false otherwise.
      Throws:
      NegativeVertexIndexException - if given Collection contains negative number(s).
      Since:
      1.0

    • connectVertices

      public boolean connectVertices(int indexV, int indexU) throws NegativeVertexIndexException, NoSuchVertexIndexException
      This method connects given two vertices by their indexes.
      Parameters:
      indexV - numerical index of the first vertex.
      indexU - numerical index of another vertex.
      Returns:
      true if vertices with given indexes have been connected, false otherwise.
      Throws:
      NegativeVertexIndexException - if any int < 0.
      NoSuchVertexIndexException - if this graph does not contain vertex with given either index.
      Since:
      1.0-beta

    • disconnectVertices

      public boolean disconnectVertices(int indexV, int indexU) throws NegativeVertexIndexException, NoSuchVertexIndexException
      This method disconnects given two vertices.
      Parameters:
      indexV - numerical index of the first vertex.
      indexU - numerical index of another vertex.
      Returns:
      true if vertices with given indexes have been disconnected, false otherwise.
      Throws:
      NegativeVertexIndexException - if any int < 0.
      NoSuchVertexIndexException - if this graph does not contain vertex with given either index.
      Since:
      1.0

    • removeVertex

      public boolean removeVertex(int index) throws NegativeVertexIndexException, NoSuchVertexIndexException
      This method removes a vertex from this graph. The Vertex is removed only if the graph contains it.
      Parameters:
      index - numerical index of a vertex.
      Returns:
      true if vertex with given index has been removed.
      Throws:
      NegativeVertexIndexException - if parameter type int < 0.
      NoSuchVertexIndexException - if this graph does not contain vertex with given int index.
      Since:
      1.0
      See Also:

    • removeVertices

      public boolean removeVertices(@NotNull @NotNull Collection<Integer> verticesToRemove) throws NegativeVertexIndexException, NoSuchVertexIndexException
      This method removes vertices from this graph.

      Removing a vertex is stopped once there is an occurrence of either: 

       negative number in given Collection,
 number that could not be identified with any vertex index.
      Parameters:
      verticesToRemove - Collection containing indexes of vertices to remove.
      Returns:
      true if each vertex from Collection has been removed.
      Throws:
      NegativeVertexIndexException - if given Collection contains negative number(s).
      NoSuchVertexIndexException - if given Collection contains number that could not be identified with any vertex index.
      Since:
      1.0

    • breadthFirstSearch

      private int breadthFirstSearch(@NotNull @NotNull Collection<Graph<T>.Vertex<T>> subset)
      This method is a modified implementation of a known traverse algorithm in graphs - breadth-first search. Only vertices from given Collection can be visited. It returns the number of visited vertices.
      Parameters:
      subset - subset of vertices of this graph.
      Returns:
      numbers of visited vertices.
      Since:
      1.0
      See Also:

    • isInSubsetNotVisited

      private boolean isInSubsetNotVisited(@NotNull @NotNull Collection<Graph<T>.Vertex<T>> subset, Graph<T>.Vertex<T> vertex, HashSet<Graph<T>.Vertex<T>> visited)
      This method checks if given vertex was not already visited and is in given subset.
      Parameters:
      subset - subset of vertices
      vertex - a vertex to check if it is given subset, and it was not yet visited.
      visited - set of visited vertices.
      Returns:
      true if vertex is in the subset and was not yet visited, false otherwise.
      Since:
      1.1

    • depthFirstSearch

      private int depthFirstSearch(@NotNull @NotNull Collection<Graph<T>.Vertex<T>> subset)
      This method is a modified implementation of a known traverse algorithm in graphs - depth-first search. Only vertices from given Collection can be visited. It returns the number of visited vertices.
      Parameters:
      subset - subset of vertices of this graph.
      Returns:
      numbers of visited vertices.
      Since:
      1.0-beta
      See Also:

    • isConnected

      public boolean isConnected()
      This method checks whether this graph is connected or disconnected.
      Returns:
      true if this graph is connected, false otherwise.
      Since:
      1.0-beta

    • doInduceConnectedSubGraph

      public boolean doInduceConnectedSubGraph(Collection<Integer> subset) throws NegativeVertexIndexException, NoSuchVertexIndexException
      This method checks whether given Collection induces connected subgraph of this graph, or does not.
      Parameters:
      subset - Collection containing indexes of vertices to check if they induce connected subgraph of this graph.
      Returns:
      true if given Collection induces connected subgraph of this graph, false otherwise.
      Throws:
      NegativeVertexIndexException - if given Collection contains negative number(s).
      NoSuchVertexIndexException - if given Collection contains number that could not be identified with any vertex index.
      Since:
      1.0-beta

    • isConnectedSubGraph

      private boolean isConnectedSubGraph(Collection<Graph<T>.Vertex<T>> subset)
      This method checks whether the all given vertices are in a connected subgraph of this graph or are not.
      Parameters:
      subset - subset of vertices of this graph.
      Returns:
      true if given Collection induces connected subgraph of this graph, false otherwise.
      Since:
      1.0-beta
      See Also:

    • isComplete

      public boolean isComplete()
      This method checks whether this graph is complete or is not.
      Returns:
      true if graph is complete, false otherwise.
      Since:
      1.0

    • isBipartite

      public boolean isBipartite()
      This method checks whether this graph is bipartite or is not.
      Returns:
      true if this graph is bipartite, false otherwise.
      Since:
      1.0

    • doInduceBipartiteSubGraph

      public boolean doInduceBipartiteSubGraph(@NotNull @NotNull Collection<Integer> subset) throws NegativeVertexIndexException, NoSuchVertexIndexException
      This method checks whether given Collection induces bipartite subgraph of this graph or does not.
      Parameters:
      subset - Collection containing indexes of vertices to check if they induce bipartite subgraph of this graph.
      Returns:
      true if given Collection is a subset of vertices of this graph that induces bipartite subgraph, false otherwise.
      Throws:
      NegativeVertexIndexException - if given Collection contains negative number(s).
      NoSuchVertexIndexException - if given Collection contains number that could not be identified with any vertex index.
      Since:
      1.0
      See Also:

    • isBipartiteSubGraph

      private boolean isBipartiteSubGraph(@NotNull @NotNull Collection<Graph<T>.Vertex<T>> subset)
      This method checks whether the all given vertices are in a bipartite subgraph of this graph or are not.
      Parameters:
      subset - subset of vertices of this graph.
      Returns:
      true if given Collection induces bipartite subgraph of this graph, false otherwise.
      Since:
      1.0

    • isCDS

      public boolean isCDS(Collection<Integer> subset) throws NegativeVertexIndexException, NoSuchVertexIndexException
      This method checks whether given Collection is a connected dominating set of this graph or is not.
      Parameters:
      subset - Collection containing indexes of vertices to check if they induce a connected dominating set of this graph.
      Returns:
      true if given Collection is a connected dominating set in this graph, false otherwise.
      Throws:
      NegativeVertexIndexException - if given Collection contains negative number(s).
      NoSuchVertexIndexException - if given Collection contains number that could not be identified with any vertex index.
      Since:
      1.0-beta

    • isIndependentSet

      public boolean isIndependentSet(Collection<Integer> subset) throws NegativeVertexIndexException, NoSuchVertexIndexException
      This method checks whether given Collection is an independent set of vertices of this graph or is not.
      Parameters:
      subset - Collection containing indexes of vertices to check if they induce an independent set in this graph.
      Returns:
      true if given Collection is an independent set of this graph, false otherwise.
      Throws:
      NegativeVertexIndexException - if given Collection contains negative number(s).
      NoSuchVertexIndexException - if given Collection contains number that could not be identified with any vertex index.
      Since:
      1.0

    • findMCDS

      @NotNull public final @NotNull @Unmodifiable Set<Integer> findMCDS()
      This method finds a minimal connected dominating set in this graph. The result is an unmodifiable-sorted subset of vertices of this graph.

      To learn more details, read here computeMCDS().

      Returns:
      minimal connected dominating set of this graph.
      Since:
      1.0-beta

    • computeMCDS

      @NotNull private @NotNull Collection<Graph<T>.Vertex<T>> computeMCDS()
      This method computes a minimal connected dominating set in this graph.

      It is an implementation of an approximation algorithm for finding minimum connected dominating set in Graph. Since domination problem is a NP-C problem, this method can find not necessary an optimal solution. Hence, we will say it computes minimal connected dominating set, which is indeed always a true.

      Returns:
      minimal connected dominating set in this graph as a Collection of Graph.Vertex.
      Since:
      1.0-beta
      See Also:

    • findMDS

      @NotNull public final @NotNull @Unmodifiable Set<Integer> findMDS()
      This method finds a minimal dominating set in this graph. The result is an unmodifiable-sorted subset of vertices of this graph.

      To learn more details, read here: computeMDS().

      Returns:
      minimal dominating set of this graph.
      Since:
      1.0

    • computeMDS

      @NotNull private @NotNull Collection<Graph<T>.Vertex<T>> computeMDS()
      This method computes a minimal dominating set in this graph.

      It is an implementation of an approximation algorithm for finding minimum dominating set in Graph. Since domination problem is a NP-C problem, this method can find not necessary an optimal solution. Hence, we will say it computes minimal dominating set, which is indeed always a true.

      Returns:
      minimal dominating set in this graph as a Collection of Graph.Vertex.
      Since:
      1.0
      See Also:

    • findMIS

      @NotNull public final @NotNull @Unmodifiable Set<Integer> findMIS()
      This method finds a maximal independent set of this graph. The result is an unmodifiable-sorted subset of vertices of this graph.

      To learn more details, read here: computeMIS()

      Returns:
      maximal independent set of this graph.
      Since:
      1.0

    • computeMIS

      @NotNull private @NotNull Collection<Graph<T>.Vertex<T>> computeMIS()
      This method computes a maximal independent set in this graph.

      It is an implementation of an approximation algorithm for finding maximum independent set in Graph. Since maximum independent set problem is a NP-hard problem that is hard to approximate, this method can find not necessary an optimal solution. Hence, we will say it computes maximal independent set, which is indeed always a true.

      Returns:
      maximal independent set in this graph as a Collection of Graph.Vertex.
      Since:
      1.0
      See Also:

    • mapIndexesToVertices

      @NotNull private @NotNull Collection<Graph<T>.Vertex<T>> mapIndexesToVertices(@NotNull @NotNull Collection<Integer> indexes) throws NegativeVertexIndexException, NoSuchVertexIndexException
      This method maps a Collection of vertices indexes to a Collection of Graph.Vertex.
      Parameters:
      indexes - subset of vertices indexes of this graph.
      Returns:
      Collection of Graph.Vertex.
      Throws:
      NegativeVertexIndexException - if given Collection contains negative number(s).
      NoSuchVertexIndexException - if given Collection contains number that could not be identified with any vertex index.
      Since:
      1.0-beta

    • mapVerticesToIndexes

      @NotNull private @NotNull @UnmodifiableView Set<Integer> mapVerticesToIndexes(@NotNull @NotNull Collection<Graph<T>.Vertex<T>> vertices)
      This method maps a Collection of Graph.Vertex to unmodifiable SortedSet of their indexes.
      Parameters:
      vertices - Collection of Graph.Vertex to map from.
      Returns:
      unmodifiable SortedSet of vertices indexes mapped from a given Collection of Graph.Vertex.
      Since:
      1.0
      See Also:

    • toString

      public String toString()
      This method returns user-friendly representation of Graph as each vertex index with its neighbourhood list.

      It displays in following pattern: 

       <optional>int -> [<optional>int, ..., <optional>int], content: T
 .
 .
 .
 <optional>int -> [<optional>int, ..., <optional>int], content: T
      Overrides:
      toString in class Object
      Returns:
      user-friendly representation of this graph.
      Since:
      1.0-beta