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