Package org.simplegraph.impl

Class WeightedDenseGraph<V>

java.lang.Object
org.simplegraph.impl.WeightedDenseGraph<V>
All Implemented Interfaces:
WeightedGraph<V>
public class WeightedDenseGraph<V> extends Object implements WeightedGraph<V>
Dense graph implemention for weighted graphs.

  • Field Details

    • edges

      protected ArrayList<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

    • WeightedDenseGraph

      public WeightedDenseGraph()

    • WeightedDenseGraph

      public WeightedDenseGraph(int size)

    • WeightedDenseGraph

      public WeightedDenseGraph(WeightedDenseGraph<V> graph)

  • Method Details

    • 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

    • 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 between the two vertices
      Parameters:
      v1 - first vertex
      v2 - second vertex
      Returns:
      true if an edge between v1 and v2

    • countNeighbors

      public int countNeighbors(V vertex)
      Get the number of neighbors for a vertex.
      Parameters:
      vertex - the spefied vertex
      Returns:
      number of neighbors, -1 if vertex does not exists

    • 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 - source vertex
      destination - destination vertex
      Returns:
      a list containing the vertices that compose the path, in order; an empty list if there is no path, null if the source and the destination are equals or are not contained in the graph

    • 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 the graph has been changed

    • 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

    • getSpanningTree

      public WeightedGraph<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 WeightedGraph<V> getMinimumSpanningTree()
      Specified by:
      getMinimumSpanningTree in interface WeightedGraph<V>

    • copy

      protected void copy(org.simplegraph.impl.BaseUndirectedDenseGraph<V,Double> graph)

    • 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.

    • getEdgesSize

      protected int getEdgesSize(int verticesSize)
      Get how much edges there are for the size passed.
      Parameters:
      verticesSize - Number of vertices.
      Returns:
      Number of edges based on the number of vertices.

    • addSingleEdge

      protected boolean addSingleEdge(V v1, V v2, Double edge)

    • getSingleEdge

      protected Double getSingleEdge(V v1, V v2)

    • getEdgeIndex

      protected int getEdgeIndex(V v1, V v2)
      Get index of the edge between v1 and v2.
      Parameters:
      v1 - first vertex
      v2 - second vertex
      Returns:
      index of the edge between v1 and v2

    • countEdges

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

    • _getSpanningTree

      protected org.simplegraph.impl.BaseUndirectedDenseGraph<V,Double> _getSpanningTree()

    • getShortestPath

      public Graph<V> getShortestPath()

    • 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.