uchicago.src.sim.topology.graph
Class DirectedGraph

java.lang.Object
  uchicago.src.sim.topology.graph.AbstractGraph
      uchicago.src.sim.topology.graph.DirectedGraph

All Implemented Interfaces:

Graph, ModifyableTopology, RelationTopology, java.io.Serializable

Direct Known Subclasses:

WeightedDirectedGraph

public class DirectedGraph

extends AbstractGraph

implements java.io.Serializable

This represents a DirectedGraph.

Version:

$Revision: 1.6 $

Author:

Tom Howe

See Also:

Serialized Form

Constructor Summary

DirectedGraph(java.util.Set s)
Construct a graph using the specified set of vertices.

DirectedGraph(java.util.Set s, java.lang.String type)
Construct a graph using the specified set of vertices and the type.

Method Summary

boolean	areAdjacent(java.lang.Object v, java.lang.Object v1, EdgeType type) Returns whether the two elements share an edge with the given directionality.
double	clusterCoeffient() Calculates the clustering coefficient for this graph.
int	degree(java.lang.Object v, EdgeType type) Returns the number of edges for the object with the given directionality.
double	distance(java.lang.Object element1, java.lang.Object element2) This returns the distance between two vertices in the graph.
boolean	equals(java.lang.Object oth)
java.util.List	getAdjacentNodes(java.lang.Object v, double distance, EdgeType type) Get a list of the vertices that are attached to the specified vertex of the given direction and within the given distance.
java.util.List	getAdjacentNodes(java.lang.Object v, EdgeType type) Get the Nodes that share an edge with the parameter with the proper directionality.
java.util.List	getEdges(java.lang.Object v, EdgeType type) Returns the edge objects of the given directionality for the object.
protected java.util.Set	getEdgeSet(java.lang.Object v, EdgeType e)
java.util.List	getInNodes(java.lang.Object v) Get all of the vertices that the given vertex has an in edge from.
java.util.Set	getNodes()
java.util.List	getOutNodes(java.lang.Object v) Get all of the vertices that the given vertex has an out edge to.
int	hashCode()
void	insertEdge(Edge e) Insert an edge that has already been created.
void	insertEdge(java.lang.Object e, java.lang.Object e1, double strength) Insert a new edge into the graph.
boolean	isAcyclic() Determines if the graph is acyclic.
boolean	isUndirected(Edge e) Determine if a given edge is directed or undirected.
java.util.Iterator	iterator() Get an iterator for the graph.
void	makeUndirected(Edge e) This makes a directed edge undirected.
void	removeEdge(Edge e) Removes an edge from the graph.
void	removeEdge(java.lang.Object e, java.lang.Object e1) Remove the edge between the two given vertices.
boolean	reverseDirection(Edge e) Reverse the direction of the edge.
void	setDirectionFrom(Edge e, java.lang.Object v) This should force the directionality of an edge to be from the passed element.
int	size() Returns the number of vertices in this graph.
boolean	topologicalSort() Sort the nodes of this graph according to topological order.

Methods inherited from class uchicago.src.sim.topology.graph.AbstractGraph

addRelation, getRelations, getRelations, getRelationType, removeRelation, setRelationType

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

DirectedGraph

public DirectedGraph(java.util.Set s)

Construct a graph using the specified set of vertices. The type is set to "DirectedGraph"

Parameters:

s -

DirectedGraph

public DirectedGraph(java.util.Set s,
                     java.lang.String type)

Construct a graph using the specified set of vertices and the type.

Parameters:

s -

type -

Method Detail

getEdgeSet

protected java.util.Set getEdgeSet(java.lang.Object v,
                                   EdgeType e)

insertEdge

public void insertEdge(java.lang.Object e,
                       java.lang.Object e1,
                       double strength)

Insert a new edge into the graph. This method will create a new edge based on the class specification from the edgeClass parameter.

Specified by:

insertEdge in interface Graph

Parameters:

e -

e1 -

insertEdge

public void insertEdge(Edge e)

Insert an edge that has already been created.

Specified by:

insertEdge in interface Graph

Parameters:

e -

removeEdge

public void removeEdge(Edge e)

Removes an edge from the graph. This should also remove the edge from the elements of the edge. In other words, after this call, there should be no references to the edge.

Specified by:

removeEdge in interface Graph

Parameters:

e -

removeEdge

public void removeEdge(java.lang.Object e,
                       java.lang.Object e1)

Remove the edge between the two given vertices.

Specified by:

removeEdge in interface Graph

Parameters:

e -

e1 -

isUndirected

public boolean isUndirected(Edge e)

Determine if a given edge is directed or undirected. The semantics of how directionality is handled is left up to the implementor.

Parameters:

e -

Returns:

reverseDirection

public boolean reverseDirection(Edge e)

Reverse the direction of the edge. If the edge is undirected, this method, should not alter the directionality.

Parameters:

e -

Returns:

setDirectionFrom

public void setDirectionFrom(Edge e,
                             java.lang.Object v)

This should force the directionality of an edge to be from the passed element. An undirected edge should become directed.

Parameters:

e -

v -

getAdjacentNodes

public java.util.List getAdjacentNodes(java.lang.Object v,
                                       EdgeType type)

Get the Nodes that share an edge with the parameter with the proper directionality.

Specified by:

getAdjacentNodes in interface Graph

Parameters:

v -

type -

Returns:

getInNodes

public java.util.List getInNodes(java.lang.Object v)

Get all of the vertices that the given vertex has an in edge from.

Parameters:

v -

Returns:

getOutNodes

public java.util.List getOutNodes(java.lang.Object v)

Get all of the vertices that the given vertex has an out edge to.

Parameters:

v -

Returns:

getAdjacentNodes

public java.util.List getAdjacentNodes(java.lang.Object v,
                                       double distance,
                                       EdgeType type)

Get a list of the vertices that are attached to the specified vertex of the given direction and within the given distance.

Specified by:

getAdjacentNodes in interface Graph

Parameters:

v -

distance -

type -

Returns:

areAdjacent

public boolean areAdjacent(java.lang.Object v,
                           java.lang.Object v1,
                           EdgeType type)

Returns whether the two elements share an edge with the given directionality.

Specified by:

areAdjacent in interface Graph

Parameters:

v -

v1 -

type -

Returns:

getEdges

public java.util.List getEdges(java.lang.Object v,
                               EdgeType type)

Returns the edge objects of the given directionality for the object.

Specified by:

getEdges in interface Graph

Parameters:

v -

type -

Returns:

degree

public int degree(java.lang.Object v,
                  EdgeType type)

Returns the number of edges for the object with the given directionality.

Specified by:

degree in interface Graph

Parameters:

v -

type -

Returns:

iterator

public java.util.Iterator iterator()

Get an iterator for the graph.

Specified by:

iterator in interface Graph

Returns:

distance

public double distance(java.lang.Object element1,
                       java.lang.Object element2)

This returns the distance between two vertices in the graph.

Specified by:

distance in interface RelationTopology

Parameters:

element1 -

element2 -

Returns:

makeUndirected

public void makeUndirected(Edge e)

This makes a directed edge undirected. For the DirectedGraph, this method add the transposed edge, i.e., given edge (u,v), this will insert (v, u). The two edges will share any object references and will start with the same strength. Note, there are two edges, so if you change primitives in one edge, they will not change in the second edge.

See Also:

uchicago.src.sim.topology.graph.Graph#makeUndirected(uchicago.src.sim.topology.graph.Edge)

size

public int size()

Returns the number of vertices in this graph.

Specified by:

size in interface Graph

isAcyclic

public boolean isAcyclic()

Determines if the graph is acyclic. For an acyclic graph, this will take O(V + E) where V is the number of vertices and E is the number of edges. For a cyclic graph, this will return as soon as the back edge is found.

Returns:

topologicalSort

public boolean topologicalSort()

Sort the nodes of this graph according to topological order. This performs at O(V + E) where V is the number of vertices and E is the number of edges. This will return false if the graph is not acyclic.

Returns:

true if the sort is successful, false otherwise (usually because the graph is not acyclic).

getNodes

public java.util.Set getNodes()

Specified by:

getNodes in interface Graph

hashCode

public int hashCode()

Overrides:

hashCode in class AbstractGraph

equals

public boolean equals(java.lang.Object oth)

Overrides:

equals in class AbstractGraph

clusterCoeffient

public double clusterCoeffient()

Calculates the clustering coefficient for this graph. For our purposes the clustering coefficient is defined as The density of local networks. From a practical perspective this is calculated by averaging the results of the following procedure over all of the nodes. - Get all adjacent nodes, ignoring self loops (jNodes) - for each of those nodes, get all adjacent nodes (kNodes) - determine how many kNodes are also jNodes - divide by the total number possible: (degree(i) * (degree(i) - 1))

Returns: