IncidenceListGraph (Docs for JDSL 2.1.1)

Overview

Package

Class

Tree

Deprecated

Index

Help

PREV CLASS NEXT CLASS

FRAMES NO FRAMES

SUMMARY: NESTED | FIELD | CONSTR | METHOD

DETAIL: FIELD | CONSTR | METHOD

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:

Use caches and copy-on-write techniques in more methods that return iterators. However, many graph algorithms iterate over a given set only once, so caching the iteration might just waste time and space. It might also be difficult to determine when to invalidate a cache.
Use dictionaries to store some information, for example the adjacency lists, in order to have better running-time for adjacency queries -- for example, connectingEdges(V,V). This would improve asymptotic performance of adjacency queries at the expense of asymptotic penalties in modifications, and at the expense of constant-factor penalties everywhere.
Have vertices store 3 lists of edges, incoming, outgoing, and undirected, for faster iterations over categories of edges. However, this gives space overhead, and is faster only in the rare case of a graph with both directed and undirected edges.

Version:: JDSL 2.1.1
Author:: Benoit Hudson, Mark Handy
See Also:: Graph, Vertex, Edge, EdgeDirection

Nested Class Summary

Nested classes inherited from class jdsl.graph.ref.AbstractGraph

AbstractGraph.OO_to_O_MergerIterator

Field Summary

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, Object vertexInfo, Object edgeInfo)` O(1)
`Edge`	`attachVertexFrom(Vertex v, Object vertexInfo, Object edgeInfo)` O(1)
`Edge`	`attachVertexTo(Vertex v, Object vertexInfo, 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, Object elt)` O(1)
`Edge`	`insertEdge(Vertex v1, Vertex v2, Object elt)` O(1)
`Vertex`	`insertVertex(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)
`Object`	`removeEdge(Edge e)` O(1)
`Object`	`removeVertex(Vertex v)` O(degree)
`Object`	`replaceElement(Accessor p, 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, Object elt)` O(1)
`String`	`toString()`
`Edge`	`unsplitEdge(Vertex v, 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