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>
,java.io.Serializable
- Direct Known Subclasses:
AbstractTypedGraph
,SparseGraph
,SparseMultigraph
public abstract class AbstractGraph<V,E> extends java.lang.Object implements Graph<V,E>, java.io.Serializable
Abstract implementation of theGraph
interface. Designed to simplify implementation of new graph classes.- Author:
- Joshua O'Madadhain
- See Also:
- Serialized Form
-
-
Constructor Summary
Constructors Constructor Description AbstractGraph()
-
Method Summary
All Methods Instance Methods Abstract Methods Concrete Methods Modifier and Type Method Description boolean
addEdge(E edge, Pair<? extends V> endpoints)
Addsedge
to this graph with the specifiedendpoints
, with the default edge type.abstract boolean
addEdge(E edge, Pair<? extends V> endpoints, EdgeType edgeType)
Addsedge
to this graph with the specifiedendpoints
andEdgeType
.boolean
addEdge(E edge, java.util.Collection<? extends V> vertices)
Addsedge
to this graph.boolean
addEdge(E edge, java.util.Collection<? extends V> vertices, EdgeType edgeType)
Addsedge
to this graph with typeedge_type
.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 edge_type)
Adds edgee
to this graph such that it connects vertexv1
tov2
.int
degree(V vertex)
Returns the number of edges incident tovertex
.E
findEdge(V v1, V v2)
Returns an edge that connects this vertex tov
.java.util.Collection<E>
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
.java.util.Collection<V>
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).V
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.protected Pair<V>
getValidatedEndpoints(E edge, Pair<? extends V> endpoints)
int
inDegree(V vertex)
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
outDegree(V vertex)
Returns the number of outgoing edges incident tovertex
.java.lang.String
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
-
-
-
-
Method Detail
-
addEdge
public boolean addEdge(E edge, java.util.Collection<? extends V> vertices)
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
public boolean addEdge(E edge, java.util.Collection<? extends V> vertices, EdgeType edgeType)
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
public boolean addEdge(E e, V v1, V v2)
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.- Specified by:
addEdge
in interfaceGraph<V,E>
- 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)
,Graph.addEdge(Object, Object, Object, EdgeType)
-
addEdge
public boolean addEdge(E e, V v1, V v2, EdgeType edge_type)
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.- Specified by:
addEdge
in interfaceGraph<V,E>
- Parameters:
e
- the edge to be addedv1
- the first vertex to be connectedv2
- the second vertex to be connectededge_type
- the type to be assigned to the edge- Returns:
true
if the add is successful,false
otherwise- See Also:
Hypergraph.addEdge(Object, Collection)
,Graph.addEdge(Object, Object, Object)
-
addEdge
public boolean addEdge(E edge, Pair<? extends V> endpoints)
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
public abstract boolean addEdge(E edge, Pair<? extends V> endpoints, EdgeType edgeType)
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
-
inDegree
public int inDegree(V vertex)
Description copied from interface:Graph
Returns the number of incoming edges incident tovertex
. Equivalent togetInEdges(vertex).size()
.
-
outDegree
public int outDegree(V vertex)
Description copied from interface:Graph
Returns the number of outgoing edges incident tovertex
. Equivalent togetOutEdges(vertex).size()
.
-
isPredecessor
public boolean isPredecessor(V v1, V v2)
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
public boolean isSuccessor(V v1, V v2)
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
public int getPredecessorCount(V vertex)
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
public int getSuccessorCount(V vertex)
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
public boolean isNeighbor(V v1, V v2)
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
public boolean isIncident(V vertex, E edge)
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
public int getNeighborCount(V vertex)
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
public int degree(V vertex)
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:
Hypergraph.getNeighborCount(Object)
-
getIncidentCount
public int getIncidentCount(E edge)
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
public V getOpposite(V vertex, E edge)
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
public E findEdge(V v1, V v2)
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:
Hypergraph.findEdgeSet(Object, Object)
-
findEdgeSet
public java.util.Collection<E> findEdgeSet(V v1, V v2)
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:
Hypergraph.findEdge(Object, Object)
-
getIncidentVertices
public java.util.Collection<V> getIncidentVertices(E edge)
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
public java.lang.String toString()
- Overrides:
toString
in classjava.lang.Object
-
-