| 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 |
|