V
- the type of vertex that should be used in the graphE
- the type of edge that should be used in the graphpublic class Graph<V extends Vertex,E extends Edge>
extends java.lang.Object
add(Vertex)
or remove(Vertex)
. The caption of
a vertex is unique that means a graph can only contain vertices with different captions. If you try to add
a vertex "A" although there is already a vertex with the caption "A" then the vertex to add is ignored.getOrder()
and getVertex(int)
.
add(Edge)
or remove(Edge)
. A graph can contain loops but only has one edge between
any two vertices.getSize()
and getEdge(int)
or use getEdge(Vertex, Vertex)
to check
if there is an edge between two vertices.
MultiGraph
.SimpleGraph
to represent a graph that has no loops (edges connected at both ends to the same vertex) and
no more than one edge between any two different vertices.
Vertex.getIncomingEdge(int)
/Vertex.getOutgoingEdge(int)
to iterate over the graph.
Walk
or its possible variations Path
and Trail
.MultiGraph
,
SimpleGraph
,
GraphUtils
,
Walk
,
Path
,
Trail
Modifier and Type | Method and Description |
---|---|
boolean |
add(E edge)
Adds a new edge to the graph.
|
boolean |
add(V vertex)
Adds a new vertex to the graph.
|
protected void |
afterEdgeAdded(E edge)
Is invoked after a new edge is added to the graph.
|
protected void |
afterEdgeRemoved(E edge)
Is invoked after an edge is removed from the graph.
|
protected void |
afterVertexAdded(V vertex)
Is invoked after a new vertex is added to the graph.
|
protected void |
afterVertexRemoved(V vertex)
Is invoked after a vertex is removed from the graph.
|
protected void |
beforeEdgeAdded(E edge)
Is invoked before a new edge is added to the graph.
|
protected void |
beforeVertexAdded(V vertex)
Is invoked before a new vertex is added to the graph.
|
boolean |
contains(E edge)
Indicates if the graph contains the given edge.
|
boolean |
contains(V vertex)
Indicates if the graph contains the given vertex.
|
protected int |
containsEdge(E edge)
Checks if the graph already contains the given edge, that means if
getEdge(i).equalsIgnoreWeight(edge)
Notice: Override this method if you want to handle that multiple edges are allowed, etc. |
protected boolean |
containsVertex(V vertex)
Checks if the graph already contains the given vertex, that means if there is already a vertex in the graph
with the caption of the specified vertex.
|
boolean |
equals(Graph<V,E> graph)
Indicates whether the specified graph equals this graph.
|
boolean |
equals(java.lang.Object obj)
Indicates whether the specified graph equals this graph.
|
E |
getEdge(int index)
Gets the edge at the given index.
|
E |
getEdge(int v1,
int v2)
Gets the edge between the two vertices.
|
E |
getEdge(V v1,
V v2)
Gets the edge between the two vertices.
|
E |
getEdgeByID(int id)
Gets the edge with the specified id.
|
Set<java.lang.Integer> |
getEdgeByIDSet()
Gets the edge set containing the identifiers of all edges the graph consists of currently.
|
java.util.List<E> |
getEdges(int v1,
int v2)
Gets a list of all edges between the two vertices.
|
java.util.List<E> |
getEdges(V v1,
V v2)
Gets a list of all edges between the two vertices.
|
Set<E> |
getEdgeSet()
Gets the edge set of all edges the graph consists of currently.
|
int |
getOrder()
Gets the number of vertices in the graph.
|
int |
getSize()
Gets the number of edges in the graph.
|
Type |
getType()
Gets the type of the graph.
|
V |
getVertex(int index)
Gets the vertex at the given index.
|
V |
getVertexByCaption(java.lang.String caption)
Gets the vertex with the given caption.
|
V |
getVertexByID(int id)
Gets the vertex with the specified id.
|
Set<java.lang.Integer> |
getVertexByIDSet()
Gets the vertex set containing the identifiers of all vertices the graph consists of currently.
|
Set<V> |
getVertexSet()
Gets the vertex set of all vertices the graph consists of currently.
|
protected boolean |
isEdgeAllowed(E edge)
Checks if the given edge is allowed.
|
protected boolean |
isRemovable(E edge)
Indicates if the given edge may be removed.
|
protected boolean |
isRemovable(V vertex)
Indicates if the given vertex may be removed.
|
protected boolean |
isVertexAllowed(V vertex)
Checks if the given vertex is allowed.
|
boolean |
remove(E edge)
Removes an edge from the graph.
|
boolean |
remove(V vertex)
Removes a vertex from the graph.
|
void |
removeAll()
Removes all vertices and edges from the graph that are allowed to be removed.
|
java.lang.String |
toString() |
public Graph(Type type)
type
- the type of the graphpublic final Type getType()
public final int getOrder()
public final V getVertex(int index) throws java.lang.IndexOutOfBoundsException
index
- the indexjava.lang.IndexOutOfBoundsException
- index < 0 || index >= getOrder()
)public final V getVertexByCaption(java.lang.String caption)
caption
- the caption of the vertexnull
if there is no vertex with the specified captionpublic final V getVertexByID(int id)
id
- the identifiernull
if there is no vertex with the specified idpublic final int getSize()
public final E getEdge(int index) throws java.lang.IndexOutOfBoundsException
index
- the indexjava.lang.IndexOutOfBoundsException
- index < 0 || index >= getSize()
)public final E getEdgeByID(int id)
id
- the identifiernull
if there is no edge with the specified idpublic final E getEdge(int v1, int v2)
G = (V, E)
be a graph with V
as the set of vertices and E
as the set of edges and m
be the
adjacency matrix. then m(i,k) = edge
if (i,k)
is an element of E
and m(i,k) = null
if (i,k)
is not
an element of E
.v1
- the id of the first vertexv2
- the id of the second vertexnull
if there is no edge between v1 and v2 ((v1,v2)
is not an element of E
)public final E getEdge(V v1, V v2) throws java.lang.NullPointerException
G = (V, E)
be a graph with V
as the set of vertices and E
as the set of edges and m
be the
adjacency matrix. then m(i,k) = edge
if (i,k)
is an element of E
and m(i,k) = null
if (i,k)
is not
an element of E
.v1
- the first vertexv2
- the second vertexnull
if there is no edge between v1 and v2 ((v1,v2)
is not an element of E
)java.lang.NullPointerException
- getEdge(int, int)
public final java.util.List<E> getEdges(int v1, int v2)
getAll(v1,v2) == getAll(v2,v1)
otherwise
one has getAll(v1,v2) != getAll(v2,v1)
.v1
- the id of the first vertexv2
- the id of the second vertexnull
if there is no edge between the verticesgetEdge(int, int)
public final java.util.List<E> getEdges(V v1, V v2)
getAll(v1,v2) == getAll(v2,v1)
otherwise
one has getAll(v1,v2) != getAll(v2,v1)
.v1
- the first vertexv2
- the second vertexnull
if there is no edge between the verticesjava.lang.NullPointerException
- getEdge(Vertex, Vertex)
public final boolean add(V vertex)
vertex
- the vertextrue
if the vertex could be added otherwise false
(this could be if the vertex caption does already exist or is added to another graph before)public final boolean remove(V vertex)
vertex
- the vertextrue
if the vertex could be removed otherwise false
public final boolean add(E edge) throws java.lang.IllegalArgumentException
edge
- the edgetrue
if the edge could be added otherwise false
(this could be if the edge is added to another graph before)java.lang.IllegalArgumentException
- public final boolean remove(E edge)
edge
- the edgetrue
if the edge could be removed otherwise false
public final void removeAll()
public Set<java.lang.Integer> getVertexByIDSet()
getVertexByID(int)
public Set<V> getVertexSet()
public Set<java.lang.Integer> getEdgeByIDSet()
getEdgeByID(int)
public Set<E> getEdgeSet()
public boolean contains(V vertex)
vertex
- the vertextrue
if the graph contains the vertex otherwise false
public boolean contains(E edge)
edge
- the edgetrue
if the graph contains the edge otherwise false
public boolean equals(Graph<V,E> graph)
graph
- another graphtrue
if both graphs are equal otherwise false
public boolean equals(java.lang.Object obj)
equals
in class java.lang.Object
obj
- another graph of the same typetrue
if both graphs are equal otherwise false
public java.lang.String toString()
toString
in class java.lang.Object
protected boolean containsVertex(V vertex)
vertex
- the vertextrue
if the vertex already exists otherwise false
protected int containsEdge(E edge)
getEdge(i).equalsIgnoreWeight(edge)
edge
- the edge-1
if the edge does not exist otherwise the index of the edge in the list of edgesprotected boolean isVertexAllowed(V vertex)
vertex
- the vertextrue
if the vertex is allowed otherwise false
protected boolean isEdgeAllowed(E edge)
edge
- the edgetrue
if the edge is allowed otherwise false
protected boolean isRemovable(V vertex)
vertex
- the vertextrue
if the vertex can be removed otherwise false
protected boolean isRemovable(E edge)
edge
- the edgetrue
if the edge can be removed otherwise false
protected void beforeVertexAdded(V vertex)
vertex
- the vertex that is addedprotected void beforeEdgeAdded(E edge)
edge
- the edge that is addedprotected void afterVertexAdded(V vertex)
vertex
- the vertex that is addedprotected void afterEdgeAdded(E edge)
edge
- the edge that is addedprotected void afterVertexRemoved(V vertex)
vertex
- the vertex that is removedprotected void afterEdgeRemoved(E edge)
edge
- the edge that is removed