ca.ualberta.cs.poker.free.server
Class DirectedGraph

java.lang.Object
  extended by ca.ualberta.cs.poker.free.server.DirectedGraph
All Implemented Interfaces:
java.lang.Cloneable
Direct Known Subclasses:
UndirectedGraph

public class DirectedGraph
extends java.lang.Object
implements java.lang.Cloneable

DirectedGraph represents a directed graph. A DirectedGraph may contain zero or more DirectedNodes. A DirectedGraph may be named. DirectedGraph uses a LinkedHashMap to store references to the DirectedNodes that are members of a DirectedGraph. DirectedGraph has a NodeIDGenerator member to assign unique node id's to DirectedNodes that are added to a DirectedGraph.


Field Summary
protected  java.lang.String name
           
protected  java.util.LinkedHashMap nodes
           
 
Constructor Summary
DirectedGraph()
          Creates an empty DirectedGraph.
 
Method Summary
 void addEdge(Node source, Node dest)
          Adds a directed edge from the source Node to the dest Directed Node
 void addEdge(Node source, Node dest, java.lang.Double weight)
           
 void addNode(Node n)
          Adds the provided Node to this DirectedGraph
 java.lang.Object clone()
           
protected  void dfsVisit(Node u, int[] color, int[] pi, java.util.ArrayList ret)
           
 boolean existsEdge(int source_id, int dest_id)
          Determines if a directed edge exists from the source Node to this destination Node
 boolean existsEdge(Node source, Node dest)
          Determines if a directed edge exists from the source Node to this destination Node
 java.lang.String getName()
          getName returns the name of the DirectedGraph
 Node getNode(int id)
          getDirectedNode returns the Node from the DirectedGraph with the specified id.
 Node getRootNode()
           
 java.util.List getRootNodes()
          Returns a List containing all the root nodes (i.e.
 java.util.Iterator keyIterator()
           
 java.util.Iterator nodeIterator()
           
 void removeEdge(Node source, Node dest)
          Removes the directed edge between the source Node and the destination Node
 void removeNode(Node n)
          Removes the specified Node and it's associated edges from this DirectedGraph.
 void setName(java.lang.String string)
          setName sets the name of the DirectedGraph to the specifed String value
 int size()
          size returns the number of DirectedNodes in the DirectedGraph
 java.util.List topologicalSort()
          Does topological sort in the DirectedGraph
 java.lang.String toString()
           
 
Methods inherited from class java.lang.Object
equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

name

protected java.lang.String name

nodes

protected java.util.LinkedHashMap nodes
Constructor Detail

DirectedGraph

public DirectedGraph()
Creates an empty DirectedGraph. The graph's storage and NodeIDGenerator are initialized.

Method Detail

clone

public java.lang.Object clone()
Overrides:
clone in class java.lang.Object

addEdge

public void addEdge(Node source,
                    Node dest)
Adds a directed edge from the source Node to the dest Directed Node

Parameters:
source -
dest -

addEdge

public void addEdge(Node source,
                    Node dest,
                    java.lang.Double weight)

getRootNodes

public java.util.List getRootNodes()
Returns a List containing all the root nodes (i.e. DirectedNodes with out parents) from this DirectedGraph.

Returns:
aList of the DirectedNodes from this DirectedGraph which are root nodes

getRootNode

public Node getRootNode()

removeNode

public void removeNode(Node n)
Removes the specified Node and it's associated edges from this DirectedGraph.

Parameters:
n - the Node to be removed.

removeEdge

public void removeEdge(Node source,
                       Node dest)
Removes the directed edge between the source Node and the destination Node

Parameters:
source -
dest -

existsEdge

public boolean existsEdge(Node source,
                          Node dest)
Determines if a directed edge exists from the source Node to this destination Node

Parameters:
source -
dest -
Returns:
true if a directed edge exists between the source Node and the dest Node, returns false otherwise

existsEdge

public boolean existsEdge(int source_id,
                          int dest_id)
Determines if a directed edge exists from the source Node to this destination Node

Parameters:
source_id - the id of the source Node
dest_id - the id of the destination Node
Returns:
true if a directed edge exists between the source Node and the dest Node, returns false otherwise

addNode

public void addNode(Node n)
Adds the provided Node to this DirectedGraph

Parameters:
n - the Node to be added

toString

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

dfsVisit

protected void dfsVisit(Node u,
                        int[] color,
                        int[] pi,
                        java.util.ArrayList ret)

nodeIterator

public java.util.Iterator nodeIterator()

keyIterator

public java.util.Iterator keyIterator()

topologicalSort

public java.util.List topologicalSort()
Does topological sort in the DirectedGraph

Returns:
a List of the DirectedNodes of this DirectedGraph in topological sort order

getNode

public Node getNode(int id)
getDirectedNode returns the Node from the DirectedGraph with the specified id.

Parameters:
id - the unique id of the Node to be returned
Returns:
the Node with the specified id

size

public int size()
size returns the number of DirectedNodes in the DirectedGraph

Returns:
the size (number of nodes) of the DirectedGraph

getName

public java.lang.String getName()
getName returns the name of the DirectedGraph

Returns:
the name of the DirectedGraph

setName

public void setName(java.lang.String string)
setName sets the name of the DirectedGraph to the specifed String value

Parameters:
string - the name that the DirectedGraph is to be given