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

java.lang.Object
  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