public class SparseDirectedGraph extends AbstractGraph<DirectedEdge,SparseDirectedEdgeSet> implements DirectedGraph<DirectedEdge>
DirectedGraph that uses a sparse backing
representation. This implementation assumes that the total number of edges
is less than the n2 possible, where n is the
number of vertices.
This class supports all optional Graph and DirectedGraph
methods. All returned DirectedEdge-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.
AbstractGraph.Subgraph| Constructor and Description |
|---|
SparseDirectedGraph()
Creates an empty directed graph
|
SparseDirectedGraph(Graph<? extends DirectedEdge> g)
Creates a directed graph with a copy of all the vertices and edges in
g. |
SparseDirectedGraph(Set<Integer> vertices)
Creates a directed graph with the provided vertices
|
| Modifier and Type | Method and Description |
|---|---|
DirectedGraph<DirectedEdge> |
copy(Set<Integer> vertices)
Creates a copy of this graph containing only the specified number of
vertices and all edges between those vertices.
|
protected SparseDirectedEdgeSet |
createEdgeSet(int vertex)
Creates an
EdgeSet for storing DirectedEdge instances for
the specified vertex. |
int |
inDegree(int vertex)
Returns the number of directed edges where
vertex is the head of
the edge, i.e. |
Set<DirectedEdge> |
inEdges(int vertex)
Returns the set of directed edges where
vertex is the head of the
edge |
int |
outDegree(int vertex)
Returns the number of directed edges where
vertex is the tail of
the edge, i.e. |
Set<DirectedEdge> |
outEdges(int vertex)
Returns the set of directed edges where
vertex is the tail of the
edge, i.e. |
IntSet |
predecessors(int vertex)
Returns the set of vertices that point to this vertex.
|
DirectedGraph |
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 |
successors(int vertex)
Returns the set of vertices that can be reached by following the outgoing
edges from this vertex.
|
add, add, clear, clearEdges, contains, contains, contains, degree, edges, equals, getAdjacencyList, getEdges, getEdgeSet, getNeighbors, hasCycles, hashCode, iterator, order, remove, remove, size, toString, verticesclone, finalize, getClass, notify, notifyAll, wait, wait, waitgetEdgespublic SparseDirectedGraph()
public SparseDirectedGraph(Set<Integer> vertices)
public SparseDirectedGraph(Graph<? extends DirectedEdge> g)
g.public DirectedGraph<DirectedEdge> copy(Set<Integer> vertices)
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.copy in interface DirectedGraph<DirectedEdge>copy in interface Graph<DirectedEdge>copy in class AbstractGraph<DirectedEdge,SparseDirectedEdgeSet>protected SparseDirectedEdgeSet createEdgeSet(int vertex)
EdgeSet for storing DirectedEdge instances for
the specified vertex.createEdgeSet in class AbstractGraph<DirectedEdge,SparseDirectedEdgeSet>public int inDegree(int vertex)
vertex is the head of
the edge, i.e. the edge points to vertex.inDegree in interface DirectedGraph<DirectedEdge>public Set<DirectedEdge> inEdges(int vertex)
vertex is the head of the
edgeinEdges in interface DirectedGraph<DirectedEdge>public int outDegree(int vertex)
vertex is the tail of
the edge, i.e. the edge originates at vertexoutDegree in interface DirectedGraph<DirectedEdge>public Set<DirectedEdge> outEdges(int vertex)
vertex is the tail of the
edge, i.e. the edge originates at vertexoutEdges in interface DirectedGraph<DirectedEdge>public IntSet predecessors(int vertex)
predecessors in interface DirectedGraph<DirectedEdge>public DirectedGraph subgraph(Set<Integer> vertices)
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.
subgraph in interface DirectedGraph<DirectedEdge>subgraph in interface Graph<DirectedEdge>subgraph in class AbstractGraph<DirectedEdge,SparseDirectedEdgeSet>vertices - the vertices to include in the subgraphpublic IntSet successors(int vertex)
successors in interface DirectedGraph<DirectedEdge>Copyright © 2012. All Rights Reserved.