public class Graph
extends java.lang.Object
Graph
class. This is the main class for the
graph theory library.
A graph is an ordered pair of sets (V, E), where V is a set of Vertices
and can be any set. E is a set of 2-element subsets of V, called Edges.
This class allows for the modeling of Graph objects.
This class also contains several static methods for performing operations
on graphs and creating certain types of graphs.
This library is meant to provide simple ways to visualize graphs and
graph theory algorithms. Graph data structures can also be used to model
many things.Modifier and Type | Class and Description |
---|---|
static class |
Graph.DisjointSet<E>
This is the
DisjointSet class. |
Constructor and Description |
---|
Graph()
This is the constructor for
Graph objects. |
Modifier and Type | Method and Description |
---|---|
void |
addEdge(Edge e)
This adds the given
Edge to the Graph .
This also adds the Edge's vertices if they are not in the Graph . |
void |
addEdge(Vertex a,
Vertex b)
This creates a new
Edge connecting the two
given vertices and adds it to the set of Edges.
If either of the two vertices of the new Edge are not in this
Graph , then they are also added. |
void |
addVertex(Vertex v)
Adds a vertex to the TreeSet of Vertices or does nothing if
the vertex is already in the graph.
|
void |
clearEdges()
This clears the set of Edges.
|
void |
clearVertices()
This clears all the vertices in the graph.
This also clears all of the edges, because the edges cannot
exist in the absense of vertices.
|
boolean |
containsEdge(Edge e)
This tests to see if the
Graph contains the given edge. |
boolean |
containsVertex(Vertex v)
Searches the
Graph for the given Vertex . |
java.util.TreeSet<Edge> |
getEdges()
Returns the TreeSet of edges.
|
java.util.TreeSet<Vertex> |
getVertices()
Returns the TreeSet of vertices.
|
static Graph |
minimalSpanningTree(java.util.Collection<Vertex> vertices)
This is an implementation of Kruskal's Algorithm for finding the minimal
spanning tree for the given collection of Vertex objects.
This will return a minimal spanning tree for the complete graph that
contains these vertices.
|
static Graph |
minimalSpanningTree(Graph g)
This is an implementation of Kruskal's Algorithm for finding the minimal
spanning tree of a graph.
This will work for disconnected graphs, but it will return a Graph
which contains multiple distinct trees.
|
static Graph |
randomCompleteGraph(int numberOfVertices,
processing.core.PApplet parent)
This will generate a complete
Graph with the specified
number of vertices that are randomly distributed so that the coordinates
of each vertex lie somewhere on the canvas of the parent
PApplet . |
void |
removeEdge(Edge e)
This removes the
Edge from the set
of edges if it exists in the Graph . |
void |
removeEdge(Vertex a,
Vertex b)
This removes the
Edge containing the two vertices from the set
of edges if it exists in the Graph . |
void |
removeVertex(Vertex v)
Removes the
Vertex from the Graph if it is
present, or does nothing if it is not present. |
static Graph |
spanningTree(Graph graph,
Vertex initialVertex)
This is a breadth-first algorithm for finding a spanning
tree of the given
Graph starting from the specified
Vertex . |
static java.util.Collection<Triangle> |
toTriangles(java.util.Collection<Vertex> vertices)
This returns a list of triangles that make up the delaunay triangulation
of the vertices in the source
Graph . |
static java.util.Collection<Triangle> |
toTriangles(Graph graph)
This returns a list of triangles that make up the delaunay triangulation
of the vertices in the source
Graph . |
static Graph |
triangulatedGraph(java.util.Collection<Vertex> vertices)
This will return a delaunay triangulation of the collection of
vertices.
This uses the Triangulate library which can be found at: http://wiki.processing.org/w/Triangulation |
static Graph |
triangulatedGraph(Graph graph)
This will return a delaunay triangulation of the vertices in the
source graph.
This uses the Triangulate library which can be found at: http://wiki.processing.org/w/Triangulation Note: This method does not take the edges of the source graph into consideration. |
public void addVertex(Vertex v)
v
- the Vertex
public void removeVertex(Vertex v)
Vertex
from the Graph
if it is
present, or does nothing if it is not present. If the vertex is removed
all of the edges incident to it are also removed.v
- the Vertex
to be removed.public void clearVertices()
public boolean containsVertex(Vertex v)
Graph
for the given Vertex
.v
- the Vertex
in question.Vertex
is contained in this
Graph
.public void addEdge(Vertex a, Vertex b)
Edge
connecting the two
given vertices and adds it to the set of Edges.
If either of the two vertices of the new Edge
are not in this
Graph
, then they are also added.a
- the first Vertex
.b
- the second Vertex
.public void addEdge(Edge e)
Edge
to the Graph
.
This also adds the Edge's vertices if they are not in the Graph
.e
- the new Edge
to be added.public void removeEdge(Vertex a, Vertex b)
Edge
containing the two vertices from the set
of edges if it exists in the Graph
.a
- the first Vertex
in the Edge
.b
- the second Vertex
in the Edge
.public void removeEdge(Edge e)
Edge
from the set
of edges if it exists in the Graph
.e
- the Edge
to be removed.public void clearEdges()
public boolean containsEdge(Edge e)
Graph
contains the given edge.e
- the Edge
in question.true
if the Edge
is contained in the
Graph
.public java.util.TreeSet<Vertex> getVertices()
Vertex
objects that are the
vertices of the Graph
.public java.util.TreeSet<Edge> getEdges()
Edge
objects that are the
edges of the Graph
.public static Graph randomCompleteGraph(int numberOfVertices, processing.core.PApplet parent)
Graph
with the specified
number of vertices that are randomly distributed so that the coordinates
of each vertex lie somewhere on the canvas of the parent
PApplet
.numberOfVertices
- The number of vertices.parent
- the PApplet
that is creating this
Graph
.Graph
.public static Graph minimalSpanningTree(Graph g)
g
- The source Graph
for the tree.public static Graph minimalSpanningTree(java.util.Collection<Vertex> vertices)
vertices
- A Collection
of Vertex
public static Graph spanningTree(Graph graph, Vertex initialVertex)
Graph
starting from the specified
Vertex
. The resulting tree contains all the vertices
in the original Graph
.
If this method is passed a complete graph, the spanning tree that
results will just be a Graph with Edges connecting the initial
Vertex to the rest of the Vertices in the source Graph.graph
- The source Graph
.initialVertex
- The initial Vertex
.public static Graph triangulatedGraph(Graph graph)
graph
- The source Graph
.Graph
.public static Graph triangulatedGraph(java.util.Collection<Vertex> vertices)
vertices
- A collection of Vertex objects to be triangulated.graph
that is a planar triangulation of the given
collection of vertices.public static java.util.Collection<Triangle> toTriangles(Graph graph)
Graph
.
This is identical to the triangulate() method of the Triangulation
library, which can be found here:
http://wiki.processing.org/w/Triangulationgraph
- The source Graph
.Triangle
objects that represent the
trianglulation of the source Graph
.public static java.util.Collection<Triangle> toTriangles(java.util.Collection<Vertex> vertices)
Graph
.
This is identical to the triangulate() method of the Triangulation
library, which can be found here:
http://wiki.processing.org/w/Triangulationvertices
- The collection of vertices to make up the triangulation.Triangle
objects that represent the
trianglulation of the source Graph
.