AbstractGraph (S-Space Package 2.0.1 API)

java.lang.Object
- edu.ucla.sspace.graph.AbstractGraph<T,S>

All Implemented Interfaces:

Graph<T>, Serializable

Direct Known Subclasses:

GenericGraph, SparseDirectedGraph, SparseUndirectedGraph, SparseWeightedGraph
```
public abstract class AbstractGraph<T extends Edge,S extends EdgeSet<T>>
extends Object
implements Graph<T>, Serializable
```
A base class for many Graph implementations. The core functionality of this class is provided by the EdgeSet instances returned by the subclass for specifying how edges are to be stored and which edges are valid. All calls to these sets are wrapped to ensure proper state is maintained by this AbstractGraph instance.
This class support all optional Graph methods provided that the EdgeSet implementations used by the subclass also support them. Furthermore, all methods that return non-empty collections of Edge instance can be used to modify the state of this graph by any of their respective mutation methods (e.g., adding or removing Edge instances). In addition, changes to the set of vertices returned by vertices() has the same effect as adding and removing vertices to this graph. Subclasses that wish to avoid this behavior may override these calls and wrap this classes return value in a Collections.unmodifiableSet(Set).

Author:

David Jurgens

See Also:
Serialized Form

Nested Class Summary

Nested Classes
Modifier and Type	Class and Description
`protected class`	`AbstractGraph.Subgraph` 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.

Constructor Summary

Constructors
Constructor and Description

AbstractGraph()
Creates an empty AbstractGraph

AbstractGraph(Set<Integer> vertices)
Creates a new AbstractGraph with the provided set of vertices.

Constructors
Constructor and Description
`AbstractGraph()` Creates an empty `AbstractGraph`
`AbstractGraph(Set<Integer> vertices)` Creates a new `AbstractGraph` with 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 vertex)` 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`.
`abstract 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.
`protected abstract S`	`createEdgeSet(int vertex)` Returns a `EdgeSet` that will be used to store the edges of the specified vertex
`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.
`protected S`	`getEdgeSet(int vertex)` Returns the set of edges assocated with the vertex, or `null` if this vertex is not in this graph.
`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()` Returns a description of the graph as the sequence of its edges.
`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
```
public AbstractGraph()
```
    Creates an empty AbstractGraph
  - AbstractGraph
```
public AbstractGraph(Set<Integer> vertices)
```
    Creates a new AbstractGraph with 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 vertex)
```
    Returns true if this graph a vertex with the specified index
    
    Specified by:
    
    contains 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.
    This method is sensitive to the vertex ordering; a call will check whether the edge set for e.from() contains e. Subclasses should override this method if their EdgeSet implementations are sensitive to the ordering of the vertex indices, or if a more advanced behavior is needed.
    
    Specified by:
    
    contains in interface Graph<T extends Edge>
  - copy
```
public abstract 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. 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>
  - createEdgeSet
```
protected abstract S createEdgeSet(int vertex)
```
    Returns a EdgeSet that will be used to store the edges of the specified vertex
  - 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>
  - getEdgeSet
```
protected S getEdgeSet(int vertex)
```
    Returns the set of edges assocated with the vertex, or null if this vertex is not in this graph.
  - 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).
    This method is sensitive to the vertex ordering; a call will remove the vertex for e.to() from the edge for e.from(). Subclasses should override this method if their EdgeSet implementations are sensitive to the ordering of the vertex indices, or if a more advanced behavior is needed.
    
    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()
```
    Returns a description of the graph as the sequence of its edges.
    
    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>

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

Nested Class Summary

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Constructor Detail

AbstractGraph

AbstractGraph

Method Detail

add

add

clear

clearEdges

contains

contains

contains

copy

createEdgeSet

degree

edges

equals

getAdjacencyList

getNeighbors

getEdges

getEdgeSet

hasCycles

hashCode

iterator

order

remove

remove

size

subgraph

toString

vertices