nz.ac.waikato.jdsl.graph.ref
Class AbstractGraph

java.lang.Object
  nz.ac.waikato.jdsl.core.ref.AbstractPositionalContainer
      nz.ac.waikato.jdsl.graph.ref.AbstractGraph

All Implemented Interfaces:

Container, InspectableContainer, InspectablePositionalContainer, PositionalContainer, InspectableGraph

Direct Known Subclasses:

IncidenceListGraph

public abstract class AbstractGraph
extends AbstractPositionalContainer
implements InspectableGraph

An implementation of many of the methods of InspectableGraph in terms of a few primitives. Note that that says "InspectableGraph," not "Graph," but that this class extends AbstractPositionalContainer, which implements replaceElements(.). All the methods implemented here belong to InspectableGraph.

The implementor must define the primitives called by the functions here. In addition, the implementor must define any primitives needed for AbstractPositionalContainer not defined here.

In several places when the AbstractGraph calls a method that the implementer must define, the AbstractGraph is relying on the implementer also checking the input vertex or edge for validity.

The complexities of the methods implemented here depend on the complexities of the underlying methods. Therefore, the complexity documented for each method below is based on suppositions about the underlying implementation.

Version:

JDSL 2.1.1

Author:

Mark Handy, Benoit Hudson

Nested Class Summary

protected static class

AbstractGraph.OO_to_O_MergerIterator

Constructor Summary

protected

AbstractGraph()

Method Summary

Vertex	aCommonVertex(Edge e1, Edge e2) Built on endVertices(.)
Edge	aConnectingEdge(Vertex v1, Vertex v2) Built on incidentEdges(.)
VertexIterator	adjacentVertices(Vertex v) Built on incidentEdges(.)
VertexIterator	adjacentVertices(Vertex v, int edgetype) Built on incidentEdges(.)
boolean	areAdjacent(Edge e1, Edge e2) Built on endVertices(.)
boolean	areAdjacent(Vertex v1, Vertex v2) Built on incidentEdges(.)
EdgeIterator	connectingEdges(Vertex v1, Vertex v2) Built on incidentEdges(.)
EdgeIterator	directedEdges() Built on edges() and isDirected(.)
PositionIterator	positions() Built on vertices() and edges().
int	size() Built on numVertices() and numEdges().
EdgeIterator	undirectedEdges() Built on edges() and isDirected(.)

Methods inherited from class nz.ac.waikato.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 nz.ac.waikato.jdsl.graph.api.InspectableGraph

anEdge, anIncidentEdge, anIncidentEdge, areIncident, aVertex, degree, degree, destination, edges, endVertices, incidentEdges, incidentEdges, isDirected, numEdges, numVertices, opposite, origin, vertices

Methods inherited from interface nz.ac.waikato.jdsl.core.api.InspectableContainer

contains, elements, isEmpty

Methods inherited from interface nz.ac.waikato.jdsl.core.api.Container

newContainer, replaceElement

Constructor Detail

AbstractGraph

protected AbstractGraph()

Method Detail

size

public int size()

Built on numVertices() and numEdges().

O(1)

Specified by:

size in interface InspectableContainer

Returns:

Number of elements stored by the container.

See Also:

InspectableGraph.numVertices(), InspectableGraph.numEdges()

positions

public PositionIterator positions()

Built on vertices() and edges().

O(V+E)

Specified by:

positions in interface InspectablePositionalContainer

Returns:

A PositionIterator over all positions in the container

See Also:

InspectableGraph.vertices(), InspectableGraph.edges()

directedEdges

public EdgeIterator directedEdges()

Built on edges() and isDirected(.)

O(E)

Specified by:

directedEdges in interface InspectableGraph

Returns:

an iterator over all directed edges in the graph

See Also:

InspectableGraph.edges(), InspectableGraph.isDirected(Edge)

undirectedEdges

public EdgeIterator undirectedEdges()

Built on edges() and isDirected(.)

O(E)

Specified by:

undirectedEdges in interface InspectableGraph

Returns:

an iterator over all undirected edges in the graph

See Also:

InspectableGraph.edges(), InspectableGraph.isDirected(Edge)

adjacentVertices

public VertexIterator adjacentVertices(Vertex v)

Built on incidentEdges(.)

O(deg[v])

Specified by:

adjacentVertices in interface InspectableGraph

Parameters:

v - a vertex

Returns:

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

See Also:

InspectableGraph.incidentEdges(Vertex)

adjacentVertices

public VertexIterator adjacentVertices(Vertex v,
                                       int edgetype)

Built on incidentEdges(.)

O(deg[v])

Specified by:

adjacentVertices in interface InspectableGraph

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

See Also:

InspectableGraph.incidentEdges(Vertex)

areAdjacent

public boolean areAdjacent(Vertex v1,
                           Vertex v2)

Built on incidentEdges(.)

O( min(v1.degree,v2.degree) )

Specified by:

areAdjacent in interface InspectableGraph

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

See Also:

InspectableGraph.areAdjacent(Vertex,Vertex)

areAdjacent

public boolean areAdjacent(Edge e1,
                           Edge e2)

Built on endVertices(.)

O(1)

Specified by:

areAdjacent in interface InspectableGraph

Parameters:

e1 - an edge

e2 - an edge

Returns:

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

See Also:

InspectableGraph.endVertices(Edge)

connectingEdges

public EdgeIterator connectingEdges(Vertex v1,
                                    Vertex v2)

Built on incidentEdges(.)

O( min(v1.degree,v2.degree) )

Specified by:

connectingEdges in interface InspectableGraph

Parameters:

v1 - a vertex

v2 - a vertex

Returns:

an iterator over the edges in common between v1 and v2

See Also:

InspectableGraph.incidentEdges(Vertex)

aConnectingEdge

public Edge aConnectingEdge(Vertex v1,
                            Vertex v2)

Built on incidentEdges(.)

O( min(v1.degree,v2.degree) )

Specified by:

aConnectingEdge in interface InspectableGraph

Parameters:

v1 - a vertex

v2 - a vertex

Returns:

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

See Also:

InspectableGraph.incidentEdges(Vertex)

aCommonVertex

public Vertex aCommonVertex(Edge e1,
                            Edge e2)

Built on endVertices(.)

O(1)

Specified by:

aCommonVertex in interface InspectableGraph

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

See Also:

InspectableGraph.endVertices(Edge)