2 * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
6 * This file may be distributed and/or modified under the terms of the
7 * GNU General Public License version 2 as published by the Free Software
8 * Foundation and appearing in the file LICENSE.GPL included in the
9 * packaging of this file.
11 * Licensees holding valid libFirm Professional Edition licenses may use
12 * this file in accordance with the libFirm Commercial License.
13 * Agreement provided with the Software.
15 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
16 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * @brief Partitioned Boolean Quadratic Problem (PBQP) solver.
24 * @author Sebastian Buchwald
28 #include "adt/array.h"
29 #include "adt/xmalloc.h"
33 #include "pbqp_edge.h"
34 #include "pbqp_edge_t.h"
35 #include "pbqp_node.h"
36 #include "pbqp_node_t.h"
39 pbqp_node_t *get_node(pbqp_t *pbqp, unsigned index)
41 return pbqp->nodes[index];
44 pbqp_edge_t *get_edge(pbqp_t *pbqp, unsigned src_index, unsigned tgt_index)
48 pbqp_node_t *src_node;
49 pbqp_node_t *tgt_node;
51 if (tgt_index < src_index) {
52 unsigned tmp = src_index;
53 src_index = tgt_index;
57 src_node = get_node(pbqp, src_index);
58 tgt_node = get_node(pbqp, tgt_index);
61 len = ARR_LEN(src_node->edges);
63 for (i = 0; i < len; ++i) {
64 pbqp_edge_t *cur_edge = src_node->edges[i];
65 if (cur_edge->tgt == tgt_node) {
73 pbqp_t *alloc_pbqp(unsigned number_nodes)
75 pbqp_t *pbqp = XMALLOC(pbqp_t);
77 obstack_init(&pbqp->obstack);
80 pbqp->num_nodes = number_nodes;
82 pbqp->dump_file = NULL;
84 pbqp->nodes = OALLOCNZ(&pbqp->obstack, pbqp_node_t*, number_nodes);
98 void free_pbqp(pbqp_t *pbqp)
100 obstack_free(&pbqp->obstack, NULL);
104 void add_node_costs(pbqp_t *pbqp, unsigned node_index, vector_t *costs)
106 pbqp_node_t *node = get_node(pbqp, node_index);
109 node = alloc_node(pbqp, node_index, costs);
110 pbqp->nodes[node_index] = node;
112 vector_add(node->costs, costs);
116 void add_edge_costs(pbqp_t *pbqp, unsigned src_index, unsigned tgt_index,
117 pbqp_matrix_t *costs)
119 pbqp_edge_t *edge = get_edge(pbqp, src_index, tgt_index);
121 if (tgt_index < src_index) {
122 pbqp_matrix_transpose(pbqp, costs);
123 add_edge_costs(pbqp, tgt_index, src_index, costs);
128 edge = alloc_edge(pbqp, src_index, tgt_index, costs);
130 pbqp_matrix_add(edge->costs, costs);
134 num get_node_solution(pbqp_t *pbqp, unsigned node_index)
136 pbqp_node_t *node = get_node(pbqp, node_index);
138 return node->solution;
141 num get_solution(pbqp_t *pbqp)
143 return pbqp->solution;
147 void set_dumpfile(pbqp *pbqp, FILE *f)