lu.cs.co.graph
Class Forest

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

public class Forest

extends Object

implements Subgraph, Cloneable

A class for (undirected) forests whose vertex set coincides with the underlying graph. Provides methods for edges insertion and cycle detection.

Field Summary

int	len The total edge length/weigth of all edges in the forest.

Constructor Summary

Forest(Graph G)
Constructs an empty forest over a given graph.

Method Summary

Object	clone() Returns a clone of this forest.
boolean	contains(Edge e) Returns true iff a given edge is in the forest.
boolean	contains(Vertex v) Always returns true.
int	degree(Vertex v) Returns the degree of a given vertex in this forest, that is, the number of incident forest edges.
Edges	edges()
boolean	inducesCycle(Edge e) Returns true iff inserting the given edge would induce a cycle in this forest.
void	insert(Edge e) Inserts an edge.
int	numEdges()
int	numVertices() Returns the number of forest vertices, which is always the number of vertices in the underlying graph.
int	size() Returns the number of edges in the forest.
String	toString() Returns a textual representation of the forest.
Graph	underlying()
Vertices	vertices()

Methods inherited from class java.lang.Object

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

Field Detail

len

public int len

The total edge length/weigth of all edges in the forest.

Constructor Detail

Forest

public Forest(Graph G)

Constructs an empty forest over a given graph. The forest contains all vertices and no edges from the given graph.

Method Detail

clone

public Object clone()

Returns a clone of this forest. This clones only the references to edges in the forest, so the clone and the original share the underlyging subgraph, including its vertices and edges.

Returns:

a clone of this edge

edges

public Edges edges()

vertices

public Vertices vertices()

insert

public void insert(Edge e)

Inserts an edge. Throws a StructureViolationException if the edge induces a cycle.

Throws:

StructureViolationException - If the edge to be inserted induces a cycle in this forest

degree

public int degree(Vertex v)

Returns the degree of a given vertex in this forest, that is, the number of incident forest edges. Note that rhis is not necessarily the same as the degree of the vertex in the underlying graph.

Parameters:

v - the given vertex

Returns:

the degree of the given vertex in the forest

underlying

public Graph underlying()

Specified by:

underlying in interface Subgraph

contains

public boolean contains(Edge e)

Returns true iff a given edge is in the forest. The given edge is supposed to be present in the underlying graph. The implementation is inefficient.

Specified by:

contains in interface Subgraph

Parameters:

e - the given edge

Returns:

true if and only if the given edge is in the forest.

contains

public boolean contains(Vertex v)

Always returns true.

Specified by:

contains in interface Subgraph

inducesCycle

public boolean inducesCycle(Edge e)

Returns true iff inserting the given edge would induce a cycle in this forest.

Parameters:

e - the given edge

Returns:

true if inserting the given edge would induce a cycle

size

public int size()

Returns the number of edges in the forest. Synomym for numEdges().

Returns:

the number of forest edges

numVertices

public int numVertices()

Returns the number of forest vertices, which is always the number of vertices in the underlying graph. This method only exists for implementing the Subgraph interface.

Specified by:

numVertices in interface Subgraph

Returns:

the number of vertices (which is underlying().numVertices())

numEdges

public int numEdges()

Specified by:

numEdges in interface Subgraph

toString

public String toString()

Returns a textual representation of the forest.

Overrides:

toString in class Object