Package com.powsybl.math.graph

Class UndirectedGraphImpl<V,E>

java.lang.Object
com.powsybl.math.graph.UndirectedGraphImpl<V,E>
All Implemented Interfaces:
UndirectedGraph<V,E>
public class UndirectedGraphImpl<V,E> extends Object implements UndirectedGraph<V,E>
Author:
Geoffroy Jamgotchian <geoffroy.jamgotchian at rte-france.com>

  • Constructor Details

    • UndirectedGraphImpl

      public UndirectedGraphImpl(int vertexLimit)

  • Method Details

    • addVertex

      public int addVertex()
      Description copied from interface: UndirectedGraph
      Create a new vertex and notify the UndirectedGraphListeners.
      Specified by:
      addVertex in interface UndirectedGraph<V,E>
      Returns:
      the index of the new vertex.

    • addVertexIfNotPresent

      public void addVertexIfNotPresent(int v)
      Description copied from interface: UndirectedGraph
      If the specified vertex does not exist or is null, create it and notify the UndirectedGraphListener
      Specified by:
      addVertexIfNotPresent in interface UndirectedGraph<V,E>

    • vertexExists

      public boolean vertexExists(int v)
      Description copied from interface: UndirectedGraph
      Check if a specified vertex exists. This method throws a PowsyblException if the vertex index is invalid (negative).
      Specified by:
      vertexExists in interface UndirectedGraph<V,E>

    • removeVertex

      public V removeVertex(int v)
      Description copied from interface: UndirectedGraph
      Remove the specified vertex and notify the UndirectedGraphListeners. This method throws a PowsyblException if the vertex doesn't exist or if an edge is connected to this vertex.
      Specified by:
      removeVertex in interface UndirectedGraph<V,E>
      Parameters:
      v - the vertex index to remove.
      Returns:
      the value attached to the vertex.

    • getVertexCount

      public int getVertexCount()
      Description copied from interface: UndirectedGraph
      Return the number of non-null vertices. As the contiguity of vertices is not mandatory, the number of vertices can be less than the highest vertex index.
      Specified by:
      getVertexCount in interface UndirectedGraph<V,E>
      Returns:
      the number of vertices.

    • removeAllVertices

      public void removeAllVertices()
      Description copied from interface: UndirectedGraph
      Remove all the vertices of this graph. This method throws a PowsyblException if edges exist.
      Specified by:
      removeAllVertices in interface UndirectedGraph<V,E>

    • addEdge

      public int addEdge(int v1, int v2, E obj)
      Description copied from interface: UndirectedGraph
      Create an edge between the two specified vertices and notify the UndirectedGraphListeners. This method throws a PowsyblException if one of the vertices doesn't exist.
      Specified by:
      addEdge in interface UndirectedGraph<V,E>
      Parameters:
      v1 - the first end of the edge.
      v2 - the second end of the edge.
      obj - the value attached to the edge.
      Returns:
      the index of the new edge.

    • removeEdge

      public E removeEdge(int e)
      Description copied from interface: UndirectedGraph
      Remove the specified edge and notify the UndirectedGraphListeners. This method thows a PowsyblException if the edge doesn't exist.
      Specified by:
      removeEdge in interface UndirectedGraph<V,E>
      Parameters:
      e - the edge index to remove.
      Returns:
      the value attached to the edge.

    • removeAllEdges

      public void removeAllEdges()
      Description copied from interface: UndirectedGraph
      Remove all the edges and notify the UndirectedGraphListeners.
      Specified by:
      removeAllEdges in interface UndirectedGraph<V,E>

    • getEdgeCount

      public int getEdgeCount()
      Description copied from interface: UndirectedGraph
      Return the number of edges.
      Specified by:
      getEdgeCount in interface UndirectedGraph<V,E>
      Returns:
      the number of edges.

    • getVertices

      public int[] getVertices()
      Description copied from interface: UndirectedGraph
      Return the indices of the vertices.
      Specified by:
      getVertices in interface UndirectedGraph<V,E>
      Returns:
      the indices of the vertices.

    • getEdges

      public int[] getEdges()
      Description copied from interface: UndirectedGraph
      Return the indices of the edges.
      Specified by:
      getEdges in interface UndirectedGraph<V,E>
      Returns:
      the indices of the edges.

    • getVertexCapacity

      public int getVertexCapacity()
      Description copied from interface: UndirectedGraph
      Return the maximum number of vertices that this graph can contain. The vertex indices are in the range [0, getVertexCapacity[ As the contiguity of the vertices is not mandatory, do not use this method to iterate over the vertices. Use UndirectedGraph.getVertices() instead. To get the number of vertices in this graph, use UndirectedGraph.getVertexCount().
      Specified by:
      getVertexCapacity in interface UndirectedGraph<V,E>
      Returns:
      the maximum number of vertices contained in this graph.

    • getVerticesObj

      public Iterable<V> getVerticesObj()
      Description copied from interface: UndirectedGraph
      Return an Iterable to iterate over the values attached to the vertices.
      Specified by:
      getVerticesObj in interface UndirectedGraph<V,E>
      Returns:
      an Iterable to iterate over the values attached to the vertices.

    • getVertexObjectStream

      public Stream<V> getVertexObjectStream()
      Description copied from interface: UndirectedGraph
      Return a Stream to iterate over the values attached to the vertices.
      Specified by:
      getVertexObjectStream in interface UndirectedGraph<V,E>
      Returns:
      a Stream to iterate over the values attached to the vertices.

    • getVertexObject

      public V getVertexObject(int v)
      Description copied from interface: UndirectedGraph
      Return the value attached to the specified vertex. This method throws a PowsyblException if the vertex doesn't exist.
      Specified by:
      getVertexObject in interface UndirectedGraph<V,E>
      Parameters:
      v - the vertex index
      Returns:
      the value attached to the specified vertex.

    • setVertexObject

      public void setVertexObject(int v, V obj)
      Description copied from interface: UndirectedGraph
      Set the value attached to the specified vertex. This method throws a PowsyblException if the vertex doesn't exist.
      Specified by:
      setVertexObject in interface UndirectedGraph<V,E>
      Parameters:
      v - the vertex index.
      obj - the value to attach to the vertex.

    • getEdgeVertex1

      public int getEdgeVertex1(int e)
      Description copied from interface: UndirectedGraph
      Return the index of the first vertex that the specified edge is connected to. This method throws a PowsyblException if the edge doesn't exist.
      Specified by:
      getEdgeVertex1 in interface UndirectedGraph<V,E>
      Parameters:
      e - the edge index.
      Returns:
      the index of the first vertex that the specified edge is connected to.

    • getEdgeObjectsConnectedToVertex

      public List<E> getEdgeObjectsConnectedToVertex(int v)
      Description copied from interface: UndirectedGraph
      Return the edge objects connected to the specified vertex. This method throws a PowsyblException if the vertex doesn't exist.
      Specified by:
      getEdgeObjectsConnectedToVertex in interface UndirectedGraph<V,E>
      Parameters:
      v - the vertex index.
      Returns:
      an iterable of the edge objects

    • getEdgeObjectConnectedToVertexStream

      public Stream<E> getEdgeObjectConnectedToVertexStream(int v)
      Description copied from interface: UndirectedGraph
      Return the edge objects connected to the specified vertex. This method throws a PowsyblException if the vertex doesn't exist.
      Specified by:
      getEdgeObjectConnectedToVertexStream in interface UndirectedGraph<V,E>
      Parameters:
      v - the vertex index.
      Returns:
      a stream of the edge objects

    • getEdgesConnectedToVertex

      public List<Integer> getEdgesConnectedToVertex(int v)
      Description copied from interface: UndirectedGraph
      Return the indices of the edges connected to the specified vertex. This method throws a PowsyblException if the vertex doesn't exist.
      Specified by:
      getEdgesConnectedToVertex in interface UndirectedGraph<V,E>
      Parameters:
      v - the vertex index.
      Returns:
      an iterable of the edge indices

    • getEdgeConnectedToVertexStream

      public IntStream getEdgeConnectedToVertexStream(int v)
      Description copied from interface: UndirectedGraph
      Return the indices of the edges connected to the specified vertex. This method throws a PowsyblException if the vertex doesn't exist.
      Specified by:
      getEdgeConnectedToVertexStream in interface UndirectedGraph<V,E>
      Parameters:
      v - the vertex index.
      Returns:
      a stream of the edge indices

    • getEdgeVertex2

      public int getEdgeVertex2(int e)
      Description copied from interface: UndirectedGraph
      Return the index of the second vertex that the specified edge is connected to. This method throws a PowsyblException if the edge doesn't exist.
      Specified by:
      getEdgeVertex2 in interface UndirectedGraph<V,E>
      Parameters:
      e - the edge index.
      Returns:
      the index of the second vertex that the specified edge is connected to.

    • getEdgesObject

      public Iterable<E> getEdgesObject()
      Description copied from interface: UndirectedGraph
      Return an Iterable to iterate over the values attached to the edges.
      Specified by:
      getEdgesObject in interface UndirectedGraph<V,E>
      Returns:
      an Iterable to iterate over the values attached to the edges.

    • getEdgeObjectStream

      public Stream<E> getEdgeObjectStream()
      Description copied from interface: UndirectedGraph
      Return a Stream to iterate over the values attached to the edges.
      Specified by:
      getEdgeObjectStream in interface UndirectedGraph<V,E>
      Returns:
      a Stream to iterate over the values attached to the edges.

    • getEdgeObject

      public E getEdgeObject(int e)
      Description copied from interface: UndirectedGraph
      Return the value attached to the specified edge.
      Specified by:
      getEdgeObject in interface UndirectedGraph<V,E>
      Parameters:
      e - the index of an edge.
      Returns:
      the value attached to the specified edge.

    • getEdgeObjects

      public List<E> getEdgeObjects(int v1, int v2)
      Description copied from interface: UndirectedGraph
      Return a List containing the values attached to the edges between the vertices v1 and v2.
      Specified by:
      getEdgeObjects in interface UndirectedGraph<V,E>
      Returns:
      a List containing the values attached to the edges between the vertices v1 and v2.

    • traverse

      public boolean traverse(int v, TraversalType traversalType, Traverser traverser, boolean[] encountered)
      Description copied from interface: UndirectedGraph
      Traverse the entire graph, starting at the specified vertex v. This method relies on a Traverser instance to know if the traverse of the graph should continue or stop. This method throws a PowsyblException if the encountered table size is less than the maximum vertex index. At the end of the method, the encountered array contains true for all the traversed vertices, false otherwise.
      Specified by:
      traverse in interface UndirectedGraph<V,E>
      Parameters:
      v - the vertex index where the traverse has to start.
      traversalType - the type of traversal (breadth-first or depth-first)
      traverser - the Traverser instance to use to know if the traverse should continue or stop.
      encountered - the list of traversed vertices.
      Returns:
      false if the whole traversing has to stop, meaning that a TraverseResult.TERMINATE_TRAVERSER has been returned from the traverser, true otherwise

    • traverse

      public boolean traverse(int v, TraversalType traversalType, Traverser traverser)
      Description copied from interface: UndirectedGraph
      Traverse the entire graph, starting at the specified vertex v. This method allocates a boolean array and calls UndirectedGraph.traverse(int, TraversalType, Traverser, boolean[]).
      Specified by:
      traverse in interface UndirectedGraph<V,E>
      Parameters:
      v - the vertex index where the traverse has to start.
      traversalType - the type of traversal (breadth-first or depth-first)
      traverser - the Traverser instance to use to know if the traverse should continue or stop.
      Returns:
      false if the whole traversing has to stop, meaning that a TraverseResult.TERMINATE_TRAVERSER has been returned from the traverser, true otherwise

    • traverse

      public boolean traverse(int[] startingVertices, TraversalType traversalType, Traverser traverser)
      Description copied from interface: UndirectedGraph
      Traverse the entire graph, starting at each vertex index of the specified vertices array v. This method allocates a boolean array and calls UndirectedGraph.traverse(int, TraversalType, Traverser, boolean[]) for each entry of the array.
      Specified by:
      traverse in interface UndirectedGraph<V,E>
      Parameters:
      startingVertices - the array of vertex indices where the traverse has to start.
      traversalType - the type of traversal (breadth-first or depth-first)
      traverser - the Traverser instance to use to know if the traverse should continue or stop.
      Returns:
      false if the whole traversing has to stop, meaning that a TraverseResult.TERMINATE_TRAVERSER has been returned from the traverser, true otherwise

    • findAllPaths

      public List<gnu.trove.list.array.TIntArrayList> findAllPaths(int from, Predicate<V> pathComplete, Predicate<? super E> pathCancelled)
      Find all paths from the specified vertex. This method relies on two functions to stop the traverse when the target vertex is found or when an edge must not be traversed.

      This method allocates a List of TIntArrayList to store the paths, a BitSet to store the encountered vertices and calls findAllPaths(int, Predicate, Predicate, TIntArrayList, BitSet, List).

      In the output, the paths are sorted by size considering the number of switches in each path.
      Specified by:
      findAllPaths in interface UndirectedGraph<V,E>
      Parameters:
      from - the vertex index where the traverse has to start.
      pathComplete - a function that returns true when the target vertex is found.
      pathCancelled - a function that returns true when the edge must not be traversed.
      Returns:
      a list that contains the index of the traversed edges.

    • findAllPaths

      public List<gnu.trove.list.array.TIntArrayList> findAllPaths(int from, Predicate<V> pathComplete, Predicate<? super E> pathCancelled, Comparator<gnu.trove.list.array.TIntArrayList> comparator)
      Find all paths from the specified vertex. This method relies on two functions to stop the traverse when the target vertex is found or when an edge must not be traversed.

      This method allocates a List of TIntArrayList to store the paths, a BitSet to store the encountered vertices and calls findAllPaths(int, Predicate, Predicate, TIntArrayList, BitSet, List). In the output, the paths are sorted by using the given comparator.

      Specified by:
      findAllPaths in interface UndirectedGraph<V,E>
      Parameters:
      from - the vertex index where the traverse has to start.
      pathComplete - a function that returns true when the target vertex is found.
      pathCancelled - a function that returns true when the edge must not be traversed.
      comparator - a comparator used to sort the paths
      Returns:
      a list that contains the index of the traversed edges.

    • addListener

      public void addListener(UndirectedGraphListener<V,E> l)
      Description copied from interface: UndirectedGraph
      Add a UndirectedGraphListener to get notified when the graph changes.
      Specified by:
      addListener in interface UndirectedGraph<V,E>
      Parameters:
      l - the listener to add.

    • removeListener

      public void removeListener(UndirectedGraphListener<V,E> l)
      Description copied from interface: UndirectedGraph
      Remove a UndirectedGraphListener to stop listening the graph changes.
      Specified by:
      removeListener in interface UndirectedGraph<V,E>
      Parameters:
      l - the listener to remove.

    • print

      public void print(PrintStream out, Function<V,String> vertexToString, Function<E,String> edgeToString)
      Description copied from interface: UndirectedGraph
      Prints the entire graph to the specified PrintStream. The printing relies on the two specified functions to render the values attached to a vertex or an edge.
      Specified by:
      print in interface UndirectedGraph<V,E>
      Parameters:
      out - the output stream.
      vertexToString - the function to use to render the values of vertices.
      edgeToString - the function to use to render the values of edges.

    • removeIsolatedVertices

      public void removeIsolatedVertices(int v, gnu.trove.list.array.TIntArrayList[] adjacencyList)

    • removeIsolatedVertices

      public void removeIsolatedVertices()
      Description copied from interface: UndirectedGraph
      Remove from the vertices which are not connected to any edge, and which have no associated object.
      Specified by:
      removeIsolatedVertices in interface UndirectedGraph<V,E>