lu.cs.co.graph
Class Path

java.lang.Object
  |
  +--lu.cs.co.graph.Path

public class Path

extends Object

implements Subgraph

A class for simple paths in a graph. A path is a sequence of adjecent vertices in a graph (or digraph) without repeated vertices, except maybe the first and last (in which case the path is a cycle). The number of vertices is given by the method size, which is the same as the method numVertices specified by the Subgraph interface.

The vertices are ordered 0..numVertices-1. The edges are ordered 0..numEdges-1. If the path is simple then numVertices = numEdges+1. If the path is closed then numVertices=numEdges.

The path's length (in the field len) is the total length of the edges joining the path's vertices in the underlying graph.

Field Summary

int	len The total length of the path.

Constructor Summary

Path(Graph G)
Constructs an empty path.

Path(Graph G, int[] pi, boolean closed)
Constructs a path from an array of vertex indices.

Path(Graph G, Vertex v)
Constructs a path consisting of one vertex only.

Path(Graph G, Vertices V)
Constructs a path consisting of the given vertices.

Method Summary

Object	clone() Returns a clone of this path.
boolean	contains(Edge e)
boolean	contains(Vertex u) Check if the path contains a given vertex.
Edges	edges() Creates an iterator over the edges on this path
void	exchange(int i, int j) Exchange the two vertices on a closed path.
Edge	getEdge(int i) Gets the edge with given index on this path.
Vertex	getVertex(int i) Gets the vertex with given index on this path.
Vertex	head() The last vertex on this path.
void	insert(Edge e) Extends the path with a new edge.
boolean	isClosed() Returns true iff this path is a cycle.
boolean	isExtendedBy(Edge e) Checks if an edge can be added to the path.
boolean	isHamiltonian() Check if the path is Hamiltonian, that is, it contains every vertex in the underlying graph precisely once.
int	numEdges() The number of edges on this path.
int	numVertices() The number of vertices on this path.
int	size() The number of vertices on this path.
Vertex	tail() The first vertex on this path.
String	toString()
Graph	underlying()
Vertices	vertices() Creates an iterator over the vertices on this path.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

len

public int len

The total length of the path. I.e., the sum of the edge lengths.

Constructor Detail

Path

public Path(Graph G)

Constructs an empty path.

Parameters:

G - the underlying graph

Path

public Path(Graph G,
            Vertex v)

Constructs a path consisting of one vertex only. The length of the resulting path is zero.

Parameters:

G - the underlying graph

v - the (only) vertex in the path

Path

public Path(Graph G,
            int[] pi,
            boolean closed)

Constructs a path from an array of vertex indices. The second argument is a list of integers given the indices (in the ordering of the given underlying graph) of the vertices to appear on the path in order. For example, with argument [6,7,3] the constructed path is 6--7--3, visiting the 6th, 7th and 3rd vertex in the argument graph in that order. The third argument allows the path to by closed, returning to the start vertex (that is, the path is a cycle). In our example, this would construct the path 6--7--3--6. The method insert is used to insert the edges, throwing exceptions if the vertex list is illegal.

Parameters:

G - the underlying graph

pi - an array of vertex indices

closed - if true, connects the last vertex to the first, forming a cycle

Path

public Path(Graph G,
            Vertices V)

Constructs a path consisting of the given vertices. Uses insert(Edge e) to insert the edges between these vertices; that method will throw an exception when an illegal insertion is attemped; Graph.getEdge(Vertex, Vertex) will similaraly throw an exception. FIXME, this is not very elegant.

Method Detail

numVertices

public int numVertices()

The number of vertices on this path.

Specified by:

numVertices in interface Subgraph

Returns:

the number of vertices

numEdges

public int numEdges()

The number of edges on this path.

Specified by:

numEdges in interface Subgraph

Returns:

the number of edges

tail

public Vertex tail()

The first vertex on this path.

Returns:

the first vertex

head

public Vertex head()

The last vertex on this path.

Returns:

the last vertex

size

public int size()

The number of vertices on this path. Synonym for numVertices().

Returns:

the number of vertices

toString

public String toString()

Overrides:

toString in class Object

contains

public boolean contains(Vertex u)

Check if the path contains a given vertex. Linear time.

Specified by:

contains in interface Subgraph

Parameters:

u - a vertex in the underlying graph

contains

public boolean contains(Edge e)

Specified by:

contains in interface Subgraph

underlying

public Graph underlying()

Specified by:

underlying in interface Subgraph

edges

public Edges edges()

Creates an iterator over the edges on this path

Returns:

an iterator representing the edges of this graph in the order they appear on this path

vertices

public Vertices vertices()

Creates an iterator over the vertices on this path.

Returns:

an iterator representing the vertices of this path in the order they appear on the path

getVertex

public Vertex getVertex(int i)

Gets the vertex with given index on this path.

Parameters:

i - the index, must be in the range 0..numVertices-1.

Returns:

the vertex with the given index

getEdge

public Edge getEdge(int i)

Gets the edge with given index on this path.

Parameters:

i - the index, must be in the range 0..numEdges-1.

Returns:

the vertex with the given index

insert

public void insert(Edge e)

Extends the path with a new edge. This assumes that isExtendedBy(e) is true.

Parameters:

e - the new edge

isClosed

public boolean isClosed()

Returns true iff this path is a cycle.

Returns:

true if and only if this path is cycle

isHamiltonian

public boolean isHamiltonian()

Check if the path is Hamiltonian, that is, it contains every vertex in the underlying graph precisely once. A Hamiltonian path is a Hamiltonian cycle if it is Hamiltonian and closed.

Returns:

true iff the path is a Hamiltonian path

isExtendedBy

public boolean isExtendedBy(Edge e)

Checks if an edge can be added to the path. An edge can be added to a path if

1. the path is not already closed,
2. the new edge is incident to the path's head, and
3. the new edge does not induce a cycle in the path, except if it closes the path.

Directed edges also have to point in the "right direction," i.e., the source must be incident to the path's head.

The implementation is inefficient.

Parameters:

e - the edge to be added

Returns:

true iff the given edge can be added to the path

exchange

public void exchange(int i,
                     int j)

Exchange the two vertices on a closed path. Assumes that the underlying graph is complete, i.e., all edges are present.

Parameters:

i - the index of one of the vertices to be exchanged

j - the index of the other vertex to be exchanged

clone

public Object clone()

Returns a clone of this path. This clones only the references to this path's vertices and edges; in other words, the original and the copy share edges and vertices.

Returns:

a clone of this path