Package org.jgrapht.alg.shortestpath
Class RankingPathElementList<V,E>
- java.lang.Object
-
- java.util.AbstractCollection<E>
-
- java.util.AbstractList<T>
-
- org.jgrapht.alg.shortestpath.AbstractPathElementList<V,E,RankingPathElement<V,E>>
-
- org.jgrapht.alg.shortestpath.RankingPathElementList<V,E>
-
- All Implemented Interfaces:
java.lang.Iterable<RankingPathElement<V,E>>
,java.util.Collection<RankingPathElement<V,E>>
,java.util.List<RankingPathElement<V,E>>
final class RankingPathElementList<V,E> extends AbstractPathElementList<V,E,RankingPathElement<V,E>>
List of simple paths in increasing order of weight.- Since:
- July 5, 2007
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description private static class
RankingPathElementList.PathMask<V,E>
-
Field Summary
Fields Modifier and Type Field Description private PathValidator<V,E>
externalPathValidator
To be used on top of general path validations.private V
guardVertexToNotDisconnect
Vertex that paths of the list must not disconnect.private java.util.Map<RankingPathElement<V,E>,java.lang.Boolean>
path2disconnect
-
Fields inherited from class org.jgrapht.alg.shortestpath.AbstractPathElementList
graph, maxSize, pathElements, vertex
-
-
Constructor Summary
Constructors Constructor Description RankingPathElementList(Graph<V,E> graph, int maxSize, RankingPathElement<V,E> pathElement)
Creates a list with an empty path.RankingPathElementList(Graph<V,E> graph, int maxSize, RankingPathElement<V,E> pathElement, PathValidator<V,E> pathValidator)
Creates a list with an empty path.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.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.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.RankingPathElementList(Graph<V,E> graph, int maxSize, V vertex)
Creates an empty list.RankingPathElementList(Graph<V,E> graph, int maxSize, V vertex, PathValidator<V,E> pathValidator)
Creates an empty list.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description boolean
addPathElements(RankingPathElementList<V,E> elementList, E edge)
Adds paths in the list at vertex y.private double
calculatePathWeight(RankingPathElement<V,E> pathElement, E edge)
Costs taken into account are the weights stored inEdge
objects.(package private) java.util.List<RankingPathElement<V,E>>
getPathElements()
private boolean
isGuardVertexDisconnected(RankingPathElement<V,E> prevPathElement)
Ensures that paths of the list do not disconnect the guard-vertex.private boolean
isNotValidPath(RankingPathElement<V,E> prevPathElement, E edge)
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).-
Methods inherited from class org.jgrapht.alg.shortestpath.AbstractPathElementList
get, getVertex, size
-
Methods inherited from class java.util.AbstractList
add, add, addAll, clear, equals, hashCode, indexOf, iterator, lastIndexOf, listIterator, listIterator, remove, removeRange, set, subList
-
Methods inherited from class java.util.AbstractCollection
addAll, contains, containsAll, isEmpty, remove, removeAll, retainAll, toArray, toArray, toString
-
-
-
-
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 ofRankingPathElement
.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 ofRankingPathElement
.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 ofRankingPathElement
.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
Complexity =elementList
at vertex v.- w/o guard-vertex: O(
k*np
) wherek
is the max size limit of the list andnp
is the maximum number of vertices in the paths stored in the list - with guard-vertex: O(
k*(m+n)
) wherek
is the max size limit of the list,m
is the number of edges of the graph andn
is the number of vertices of the graph, O(m+n
) being the complexity of theConnectivityInspector
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.
- w/o guard-vertex: O(
-
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 inEdge
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.
-
-