Package org.jgrapht.graph

Class AbstractGraph<V,E>

java.lang.Object

org.jgrapht.graph.AbstractGraph<V,E>

Type Parameters:

V - the graph vertex type

E - the graph edge type

All Implemented Interfaces:

Graph<V,E>

Direct Known Subclasses:

AbstractBaseGraph, AsGraphUnion, AsSubgraph, BaseGraphAdapter, BaseNetworkAdapter, BaseValueGraphAdapter, GraphDelegator, MaskSubgraph, SparseIntDirectedGraph, SparseIntUndirectedGraph

public abstract class AbstractGraph<V,E>
extends Object
implements Graph<V,E>

A skeletal implementation of the Graph interface, to minimize the effort required to implement graph interfaces. This implementation is applicable to both: directed graphs and undirected graphs.

Author:

Barak Naveh

See Also:

Graph

Field Summary

Fields inherited from interface org.jgrapht.Graph

DEFAULT_EDGE_WEIGHT

Constructor Summary

Constructors

Modifier	Constructor	Description
protected	AbstractGraph()	Construct a new empty graph object.

Method Summary

Modifier and Type	Method	Description
protected boolean	assertVertexExist(V v)	Ensures that the specified vertex exists in this graph, or else throws exception.
boolean	containsEdge(V sourceVertex, V targetVertex)	Returns true if and only if this graph contains an edge going from the source vertex to the target vertex.
boolean	equals(Object obj)	Indicates whether some other object is "equal to" this graph.
int	hashCode()	Returns a hash code value for this graph.
protected boolean	removeAllEdges(E[] edges)	Removes all the edges in this graph that are also contained in the specified edge array.
boolean	removeAllEdges(Collection<? extends E> edges)	Removes all the edges in this graph that are also contained in the specified edge collection.
Set<E>	removeAllEdges(V sourceVertex, V targetVertex)	Removes all the edges going from the specified source vertex to the specified target vertex, and returns a set of all removed edges.
boolean	removeAllVertices(Collection<? extends V> vertices)	Removes all the vertices in this graph that are also contained in the specified vertex collection.
String	toString()	Returns a string of the parenthesized pair (V, E) representing this G=(V,E) graph.
protected String	toStringFromSets(Collection<? extends V> vertexSet, Collection<? extends E> edgeSet, boolean directed)	Helper for subclass implementations of toString( ).

Methods inherited from class java.lang.Object

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

Methods inherited from interface org.jgrapht.Graph

addEdge, addEdge, addVertex, addVertex, containsEdge, containsVertex, degreeOf, edgeSet, edgesOf, getAllEdges, getEdge, getEdgeSource, getEdgeSupplier, getEdgeTarget, getEdgeWeight, getType, getVertexSupplier, incomingEdgesOf, inDegreeOf, outDegreeOf, outgoingEdgesOf, removeEdge, removeEdge, removeVertex, setEdgeWeight, setEdgeWeight, vertexSet

Constructor Detail

AbstractGraph

protected AbstractGraph()

Construct a new empty graph object.

Method Detail

containsEdge

public boolean containsEdge(V sourceVertex,
                            V targetVertex)

Description copied from interface: Graph

Returns true if and only if this graph contains an edge going from the source vertex to the target vertex. In undirected graphs the same result is obtained when source and target are inverted. If any of the specified vertices does not exist in the graph, or if is null, returns false.

Specified by:

containsEdge in interface Graph<V,E>

Parameters:

sourceVertex - source vertex of the edge.

targetVertex - target vertex of the edge.

Returns:

true if this graph contains the specified edge.

See Also:

Graph.containsEdge(Object, Object)

removeAllEdges

public boolean removeAllEdges(Collection<? extends E> edges)

Description copied from interface: Graph

Removes all the edges in this graph that are also contained in the specified edge collection. After this call returns, this graph will contain no edges in common with the specified edges. This method will invoke the Graph.removeEdge(Object) method.

Specified by:

removeAllEdges in interface Graph<V,E>

Parameters:

edges - edges to be removed from this graph.

Returns:

true if this graph changed as a result of the call

See Also:

Graph.removeAllEdges(Collection)

removeAllEdges

public Set<E> removeAllEdges(V sourceVertex,
                             V targetVertex)

Description copied from interface: Graph

Removes all the edges going from the specified source vertex to the specified target vertex, and returns a set of all removed edges. Returns null if any of the specified vertices does not exist in the graph. If both vertices exist but no edge is found, returns an empty set. This method will either invoke the Graph.removeEdge(Object) method, or the Graph.removeEdge(Object, Object) method.

Specified by:

removeAllEdges in interface Graph<V,E>

Parameters:

sourceVertex - source vertex of the edge.

targetVertex - target vertex of the edge.

Returns:

the removed edges, or null if either vertex is not part of graph

See Also:

Graph.removeAllEdges(Object, Object)

removeAllVertices

public boolean removeAllVertices(Collection<? extends V> vertices)

Description copied from interface: Graph

Removes all the vertices in this graph that are also contained in the specified vertex collection. After this call returns, this graph will contain no vertices in common with the specified vertices. This method will invoke the Graph.removeVertex(Object) method.

Specified by:

removeAllVertices in interface Graph<V,E>

Parameters:

vertices - vertices to be removed from this graph.

Returns:

true if this graph changed as a result of the call

See Also:

Graph.removeAllVertices(Collection)

toString

public String toString()

Returns a string of the parenthesized pair (V, E) representing this G=(V,E) graph. 'V' is the string representation of the vertex set, and 'E' is the string representation of the edge set.

Overrides:

toString in class Object

Returns:

a string representation of this graph.

assertVertexExist

protected boolean assertVertexExist(V v)

Ensures that the specified vertex exists in this graph, or else throws exception.

Parameters:

v - vertex

Returns:

true if this assertion holds.

Throws:

NullPointerException - if specified vertex is null.

IllegalArgumentException - if specified vertex does not exist in this graph.

removeAllEdges

protected boolean removeAllEdges(E[] edges)

Removes all the edges in this graph that are also contained in the specified edge array. After this call returns, this graph will contain no edges in common with the specified edges. This method will invoke the Graph.removeEdge(Object) method.

Parameters:

edges - edges to be removed from this graph.

Returns:

true if this graph changed as a result of the call.

See Also:

Graph.removeEdge(Object), Graph.containsEdge(Object)

toStringFromSets

protected String toStringFromSets(Collection<? extends V> vertexSet,
                                  Collection<? extends E> edgeSet,
                                  boolean directed)

Helper for subclass implementations of toString( ).

Parameters:

vertexSet - the vertex set V to be printed

edgeSet - the edge set E to be printed

directed - true to use parens for each edge (representing directed); false to use curly braces (representing undirected)

Returns:

a string representation of (V,E)

hashCode

public int hashCode()

Returns a hash code value for this graph. The hash code of a graph is defined to be the sum of the hash codes of vertices and edges in the graph. It is also based on graph topology and edges weights.

Overrides:

hashCode in class Object

Returns:

the hash code value this graph

See Also:

Object.hashCode()

equals

public boolean equals(Object obj)

Indicates whether some other object is "equal to" this graph. Returns true if the given object is also a graph, the two graphs are instances of the same graph class, have identical vertices and edges sets with the same weights.

Overrides:

equals in class Object

Parameters:

obj - object to be compared for equality with this graph

Returns:

true if the specified object is equal to this graph

See Also:

Object.equals(Object)