Graph (S-Space Package 2.0.1 API)

All Known Subinterfaces:

DirectedGraph<E>, DynamicGraph, Multigraph<T,E>, WeightedGraph<E>

All Known Implementing Classes:

AbstractGraph, AbstractGraph.Subgraph, DirectedMultigraph, GenericGraph, GraphAdaptor, LabeledGraph, SparseDirectedGraph, SparseUndirectedGraph, SparseWeightedGraph, UndirectedMultigraph, WeightedDirectedMultigraph
```
public interface Graph<E extends Edge>
```
An interface specification for interacting with Graph objects. This interface assumes the most general contract for interacting with a graph as a set of edges and vertices. This interface permits the following behaviors of a graph:
- Multiple edges between two vertices (a Multigraph).
- Weights associated with each edge (a WeightedGraph);
- Directionality between edges, i.e. an edge x->y is not equal to x<-y (a DirectedGraph)
- Self-loops
Implementations may enforce any, some, or all of these behaviors to fully define their behavior.
All implementations are also encourage to support two general purpose constructors: a no-arg constructor that creates an empty graph, and a second constructor that takes in a Graph instance of the appropriate type and makes a copy of its vertices and edges. This second constructor allows the user to easily make a copy of the graph.
All operations that may modify the state of the Graph are optional. Implementations that are read-only (or only support some subset of the operations) should throw an UnsupportedOperationException if such methods are called.
This interface exposes two different methods to examine a portion of the graph at one time: copy(Set) and subgraph(Set). The Graph instances returned from copy(Set) differs in that the returned copy is not tied to this graph's data and so any changes to the copy are not reflected in this graph. In contrast, the graph returned form subview is back by the current graph; however, the graph is unmodifiable, presenting a read-only view. Any changes to the backing graph will be reflected in the subgraph.
Author:

David Jurgens

Method Summary

Methods
Modifier and Type	Method and Description
`boolean`	`add(E edge)` Adds an edge between the two vertices, returning `true` if the edge was not previously present (optional operation).
`boolean`	`add(int i)` Adds a vertex with the provided index to the graph, returning `true` if the vertex 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 from, int to)` Returns `true` if this graph contains an edge between `from` and `to`.
`Graph<E>`	`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<E>`	`edges()` Returns the set of edges contained in this graph.
`Set<E>`	`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<E>`	`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`	`order()` Returns the number of vertices in this graph.
`boolean`	`remove(E 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<E>`	`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).
`IntSet`	`vertices()` Returns the set of vertices in this graph.

- Method Detail
  - add
```
boolean add(int i)
```
    Adds a vertex with the provided index to the graph, returning true if the vertex was not previously present (optional operation).
    
    Parameters:
    i - 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
    
    Throws:
    
    IllegalArgumentException - if i is negative or beyond the number of representable vertices in the current instance
  - add
```
boolean add(E edge)
```
    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).
    
    Returns:
    true if the edge was added, false if the edge was not added, or if the edge was aready present
    
    Throws:
    
    GraphConstructionException - if adding this edge cannot be added to the graph
    See Also:
    #containsEdge(int, int)
  - clear
```
void clear()
```
    Removes all the edges and vertices from this graph (optional operation).
  - clearEdges
```
void clearEdges()
```
    Removes all the edges in this graph, retaining all the vertices (optional operation).
  - contains
```
boolean contains(int vertex)
```
    Returns true if this graph a vertex with the specified index
  - contains
```
boolean contains(int from,
               int to)
```
    Returns true if this graph contains an edge between from and to. Imeplementations are free to define whether the ordering of the vertices matters.
  - contains
```
boolean contains(Edge e)
```
    Returns true if this graph contains an edge of the specific type between vertex1 and vertex2.
  - copy
```
Graph<E> 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.
  - degree
```
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.
  - edges
```
Set<E> edges()
```
    Returns the set of edges contained in this graph. It is expected that changes to this set be reflected in the backing graph.
  - getAdjacencyList
```
Set<E> getAdjacencyList(int vertex)
```
    Returns the set of edges connected to the provided vertex or an empty set if vertex is not in this graph.
  - getNeighbors
```
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.
  - getEdges
```
Set<E> getEdges(int vertex1,
              int vertex2)
```
    Returns the Edge instances connecting the two vertices or an empty set if the vertices are not connected.
  - hasCycles
```
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.
  - order
```
int order()
```
    Returns the number of vertices in this graph.
  - remove
```
boolean remove(E e)
```
    Removes the edge from vertex1 to vertex2, returning true if the edge existed and was removed (optional operation).
  - remove
```
boolean remove(int vertex)
```
    Removes the vertex and all of its connected edges from the graph (optional operation).
  - size
```
int size()
```
    Returns the number of edges in this graph.
  - subgraph
```
Graph<E> 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.
    
    Parameters:
    vertices - the vertices to include in the subgraph
    
    Throws:
    
    IllegalArgumentException - if vertices contains vertices not present in this graph
  - vertices
```
IntSet vertices()
```
    Returns the set of vertices in this graph.

Interface Graph<E extends Edge>

Method Summary

Method Detail

add

add

clear

clearEdges

contains

contains

contains

copy

degree

edges

getAdjacencyList

getNeighbors

getEdges

hasCycles

order

remove

remove

size

subgraph

vertices