edu.ucla.sspace.graph

Class SparseUndirectedGraph

java.lang.Object

edu.ucla.sspace.graph.AbstractGraph<Edge,SparseUndirectedEdgeSet>

edu.ucla.sspace.graph.SparseUndirectedGraph

All Implemented Interfaces:

Graph<Edge>, Serializable

public class SparseUndirectedGraph
extends AbstractGraph<Edge,SparseUndirectedEdgeSet>

An undirected implementation of Graph that uses a sparse backing representation. This implementation assumes that the total number of edges is less than the n² possible, where n is the number of vertices.

This class supports all optional Graph. All returned Edge-based collections will reflect the state of the graph and may be modified to change the graph; i.e., adding an edge to the adjacency list of a vertex or edge list of the graph will add that edge in the backing graph. Adding vertices by adding to the AbstractGraph.vertices() set is supported. Adding edges by adding a vertex to the set of adjacent vertex is not supported.

Author:

David Jurgens

See Also:

Serialized Form

Nested Class Summary

Nested classes/interfaces inherited from class edu.ucla.sspace.graph.AbstractGraph

AbstractGraph.Subgraph

Constructor Summary

Constructors

Constructor and Description
SparseUndirectedGraph() Creates an empty undirected graph
SparseUndirectedGraph(Graph<? extends Edge> g) Creates an undirected graph with a copy of all the vertices and edges in g.
SparseUndirectedGraph(Set<Integer> vertices) Creates an undirected graph with no edges and the provided set of vertices

Method Summary

Methods

Modifier and Type	Method and Description
Graph<Edge>	copy(Set<Integer> vertices) Creates a copy of this graph containing only the specified number of vertices and all edges between those vertices.
protected SparseUndirectedEdgeSet	createEdgeSet(int vertex) Creates a sparse edge set that treats all edges as symmetric.

Methods inherited from class edu.ucla.sspace.graph.AbstractGraph

add, add, clear, clearEdges, contains, contains, contains, degree, edges, equals, getAdjacencyList, getEdges, getEdgeSet, getNeighbors, hasCycles, hashCode, iterator, order, remove, remove, size, subgraph, toString, vertices

Methods inherited from class java.lang.Object

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

Constructor Detail

SparseUndirectedGraph

public SparseUndirectedGraph()

Creates an empty undirected graph

SparseUndirectedGraph

public SparseUndirectedGraph(Set<Integer> vertices)

Creates an undirected graph with no edges and the provided set of vertices

SparseUndirectedGraph

public SparseUndirectedGraph(Graph<? extends Edge> g)

Creates an undirected graph with a copy of all the vertices and edges in g.

Method Detail

copy

public Graph<Edge> copy(Set<Integer> vertices)

Creates a copy of this graph containing only the specified number of vertices and all edges between those vertices. If vertices is empty a new, empty graph of this instance's type is returned. Any changes made to this graph will not be reflected in returned copy or vice-versa.

Specified by:

copy in interface Graph<Edge>

Specified by:

copy in class AbstractGraph<Edge,SparseUndirectedEdgeSet>

createEdgeSet

protected SparseUndirectedEdgeSet createEdgeSet(int vertex)

Creates a sparse edge set that treats all edges as symmetric.

Specified by:

createEdgeSet in class AbstractGraph<Edge,SparseUndirectedEdgeSet>