Interface Hypergraph<V,E>
- All Known Subinterfaces:
DirectedGraph<V,
,E> Forest<V,
,E> Graph<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
,SetHypergraph
,SortedSparseMultigraph
,SparseGraph
,SparseMultigraph
,UndirectedOrderedSparseMultigraph
,UndirectedSparseGraph
,UndirectedSparseMultigraph
V
and a set of hyperedges of type E
which connect the vertices.
This is the base interface for all JUNG graph types.
This interface permits, but does not enforce, any of the following common variations of graphs:
- hyperedges (edges which connect a set of vertices of any size)
- edges (these have have exactly two endpoints, which may or may not be distinct)
- self-loops (edges which connect exactly one vertex)
- directed and undirected edges
- vertices and edges with attributes (for example, weighted edges)
- vertices and edges with different constraints or properties (for example, bipartite or multimodal graphs)
- parallel edges (multiple edges which connect a single set of vertices)
- internal representations as matrices or as adjacency lists or adjacency maps
Notes:
- The collections returned by
Hypergraph
instances should be treated in general as if read-only. While they are not contractually guaranteed (or required) to be immutable, this interface does not define the outcome if they are mutated. Mutations should be done via{add,remove}{Edge,Vertex}
, or in the constructor.
-
Method Summary
Modifier and TypeMethodDescriptionboolean
addEdge
(E edge, Collection<? extends V> vertices) Addsedge
to this graph.boolean
addEdge
(E edge, Collection<? extends V> vertices, EdgeType edge_type) Addsedge
to this graph with typeedge_type
.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
.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
.Returns the default edge type for this graph.Ifdirected_edge
is a directed edge in this graph, returns the destination; otherwise returnsnull
.int
Returns the number of edges in this graph.int
getEdgeCount
(EdgeType edge_type) Returns the number of edges of typeedge_type
in this graph.getEdges()
Returns a view of all edges in this graph.Returns the collection of edges in this graph which are of typeedge_type
.getEdgeType
(E edge) Returns the edge type ofedge
in this graph.int
getIncidentCount
(E edge) Returns the number of vertices that are incident toedge
.getIncidentEdges
(V vertex) Returns the collection of edges in this graph which are connected tovertex
.getIncidentVertices
(E edge) Returns the collection of vertices in this graph which are connected toedge
.getInEdges
(V vertex) Returns aCollection
view of the incoming edges incident tovertex
in this graph.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).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.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.int
Returns the number of outgoing edges incident tovertex
.boolean
removeEdge
(E edge) Removesedge
from this graph.boolean
removeVertex
(V vertex) Removesvertex
from this graph.
-
Method Details
-
getEdges
Collection<E> getEdges()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.- Returns:
- a
Collection
view of all edges in this graph
-
getVertices
Collection<V> getVertices()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.- Returns:
- a
Collection
view of all vertices in this graph
-
containsVertex
Returns true if this graph's vertex collection containsvertex
. Equivalent togetVertices().contains(vertex)
.- Parameters:
vertex
- the vertex whose presence is being queried- Returns:
- true iff this graph contains a vertex
vertex
-
containsEdge
Returns true if this graph's edge collection containsedge
. Equivalent togetEdges().contains(edge)
.- Parameters:
edge
- the edge whose presence is being queried- Returns:
- true iff this graph contains an edge
edge
-
getEdgeCount
int getEdgeCount()Returns the number of edges in this graph.- Returns:
- the number of edges in this graph
-
getVertexCount
int getVertexCount()Returns the number of vertices in this graph.- Returns:
- the number of vertices in this graph
-
getNeighbors
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.- 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
Returns the collection of edges in this graph which are connected tovertex
.- 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
-
getIncidentVertices
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.- 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
-
findEdge
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
.)- 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
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
.)- 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:
-
addVertex
Addsvertex
to this graph. Fails ifvertex
is null or already in the graph.- Parameters:
vertex
- the vertex to add- Returns:
true
if the add is successful, andfalse
otherwise- Throws:
IllegalArgumentException
- ifvertex
isnull
-
addEdge
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
- Parameters:
edge
- the edge to addvertices
- the vertices to which the edge will be connected- Returns:
true
if the add is successful, andfalse
otherwise- Throws:
IllegalArgumentException
- ifedge
orvertices
is null, or if a different vertex set in this graph is already connected byedge
, or ifvertices
are not a legal vertex set foredge
-
addEdge
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
- Parameters:
edge
- edge to add to this graphvertices
- vertices which are to be connected by this edgeedge_type
- type of edge to add- Returns:
true
if the add is successful, andfalse
otherwise- Throws:
IllegalArgumentException
- ifedge
orvertices
is null, or if a different vertex set in this graph is already connected byedge
, or ifvertices
are not a legal vertex set foredge
-
removeVertex
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
- Parameters:
vertex
- the vertex to remove- Returns:
true
if the removal is successful,false
otherwise
-
removeEdge
Removesedge
from this graph. Fails ifedge
is null, or is otherwise not an element of this graph.- Parameters:
edge
- the edge to remove- Returns:
true
if the removal is successful,false
otherwise
-
isNeighbor
Returnstrue
ifv1
andv2
share an incident edge. Equivalent togetNeighbors(v1).contains(v2)
.- Parameters:
v1
- the first vertex to testv2
- the second vertex to test- Returns:
true
ifv1
andv2
share an incident edge
-
isIncident
Returnstrue
ifvertex
andedge
are incident to each other. Equivalent togetIncidentEdges(vertex).contains(edge)
and togetIncidentVertices(edge).contains(vertex)
.- Parameters:
vertex
- vertex to testedge
- edge to test- Returns:
true
ifvertex
andedge
are incident to each other
-
degree
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()
.- Parameters:
vertex
- the vertex whose degree is to be returned- Returns:
- the degree of this node
- See Also:
-
getNeighborCount
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()
.- Parameters:
vertex
- the vertex whose neighbor count is to be returned- Returns:
- the number of neighboring vertices
-
getIncidentCount
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()
.- Parameters:
edge
- the edge whose incident vertex count is to be returned- Returns:
- the number of vertices that are incident to
edge
.
-
getEdgeType
Returns the edge type ofedge
in this graph.- Parameters:
edge
- the edge whose type is to be returned- Returns:
- the
EdgeType
ofedge
, ornull
ifedge
has no defined type
-
getDefaultEdgeType
EdgeType getDefaultEdgeType()Returns the default edge type for this graph.- Returns:
- the default edge type for this graph
-
getEdges
Returns the collection of edges in this graph which are of typeedge_type
.- Parameters:
edge_type
- the type of edges to be returned- Returns:
- the collection of edges which are of type
edge_type
, ornull
if the graph does not accept edges of this type - See Also:
-
getEdgeCount
Returns the number of edges of typeedge_type
in this graph.- Parameters:
edge_type
- the type of edge for which the count is to be returned- Returns:
- the number of edges of type
edge_type
in this graph
-
getInEdges
Returns aCollection
view of the incoming edges incident tovertex
in this graph.- 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
Returns aCollection
view of the outgoing edges incident tovertex
in this graph.- Parameters:
vertex
- the vertex whose outgoing edges are to be returned- Returns:
- a
Collection
view of the outgoing edges incident tovertex
in this graph
-
inDegree
Returns the number of incoming edges incident tovertex
. Equivalent togetInEdges(vertex).size()
.- Parameters:
vertex
- the vertex whose indegree is to be calculated- Returns:
- the number of incoming edges incident to
vertex
-
outDegree
Returns the number of outgoing edges incident tovertex
. Equivalent togetOutEdges(vertex).size()
.- Parameters:
vertex
- the vertex whose outdegree is to be calculated- Returns:
- the number of outgoing edges incident to
vertex
-
getSource
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
.- 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
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
.- 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
-
getPredecessors
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
.- Parameters:
vertex
- the vertex whose predecessors are to be returned- Returns:
- a
Collection
view of the predecessors ofvertex
in this graph
-
getSuccessors
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
.- Parameters:
vertex
- the vertex whose predecessors are to be returned- Returns:
- a
Collection
view of the successors ofvertex
in this graph
-