/* Let's see if we can whip together a general-purpose package for
fiddling with directed graphs. I will suppose a set of "nodes"
(really just addresses of structures containing interesting
information) and a set of edges (ditto). I suspect it would be
useful to overlay more than one set of edges onto the nodes,
and I suspect that it would be good to allow labelled nodes.
I will further suppose that being able to enumerate and quickly
access edges adjacent to/from a node is a good thing.
*/
struct graph_node {
struct graph_edge_bunch * from_list;
struct graph_edge_bunch * to_list;
struct graph_node * next_node;
UINT * data;
};
typedef UINT GRAPH_INDEX;
struct graph_edge {
struct graph_node * from;
struct graph_node * to;
UINT label;
GRAPH_INDEX index;
struct graph_edge * next_from;
struct graph_edge * next_to;
};
struct graph_edge_bunch {
GRAPH_INDEX index;
struct graph_edge * first_edge;
struct graph_edge * last_edge;
struct graph_edge_bunch * next_bunch;
};
typedef struct graph {
struct graph_node * first_node;
struct graph_node * last_node;
GRAPH_INDEX next_graph_index;
GRAPH_INDEX max_graph_index; /* Expand data fields when this
limit is reached. */
struct graph_edge * edge_cache;
struct graph_edge_bunch * bunch_cache;
GMAP lookup_table;
};
typedef struct graph_edge * GRAPH_EDGE;
typedef struct graph_node * GRAPH_NODE;
typedef struct graph_edge_bunch * GRAPH_BUNCH;
typedef struct graph * GRAPH;
extern GRAPH new_graph();
extern GRAPH_INDEX next_graph_index(/* graph */);
extern GRAPH_NODE new_node(/* graph */);
extern GRAPH_EDGE new_edge_after(/* graph, index, label, from, to */);
extern GRAPH_EDGE new_edge_before(/* graph, index, label, from, to */);
extern GRAPH_EDGE find_edge(/* graph, index, label, from, to */);
extern delete_edge(/* graph, edge */);
extern delete_graph_index(/* graph, index */);
#define NULL_EDGE ((GRAPH_EDGE)0)
#define NULL_NODE ((GRAPH_NODE)0)
#define NULL_INDEX ((GRAPH_INDEX)0)
#define NULL_BUNCH ((GRAPH_BUNCH)0)
#define node_data(n,i) ((n)->data[i])
#define edge_label(e) ((e) -> label)
#define edge_from(e) ((e) -> from)
#define edge_to(e) ((e) -> to)
#define edge_index(e) ((e) -> index)
/* UINT newstate = (*func) (edge, state) */
extern UINT foreach_edge_from(/* graph, index, from, func, state */);
extern UINT foreach_edge_to(/* graph, index, to, func, state */);
extern UINT foreach_edge(/* graph, func, state */);
extern UINT foreach_edge_in_i(/* graph, index, func, state */);
#define foreachnodein(g,n) \
for (n = g -> first_node; n != NULL_NODE ; n = n -> next_node)