Package edu.uci.ics.jung.graph
Class UndirectedSparseGraph<V,E>
java.lang.Object
edu.uci.ics.jung.graph.AbstractGraph<V,E>
edu.uci.ics.jung.graph.AbstractTypedGraph<V,E>
edu.uci.ics.jung.graph.UndirectedSparseGraph<V,E>
- All Implemented Interfaces:
Graph<V,
,E> Hypergraph<V,
,E> UndirectedGraph<V,
,E> Serializable
public class UndirectedSparseGraph<V,E>
extends AbstractTypedGraph<V,E>
implements UndirectedGraph<V,E>
An implementation of
UndirectedGraph
that is suitable
for sparse graphs.- See Also:
-
Field Summary
FieldsModifier and TypeFieldDescriptionFields inherited from class edu.uci.ics.jung.graph.AbstractTypedGraph
edge_type
-
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionboolean
Addsedge
to this graph with the specifiedendpoints
andEdgeType
.boolean
Addsvertex
to this graph.boolean
containsEdge
(E edge) Returns true if this graph's edge collection containsedge
.boolean
containsVertex
(V vertex) Returns true if this graph's vertex collection containsvertex
.Returns an edge that connects this vertex tov
.findEdgeSet
(V v1, V v2) Returns all edges that connects this vertex tov
.Ifdirected_edge
is a directed edge in this graph, returns the destination; otherwise returnsnull
.int
Returns the number of edges in this graph.getEdges()
Returns a view of all edges in this graph.getEndpoints
(E edge) Returns the endpoints ofedge
as aPair
.static <V,
E> com.google.common.base.Supplier <UndirectedGraph<V, E>> getIncidentEdges
(V vertex) Returns the collection of edges in this graph which are connected tovertex
.getInEdges
(V vertex) Returns aCollection
view of the incoming edges incident tovertex
in this graph.getNeighbors
(V vertex) Returns the collection of vertices which are connected tovertex
via any edges in this graph.getOutEdges
(V vertex) Returns aCollection
view of the outgoing edges incident tovertex
in this graph.getPredecessors
(V vertex) Returns aCollection
view of the predecessors ofvertex
in this graph.Ifdirected_edge
is a directed edge in this graph, returns the source; otherwise returnsnull
.getSuccessors
(V vertex) Returns aCollection
view of the successors ofvertex
in this graph.int
Returns the number of vertices in this graph.Returns a view of all vertices in this graph.boolean
Returnstrue
ifvertex
is the destination ofedge
.boolean
Returnstrue
ifvertex
is the source ofedge
.boolean
removeEdge
(E edge) Removesedge
from this graph.boolean
removeVertex
(V vertex) Removesvertex
from this graph.Methods inherited from class edu.uci.ics.jung.graph.AbstractTypedGraph
getDefaultEdgeType, getEdgeCount, getEdges, getEdgeType, hasEqualEdgeType, validateEdgeType
Methods inherited from class edu.uci.ics.jung.graph.AbstractGraph
addEdge, addEdge, addEdge, addEdge, addEdge, degree, getIncidentCount, getIncidentVertices, getNeighborCount, getOpposite, getPredecessorCount, getSuccessorCount, getValidatedEndpoints, inDegree, isIncident, isNeighbor, isPredecessor, isSuccessor, outDegree, 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
addEdge, addEdge, getOpposite, getPredecessorCount, getSuccessorCount, inDegree, isPredecessor, isSuccessor, outDegree
Methods inherited from interface edu.uci.ics.jung.graph.Hypergraph
addEdge, addEdge, degree, getDefaultEdgeType, getEdgeCount, getEdges, getEdgeType, getIncidentCount, getIncidentVertices, getNeighborCount, isIncident, isNeighbor
-
Field Details
-
vertices
-
edges
-
-
Constructor Details
-
UndirectedSparseGraph
public UndirectedSparseGraph()Creates an instance.
-
-
Method Details
-
getFactory
- Type Parameters:
V
- the vertex type for the graph SupplierE
- the edge type for the graph Supplier- Returns:
- a
Supplier
that creates an instance of this graph type.
-
addEdge
Description copied from class:AbstractGraph
Addsedge
to this graph with the specifiedendpoints
andEdgeType
.- Specified by:
addEdge
in classAbstractGraph<V,
E> - 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
-
getInEdges
Description copied from interface:Graph
Returns aCollection
view of the incoming edges incident tovertex
in this graph.- Specified by:
getInEdges
in interfaceGraph<V,
E> - 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
Description copied from interface:Graph
Returns aCollection
view of the outgoing edges incident tovertex
in this graph.- Specified by:
getOutEdges
in interfaceGraph<V,
E> - 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
Description copied from interface:Graph
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 interfaceGraph<V,
E> - 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
Description copied from interface:Graph
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 interfaceGraph<V,
E> - 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
-
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> - Overrides:
findEdge
in classAbstractGraph<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> - Overrides:
findEdgeSet
in classAbstractGraph<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:
-
getEndpoints
Description copied from interface:Graph
Returns the endpoints ofedge
as aPair
.- Specified by:
getEndpoints
in interfaceGraph<V,
E> - Parameters:
edge
- the edge whose endpoints are to be returned- Returns:
- the endpoints (incident vertices) of
edge
-
getSource
Description copied from interface:Graph
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
. -
getDest
Description copied from interface:Graph
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
. -
isSource
Description copied from interface:Graph
Returnstrue
ifvertex
is the source ofedge
. Equivalent togetSource(edge).equals(vertex)
. -
isDest
Description copied from interface:Graph
Returnstrue
ifvertex
is the destination ofedge
. Equivalent togetDest(edge).equals(vertex)
. -
getEdges
Description copied from interface:Hypergraph
Returns a view of all edges in this graph. In general, this obeys theCollection
contract, and therefore makes no guarantees about the ordering of the vertices within the set.- Specified by:
getEdges
in interfaceHypergraph<V,
E> - Returns:
- a
Collection
view of all edges in this graph
-
getVertices
Description copied from interface:Hypergraph
Returns a view of all vertices in this graph. In general, this obeys theCollection
contract, and therefore makes no guarantees about the ordering of the vertices within the set.- Specified by:
getVertices
in interfaceHypergraph<V,
E> - Returns:
- a
Collection
view of all vertices in this graph
-
containsVertex
Description copied from interface:Hypergraph
Returns true if this graph's vertex collection containsvertex
. Equivalent togetVertices().contains(vertex)
.- Specified by:
containsVertex
in interfaceHypergraph<V,
E> - Parameters:
vertex
- the vertex whose presence is being queried- Returns:
- true iff this graph contains a vertex
vertex
-
containsEdge
Description copied from interface:Hypergraph
Returns true if this graph's edge collection containsedge
. Equivalent togetEdges().contains(edge)
.- Specified by:
containsEdge
in interfaceHypergraph<V,
E> - Parameters:
edge
- the edge whose presence is being queried- Returns:
- true iff this graph contains an edge
edge
-
getEdgeCount
public int getEdgeCount()Description copied from interface:Hypergraph
Returns the number of edges in this graph.- Specified by:
getEdgeCount
in interfaceHypergraph<V,
E> - Returns:
- the number of edges in this graph
-
getVertexCount
public int getVertexCount()Description copied from interface:Hypergraph
Returns the number of vertices in this graph.- Specified by:
getVertexCount
in interfaceHypergraph<V,
E> - Returns:
- the number of vertices in this graph
-
getNeighbors
Description copied from interface:Hypergraph
Returns the collection of vertices which are connected tovertex
via any edges in this graph. Ifvertex
is connected to itself with a self-loop, then it will be included in the collection returned.- Specified by:
getNeighbors
in interfaceHypergraph<V,
E> - Parameters:
vertex
- the vertex whose neighbors are to be returned- Returns:
- the collection of vertices which are connected to
vertex
, ornull
ifvertex
is not present
-
getIncidentEdges
Description copied from interface:Hypergraph
Returns the collection of edges in this graph which are connected tovertex
.- Specified by:
getIncidentEdges
in interfaceHypergraph<V,
E> - Parameters:
vertex
- the vertex whose incident edges are to be returned- Returns:
- the collection of edges which are connected to
vertex
, ornull
ifvertex
is not present
-
addVertex
Description copied from interface:Hypergraph
Addsvertex
to this graph. Fails ifvertex
is null or already in the graph.- Specified by:
addVertex
in interfaceHypergraph<V,
E> - Parameters:
vertex
- the vertex to add- Returns:
true
if the add is successful, andfalse
otherwise
-
removeVertex
Description copied from interface:Hypergraph
Removesvertex
from this graph. As a side effect, removes any edgese
incident tovertex
if the removal ofvertex
would causee
to be incident to an illegal number of vertices. (Thus, for example, incident hyperedges are not removed, but incident edges--which must be connected to a vertex at both endpoints--are removed.)Fails under the following circumstances:
vertex
is not an element of this graphvertex
isnull
- Specified by:
removeVertex
in interfaceHypergraph<V,
E> - Parameters:
vertex
- the vertex to remove- Returns:
true
if the removal is successful,false
otherwise
-
removeEdge
Description copied from interface:Hypergraph
Removesedge
from this graph. Fails ifedge
is null, or is otherwise not an element of this graph.- Specified by:
removeEdge
in interfaceHypergraph<V,
E> - Parameters:
edge
- the edge to remove- Returns:
true
if the removal is successful,false
otherwise
-