game2dai.graph.Graph Class Reference

Classes
class	FloatingEdge

Public Member Functions
	Graph ()
	Graph (int nbrNodes)
double	distance (GraphNode nodeFrom, GraphNode nodeTo)
double	distance (int nodeFromID, int nodeToID)
void	addNode (GraphNode node)
boolean	removeNode (int nodeID)
GraphNode	getNode (int id)
boolean	hasNode (int id)
GraphNode	getNodeNear (double x, double y, double z, double maxDistance)
GraphNode	getNodeNear (double x, double y, double maxDistance)
GraphNode	getNodeNearest (GraphNode a_node)
GraphNode	getNodeNearest (int id)
GraphNode	getNodeNearest (double x, double y, double z)
GraphNode	getNodeNearest (double x, double y)
int	getNbrNodes ()
boolean	addEdge (int fromID, int toID, double cost)
boolean	addEdge (int fromID, int toID, double costOutward, double costInward)
void	compact ()
GraphEdge	getEdge (int fromID, int toID)
double	getEdgeCost (int fromID, int toID)
boolean	removeEdge (int fromID, int toID)
boolean	hasEdge (int from, int to)
LinkedList< GraphEdge >	getEdgeList (int nodeID)
LinkedList< GraphEdge >	getEdgeList (GraphNode node)
GraphEdge[]	getEdgeArray ()
GraphEdge[]	getEdgeArray (int from)
int	getNbrEdges ()
GraphNode[]	getNodeArray ()
String	toString ()

Static Public Member Functions
static Graph	makeFromXML (PApplet app, String xmlFilename)
static Graph	makeFromXML (String xmlFilename)
static Graph	makeFromXML (File xmlFile)

Protected Member Functions
void	resolveFloatEdges (GraphNode node)
void	addValidEdge (GraphEdge edge)
void	rememberFloatingEdge (int id, FloatingEdge floatEdge)

Protected Attributes
HashMap< Integer, GraphNode >	nodes
HashMap< GraphNode, LinkedList< GraphEdge > >	edgeLists
HashMap< Integer, LinkedList< FloatingEdge > >	nodesToBe

Package Functions
public< T extends GraphEdge > T[]	getEdgeArray (T[] array)
public< T extends GraphEdge > T[]	getEdgeArray (int from, T[] array)
public< T extends GraphNode > T[]	getNodeArray (T[] array)

Detailed Description

Objects of this class represents graphs that can be used in games.

The class maintains collections of nodes (vertices) and directed edges.

Each node should have a unique ID number, attempting to add a node which the same ID as a node already added to the graph will replace the existing node.

An edge is specified by the id numbers to the 2 nodes that are to be joined. Each edge is directed i.e. one-way, so to create a bidirectional (two-way) link between the nodes requires two edges to be created. This does have the advantage that each the cost of travelling between 2 nodes does not have to be the same in both directions.

It is more efficient to add all the nodes first and then the edges but not essential.

Attempting to add an edge where one or both of the connecting nodes do not yet exist in the graph will be 'remembered' - this is called a floating edge. Once both nodes have been added to the graph then the floating edge will also be added to the graph.
Floating edges are segregated from the graph edges to simply the graph searching algorithms.

This arrangement is very flexible and can simplify the code needed to create the graph at the expense of creating large numbers of floating edges that will never be added to the graph. Once you have created the final graph it is recommended that the user calls the compact method which simply deletes any floating edges and requests a garbage collection to release the memory.

The classes

See also

GraphNode

GraphEdge are the base classes used to store nodes and edges. These classes support inheritance so you can provide more specialised classes for your graphs.

The following classes can be used to search the graph.

See also

GraphSearch_DFS

GraphSearch_BFS

GraphSearch_Dijkstra

GraphSearch_Astar

Author

Peter Lager

Constructor & Destructor Documentation

Graph() [1/2]

game2dai.graph.Graph.Graph

(

)

Create a graph with an initial capacity of 16 nodes.

Graph() [2/2]

game2dai.graph.Graph.Graph

(

int

nbrNodes

)

Create a graph with an initial capacity based on an estimate of the number of nodes to be added.

Parameters

nbrNodes

Member Function Documentation

addEdge() [1/2]

boolean game2dai.graph.Graph.addEdge	(	int	fromID,
		int	toID,
		double	cost
	)

Add a unidirectional edge to the graph.

Parameters

fromID	the ID number of the from node
toID	the ID number of the to node
cost	cost from > to

Returns

true if the edge was added else false

addEdge() [2/2]

boolean game2dai.graph.Graph.addEdge	(	int	fromID,
		int	toID,
		double	costOutward,
		double	costInward
	)

Add bidirectional link with the costs indicated.

Parameters

fromID	the ID number of the from node
toID	the ID number of the to node
costOutward	cost from > to
costInward	cost to > from

Returns

true if the edge was added else false

addNode()

void game2dai.graph.Graph.addNode

(

GraphNode

node

)

Add a node to the list. The user must ensure that the node id is unique.

Parameters

node

addValidEdge()

void game2dai.graph.Graph.addValidEdge ( GraphEdge  edge )

protected

This method is called to add a validated edge to the graph.

Parameters

edge	the validated edge to add.

compact()

void game2dai.graph.Graph.compact

(

)

Clear out all remaining floating edges.

distance() [1/2]

double game2dai.graph.Graph.distance	(	GraphNode	nodeFrom,
		GraphNode	nodeTo
	)

Gets the world distance between 2 nodes.

Parameters

nodeFrom	first node
nodeTo	second node

Returns

distance between them or 0 if either node does not exist

distance() [2/2]

double game2dai.graph.Graph.distance	(	int	nodeFromID,
		int	nodeToID
	)

Get the distance between two nodes.

Parameters

nodeFromID	ID of first node
nodeToID	ID of second node

Returns

distance between them or 0 if either node does not exist

getEdge()

GraphEdge game2dai.graph.Graph.getEdge	(	int	fromID,
		int	toID
	)

Get the edge between 2 nodes.
If either node does not exist or there is no edge exists between them then the method returns null.

Parameters

fromID	ID for the from node
toID	ID for the to node

Returns

the edge or null if it doesn't exist

getEdgeArray() [1/4]

GraphEdge[] game2dai.graph.Graph.getEdgeArray

(

)

Will return an array of all the GraphEdges in the graph.
The type of each element in the array will be of type GraphEdge

getEdgeArray() [2/4]

GraphEdge[] game2dai.graph.Graph.getEdgeArray

(

int

from

)

Will return an array of all the GraphEdges that start from the node.
The type of each element in the array will be of type GraphEdge

Parameters

from	the node where the edges start from

getEdgeArray() [3/4]

public< T extends GraphEdge > T[] game2dai.graph.Graph.getEdgeArray ( int  from, T[]  array  )

package

Will return an array of all the GraphEdges that start from the node.
The type of each element in the array will be of type Object if the parameter is null otherwise it is T (where T is GraphEdge or any class that extends GrahEdge.

Parameters

<T>
from	the node where the edges start from
array	a zero length array of GraphNode or any derived class.

getEdgeArray() [4/4]

public< T extends GraphEdge > T[] game2dai.graph.Graph.getEdgeArray ( T[]  array )

package

Will return an array of all the GraphEdges in the graph.
The type of each element in the array will be of type Object if the parameter is null otherwise it is T (where T is GraphEdge or any class derived from GraphEdge.

Parameters

<T>
array	a zero length array of GraphNode or any derived class.

getEdgeCost()

double game2dai.graph.Graph.getEdgeCost	(	int	fromID,
		int	toID
	)

Get the cost of traversing an edge between 2 nodes.
If either node does not exist or there is no edge exists between them then the method returns a value <0.

Parameters

fromID	ID for the from node
toID	ID for the to node

Returns

the edge or null if it doesn't exist

getEdgeList() [1/2]

LinkedList< GraphEdge > game2dai.graph.Graph.getEdgeList

(

GraphNode

node

)

Gets a list of GraphEdges leaving (from) this node.
Used by graph search classes.

Parameters

node	the node where the edges start from

getEdgeList() [2/2]

LinkedList< GraphEdge > game2dai.graph.Graph.getEdgeList

(

int

nodeID

)

Gets a list of GraphEdges leaving (from) this node.
Used by graph search classes.

Parameters

nodeID

id of the node where the edges start from

getNbrNodes()

int game2dai.graph.Graph.getNbrNodes

(

)

get the number of nodes in the graph

getNode()

GraphNode game2dai.graph.Graph.getNode

(

int

id

)

Get a node with a given id.

Parameters

id

Returns

the node if it exists else null

getNodeArray() [1/2]

GraphNode[] game2dai.graph.Graph.getNodeArray

(

)

Will return an array of all the GraphNodes in the graph.
The type of each element in the array will be of type GraphNode

getNodeArray() [2/2]

public< T extends GraphNode > T[] game2dai.graph.Graph.getNodeArray ( T[]  array )

package

Will return an array of all the GraphNodes in the graph.
The type of each element in the array will be of type Object if the parameter is null otherwise it is T (where T is GraphNode or any class that extends GraphNode.

Parameters

<T>
array	a zero length array of GraphNode or any derived class.

getNodeNear() [1/2]

GraphNode game2dai.graph.Graph.getNodeNear	(	double	x,
		double	y,
		double	maxDistance
	)

Locate and return the first node encountered that is within a stated distance of a position at [x,y,0]

Parameters

x
y
maxDistance	only consider a node that is with this distance of [x,y,z]

Returns

the node if it meets the distance criteria else null

getNodeNear() [2/2]

GraphNode game2dai.graph.Graph.getNodeNear	(	double	x,
		double	y,
		double	z,
		double	maxDistance
	)

Locate and return the first node encountered that is within a stated distance of a position at [x,y,z]

Parameters

x
y
z
maxDistance	only consider a node that is with this distance of [x,y,z]

Returns

the node if it meets the distance criteria else null

getNodeNearest() [1/4]

GraphNode game2dai.graph.Graph.getNodeNearest	(	double	x,
		double	y
	)

Locate and return the node nearest a given position irrespective of the distance apart in the x/y plane (ignores z).

Parameters

x
y

Returns

the nearest node

getNodeNearest() [2/4]

GraphNode game2dai.graph.Graph.getNodeNearest	(	double	x,
		double	y,
		double	z
	)

Locate and return the node nearest a given position irrespective of the distance apart.

Parameters

x
y
z

Returns

the nearest node

getNodeNearest() [3/4]

GraphNode game2dai.graph.Graph.getNodeNearest

(

GraphNode

a_node

)

Find the node nearest the node specified based on Euclidean distance between them.

Parameters

a_node

the node to use as the origin.

Returns

the nearest node found or null if none exists.

getNodeNearest() [4/4]

GraphNode game2dai.graph.Graph.getNodeNearest

(

int

id

)

Find the node nearest the node with the specified ID number based on Euclidean distance between them.

Parameters

id	the ID number of the node to use as the origin

Returns

the nearest node found or null if none exists.

hasEdge()

boolean game2dai.graph.Graph.hasEdge	(	int	from,
		int	to
	)

Sees whether the graph has this edge

Parameters

from	node id of from-node
to	node if of to-node

Returns

true if the graph has this node else false

hasNode()

boolean game2dai.graph.Graph.hasNode

(

int

id

)

Does a node with a given id exist?

Parameters

id

Returns

true if the node exists else false

rememberFloatingEdge()

void game2dai.graph.Graph.rememberFloatingEdge ( int  id, FloatingEdge  floatEdge  )

protected

This method is used to remember floating edges.

Parameters

id
floatEdge

removeEdge()

boolean game2dai.graph.Graph.removeEdge	(	int	fromID,
		int	toID
	)

Remove an edge between 2 nodes.
This will delete the edge from one node to another but does not remove any return edge.
To remove a 'bidirectional route' between nodes 22 and 33 then you must call this method twice e.g. graph.removeEdge(22, 33); graph.removeEdge(33, 22);

Parameters

fromID	ID for the from node
toID	ID for the to node

Returns

true if an edge has been removed

removeNode()

boolean game2dai.graph.Graph.removeNode

(

int

nodeID

)

If the node exists remove it and all edges that start or end at this node.

Parameters

nodeID

id of the node to remove

Returns

true if the node was removed else false

resolveFloatEdges()

void game2dai.graph.Graph.resolveFloatEdges ( GraphNode  node )

protected

This method is called every time a node is added to the graph. It will update all floating edges and where possible add the resolved floating edge to the graph.

Parameters

node	a node to be added to the graph (must not be null)

toString()

String game2dai.graph.Graph.toString

(

)

Used for debugging only.

---

The documentation for this class was generated from the following file:

• /Users/peter/git/ai4games-repos/AI_4_2D_Games/src/game2dai/graph/Graph.java