Package squidpony.squidai.graph

Class Graph<V>

java.lang.Object

squidpony.squidai.graph.Graph<V>

Type Parameters:

V - the vertex type; often Coord

Direct Known Subclasses:

DirectedGraph, UndirectedGraph

public abstract class Graph<V>
extends Object

Abstract superclass of actual Graph types, like DirectedGraph and UndirectedGraph.

Author:

earlygrey

Field Summary

Fields

Modifier and Type	Field	Description
protected OrderedMap<Connection<V>,Connection<V>>	edgeMap
protected OrderedMap<V,Node<V>>	vertexMap

Constructor Summary

Constructors

Modifier	Constructor	Description
protected	Graph()
protected	Graph(Collection<V> vertices)

Method Summary

Modifier and Type	Method	Description
protected Connection<V>	addConnection(Node<V> a, Node<V> b)
protected Connection<V>	addConnection(Node<V> a, Node<V> b, float weight)
Connection<V>	addEdge(V v, V w)	Add an edge to the graph, from v to w.
Connection<V>	addEdge(V v, V w, float weight)	Add an edge to the graph, from v to w and with the specified weight.
boolean	addVertex(V v)	Adds a vertex to the graph.
void	addVertices(Collection<V> vertices)	Adds all the vertices in the collection to the graph.
abstract Algorithms<V>	algorithms()
protected boolean	connectionExists(Node<V> u, Node<V> v)
boolean	contains(V v)	Check if the graph contains a vertex.
protected abstract Graph<V>	createNew()
boolean	edgeExists(V v, V w)	Check if the graph contains an edge from v to w.
protected Connection<V>	getEdge(Node<V> a, Node<V> b)
Edge<V>	getEdge(V v, V w)	Retrieve the edge which is from v to w.
int	getEdgeCount()	Get the number of edges in the graph.
SortedSet<? extends Edge<V>>	getEdges()	Get a collection containing all the edges in the graph.
List<? extends Edge<V>>	getEdges(V v)	Get a collection containing all the edges which have v as a source.
protected Node<V>	getNode(V v)
protected Collection<Node<V>>	getNodes()
SortedSet<V>	getVertices()	Get a collection containing all the vertices in the graph.
boolean	isDirected()	Check if the graph is directed, that is whether the edges form an ordered pair or a set.
protected abstract Connection<V>	obtainEdge()
void	removeAllEdges()	Removes all edges from the graph.
void	removeAllVertices()	Removes all vertices and edges from the graph.
protected boolean	removeConnection(Node<V> a, Node<V> b)
boolean	removeEdge(Edge<V> edge)
boolean	removeEdge(V v, V w)	Removes the edge from v to w from the graph.
protected void	removeNode(Node<V> node)
boolean	removeVertex(V v)	Removes a vertex from the graph, and any adjacent edges.
void	removeVertices(Collection<V> vertices)	Removes all the vertices in the collection from the graph, and any adjacent edges.
int	size()	Get the number of vertices in the graph.
void	sortEdges(Comparator<Connection<V>> comparator)	Sort the edges using the provided comparator.
void	sortVertices(Comparator<V> comparator)	Sort the vertices using the provided comparator.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Details

vertexMap

protected final OrderedMap<V,Node<V>> vertexMap

edgeMap

protected final OrderedMap<Connection<V>,Connection<V>> edgeMap

Constructor Details

Graph

protected Graph()

Graph

protected Graph(Collection<V> vertices)

Method Details

obtainEdge

protected abstract Connection<V> obtainEdge()

createNew

protected abstract Graph<V> createNew()

algorithms

public abstract Algorithms<V> algorithms()

addVertex

public boolean addVertex(V v)

Adds a vertex to the graph.

Parameters:

v - the vertex to be added

Returns:

true if the vertex was not already in the graph, false otherwise

addVertices

public void addVertices(Collection<V> vertices)

Adds all the vertices in the collection to the graph.

Parameters:

vertices - a collection of vertices to be added

removeVertex

public boolean removeVertex(V v)

Removes a vertex from the graph, and any adjacent edges.

Parameters:

v - the vertex to be removed

Returns:

true if the vertex was in the graph, false otherwise

removeVertices

public void removeVertices(Collection<V> vertices)

Removes all the vertices in the collection from the graph, and any adjacent edges.

Parameters:

vertices - vertices a collection of vertices to be removed

addEdge

public Connection<V> addEdge(V v, V w)

Add an edge to the graph, from v to w. The edge will have a default weight of 1. If there is already an edge between v and w, its weight will be set to 1.

Parameters:

v - the source vertex of the edge

w - the destination vertex of the edge

Returns:

the edge

addEdge

public Connection<V> addEdge(V v, V w, float weight)

Add an edge to the graph, from v to w and with the specified weight. If there is already an edge between v and w, its weight will be set to the specified weight.

Parameters:

v - the source vertex of the edge

w - the destination vertex of the edge

weight - the weight of the edge

Returns:

the edge

removeEdge

public boolean removeEdge(V v, V w)

Removes the edge from v to w from the graph.

Parameters:

v - the source vertex of the edge

w - the destination vertex of the edge

Returns:

the edge if there exists an edge from v to w, or null if there is no edge

removeEdge

public boolean removeEdge(Edge<V> edge)

removeAllEdges

public void removeAllEdges()

Removes all edges from the graph.

removeAllVertices

public void removeAllVertices()

Removes all vertices and edges from the graph.

sortVertices

public void sortVertices(Comparator<V> comparator)

Sort the vertices using the provided comparator. This is reflected in the iteration order of the collection returned by getVertices(), as well as algorithms which involve iterating over all vertices.

Parameters:

comparator - a comparator for comparing vertices

sortEdges

public void sortEdges(Comparator<Connection<V>> comparator)

Sort the edges using the provided comparator. This is reflected in the iteration order of the collection returned by getEdges(), as well as algorithms which involve iterating over all edges.

Parameters:

comparator - a comparator for comparing edges

removeNode

protected void removeNode(Node<V> node)

addConnection

protected Connection<V> addConnection(Node<V> a, Node<V> b)

addConnection

protected Connection<V> addConnection(Node<V> a, Node<V> b, float weight)

removeConnection

protected boolean removeConnection(Node<V> a, Node<V> b)

contains

public boolean contains(V v)

Check if the graph contains a vertex.

Parameters:

v - the vertex with which to check

Returns:

true if the graph contains the vertex, false otherwise

getEdge

public Edge<V> getEdge(V v, V w)

Retrieve the edge which is from v to w.

Parameters:

v - the source vertex of the edge

w - the destination vertex of the edge

Returns:

the edge if it is in the graph, otherwise null

edgeExists

public boolean edgeExists(V v, V w)

Check if the graph contains an edge from v to w.

Parameters:

v - the source vertex of the edge

w - the destination vertex of the edge

Returns:

true if the edge is in the graph, false otherwise

getEdges

public List<? extends Edge<V>> getEdges(V v)

Get a collection containing all the edges which have v as a source.

Parameters:

v - the source vertex of all the edges

Returns:

an unmodifiable collection of edges

getEdges

public SortedSet<? extends Edge<V>> getEdges()

Get a collection containing all the edges in the graph.

Returns:

an unmodifiable collection of all the edges in the graph

getVertices

public SortedSet<V> getVertices()

Get a collection containing all the vertices in the graph.

Returns:

an unmodifiable collection of all the vertices in the graph

isDirected

public boolean isDirected()

Check if the graph is directed, that is whether the edges form an ordered pair or a set.

Returns:

whether the graph is directed

size

public int size()

Get the number of vertices in the graph.

Returns:

the number of vertices

getEdgeCount

public int getEdgeCount()

Get the number of edges in the graph.

Returns:

the number of edges

getNode

protected Node<V> getNode(V v)

getNodes

protected Collection<Node<V>> getNodes()

connectionExists

protected boolean connectionExists(Node<V> u, Node<V> v)

getEdge

protected Connection<V> getEdge(Node<V> a, Node<V> b)