Package org.simplegraph.impl

Class DirectedWeightedDenseGraph<V>

java.lang.Object
org.simplegraph.impl.DirectedWeightedDenseGraph<V>
All Implemented Interfaces:
DirectedWeightedGraph<V>, WeightedGraph<V>
public class DirectedWeightedDenseGraph<V> extends Object implements DirectedWeightedGraph<V>
Dense graph implementation for directed and weighted graphs.

  • Field Details

    • edges

      protected Double[][] edges

    • DEFAULT_SIZE

      protected static final short DEFAULT_SIZE
      See Also:

    • size

      protected int size

    • verticesCount

      protected int verticesCount

    • verticesArray

      protected ArrayList<V> verticesArray

    • verticesMap

      protected Map<V,Integer> verticesMap

  • Constructor Details

    • DirectedWeightedDenseGraph

      public DirectedWeightedDenseGraph()

    • DirectedWeightedDenseGraph

      public DirectedWeightedDenseGraph(int size)

    • DirectedWeightedDenseGraph

      public DirectedWeightedDenseGraph(DirectedWeightedDenseGraph<V> graph)

  • Method Details

    • addVertex

      public boolean addVertex(V vertex)
      Add a vertex to the graph.
      Parameters:
      vertex - the vertex to add
      Returns:
      true if the the graph has been modified

    • containsVertex

      public boolean containsVertex(V vertex)
      Check the existence of a vertex in the graph.
      Parameters:
      vertex - the vertex to check
      Returns:
      true if the graph contains vertex

    • countVertices

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

    • existsPath

      public boolean existsPath(V source, V destination)
      Does a path exists between source and destination.
      Parameters:
      source - source vertex
      destination - destination vertex
      Returns:
      true if a path exists

    • existsEdge

      public boolean existsEdge(V v1, V v2)
      Check the existence of an edge that goes from the first vertex to the second.
      Parameters:
      v1 - first vertex
      v2 - second vertex
      Returns:
      true if an edge from v1 to v2 exists

    • countNeighbors

      public int countNeighbors(V vertex)
      Get the number of neighbors for a vertex, both incident and outer
      Parameters:
      vertex - the specified vertex
      Returns:
      number of neighbors, -1 if vertex is not contained in graph

    • getNeighbors

      public List<V> getNeighbors(V vertex)
      Get the neighbors of a vertex, both incident and outer vertices.
      Parameters:
      vertex - the specified vertex
      Returns:
      the list of vertices that are neighbors of vertex null if the vertex is not contained in the graph

    • getPath

      public List<V> getPath(V source, V destination)
      Get a path between a source and a destination
      Parameters:
      source - The vertex from where the path shall begin
      destination - The vertex from where the path shall end
      Returns:
      Ordered list of the vertices that form a path between source and destination, null if source and destination are the same or if they are not contained in the graph, an empty LinkedList if there is no path between them

    • removeEdge

      public boolean removeEdge(V v1, V v2)
      Remove an edge that goes from the first vertex to the second.
      Parameters:
      v1 - first vertex
      v2 - second vertex
      Returns:
      true if an edge from v1 to v2 exists

    • removeVertex

      public boolean removeVertex(V vertex)
      Remove a vertex from the graph
      Parameters:
      vertex - the vertex to remove
      Returns:
      true if the graph has been modified

    • getVertices

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

    • addEdge

      public boolean addEdge(V v1, V v2, Double weight)
      Description copied from interface: WeightedGraph
      Add an edge between two vertices. Add the two vertices in the graph if they don't exists
      Specified by:
      addEdge in interface WeightedGraph<V>
      Parameters:
      v1 - first vertex
      v2 - second vertex
      Returns:
      true if the graph has been modified

    • getWeight

      public Double getWeight(V v1, V v2)
      Description copied from interface: WeightedGraph
      Get the edge between two vertices
      Specified by:
      getWeight in interface WeightedGraph<V>
      Parameters:
      v1 - first vertex
      v2 - second vertex
      Returns:
      the edge between v1 and v2, if it exists, null otherwise

    • getSpanningTree

      public DirectedWeightedGraph<V> getSpanningTree()
      Specified by:
      getSpanningTree in interface WeightedGraph<V>

    • getMinimumDistance

      public Double getMinimumDistance(V source, V destination)
      Specified by:
      getMinimumDistance in interface WeightedGraph<V>

    • getShortestPath

      public List<V> getShortestPath(V source, V destination)
      Specified by:
      getShortestPath in interface WeightedGraph<V>

    • getMinimumSpanningTree

      public DirectedWeightedGraph<V> getMinimumSpanningTree()
      Specified by:
      getMinimumSpanningTree in interface DirectedWeightedGraph<V>
      Specified by:
      getMinimumSpanningTree in interface WeightedGraph<V>

    • copy

      protected void copy(org.simplegraph.impl.BaseDirectedDenseGraph<V,Double> graph)
      Copy constructor
      Parameters:
      graph - graph to copy

    • initialize

      protected void initialize(int startSize)
      Initialize all attributes for storing graph data.
      Parameters:
      startSize - Number of vertices to store initially in the graph.

    • grow

      public void grow(int newSize)
      Grow the graph size to the specified size
      Parameters:
      newSize - New size for the graph.

    • addSingleEdge

      protected boolean addSingleEdge(V v1, V v2, Double edge)
      Add an edge that goes from the first vertex to the second. Add the two vertices in the graph if they don't exists.
      Parameters:
      v1 - first vertex
      v2 - second vertex
      edge - edge to add
      Returns:
      true if the graph has been modified

    • getSingleEdge

      protected Double getSingleEdge(V v1, V v2)

    • countEdges

      public int countEdges()
      Get how many edges the graph contains.
      Returns:
      number of edges

    • checkEdge

      protected boolean checkEdge(V vertex, Double edge, boolean in)

    • getInVertices

      public List<V> getInVertices(V vertex)
      Get the incident vertices of a vertex.
      Parameters:
      vertex - the specified vertex
      Returns:
      a LinkedList containing the incident vertices of vertex, null if vertex is not contained in the graph

    • getOutVertices

      public List<V> getOutVertices(V vertex)
      Get the outer vertices of a vertex.
      Parameters:
      vertex - the specified vertex
      Returns:
      a list containing the outer vertices of vertex, null if vertex is not contained in the graph

    • getInDegree

      public int getInDegree(V vertex)
      Get the number of incident vertices of a vertex.
      Parameters:
      vertex - the specified vertex
      Returns:
      the number of incident vertices of vertex, -1 if vertex is not contained in the graph

    • getOutDegree

      public int getOutDegree(V vertex)
      Get the number of outer vertices of a vertex.
      Parameters:
      vertex - the specified vertex
      Returns:
      the number of outer vertices of vertex, -1 if vertex is not contained in the graph

    • _getSpanningTree

      protected org.simplegraph.impl.BaseDirectedDenseGraph<V,Double> _getSpanningTree()
      Get a spanning tree if it exists.
      Returns:
      Graph containing a spanning tree if it exists, null otherwise.

    • copyVertices

      protected void copyVertices(org.simplegraph.impl.BaseDenseGraph<V> graph)

    • getVertexIndex

      protected int getVertexIndex(V vertex)
      Get index of the vertex.
      Parameters:
      vertex - Selected vertex.
      Returns:
      Index of the selected vertex.