DefaultGraph

Overview

Package

Class

Use

Deprecated

Index

Home >> All >> com >> phoenixst >> [ plexus overview ]

PREV CLASS NEXT CLASS

SUMMARY:

JAVADOC |

Sourc code of com.phoenixst.plexus.DefaultGraph

SOURCE |

Download com.phoenixst.plexus.DefaultGraph

DOWNLOAD | NESTED | FIELD | CONSTR | METHOD

DETAIL: FIELD | CONSTR | METHOD

com.phoenixst.plexus
Class DefaultGraph

java.lang.Object
  com.phoenixst.plexus.DefaultGraph

All Implemented Interfaces:: Graph, ObservableGraph, java.io.Serializable

public class DefaultGraph
extends java.lang.Object
implements ObservableGraph, java.io.Serializable

A default implementation of the ObservableGraph interface.

Design Criteria

There are many ways of representing graphs in software, and this package uses just one of those for the general implementation. Of the two most basic, adjacency list and adjacency matrix, adjacency list is the most efficient for even remotely sparse graphs. Also, the design constraint that nodes and edges are user-provided objects would have made an adjacency matrix representation much more costly in terms of space (a HashMap would be required to map nodes to indices).

In general, it seems preferable to implement a graph as a HashMap from nodes to their adjacency lists. The alternative (using some non-O(1) access Collection) is just too prohibitive in time for the modest gains in space. There are a few different options for distinguishing out-edges from in-edges in a directed graph:

Directed Graph Implementation Options

A directed graph is two maps, one for out-adjacency lists and one for in adjacency lists.
A directed graph is one map, mapping each node to a Pair of adjacency lists.
A directed graph is one map, mapping each node to a single adjacency list which knows how to distinguish out-edges from in-edges.

For a graph with N nodes, we have the following object counts:

Option HashMap Map.Entry Pair AdjList
#1 2 2N 0 2N
#2 1 N N 2N
#3 1 N 0 N

Option	HashMap	Map.Entry	Pair	AdjList
#1	2	2N	0	2N
#2	1	N	N	2N
#3	1	N	0	N

Given that a Pair is smaller than a Map.Entry, and that #2 requires one lookup per node whereas #1 requires two, we can seee that #2 is clearly better than #1. It even more obvious that #3 is better than #2, but only if the adjacency list implementation allows this. The only tradeoff is that the adjacency lists will be twice as large on average, and so will take longer to traverse. This will normally be much less of an issue than the garbage collection overhead caused by having 2N more objects.

Now, how to represent an adjacency list? All an adjacency list needs to do is associate adjacent nodes with the edges that go to them. I examined 5 different ways of doing this, and considered how time and space efficient each would be when used for the 4 different default graph implementations( Directed vs. Undirected, Simple vs. Multi):

Adjacency List Implementation Options

Map adjacent node -> edge. (Simple only)
Map adjacent node -> Collection of edges. (Multi only)
Collection of ( Pair ( adjacent node, Collection of edges ) ). (Multi only)
Collection of ( Pair ( adjacent node, edge ) ).
Collection of ( Triple( tail node, head node, edge ) ).

For this application, an ArrayList is probably the best Collection implementation since it doesn't allocate an extra object for each thing in it (unlike LinkedList and HashMap). For a graph with N nodes, E edges, and A adjacent nodes, we have the following object counts:

Option HashMap Map.Entry List Pair Triple Digraph Option# Notes
#1 N+1/2N+1 N+2E 0 0/N 0 #2 Simple only
#2 N+1/2N+1 N+2A A 0/N 0 #2 Multi only
#3 1 N N+A/2N+A 2A/N+2A 0 #2 Multi only
#4 1 N N/2N 2E/N+2E 0 #2
#5 1 N N/N 0 E #3
Notes:

Option	HashMap	Map.Entry	List	Pair	Triple	Digraph Option#	Notes
#1	N+1/2N+1	N+2E	0	0/N	0	#2	Simple only
#2	N+1/2N+1	N+2A	A	0/N	0	#2	Multi only
#3	1	N	N+A/2N+A	2A/N+2A	0	#2	Multi only
#4	1	N	N/2N	2E/N+2E	0	#2
#5	1	N	N/N	0	E	#3

For dual entries, the number before the slash is for undirected graphs, the number after is for directed graphs (an undirected graph has one adjacency list per node, a directed graph has one or two depending upon Digraph option #3).
A <= E, and, normally, N < A.

The comparisons aren't even really close, especially considering that option #5 allows for the same adjacency list representation for both simple and multi-graphs. And, it just so happens to be the same for both directed and undirected graphs; only how the Triples are interpreted changes.

Since:: 1.0
Version:: $Revision: 1.35 $

Nested Class Summary

private class DefaultGraph.AdjacencyList
          An adjacency list implementation.

private class DefaultGraph.AllEdgesIteratorImpl
          Private implementation class for edgeIterator().

private static class DefaultGraph.CursorReaper
          A thread which reaps cursors from ALL DefaultGraph instances.

private class DefaultGraph.CursorReference
          Basically, a WeakReference for a Cursor that knows which graph created it.

private class DefaultGraph.EdgeIteratorImpl
          Support implementation class for use by edgeIterator( tail, head ).

private class DefaultGraph.NodeIterator
          Private node iterator implementation.

private class DefaultGraph.TraverserImpl
          Support implementation class used by both directed and undirected standard traverser methods.

Nested classes inherited from class com.phoenixst.plexus.Graph

Graph.Edge

Field Summary

private java.util.List backupCursors
          The backup list of currently iterating cursors.

private java.util.List cursors
          The list of currently iterating cursors.

private int edgeSize
          The number of edges in this graph.

private boolean isDirected
          Whether or not this Graph is directed.

private boolean isSimple
          Whether or not this Graph is simple.

private GraphListener[] listenerArray
          An array copy of the listener list, if it hasn't changed.

private java.util.List listeners
          The list of GraphListeners.

private java.util.Map nodeMap
          Map from nodes to adjacency lists.

private java.lang.Object syncObject
          The object to sync upon when iterating over the cursors list, as which list that is can change.

Constructor Summary

DefaultGraph()
          Creates a new directed, multi DefaultGraph.

DefaultGraph(boolean isDirected, boolean isSimple)
          Creates a new DefaultGraph.

DefaultGraph(boolean isDirected, boolean isSimple, Graph g)
          Creates a new DefaultGraph which is a copy of the specified Graph.

private DefaultGraph(boolean isDirected, boolean isSimple, int nodeSize)
          Creates a new DefaultGraph with space for the specified number of nodes.

DefaultGraph(Graph g)
          Creates a new DefaultGraph which is a copy of the specified Graph.

Method Summary

Graph.Edge addEdge(java.lang.Object object, java.lang.Object tail, java.lang.Object head)
          Adds the specified edge to the Graph (optional operation).

void addGraphListener(GraphListener listener)
          Adds the specified GraphListener which will be notified whenever this ObservableGraph's structure changes.

boolean addNode(java.lang.Object node)
          Adds node to this Graph (optional operation).

private void alertEdgeAdded(DefaultGraph.AdjacencyList adj)
          Invoked when an edge has been added to alert any listening Cursors.

private void alertEdgeRemoved(DefaultGraph.AdjacencyList adj, int index)
          Invoked when an edge has been removed to alert any listening Cursors.

private DefaultGraph.AdjacencyList checkNode(java.lang.Object node)
          Checks to see whether node is in this Graph.

void clear()
          Removes all nodes and edges from this Graph (optional operation).

boolean containsEdge(Graph.Edge edge)
          Returns true if this Graph contains the specified Edge.

boolean containsNode(java.lang.Object node)
          Returns true if this Graph contains the specified node.

private GraphListener[] createListenerArray()
          Returns the array copy of the listener list, creating it if it has changed.

private java.lang.String debugToString()
          A debugging toString method, showing the internal data structures.

int degree(java.lang.Object node)
          Returns the degree of node, defined as the number of edges incident on node, with self-loops counted twice.

protected void edgeAdded(Graph.Edge edge)
          Invoked after an edge has been added to this Graph.

java.util.Iterator edgeIterator()
          Returns an Iterator over all the Edges in this Graph.

java.util.Iterator edgeIterator(java.lang.Object tail, java.lang.Object head)
          Returns an Iterator over all Edges from this Graph with the specified tail and head.

protected void edgeRemoved(Graph.Edge edge)
          Invoked after an edge has been removed from this Graph.

int edgeSize()
          Returns the number of edges in this Graph.

private void fireEdgeAdded(Graph.Edge edge)
          Sends edge added event to registered listeners.

private void fireEdgeRemoved(Graph.Edge edge)
          Sends edge removed event to registered listeners.

private void fireNodeAdded(java.lang.Object node)
          Sends node added event to registered listeners.

private void fireNodeRemoved(java.lang.Object node)
          Sends node removed event to registered listeners.

Graph.Edge getEdge(java.lang.Object tail, java.lang.Object head)
          Returns an Edge from this Graph with the specified tail and head, or null if it does not exist.

int inDegree(java.lang.Object node)
          If this is a directed graph, returns the in degree of node, defined as the number of edges entering node.

Traverser inTraverser(java.lang.Object node)
          Returns a Traverser from node to all adjacent nodes reachable through edges whose head is the given node.

boolean isDirected()
          Returns whether or not this Graph is directed.

boolean isEmpty()
          Returns true if this Graph contains no edges, it may contain nodes.

boolean isSimple()
          Returns whether or not this Graph is simple.

protected void nodeAdded(java.lang.Object node)
          Invoked after a node has been added to this Graph.

java.util.Iterator nodeIterator()
          Returns an Iterator over all the nodes in this Graph.

protected void nodeRemoved(java.lang.Object node)
          Invoked after a node has been removed from this Graph.

int nodeSize()
          Returns the number of nodes in this Graph.

int outDegree(java.lang.Object node)
          If this is a directed graph, returns the out degree of node, defined as the number of edges leaving node.

Traverser outTraverser(java.lang.Object node)
          Returns a Traverser from node to all adjacent nodes reachable through edges whose tail is the given node.

private void processEdgeAdded(Graph.Edge edge)


private void processEdgeRemoved(Graph.Edge edge)


private void processNodeAdded(java.lang.Object node)


private void processNodeRemoved(java.lang.Object node)


private void readObject(java.io.ObjectInputStream in)


private void reapCursors()
          Removes all dead cursors.

boolean removeEdge(Graph.Edge edge)
          Removes the specified Edge from this Graph (optional operation).

void removeGraphListener(GraphListener listener)
          Removes a previously added GraphListener.

boolean removeNode(java.lang.Object node)
          Removes node from this Graph (optional operation).

java.lang.String toString()
          Convert this Object to a human-readable String.

Traverser traverser(java.lang.Object node)
          Returns a Traverser from node to all adjacent nodes.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

nodeMap

private java.util.Map nodeMap

Map from nodes to adjacency lists.

edgeSize

private int edgeSize

The number of edges in this graph.

isDirected

private boolean isDirected

Whether or not this Graph is directed.

isSimple

private boolean isSimple

Whether or not this Graph is simple.

listeners

private transient java.util.List listeners

The list of GraphListeners.

listenerArray

private transient GraphListener[] listenerArray

An array copy of the listener list, if it hasn't changed.

cursors

private transient java.util.List cursors

The list of currently iterating cursors.

backupCursors

private transient java.util.List backupCursors

The backup list of currently iterating cursors.

syncObject

private transient java.lang.Object syncObject

The object to sync upon when iterating over the cursors list, as which list that is can change.

Constructor Detail

DefaultGraph

private DefaultGraph(boolean isDirected,
                     boolean isSimple,
                     int nodeSize)

Creates a new DefaultGraph with space for the specified number of nodes.

DefaultGraph

public DefaultGraph()

Creates a new directed, multi DefaultGraph.

DefaultGraph

public DefaultGraph(boolean isDirected,
                    boolean isSimple)

Creates a new DefaultGraph.

DefaultGraph

public DefaultGraph(Graph g)

Creates a new DefaultGraph which is a copy of the specified Graph.

DefaultGraph

public DefaultGraph(boolean isDirected,
                    boolean isSimple,
                    Graph g)

Creates a new DefaultGraph which is a copy of the specified Graph. If this Graph and the specified Graph do not match in what sort of graph they are (one directed and the other undirected, e.g.), then a best effort is still made to copy the graph.

Method Detail

nodeAdded

protected void nodeAdded(java.lang.Object node)

Invoked after a node has been added to this Graph.

nodeRemoved

protected void nodeRemoved(java.lang.Object node)

Invoked after a node has been removed from this Graph.

edgeAdded

protected void edgeAdded(Graph.Edge edge)

Invoked after an edge has been added to this Graph.

edgeRemoved

protected void edgeRemoved(Graph.Edge edge)

Invoked after an edge has been removed from this Graph.

checkNode

private DefaultGraph.AdjacencyList checkNode(java.lang.Object node)

Checks to see whether node is in this Graph. If so, return the adjacency list for the node. If not, throw an NoSuchNodeException.

reapCursors

private void reapCursors()

Removes all dead cursors. This should only be called by the reaper thread.

alertEdgeAdded

private void alertEdgeAdded(DefaultGraph.AdjacencyList adj)

Invoked when an edge has been added to alert any listening Cursors.

alertEdgeRemoved

private void alertEdgeRemoved(DefaultGraph.AdjacencyList adj,
                              int index)

Invoked when an edge has been removed to alert any listening Cursors.

processNodeAdded

private void processNodeAdded(java.lang.Object node)

processNodeRemoved

private void processNodeRemoved(java.lang.Object node)

processEdgeAdded

private void processEdgeAdded(Graph.Edge edge)

processEdgeRemoved

private void processEdgeRemoved(Graph.Edge edge)

createListenerArray

private GraphListener[] createListenerArray()

Returns the array copy of the listener list, creating it if it has changed.

fireNodeAdded

private void fireNodeAdded(java.lang.Object node)

Sends node added event to registered listeners.

fireNodeRemoved

private void fireNodeRemoved(java.lang.Object node)

Sends node removed event to registered listeners.

fireEdgeAdded

private void fireEdgeAdded(Graph.Edge edge)

Sends edge added event to registered listeners.

fireEdgeRemoved

private void fireEdgeRemoved(Graph.Edge edge)

Sends edge removed event to registered listeners.

debugToString

private java.lang.String debugToString()

A debugging toString method, showing the internal data structures.