solver/solver.h at master · ustaerk/solver · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
/*
 * solver.h - Headerdatei fuer 'solver'
 *
 * (C) 2004 Ulrich Staerk
 *
 * Stellt Datenstrukturen zur Speicherung der Daten bereit
 * und enthaelt Funktionsdeklarationen.
 */

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define DEBUG 0
#define BIGINT 2147483647

/*
 * Datentyp zum Halten des kompletten Problems
 */

typedef struct problem_s
{
	int angebot;		/* # Angebotsknoten */
	int nachfrage;		/* # Nachfrageknoten */
	int num_spalten;	/* # Spalten */
	int num_zeilen;		/* # Zeilen */
	int num_kanten;
	int *zeilen;		/* Zeile gestrichen = 0 */
	int *spalten;		/* Spalte gestrichen = 0 */
	int *angebote;		/* Kapazitaet der Angebotsknoten */
	int *nachfragen;	/* Kapazitaet der Nachfrageknoten */
	int *matrix;		/* Kosten auf den Kanten */
	int *vogel_spalten;	/* Differenz zwischen besten und zweitbesten Kosten fuer die Spalten */
	int *vogel_zeilen;  /* Differenz zwischen besten und zweitbesten Kosten fuer die Zeilen */
	int *alpha;			/* alpha fuer modi */
	int *beta;			/* beta fuer modi */
} problem;

/*
 * eine Matrix (z.B. die Ergebnismatrix)
 */

typedef struct matrix_s
{
	int x;				/* x-Dimension */
	int y;				/* y-Dimension */
	int *matrix;		/* Zeiger auf Speicherbereich mit den Werten */
} matrix;

/*
 * Speichert das Maximum von vogel_spalten oder
 * vogel_zeilen und speichert dessen Position im
 * array.
 */

typedef struct vogel_s
{
	int coord;			/* int Wert mit Position in vogel_spalte bzw. vogel_zeile */
	int max;			/* Maximum-Wert */
} vogel_t;

typedef struct tmatrix_s
{
	int x;				/* x-Dimension */
	int y;				/* y-Dimension */
	int *matrix;		/* Zeiger auf Speicherbereich mit den Werten */
} tmatrix;

typedef struct node_s { int x; int y; struct node_t *next;} node;

/*
 * Funktionen aus problem.c
 */

problem *newproblem(int angebot, int nachfrage);
void streichezeile(int z, problem *p);
void streichespalte(int s, problem *p);
void updatezeile(int i, problem *p);
void updatespalte(int j, problem *p);

/*
 * Funktionen aus vogel.c
 */

void vogel(problem*);
vogel_t *vogel_max_spalten(problem *p);
vogel_t *vogel_max_zeilen(problem *p);
void waehlekante_vogel(problem*, matrix*);

/*
 * Funktionen aus common.c
 */

matrix *newmatrix(int x, int y);
void printtmatrix(tmatrix *x);
void printgraph(problem *p);
void printmatrix(matrix *x);
int min(int a, int b);

/*
 * Variablen zum Speichern der Anzahl der Knoten und Kanten
 */

int nodes,edges;

/*
 * Funktionen aus graphreader.c
 */

problem *readparameters(int *nodes, int *edges);
void readgraph(problem *p);

/*
 * Funktionen aus nwe.c
 */

void waehlekante_nwe(problem *p, matrix *x);

/*
 * Funktionen aus mkk.c
 */

void waehlekante_mkk(problem *p, matrix *x);


/*
 * Funktionen aus zyklus.c
 */

node *newnode(int x, int y);
int findezyklus(node *n, tmatrix *m);
int nextzeilennachbar(node *n, tmatrix *m, node *p);
int nextspaltennachbar(node *n, tmatrix *m, node *p);
tmatrix *newtmatrix(matrix *m);
void cycleprint(node *n);
int zykluskosten(node *n, problem *p, int i, int j);
int maxfluss(node *n, matrix *x, int i, int j);
void aenderloesung(matrix *x, node *n, int mfluss, int i, int nu);

/*
 * Funktionen aus stepstone.c
 */

void stepstone(matrix *x, problem *p);

void update_alphabeta(problem *p, tmatrix *m);
void print_alphabeta(problem *p);
void modi(problem *p, matrix *x);