edu.ucla.sspace.graph

Class AbstractGraph.Subgraph

java.lang.Object

edu.ucla.sspace.graph.AbstractGraph.Subgraph

All Implemented Interfaces:

Graph<T>

Enclosing class:

AbstractGraph<T extends Edge,S extends EdgeSet<T>>

protected class AbstractGraph.Subgraph
extends Object
implements Graph<T>

A Graph implementation for representing the view of a subset of a graph's vertices while tracking changes to the graph on which this Subgraph is a view.

All edge information is stored in the backing graph. Subgraph instances only retain information on which vertices are currently represented as a part of the subgraph. Changes to edge by other subgraphs or to the backing graph are automatically detected and incorporated at call time.

Constructor Summary

Constructors

Constructor and Description
AbstractGraph.Subgraph(Set<Integer> vertices) Creates a new subgraph from the provided set of vertices

Method Summary

Methods

Modifier and Type	Method and Description
boolean	add(int v) Adds a vertex with the provided index to the graph, returning true if the vertex was not previously present (optional operation).
boolean	add(T e) Adds an edge between the two vertices, returning true if the edge was not previously present (optional operation).
void	clear() Removes all the edges and vertices from this graph (optional operation).
void	clearEdges() Removes all the edges in this graph, retaining all the vertices (optional operation).
boolean	contains(Edge e) Returns true if this graph contains an edge of the specific type between vertex1 and vertex2.
boolean	contains(int v) Returns true if this graph a vertex with the specified index
boolean	contains(int vertex1, int vertex2) Returns true if this graph contains an edge between from and to.
Graph<T>	copy(Set<Integer> vertices) Creates a copy of this graph containing only the specified number of vertices and all edges between those vertices.
int	degree(int vertex) Returns the number of edges that connect this vertex to other vertices in this graph.
Set<T>	edges() Returns the set of edges contained in this graph.
boolean	equals(Object o)
Set<T>	getAdjacencyList(int vertex) Returns the set of edges connected to the provided vertex or an empty set if vertex is not in this graph.
Set<T>	getEdges(int vertex1, int vertex2) Returns the Edge instances connecting the two vertices or an empty set if the vertices are not connected.
IntSet	getNeighbors(int vertex) Returns the set of vertices that are connected to the specified vertex, or an empty set if the vertex is not in this graph.
boolean	hasCycles() Computes whether this graph is acyclic with its current set of edges, and returns true if this graph contains cycles, false if acyclic.
int	hashCode()
Iterator<Integer>	iterator()
int	order() Returns the number of vertices in this graph.
boolean	remove(Edge e) Removes the edge from vertex1 to vertex2, returning true if the edge existed and was removed (optional operation).
boolean	remove(int vertex) Removes the vertex and all of its connected edges from the graph (optional operation).
int	size() Returns the number of edges in this graph.
Graph<T>	subgraph(Set<Integer> vertices) Returns a view of this graph containing only the specified vertices where the returned graph's vertinces are renamed (0, ..., n).
String	toString()
IntSet	vertices() Returns the set of vertices in this graph.

Methods inherited from class java.lang.Object

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

Constructor Detail

AbstractGraph.Subgraph

public AbstractGraph.Subgraph(Set<Integer> vertices)

Creates a new subgraph from the provided set of vertices

Method Detail

add

public boolean add(int v)

Adds a vertex with the provided index to the graph, returning true if the vertex was not previously present (optional operation).

Specified by:

add in interface Graph<T extends Edge>

Parameters:

v - a non-negative index for a vertex. If the graph has size bounds (i.e. a limited number of vertices), the implementation may throw an exception if this index exceeds those bounds.

Returns:

if the vertex was not previously present

add

public boolean add(T e)

Adds an edge between the two vertices, returning true if the edge was not previously present (optional operation).

If adding this edge would violate some structural constraints on the graph, implementations may return false or throw a GraphConstructionException. If false is returned, the called may check whether the edge was added using containsEdge

Implemenations are free to decide the behavior for cases where one or both of the vertices are not currently in the graph, and whether self-edges are allowed (i.e. vertex1 == vertex2).

Specified by:

add in interface Graph<T extends Edge>

Returns:

true if the edge was added, false if the edge was not added, or if the edge was aready present

See Also:

#containsEdge(int, int)

clear

public void clear()

Removes all the edges and vertices from this graph (optional operation).

Specified by:

clear in interface Graph<T extends Edge>

clearEdges

public void clearEdges()

Removes all the edges in this graph, retaining all the vertices (optional operation).

Specified by:

clearEdges in interface Graph<T extends Edge>

contains

public boolean contains(int vertex1,
               int vertex2)

Returns true if this graph contains an edge between from and to. Imeplementations are free to define whether the ordering of the vertices matters.

Specified by:

contains in interface Graph<T extends Edge>

contains

public boolean contains(Edge e)

Returns true if this graph contains an edge of the specific type between vertex1 and vertex2.

Specified by:

contains in interface Graph<T extends Edge>

contains

public boolean contains(int v)

Returns true if this graph a vertex with the specified index

Specified by:

contains in interface Graph<T extends Edge>

copy

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

Description copied from interface: Graph

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<T extends Edge>

degree

public int degree(int vertex)

Returns the number of edges that connect this vertex to other vertices in this graph. If the provided vertex is not in graph, this method returns 0.

Specified by:

degree in interface Graph<T extends Edge>

edges

public Set<T> edges()

Returns the set of edges contained in this graph. It is expected that changes to this set be reflected in the backing graph.

Specified by:

edges in interface Graph<T extends Edge>

equals

public boolean equals(Object o)

Overrides:

equals in class Object

getAdjacencyList

public Set<T> getAdjacencyList(int vertex)

Returns the set of edges connected to the provided vertex or an empty set if vertex is not in this graph.

Specified by:

getAdjacencyList in interface Graph<T extends Edge>

getNeighbors

public IntSet getNeighbors(int vertex)

Returns the set of vertices that are connected to the specified vertex, or an empty set if the vertex is not in this graph.

Specified by:

getNeighbors in interface Graph<T extends Edge>

getEdges

public Set<T> getEdges(int vertex1,
              int vertex2)

Returns the Edge instances connecting the two vertices or an empty set if the vertices are not connected.

Specified by:

getEdges in interface Graph<T extends Edge>

hasCycles

public boolean hasCycles()

Computes whether this graph is acyclic with its current set of edges, and returns true if this graph contains cycles, false if acyclic.

Specified by:

hasCycles in interface Graph<T extends Edge>

hashCode

public int hashCode()

Overrides:

hashCode in class Object

iterator

public Iterator<Integer> iterator()

order

public int order()

Returns the number of vertices in this graph.

Specified by:

order in interface Graph<T extends Edge>

remove

public boolean remove(Edge e)

Removes the edge from vertex1 to vertex2, returning true if the edge existed and was removed (optional operation).

Specified by:

remove in interface Graph<T extends Edge>

remove

public boolean remove(int vertex)

Removes the vertex and all of its connected edges from the graph (optional operation).

Specified by:

remove in interface Graph<T extends Edge>

size

public int size()

Returns the number of edges in this graph.

Specified by:

size in interface Graph<T extends Edge>

subgraph

public Graph<T> subgraph(Set<Integer> vertices)

Returns a view of this graph containing only the specified vertices where the returned graph's vertinces are renamed (0, ..., n). This renaming is to ensure a conceptual distance between the "new" returned graph and the backing graph in terms of vertex labeling; for example, adding vertex n to the subgraph may not necessarily correspond to vertex n in the backing graph.

Only edges connecting two vertices in the provided set will be viewable in the subgraph. Any changes to the subgraph will be reflected in this graph and vice versa.

This view allows for direct manipulation of a part of the graph. For example, clearing this subgraph will remove all of its corresponding vertices and edges from the backing graph.

Specified by:

subgraph in interface Graph<T extends Edge>

Parameters:

vertices - the vertices to include in the subgraph

toString

public String toString()

Overrides:

toString in class Object

vertices

public IntSet vertices()

Returns the set of vertices in this graph.

Specified by:

vertices in interface Graph<T extends Edge>