jdsl.graph.ref
Class IncidenceListGraph

java.lang.Object
  |
  +--jdsl.core.ref.AbstractPositionalContainer
        |
        +--jdsl.graph.ref.AbstractGraph
              |
              +--jdsl.graph.ref.IncidenceListGraph
All Implemented Interfaces:
Container, EdgeDirection, Graph, InspectableContainer, InspectableGraph, InspectablePositionalContainer, ModifiableGraph, PositionalContainer

public class IncidenceListGraph
extends AbstractGraph
implements Graph, EdgeDirection

An implementation of the Graph interface, including self-loops, parallel edges, and mixed directed and undirected edges. For specifications of the methods, see the documentation of the interfaces. The remainder of this description is about the implementation.

The following is a high-level description of the design; low-level details appear further below. The graph is implemented via a list of vertices and a list of edges. The nodes of these "global" lists are the vertices and edges of the graph, respectively. In addition to the global lists of vertices and edges, each vertex has a "local" list of its incident edges. Thus, each edge participates in two local lists (one for each endpoint) plus the global list. Each vertex participates in only the global list. Although sequential data structures are used to implement the graph, the graph conceptually consists of unordered sets; no guarantee is made about where in the various lists a given accessor appears.

This design forces most of the methods' time complexities. Insertion and deletion of vertices and edges are constant-time because the various doubly-linked lists can be modified in constant time. Adjacency queries are typically O(degrees of vertices involved). Iterations take time linear in the number of things iterated over.

The remainder of this description is about low-level details of the design, and efficiency tradeoffs of alternate designs.

The global list of edges exists to avoid having the duplicates in edges() that would result from asking all vertices for their incident edges (each edge would appear twice). For most other purposes, the only global list required would be the vertex list. An alternate design would get rid of the global edge list and would do a traversal to get edges(). This would save space at the cost of increasing the complexity of edges() from O(E) to O(V+E).

Both global lists are implemented with JDSL NodeSequences. In contrast, the local incidence lists at each vertex are implemented "by hand," with links in the ILEdges, for space efficiency. Internal methods that refer to those links also take a vertex, so the edge knows which set of links is being referred to (the set for one endpoint or the set for the other endpoint). Each local list includes a dummy edge to handle special cases (empty list, iterating till end of list, inserting at beginning of list).

To avoid the space overhead of having the global lists' positions point to vertex/edge objects, which would need to point back to the positions, the positions *are* the vertices/edges. This is accomplished by inheriting from the position implementation of the NodeSequence (called FNSNode) and using the posInsert* methods to put objects of the subclass into the global lists.

Research issues. The following are changes to the design that could be made if experiments indicated they were worthwhile:

Version:
$Id: IncidenceListGraph.java,v 1.24 2001/03/21 17:16:23 lv Exp $
Author:
Benoit Hudson, Mark Handy
See Also:
Graph, Vertex, Edge, EdgeDirection

Inner classes inherited from class jdsl.graph.ref.AbstractGraph
AbstractGraph.OO_to_O_MergerIterator
 
Fields inherited from interface jdsl.graph.api.EdgeDirection
IN, OUT, UNDIR
 
Constructor Summary
IncidenceListGraph()
          Creates a new IncidenceListGraph with default parameters.
 
Method Summary
 Edge anEdge()
          O(1)
 Edge anIncidentEdge(Vertex v)
          O(1)
 Edge anIncidentEdge(Vertex v, int edgetype)
          O(degree)
 boolean areIncident(Vertex v, Edge e)
          O(1)
 Edge attachVertex(Vertex v, java.lang.Object vertexInfo, java.lang.Object edgeInfo)
          O(1)
 Edge attachVertexFrom(Vertex v, java.lang.Object vertexInfo, java.lang.Object edgeInfo)
          O(1)
 Edge attachVertexTo(Vertex v, java.lang.Object vertexInfo, java.lang.Object edgeInfo)
          O(1)
 Vertex aVertex()
          O(1)
 boolean contains(Accessor p)
          O(1)
 int degree(Vertex v)
          O(1)
 int degree(Vertex v, int edgetype)
          O(degree)
 Vertex destination(Edge e)
          O(1)
 EdgeIterator edges()
          O(E)
 ObjectIterator elements()
          O(V+E)
 Vertex[] endVertices(Edge e)
          O(1)
 EdgeIterator incidentEdges(Vertex v)
          O(degree)
 EdgeIterator incidentEdges(Vertex v, int edgetype)
          O(degree)
 Edge insertDirectedEdge(Vertex v1, Vertex v2, java.lang.Object elt)
          O(1)
 Edge insertEdge(Vertex v1, Vertex v2, java.lang.Object elt)
          O(1)
 Vertex insertVertex(java.lang.Object elt)
          O(1)
 boolean isDirected(Edge e)
          O(1)
 void makeUndirected(Edge e)
          O(1)
 Container newContainer()
          O(1)
 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 removeEdge(Edge e)
          O(1)
 java.lang.Object removeVertex(Vertex v)
          O(degree)
 java.lang.Object replaceElement(Accessor p, java.lang.Object newElement)
          O(1)
 void reverseDirection(Edge e)
          O(1)
 void setDirectionFrom(Edge e, Vertex v)
          O(1)
 void setDirectionTo(Edge e, Vertex v)
          O(1)
 Vertex splitEdge(Edge e, java.lang.Object elt)
          O(1)
 java.lang.String toString()
           
 Edge unsplitEdge(Vertex v, java.lang.Object o)
          Note: the "two" edges incident on v cannot be the same edge.
 VertexIterator vertices()
          O(V)
 
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, wait, wait, wait
 
Methods inherited from interface jdsl.graph.api.InspectableGraph
aCommonVertex, aConnectingEdge, adjacentVertices, adjacentVertices, areAdjacent, areAdjacent, connectingEdges, directedEdges, undirectedEdges
 
Methods inherited from interface jdsl.core.api.InspectablePositionalContainer
positions
 
Methods inherited from interface jdsl.core.api.InspectableContainer
isEmpty, size
 
Methods inherited from interface jdsl.core.api.PositionalContainer
swapElements
 

Constructor Detail

IncidenceListGraph

public IncidenceListGraph()
Creates a new IncidenceListGraph with default parameters.

O(1)

Method Detail

newContainer

public Container newContainer()
O(1)
Specified by:
newContainer in interface Container
Following copied from interface: jdsl.core.api.Container
Returns:
A new, empty Container of the same class as this one.

replaceElement

public java.lang.Object replaceElement(Accessor p,
                                       java.lang.Object newElement)
O(1)
Specified by:
replaceElement in interface Container
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

contains

public boolean contains(Accessor p)
O(1)
Specified by:
contains in interface InspectableContainer
Following copied from interface: jdsl.core.api.InspectableContainer
Throws:
InvalidAccessorException - if a is null

elements

public ObjectIterator elements()
O(V+E)
Specified by:
elements in interface InspectableContainer
Following copied from interface: jdsl.core.api.InspectableContainer
Returns:
an iterator over all the elements stored in this container

numVertices

public int numVertices()
O(1)
Specified by:
numVertices in interface InspectableGraph
Following copied from interface: jdsl.graph.api.InspectableGraph
Returns:
the number of vertices

numEdges

public int numEdges()
O(1)
Specified by:
numEdges in interface InspectableGraph
Following copied from interface: jdsl.graph.api.InspectableGraph
Returns:
the number of edges

vertices

public VertexIterator vertices()
O(V)
Specified by:
vertices in interface InspectableGraph
Following copied from interface: jdsl.graph.api.InspectableGraph
Returns:
an iterator over all vertices in the graph

aVertex

public Vertex aVertex()
O(1)
Specified by:
aVertex in interface InspectableGraph
Following copied from interface: jdsl.graph.api.InspectableGraph
Returns:
an arbitrary vertex, or Vertex.NONE if the graph is empty

edges

public EdgeIterator edges()
O(E)
Specified by:
edges in interface InspectableGraph
Following copied from interface: jdsl.graph.api.InspectableGraph
Returns:
an iterator over all edges in the graph

anEdge

public Edge anEdge()
O(1)
Specified by:
anEdge in interface InspectableGraph
Following copied from interface: jdsl.graph.api.InspectableGraph
Returns:
an arbitrary edge, or Edge.NONE if the graph has no edges

degree

public int degree(Vertex v)
           throws InvalidAccessorException
O(1)
Specified by:
degree in interface InspectableGraph
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)
           throws InvalidAccessorException
O(degree)
Specified by:
degree in interface InspectableGraph
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

incidentEdges

public EdgeIterator incidentEdges(Vertex v)
                           throws InvalidAccessorException
O(degree)
Specified by:
incidentEdges in interface InspectableGraph
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)
                           throws InvalidAccessorException
O(degree)
Specified by:
incidentEdges in interface InspectableGraph
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

anIncidentEdge

public Edge anIncidentEdge(Vertex v)
                    throws InvalidAccessorException
O(1)
Specified by:
anIncidentEdge in interface InspectableGraph
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)
                    throws InvalidAccessorException
O(degree)
Specified by:
anIncidentEdge in interface InspectableGraph
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

endVertices

public Vertex[] endVertices(Edge e)
O(1)
Specified by:
endVertices in interface InspectableGraph
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

areIncident

public boolean areIncident(Vertex v,
                           Edge e)
O(1)
Specified by:
areIncident in interface InspectableGraph
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

opposite

public Vertex opposite(Vertex v,
                       Edge e)
O(1)
Specified by:
opposite in interface InspectableGraph
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)
Specified by:
origin in interface InspectableGraph
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)
Specified by:
destination in interface InspectableGraph
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

insertVertex

public Vertex insertVertex(java.lang.Object elt)
O(1)
Specified by:
insertVertex in interface Graph
Following copied from interface: jdsl.graph.api.Graph
Parameters:
element - the object to be stored in the new vertex
Returns:
the new vertex

removeVertex

public java.lang.Object removeVertex(Vertex v)
                              throws InvalidAccessorException
O(degree)
Specified by:
removeVertex in interface Graph
Following copied from interface: jdsl.graph.api.Graph
Parameters:
v - the vertex to be deleted
Returns:
the element stored at v
Throws:
InvalidAccessorException - if the vertex does not belong to this graph

attachVertex

public Edge attachVertex(Vertex v,
                         java.lang.Object vertexInfo,
                         java.lang.Object edgeInfo)
                  throws InvalidAccessorException
O(1)
Specified by:
attachVertex in interface Graph
Following copied from interface: jdsl.graph.api.Graph
Parameters:
v - a vertex
vertexElement - the object to be stored in v
edgeElement - the object to be stored in the new edge
Returns:
the new edge e; to get the new vertex, use method opposite(v,e)
Throws:
InvalidAccessorException - if vertex to be attached to does not belong to this graph

attachVertexFrom

public Edge attachVertexFrom(Vertex v,
                             java.lang.Object vertexInfo,
                             java.lang.Object edgeInfo)
                      throws InvalidAccessorException
O(1)
Specified by:
attachVertexFrom in interface Graph
Following copied from interface: jdsl.graph.api.Graph
Parameters:
origin - a vertex
vertexElement - the object to be stored in v
edgeElement - the object to be stored in the new edge
Returns:
the new edge e; to get the new vertex, use method opposite(v,e)
Throws:
InvalidAccessorException - if origin does not belong to this graph

attachVertexTo

public Edge attachVertexTo(Vertex v,
                           java.lang.Object vertexInfo,
                           java.lang.Object edgeInfo)
                    throws InvalidAccessorException
O(1)
Specified by:
attachVertexTo in interface Graph
Following copied from interface: jdsl.graph.api.Graph
Parameters:
destination - a vertex
vertexElement - the object to be stored in v
edgeElement - the object to be stored in the new edge
Returns:
the new edge e; to get the new vertex, use method opposite(v,e)
Throws:
InvalidAccessorException - if destination does not belong to this graph

insertEdge

public Edge insertEdge(Vertex v1,
                       Vertex v2,
                       java.lang.Object elt)
                throws InvalidAccessorException
O(1)
Specified by:
insertEdge in interface Graph
Following copied from interface: jdsl.graph.api.Graph
Parameters:
v1 - the first endvertex
v2 - the second endvertex
element - the object to be stored in the new edge
Returns:
the new edge
Throws:
InvalidAccessorException - if either v1 or v2 does not belong to this graph

insertDirectedEdge

public Edge insertDirectedEdge(Vertex v1,
                               Vertex v2,
                               java.lang.Object elt)
                        throws InvalidAccessorException
O(1)
Specified by:
insertDirectedEdge in interface Graph
Following copied from interface: jdsl.graph.api.Graph
Parameters:
v1 - the origin vertex
v2 - the destination vertex
element - the object to be stored in the new edge
Returns:
the new edge
Throws:
InvalidAccessorException - if either v1 or v2 does not belong to this graph

removeEdge

public java.lang.Object removeEdge(Edge e)
                            throws InvalidAccessorException
O(1)
Specified by:
removeEdge in interface Graph
Following copied from interface: jdsl.graph.api.Graph
Parameters:
e - the edge to be removed
Returns:
the element formerly stored at e
Throws:
InvalidAccessorException - if the edge does not belong to this graph

splitEdge

public Vertex splitEdge(Edge e,
                        java.lang.Object elt)
                 throws InvalidAccessorException
O(1)
Specified by:
splitEdge in interface ModifiableGraph
Following copied from interface: jdsl.graph.api.ModifiableGraph
Parameters:
e - the edge to be split
vertElement - the object to be stored in v
Returns:
the new vertex w; to get the new edges, use method incidentEdges(w)
Throws:
InvalidAccessorException - if the edge does not belong to this graph

unsplitEdge

public Edge unsplitEdge(Vertex v,
                        java.lang.Object o)
                 throws InvalidAccessorException,
                        InvalidVertexException
Note: the "two" edges incident on v cannot be the same edge. That is, v is technically of degree 2 if it has a single self-loop and is otherwise isolated, but it is impossible to unsplit that edge-vertex-edge combination, so we throw IVE in that case.

O(1)

Specified by:
unsplitEdge in interface ModifiableGraph
Following copied from interface: jdsl.graph.api.ModifiableGraph
Parameters:
v - the vertex to be removed
edgeElement - the element to be stored in the new edge
Returns:
the new edge
Throws:
InvalidVertexException - If the vertex is not of degree 2 or is of degree 2 but the "two" edges are a single self-loop
InvalidAccessorException - if the vertex does not belong to this graph

isDirected

public boolean isDirected(Edge e)
O(1)
Specified by:
isDirected in interface InspectableGraph
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

setDirectionFrom

public void setDirectionFrom(Edge e,
                             Vertex v)
O(1)
Specified by:
setDirectionFrom in interface ModifiableGraph
Following copied from interface: jdsl.graph.api.ModifiableGraph
Parameters:
e - an edge
v - an endvertex of e
Throws:
InvalidVertexException - if v is not an endvertex of e but both v and e belong to this graph
InvalidAccessorException - if either e or v does not belong to this graph

setDirectionTo

public void setDirectionTo(Edge e,
                           Vertex v)
O(1)
Specified by:
setDirectionTo in interface ModifiableGraph
Following copied from interface: jdsl.graph.api.ModifiableGraph
Parameters:
e - an edge
v - an endvertex of e
Throws:
InvalidVertexException - if v is not an endvertex of e
InvalidAccessorException - if either e or v does not belong to this graph

makeUndirected

public void makeUndirected(Edge e)
O(1)
Specified by:
makeUndirected in interface ModifiableGraph
Following copied from interface: jdsl.graph.api.ModifiableGraph
Parameters:
e - an edge
Throws:
InvalidAccessorException - if the edge does not belong to this graph

reverseDirection

public void reverseDirection(Edge e)
O(1)
Specified by:
reverseDirection in interface ModifiableGraph
Following copied from interface: jdsl.graph.api.ModifiableGraph
Parameters:
e - an edge
Throws:
InvalidEdgeException - If the edge is undirected
InvalidAccessorException - if the edge does not belong to this graph

toString

public java.lang.String toString()
Overrides:
toString in class java.lang.Object