#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#define N 5
int Q [1024];
int Qtop = 0;
int Qbottom = 0;
void Qput (int v) {
Q [Qtop] = v;
Qtop ++;
}
int Qget (void) {
int v = Q [Qbottom];
Qbottom++;
return v;
}
int QIsNotEmpty () {
return (Qbottom < Qtop);
}
void init_adjazenzmatrix_city (int a [N][N]) {
/* Holzmarkt, 0
* Judengasse, 1
* Neckarbruecke, 2
* Jakobuskirche, 3
* Kelternplatz, 4
*/
/*
*
(Holzmarkt, Judengasse, 350m)
(Holzmarkt, Neckarbrücke, 300m)
(Holzmarkt, Jakobuskirche, 500m)
(Holzmarkt, Kelternplatz, 600m)
(Judengasse, Neckarbrücke, 160m)
(Judengasse, Jakobuskirche, 160m)
(Judengasse, Kelternplatz, 350m)
(Neckarbrücke, Jakobuskirche, 800m)
(Neckarbrücke, Kelternplatz, 950m)
(Jakobuskirche, Kelternplatz, 220m)
*/
#define HOLZMARKT 0
#define JUDENGASSE 1
#define NECKARBRUECKE 2
#define JAKOBUSKIRCHE 3
#define KELTERNPLATZ 4
a [HOLZMARKT][HOLZMARKT] = 0;
a [JUDENGASSE][JUDENGASSE] = 0;
a [JAKOBUSKIRCHE][JAKOBUSKIRCHE] = 0;
a [JUDENGASSE][JUDENGASSE] = 0;
a [NECKARBRUECKE][NECKARBRUECKE] = 0;
a [HOLZMARKT][JUDENGASSE] = 300;
a [JUDENGASSE][HOLZMARKT] = 300;
a [HOLZMARKT][NECKARBRUECKE] = 300;
a [NECKARBRUECKE][HOLZMARKT] = 300;
a [HOLZMARKT][JAKOBUSKIRCHE] = 350;
a [JAKOBUSKIRCHE][HOLZMARKT] = 350;
a [HOLZMARKT][KELTERNPLATZ] = 600;
a [KELTERNPLATZ][HOLZMARKT] = 600;
a [JUDENGASSE][NECKARBRUECKE] = 160;
a [NECKARBRUECKE][JUDENGASSE] = 160;
a [JUDENGASSE][JAKOBUSKIRCHE] = 160;
a [JAKOBUSKIRCHE][JUDENGASSE] = 160;
a [JUDENGASSE][KELTERNPLATZ] = 350;
a [KELTERNPLATZ][JUDENGASSE] = 350;
a [NECKARBRUECKE][JAKOBUSKIRCHE] = 800;
a [JAKOBUSKIRCHE][NECKARBRUECKE] = 800;
a [NECKARBRUECKE][KELTERNPLATZ] = 950;
a [KELTERNPLATZ][NECKARBRUECKE] = 950;
a [JAKOBUSKIRCHE][KELTERNPLATZ] = 220;
a [KELTERNPLATZ][JAKOBUSKIRCHE] = 220;
}
int globalsum = 0;
int stack [1024];
int stack_ptr = 1024;
void push (int v) {
stack_ptr--;
stack [stack_ptr] = v;
}
int pop () {
int v = stack [stack_ptr];
stack_ptr++;
return v;
}
int is_on_stack (int v) {
int i;
for (i = 1023; i >= stack_ptr; i--)
if (stack [i] == v)
return 1;
return 0;
}
char *tue_name [] = {"HOLZMARKT", "JUDENGASSE", "NECKARBRUECKE", "JAKOBUSKIRCHE", "KELTERNPLATZ"};
int print_stack () {
int i;
if ((stack_ptr + N) == 1024) {
for (i = stack_ptr; i < 1024; i++)
printf ("%s, ", tue_name[stack [i]]);
printf ("\n");
return 1;
}
return 0;
}
void tue_city (int a [N][N], int i, int sum) {
int j;
int flag = 0;
push (i);
for (j = 0; j < N; j++) {
if (!is_on_stack (j)) {
sum = sum + a [i][j];
tue_city (a, j, sum);
}
else
flag = 1;
}
if(print_stack ())
printf ("%i\n", sum);
pop ();
}
void breadth_first_search (int a [N][N], int *component, int *pred, int r) {
int w, v;
int i = 0;
for (i = 0; i < 1024; i++) {
pred [i] = -1;
component [i] = -1;
}
pred [r] = r;
component [r] = r;
Qput (r);
while (QIsNotEmpty ()) {
v = Qget ();
printf ("%c\n", v + 'a');
for (w = 0; w < N; w++) {
if (a [v][w]) {
if (pred [w] == -1) {
pred [w] = v;
component [w] = component [v];
Qput (w);
}
}
}
}
}
int _bfs (int a [N][N], int marked [N], int r) {
int i;
int retv;
if (marked [r] == -1) {
marked [r] = 1;
for (i = 0; i < N; i++)
if(retv = _bfs (a, marked, a [r][i]))
printf ("%c", r+'a');
return retv;
}
return 0;
}
void bfs (int a [N][N], int r) {
int i;
int marked [N];
for (i = 0; i < N; i++)
marked [i] = -1;
_bfs (a, marked, r);
}
void generate_adjanzenzmatrix (int a [N][N], int n) {
int i, j;
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
a [i][j] = -1;
}
}
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
if ((a [i][j] == -1) && (a [j][i] == -1)) {
a[j][i] = a [i][j] = rand () % 2;
}
}
}
}
void print_csv_adjanzenzmatrix (int a [N][N], int n) {
int i, j;
printf ("%c,", ' ');
for (i = 0; i < n-1; i++)
printf ("%c,", i + 'a');
printf ("%c\n", i+'a');
for (i = 0; i < n; i++) {
printf ("%c,", i+'a');
for (j = 0; j < n-1; j++) {
//printf ("%c,", a [i][j] + '0');
}
//printf ("%c\n", a [i][j] + '0');
}
}
void read_csv_adjanzenzmatrix (int a [N][N], int n) {
int i, j;
int ch;
scanf ("%c,", &ch);
for (i = 0; i < n-1; i++) {
scanf ("%c,", &ch);
}
scanf ("%c\n", &ch);
for (i = 0; i < n; i++) {
scanf ("%c,", &ch);
for (j = 0; j < n-1; j++) {
scanf ("%i,", &ch);
a [i] [j] = ch;
}
scanf ("%i\n", &ch);
a [i] [j] = ch;
}
}
void convert_csv_adjanzenzmatrix_to_adjazensliste (int a [N][N], int b [N][N], int n) {
int i, j, k;
for (i = 0; i < n; i++) {
for (j = 0, k = 0; j < n; j++) {
if (a [i][j] == 1) {
b [i][k] = j;
k++;
}
}
for (; k < n; k++)
b [i][k] = -1;
}
}
void convert_csv_adjanzenzliste_to_adjazensmatrix (int a [N][N], int b [N][N], int n) {
int i, j;
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++)
a [i][j] = 0;
}
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++)
if (b [i][j] != -1)
a [i][b[i][j]] = 1;
}
}
void read_csv_adjanzenzliste (int b [N][N], int n) {
int i, j, k;
int ch = 0;
scanf ("%c,", &ch);
for (i = 0; i < n-1; i++) {
scanf ("%c,", &ch);
}
scanf ("%c\n", &ch);
for (i = 0; i < n; i++) {
scanf ("%c,", &ch);
for (j = 0, k = 0; j < n-1; j++) {
scanf ("%c,", &ch);
if (ch == ' ')
b [i][j] = -1;
else
b [i][j] = ch - 'a';
}
scanf ("%c\n", &ch);
if (ch == ' ')
b [i][j] = -1;
else
b [i][j] = ch - 'a';
}
}
void print_csv_adjanzenzliste (int b [N][N], int n) {
int i, j;
printf ("%c,", ' ');
for (i = 0; i < n-1; i++)
printf ("%c,", i + 'a');
printf ("%c\n", i+'a');
for (i = 0; i < n; i++) {
printf ("%c,", i+'a');
for (j = 0; j < n-1; j++) {
if (b [i][j] != -1)
printf ("%c,", b [i][j] + 'a');
else
printf (" ,");
}
if (b [i][j] != -1)
printf ("%c\n", b [i][j] + 'a');
else
printf (" \n");
}
}
void print_tex (int a [N][N], int component [1024]) {
int i, j;
int codez = 8;
printf("\\documentclass{article}\n");
printf("\\usepackage[utf8]{inputenc}\n");
printf("\\usepackage{pgf, tikz}\n");
printf("\\usetikzlibrary{arrows , automata , positioning}\n");
printf("\\begin{document}\n\n");
printf("\\begin{center}\n");
printf("\\begin{tikzpicture}[>=stealth',shorten >=1pt,auto,node distance=2.5cm]\n");
printf("\%Knoten\n");
printf("\\node (a) [state, thick] {a};\n");
printf("\\node (b) [state, thick, right of= a, below of=a] {b};\n");
printf("\\node (c) [state, thick, left of= a, below of=a] {c};\n");
printf("\\node (d) [state, thick, below of=b, right of=b] {d};\n\n");
printf("\\node (e) [state, thick, below of=c, left of=c] {e};\n\n");
printf("\\node (g) [state, thick, below of=d, left of=d] {g};\n\n");
printf("\\node (f) [state, thick, below of=e, right of=e] {f};\n\n");
printf("\%Verbindungen\n");
printf("\\path[thick,->]\n");
char *leftright [] = {"left", "right"};
char *abovebelow [] = {"above", "below"};
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++) {
if (a [i] [j] == 1)
printf ("(%c) edge [bend angle=20, bend left,below] (%c)\n", (char)('a' + i), (char)('a' + j));
}
}
for (i = 0; i < N-1; i++)
printf ("(%c) edge [bend angle=20, bend left,below, style thick] (%c)\n", component [i] + 'a', component [i+1] + 'a');
printf(";\n");
printf("\\end{tikzpicture}\n");
printf("\\end{center}\n");
printf("\\end{document}\n");
}
int main (int argc, char *argv []) {
time_t t;
int n = N;
int a [N][N];
int b [N][N];
int component [1024], pred [1024];
srand ((unsigned) time (&t));
/*if (argc != 3) {
printf ("Wrong Parameter!\ng: generete generate_adjanzenzmatrix\nr: read_csv_adjanzenzmatrix\ns: read_csv_adjanzenzliste\n\np: print_csv_adjanzenzmatrix\nq: print_csv_adjanzenzliste");
return 1;
}
if (strcmp(argv [1], "r") == 0) {
read_csv_adjanzenzmatrix (a, n);
convert_csv_adjanzenzmatrix_to_adjazensliste (a, b, n);
}
else if (strcmp (argv [1], "g") == 0) {
generate_adjanzenzmatrix (a, n);
convert_csv_adjanzenzmatrix_to_adjazensliste (a, b, n);
}
else if (strcmp (argv [1], "s") == 0) {
read_csv_adjanzenzliste (b, n);
convert_csv_adjanzenzliste_to_adjazensmatrix (a, b, n);
}
else
printf ("Wrong Parameter!\ng: generete generate_adjanzenzmatrix\nr: read_csv_adjanzenzmatrix\ns: read_csv_adjanzenzliste\n\np: print_csv_adjanzenzmatrix\nq: print_csv_adjanzenzliste");
breadth_first_search (a, component, pred, 1);
if (strcmp (argv [2], "p") == 0) {
int i;
for (i = 0; i < N; i++)
printf ("%i, ", pred [i]);
print_csv_adjanzenzmatrix (a, n);
}
else if (strcmp (argv [2], "q") == 0)
print_csv_adjanzenzliste (b, n);
else if (strcmp (argv [2], "t") == 0)
print_tex (a, pred);
*/
init_adjazenzmatrix_city (a);
int i;
for (i = 0; i < N; i++)
tue_city (a, i, 0);
return 0;
}
