1 /* maxflp.c (convert maximum flow problem to LP) */
2
3 /***********************************************************************
4 * This code is part of GLPK (GNU Linear Programming Kit).
5 * Copyright (C) 2009-2016 Free Software Foundation, Inc.
6 * Written by Andrew Makhorin <mao@gnu.org>.
7 *
8 * GLPK is free software: you can redistribute it and/or modify it
9 * under the terms of the GNU General Public License as published by
10 * the Free Software Foundation, either version 3 of the License, or
11 * (at your option) any later version.
12 *
13 * GLPK is distributed in the hope that it will be useful, but WITHOUT
14 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
15 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
16 * License for more details.
17 *
18 * You should have received a copy of the GNU General Public License
19 * along with GLPK. If not, see <http://www.gnu.org/licenses/>.
20 ***********************************************************************/
21
22 #include "env.h"
23 #include "glpk.h"
24
25 /***********************************************************************
26 * NAME
27 *
28 * glp_maxflow_lp - convert maximum flow problem to LP
29 *
30 * SYNOPSIS
31 *
32 * void glp_maxflow_lp(glp_prob *lp, glp_graph *G, int names, int s,
33 * int t, int a_cap);
34 *
35 * DESCRIPTION
36 *
37 * The routine glp_maxflow_lp builds an LP problem, which corresponds
38 * to the maximum flow problem on the specified network G. */
39
glp_maxflow_lp(glp_prob * lp,glp_graph * G,int names,int s,int t,int a_cap)40 void glp_maxflow_lp(glp_prob *lp, glp_graph *G, int names, int s,
41 int t, int a_cap)
42 { glp_vertex *v;
43 glp_arc *a;
44 int i, j, type, ind[1+2];
45 double cap, val[1+2];
46 if (!(names == GLP_ON || names == GLP_OFF))
47 xerror("glp_maxflow_lp: names = %d; invalid parameter\n",
48 names);
49 if (!(1 <= s && s <= G->nv))
50 xerror("glp_maxflow_lp: s = %d; source node number out of rang"
51 "e\n", s);
52 if (!(1 <= t && t <= G->nv))
53 xerror("glp_maxflow_lp: t = %d: sink node number out of range "
54 "\n", t);
55 if (s == t)
56 xerror("glp_maxflow_lp: s = t = %d; source and sink nodes must"
57 " be distinct\n", s);
58 if (a_cap >= 0 && a_cap > G->a_size - (int)sizeof(double))
59 xerror("glp_maxflow_lp: a_cap = %d; invalid offset\n", a_cap);
60 glp_erase_prob(lp);
61 if (names) glp_set_prob_name(lp, G->name);
62 glp_set_obj_dir(lp, GLP_MAX);
63 glp_add_rows(lp, G->nv);
64 for (i = 1; i <= G->nv; i++)
65 { v = G->v[i];
66 if (names) glp_set_row_name(lp, i, v->name);
67 if (i == s)
68 type = GLP_LO;
69 else if (i == t)
70 type = GLP_UP;
71 else
72 type = GLP_FX;
73 glp_set_row_bnds(lp, i, type, 0.0, 0.0);
74 }
75 if (G->na > 0) glp_add_cols(lp, G->na);
76 for (i = 1, j = 0; i <= G->nv; i++)
77 { v = G->v[i];
78 for (a = v->out; a != NULL; a = a->t_next)
79 { j++;
80 if (names)
81 { char name[50+1];
82 sprintf(name, "x[%d,%d]", a->tail->i, a->head->i);
83 xassert(strlen(name) < sizeof(name));
84 glp_set_col_name(lp, j, name);
85 }
86 if (a->tail->i != a->head->i)
87 { ind[1] = a->tail->i, val[1] = +1.0;
88 ind[2] = a->head->i, val[2] = -1.0;
89 glp_set_mat_col(lp, j, 2, ind, val);
90 }
91 if (a_cap >= 0)
92 memcpy(&cap, (char *)a->data + a_cap, sizeof(double));
93 else
94 cap = 1.0;
95 if (cap == DBL_MAX)
96 type = GLP_LO;
97 else if (cap != 0.0)
98 type = GLP_DB;
99 else
100 type = GLP_FX;
101 glp_set_col_bnds(lp, j, type, 0.0, cap);
102 if (a->tail->i == s)
103 glp_set_obj_coef(lp, j, +1.0);
104 else if (a->head->i == s)
105 glp_set_obj_coef(lp, j, -1.0);
106 }
107 }
108 xassert(j == G->na);
109 return;
110 }
111
112 /* eof */
113