Debian Codegraph @

SYMPHONY/Applications/VRP/include/heurs/binomial.h

raw
1 /*===========================================================================*/
2 /* */
3 /* This file is part of a demonstration application for use with the */
4 /* SYMPHONY Branch, Cut, and Price Library. This application is a solver for */
5 /* the Vehicle Routing Problem and the Traveling Salesman Problem. */
6 /* */
7 /* This application was developed by Ted Ralphs ([email protected]) */
8 /* This file was modified by Ali Pilatin January, 2005 ([email protected]) */
9 /* */
10 /* (c) Copyright 2000-2005 Ted Ralphs. All Rights Reserved. */
11 /* */
12 /* This software is licensed under the Eclipse Public License. Please see */
13 /* accompanying file for terms. */
14 /* */
15 /*===========================================================================*/
16
17 #ifndef _BINOMIAL_H
18 #define _BINOMIAL_H
19
20 #include <memory.h>
21
22 #include "sym_proto.h"
23
24 /*----------------------------------------------------------------------*\
25 | The structure tree_node is the structure used in the binomial heaps |
26 | that I employ in savings2 in order to keep track of the savings |
27 | numbers associated with each node. The degree field denotes the |
28 | degree of that node in the tree, the parent field points to the parent |
29 | node, the child field points to the left-most child of the node, and |
30 | the sibling field points to the right sibling. The other field contain |
31 | the information about the node's savings number -- savings contains |
32 | its value while node1 and node2 denote the nodes between which it can |
33 | be inserted in order to obtain that savings number. |
34 \*----------------------------------------------------------------------*/
35
36 typedef struct TREE_NODE{
37 struct TREE_NODE *parent;
38 int degree;
39 int cust_num;
40 int savings;
41 int node1;
42 int node2;
43 struct TREE_NODE *child;
44 struct TREE_NODE *sibling;
45 }tree_node;
46
47 tree_node *find_max PROTO((tree_node *head));
48 tree_node *make_heap PROTO((int custnum, int savings,
49 int node1, int node2));
50 tree_node *merge_heaps PROTO((tree_node *head1, tree_node *head2));
51 tree_node *heap_insert PROTO((
52 tree_node * head, int cust_num, int savings,
53 int node1, int node2));
54 tree_node *extract_max PROTO((tree_node *head, tree_node *max_ptr));
55 int print_tree PROTO((tree_node *head));
56 void link_trees PROTO((tree_node *tree1, tree_node *tree2));
57 tree_node *merge_roots PROTO((tree_node *head1, tree_node *head2));
58 tree_node *reverse_list PROTO((tree_node *head));
59 void exchange_data PROTO((tree_node *tree_node1, tree_node *tree_node2));
60 void update PROTO((tree_node *cur_node, int savings, int node1,
61 int node2));
62
63 #endif
64