org.jgrapht.graph

Class Subgraph<V,E,G extends Graph<V,E>>

java.lang.Object

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

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

org.jgrapht.graph.Subgraph<V,E,G>

Type Parameters:

V - the vertex type

E - the edge type

G - the type of the base graph

All Implemented Interfaces:

Serializable, Graph<V,E>

Direct Known Subclasses:

DirectedSubgraph, UndirectedSubgraph

Deprecated.

In favor of AsSubgraph.

@Deprecated
public class Subgraph<V,E,G extends Graph<V,E>>
extends AsSubgraph<V,E>
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).

Note that this implementation tries to maintain a "live-window" on the base graph, which has implications in the performance of the various operations. For example iterating over the adjacent edges of a vertex takes time proportional to the number of adjacent edges of the vertex in the base graph even if the subgraph contains only a small subset of those edges. Therefore, the user must be aware that using this implementation for certain algorithms might come with computational overhead. For certain algorithms it is better to maintain a subgraph by hand instead of using this implementation as a black box.

Since:

Jul 18, 2003

Author:

Barak Naveh

See Also:

Graph, Set, Serialized Form

Field Summary

Fields

Modifier and Type	Field and Description
protected G	g Deprecated.

Fields inherited from class org.jgrapht.graph.AsSubgraph

base, baseType, edgeSet, isInduced, vertexSet

Fields inherited from interface org.jgrapht.Graph

DEFAULT_EDGE_WEIGHT

Constructor Summary

Constructors

Constructor and Description
Subgraph(G base) Deprecated. Creates a new induced Subgraph with all vertices included.
Subgraph(G base, Set<? extends V> vertexSubset) Deprecated. Creates a new induced Subgraph.
Subgraph(G base, Set<? extends V> vertexSubset, Set<? extends E> edgeSubset) Deprecated. Creates a new Subgraph.

Method Summary

Modifier and Type	Method and Description
G	getBase() Deprecated. Get the base graph.

Methods inherited from class org.jgrapht.graph.AsSubgraph

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

Methods inherited from class org.jgrapht.graph.AbstractGraph

assertVertexExist, containsEdge, equals, hashCode, removeAllEdges, removeAllEdges, removeAllEdges, removeAllVertices, toString, toStringFromSets

Methods inherited from class java.lang.Object

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

Field Detail

g

protected final G extends Graph<V,E> g

Deprecated.

Constructor Detail

Subgraph

public Subgraph(G base,
                Set<? extends V> vertexSubset,
                Set<? extends E> edgeSubset)

Deprecated.

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.

Subgraph

public Subgraph(G base,
                Set<? extends V> vertexSubset)

Deprecated.

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(G base)

Deprecated.

Creates a new induced Subgraph with all vertices included. 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, null, null).

Parameters:

base - the base (backing) graph on which the subgraph will be based.

Method Detail

getBase

public G getBase()

Deprecated.

Get the base graph.

Returns:

the base graph