Public Member Functions
	Graph ()

	Graph (int nbrNodes)

void	addNode (GraphNode node)

boolean	removeNode (int nodeID)

GraphNode	getNode (int id)

boolean	hasNode (int id)

GraphNode	getNodeAt (double x, double y, double z, double maxDistance)

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[]	getAllEdgeArray ()

GraphEdge[]	getEdgeArray (int from)

GraphNode[]	getNodeArray ()

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

boolean	nodesFirst = false

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]

pathfinder.Graph.Graph ( )

Create a graph with an initial capacity of 16 nodes.

◆ Graph() [2/2]

pathfinder.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 pathfinder.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 pathfinder.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 pathfinder.Graph.addNode ( GraphNode node )

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

Parameters

node

◆ addValidEdge()

void pathfinder.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 pathfinder.Graph.compact ( )

Clear out all remaining floating edges.

◆ getAllEdgeArray()

GraphEdge[] pathfinder.Graph.getAllEdgeArray ( )

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

◆ getEdge()

GraphEdge pathfinder.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()

GraphEdge[] pathfinder.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

◆ getEdgeCost()

double pathfinder.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 > pathfinder.Graph.getEdgeList ( GraphNode node )

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

Parameters

node	the node where the edges start from

Returns: a list of departing edges (the list wil be empty if no departing edges)

◆ getEdgeList() [2/2]

LinkedList< GraphEdge > pathfinder.Graph.getEdgeList ( int nodeID )

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

Parameters

nodeID id of the node where the edges start from

Returns: a list of departing edges (the list will be empty if no departing edges)

◆ getNbrNodes()

int pathfinder.Graph.getNbrNodes ( )

get the number of nodes in the graph

Returns: the number of nodes in this graph

◆ getNode()

GraphNode pathfinder.Graph.getNode ( int id )

Get a node with a given id.

Parameters

id

Returns: the node if it exists else null

◆ getNodeArray()

GraphNode[] pathfinder.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

◆ getNodeAt()

GraphNode pathfinder.Graph.getNodeAt	(	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

◆ hasEdge()

boolean pathfinder.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 pathfinder.Graph.hasNode ( int id )

Does a node with a given id exist?

Parameters

id

Returns: true if the node exists else false

◆ rememberFloatingEdge()

void pathfinder.Graph.rememberFloatingEdge	(	int	id,
		FloatingEdge	floatEdge
	)

protected

This method is used to remember floating edges.

Parameters

id
floatEdge

◆ removeEdge()

boolean pathfinder.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 pathfinder.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 pathfinder.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 adding the floating edge to the graph.

Parameters

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

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

/Users/peter/git/path-finder-repos/Path Finder/src/pathfinder/Graph.java

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

Constructor & Destructor Documentation

◆ Graph() [1/2]

◆ Graph() [2/2]

Member Function Documentation

◆ addEdge() [1/2]

◆ addEdge() [2/2]

◆ addNode()

◆ addValidEdge()

◆ compact()

◆ getAllEdgeArray()

◆ getEdge()

◆ getEdgeArray()

◆ getEdgeCost()

◆ getEdgeList() [1/2]

◆ getEdgeList() [2/2]

◆ getNbrNodes()

◆ getNode()

◆ getNodeArray()

◆ getNodeAt()

◆ hasEdge()

◆ hasNode()

◆ rememberFloatingEdge()

◆ removeEdge()

◆ removeNode()

◆ resolveFloatEdges()