jdsl.graph.ref
Class InspectableSubgraph

java.lang.Object
  |
  +--jdsl.core.ref.AbstractPositionalContainer
        |
        +--jdsl.graph.ref.AbstractGraph
              |
              +--jdsl.graph.ref.InspectableSubgraph

All Implemented Interfaces:

Container, InspectableContainer, InspectableGraph, InspectablePositionalContainer, PositionalContainer

public class InspectableSubgraph

extends AbstractGraph

This class represents a subgraph of an InspectableGraph. It can be constructed from a set of vertices or edges Note that n, E, and V in all time complexities are with respect to the original graph, not the size of the subgraph, unless otherwise stated. All Positions returned by the subgraph will be the same as the positions returned in the original graph. Even though this is an AbstractGraph, you may not modify this graph. All attempts to do so will fail. This graph maintains a reference to the graph upon which this subgraph is induced. If that graph changes, then the inspectable graph will change.

Version:

$Revision: 1.8 $, $Date: 2001/03/21 17:16:24 $

Author:

Mike Boilen

Inner classes inherited from class jdsl.graph.ref.AbstractGraph

AbstractGraph.OO_to_O_MergerIterator

Constructor Summary

InspectableSubgraph(InspectableGraph graph, EdgeIterator edges)
Constructs the subgraph induced by the given edges.

InspectableSubgraph(InspectableGraph graph, VertexIterator vertices)
Constructs the subgraph induced by the given vertices.

Method Summary

Edge	anEdge() This runs in time proportional to the running time of the corresponding method in the graph around which this subgraph wraps.
Edge	anIncidentEdge(Vertex v) This runs in time proportional to the running time of the corresponding method in the graph around which this subgraph wraps.
Edge	anIncidentEdge(Vertex v, int edgeType) This runs in time proportional to the running time of the corresponding method in the graph around which this subgraph wraps.
boolean	areIncident(Vertex v, Edge e) O(1)
Vertex	aVertex() This runs in time proportional to the running time of the corresponding method in the graph around which this subgraph wraps.
boolean	contains(Accessor a) O(1)
int	degree(Vertex v) This runs in time proportional to the running time of the corresponding method in the graph around which this subgraph wraps.
int	degree(Vertex v, int edgeType) This runs in time proportional to the running time of the corresponding method in the graph around which this subgraph wraps.
Vertex	destination(Edge e) O(1)
EdgeIterator	edges() O(E in subgraph )
ObjectIterator	elements() Runs in time proportional to vertices() + elements() in the subgraph.
Vertex[]	endVertices(Edge e)
EdgeIterator	incidentEdges(Vertex v) This runs in time proportional to the running time of the corresponding method in the graph around which this subgraph wraps.
EdgeIterator	incidentEdges(Vertex v, int edgeType) This runs in time proportional to the running time of the corresponding method in the graph around which this subgraph wraps.
boolean	isDirected(Edge e) This runs in time proportional to the running time of the corresponding method in the graph around which this subgraph wraps.
Container	newContainer() This method is unsupported.
int	numEdges() O(1)
int	numVertices() O(1)
Vertex	opposite(Vertex v, Edge e) O(1)
Vertex	origin(Edge e) O(1)
java.lang.Object	replaceElement(Accessor a, java.lang.Object obj) This method is unsupported.
VertexIterator	vertices() O( V in subgraph )

Methods inherited from class jdsl.graph.ref.AbstractGraph

aCommonVertex, aConnectingEdge, adjacentVertices, adjacentVertices, areAdjacent, areAdjacent, connectingEdges, directedEdges, positions, size, undirectedEdges

Methods inherited from class jdsl.core.ref.AbstractPositionalContainer

isEmpty, swapElements

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface jdsl.core.api.InspectableContainer

isEmpty

Constructor Detail

InspectableSubgraph

public InspectableSubgraph(InspectableGraph graph,
                           VertexIterator vertices)

Constructs the subgraph induced by the given vertices.

InspectableSubgraph

public InspectableSubgraph(InspectableGraph graph,
                           EdgeIterator edges)

Constructs the subgraph induced by the given edges.

Method Detail

replaceElement

public java.lang.Object replaceElement(Accessor a,
                                       java.lang.Object obj)
                                throws InvalidAccessorException

This method is unsupported.

Following copied from interface: jdsl.core.api.Container

Parameters:

a - Accessor in this container

newElement - to be stored at a

Returns:

old element, previously stored at a

Throws:

InvalidAccessorException - if a is null or does not belong to this container

numVertices

public int numVertices()

O(1)

Following copied from interface: jdsl.graph.api.InspectableGraph

Returns:

the number of vertices

vertices

public VertexIterator vertices()

O( V in subgraph )

Following copied from interface: jdsl.graph.api.InspectableGraph

Returns:

an iterator over all vertices in the graph

numEdges

public int numEdges()

O(1)

Following copied from interface: jdsl.graph.api.InspectableGraph

Returns:

the number of edges

edges

public EdgeIterator edges()

O(E in subgraph )

Following copied from interface: jdsl.graph.api.InspectableGraph

Returns:

an iterator over all edges in the graph

incidentEdges

public EdgeIterator incidentEdges(Vertex v)

This runs in time proportional to the running time of the corresponding method in the graph around which this subgraph wraps.

Following copied from interface: jdsl.graph.api.InspectableGraph

Parameters:

v - a vertex

Returns:

an iterator over all edges incident on v

Throws:

InvalidAccessorException - if v is not contained in this graph

incidentEdges

public EdgeIterator incidentEdges(Vertex v,
                                  int edgeType)

This runs in time proportional to the running time of the corresponding method in the graph around which this subgraph wraps.

Following copied from interface: jdsl.graph.api.InspectableGraph

Parameters:

v - a vertex

edgetype - A constant from the EdgeDirection interface

Returns:

an iterator over all edges of the specified type incident on v

Throws:

InvalidAccessorException - if v is not contained in this graph

See Also:

EdgeDirection

isDirected

public boolean isDirected(Edge e)

This runs in time proportional to the running time of the corresponding method in the graph around which this subgraph wraps.

Following copied from interface: jdsl.graph.api.InspectableGraph

Parameters:

e - an edge

Returns:

true if e is directed, false otherwise

Throws:

InvalidAccessorException - if e is not contained in this graph

endVertices

public Vertex[] endVertices(Edge e)
                     throws InvalidAccessorException

Following copied from interface: jdsl.graph.api.InspectableGraph

Parameters:

e - an edge

Returns:

an array (of size 2) containing the two endvertices of e; if e is directed, the first element of the array is the origin of e and the second element is the destination of e

Throws:

InvalidAccessorException - if e is not contained in this graph

aVertex

public Vertex aVertex()

This runs in time proportional to the running time of the corresponding method in the graph around which this subgraph wraps. However, this method takes at least O(V) time.

Following copied from interface: jdsl.graph.api.InspectableGraph

Returns:

an arbitrary vertex, or Vertex.NONE if the graph is empty

anEdge

public Edge anEdge()

This runs in time proportional to the running time of the corresponding method in the graph around which this subgraph wraps. However, this method takes at least O(E) time.

Following copied from interface: jdsl.graph.api.InspectableGraph

Returns:

an arbitrary edge, or Edge.NONE if the graph has no edges

opposite

public Vertex opposite(Vertex v,
                       Edge e)

O(1)

Following copied from interface: jdsl.graph.api.InspectableGraph

Parameters:

v - one endvertex of e

e - an edge

Returns:

the endvertex of e different from v

Throws:

InvalidVertexException - if v is not an endvertex of e

InvalidAccessorException - if v or e is not contained in this graph

origin

public Vertex origin(Edge e)

O(1)

Following copied from interface: jdsl.graph.api.InspectableGraph

Parameters:

e - an edge

Returns:

the origin vertex of e, if e is directed

Throws:

InvalidEdgeException - if e is undirected

InvalidAccessorException - if e is not contained in this graph

destination

public Vertex destination(Edge e)

O(1)

Following copied from interface: jdsl.graph.api.InspectableGraph

Parameters:

e - an edge

Returns:

the destination vertex of e, if e is directed

Throws:

InvalidEdgeException - if e is undirected

InvalidAccessorException - if e is not contained in this graph

areIncident

public boolean areIncident(Vertex v,
                           Edge e)

O(1)

Following copied from interface: jdsl.graph.api.InspectableGraph

Parameters:

v - a vertex

e - an edge

Returns:

whether v and e are incident, i.e., whether v is an endvertex of e

Throws:

InvalidAccessorException - if either v or e is not contained in this graph

newContainer

public Container newContainer()

This method is unsupported. All attempts to call this will fail.

Following copied from interface: jdsl.core.api.Container

Returns:

A new, empty Container of the same class as this one.

contains

public boolean contains(Accessor a)

O(1)

Following copied from interface: jdsl.core.api.InspectableContainer

Throws:

InvalidAccessorException - if a is null

anIncidentEdge

public Edge anIncidentEdge(Vertex v)
                    throws NoSuchEdgeException,
                           InvalidAccessorException

This runs in time proportional to the running time of the corresponding method in the graph around which this subgraph wraps.

Following copied from interface: jdsl.graph.api.InspectableGraph

Parameters:

v - a vertex

Returns:

any edge incident on v, or Edge.NONE if there is no edge incident on v

Throws:

InvalidAccessorException - if v is not contained in this graph

anIncidentEdge

public Edge anIncidentEdge(Vertex v,
                           int edgeType)

This runs in time proportional to the running time of the corresponding method in the graph around which this subgraph wraps.

Following copied from interface: jdsl.graph.api.InspectableGraph

Parameters:

v - a vertex

edgetype - A constant from the EdgeDirection interface

Returns:

any edge of the specified type incident on v, or Edge.NONE if there is no such edge incident on v

Throws:

InvalidAccessorException - if v is not contained in this graph

See Also:

EdgeDirection

degree

public int degree(Vertex v)

This runs in time proportional to the running time of the corresponding method in the graph around which this subgraph wraps. However, it can take no less than O( degree ) time.

Following copied from interface: jdsl.graph.api.InspectableGraph

Parameters:

v - a vertex

Returns:

the number of edges (directed and undirected) incident with v

Throws:

InvalidAccessorException - if v is not contained in this graph

degree

public int degree(Vertex v,
                  int edgeType)

This runs in time proportional to the running time of the corresponding method in the graph around which this subgraph wraps. However, it can take no less than O( degree ) time.

Following copied from interface: jdsl.graph.api.InspectableGraph

Parameters:

v - a vertex

edgetype - A constant from the EdgeDirection interface

Returns:

the number of edges of the specified type incident with v

Throws:

InvalidAccessorException - if v is not contained in this graph

See Also:

EdgeDirection

elements

public ObjectIterator elements()

Runs in time proportional to vertices() + elements() in the subgraph.

Following copied from interface: jdsl.core.api.InspectableContainer

Returns:

an iterator over all the elements stored in this container