Logo Search packages:      
Sourcecode: libjgrapht-java version File versions  Download package

org::_3pq::jgrapht::graph::Subgraph Class Reference

Inheritance diagram for org::_3pq::jgrapht::graph::Subgraph:

org::_3pq::jgrapht::graph::AbstractGraph org::_3pq::jgrapht::Graph org::_3pq::jgrapht::graph::DirectedSubgraph org::_3pq::jgrapht::graph::UndirectedSubgraph org::_3pq::jgrapht::graph::DirectedWeightedSubgraph org::_3pq::jgrapht::graph::UndirectedWeightedSubgraph

List of all members.

Detailed Description

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 org._3pq.jgrapht.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).

Barak Naveh
See also:


Jul 18, 2003

Definition at line 126 of file Subgraph.java.

Public Member Functions

boolean addAllEdges (Collection edges)
boolean addAllVertices (Collection vertices)
boolean addEdge (Edge e)
Edge addEdge (Object sourceVertex, Object targetVertex)
boolean addVertex (Object v)
boolean containsEdge (Object sourceVertex, Object targetVertex)
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 ()
List incomingEdgesOf (Object vertex)
int inDegreeOf (Object vertex)
boolean isVerifyIntegrity ()
int outDegreeOf (Object vertex)
List outgoingEdgesOf (Object vertex)
List removeAllEdges (Object sourceVertex, Object targetVertex)
boolean removeAllEdges (Collection edges)
boolean removeAllVertices (Collection vertices)
Edge removeEdge (Object sourceVertex, Object targetVertex)
boolean removeEdge (Edge e)
boolean removeVertex (Object v)
void setVerifyIntegrity (boolean verifyIntegrity)
 Subgraph (Graph base, Set vertexSubset)
 Subgraph (Graph base, Set vertexSubset, Set edgeSubset)
String toString ()
Set vertexSet ()

Protected Member Functions

boolean assertVertexExist (Object v)
boolean removeAllEdges (Edge[] edges)
String toStringFromSets (Collection vertexSet, Collection edgeSet)

Package Attributes

Set m_edgeSet = new LinkedHashSet( )
Set m_vertexSet = new LinkedHashSet( )

Private Member Functions

void addEdgesUsingFilter (Set edgeSet, Set filter)
void addVerticesUsingFilter (Set vertexSet, Set filter)

Private Attributes

Graph m_base
boolean m_isInduced = false
transient Set m_unmodifiableEdgeSet = null
transient Set m_unmodifiableVertexSet = null
boolean m_verifyIntegrity = true

Static Private Attributes

static final String NO_SUCH_EDGE_IN_BASE
static final String NO_SUCH_VERTEX_IN_BASE


class  BaseGraphListener

The documentation for this class was generated from the following file:

Generated by  Doxygen 1.6.0   Back to index