/* * File: graph.h * ------------- * This interface exports a simple graph abstraction. In this abstraction, * graphs closely model their mathematical formulation as a set of nodes * connected by a set of arcs. */ #ifndef _graph_h #define _graph_h #include "cslib.h" #include "cmpfn.h" #include "set.h"/* * Type: Graph * ----------- * This type represents the abstract type for a graph. Conceptually, a * Graph consists of a set of nodes together with a set of arcs. Each arc * connects two nodes in one direction. Undirected graphs must include two * arcs for each bidirectional connection. */ typedef struct GraphCDT *Graph;/* * Type: Node * ---------- * This type is the abstract type for a node in a graph. Clients can store * their own data in a node by using the functions getBlockData and * setBlockData described in cslib.h. */ typedef struct NodeCDT *Node;/* * Type: Arc * --------- * This type is the abstract type for an arc in a graph. Clients can store * their own data in an arc by using the functions getBlockData and * setBlockData described in cslib.h. */ typedef struct ArcCDT *Arc;/* * Function: newGraph * Usage: g = newGraph(); * ---------------------- * Returns a new graph with no nodes or arcs. */ Graph newGraph(void);/* * Function: freeGraph * Usage: freeGraph(g); * -------------------- * Frees the storage for the graph, along with its nodes and arcs. */ void freeGraph(Graph g);/* * Function: addNode * Usage: node = addNode(g, name); * ------------------------------- * Adds a node to the graph with the specified name. If there is already a * node with that name, addNode generates an error. The function returns * the Node value. */ Node addNode(Graph g, string name);/* * Function: removeNode * Usage: removeNode(g, node); * --------------------------- * Removes and frees the specified node from the graph, along with any arcs * that enter or leave that node. */ void removeNode(Graph g, Node node);/* * Function: getNode * Usage: node = getNode(g, name); * ------------------------------- * Returns the node in the graph that has the specified name. If there is * no such node, getNode returns NULL. */ Node getNode(Graph g, string name);/* * Function: addArc * Usage: arc = addArc(g, n1, n2); * ------------------------------- * Adds a new arc to the graph connecting nodes n1 and n2. The function * returns the Arc value. */ Arc addArc(Graph g, Node n1, Node n2);/* * Function: removeArc * Usage: removeArc(g, arc); * ------------------------- * Removes and frees the specified arc. */ void removeArc(Graph g, Arc arc);/* * Function: isConnected * Usage: if (isConnected(n1, n2)) . . . * ------------------------------------- * Returns true if there is an arc from n1 to n2. */ bool isConnected(Node n1, Node n2);/* * Function: getNodeSet * Usage: nodeSet = getNodeSet(g); * ------------------------------- * Returns a set consisting of all nodes in the graph. This function is * typically used in conjunction with the foreach macro to initialize an * iterator. For example, the following idiom iterates over the nodes in * the specified graph: * * foreach (node in getNodeSet(g)) . . . */ Set getNodeSet(Graph g);/* * Function: getArcSet * Usage: arcSet = getArcSet(g); * arcSet = getArcSet(node); * -------------------------------- * Returns a set consisting of all arcs, either in the graph or starting at * the specified node. This function is typically used in conjunction with * the foreach macro to initialize an iterator. For example, the following * idiom iterates over the arcs in the specified graph: * * foreach (arc in getArcSet(g)) . . . */ Set getArcSet(void *arg);/* * Function: getNeighbors * Usage: nodeSet = getNeighbors(node); * ------------------------------------ * Returns a set consisting of the nodes to which a given node is * connected. This function is typically used in conjunction with the * foreach macro to initialize an iterator. For example, the following * idiom iterates over the nodes to which the node start is connected: * * foreach (node in getNeighbors(start)) . . . */ Set getNeighbors(Node node);/* * Function: getName * Usage: str = getName(node); * --------------------------- * Returns the name of the node. */ string getName(Node node);/* * Function: startOfArc * Usage: node = startOfArc(arc); * ------------------------------ * Returns the node at the beginning of the specified arc. */ Node startOfArc(Arc arc);/* * Function: endOfArc * Usage: node = endOfArc(arc); * ---------------------------- * Returns the node at the end of the specified arc. */ Node endOfArc(Arc arc);/* * Function: getCost * Usage: cost = getCost(arc); * --------------------------- * Returns the "cost" associated with traversing an arc. This cost need * not be economic and will often refer to some other metric, such as * distance. */ double getCost(Arc arc);/* * Function: setCost * Usage: setCost(arc, cost); * -------------------------- * Sets the cost of traversing the arc. */ void setCost(Arc arc, double cost);/* * Function: setNodeOrdering * Usage: setNodeOrdering(graph, cmpFn); * ------------------------------------- * Sets the comparison function used to order the nodes in a graph when * they are enumerated. By default, nodes are sorted in alphabetical order * by name. */ void setNodeOrdering(Graph graph, CompareFn cmpFn);/* * Function: setArcOrdering * Usage: setArcOrdering(graph, cmpFn); * ------------------------------------ * Sets the comparison function used to order the arcs in a graph when they * are enumerated. By default, arcs are sorted in alphabetical order by * the name of the start node followed by the name of the end node. */ void setArcOrdering(Graph graph, CompareFn cmpFn); #endif