Package org.simplegraph.impl

Class DirectedDenseGraph<V>

java.lang.Object
org.simplegraph.impl.DirectedDenseGraph<V>
All Implemented Interfaces:
DirectedGraph<V>, Graph<V>
public class DirectedDenseGraph<V> extends Object implements DirectedGraph<V>
Dense graph implementation for directed graphs.

  • Field Details

    • edges

      protected Boolean[][] 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

    • DirectedDenseGraph

      public DirectedDenseGraph()
      Default constructor

    • DirectedDenseGraph

      public DirectedDenseGraph(int size)
      Create a graph of a specified size
      Parameters:
      size - starting size

    • DirectedDenseGraph

      public DirectedDenseGraph(DirectedDenseGraph<V> graph)
      Copy constructor
      Parameters:
      graph - graph to copy

  • 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

    • addEdge

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

    • 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

    • getSpanningTree

      public DirectedGraph<V> getSpanningTree()
      Specified by:
      getSpanningTree in interface Graph<V>

    • copy

      protected void copy(org.simplegraph.impl.BaseDirectedDenseGraph<V,Boolean> 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, Boolean 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 Boolean 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, Boolean 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,Boolean> _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.