simplex-glpk with modified glpk for fpgaHEADmaster

1 files changed, 502 insertions, 0 deletions

diff --git a/glpk-5.0/src/api/graph.c b/glpk-5.0/src/api/graph.c
new file mode 100644
index 0000000..a522282
--- /dev/null
+++ b/glpk-5.0/src/api/graph.c
@@ -0,0 +1,502 @@
+/* graph.c (basic graph routines) */
+
+/***********************************************************************
+*  This code is part of GLPK (GNU Linear Programming Kit).
+*  Copyright (C) 2009-2016 Free Software Foundation, Inc.
+*  Written by Andrew Makhorin <mao@gnu.org>.
+*
+*  GLPK is free software: you can redistribute it and/or modify it
+*  under the terms of the GNU General Public License as published by
+*  the Free Software Foundation, either version 3 of the License, or
+*  (at your option) any later version.
+*
+*  GLPK is distributed in the hope that it will be useful, but WITHOUT
+*  ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
+*  or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
+*  License for more details.
+*
+*  You should have received a copy of the GNU General Public License
+*  along with GLPK. If not, see <http://www.gnu.org/licenses/>.
+***********************************************************************/
+
+#include "avl.h"
+#include "dmp.h"
+#include "env.h"
+#include "glpk.h"
+
+/* CAUTION: DO NOT CHANGE THE LIMITS BELOW */
+
+#define NV_MAX 100000000 /* = 100*10^6 */
+/* maximal number of vertices in the graph */
+
+#define NA_MAX 500000000 /* = 500*10^6 */
+/* maximal number of arcs in the graph */
+
+/***********************************************************************
+*  NAME
+*
+*  glp_create_graph - create graph
+*
+*  SYNOPSIS
+*
+*  glp_graph *glp_create_graph(int v_size, int a_size);
+*
+*  DESCRIPTION
+*
+*  The routine creates a new graph, which initially is empty, i.e. has
+*  no vertices and arcs.
+*
+*  The parameter v_size specifies the size of data associated with each
+*  vertex of the graph (0 to 256 bytes).
+*
+*  The parameter a_size specifies the size of data associated with each
+*  arc of the graph (0 to 256 bytes).
+*
+*  RETURNS
+*
+*  The routine returns a pointer to the graph created. */
+
+static void create_graph(glp_graph *G, int v_size, int a_size)
+{     G->pool = dmp_create_pool();
+      G->name = NULL;
+      G->nv_max = 50;
+      G->nv = G->na = 0;
+      G->v = xcalloc(1+G->nv_max, sizeof(glp_vertex *));
+      G->index = NULL;
+      G->v_size = v_size;
+      G->a_size = a_size;
+      return;
+}
+
+glp_graph *glp_create_graph(int v_size, int a_size)
+{     glp_graph *G;
+      if (!(0 <= v_size && v_size <= 256))
+         xerror("glp_create_graph: v_size = %d; invalid size of vertex "
+            "data\n", v_size);
+      if (!(0 <= a_size && a_size <= 256))
+         xerror("glp_create_graph: a_size = %d; invalid size of arc dat"
+            "a\n", a_size);
+      G = xmalloc(sizeof(glp_graph));
+      create_graph(G, v_size, a_size);
+      return G;
+}
+
+/***********************************************************************
+*  NAME
+*
+*  glp_set_graph_name - assign (change) graph name
+*
+*  SYNOPSIS
+*
+*  void glp_set_graph_name(glp_graph *G, const char *name);
+*
+*  DESCRIPTION
+*
+*  The routine glp_set_graph_name assigns a symbolic name specified by
+*  the character string name (1 to 255 chars) to the graph.
+*
+*  If the parameter name is NULL or an empty string, the routine erases
+*  the existing symbolic name of the graph. */
+
+void glp_set_graph_name(glp_graph *G, const char *name)
+{     if (G->name != NULL)
+      {  dmp_free_atom(G->pool, G->name, strlen(G->name)+1);
+         G->name = NULL;
+      }
+      if (!(name == NULL || name[0] == '\0'))
+      {  int j;
+         for (j = 0; name[j] != '\0'; j++)
+         {  if (j == 256)
+               xerror("glp_set_graph_name: graph name too long\n");
+            if (iscntrl((unsigned char)name[j]))
+               xerror("glp_set_graph_name: graph name contains invalid "
+                  "character(s)\n");
+         }
+         G->name = dmp_get_atom(G->pool, strlen(name)+1);
+         strcpy(G->name, name);
+      }
+      return;
+}
+
+/***********************************************************************
+*  NAME
+*
+*  glp_add_vertices - add new vertices to graph
+*
+*  SYNOPSIS
+*
+*  int glp_add_vertices(glp_graph *G, int nadd);
+*
+*  DESCRIPTION
+*
+*  The routine glp_add_vertices adds nadd vertices to the specified
+*  graph. New vertices are always added to the end of the vertex list,
+*  so ordinal numbers of existing vertices remain unchanged.
+*
+*  Being added each new vertex is isolated (has no incident arcs).
+*
+*  RETURNS
+*
+*  The routine glp_add_vertices returns an ordinal number of the first
+*  new vertex added to the graph. */
+
+int glp_add_vertices(glp_graph *G, int nadd)
+{     int i, nv_new;
+      if (nadd < 1)
+         xerror("glp_add_vertices: nadd = %d; invalid number of vertice"
+            "s\n", nadd);
+      if (nadd > NV_MAX - G->nv)
+         xerror("glp_add_vertices: nadd = %d; too many vertices\n",
+            nadd);
+      /* determine new number of vertices */
+      nv_new = G->nv + nadd;
+      /* increase the room, if necessary */
+      if (G->nv_max < nv_new)
+      {  glp_vertex **save = G->v;
+         while (G->nv_max < nv_new)
+         {  G->nv_max += G->nv_max;
+            xassert(G->nv_max > 0);
+         }
+         G->v = xcalloc(1+G->nv_max, sizeof(glp_vertex *));
+         memcpy(&G->v[1], &save[1], G->nv * sizeof(glp_vertex *));
+         xfree(save);
+      }
+      /* add new vertices to the end of the vertex list */
+      for (i = G->nv+1; i <= nv_new; i++)
+      {  glp_vertex *v;
+         G->v[i] = v = dmp_get_atom(G->pool, sizeof(glp_vertex));
+         v->i = i;
+         v->name = NULL;
+         v->entry = NULL;
+         if (G->v_size == 0)
+            v->data = NULL;
+         else
+         {  v->data = dmp_get_atom(G->pool, G->v_size);
+            memset(v->data, 0, G->v_size);
+         }
+         v->temp = NULL;
+         v->in = v->out = NULL;
+      }
+      /* set new number of vertices */
+      G->nv = nv_new;
+      /* return the ordinal number of the first vertex added */
+      return nv_new - nadd + 1;
+}
+
+/**********************************************************************/
+
+void glp_set_vertex_name(glp_graph *G, int i, const char *name)
+{     /* assign (change) vertex name */
+      glp_vertex *v;
+      if (!(1 <= i && i <= G->nv))
+         xerror("glp_set_vertex_name: i = %d; vertex number out of rang"
+            "e\n", i);
+      v = G->v[i];
+      if (v->name != NULL)
+      {  if (v->entry != NULL)
+         {  xassert(G->index != NULL);
+            avl_delete_node(G->index, v->entry);
+            v->entry = NULL;
+         }
+         dmp_free_atom(G->pool, v->name, strlen(v->name)+1);
+         v->name = NULL;
+      }
+      if (!(name == NULL || name[0] == '\0'))
+      {  int k;
+         for (k = 0; name[k] != '\0'; k++)
+         {  if (k == 256)
+               xerror("glp_set_vertex_name: i = %d; vertex name too lon"
+                  "g\n", i);
+            if (iscntrl((unsigned char)name[k]))
+               xerror("glp_set_vertex_name: i = %d; vertex name contain"
+                  "s invalid character(s)\n", i);
+         }
+         v->name = dmp_get_atom(G->pool, strlen(name)+1);
+         strcpy(v->name, name);
+         if (G->index != NULL)
+         {  xassert(v->entry == NULL);
+            v->entry = avl_insert_node(G->index, v->name);
+            avl_set_node_link(v->entry, v);
+         }
+      }
+      return;
+}
+
+/***********************************************************************
+*  NAME
+*
+*  glp_add_arc - add new arc to graph
+*
+*  SYNOPSIS
+*
+*  glp_arc *glp_add_arc(glp_graph *G, int i, int j);
+*
+*  DESCRIPTION
+*
+*  The routine glp_add_arc adds a new arc to the specified graph.
+*
+*  The parameters i and j specify the ordinal numbers of, resp., tail
+*  and head vertices of the arc. Note that self-loops and multiple arcs
+*  are allowed.
+*
+*  RETURNS
+*
+*  The routine glp_add_arc returns a pointer to the arc added. */
+
+glp_arc *glp_add_arc(glp_graph *G, int i, int j)
+{     glp_arc *a;
+      if (!(1 <= i && i <= G->nv))
+         xerror("glp_add_arc: i = %d; tail vertex number out of range\n"
+            , i);
+      if (!(1 <= j && j <= G->nv))
+         xerror("glp_add_arc: j = %d; head vertex number out of range\n"
+            , j);
+      if (G->na == NA_MAX)
+         xerror("glp_add_arc: too many arcs\n");
+      a = dmp_get_atom(G->pool, sizeof(glp_arc));
+      a->tail = G->v[i];
+      a->head = G->v[j];
+      if (G->a_size == 0)
+         a->data = NULL;
+      else
+      {  a->data = dmp_get_atom(G->pool, G->a_size);
+         memset(a->data, 0, G->a_size);
+      }
+      a->temp = NULL;
+      a->t_prev = NULL;
+      a->t_next = G->v[i]->out;
+      if (a->t_next != NULL) a->t_next->t_prev = a;
+      a->h_prev = NULL;
+      a->h_next = G->v[j]->in;
+      if (a->h_next != NULL) a->h_next->h_prev = a;
+      G->v[i]->out = G->v[j]->in = a;
+      G->na++;
+      return a;
+}
+
+/***********************************************************************
+*  NAME
+*
+*  glp_del_vertices - delete vertices from graph
+*
+*  SYNOPSIS
+*
+*  void glp_del_vertices(glp_graph *G, int ndel, const int num[]);
+*
+*  DESCRIPTION
+*
+*  The routine glp_del_vertices deletes vertices along with all
+*  incident arcs from the specified graph. Ordinal numbers of vertices
+*  to be deleted should be placed in locations num[1], ..., num[ndel],
+*  ndel > 0.
+*
+*  Note that deleting vertices involves changing ordinal numbers of
+*  other vertices remaining in the graph. New ordinal numbers of the
+*  remaining vertices are assigned under the assumption that the
+*  original order of vertices is not changed. */
+
+void glp_del_vertices(glp_graph *G, int ndel, const int num[])
+{     glp_vertex *v;
+      int i, k, nv_new;
+      /* scan the list of vertices to be deleted */
+      if (!(1 <= ndel && ndel <= G->nv))
+         xerror("glp_del_vertices: ndel = %d; invalid number of vertice"
+            "s\n", ndel);
+      for (k = 1; k <= ndel; k++)
+      {  /* take the number of vertex to be deleted */
+         i = num[k];
+         /* obtain pointer to i-th vertex */
+         if (!(1 <= i && i <= G->nv))
+            xerror("glp_del_vertices: num[%d] = %d; vertex number out o"
+               "f range\n", k, i);
+         v = G->v[i];
+         /* check that the vertex is not marked yet */
+         if (v->i == 0)
+            xerror("glp_del_vertices: num[%d] = %d; duplicate vertex nu"
+               "mbers not allowed\n", k, i);
+         /* erase symbolic name assigned to the vertex */
+         glp_set_vertex_name(G, i, NULL);
+         xassert(v->name == NULL);
+         xassert(v->entry == NULL);
+         /* free vertex data, if allocated */
+         if (v->data != NULL)
+            dmp_free_atom(G->pool, v->data, G->v_size);
+         /* delete all incoming arcs */
+         while (v->in != NULL)
+            glp_del_arc(G, v->in);
+         /* delete all outgoing arcs */
+         while (v->out != NULL)
+            glp_del_arc(G, v->out);
+         /* mark the vertex to be deleted */
+         v->i = 0;
+      }
+      /* delete all marked vertices from the vertex list */
+      nv_new = 0;
+      for (i = 1; i <= G->nv; i++)
+      {  /* obtain pointer to i-th vertex */
+         v = G->v[i];
+         /* check if the vertex is marked */
+         if (v->i == 0)
+         {  /* it is marked, delete it */
+            dmp_free_atom(G->pool, v, sizeof(glp_vertex));
+         }
+         else
+         {  /* it is not marked, keep it */
+            v->i = ++nv_new;
+            G->v[v->i] = v;
+         }
+      }
+      /* set new number of vertices in the graph */
+      G->nv = nv_new;
+      return;
+}
+
+/***********************************************************************
+*  NAME
+*
+*  glp_del_arc - delete arc from graph
+*
+*  SYNOPSIS
+*
+*  void glp_del_arc(glp_graph *G, glp_arc *a);
+*
+*  DESCRIPTION
+*
+*  The routine glp_del_arc deletes an arc from the specified graph.
+*  The arc to be deleted must exist. */
+
+void glp_del_arc(glp_graph *G, glp_arc *a)
+{     /* some sanity checks */
+      xassert(G->na > 0);
+      xassert(1 <= a->tail->i && a->tail->i <= G->nv);
+      xassert(a->tail == G->v[a->tail->i]);
+      xassert(1 <= a->head->i && a->head->i <= G->nv);
+      xassert(a->head == G->v[a->head->i]);
+      /* remove the arc from the list of incoming arcs */
+      if (a->h_prev == NULL)
+         a->head->in = a->h_next;
+      else
+         a->h_prev->h_next = a->h_next;
+      if (a->h_next == NULL)
+         ;
+      else
+         a->h_next->h_prev = a->h_prev;
+      /* remove the arc from the list of outgoing arcs */
+      if (a->t_prev == NULL)
+         a->tail->out = a->t_next;
+      else
+         a->t_prev->t_next = a->t_next;
+      if (a->t_next == NULL)
+         ;
+      else
+         a->t_next->t_prev = a->t_prev;
+      /* free arc data, if allocated */
+      if (a->data != NULL)
+         dmp_free_atom(G->pool, a->data, G->a_size);
+      /* delete the arc from the graph */
+      dmp_free_atom(G->pool, a, sizeof(glp_arc));
+      G->na--;
+      return;
+}
+
+/***********************************************************************
+*  NAME
+*
+*  glp_erase_graph - erase graph content
+*
+*  SYNOPSIS
+*
+*  void glp_erase_graph(glp_graph *G, int v_size, int a_size);
+*
+*  DESCRIPTION
+*
+*  The routine glp_erase_graph erases the content of the specified
+*  graph. The effect of this operation is the same as if the graph
+*  would be deleted with the routine glp_delete_graph and then created
+*  anew with the routine glp_create_graph, with exception that the
+*  handle (pointer) to the graph remains valid. */
+
+static void delete_graph(glp_graph *G)
+{     dmp_delete_pool(G->pool);
+      xfree(G->v);
+      if (G->index != NULL) avl_delete_tree(G->index);
+      return;
+}
+
+void glp_erase_graph(glp_graph *G, int v_size, int a_size)
+{     if (!(0 <= v_size && v_size <= 256))
+         xerror("glp_erase_graph: v_size = %d; invalid size of vertex d"
+            "ata\n", v_size);
+      if (!(0 <= a_size && a_size <= 256))
+         xerror("glp_erase_graph: a_size = %d; invalid size of arc data"
+            "\n", a_size);
+      delete_graph(G);
+      create_graph(G, v_size, a_size);
+      return;
+}
+
+/***********************************************************************
+*  NAME
+*
+*  glp_delete_graph - delete graph
+*
+*  SYNOPSIS
+*
+*  void glp_delete_graph(glp_graph *G);
+*
+*  DESCRIPTION
+*
+*  The routine glp_delete_graph deletes the specified graph and frees
+*  all the memory allocated to this program object. */
+
+void glp_delete_graph(glp_graph *G)
+{     delete_graph(G);
+      xfree(G);
+      return;
+}
+
+/**********************************************************************/
+
+void glp_create_v_index(glp_graph *G)
+{     /* create vertex name index */
+      glp_vertex *v;
+      int i;
+      if (G->index == NULL)
+      {  G->index = avl_create_tree(avl_strcmp, NULL);
+         for (i = 1; i <= G->nv; i++)
+         {  v = G->v[i];
+            xassert(v->entry == NULL);
+            if (v->name != NULL)
+            {  v->entry = avl_insert_node(G->index, v->name);
+               avl_set_node_link(v->entry, v);
+            }
+         }
+      }
+      return;
+}
+
+int glp_find_vertex(glp_graph *G, const char *name)
+{     /* find vertex by its name */
+      AVLNODE *node;
+      int i = 0;
+      if (G->index == NULL)
+         xerror("glp_find_vertex: vertex name index does not exist\n");
+      if (!(name == NULL || name[0] == '\0' || strlen(name) > 255))
+      {  node = avl_find_node(G->index, name);
+         if (node != NULL)
+            i = ((glp_vertex *)avl_get_node_link(node))->i;
+      }
+      return i;
+}
+
+void glp_delete_v_index(glp_graph *G)
+{     /* delete vertex name index */
+      int i;
+      if (G->index != NULL)
+      {  avl_delete_tree(G->index), G->index = NULL;
+         for (i = 1; i <= G->nv; i++) G->v[i]->entry = NULL;
+      }
+      return;
+}
+
+/* eof */