Package 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:
GraphDecorator
,ObservableGraph
public interface Graph<V,E> extends Hypergraph<V,E>
A graph consisting of a set of vertices of typeV
set and a set of edges of typeE
. 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
Definitions (with respect to a given vertex
v
):-
incoming edge of
v
: an edge that can be traversed from a neighbor ofv
to reachv
outgoing edge ofv
: an edge that can be traversed fromv
to reach some neighbor ofv
predecessor ofv
: a vertex at the other end of an incoming edge ofv
successor ofv
: a vertex at the other end of an outgoing edge ofv
-
-
Method Summary
All Methods Instance Methods Abstract Methods Modifier and Type Method Description boolean
addEdge(E e, V v1, V v2)
Adds edgee
to this graph such that it connects vertexv1
tov2
.boolean
addEdge(E e, V v1, V v2, EdgeType edgeType)
Adds edgee
to this graph such that it connects vertexv1
tov2
.V
getDest(E directed_edge)
Ifdirected_edge
is a directed edge in this graph, returns the destination; otherwise returnsnull
.Pair<V>
getEndpoints(E edge)
Returns the endpoints ofedge
as aPair
.java.util.Collection<E>
getInEdges(V vertex)
Returns aCollection
view of the incoming edges incident tovertex
in this graph.V
getOpposite(V vertex, E edge)
Returns the vertex at the other end ofedge
fromvertex
.java.util.Collection<E>
getOutEdges(V vertex)
Returns aCollection
view of the outgoing edges incident tovertex
in this graph.int
getPredecessorCount(V vertex)
Returns the number of predecessors thatvertex
has in this graph.java.util.Collection<V>
getPredecessors(V vertex)
Returns aCollection
view of the predecessors ofvertex
in this graph.V
getSource(E directed_edge)
Ifdirected_edge
is a directed edge in this graph, returns the source; otherwise returnsnull
.int
getSuccessorCount(V vertex)
Returns the number of successors thatvertex
has in this graph.java.util.Collection<V>
getSuccessors(V vertex)
Returns aCollection
view of the successors ofvertex
in this graph.int
inDegree(V vertex)
Returns the number of incoming edges incident tovertex
.boolean
isDest(V vertex, E edge)
Returnstrue
ifvertex
is the destination ofedge
.boolean
isPredecessor(V v1, V v2)
Returnstrue
ifv1
is a predecessor ofv2
in this graph.boolean
isSource(V vertex, E edge)
Returnstrue
ifvertex
is the source ofedge
.boolean
isSuccessor(V v1, V v2)
Returnstrue
ifv1
is a successor ofv2
in this graph.int
outDegree(V vertex)
Returns the number of outgoing edges incident tovertex
.-
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
java.util.Collection<E> getInEdges(V vertex)
Returns aCollection
view of the incoming edges incident tovertex
in this graph.- Specified by:
getInEdges
in interfaceHypergraph<V,E>
- Parameters:
vertex
- the vertex whose incoming edges are to be returned- Returns:
- a
Collection
view of the incoming edges incident tovertex
in this graph
-
getOutEdges
java.util.Collection<E> getOutEdges(V vertex)
Returns aCollection
view of the outgoing edges incident tovertex
in this graph.- Specified by:
getOutEdges
in interfaceHypergraph<V,E>
- Parameters:
vertex
- the vertex whose outgoing edges are to be returned- Returns:
- a
Collection
view of the outgoing edges incident tovertex
in this graph
-
getPredecessors
java.util.Collection<V> getPredecessors(V vertex)
Returns aCollection
view of the predecessors ofvertex
in this graph. A predecessor ofvertex
is defined as a vertexv
which is connected tovertex
by an edgee
, wheree
is an outgoing edge ofv
and an incoming edge ofvertex
.- Specified by:
getPredecessors
in interfaceHypergraph<V,E>
- Parameters:
vertex
- the vertex whose predecessors are to be returned- Returns:
- a
Collection
view of the predecessors ofvertex
in this graph
-
getSuccessors
java.util.Collection<V> getSuccessors(V vertex)
Returns aCollection
view of the successors ofvertex
in this graph. A successor ofvertex
is defined as a vertexv
which is connected tovertex
by an edgee
, wheree
is an incoming edge ofv
and an outgoing edge ofvertex
.- Specified by:
getSuccessors
in interfaceHypergraph<V,E>
- Parameters:
vertex
- the vertex whose predecessors are to be returned- Returns:
- a
Collection
view of the successors ofvertex
in this graph
-
inDegree
int inDegree(V vertex)
Returns the number of incoming edges incident tovertex
. Equivalent togetInEdges(vertex).size()
.- Specified by:
inDegree
in interfaceHypergraph<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 tovertex
. Equivalent togetOutEdges(vertex).size()
.- Specified by:
outDegree
in interfaceHypergraph<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)
Returnstrue
ifv1
is a predecessor ofv2
in this graph. Equivalent tov1.getPredecessors().contains(v2)
.- Parameters:
v1
- the first vertex to be queriedv2
- the second vertex to be queried- Returns:
true
ifv1
is a predecessor ofv2
, and false otherwise.
-
isSuccessor
boolean isSuccessor(V v1, V v2)
Returnstrue
ifv1
is a successor ofv2
in this graph. Equivalent tov1.getSuccessors().contains(v2)
.- Parameters:
v1
- the first vertex to be queriedv2
- the second vertex to be queried- Returns:
true
ifv1
is a successor ofv2
, and false otherwise.
-
getPredecessorCount
int getPredecessorCount(V vertex)
Returns the number of predecessors thatvertex
has in this graph. Equivalent tovertex.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 thatvertex
has in this graph. Equivalent tovertex.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)
Ifdirected_edge
is a directed edge in this graph, returns the source; otherwise returnsnull
. The source of a directed edged
is defined to be the vertex for whichd
is an outgoing edge.directed_edge
is guaranteed to be a directed edge if itsEdgeType
isDIRECTED
.- Specified by:
getSource
in interfaceHypergraph<V,E>
- Parameters:
directed_edge
-- Returns:
- the source of
directed_edge
if it is a directed edge in this graph, ornull
otherwise
-
getDest
V getDest(E directed_edge)
Ifdirected_edge
is a directed edge in this graph, returns the destination; otherwise returnsnull
. The destination of a directed edged
is defined to be the vertex incident tod
for whichd
is an incoming edge.directed_edge
is guaranteed to be a directed edge if itsEdgeType
isDIRECTED
.- Specified by:
getDest
in interfaceHypergraph<V,E>
- Parameters:
directed_edge
-- Returns:
- the destination of
directed_edge
if it is a directed edge in this graph, ornull
otherwise
-
isSource
boolean isSource(V vertex, E edge)
Returnstrue
ifvertex
is the source ofedge
. Equivalent togetSource(edge).equals(vertex)
.- Parameters:
vertex
- the vertex to be queriededge
- the edge to be queried- Returns:
true
iffvertex
is the source ofedge
-
isDest
boolean isDest(V vertex, E edge)
Returnstrue
ifvertex
is the destination ofedge
. Equivalent togetDest(edge).equals(vertex)
.- Parameters:
vertex
- the vertex to be queriededge
- the edge to be queried- Returns:
true
iffvertex
is the destination ofedge
-
addEdge
boolean addEdge(E e, V v1, V v2)
Adds edgee
to this graph such that it connects vertexv1
tov2
. Equivalent toaddEdge(e, new Pair
. If this graph does not contain(v1, v2)) v1
,v2
, or both, implementations may choose to either silently add the vertices to the graph or throw anIllegalArgumentException
. If this graph assigns edge types to its edges, the edge type ofe
will be the default for this graph. SeeHypergraph.addEdge()
for a listing of possible reasons for failure.- Parameters:
e
- the edge to be addedv1
- the first vertex to be connectedv2
- 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 edgee
to this graph such that it connects vertexv1
tov2
. Equivalent toaddEdge(e, new Pair
. If this graph does not contain(v1, v2)) v1
,v2
, or both, implementations may choose to either silently add the vertices to the graph or throw anIllegalArgumentException
. IfedgeType
is not legal for this graph, this method will throwIllegalArgumentException
. SeeHypergraph.addEdge()
for a listing of possible reasons for failure.- Parameters:
e
- the edge to be addedv1
- the first vertex to be connectedv2
- the second vertex to be connectededgeType
- 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 ofedge
as aPair
.- 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 ofedge
fromvertex
. (That is, returns the vertex incident toedge
which is notvertex
.)- Parameters:
vertex
- the vertex to be queriededge
- the edge to be queried- Returns:
- the vertex at the other end of
edge
fromvertex
-
-