Uses of Interface
org.jgrapht.GraphPath
Packages that use GraphPath
Package
Description
Algorithms related to graph cycles.
Algorithm related interfaces.
Shortest-path related algorithms.
Graph tours related algorithms.
Implementations of various graphs.
-
Uses of GraphPath in org.jgrapht.alg.cycle
Fields in org.jgrapht.alg.cycle declared as GraphPathModifier and TypeFieldDescriptionBergeGraphInspector.certificate
WeakChordalityInspector.certificate
Contains a hole or an anti-hole of the graph, if it isn't weakly chordalChordalityInspector.hole
A hole contained in the inspectedgraph
.Methods in org.jgrapht.alg.cycle that return GraphPathModifier and TypeMethodDescriptionConstructs cycle with minimum mean using information inpolicyGraph
.WeakChordalityInspector.findHole
(Graph<V, E> graph, V sourceInSeparator, V source, V target, V targetInSeparator) Finds a hole in the specifiedgraph
.BergeGraphInspector.getCertificate()
Returns the certificate in the form of a hole or anti-hole in the inspected graph, when theBergeGraphInspector.isBerge(org.jgrapht.Graph<V, E>, boolean)
method is previously called withcomputeCertificate=true
.WeakChordalityInspector.getCertificate()
Computes and returns the certificate in the form of a hole or anti-hole in the inspectedgraph
.ChinesePostman.getCPPSolution
(Graph<V, E> graph) Solves the Chinese Postman Problem on the given graph.HowardMinimumMeanCycle.getCycle()
Computes cycle with minimum mean.HierholzerEulerianCycle.getEulerianCycle
(Graph<V, E> g) Compute an Eulerian cycle of a graph.ChordalityInspector.getHole()
A graph which is not chordal, must contain a hole (chordless cycle on 4 or more vertices).Returns a path in g from start to end avoiding the vertices in XBergeGraphInspector.p
(Graph<V, E> g, GraphPath<V, E> pathS, GraphPath<V, E> pathT, V m, V b1, V b2, V b3, V s1, V s2, V s3) Assembles a GraphPath of the Paths S and T.ChinesePostman.replaceShortcutEdges
(Graph<V, E> inputGraph, GraphPath<V, E> pathWithShortcuts, Map<E, GraphPath<V, E>> shortcutEdges) static <V,
E> GraphPath <V, E> Cycles.simpleCycleToGraphPath
(Graph<V, E> graph, List<E> cycle) Transform a simple cycle from an edge set representation to a graph path.ChinesePostman.solveCPPDirected
(Graph<V, E> graph) Solves the CPP for directed graphsChinesePostman.solveCPPUndirected
(Graph<V, E> graph) Solves the CPP for undirected graphsMethods in org.jgrapht.alg.cycle with parameters of type GraphPathModifier and TypeMethodDescriptionLists the vertices which are covered by two pathsBergeGraphInspector.p
(Graph<V, E> g, GraphPath<V, E> pathS, GraphPath<V, E> pathT, V m, V b1, V b2, V b3, V s1, V s2, V s3) Assembles a GraphPath of the Paths S and T.ChinesePostman.replaceShortcutEdges
(Graph<V, E> inputGraph, GraphPath<V, E> pathWithShortcuts, Map<E, GraphPath<V, E>> shortcutEdges) Method parameters in org.jgrapht.alg.cycle with type arguments of type GraphPath -
Uses of GraphPath in org.jgrapht.alg.interfaces
Fields in org.jgrapht.alg.interfaces with type parameters of type GraphPathModifier and TypeFieldDescriptionCycleBasisAlgorithm.CycleBasisImpl.graphPaths
TreeToPathDecompositionAlgorithm.PathDecompositionImpl.paths
Methods in org.jgrapht.alg.interfaces that return GraphPathModifier and TypeMethodDescriptionMinimumCycleMeanAlgorithm.getCycle()
Computes cycle with minimum mean.EulerianCycleAlgorithm.getEulerianCycle
(Graph<V, E> graph) Compute an Eulerian cycle of a graph.Return the path from thesource
vertex to thetarget
vertex.Get a shortest path from a source vertex to a sink vertex.Return the path from the source vertex to the sink vertex.Computes a tour.HamiltonianCycleImprovementAlgorithm.improveTour
(GraphPath<V, E> tour) Improves a tour.Methods in org.jgrapht.alg.interfaces that return types with arguments of type GraphPathModifier and TypeMethodDescriptionCycleBasisAlgorithm.CycleBasis.getCyclesAsGraphPaths()
Return the set of cycles of the cycle basis.CycleBasisAlgorithm.CycleBasisImpl.getCyclesAsGraphPaths()
Return the set of cycles of the cycle basis.Get a list of k-shortest paths from a source vertex to a sink vertex.Get a shortest path from a source vertex to a sink vertex.Return the path from the source vertex to the sink vertex.TreeToPathDecompositionAlgorithm.PathDecomposition.getPaths()
Set of disjoint paths of the decompositionTreeToPathDecompositionAlgorithm.PathDecompositionImpl.getPaths()
Methods in org.jgrapht.alg.interfaces with parameters of type GraphPath -
Uses of GraphPath in org.jgrapht.alg.shortestpath
Classes in org.jgrapht.alg.shortestpath that implement GraphPathModifier and TypeClassDescriptionprivate class
Represents a path that is generated during the computations.Fields in org.jgrapht.alg.shortestpath declared as GraphPathModifier and TypeFieldDescriptionprivate GraphPath
<?, ?> NegativeCycleDetectedException.cycle
TransitNodeRoutingPrecomputation.AccessVertex.path
Path between a vertex $v$ this access vertex is computed for andvertex
.Fields in org.jgrapht.alg.shortestpath with type parameters of type GraphPathModifier and TypeFieldDescriptionYenShortestPathIterator.candidatePaths
Heap of the candidate path generated so far and sorted my their weights.YenShortestPathIterator.firstDeviations
For each path $P$, stores its deviation point.YenShortestPathIterator.lastDeviations
For each path $P$ stores the vertex $u$ such that $pathValidator#isValidPath([start_vertex, u], (u,v)) = false$, where $[start_vertex, u]$ denotes the subpath of $P$ from its start to vertex $u$ and $v$ is the next vertex in $P$ after $u$.ListMultiObjectiveSingleSourcePathsImpl.paths
One path per vertexListSingleSourcePathsImpl.paths
One path per vertexDefaultManyToManyShortestPaths.DefaultManyToManyShortestPathsImpl.pathsMap
Map with paths between sources and targets.TransitNodeRoutingPrecomputation.PathsUnpackingTask.pathsMap
Map where the unpacked paths will be stored.YenShortestPathIterator.resultList
List of the paths returned so far via theYenShortestPathIterator.next()
method.Methods in org.jgrapht.alg.shortestpath that return GraphPathModifier and TypeMethodDescriptionAStarShortestPath.buildGraphPath
(V startVertex, V targetVertex, double pathLength) Builds the graph pathBaseKDisjointShortestPathsAlgorithm.calculateShortestPath
(V startVertex, V endVertex) Calculates the shortest paths for the current iteration.BhandariKDisjointShortestPaths.calculateShortestPath
(V startVertex, V endVertex) SuurballeKDisjointShortestPaths.calculateShortestPath
(V startVertex, V endVertex) BellmanFordShortestPath.computeNegativeCycle
(E edge, Map<V, E> pred) Computes a negative weight cycle assuming that the algorithm has already determined that it exists.BaseMultiObjectiveShortestPathAlgorithm.createEmptyPath
(V source, V sink) Create an empty path.BaseShortestPathAlgorithm.createEmptyPath
(V source, V sink) Create an empty path.BaseKDisjointShortestPathsAlgorithm.createGraphPath
(List<E> edgeList, V startVertex, V endVertex) BaseBidirectionalShortestPathAlgorithm.createPath
(BaseBidirectionalShortestPathAlgorithm.BaseSearchFrontier<V, E> forwardFrontier, BaseBidirectionalShortestPathAlgorithm.BaseSearchFrontier<V, E> backwardFrontier, double weight, V source, V commonVertex, V sink) Builds shortest path betweensource
andsink
based on the information provided by search frontiers and common vertex.ContractionHierarchyBidirectionalDijkstra.createPath
(ContractionHierarchyBidirectionalDijkstra.ContractionSearchFrontier<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionEdge<E>> forwardFrontier, ContractionHierarchyBidirectionalDijkstra.ContractionSearchFrontier<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionEdge<E>> backwardFrontier, double weight, ContractionHierarchyPrecomputation.ContractionVertex<V> source, ContractionHierarchyPrecomputation.ContractionVertex<V> commonVertex, ContractionHierarchyPrecomputation.ContractionVertex<V> sink) Builds shortest unpacked path betweensource
andsink
based on the information provided by search frontiers and common vertex.static <V,
E> GraphPath <V, E> BellmanFordShortestPath.findPathBetween
(Graph<V, E> graph, V source, V sink) Find a path between two vertices.static <V,
E> GraphPath <V, E> BFSShortestPath.findPathBetween
(Graph<V, E> graph, V source, V sink) Find a path between two vertices.static <V,
E> GraphPath <V, E> BidirectionalDijkstraShortestPath.findPathBetween
(Graph<V, E> graph, V source, V sink) Find a path between two vertices.static <V,
E> GraphPath <V, E> DijkstraShortestPath.findPathBetween
(Graph<V, E> graph, V source, V sink) Find a path between two vertices.IntVertexDijkstraShortestPath.findPathBetween
(Graph<Integer, E> graph, Integer source, Integer sink) Find a path between two vertices.YenShortestPathIterator.getCandidatePath
(GraphPath<V, E> path, int recoverVertexIndex, GraphPath<V, E> spurPath) Builds a candidate path based on the information provided in the methods parameters.GraphPath
<?, ?> NegativeCycleDetectedException.getCycle()
Get the actual negative cycle, or null if not provided.Calculates (and returns) the shortest path from the sourceVertex to the targetVertex.Get a shortest path from a source vertex to a sink vertex.Get a shortest path from a source vertex to a sink vertex.Get a shortest path from a source vertex to a sink vertex.Get a shortest path from a source vertex to a sink vertex.Return the path from thesource
vertex to thetarget
vertex.Get a shortest path from a source vertex to a sink vertex.Return the path from thesource
vertex to thetarget
vertex.Get a shortest path from a source vertex to a sink vertex.Return the path from thesource
vertex to thetarget
vertex.Get a shortest path from a source vertex to a sink vertex.Get a shortest path from a source vertex to a sink vertex.Get a shortest path from a source vertex to a sink vertex.Return the path from the source vertex to the sink vertex.TransitNodeRoutingPrecomputation.AccessVertex.getPath()
Returns path between a vertex in the graph andvertex
.Get a shortest path from a source vertex to a sink vertex.Return the path from the source vertex to the sink vertex.Transform an ordered list of edges into a GraphPath.TransitNodeRoutingShortestPath.mergePaths
(GraphPath<V, E> first, GraphPath<V, E> second, GraphPath<V, E> third) Computes a path which consists offirst
,second
andthird
paths.EppsteinShortestPathIterator.next()
YenShortestPathIterator.next()
Methods in org.jgrapht.alg.shortestpath that return types with arguments of type GraphPathModifier and TypeMethodDescriptionBaseKDisjointShortestPathsAlgorithm.buildPaths
(V startVertex, V endVertex) After removing overlapping edges, each path is not necessarily connecting start to end vertex.MartinShortestPath.buildPaths
(V source) Build the actual paths from the final labels of each node.AllDirectedPaths.generatePaths
(Set<V> sourceVertices, Set<V> targetVertices, boolean simplePathsOnly, Integer maxPathLength, Map<E, Integer> edgeMinDistancesFromTargets) Generate all paths from the sources to the targets, using pre-computed minimum distances.AllDirectedPaths.getAllPaths
(Set<V> sourceVertices, Set<V> targetVertices, boolean simplePathsOnly, Integer maxPathLength) Calculate (and return) all paths from the source vertices to the target vertices.AllDirectedPaths.getAllPaths
(V sourceVertex, V targetVertex, boolean simplePathsOnly, Integer maxPathLength) Calculate (and return) all paths from the source vertex to the target vertex.Returns the $k$ shortest simple paths in increasing order of weight.Computesk
shortest paths betweensource
andsink
.Computesk
shortest loopless paths betweensource
andsink
.BaseKDisjointShortestPathsAlgorithm.resolvePaths
(V startVertex, V endVertex) At the end of the search we have list of intermediate paths - not necessarily disjoint and may contain reversed edges.Methods in org.jgrapht.alg.shortestpath with parameters of type GraphPathModifier and TypeMethodDescriptionprivate int
YenShortestPathIterator.addDeviations
(GraphPath<V, E> path) Builds unique loopless deviations from the given path in thegraph
.YenShortestPathIterator.getCandidatePath
(GraphPath<V, E> path, int recoverVertexIndex, GraphPath<V, E> spurPath) Builds a candidate path based on the information provided in the methods parameters.private V
YenShortestPathIterator.getLastValidDeviation
(GraphPath<V, E> path, V firstDeviation) Computes vertex $u$ such that $pathValidator#isValidPath([start_vertex, u], (u,v)) = false$, where $[start_vertex, u]$ denotes the subpath of $P$ from its start to vertex $u$ and $v$ is the next vertex in $P$ after $u$.YenShortestPathIterator.getMaskedVerticesAndEdges
(GraphPath<V, E> path, V pathDeviation, int pathDeviationIndex) For the givenpath
builds sets of vertices and edges to be masked.boolean
PathValidator.isValidPath
(GraphPath<V, E> partialPath, E edge) Checks if an edge can be added to a previous path element.TransitNodeRoutingShortestPath.mergePaths
(GraphPath<V, E> first, GraphPath<V, E> second, GraphPath<V, E> third) Computes a path which consists offirst
,second
andthird
paths.void
Set the negative cycle.Constructors in org.jgrapht.alg.shortestpath with parameters of type GraphPathModifierConstructorDescriptionAccessVertex
(V vertex, GraphPath<V, E> path) Constructs a new instance for the givenvertex
andpath
.NegativeCycleDetectedException
(String message, GraphPath<?, ?> cycle) Constructs a new exception with the specified detail message.Constructor parameters in org.jgrapht.alg.shortestpath with type arguments of type GraphPathModifierConstructorDescription(package private)
DefaultManyToManyShortestPathsImpl
(Set<V> sources, Set<V> targets, Map<V, Map<V, GraphPath<V, E>>> pathsMap) Constructs an instance of the algorithm for the givensources
,targets
andpathsMap
.ListMultiObjectiveSingleSourcePathsImpl
(Graph<V, E> graph, V source, Map<V, List<GraphPath<V, E>>> paths) Construct a new instance.Construct a new instance.PathsUnpackingTask
(int taskId, List<V> transitVertices, Map<V, Map<V, GraphPath<V, E>>> pathsMap, ManyToManyShortestPathsAlgorithm.ManyToManyShortestPaths<V, E> shortestPaths) Constructs a new instance for the giventaskId
,transitVertices
,pathsMap
andshortestPaths
.YenShortestPathIterator
(Graph<V, E> graph, V source, V sink, Supplier<org.jheaps.AddressableHeap<Double, Pair<GraphPath<V, E>, Boolean>>> heapSupplier) Constructs an instance of the algorithm for givengraph
,source
,sink
andheapSupplier
.YenShortestPathIterator
(Graph<V, E> graph, V source, V sink, Supplier<org.jheaps.AddressableHeap<Double, Pair<GraphPath<V, E>, Boolean>>> heapSupplier, PathValidator<V, E> pathValidator) Constructs an instance of the algorithm for givengraph
,source
,sink
,heapSupplier
andpathValidator
. -
Uses of GraphPath in org.jgrapht.alg.tour
Fields in org.jgrapht.alg.tour declared as GraphPathMethods in org.jgrapht.alg.tour that return GraphPathModifier and TypeMethodDescriptionTransform from a closed List representation (first and last vertex element are the same) to a graph path.Transform from a Set representation to a graph path.HamiltonianCycleAlgorithmBase.getSingletonTour
(Graph<V, E> graph) Creates a tour for a graph with 1 vertexComputes a $3/2$-approximate tour.Computes a tour using the greedy heuristic.Computes a minimum-cost Hamiltonian tour.Computes a tour using the nearest insertion heuristic.Computes a tour using the nearest neighbour heuristic.Computes a Hamiltonian tour.Computes a tour using the greedy heuristic.Computes a 2-approximate tour.Computes a 2-approximate tour.TwoOptHeuristicTSP.improveTour
(GraphPath<V, E> tour) Try to improve a tour by running the 2-opt heuristic.TwoOptHeuristicTSP.tourToPath
(int[] tour) Transform from an array representation to a graph path.Transform from a List representation to a graph path.Methods in org.jgrapht.alg.tour with parameters of type GraphPathModifier and TypeMethodDescriptionTwoOptHeuristicTSP.improveTour
(GraphPath<V, E> tour) Try to improve a tour by running the 2-opt heuristic.private int[]
TwoOptHeuristicTSP.pathToTour
(GraphPath<V, E> path) Transform from a path representation to an array representation.Constructors in org.jgrapht.alg.tour with parameters of type GraphPathModifierConstructorDescriptionNearestInsertionHeuristicTSP
(GraphPath<V, E> subtour) Constructor Specifies an existing sub-tour that will be augmented to form a complete tour whenNearestInsertionHeuristicTSP.getTour(org.jgrapht.Graph)
is called -
Uses of GraphPath in org.jgrapht.graph
Classes in org.jgrapht.graph that implement GraphPathModifier and TypeClassDescriptionclass
GraphWalk<V,
E> A walk in a graph is an alternating sequence of vertices and edges, starting and ending at a vertex, in which each edge is adjacent in the sequence to its two endpoints.