graphlab.library
Class BaseGraph<VertexType extends BaseVertex,EdgeType extends BaseEdge<VertexType>>

java.lang.Object
  graphlab.library.BaseGraph<VertexType,EdgeType>

All Implemented Interfaces:

java.lang.Iterable<VertexType>

Direct Known Subclasses:

ListGraph, MatrixGraph

public abstract class BaseGraph<VertexType extends BaseVertex,EdgeType extends BaseEdge<VertexType>>
extends java.lang.Object
implements java.lang.Iterable<VertexType>

Generic base class for representation of all types of graphs.

Author:

Omid Aladini

Constructor Summary

BaseGraph()

Method Summary

abstract void	checkVertex(VertexType v) If the supplied vertex is invalid (Not one of graph's vertices), throws InvalidVertexException.
abstract void	clear() Clears the graph.
abstract boolean	containsVertex(VertexType v) This method returns true if the graph contains the specified vertex, false otherwise.
abstract BaseGraph<VertexType,EdgeType>	copy(GraphConverter<EdgeType,EdgeType,VertexType,VertexType> gc) Creates a clone of the current graph using the GraphConverter object which is responsible for duplication of the graph elements (edges and vertices).
abstract BaseGraph<VertexType,EdgeType>	createEmptyGraph() Returns a new instance of an empty graph of the current graph type.
abstract void	dump() Prints the Adjacency Matrix to the standard output.
abstract java.util.Iterator<EdgeType>	edgeIterator() Constructs and returns an Edge Iterator object which iterates through all the edges in the graph.
abstract java.util.Iterator<EdgeType>	edgeIterator(VertexType v) Constructs an Edge Iterator object which iterates through all the edges going to or coming from the specified vertex v.
abstract java.util.Iterator<EdgeType>	edgeIterator(VertexType v, boolean head) Constructs an Edge Iterator object which iterates through all the edges going to or coming from (depending on the second parameter) the specified vertex v.
abstract Jama.Matrix	getAdjacencyMatrix() Returns a Jama Matrix object that represents adjacency matrix of the graph.
abstract int[][]	getEdgeArray() Returns array of array of 'int's where represents a simple adjacency list.
abstract java.util.Collection<EdgeType>	getEdges(VertexType head, VertexType tail) Returns a collection of all edges which connects two vertices supplied as first and second arguments of this method.
abstract int	getInDegree(VertexType v) Returns in-degree of vertex vertexId, the number of edges which their tail goes to the specified vertex.
abstract int	getOutDegree(VertexType v) Returns out-degree of the supplied vertex, the number of edges which their head is attached to the specified vertex.
abstract BaseVertex[]	getVertexArray() Returns array of vertices upcasted to BaseVertex.
abstract int	getVerticesCount() Returns the number of vertices.
abstract void	insertEdge(EdgeType newEdge) Inserts an edge in the graph.
abstract void	insertVertex(VertexType newVertex) Inserts a new vertex to the graph.
abstract boolean	isDirected() Returns whether the graph is directed.
abstract boolean	isEdge(VertexType head, VertexType tail) Returns true if there is an edge between specified vertices (direction considered for directed graphs).
abstract java.util.Iterator<VertexType>	iterator() Returns iterator object for the vertices.
abstract java.util.Iterator<EdgeType>	lightEdgeIterator() Returns a light(weight) Edge Iterator object which iterates through all the edges in the graph.
abstract java.util.Iterator<EdgeType>	lightEdgeIterator(VertexType v) Constructs a light(weight) Edge Iterator object which iterates through all the edges going to or coming from the specified vertex v.
abstract java.util.Iterator<EdgeType>	lightEdgeIterator(VertexType v, boolean head) Constructs a light(weight) Edge Iterator object which iterates through all the edges going to or coming from (depending on the second parameter) the specified vertex v.
abstract void	removeAllEdges(VertexType head, VertexType tail) Removes all edges between two vertices.
abstract void	removeEdge(EdgeType edge) Removes an edge from the graph.
abstract void	removeVertex(VertexType v) Removes a vertex and all it's connected edges.
abstract void	setDirected(boolean isDirected)

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

BaseGraph

public BaseGraph()

Method Detail

getVerticesCount

public abstract int getVerticesCount()

Returns the number of vertices.

Returns:

Number of vertices in the graph.

copy

public abstract BaseGraph<VertexType,EdgeType> copy(GraphConverter<EdgeType,EdgeType,VertexType,VertexType> gc)
                                                                                             throws InvalidGraphException

Creates a clone of the current graph using the GraphConverter object which is responsible for duplication of the graph elements (edges and vertices).

Parameters:

gc - Reference to GraphConverter object.

Returns:

Clone of the current graph which is independent of it's source graph.

Throws:

InvalidGraphException - If the graph is not a valid graph object.

insertEdge

public abstract void insertEdge(EdgeType newEdge)
                         throws InvalidVertexException

Inserts an edge in the graph.

Parameters:

newEdge - Reference to the new edge object.

Throws:

InvalidVertexException - Thrown when the edge object tries to connect two vertices whom their indexes are invalid.

removeAllEdges

public abstract void removeAllEdges(VertexType head,
                                    VertexType tail)
                             throws InvalidVertexException

Removes all edges between two vertices.

Parameters:

head - Index of the edges' start point.

tail - Index of the edges' end point.

Throws:

InvalidVertexException - Thrown when two supplied indexes of vertices are invalid.

removeEdge

public abstract void removeEdge(EdgeType edge)
                         throws InvalidEdgeException

Removes an edge from the graph.

Parameters:

edge - Edge to be removed.

Throws:

InvalidEdgeException - If edge is an invalid edge object.

getEdges

public abstract java.util.Collection<EdgeType> getEdges(VertexType head,
                                                        VertexType tail)
                                                                              throws InvalidVertexException

Returns a collection of all edges which connects two vertices supplied as first and second arguments of this method.

Parameters:

Head - of the desired edges.

Tail - of the desired edges.

Returns:

Returns a collection of all edges which connects two vertices supplied as first and second arguments of this method.

Throws:

InvalidVertexException - if supplied head or tail are invalid.

isEdge

public abstract boolean isEdge(VertexType head,
                               VertexType tail)
                        throws InvalidVertexException

Returns true if there is an edge between specified vertices (direction considered for directed graphs).

Parameters:

Head - of the edge for existance check.

Tail - of the edge for existance check.

Returns:

true if there is an edge between specified vertices (direction considered for directed graphs).

Throws:

InvalidVertexException - if supplied head or tail are invalid.

insertVertex

public abstract void insertVertex(VertexType newVertex)

Inserts a new vertex to the graph.

Parameters:

newVertex - The new vertex to be inserted.

removeVertex

public abstract void removeVertex(VertexType v)
                           throws InvalidVertexException

Removes a vertex and all it's connected edges.

Parameters:

Vertex - to be removed.

Throws:

InvalidVertexException

iterator

public abstract java.util.Iterator<VertexType> iterator()

Returns iterator object for the vertices.

Specified by:

iterator in interface java.lang.Iterable<VertexType extends BaseVertex>

Returns:

iterator object for the vertices.

getInDegree

public abstract int getInDegree(VertexType v)
                         throws InvalidVertexException

Returns in-degree of vertex vertexId, the number of edges which their tail goes to the specified vertex.

Returns:

in-degree of vertex vertexId.

Throws:

InvalidVertexException

getOutDegree

public abstract int getOutDegree(VertexType v)
                          throws InvalidVertexException

Returns out-degree of the supplied vertex, the number of edges which their head is attached to the specified vertex.

Returns:

out-degree of vertex vertexId.

Throws:

InvalidVertexException

getAdjacencyMatrix

public abstract Jama.Matrix getAdjacencyMatrix()

Returns a Jama Matrix object that represents adjacency matrix of the graph. the Matrix object have the ability apply simple linear algebra operations on the adjacency matrix.

Returns:

Adjacency Matrix of the graph as a Jama Matrix object.

isDirected

public abstract boolean isDirected()

Returns whether the graph is directed.

Returns:

True is graph is constructed as a directed graph and false otherwise.

dump

public abstract void dump()

Prints the Adjacency Matrix to the standard output.

edgeIterator

public abstract java.util.Iterator<EdgeType> edgeIterator()

Constructs and returns an Edge Iterator object which iterates through all the edges in the graph. Note that if the graph object is changed during iteration, the iteration may not actually represent current state of the graph. For example, if you deleted an edge after construction of this object, the edge would be included in the iteration.

Returns:

Iterator object on edges.

edgeIterator

public abstract java.util.Iterator<EdgeType> edgeIterator(VertexType v)
                                                                                throws InvalidVertexException

Constructs an Edge Iterator object which iterates through all the edges going to or coming from the specified vertex v. Note that if the graph object is changed during iteration, the iteration may not actually represent current state of the graph. For example, if you deleted an edge after construction of this object, the edge would be included in the iteration.

Parameters:

v - Head or tail of desired edges.

Returns:

Iterator object on edges which their heads or tails are the supplied vertex.

Throws:

InvalidVertexException

edgeIterator

public abstract java.util.Iterator<EdgeType> edgeIterator(VertexType v,
                                                          boolean head)
                                                                                throws InvalidVertexException

Constructs an Edge Iterator object which iterates through all the edges going to or coming from (depending on the second parameter) the specified vertex v. If the second parameter it true, then the first parameter is considered to be head of all desired edges, and if it's false the first parameter is considered to be tail of desired edges. Note that if the graph object is changed during iteration, the iteration may not actually represent current state of the graph. For example, if you deleted an edge after construction of this object, the edge would be included in the iteration.

Parameters:

v - If the second parameter is true indicated the vertex which is head of desired edges, otherwise it is considered to be tail of desired edges.

head - True means the first parameter should be considered head of desired edges.

Returns:

Iterator on edges which either their heads or their tails, but not necessarily both, are the supplied vertex.

Throws:

InvalidVertexException

containsVertex

public abstract boolean containsVertex(VertexType v)

This method returns true if the graph contains the specified vertex, false otherwise.

Parameters:

v - Vertex to check existance.

Returns:

True if the graph contains the specified vertex, false otherwise.

checkVertex

public abstract void checkVertex(VertexType v)
                          throws InvalidVertexException

If the supplied vertex is invalid (Not one of graph's vertices), throws InvalidVertexException. This method should be called before any operation by algorithms where some vertices are supplied as their arguments.

Parameters:

v - The vertex to be checked.

Throws:

InvalidVertexException - If the supplied vertex is invalid.

createEmptyGraph

public abstract BaseGraph<VertexType,EdgeType> createEmptyGraph()

Returns a new instance of an empty graph of the current graph type.

Returns:

A new instance of an empty graph of the current graph type.

getVertexArray

public abstract BaseVertex[] getVertexArray()

Returns array of vertices upcasted to BaseVertex.

Returns:

Array of vertices upcasted to BaseVertex.

getEdgeArray

public abstract int[][] getEdgeArray()

Returns array of array of 'int's where represents a simple adjacency list.

Returns:

Array of array of 'int's where represents a simple adjacency list.

lightEdgeIterator

public abstract java.util.Iterator<EdgeType> lightEdgeIterator()

Returns a light(weight) Edge Iterator object which iterates through all the edges in the graph. The light(weight) edge iterator presents an iterator with O(1) constructor. Note that you should not change the content of the graph during your iteration. You can still change properties of each edge or vertex.

Returns:

Returns a light(weight) Edge Iterator object.

lightEdgeIterator

public abstract java.util.Iterator<EdgeType> lightEdgeIterator(VertexType v)
                                                                                     throws InvalidVertexException

Constructs a light(weight) Edge Iterator object which iterates through all the edges going to or coming from the specified vertex v. The light(weight) edge iterator presents an iterator with O(1) constructor. Note that you should not change the content of the graph during your iteration. You can still change properties of each edge or vertex.

Parameters:

v - Head or tail of desired edges.

Returns:

A light(weight) Edge Iterator object which iterates through all the edges going to or coming from the specified vertex.

Throws:

InvalidVertexException

lightEdgeIterator

public abstract java.util.Iterator<EdgeType> lightEdgeIterator(VertexType v,
                                                               boolean head)
                                                                                     throws InvalidVertexException

Constructs a light(weight) Edge Iterator object which iterates through all the edges going to or coming from (depending on the second parameter) the specified vertex v. If the second parameter it true, then the first parameter is considered to be head of all desired edges, and if it's false the first parameter is considered to be tail of desired edges. The light(weight) edge iterator presents an iterator with O(1) constructor. Note that you should not change the content of the graph during your iteration. You can still change properties of each edge or vertex.

Parameters:

v - If the second parameter is true indicated the vertex which is head of desired edges, otherwise it is considered to be tail of desired edges.

head - True means the first parameter should be considered head of desired edges.

Returns:

A light(weight) Edge Iterator object which iterates through all the edges going to or coming from (depending on the second parameter) the specified vertex.

Throws:

InvalidVertexException

clear

public abstract void clear()

Clears the graph.

setDirected

public abstract void setDirected(boolean isDirected)