[Help-glpk] implementation of graphs and networks in glpk

[Andrew Makhorin]

I plan to include in the next release of glpk some new api data
structures and routines to deal with graphs and flow networks.

Below here are three data structures I developed to represent the
sparse graph (glp_graph) and its components (glp_vertex and glp_arc).
Note that unlike glp_prob these program objects are "semi-opaque" in
the sense that the application program can access content of these
objects directly (for the sake of efficiency), however, any changes
have to be made only with corresponding api routines.

Any comments and suggestions are appreciated. Thanks.

Andrew Makhorin

------------------------------------------------------------------------

#ifdef GLP_PRERELEASE
typedef struct glp_graph glp_graph;
typedef struct glp_vertex glp_vertex;
typedef struct glp_arc glp_arc;

struct glp_graph
{     /* graph descriptor */
      void *pool; /* DMP *pool; */
      /* memory pool to store graph components */
      char *name;
      /* graph name (1 to 255 chars); NULL means no name is assigned
         to the graph */
      int nv_max;
      /* length of the vertex list (enlarged automatically) */
      int nv;
      /* number of vertices in the graph, 0 <= nv <= nv_max */
      int na;
      /* number of arcs in the graph, na >= 0 */
      glp_vertex **v; /* glp_vertex *v[1+nv_max]; */
      /* v[i], 1 <= i <= nv, is a pointer to i-th vertex */
      void *index; /* AVL *index; */
      /* vertex index to find vertices by their names; NULL means the
         index does not exist */
      int v_size;
      /* size of data associated with each vertex (0 to 256 bytes) */
      int a_size;
      /* size of data associated with each arc (0 to 256 bytes) */
};

struct glp_vertex
{     /* vertex descriptor */
      int i;
      /* vertex ordinal number, 1 <= i <= nv */
      char *name;
      /* vertex name (1 to 255 chars); NULL means no name is assigned
         to the vertex */
      void *entry; /* AVLNODE *entry; */
      /* pointer to corresponding entry in the vertex index; NULL means
         that either the index does not exist or the vertex has no name
         assigned */
      void *data;
      /* pointer to data associated with the vertex */
      void *temp;
      /* working pointer */
      glp_arc *in;
      /* pointer to the (unordered) list of incoming arcs */
      glp_arc *out;
      /* pointer to the (unordered) list of outgoing arcs */
};

struct glp_arc
{     /* arc descriptor */
      glp_vertex *tail;
      /* pointer to the tail endpoint */
      glp_vertex *head;
      /* pointer to the head endpoint */
      void *data;
      /* pointer to data associated with the arc */
      void *temp;
      /* working pointer */
      glp_arc *t_prev;
      /* pointer to previous arc having the same tail endpoint */
      glp_arc *t_next;
      /* pointer to next arc having the same tail endpoint */
      glp_arc *h_prev;
      /* pointer to previous arc having the same head endpoint */
      glp_arc *h_next;
      /* pointer to next arc having the same head endpoint */
};