//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
SparseGraph’s declaration.
template <class node_type, class edge_type>
class SparseGraph
{
public:
//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;
private:
//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