org._3pq.jgrapht.graph

Class Subgraph

Implemented Interfaces:
Serializable, Graph
Known Direct Subclasses:
DirectedSubgraph, UndirectedSubgraph

public class Subgraph
extends AbstractGraph
implements Serializable

A subgraph is a graph that has a subset of vertices and a subset of edges with respect to some base graph. More formally, a subgraph G(V,E) that is based on a base graph Gb(Vb,Eb) satisfies the following subgraph property: V is a subset of Vb and E is a subset of Eb. Other than this property, a subgraph is a graph with any respect and fully complies with the Graph interface.

If the base graph is a ListenableGraph, the subgraph listens on the base graph and guarantees the subgraph property. If an edge or a vertex is removed from the base graph, it is automatically removed from the subgraph. Subgraph listeners are informed on such removal only if it results in a cascaded removal from the subgraph. If the subgraph has been created as an induced subgraph it also keeps track of edges being added to its vertices. If vertices are added to the base graph, the subgraph remains unaffected.

If the base graph is not a ListenableGraph, then the subgraph property cannot be guaranteed. If edges or vertices are removed from the base graph, they are not removed from the subgraph.

Modifications to Subgraph are allowed as long as the subgraph property is maintained. Addition of vertices or edges are allowed as long as they also exist in the base graph. Removal of vertices or edges is always allowed. The base graph is never affected by any modification made to the subgraph.

A subgraph may provide a "live-window" on a base graph, so that changes made to its vertices or edges are immediately reflected in the base graph, and vice versa. For that to happen, vertices and edges added to the subgraph must be identical (that is, reference-equal and not only value-equal) to their respective ones in the base graph. Previous versions of this class enforced such identity, at a severe performance cost. Currently it is no longer enforced. If you want to achieve a "live-window" functionality, your safest tactics would be to NOT override the equals()methods of your vertices and edges. If you use a class that has already overridden the equals() method, such as String, than you can use a wrapper around it, or else use it directly but exercise a great care to avoid having different-but-equal instances in the subgraph and the base graph.

This graph implementation guarantees deterministic vertex and edge set ordering (via LinkedHashSet).

Author:
Barak Naveh
Since:
Jul 18, 2003
See Also:
Graph, java.util.Set

Constructor Summary

Subgraph(Graph base, Set vertexSubset)
Creates a new induced Subgraph.
Subgraph(Graph base, Set vertexSubset, Set edgeSubset)
Creates a new Subgraph.

Method Summary

Edge
addEdge(Object sourceVertex, Object targetVertex)
boolean
addEdge(Edge e)
Adds the specified edge to this subgraph.
boolean
addVertex(Object v)
Adds the specified vertex to this subgraph.
boolean
containsEdge(Edge e)
boolean
containsVertex(Object v)
int
degreeOf(Object vertex)
Set
edgeSet()
List
edgesOf(Object vertex)
List
getAllEdges(Object sourceVertex, Object targetVertex)
Edge
getEdge(Object sourceVertex, Object targetVertex)
EdgeFactory
getEdgeFactory()
int
inDegreeOf(Object vertex)
List
incomingEdgesOf(Object vertex)
boolean
isVerifyIntegrity()
Deprecated. method will be deleted in future versions.
int
outDegreeOf(Object vertex)
List
outgoingEdgesOf(Object vertex)
Edge
removeEdge(Object sourceVertex, Object targetVertex)
boolean
removeEdge(Edge e)
boolean
removeVertex(Object v)
void
setVerifyIntegrity(boolean verifyIntegrity)
Deprecated. method will be deleted in future versions.
Set
vertexSet()

Methods inherited from class org._3pq.jgrapht.graph.AbstractGraph

addAllEdges, addAllVertices, assertVertexExist, containsEdge, removeAllEdges, removeAllEdges, removeAllEdges, removeAllVertices, toString, toStringFromSets

Constructor Details

Subgraph

public Subgraph(Graph base,
                Set vertexSubset)
Creates a new induced Subgraph. The subgraph will keep track of edges being added to its vertex subset as well as deletion of edges and vertices. If base it not listenable, this is identical to the call Subgraph(base, vertexSubset, null) .
Parameters:
base - the base (backing) graph on which the subgraph will be based.
vertexSubset - vertices to include in the subgraph. If null then all vertices are included.

Subgraph

public Subgraph(Graph base,
                Set vertexSubset,
                Set edgeSubset)
Creates a new Subgraph.
Parameters:
base - the base (backing) graph on which the subgraph will be based.
vertexSubset - vertices to include in the subgraph. If null then all vertices are included.
edgeSubset - edges to in include in the subgraph. If null then all the edges whose vertices found in the graph are included.

Method Details

addEdge

public Edge addEdge(Object sourceVertex,
                    Object targetVertex)
Specified by:
addEdge in interface Graph

addEdge

public boolean addEdge(Edge e)
Adds the specified edge to this subgraph.
Specified by:
addEdge in interface Graph
Parameters:
e - the edge to be added.
Returns:
true if the edge was added, otherwise false.

addVertex

public boolean addVertex(Object v)
Adds the specified vertex to this subgraph.
Specified by:
addVertex in interface Graph
Parameters:
v - the vertex to be added.
Returns:
true if the vertex was added, otherwise false.

containsEdge

public boolean containsEdge(Edge e)
Specified by:
containsEdge in interface Graph

containsVertex

public boolean containsVertex(Object v)
Specified by:
containsVertex in interface Graph

degreeOf

public int degreeOf(Object vertex)

edgeSet

public Set edgeSet()
Specified by:
edgeSet in interface Graph

edgesOf

public List edgesOf(Object vertex)
Specified by:
edgesOf in interface Graph

getAllEdges

public List getAllEdges(Object sourceVertex,
                        Object targetVertex)
Specified by:
getAllEdges in interface Graph

getEdge

public Edge getEdge(Object sourceVertex,
                    Object targetVertex)
Specified by:
getEdge in interface Graph

getEdgeFactory

public EdgeFactory getEdgeFactory()
Specified by:
getEdgeFactory in interface Graph

inDegreeOf

public int inDegreeOf(Object vertex)

incomingEdgesOf

public List incomingEdgesOf(Object vertex)

isVerifyIntegrity

public boolean isVerifyIntegrity()

Deprecated. method will be deleted in future versions.

Returns the value of the verifyIntegrity flag.
Returns:
the value of the verifyIntegrity flag.

outDegreeOf

public int outDegreeOf(Object vertex)

outgoingEdgesOf

public List outgoingEdgesOf(Object vertex)

removeEdge

public Edge removeEdge(Object sourceVertex,
                       Object targetVertex)
Specified by:
removeEdge in interface Graph

removeEdge

public boolean removeEdge(Edge e)
Specified by:
removeEdge in interface Graph

removeVertex

public boolean removeVertex(Object v)
Specified by:
removeVertex in interface Graph

setVerifyIntegrity

public void setVerifyIntegrity(boolean verifyIntegrity)

Deprecated. method will be deleted in future versions. verifyIntegrity flag has no effect now.

Sets the the check integrity flag.
Parameters:
verifyIntegrity -

vertexSet

public Set vertexSet()
Specified by:
vertexSet in interface Graph