/* 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)