Package org.graph4j.util

Class Walk

java.lang.Object

org.graph4j.util.VertexCollection

org.graph4j.util.VertexList

org.graph4j.util.Walk

All Implemented Interfaces:

Iterable<Integer>

Direct Known Subclasses:

Trail

public class Walk
extends VertexList

A walk is a sequence of graph vertices such that any two consecutive vertices form an edge of the graph. Vertices can repeat. Edges can repeat. In order to ensure these properties are respected, call validate. A walk is closed if the last vertex equals the first one. The length of a walk is its number of edges.

Author:

Cristian Frăsinaru

See Also:

• Trail
• Circuit
• Path
• Cycle

Field Summary

Fields

Modifier and Type	Field	Description
protected int	numEdges

Fields inherited from class org.graph4j.util.VertexCollection

bitset, DEFAULT_CAPACITY, first, graph, numVertices, vertices

Constructor Summary

Constructors

Constructor	Description
Walk(Graph graph)
Walk(Graph graph, int initialCapacity)
Walk(Graph graph, int[] vertices)

Method Summary

Modifier and Type	Method	Description
boolean	add(int v)	Adds the vertex at the end of the walk, trail or path.
protected void	checkEdge(Edge e)
protected final void	checkEdges()
double	computeEdgesWeight()
boolean	equals(Object obj)
int	hashCode()
boolean	isClosed()
boolean	isDirected()
boolean	isValid()
int	length()	The length of the walk, trail, path or cycle (number of edges).
void	reverse()	Reverses the walk. 1-2-3 becomes 3-2-1.
String	toString()
protected String	type()

Methods inherited from class org.graph4j.util.VertexList

addAll, get, indexOf, indexOf, insert, remove, removeFromPos, set, union, union

Methods inherited from class org.graph4j.util.VertexCollection

clear, computeVerticesWeight, contains, getGraph, grow, isClique, isEmpty, isStableSet, iterator, numVertices, removeAll, removeLast, retainAll, size, union, vertexToString, vertices

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.lang.Iterable

forEach, spliterator

Field Details

numEdges

protected int numEdges

Constructor Details

Walk

public Walk(Graph graph)

Walk

public Walk(Graph graph,
 int initialCapacity)

Walk

public Walk(Graph graph,
 int[] vertices)

Method Details

type

protected String type()

checkEdge

protected void checkEdge(Edge e)

checkEdges

protected final void checkEdges()

isValid

public boolean isValid()

Returns:

false if the vertices do not represent the intendended structure.

add

public boolean add(int v)

Adds the vertex at the end of the walk, trail or path.

Overrides:

add in class VertexList

Parameters:

v - a vertex number

Returns:

true if the walk was modified as a result of this invocation.

isDirected

public boolean isDirected()

Returns:

true, if it belongs to a directed graph.

isClosed

public boolean isClosed()

Returns:

true, if the first vertex equals the last one.

length

public int length()

The length of the walk, trail, path or cycle (number of edges).

Returns:

the number of edges.

computeEdgesWeight

public double computeEdgesWeight()

Returns:

the sum of the edge weights.

reverse

public void reverse()

Reverses the walk. 1-2-3 becomes 3-2-1. In case of directed graphs we have to check the reversed walk is valid.

toString

public String toString()

Overrides:

toString in class VertexCollection

hashCode

public int hashCode()

Overrides:

hashCode in class VertexCollection

equals

public boolean equals(Object obj)

Overrides:

equals in class VertexCollection