//returns true if the graph is directed

bool isDigraph()const;

//returns true if the graph contains no nodes

bool isEmpty()const;

//returns true if a node with the given index is present in the graph

bool isPresent(int nd)const;

//methods for loading and saving graphs from an open file stream or from

//a filename

bool Save(const char* FileName)const;

bool Save(std::ofstream& stream)const;

bool Load(const char* FileName);

bool Load(std::ifstream& stream);

//clears the graph ready for new node insertions

void Clear();

//iterators clients may use to access nodes and edges

class ConstEdgeIterator;

class EdgeIterator;

class NodeIterator;

class ConstNodeIterator;

};

From the information in this section you have learned that graphs are a

powerful tool to have at your disposal. However, the graph data structure

alone has few uses. Much of the power of graphs is only realized when

they are operated upon by algorithms designed to explore them, either to

find a specific node or to find a path between nodes. The rest of this chap-

ter is devoted to a study of several of those algorithms.

Graph Search Algorithms

Graph theory has been a popular area of study of mathematicians for many

years and numerous algorithms have been devised to search and explore a

graph’s topology. Among other things, by utilizing search algorithms it is

possible to:

n

Visit every node in a graph, effectively mapping out the graph’s

topology.

n

Find any path between two nodes. This is useful if you want to find a

node but you don’t really care how you get there. For example, this

type of search can be used to find one (or more) of the solutions to

the Towers of Hanoi puzzle.

n

Find the best path between two nodes. What is “best” depends on the

problem. If the graph to be searched is a navgraph, the best path may

be the shortest path between two nodes, the path that takes an agent

between two points in the fastest time, the path that avoids enemy

line of sight, or the most quiet path (à la Thief). If the graph is a state

The Secret Life of Graphs | 209

Graph Search Algorithms

Start Free Trial

No credit card required