jdsl.graph.ref
Class AbstractGraph

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

All Implemented Interfaces:

Container, InspectableContainer, InspectableGraph, InspectablePositionalContainer, PositionalContainer

Direct Known Subclasses:

IncidenceListGraph, IncidenceListOrderedGraph, InspectableSubgraph, TripartiteEmbeddedPlanarGraph

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:

$Revision: 1.19 $, $Date: 2001/03/21 17:16:23 $

Author:

Mark Handy, Benoit Hudson

Inner 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 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.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 jdsl.core.api.InspectableContainer

contains, elements, isEmpty

Methods inherited from interface 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

See Also:

InspectableGraph.numVertices(), InspectableGraph.numEdges()

positions

public PositionIterator positions()

Built on vertices() and edges().

O(V+E)

Specified by:

positions in interface InspectablePositionalContainer

See Also:

InspectableGraph.vertices(), InspectableGraph.edges()

directedEdges

public EdgeIterator directedEdges()

Built on edges() and isDirected(.)

O(E)

Specified by:

directedEdges in interface InspectableGraph

See Also:

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

undirectedEdges

public EdgeIterator undirectedEdges()

Built on edges() and isDirected(.)

O(E)

Specified by:

undirectedEdges in interface InspectableGraph

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

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

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

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

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

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

See Also:

InspectableGraph.incidentEdges(Vertex)

aCommonVertex

public Vertex aCommonVertex(Edge e1,
                            Edge e2)

Built on endVertices(.)

O(1)

Specified by:

aCommonVertex in interface InspectableGraph

See Also:

InspectableGraph.endVertices(Edge)