edu.uci.ics.jung.graph
Interface Graph<V,E>

All Superinterfaces:

Hypergraph<V,E>

All Known Subinterfaces:

DirectedGraph<V,E>, Forest<V,E>, KPartiteGraph<V,E>, Tree<V,E>, UndirectedGraph<V,E>

All Known Implementing Classes:

AbstractGraph, AbstractTypedGraph, DelegateForest, DelegateTree, DirectedOrderedSparseMultigraph, DirectedSparseGraph, DirectedSparseMultigraph, GraphDecorator, ObservableGraph, OrderedKAryTree, OrderedSparseMultigraph, SortedSparseMultigraph, SparseGraph, SparseMultigraph, UndirectedOrderedSparseMultigraph, UndirectedSparseGraph, UndirectedSparseMultigraph

public interface Graph<V,E>
extends Hypergraph<V,E>

A graph consisting of a set of vertices of type V set and a set of edges of type E. Edges of this graph type have exactly two endpoints; whether these endpoints must be distinct depends on the implementation.

This interface permits, but does not enforce, any of the following common variations of graphs:

• directed and undirected edges
• vertices and edges with attributes (for example, weighted edges)
• vertices and edges of different types (for example, bipartite or multimodal graphs)
• parallel edges (multiple edges which connect a single set of vertices)
• representations as matrices or as adjacency lists or adjacency maps

Extensions or implementations of this interface may enforce or disallow any or all of these variations.

Definitions (with respect to a given vertex v):

• incoming edge of v: an edge that can be traversed from a neighbor of v to reach v
• outgoing edge of v: an edge that can be traversed from v to reach some neighbor of v
• predecessor of v: a vertex at the other end of an incoming edge of v
• successor of v: a vertex at the other end of an outgoing edge of v

Author:

Joshua O'Madadhain

Method Summary

boolean	addEdge(E e, V v1, V v2) Adds edge e to this graph such that it connects vertex v1 to v2.
boolean	addEdge(E e, V v1, V v2, EdgeType edgeType) Adds edge e to this graph such that it connects vertex v1 to v2.
V	getDest(E directed_edge) If directed_edge is a directed edge in this graph, returns the destination; otherwise returns null.
Pair<V>	getEndpoints(E edge) Returns the endpoints of edge as a Pair.
Collection<E>	getInEdges(V vertex) Returns a Collection view of the incoming edges incident to vertex in this graph.
V	getOpposite(V vertex, E edge) Returns the vertex at the other end of edge from vertex.
Collection<E>	getOutEdges(V vertex) Returns a Collection view of the outgoing edges incident to vertex in this graph.
int	getPredecessorCount(V vertex) Returns the number of predecessors that vertex has in this graph.
Collection<V>	getPredecessors(V vertex) Returns a Collection view of the predecessors of vertex in this graph.
V	getSource(E directed_edge) If directed_edge is a directed edge in this graph, returns the source; otherwise returns null.
int	getSuccessorCount(V vertex) Returns the number of successors that vertex has in this graph.
Collection<V>	getSuccessors(V vertex) Returns a Collection view of the successors of vertex in this graph.
int	inDegree(V vertex) Returns the number of incoming edges incident to vertex.
boolean	isDest(V vertex, E edge) Returns true if vertex is the destination of edge.
boolean	isPredecessor(V v1, V v2) Returns true if v1 is a predecessor of v2 in this graph.
boolean	isSource(V vertex, E edge) Returns true if vertex is the source of edge.
boolean	isSuccessor(V v1, V v2) Returns true if v1 is a successor of v2 in this graph.
int	outDegree(V vertex) Returns the number of outgoing edges incident to vertex.

Methods inherited from interface edu.uci.ics.jung.graph.Hypergraph

addEdge, addEdge, addVertex, containsEdge, containsVertex, degree, findEdge, findEdgeSet, getDefaultEdgeType, getEdgeCount, getEdgeCount, getEdges, getEdges, getEdgeType, getIncidentCount, getIncidentEdges, getIncidentVertices, getNeighborCount, getNeighbors, getVertexCount, getVertices, isIncident, isNeighbor, removeEdge, removeVertex

Method Detail

getInEdges

Collection<E> getInEdges(V vertex)

Returns a Collection view of the incoming edges incident to vertex in this graph.

Specified by:

getInEdges in interface Hypergraph<V,E>

Parameters:

vertex - the vertex whose incoming edges are to be returned

Returns:

a Collection view of the incoming edges incident to vertex in this graph

getOutEdges

Collection<E> getOutEdges(V vertex)

Returns a Collection view of the outgoing edges incident to vertex in this graph.

Specified by:

getOutEdges in interface Hypergraph<V,E>

Parameters:

vertex - the vertex whose outgoing edges are to be returned

Returns:

a Collection view of the outgoing edges incident to vertex in this graph

getPredecessors

Collection<V> getPredecessors(V vertex)

Returns a Collection view of the predecessors of vertex in this graph. A predecessor of vertex is defined as a vertex v which is connected to vertex by an edge e, where e is an outgoing edge of v and an incoming edge of vertex.

Specified by:

getPredecessors in interface Hypergraph<V,E>

Parameters:

vertex - the vertex whose predecessors are to be returned

Returns:

a Collection view of the predecessors of vertex in this graph

getSuccessors

Collection<V> getSuccessors(V vertex)

Returns a Collection view of the successors of vertex in this graph. A successor of vertex is defined as a vertex v which is connected to vertex by an edge e, where e is an incoming edge of v and an outgoing edge of vertex.

Specified by:

getSuccessors in interface Hypergraph<V,E>

Parameters:

vertex - the vertex whose predecessors are to be returned

Returns:

a Collection view of the successors of vertex in this graph

inDegree

int inDegree(V vertex)

Returns the number of incoming edges incident to vertex. Equivalent to getInEdges(vertex).size().

Specified by:

inDegree in interface Hypergraph<V,E>

Parameters:

vertex - the vertex whose indegree is to be calculated

Returns:

the number of incoming edges incident to vertex

outDegree

int outDegree(V vertex)

Returns the number of outgoing edges incident to vertex. Equivalent to getOutEdges(vertex).size().

Specified by:

outDegree in interface Hypergraph<V,E>

Parameters:

vertex - the vertex whose outdegree is to be calculated

Returns:

the number of outgoing edges incident to vertex

isPredecessor

boolean isPredecessor(V v1,
                      V v2)

Returns true if v1 is a predecessor of v2 in this graph. Equivalent to v1.getPredecessors().contains(v2).

Parameters:

v1 - the first vertex to be queried

v2 - the second vertex to be queried

Returns:

true if v1 is a predecessor of v2, and false otherwise.

isSuccessor

boolean isSuccessor(V v1,
                    V v2)

Returns true if v1 is a successor of v2 in this graph. Equivalent to v1.getSuccessors().contains(v2).

Parameters:

v1 - the first vertex to be queried

v2 - the second vertex to be queried

Returns:

true if v1 is a successor of v2, and false otherwise.

getPredecessorCount

int getPredecessorCount(V vertex)

Returns the number of predecessors that vertex has in this graph. Equivalent to vertex.getPredecessors().size().

Parameters:

vertex - the vertex whose predecessor count is to be returned

Returns:

the number of predecessors that vertex has in this graph

getSuccessorCount

int getSuccessorCount(V vertex)

Returns the number of successors that vertex has in this graph. Equivalent to vertex.getSuccessors().size().

Parameters:

vertex - the vertex whose successor count is to be returned

Returns:

the number of successors that vertex has in this graph

getSource

V getSource(E directed_edge)

If directed_edge is a directed edge in this graph, returns the source; otherwise returns null. The source of a directed edge d is defined to be the vertex for which d is an outgoing edge. directed_edge is guaranteed to be a directed edge if its EdgeType is DIRECTED.

Specified by:

getSource in interface Hypergraph<V,E>

Parameters:

directed_edge -

Returns:

the source of directed_edge if it is a directed edge in this graph, or null otherwise

getDest

V getDest(E directed_edge)

If directed_edge is a directed edge in this graph, returns the destination; otherwise returns null. The destination of a directed edge d is defined to be the vertex incident to d for which d is an incoming edge. directed_edge is guaranteed to be a directed edge if its EdgeType is DIRECTED.

Specified by:

getDest in interface Hypergraph<V,E>

Parameters:

directed_edge -

Returns:

the destination of directed_edge if it is a directed edge in this graph, or null otherwise

isSource

boolean isSource(V vertex,
                 E edge)

Returns true if vertex is the source of edge. Equivalent to getSource(edge).equals(vertex).

Parameters:

vertex - the vertex to be queried

edge - the edge to be queried

Returns:

true iff vertex is the source of edge

isDest

boolean isDest(V vertex,
               E edge)

Returns true if vertex is the destination of edge. Equivalent to getDest(edge).equals(vertex).

Parameters:

vertex - the vertex to be queried

edge - the edge to be queried

Returns:

true iff vertex is the destination of edge

addEdge

boolean addEdge(E e,
                V v1,
                V v2)

Adds edge e to this graph such that it connects vertex v1 to v2. Equivalent to addEdge(e, new Pair(v1, v2)). If this graph does not contain v1, v2, or both, implementations may choose to either silently add the vertices to the graph or throw an IllegalArgumentException. If this graph assigns edge types to its edges, the edge type of e will be the default for this graph. See Hypergraph.addEdge() for a listing of possible reasons for failure.

Parameters:

e - the edge to be added

v1 - the first vertex to be connected

v2 - the second vertex to be connected

Returns:

true if the add is successful, false otherwise

See Also:

Hypergraph.addEdge(Object, Collection), addEdge(Object, Object, Object, EdgeType)

addEdge

boolean addEdge(E e,
                V v1,
                V v2,
                EdgeType edgeType)

Adds edge e to this graph such that it connects vertex v1 to v2. Equivalent to addEdge(e, new Pair(v1, v2)). If this graph does not contain v1, v2, or both, implementations may choose to either silently add the vertices to the graph or throw an IllegalArgumentException. If edgeType is not legal for this graph, this method will throw IllegalArgumentException. See Hypergraph.addEdge() for a listing of possible reasons for failure.

Parameters:

e - the edge to be added

v1 - the first vertex to be connected

v2 - the second vertex to be connected

edgeType - the type to be assigned to the edge

Returns:

true if the add is successful, false otherwise

See Also:

Hypergraph.addEdge(Object, Collection), addEdge(Object, Object, Object)

getEndpoints

Pair<V> getEndpoints(E edge)

Returns the endpoints of edge as a Pair.

Parameters:

edge - the edge whose endpoints are to be returned

Returns:

the endpoints (incident vertices) of edge

getOpposite

V getOpposite(V vertex,
              E edge)

Returns the vertex at the other end of edge from vertex. (That is, returns the vertex incident to edge which is not vertex.)

Parameters:

vertex - the vertex to be queried

edge - the edge to be queried

Returns:

the vertex at the other end of edge from vertex