edu.ucla.sspace.graph

Interface DirectedGraph<E extends DirectedEdge>

All Superinterfaces:

Graph<E>

All Known Implementing Classes:

DirectedMultigraph, SparseDirectedGraph, WeightedDirectedMultigraph

public interface DirectedGraph<E extends DirectedEdge>
extends Graph<E>

An interface specification for interacting with directed graph objects.

Author:

David Jurgens

Method Summary

Methods

Modifier and Type	Method and Description
DirectedGraph<E>	copy(Set<Integer> vertices) Creates a copy of this graph containing only the specified number of vertices and all edges between those vertices.
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.
int	inDegree(int vertex) Returns the number of directed edges where vertex is the head of the edge, i.e.
Set<E>	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<E>	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<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	successors(int vertex) Returns the set of vertices that can be reached by following the outgoing edges from this vertex.

Methods inherited from interface edu.ucla.sspace.graph.Graph

add, add, clear, clearEdges, contains, contains, contains, degree, edges, getAdjacencyList, getNeighbors, hasCycles, order, remove, remove, size, vertices

Method Detail

copy

DirectedGraph<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.

Specified by:

copy in interface Graph<E extends DirectedEdge>

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. If the two vertices have bidirectional edges, this set will include two edges.

Specified by:

getEdges in interface Graph<E extends DirectedEdge>

inDegree

int inDegree(int vertex)

Returns the number of directed edges where vertex is the head of the edge, i.e. the edge points to vertex.

inEdges

Set<E> inEdges(int vertex)

Returns the set of directed edges where vertex is the head of the edge

outDegree

int outDegree(int vertex)

Returns the number of directed edges where vertex is the tail of the edge, i.e. the edge originates at vertex

outEdges

Set<E> outEdges(int vertex)

Returns the set of directed edges where vertex is the tail of the edge, i.e. the edge originates at vertex

predecessors

IntSet predecessors(int vertex)

Returns the set of vertices that point to this vertex. That is, the set of vertices for which there is an incoming edge to the vertex.

successors

IntSet successors(int vertex)

Returns the set of vertices that can be reached by following the outgoing edges from this vertex.

subgraph

DirectedGraph<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.

Specified by:

subgraph in interface Graph<E extends DirectedEdge>

Parameters:

vertices - the vertices to include in the subgraph