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:
AbstractGraph
,AbstractTypedGraph
,AggregateGraph
,DelegateForest
,DelegateTree
,DirectedOrderedSparseMultigraph
,DirectedSparseGraph
,DirectedSparseMultigraph
,FastRenderingGraph
,GraphDecorator
,Graphs.SynchronizedAbstractGraph
,Graphs.SynchronizedDirectedGraph
,Graphs.SynchronizedForest
,Graphs.SynchronizedGraph
,Graphs.SynchronizedTree
,Graphs.SynchronizedUndirectedGraph
,Graphs.UnmodifiableAbstractGraph
,Graphs.UnmodifiableDirectedGraph
,Graphs.UnmodifiableForest
,Graphs.UnmodifiableGraph
,Graphs.UnmodifiableTree
,Graphs.UnmodifiableUndirectedGraph
,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 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 of
v
: an edge that can be traversed fromv
to reach some neighbor ofv
- predecessor of
v
: a vertex at the other end of an incoming edge ofv
- successor of
v
: 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
- the edge whose source is to be returned- 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
- the edge whose destination is to be returned- 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(v1, v2))
. If this graph does not containv1
,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(v1, v2))
. If this graph does not containv1
,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
-
-