Package org.jgrapht.graph
Class GraphWalk<V,E>
- java.lang.Object
-
- org.jgrapht.graph.GraphWalk<V,E>
-
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
- All Implemented Interfaces:
GraphPath<V,E>
public class GraphWalk<V,E> extends java.lang.Object implements GraphPath<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. More precisely, a walk is a connected sequence of vertices and edges in a graphv0, e0, v1, e1, v2,....vk-1, ek-1, vk
, such that for1<=i<=k<
, the edgee_i
has endpointsv_(i-1)
andv_i
. The class makes no assumptions with respect to the shape of the walk: edges may be repeated, and the start and end point of the walk may be different. See http://mathworld.wolfram.com/Walk.html GraphWalk is the default implementation ofGraphPath
. This class is implemented as a light-weight data structure; this class does not verify whether the sequence of edges or the sequence of vertices provided during construction forms an actual walk. It is the responsibility of the invoking class to provide correct input data.
-
-
Constructor Summary
Constructors Constructor Description GraphWalk(Graph<V,E> graph, java.util.List<V> vertexList, double weight)
Creates a walk defined by a sequence of vertices.GraphWalk(Graph<V,E> graph, V startVertex, V endVertex, java.util.List<E> edgeList, double weight)
Creates a walk defined by a sequence of edges.GraphWalk(Graph<V,E> graph, V startVertex, V endVertex, java.util.List<V> vertexList, java.util.List<E> edgeList, double weight)
Creates a walk defined by both a sequence of edges and a sequence of vertices.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description java.util.List<E>
getEdgeList()
Returns the edges making up the path.V
getEndVertex()
Returns the end vertex in the path.Graph<V,E>
getGraph()
Returns the graph over which this path is defined.int
getLength()
Returns the length of the path, measured in the number of edges.V
getStartVertex()
Returns the start vertex in the path.java.util.List<V>
getVertexList()
Returns the path as a sequence of vertices.double
getWeight()
Returns the weight assigned to the path.java.lang.String
toString()
-
-
-
Constructor Detail
-
GraphWalk
public GraphWalk(Graph<V,E> graph, V startVertex, V endVertex, java.util.List<E> edgeList, double weight)
Creates a walk defined by a sequence of edges. A walk defined by its edges can be specified for non-simple graphs. Edge repetition is permitted, the start and end point points (v0 and vk) can be different.- Parameters:
graph
- the graphstartVertex
- the starting vertexendVertex
- the last vertex of the pathedgeList
- the list of edges of the pathweight
- the total weight of the path
-
GraphWalk
public GraphWalk(Graph<V,E> graph, java.util.List<V> vertexList, double weight)
Creates a walk defined by a sequence of vertices. Note that the input graph must be simple, otherwise the vertex sequence does not necessarily define a unique path. Furthermore, all vertices must be pairwise adjacent.- Parameters:
graph
- the graphvertexList
- the list of vertices of the pathweight
- the total weight of the path
-
GraphWalk
public GraphWalk(Graph<V,E> graph, V startVertex, V endVertex, java.util.List<V> vertexList, java.util.List<E> edgeList, double weight)
Creates a walk defined by both a sequence of edges and a sequence of vertices. Note that both the sequence of edges and the sequence of vertices must describe the same path! This is not verified during the construction of the walk. This constructor makes it possible to store both a vertex and an edge view of the same walk, thereby saving computational overhead when switching from one to the other.- Parameters:
graph
- the graphstartVertex
- the starting vertexendVertex
- the last vertex of the pathvertexList
- the list of vertices of the pathedgeList
- the list of edges of the pathweight
- the total weight of the path
-
-
Method Detail
-
getGraph
public Graph<V,E> getGraph()
Description copied from interface:GraphPath
Returns the graph over which this path is defined. The path may also be valid with respect to other graphs.
-
getStartVertex
public V getStartVertex()
Description copied from interface:GraphPath
Returns the start vertex in the path.- Specified by:
getStartVertex
in interfaceGraphPath<V,E>
- Returns:
- the start vertex
-
getEndVertex
public V getEndVertex()
Description copied from interface:GraphPath
Returns the end vertex in the path.- Specified by:
getEndVertex
in interfaceGraphPath<V,E>
- Returns:
- the end vertex
-
getEdgeList
public java.util.List<E> getEdgeList()
Description copied from interface:GraphPath
Returns the edges making up the path. The first edge in this path is incident to the start vertex. The last edge is incident to the end vertex. The vertices along the path can be obtained by traversing from the start vertex, finding its opposite across the first edge, and then doing the same successively across subsequent edges; seeGraphPath.getVertexList()
.Whether or not the returned edge list is modifiable depends on the path implementation.
- Specified by:
getEdgeList
in interfaceGraphPath<V,E>
- Returns:
- list of edges traversed by the path
-
getVertexList
public java.util.List<V> getVertexList()
Description copied from interface:GraphPath
Returns the path as a sequence of vertices.- Specified by:
getVertexList
in interfaceGraphPath<V,E>
- Returns:
- path, denoted by a list of vertices
-
getWeight
public double getWeight()
Description copied from interface:GraphPath
Returns the weight assigned to the path. Typically, this will be the sum of the weights of the edge list entries (as defined by the containing graph), but some path implementations may use other definitions.
-
getLength
public int getLength()
Description copied from interface:GraphPath
Returns the length of the path, measured in the number of edges.
-
toString
public java.lang.String toString()
- Overrides:
toString
in classjava.lang.Object
-
-