//cost from A to B
cost = Distance(NodeA.Position, NodeB.Position)
Because there are usually eight times more edges than vertices in this type
of graph, the memory savings can be considerable when large numbers of
nodes are involved.
The SparseGraph Class
Graph nodes and edges are grouped together in the SparseGraph class. This
is implemented as a class template, enabling this type of graph to use any
appropriate node and edge types. Algorithms that operate on graphs should
be able to access the node and edge data quickly. With this in mind, the
SparseGraph class is designed so that each node’s index number keys
directly into a vector of graph nodes (
m_Nodes) and a vector of adjacency
edge lists (
m_Edges), giving a lookup time of O(1). However, this creates a
problem when a node is removed from the graph, since if it were to be
removed from
m_Nodes also, all the indexing for any higher indexed nodes
would be invalidated. Therefore, instead of erasing the node from the vec-
tor, its index is set to the enumerated value
invalid_node_index, and all the
methods of
SparseGraph treat this value as if there were no node present.
Here is the listing of
SparseGraphs declaration.
template <class node_type, class edge_type>
class SparseGraph
//enable easy client access to the edge and node types used in the graph
typedef edge_type EdgeType;
typedef node_type NodeType;
//a few more useful typedefs
typedef std::vector<node_type> NodeVector;
typedef std::list<edge_type> EdgeList;
typedef std::vector<EdgeList> EdgeListVector;
//the nodes that comprise this graph
NodeVector m_Nodes;
//a vector of adjacency edge lists. (each node index keys into the
//list of edges associated with that node)
EdgeListVector m_Edges;
//is this a directed graph?
bool m_bDigraph;
The Secret Life of Graphs | 207
Implementing a Graph Class
//the index of the next node to be added
int m_iNextNodeIndex;
SparseGraph(bool digraph): m_iNextNodeIndex(0), m_bDigraph(digraph){}
//returns the node at the given index
const NodeType& GetNode(int idx)const;
//non-const version
NodeType& GetNode(int idx);
//const method for obtaining a reference to an edge
const EdgeType& GetEdge(int from, int to)const;
//non const version
EdgeType& GetEdge(int from, int to);
//retrieves the next free node index
int GetNextFreeNodeIndex()const;
//adds a node to the graph and returns its index
int AddNode(NodeType node);
//removes a node by setting its index to invalid_node_index
void RemoveNode(int node);
//methods to add and remove edges
void AddEdge(EdgeType edge);
void RemoveEdge(int from, int to);
Note how the class has methods for removing nodes and edges. This is a
necessary feature if your graph is dynamic and has the ability to change as
the game progresses. For example, it’s easy to represent the disruption
wreaked by an earthquake by removing (and sometimes by adding) edges
from a navigation graph. Alternatively, gameplay similar to that of Com
mand & Conquer can add and remove edges as players build or blast away
bridges and walls.
//returns the number of active + inactive nodes present in the graph
int NumNodes()const;
//returns the number of active nodes present in the graph
int NumActiveNodes()const;
//returns the number of edges present in the graph
int NumEdges()const;
208 | Chapter 5
Implementing a Graph Class

Get Programming Game AI by Example now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.