Graph Class
A graph consisting of a set of vertices of type V
set and a set of edges of type E
. 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
Item Index
Methods
 addEdge
 addHyperEdge
 addVertex
 containsEdge
 containsVertex
 degree
 findEdge
 findEdgeSet
 getDefaultEdgeType
 getDest
 getEdgeCount
 getEdgeCountOfType
 getEdges
 getEdgesOfType
 getEdgeType
 getIncidentCount
 getIncidentEdges
 getIncidentVertices
 getInEdges
 getNeighborCount
 getNeighbors
 getOpposite
 getOutEdges
 getPredecessorCount
 getPredecessors
 getSource
 getSuccessorCount
 getSuccessors
 getVertexCount
 getVerticies
 inDegree
 isIncident
 isNeighbor
 isPredecessor
 isSource
 isSuccessor
 outDegree
 removeEdge
 removeVertex
Methods
addEdge

e

v1

v2
Adds edge e
to this graph such that it connects
vertex v1
to v2
.
Equivalent to addEdge(e, new Pair
.
If this graph does not contain v1
, v2
,
or both, implementations may choose to either silently add
the vertices to the graph or throw an IllegalArgumentException
.
If this graph assigns edge types to its edges, the edge type of
e
will be the default for this graph.
See Hypergraph.addEdge()
for a listing of possible reasons
for failure.
Parameters:

e
Objectthe edge to be added

v1
Objectthe first vertex to be connected

v2
Objectthe second vertex to be connected
Returns:
true
if the add is successful, false
otherwise
addHyperEdge

edge

vertices
Adds edge
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
Object 
vertices
Object
Returns:
true
if the add is successful, and
false
otherwise
Throws:
IllegalArgumentException if edge
or vertices
is null, or if
a different vertex set in this graph is already connected by
edge
, or if vertices
are not a
legal vertex set for edge
addVertex

vertex
Adds vertex
to this graph. Fails if vertex
is
null or already in the graph.
Parameters:

vertex
Objectthe vertex to add
Returns:
true
if the add is successful, and
false
otherwise
Throws:
IllegalArgumentException if vertex
is null
containsEdge

edge
Returns true if this graph's edge collection contains edge
.
Equivalent to getEdges().contains(edge)
.
Parameters:

edge
Objectthe edge whose presence is being queried
Returns:
true iff this graph contains an edge edge
containsVertex

vertex
Returns true if this graph's vertex collection contains
vertex
. Equivalent to
getVertices().contains(vertex)
.
Parameters:

vertex
Objectthe vertex whose presence is being queried
Returns:
true iff this graph contains a vertex vertex
degree

vertex
Returns the number of edges incident to vertex
. Special
cases of interest:
 Incident selfloops 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 selfloops (to avoid doublecounting).
Equivalent to getIncidentEdges(vertex).size()
.
Parameters:

vertex
Objectthe vertex whose degree is to be returned
Returns:
the degree of this node
findEdge

v1

v2
Returns an edge that connects this vertex to v
. If this edge
is not uniquely defined (that is, if the graph contains more than one
edge connecting v1
to v2
), 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 to v2
via a given directed
edge e
if
v1 == e.getSource() && v2 == e.getDest()
evaluates to
true
. (v1
and v2
are connected by
an undirected edge u
if u
is incident to both
v1
and v2
.)
Parameters:

v1
Objectbetween this

v2
Objectand that
Returns:
an edge that connects v1
to v2
, or
null
if no such edge exists (or either vertex is not
present)
findEdgeSet

v1

v2
Returns all edges that connects this vertex to v
. If this
edge is not uniquely defined (that is, if the graph contains more than
one edge connecting v1
to v2
), any of these
edges may be returned. findEdgeSet(v1, v2)
may be used to
return all such edges. Returns null if v2
is not connected
to v1
.
Returns an empty collection if either v1
or v2
are not present in this graph.
Note: for purposes of this method, v1
is only
considered to be connected to v2
via a given directed
edge d
if
v1 == d.getSource() && v2 == d.getDest()
evaluates to
true
. (v1
and v2
are connected by
an undirected edge u
if u
is incident to both
v1
and v2
.)
Parameters:

v1
Objectbetween this

v2
Objectand that
Returns:
a collection containing all edges that connect v1
to
v2
, or null
if either vertex is not
present
getDefaultEdgeType
()
Returns the default edge type for this graph.
Returns:
the default edge type for this graph
getDest

directed_edge
If directed_edge
is a directed edge in this graph, returns the destination;
otherwise returns null
.
The destination of a directed edge d
is defined to be the vertex
incident to d
for which
d
is an incoming edge.
directed_edge
is guaranteed to be a directed edge if
its EdgeType
is DIRECTED
.
Parameters:

directed_edge
Object
Returns:
the destination of directed_edge
if it is a directed edge in this graph, or null
otherwise
getEdgeCount
()
Returns the number of edges in this graph.
Returns:
the number of edges in this graph
getEdgeCountOfType

edge_type
Returns the number of edges of type edge_type
in this graph.
Parameters:

edge_type
Objectthe type of edge for which the count is to be returned
Returns:
the number of edges of type edge_type
in this graph
getEdges
()
Returns a view of all edges in this graph. In general, this obeys the
Array
contract, and therefore makes no guarantees about the
ordering of the vertices within the set.
Returns:
a Array
view of all edges in this graph
getEdgesOfType

edge_type
Returns the collection of edges in this graph which are of type
edge_type
.
Parameters:

edge_type
Objectthe type of edges to be returned
Returns:
the collection of edges which are of type edge_type
,
or null
if the graph does not accept edges of this
type
getEdgeType

edge
Returns the edge type of edge
in this graph.
Parameters:

edge
Object
Returns:
the EdgeType
of edge
, or
null
if edge
has no defined type
getIncidentCount

edge
Returns the number of vertices that are incident to edge
.
For hyperedges, this can be any nonnegative integer; for edges this must
be 2 (or 1 if selfloops are permitted).
Equivalent to getIncidentVertices(edge).size()
.
Parameters:

edge
Objectthe edge whose incident vertex count is to be returned
Returns:
the number of vertices that are incident to edge
.
getIncidentEdges

vertex
Returns the collection of edges in this graph which are connected to
vertex
.
Parameters:

vertex
Objectthe vertex whose incident edges are to be returned
Returns:
the collection of edges which are connected to
vertex
, or null
if vertex
is not present
getIncidentVertices

edge
Returns the collection of vertices in this graph which are connected to
edge
. 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
Objectthe edge whose incident vertices are to be returned
Returns:
the collection of vertices which are connected to
edge
, or null
if edge
is
not present
getInEdges

vertex
Returns a Collection
view of the incoming edges incident to vertex
in this graph.
Parameters:

vertex
Objectthe vertex whose incoming edges are to be returned
Returns:
a Collection
view of the incoming edges incident
to vertex
in this graph
getNeighborCount

vertex
Returns the number of vertices that are adjacent to vertex
(that is, the number of vertices that are incident to edges in
vertex
's incident edge set).
Equivalent to getNeighbors(vertex).size()
.
Parameters:

vertex
Objectthe vertex whose neighbor count is to be returned
Returns:
the number of neighboring vertices
getNeighbors

vertex
Returns the collection of vertices which are connected to
vertex
via any edges in this graph. If vertex
is connected to itself with a selfloop, then it will be included in the
collection returned.
Parameters:

vertex
Objectthe vertex whose neighbors are to be returned
Returns:
the collection of vertices which are connected to
vertex
, or null
if vertex
is not present
getOpposite

vertex

edge
Returns the vertex at the other end of edge
from vertex
.
(That is, returns the vertex incident to edge
which is not vertex
.)
Parameters:

vertex
Objectthe vertex to be queried

edge
Objectthe edge to be queried
Returns:
the vertex at the other end of edge
from vertex
getOutEdges

vertex
Returns a Collection
view of the outgoing edges incident to vertex
in this graph.
Parameters:

vertex
Objectthe vertex whose outgoing edges are to be returned
Returns:
a Collection
view of the outgoing edges incident
to vertex
in this graph
getPredecessorCount

vertex
Returns the number of predecessors that vertex
has in this graph.
Equivalent to vertex.getPredecessors().size()
.
Parameters:

vertex
Objectthe vertex whose predecessor count is to be returned
Returns:
the number of predecessors that vertex
has in this graph
getPredecessors

vertex
Returns a Collection
view of the predecessors of vertex
in this graph. A predecessor of vertex
is defined as a vertex v
which is connected to
vertex
by an edge e
, where e
is an outgoing edge of
v
and an incoming edge of vertex
.
Parameters:

vertex
Objectthe vertex whose predecessors are to be returned
Returns:
a Collection
view of the predecessors of
vertex
in this graph
getSource

directed_edge
If directed_edge
is a directed edge in this graph, returns the source;
otherwise returns null
.
The source of a directed edge d
is defined to be the vertex for which
d
is an outgoing edge.
directed_edge
is guaranteed to be a directed edge if
its EdgeType
is DIRECTED
.
Parameters:

directed_edge
Object
Returns:
the source of directed_edge
if it is a directed edge in this graph, or null
otherwise
getSuccessorCount

vertex
Returns the number of successors that vertex
has in this graph.
Equivalent to vertex.getSuccessors().size()
.
Parameters:

vertex
Objectthe vertex whose successor count is to be returned
Returns:
the number of successors that vertex
has in this graph
getSuccessors

vertex
Returns a Collection
view of the successors of vertex
in this graph. A successor of vertex
is defined as a vertex v
which is connected to
vertex
by an edge e
, where e
is an incoming edge of
v
and an outgoing edge of vertex
.
Parameters:

vertex
Objectthe vertex whose predecessors are to be returned
Returns:
a Collection
view of the successors of
vertex
in this graph
getVertexCount
()
Returns the number of vertices in this graph.
Returns:
the number of vertices in this graph
getVerticies
()
Returns a view of all vertices in this graph. In general, this obeys the
Array
contract, and therefore makes no guarantees about the
ordering of the vertices within the set.
Returns:
a Array
view of all vertices in this graph
inDegree

vertex
Returns the number of incoming edges incident to vertex
.
Equivalent to getInEdges(vertex).size()
.
Parameters:

vertex
Objectthe vertex whose indegree is to be calculated
Returns:
the number of incoming edges incident to vertex
isIncident

vertex

edge
Returns true
if vertex
and edge
are incident to each other. Equivalent to
getIncidentEdges(vertex).contains(edge)
and to
getIncidentVertices(edge).contains(vertex)
.
Parameters:

vertex
Object 
edge
Object
Returns:
true
if vertex
and edge
are incident to each other
isNeighbor

v1

v2
Returns true
if v1
and v2
share an
incident edge. Equivalent to getNeighbors(v1).contains(v2)
.
Parameters:

v1
Objectthe first vertex to test

v2
Objectthe second vertex to test
Returns:
true
if v1
and v2
share an
incident edge
isPredecessor

v1

v2
Returns true
if v1
is a predecessor of v2
in this graph.
Equivalent to v1.getPredecessors().contains(v2)
.
Parameters:

v1
Objectthe first vertex to be queried

v2
Objectthe second vertex to be queried
Returns:
true
if v1
is a predecessor of v2
, and false otherwise.
isSource

vertex

edge
Returns true
if vertex
is the source of edge
.
Equivalent to getSource(edge).equals(vertex)
.
Parameters:

vertex
Objectthe vertex to be queried

edge
Objectthe edge to be queried
Returns:
true
iff vertex
is the source of edge
isSuccessor

v1

v2
Returns true
if v1
is a successor of v2
in this graph.
Equivalent to v1.getSuccessors().contains(v2)
.
Parameters:

v1
Objectthe first vertex to be queried

v2
Objectthe second vertex to be queried
Returns:
true
if v1
is a successor of v2
, and false otherwise.
outDegree

vertex
Returns the number of outgoing edges incident to vertex
.
Equivalent to getOutEdges(vertex).size()
.
Parameters:

vertex
Objectthe vertex whose outdegree is to be calculated
Returns:
the number of outgoing edges incident to vertex
removeEdge

edge
Removes edge
from this graph. Fails if edge
is
null, or is otherwise not an element of this graph.
Parameters:

edge
Objectthe edge to remove
Returns:
true
if the removal is successful,
false
otherwise
removeVertex

vertex
Removes vertex
from this graph. As a side effect, removes
any edges e
incident to vertex
if the removal
of vertex
would cause e
to be incident to an
illegal number of vertices. (Thus, for example, incident hyperedges are
not removed, but incident edgeswhich must be connected to a vertex at
both endpointsare removed.)
Fails under the following circumstances:
vertex
is not an element of this graphvertex
isnull
Parameters:

vertex
Objectthe vertex to remove
Returns:
true
if the removal is successful,
false
otherwise