DBReplicator

Open Source Database Replication

• Home
• Documentation
• Downloads
• Supported Databases
• Community
• Site Help
• Contact
• Resources

Home

JavaDoc

• Developer Documentation
• Resource

org.dbreplicator.graph
Class DirectedGraph

java.lang.Object
  org.dbreplicator.graph.DirectedGraph

All Implemented Interfaces:

DGraph

public class DirectedGraph
extends java.lang.Object
implements DGraph

Constructor Summary

DirectedGraph(int hashTableInit)
A directed graph with weighted edges.

Method Summary

boolean	addEdge(java.lang.Object first, java.lang.Object second, int weight) Adds an edge of a specified weight from the vertex first to the vertex second.
boolean	addVertex(java.lang.Object obj) Adds the specified vertex to this directed graph if the vertex is not null and the vertex is not already present in this directed graph.
java.lang.Object[]	adjacentsOf(java.lang.Object obj) Returns an array containing all vertices that are adjacent to the specified vertex.
int	edgeCount() Returns the number of edges in this directed graph.
int	edgeWeight() Returns the sum of the weights of all edges in this directed graph.
int	edgeWeight(java.lang.Object first, java.lang.Object second) Returns the weight of the edge that leaves from the vertex first and enters the vertex second.
boolean	equals(java.lang.Object obj) Compares the specified object with this directed graph for equality.
void	findCycle(Vertex startVertex) Recursively seeks a cycle starting from the vertex given as a parameter.
boolean	hasCycle() Returns true if there is a cycle in the directed graph.
boolean	hasEdge(java.lang.Object first, java.lang.Object second) Returns true if this directed graph contains an edge that leaves from the vertex first and enters the vertex second.
boolean	hasEdges() Returns true if there are edges in this directed graph.
int	hashCode() Returns the hash code value for this directed graph.
boolean	hasVertex(java.lang.Object obj) Returns true if this directed graph contains the specified vertex.
boolean	hasVertices() Returns true if there are vertices in this directed graph.
int	inDegree(java.lang.Object obj) Returns the number of edges that enter the specified vertex.
boolean	isIsolated(java.lang.Object obj) Returns true if the specified vertex is isolated.
boolean	isLinearList() Returns true if the directed graph forms a linear list.
int	outDegree(java.lang.Object obj) Returns the number of edges that leave from the specified vertex.
ListElement	searchVertex(java.lang.Object objInVertex) Does the hashing.
java.util.ArrayList	TablesInCycle()
java.lang.Object[]	topologicalSort() Returns an array of all of the vertices in this directed graph in some topological sort order.
java.lang.String	toString() This method draws a "picture" of the main hash table.
int	vertexCount() Returns the number of vertices in this directed graph.
java.lang.Object[]	verticesToArray() Returns an array containing all vertices in this directed graph.

Methods inherited from class java.lang.Object

getClass, notify, notifyAll, wait, wait, wait

Constructor Detail

DirectedGraph

public DirectedGraph(int hashTableInit)

A directed graph with weighted edges. Constructed with an integer, which is the first size of the hash table.

Method Detail

searchVertex

public ListElement searchVertex(java.lang.Object objInVertex)

Does the hashing. Finds the place where the object goes or is. It wants an embedded vertex object as its parameter, and it will return the list element

• where the object is or
• the element BEFORE the element where the object should go.

In other words, it returns the list element where the search terminates in the hash table.

Parameters:

objInVertex - the object inside the vertex that we want to find

Returns:

ListElement instance where the object is, or after which the object should come, the testing of which case is the reality should be done at the caller

findCycle

public void findCycle(Vertex startVertex)

Recursively seeks a cycle starting from the vertex given as a parameter. Marks its way through the vertices by setting the marker- attribute in each vertex-object.

Parameters:

startVertex - Vertex where the search begins.

toString

public java.lang.String toString()

This method draws a "picture" of the main hash table. It works nicely if the max chain length is ~< 4. Of course it sorta scrolls the screen for big graphs, so.. directing to a file isn't a bad option sometimes. It does NOT attempt to draw any kind of representation of the graph or edges or anything complex like that. It can help in debugging matters pertaining to the hash table structure.

Overrides:

toString in class java.lang.Object

equals

public boolean equals(java.lang.Object obj)

Compares the specified object with this directed graph for equality. Returns true if the specified object is also a directed graph and the two directed graphs have the same vertices and edges.

Specified by:

equals in interface DGraph

Overrides:

equals in class java.lang.Object

Parameters:

obj - the object to be compared for equality with this directed graph.

Returns:

true if the specified Object is equal to this directed graph.

hashCode

public int hashCode()

Returns the hash code value for this directed graph. The hash code of a directed graph is defined to be the sum of the hash codes of the vertices in the directed graph. The sum is allowed to overflow if needed. This definition ensures that if s1.equals(s2) then s1.hashCode() == s2.hashCode() for any two directed graphs s1 and s2, as required by the general contract of the java.lang.Object.hashCode method.

Specified by:

hashCode in interface DGraph

Overrides:

hashCode in class java.lang.Object

Returns:

the hash code value for this directed graph.

addVertex

public boolean addVertex(java.lang.Object obj)
                  throws RepException

Adds the specified vertex to this directed graph if the vertex is not null and the vertex is not already present in this directed graph. More formally, adds the specified vertex obj to this directed graph if obj != null and this directed graph contains no vertex e such that obj.equals(e). The number of vertices in this directed graph may not exceed Integer.MAX_VALUE.

Specified by:

addVertex in interface DGraph

Parameters:

obj - the vertex to be added to this directed graph.

Returns:

true if the specified vertex was added to this directed graph.

Throws:

java.lang.IllegalStateException - if this directed graph contains the maximum number of vertices.

java.lang.IllegalArgumentException - if a specified vertex is null.

RepException

hasVertex

public boolean hasVertex(java.lang.Object obj)

Returns true if this directed graph contains the specified vertex. More formally, returns true if and only if obj != null and this directed graph contains a vertex e such that obj.equals(e).

Specified by:

hasVertex in interface DGraph

Parameters:

obj - the vertex whose presence in this directed graph is to be tested.

Returns:

true if this directed graph contains the specified vertex.

Throws:

java.lang.IllegalArgumentException - if the specified vertex is null.

hasVertices

public boolean hasVertices()

Returns true if there are vertices in this directed graph.

Specified by:

hasVertices in interface DGraph

Returns:

true if there are vertices in this directed graph.

vertexCount

public int vertexCount()

Returns the number of vertices in this directed graph.

Specified by:

vertexCount in interface DGraph

Returns:

the number of vertices in this directed graph.

verticesToArray

public java.lang.Object[] verticesToArray()

Returns an array containing all vertices in this directed graph. The vertices need not be in any special order.

The returned array will be "safe" in that no references to it are maintained by this directed graph. In other words, this method must allocate a new array even if this collection is backed by an array. The caller is thus free to modify the returned array.

Specified by:

verticesToArray in interface DGraph

Returns:

an array containing all vertices in this directed graph.

addEdge

public boolean addEdge(java.lang.Object first,
                       java.lang.Object second,
                       int weight)
                throws RepException

Adds an edge of a specified weight from the vertex first to the vertex second.

Specified by:

addEdge in interface DGraph

Parameters:

first - the vertex that the edge leaves from.

second - the vertex that the edge enters.

weight - the non-negative weight of the edge.

Returns:

true if the specified vertex was added to this directed graph, false if there already is an edge from the vertex first to the vertex second.

Throws:

java.lang.IllegalArgumentException - if a specified vertex was null or not found in this directed graph, or if the specified weight was negative.

RepException

hasEdge

public boolean hasEdge(java.lang.Object first,
                       java.lang.Object second)

Returns true if this directed graph contains an edge that leaves from the vertex first and enters the vertex second.

Specified by:

hasEdge in interface DGraph

Parameters:

first - the vertex that the edge should leave from.

second - the vertex that the edge should enter.

Returns:

true if this directed graph contains an edge that leaves from the vertex first and enters the vertex second.

Throws:

java.lang.IllegalArgumentException - if a specified vertex was null or not found in this directed graph.

edgeWeight

public int edgeWeight(java.lang.Object first,
                      java.lang.Object second)

Returns the weight of the edge that leaves from the vertex first and enters the vertex second.

Specified by:

edgeWeight in interface DGraph

Parameters:

first - the vertex that the edge should leave from.

second - the vertex that the edge should enter.

Returns:

the weight of the edge that leaves from the vertex first and enters the vertex second. Returns -1 if there is no such edge.

Throws:

java.lang.IllegalArgumentException - if a specified vertex was null or not found in this directed graph.

inDegree

public int inDegree(java.lang.Object obj)
             throws RepException

Returns the number of edges that enter the specified vertex.

Specified by:

inDegree in interface DGraph

Parameters:

obj - Object of the vertex that the edges should enter.

Returns:

the number of edges that enter the specified vertex.

Throws:

java.lang.IllegalArgumentException - if a specified vertex was null or not found in this directed graph.

RepException

outDegree

public int outDegree(java.lang.Object obj)
              throws RepException

Returns the number of edges that leave from the specified vertex.

Specified by:

outDegree in interface DGraph

Parameters:

obj - the vertex that the edges should leave from.

Returns:

the number of edges that leave from the specified vertex.

Throws:

java.lang.IllegalArgumentException - if a specified vertex was null or not found in this directed graph.

RepException

adjacentsOf

public java.lang.Object[] adjacentsOf(java.lang.Object obj)
                               throws RepException

Returns an array containing all vertices that are adjacent to the specified vertex. A vertex v is adjacent to a vertex u if there is an edge that leaves from u and enters v.

The returned array will be "safe" in that no references to it are maintained by this directed graph. In other words, this method must allocate a new array even if this collection is backed by an array. The caller is thus free to modify the returned array.

Specified by:

adjacentsOf in interface DGraph

Parameters:

obj - the specified vertex.

Returns:

an array containing all vertices that are adjacent to the specified vertex.

Throws:

java.lang.IllegalArgumentException - if a specified vertex was null or not found in this directed graph.

RepException

isIsolated

public boolean isIsolated(java.lang.Object obj)
                   throws RepException

Returns true if the specified vertex is isolated. A vertex is isolated if there are no edges leaving from or entering the vertex, or the only edge leaving from the vertex enters the vertex itself and the only edge entering the vertex leaves from the vertex itself.

Specified by:

isIsolated in interface DGraph

Parameters:

obj - the vertex that is to be tested for isolation.

Returns:

true if the specified vertex is isolated.

Throws:

java.lang.IllegalArgumentException - if a specified vertex was null or not found in this directed graph.

RepException

hasEdges

public boolean hasEdges()

Returns true if there are edges in this directed graph.

Specified by:

hasEdges in interface DGraph

Returns:

true if there are edges in this directed graph.

edgeCount

public int edgeCount()

Returns the number of edges in this directed graph. If this directed graph contains more than Integer.MAX_VALUE edges, returns Integer.MAX_VALUE.

Specified by:

edgeCount in interface DGraph

Returns:

the number of edges in this directed graph.

edgeWeight

public int edgeWeight()

Returns the sum of the weights of all edges in this directed graph. If the sum is more than Integer.MAX_VALUE, returns Integer.MAX_VALUE.

Specified by:

edgeWeight in interface DGraph

Returns:

the sum of the weights of all edges in this directed graph.

topologicalSort

public java.lang.Object[] topologicalSort()

Returns an array of all of the vertices in this directed graph in some topological sort order.

The returned array will be "safe" in that no references to it are maintained by this directed graph. In other words, this method must allocate a new array even if this collection is backed by an array. The caller is thus free to modify the returned array.

Specified by:

topologicalSort in interface DGraph

Returns:

an array of all of the vertices in this directed graph in some topological sort order. Returns null if no topological sort is possible.

hasCycle

public boolean hasCycle()

Returns true if there is a cycle in the directed graph.

Specified by:

hasCycle in interface DGraph

Returns:

true if there is a cycle in the directed graph.

isLinearList

public boolean isLinearList()

Returns true if the directed graph forms a linear list. A directed graph with no vertices or one vertex without a self loop is also considered to form a linear list.

Specified by:

isLinearList in interface DGraph

Returns:

true if the directed graph forms a linear list.

TablesInCycle

public java.util.ArrayList TablesInCycle()