Class RankingPathElementList<V,​E>

    • Field Detail

      • guardVertexToNotDisconnect

        private V guardVertexToNotDisconnect
        Vertex that paths of the list must not disconnect.
      • path2disconnect

        private java.util.Map<RankingPathElement<V,​E>,​java.lang.Boolean> path2disconnect
      • externalPathValidator

        private PathValidator<V,​E> externalPathValidator
        To be used on top of general path validations. May invalidate the path though they pass the basic validations done internally (path is from source to target and w/o loops).
    • Constructor Detail

      • RankingPathElementList

        RankingPathElementList​(Graph<V,​E> graph,
                               int maxSize,
                               RankingPathElement<V,​E> pathElement)
        Creates a list with an empty path. The list size is 1.
        Parameters:
        maxSize - max number of paths the list is able to store.
      • RankingPathElementList

        RankingPathElementList​(Graph<V,​E> graph,
                               int maxSize,
                               RankingPathElement<V,​E> pathElement,
                               PathValidator<V,​E> pathValidator)
        Creates a list with an empty path. The list size is 1.
        Parameters:
        maxSize - max number of paths the list is able to store.
        pathValidator - path validator to be used in addition to basic validations (path is from source to target w/o loops)
      • RankingPathElementList

        RankingPathElementList​(Graph<V,​E> graph,
                               int maxSize,
                               RankingPathElementList<V,​E> elementList,
                               E edge)
        Creates paths obtained by concatenating the specified edge to the specified paths.
        Parameters:
        prevPathElementList - paths, list of RankingPathElement.
        edge - edge reaching the end vertex of the created paths.
        maxSize - maximum number of paths the list is able to store.
      • RankingPathElementList

        RankingPathElementList​(Graph<V,​E> graph,
                               int maxSize,
                               RankingPathElementList<V,​E> elementList,
                               E edge,
                               V guardVertexToNotDisconnect)
        Creates paths obtained by concatenating the specified edge to the specified paths.
        Parameters:
        prevPathElementList - paths, list of RankingPathElement.
        edge - edge reaching the end vertex of the created paths.
        maxSize - maximum number of paths the list is able to store.
      • RankingPathElementList

        RankingPathElementList​(Graph<V,​E> graph,
                               int maxSize,
                               RankingPathElementList<V,​E> elementList,
                               E edge,
                               V guardVertexToNotDisconnect,
                               PathValidator<V,​E> pathValidator)
        Creates paths obtained by concatenating the specified edge to the specified paths.
        Parameters:
        prevPathElementList - paths, list of RankingPathElement.
        edge - edge reaching the end vertex of the created paths.
        maxSize - maximum number of paths the list is able to store.
        pathValidator - path validator to be used in addition to basic validations (path is from source to target w/o loops)
      • RankingPathElementList

        RankingPathElementList​(Graph<V,​E> graph,
                               int maxSize,
                               V vertex)
        Creates an empty list. The list size is 0.
        Parameters:
        maxSize - max number of paths the list is able to store.
      • RankingPathElementList

        RankingPathElementList​(Graph<V,​E> graph,
                               int maxSize,
                               V vertex,
                               PathValidator<V,​E> pathValidator)
        Creates an empty list. The list size is 0.
        Parameters:
        maxSize - max number of paths the list is able to store.
        pathValidator - path validator to be used in addition to basic validations (path is from source to target w/o loops)
    • Method Detail

      • addPathElements

        public boolean addPathElements​(RankingPathElementList<V,​E> elementList,
                                       E edge)

        Adds paths in the list at vertex y. Candidate paths are obtained by concatenating the specified edge (v->y) to the paths elementList at vertex v.

        Complexity =
        • w/o guard-vertex: O(k*np) where k is the max size limit of the list and np is the maximum number of vertices in the paths stored in the list
        • with guard-vertex: O(k*(m+n)) where k is the max size limit of the list, m is the number of edges of the graph and n is the number of vertices of the graph, O(m+n) being the complexity of the ConnectivityInspector to check whether a path exists towards the guard-vertex
        Parameters:
        elementList - list of paths at vertex v.
        edge - edge (v->y).
        Returns:
        true if at least one path has been added in the list, false otherwise.
      • getPathElements

        java.util.List<RankingPathElement<V,​E>> getPathElements()
        Returns:
        list of RankingPathElement.
      • calculatePathWeight

        private double calculatePathWeight​(RankingPathElement<V,​E> pathElement,
                                           E edge)
        Costs taken into account are the weights stored in Edge objects.
        Parameters:
        pathElement -
        edge - the edge via which the vertex was encountered.
        Returns:
        the cost obtained by concatenation.
        See Also:
        Graph#getEdgeWeight(E)
      • isGuardVertexDisconnected

        private boolean isGuardVertexDisconnected​(RankingPathElement<V,​E> prevPathElement)
        Ensures that paths of the list do not disconnect the guard-vertex.
        Returns:
        true if the specified path element disconnects the guard-vertex, false otherwise.
      • isNotValidPath

        private boolean isNotValidPath​(RankingPathElement<V,​E> prevPathElement,
                                       E edge)
      • isSimplePath

        private boolean isSimplePath​(RankingPathElement<V,​E> prevPathElement,
                                     E edge)
        Ensures that paths of the list are simple (check that the vertex was not already in the path element).
        Parameters:
        prevPathElement -
        edge -
        Returns:
        true if the resulting path (obtained by concatenating the specified edge to the specified path) is simple, false otherwise.