Package edu.uci.ics.jung.graph
Class AbstractGraph<V,E>
java.lang.Object
edu.uci.ics.jung.graph.AbstractGraph<V,E>
- All Implemented Interfaces:
Graph<V,
,E> Hypergraph<V,
,E> Serializable
- Direct Known Subclasses:
AbstractTypedGraph
,SparseGraph
,SparseMultigraph
Abstract implementation of the
Graph
interface.
Designed to simplify implementation of new graph classes.- See Also:
-
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionboolean
Addsedge
to this graph with the specifiedendpoints
, with the default edge type.abstract boolean
Addsedge
to this graph with the specifiedendpoints
andEdgeType
.boolean
addEdge
(E edge, Collection<? extends V> vertices) Addsedge
to this graph.boolean
addEdge
(E edge, Collection<? extends V> vertices, EdgeType edgeType) Addsedge
to this graph with typeedge_type
.boolean
Adds edgee
to this graph such that it connects vertexv1
tov2
.boolean
Adds edgee
to this graph such that it connects vertexv1
tov2
.int
Returns the number of edges incident tovertex
.Returns an edge that connects this vertex tov
.findEdgeSet
(V v1, V v2) Returns all edges that connects this vertex tov
.int
getIncidentCount
(E edge) Returns the number of vertices that are incident toedge
.getIncidentVertices
(E edge) Returns the collection of vertices in this graph which are connected toedge
.int
getNeighborCount
(V vertex) Returns the number of vertices that are adjacent tovertex
(that is, the number of vertices that are incident to edges invertex
's incident edge set).getOpposite
(V vertex, E edge) Returns the vertex at the other end ofedge
fromvertex
.int
getPredecessorCount
(V vertex) Returns the number of predecessors thatvertex
has in this graph.int
getSuccessorCount
(V vertex) Returns the number of successors thatvertex
has in this graph.getValidatedEndpoints
(E edge, Pair<? extends V> endpoints) int
Returns the number of incoming edges incident tovertex
.boolean
isIncident
(V vertex, E edge) Returnstrue
ifvertex
andedge
are incident to each other.boolean
isNeighbor
(V v1, V v2) Returnstrue
ifv1
andv2
share an incident edge.boolean
isPredecessor
(V v1, V v2) Returnstrue
ifv1
is a predecessor ofv2
in this graph.boolean
isSuccessor
(V v1, V v2) Returnstrue
ifv1
is a successor ofv2
in this graph.int
Returns the number of outgoing edges incident tovertex
.toString()
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
Methods inherited from interface edu.uci.ics.jung.graph.Graph
getDest, getEndpoints, getInEdges, getOutEdges, getPredecessors, getSource, getSuccessors, isDest, isSource
Methods inherited from interface edu.uci.ics.jung.graph.Hypergraph
addVertex, containsEdge, containsVertex, getDefaultEdgeType, getEdgeCount, getEdgeCount, getEdges, getEdges, getEdgeType, getIncidentEdges, getNeighbors, getVertexCount, getVertices, removeEdge, removeVertex
-
Constructor Details
-
AbstractGraph
public AbstractGraph()
-
-
Method Details
-
addEdge
Description copied from interface:Hypergraph
Addsedge
to this graph. Fails under the following circumstances:edge
is already an element of the graph- either
edge
orvertices
isnull
vertices
has the wrong number of vertices for the graph typevertices
are already connected by another edge in this graph, and this graph does not accept parallel edges
- Specified by:
addEdge
in interfaceHypergraph<V,
E> - Parameters:
edge
- the edge to addvertices
- the vertices to which the edge will be connected- Returns:
true
if the add is successful, andfalse
otherwise
-
addEdge
Description copied from interface:Hypergraph
Addsedge
to this graph with typeedge_type
. Fails under the following circumstances:edge
is already an element of the graph- either
edge
orvertices
isnull
vertices
has the wrong number of vertices for the graph typevertices
are already connected by another edge in this graph, and this graph does not accept parallel edgesedge_type
is not legal for this graph
- Specified by:
addEdge
in interfaceHypergraph<V,
E> - Parameters:
edge
- edge to add to this graphvertices
- vertices which are to be connected by this edgeedgeType
- type of edge to add- Returns:
true
if the add is successful, andfalse
otherwise
-
addEdge
Description copied from interface:Graph
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. -
addEdge
Description copied from interface:Graph
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. -
addEdge
Addsedge
to this graph with the specifiedendpoints
, with the default edge type.- Parameters:
edge
- the edge to be addedendpoints
- the endpoints to be connected to this edge- Returns:
true
iff the graph was modified as a result of this call
-
addEdge
Addsedge
to this graph with the specifiedendpoints
andEdgeType
.- Parameters:
edge
- the edge to be addedendpoints
- the endpoints to be connected to this edgeedgeType
- the type of edge to add- Returns:
- true iff the graph was modified as a result of this call
-
getValidatedEndpoints
-
inDegree
Description copied from interface:Graph
Returns the number of incoming edges incident tovertex
. Equivalent togetInEdges(vertex).size()
. -
outDegree
Description copied from interface:Graph
Returns the number of outgoing edges incident tovertex
. Equivalent togetOutEdges(vertex).size()
. -
isPredecessor
Description copied from interface:Graph
Returnstrue
ifv1
is a predecessor ofv2
in this graph. Equivalent tov1.getPredecessors().contains(v2)
.- Specified by:
isPredecessor
in interfaceGraph<V,
E> - 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
Description copied from interface:Graph
Returnstrue
ifv1
is a successor ofv2
in this graph. Equivalent tov1.getSuccessors().contains(v2)
.- Specified by:
isSuccessor
in interfaceGraph<V,
E> - 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
Description copied from interface:Graph
Returns the number of predecessors thatvertex
has in this graph. Equivalent tovertex.getPredecessors().size()
.- Specified by:
getPredecessorCount
in interfaceGraph<V,
E> - Parameters:
vertex
- the vertex whose predecessor count is to be returned- Returns:
- the number of predecessors that
vertex
has in this graph
-
getSuccessorCount
Description copied from interface:Graph
Returns the number of successors thatvertex
has in this graph. Equivalent tovertex.getSuccessors().size()
.- Specified by:
getSuccessorCount
in interfaceGraph<V,
E> - Parameters:
vertex
- the vertex whose successor count is to be returned- Returns:
- the number of successors that
vertex
has in this graph
-
isNeighbor
Description copied from interface:Hypergraph
Returnstrue
ifv1
andv2
share an incident edge. Equivalent togetNeighbors(v1).contains(v2)
.- Specified by:
isNeighbor
in interfaceHypergraph<V,
E> - Parameters:
v1
- the first vertex to testv2
- the second vertex to test- Returns:
true
ifv1
andv2
share an incident edge
-
isIncident
Description copied from interface:Hypergraph
Returnstrue
ifvertex
andedge
are incident to each other. Equivalent togetIncidentEdges(vertex).contains(edge)
and togetIncidentVertices(edge).contains(vertex)
.- Specified by:
isIncident
in interfaceHypergraph<V,
E> - Parameters:
vertex
- vertex to testedge
- edge to test- Returns:
true
ifvertex
andedge
are incident to each other
-
getNeighborCount
Description copied from interface:Hypergraph
Returns the number of vertices that are adjacent tovertex
(that is, the number of vertices that are incident to edges invertex
's incident edge set).Equivalent to
getNeighbors(vertex).size()
.- Specified by:
getNeighborCount
in interfaceHypergraph<V,
E> - Parameters:
vertex
- the vertex whose neighbor count is to be returned- Returns:
- the number of neighboring vertices
-
degree
Description copied from interface:Hypergraph
Returns the number of edges incident tovertex
. Special cases of interest:- Incident self-loops are counted once.
- If there is only one edge that connects this vertex to
each of its neighbors (and vice versa), then the value returned
will also be equal to the number of neighbors that this vertex has
(that is, the output of
getNeighborCount
). - If the graph is directed, then the value returned will be the sum of this vertex's indegree (the number of edges whose destination is this vertex) and its outdegree (the number of edges whose source is this vertex), minus the number of incident self-loops (to avoid double-counting).
Equivalent to
getIncidentEdges(vertex).size()
.- Specified by:
degree
in interfaceHypergraph<V,
E> - Parameters:
vertex
- the vertex whose degree is to be returned- Returns:
- the degree of this node
- See Also:
-
getIncidentCount
Description copied from interface:Hypergraph
Returns the number of vertices that are incident toedge
. For hyperedges, this can be any nonnegative integer; for edges this must be 2 (or 1 if self-loops are permitted).Equivalent to
getIncidentVertices(edge).size()
.- Specified by:
getIncidentCount
in interfaceHypergraph<V,
E> - Parameters:
edge
- the edge whose incident vertex count is to be returned- Returns:
- the number of vertices that are incident to
edge
.
-
getOpposite
Description copied from interface:Graph
Returns the vertex at the other end ofedge
fromvertex
. (That is, returns the vertex incident toedge
which is notvertex
.)- Specified by:
getOpposite
in interfaceGraph<V,
E> - Parameters:
vertex
- the vertex to be queriededge
- the edge to be queried- Returns:
- the vertex at the other end of
edge
fromvertex
-
findEdge
Description copied from interface:Hypergraph
Returns an edge that connects this vertex tov
. If this edge is not uniquely defined (that is, if the graph contains more than one edge connectingv1
tov2
), any of these edges may be returned.findEdgeSet(v1, v2)
may be used to return all such edges. Returns null if either of the following is true:v2
is not connected tov1
- either
v1
orv2
are not present in this graph
Note: for purposes of this method,
v1
is only considered to be connected tov2
via a given directed edgee
ifv1 == e.getSource() && v2 == e.getDest()
evaluates totrue
. (v1
andv2
are connected by an undirected edgeu
ifu
is incident to bothv1
andv2
.)- Specified by:
findEdge
in interfaceHypergraph<V,
E> - Parameters:
v1
- the first endpoint of the returned edgev2
- the second endpoint of the returned edge- Returns:
- an edge that connects
v1
tov2
, ornull
if no such edge exists (or either vertex is not present) - See Also:
-
findEdgeSet
Description copied from interface:Hypergraph
Returns all edges that connects this vertex tov
. If this edge is not uniquely defined (that is, if the graph contains more than one edge connectingv1
tov2
), any of these edges may be returned.findEdgeSet(v1, v2)
may be used to return all such edges. Returns null ifv2
is not connected tov1
.
Returns an empty collection if eitherv1
orv2
are not present in this graph.Note: for purposes of this method,
v1
is only considered to be connected tov2
via a given directed edged
ifv1 == d.getSource() && v2 == d.getDest()
evaluates totrue
. (v1
andv2
are connected by an undirected edgeu
ifu
is incident to bothv1
andv2
.)- Specified by:
findEdgeSet
in interfaceHypergraph<V,
E> - Parameters:
v1
- the first endpoint of the returned edge setv2
- the second endpoint of the returned edge set- Returns:
- a collection containing all edges that connect
v1
tov2
, ornull
if either vertex is not present - See Also:
-
getIncidentVertices
Description copied from interface:Hypergraph
Returns the collection of vertices in this graph which are connected toedge
. Note that for some graph types there are guarantees about the size of this collection (i.e., some graphs contain edges that have exactly two endpoints, which may or may not be distinct). Implementations for those graph types may provide alternate methods that provide more convenient access to the vertices.- Specified by:
getIncidentVertices
in interfaceHypergraph<V,
E> - Parameters:
edge
- the edge whose incident vertices are to be returned- Returns:
- the collection of vertices which are connected to
edge
, ornull
ifedge
is not present
-
toString
-