jdsl.graph.api
Interface InspectableGraph

All Superinterfaces:

InspectableContainer, InspectablePositionalContainer

All Known Subinterfaces:

EmbeddedPlanarGraph, Graph, InspectableEmbeddedPlanarGraph, InspectableOrderedGraph, ModifiableGraph, OrderedGraph

All Known Implementing Classes:

AbstractGraph

public interface InspectableGraph

extends InspectablePositionalContainer

An interface describing the accessor methods of a combinatorial graph. Holds both directed and undirected edges, and self-loops and parallel edges. An undirected edge is not the same as a pair of undirected edges. The graph can be disconnected. Subinterfaces can restrict any of these properties.

All iterators returned from graphs have snapshot semantics. That is, their contents are fixed at the moment the iterator is returned and remain unchanged even if the container is changed before the iterator has been exhausted.

No order is guaranteed on the vertices or edges of the graph (the sets of vertices and edges are just that: unordered sets).

Some methods dealing with edge directions take a constant, or an OR of constants, from the EdgeDirection interface. For instance,
incidentEdges(v) gets all edges incident on v,
incidentEdges(v, EdgeDirection.IN) gets all edges directed toward v, and
incidentEdges(v, EdgeDirection.IN | EdgeDirection.OUT) gets all directed edges incident on v.

Version:

$Id: InspectableGraph.java,v 1.13 2000/07/20 23:40:24 lv Exp $

Author:

Luca Vismara (lv), Mark Handy

See Also:

ModifiableGraph, EdgeDirection

Method Summary

Vertex	aCommonVertex(Edge e1, Edge e2)
Edge	aConnectingEdge(Vertex v1, Vertex v2) Gives an arbitrary edge from among those connecting the two specified vertices.
VertexIterator	adjacentVertices(Vertex v) Lists all vertices adjacent to a particular vertex by any kind of edge, with repeats corresponding to parallel edges.
VertexIterator	adjacentVertices(Vertex v, int edgetype) Lists all vertices adjacent to a particular vertex by all edges of the types specified.
Edge	anEdge()
Edge	anIncidentEdge(Vertex v)
Edge	anIncidentEdge(Vertex v, int edgetype)
boolean	areAdjacent(Edge e1, Edge e2) Checks whether two edges have at least one common endpoint.
boolean	areAdjacent(Vertex v1, Vertex v2)
boolean	areIncident(Vertex v, Edge e)
Vertex	aVertex()
EdgeIterator	connectingEdges(Vertex v1, Vertex v2) Gives all edges connecting two vertices.
int	degree(Vertex v) Gives the degree of a vertex, counting both directed and undirected edges.
int	degree(Vertex v, int edgetype) Gives the degree of a vertex, counting all edges of the specified type.
Vertex	destination(Edge e)
EdgeIterator	directedEdges()
EdgeIterator	edges()
Vertex[]	endVertices(Edge e)
EdgeIterator	incidentEdges(Vertex v)
EdgeIterator	incidentEdges(Vertex v, int edgetype)
boolean	isDirected(Edge e)
int	numEdges()
int	numVertices()
Vertex	opposite(Vertex v, Edge e)
Vertex	origin(Edge e)
EdgeIterator	undirectedEdges()
VertexIterator	vertices()

Methods inherited from interface jdsl.core.api.InspectablePositionalContainer

positions

Methods inherited from interface jdsl.core.api.InspectableContainer

contains, elements, isEmpty, size

Method Detail

numVertices

public int numVertices()

Returns:

the number of vertices

numEdges

public int numEdges()

Returns:

the number of edges

vertices

public VertexIterator vertices()

Returns:

an iterator over all vertices in the graph

aVertex

public Vertex aVertex()

Returns:

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

edges

public EdgeIterator edges()

Returns:

an iterator over all edges in the graph

anEdge

public Edge anEdge()

Returns:

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

directedEdges

public EdgeIterator directedEdges()

Returns:

an iterator over all directed edges in the graph

undirectedEdges

public EdgeIterator undirectedEdges()

Returns:

an iterator over all undirected edges in the graph

areAdjacent

public boolean areAdjacent(Vertex v1,
                           Vertex v2)
                    throws InvalidAccessorException

Parameters:

v1 - a vertex

v2 - a vertex

Returns:

whether v1 and v2 are adjacent, i.e., whether they are the endvertices of a common edge

Throws:

InvalidAccessorException - if either v1 or v2 is not contained in this graph

areAdjacent

public boolean areAdjacent(Edge e1,
                           Edge e2)
                    throws InvalidAccessorException

Checks whether two edges have at least one common endpoint. (For example, parallel edges are considered adjacent, as are two self-loops incident on a single vertex.)

Parameters:

e1 - an edge

e2 - an edge

Returns:

whether e1 and e2 are adjacent, i.e., whether they have at least one common endvertex

Throws:

InvalidAccessorException - if either e1 or e2 is not contained in this graph

areIncident

public boolean areIncident(Vertex v,
                           Edge e)
                    throws InvalidAccessorException

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

degree

public int degree(Vertex v)
           throws InvalidAccessorException

Gives the degree of a vertex, counting both directed and undirected edges.

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)
           throws InvalidAccessorException

Gives the degree of a vertex, counting all edges of the specified type.

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

adjacentVertices

public VertexIterator adjacentVertices(Vertex v)
                                throws InvalidAccessorException

Lists all vertices adjacent to a particular vertex by any kind of edge, with repeats corresponding to parallel edges.

Parameters:

v - a vertex

Returns:

an iterator over all vertices adjacent to v by undirected, incoming and outgoing edges

Throws:

InvalidAccessorException - if v is not contain in this graph

adjacentVertices

public VertexIterator adjacentVertices(Vertex v,
                                       int edgetype)
                                throws InvalidAccessorException

Lists all vertices adjacent to a particular vertex by all edges of the types specified.

Parameters:

v - a vertex

edgetype - A constant from the EdgeDirection interface

Returns:

an iterator over all vertices adjacent to v by edges of the specified type

Throws:

InvalidAccessorException - if v is is not contained in this graph

See Also:

EdgeDirection

incidentEdges

public EdgeIterator incidentEdges(Vertex v)
                           throws InvalidAccessorException

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)
                           throws InvalidAccessorException

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

anIncidentEdge

public Edge anIncidentEdge(Vertex v)
                    throws InvalidAccessorException

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)
                    throws InvalidAccessorException

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

connectingEdges

public EdgeIterator connectingEdges(Vertex v1,
                                    Vertex v2)
                             throws InvalidAccessorException

Gives all edges connecting two vertices. If v1==v2, gives all self-loops of the vertex, each reported twice as in incidentEdges(.).

Parameters:

v1 - a vertex

v2 - a vertex

Returns:

an iterator over the edges in common between v1 and v2

Throws:

InvalidAccessorException - if v1 or v2 is not contained in this graph

aConnectingEdge

public Edge aConnectingEdge(Vertex v1,
                            Vertex v2)
                     throws InvalidAccessorException

Gives an arbitrary edge from among those connecting the two specified vertices. If v1==v2, gives a self-loop of the vertex. If there is no edge that can be returned, returns Edge.NONE.

Parameters:

v1 - a vertex

v2 - a vertex

Returns:

an edge between v1 and v2, or Edge.NONE if there is no such edge

endVertices

public Vertex[] endVertices(Edge e)
                     throws InvalidAccessorException

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

opposite

public Vertex opposite(Vertex v,
                       Edge e)
                throws InvalidVertexException,
                       InvalidAccessorException

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)
              throws InvalidEdgeException,
                     InvalidAccessorException

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)
                   throws InvalidEdgeException,
                          InvalidAccessorException

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

aCommonVertex

public Vertex aCommonVertex(Edge e1,
                            Edge e2)
                     throws InvalidAccessorException

Parameters:

e1 - an edge

e2 - an edge

Returns:

any vertex that is an endpoint of both e1 and e2, or Vertex.NONE if there is no such vertex

Throws:

InvalidAccessorException - if e1 or e2 is not contained in this graph

isDirected

public boolean isDirected(Edge e)
                   throws InvalidAccessorException

Parameters:

e - an edge

Returns:

true if e is directed, false otherwise

Throws:

InvalidAccessorException - if e is not contained in this graph