org.amino.ds.graph
Class AbstractGraph<E>

java.lang.Object
  extended by org.amino.ds.graph.AbstractGraph<E>
Type Parameters:
E - Type of elements in the graph
All Implemented Interfaces:
java.lang.Cloneable, java.lang.Iterable<E>, java.util.Collection<E>, Graph<E>
Direct Known Subclasses:
DirectedGraphImpl, UndirectedGraph

public abstract class AbstractGraph<E>
extends java.lang.Object
implements Graph<E>

Default implementation of Graph interface. This graph doesn't allow duplicated key for all nodes. The constrain comes from internal structure contains a ConcurrentHashMap which uses indexed by key.

Author:
Zhi Gan

Constructor Summary
AbstractGraph()
          Default constructor.
 
Method Summary
 boolean add(E o)
          
 boolean addAll(java.util.Collection<? extends E> c)
          
 boolean addAllNodes(java.util.Collection<Node<E>> nodes)
          add all the nodes to graph.
 Node<E> addNode(E e)
          Add a node to graph, which contains value e.
 Node<E> addNode(Node<E> node)
          Add a node to graph, which contains value e.
 void clear()
          
abstract  Graph<E> clone()
          Clone this graph.
 boolean contains(java.lang.Object o)
          
 boolean containsAll(java.util.Collection<?> c)
          
 boolean containsEdge(E start, E end)
          Returns whether this graph contains an edge between start and end.
 boolean containsNode(Node<E> node)
          Judge if node is contained in graph.
 void dumpGraph()
          for testing.
protected  boolean freeMultiOwnerShip(AdjacentList<E>[] targets)
          release all ownership of every element in targets.
 java.util.Collection<Node<E>> getAllNodes()
          get all the nodes in the graph.
 java.util.Collection<Edge<E>> getEdges(E start, E end)
          get all the edge start from the nodes which contain value start and end.
 java.util.Collection<Edge<E>> getEdges(Node<E> start, Node<E> end)
          get all all the edges which start from node start and end with node end.
 java.util.Collection<Edge<E>> getLinkedEdges(Node<E> node)
          get all edges directly linked to the specified node.
 java.util.Collection<AdjacentNode<E>> getLinkedNodes(Node<E> node)
          get all nodes which directly linked to node.
protected  boolean getMultiOwnerShip(AdjacentList<E>[] targets)
          Get all ownership of multiple AdjacentList.
 java.util.Collection<Node<E>> getNodes(E e)
          get all nodes whose value equal to e.
 boolean isEmpty()
          
 java.util.Iterator<E> iterator()
          
 boolean remove(java.lang.Object o)
          
 boolean removeAll(java.util.Collection<?> c)
          
 boolean removeNode(Node<E> node)
          remove the node from the graph.
 boolean retainAll(java.util.Collection<?> c)
          
protected  boolean simpleContentionManager(AdjacentList<E> targets)
          manage contention of multithreads in the rush for ownership.
protected  boolean simpleContentionManager(AdjacentList<E>[] targets)
          manage contention of multi-threads in the rush for ownership.
 int size()
          
 java.lang.Object[] toArray()
          
<E> E[]
toArray(E[] a)
          
 
Methods inherited from class java.lang.Object
equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 
Methods inherited from interface org.amino.ds.graph.Graph
addEdge, addEdge, addEdge, removeEdge, removeEdge, removeEdge
 
Methods inherited from interface java.util.Collection
equals, hashCode
 

Constructor Detail

AbstractGraph

public AbstractGraph()
Default constructor.

Method Detail

getMultiOwnerShip

protected boolean getMultiOwnerShip(AdjacentList<E>[] targets)
Get all ownership of multiple AdjacentList.

Parameters:
targets - Collection of elements need ownership
Returns:
true if the operation is successful

freeMultiOwnerShip

protected boolean freeMultiOwnerShip(AdjacentList<E>[] targets)
release all ownership of every element in targets.

Parameters:
targets - Collection of elements whose ownership is released
Returns:
true if operation is successful

simpleContentionManager

protected boolean simpleContentionManager(AdjacentList<E>[] targets)
manage contention of multi-threads in the rush for ownership. When contention occurred, this method will release all owned locks and return false.

Parameters:
targets - Array of elements whose ownership need to be got
Returns:
true if get all ownership of elements in the array

simpleContentionManager

protected boolean simpleContentionManager(AdjacentList<E> targets)
manage contention of multithreads in the rush for ownership. Policy is aborting itself

Parameters:
targets - element whose ownership need to be got
Returns:
true if get ownership of element

addNode

public Node<E> addNode(E e)
Add a node to graph, which contains value e. If the tree already contains e, return the existing node instead of creating a new one.
FIXME: This method doesn't tell if a node is created or not. We need to add an boolean addIfAbsent(E e) method?

Specified by:
addNode in interface Graph<E>
Parameters:
e - the value to add.
Returns:
a node in graph which contains the value

addNode

public Node<E> addNode(Node<E> node)
Add a node to graph, which contains value e. If the tree already contains e, return the existing node instead of creating a new one.

Specified by:
addNode in interface Graph<E>
Parameters:
node - the node to add
Returns:
return adding node if succeed. If there is already a graph node has the same value as node, return node in graph.

addAllNodes

public boolean addAllNodes(java.util.Collection<Node<E>> nodes)
add all the nodes to graph.

Specified by:
addAllNodes in interface Graph<E>
Parameters:
nodes - nodes to be added
Returns:
true if the operation is successful

containsEdge

public boolean containsEdge(E start,
                            E end)
Returns whether this graph contains an edge between start and end.

Specified by:
containsEdge in interface Graph<E>
Parameters:
start - starting node of edge
end - ending node of edge
Returns:
true if this graph contains edge between start and end, false otherwise.

getLinkedNodes

public java.util.Collection<AdjacentNode<E>> getLinkedNodes(Node<E> node)
get all nodes which directly linked to node.

Specified by:
getLinkedNodes in interface Graph<E>
Parameters:
node - start node
Returns:
collection of all linked nodes

getLinkedEdges

public java.util.Collection<Edge<E>> getLinkedEdges(Node<E> node)
get all edges directly linked to the specified node.

Specified by:
getLinkedEdges in interface Graph<E>
Parameters:
node - start node
Returns:
collection of all linked edges

addAll

public boolean addAll(java.util.Collection<? extends E> c)

Specified by:
addAll in interface java.util.Collection<E>

clear

public void clear()

Specified by:
clear in interface java.util.Collection<E>

contains

public boolean contains(java.lang.Object o)

Specified by:
contains in interface java.util.Collection<E>

containsNode

public boolean containsNode(Node<E> node)
Judge if node is contained in graph.

Specified by:
containsNode in interface Graph<E>
Parameters:
node - target node
Returns:
true if node is contained in mainList

containsAll

public boolean containsAll(java.util.Collection<?> c)

Specified by:
containsAll in interface java.util.Collection<E>

isEmpty

public boolean isEmpty()

Specified by:
isEmpty in interface java.util.Collection<E>

iterator

public java.util.Iterator<E> iterator()

Specified by:
iterator in interface java.lang.Iterable<E>
Specified by:
iterator in interface java.util.Collection<E>

removeAll

public boolean removeAll(java.util.Collection<?> c)

Specified by:
removeAll in interface java.util.Collection<E>

retainAll

public boolean retainAll(java.util.Collection<?> c)

Specified by:
retainAll in interface java.util.Collection<E>

size

public int size()

Specified by:
size in interface java.util.Collection<E>

toArray

public java.lang.Object[] toArray()

Specified by:
toArray in interface java.util.Collection<E>

toArray

public <E> E[] toArray(E[] a)

Specified by:
toArray in interface java.util.Collection<E>

add

public boolean add(E o)

Specified by:
add in interface java.util.Collection<E>

remove

public boolean remove(java.lang.Object o)

Specified by:
remove in interface java.util.Collection<E>

removeNode

public boolean removeNode(Node<E> node)
remove the node from the graph.

Specified by:
removeNode in interface Graph<E>
Parameters:
node - node removed
Returns:
true if the operation is successful

getAllNodes

public java.util.Collection<Node<E>> getAllNodes()
get all the nodes in the graph.

Specified by:
getAllNodes in interface Graph<E>
Returns:
a collection of all the nodes in the graph

getEdges

public java.util.Collection<Edge<E>> getEdges(E start,
                                              E end)
get all the edge start from the nodes which contain value start and end. to nodes which contain value end

Specified by:
getEdges in interface Graph<E>
Parameters:
start - start value
end - end value
Returns:
collection of all the edge start from the nodes which contain value start and end to nodes which contain value end

getEdges

public java.util.Collection<Edge<E>> getEdges(Node<E> start,
                                              Node<E> end)
get all all the edges which start from node start and end with node end.

Specified by:
getEdges in interface Graph<E>
Parameters:
start - the start node of the edge
end - the end node of the edge
Returns:
collection of all the edges which start from node start and end with node end

getNodes

public java.util.Collection<Node<E>> getNodes(E e)
get all nodes whose value equal to e.

Specified by:
getNodes in interface Graph<E>
Parameters:
e - value to be got
Returns:
a collection of nodes

dumpGraph

public void dumpGraph()
for testing.


clone

public abstract Graph<E> clone()
                        throws java.lang.CloneNotSupportedException
Clone this graph.

Specified by:
clone in interface Graph<E>
Overrides:
clone in class java.lang.Object
Returns:
a graph
Throws:
java.lang.CloneNotSupportedException - clone not supported


Copyright © 2008. All Rights Reserved.