#include <stdio.h>
#include <stdlib.h>
#include "utils.h"
#include "graph.h"

int zufallSurfer(struct Graph *g,int steps, int p) {
    //Falls Graph keien Knoten enthält kehre zurück
    if (g->anzahlKnoten <= 0) {
        return 0;
    }
    //Zufälliger Startknoten
    struct Knoten* knoten = g->array[randu(g->anzahlKnoten)];
    for(int step = 0; step < steps; step++) {
        //Wenn Knoten keine Kanten hat wähle zufälligen Knoten aus dem Graph
        if(knoten->kanten <= 0) {
            knoten = g->array[randu(g->anzahlKnoten)];
            knoten->visited += 1;
        } else if(randu(100) >= (unsigned) p) {
            knoten = knoten->ausgehend[randu(knoten->kanten)];
            knoten->visited += 1;
        } else {
            knoten = g->array[randu(g->anzahlKnoten)];
            knoten->visited += 1;
        }
    }

    //Gebe Ergebnisse aus
    for(int i = 0; i < (g->anzahlKnoten); i++) {
        printf("%s \t\t %.10lf\n", g->array[i]->bezeichner, (g->array[i]->visited/((double) steps)));
    }
    return 0;
}

int markowKette(struct Graph *g,int steps, double p) {
    //Falls Graph keien Knoten enthält kehre zurück
    if (g->anzahlKnoten <= 0) {
        return 0;
    }

    double *vAlt = (double*) malloc(g->anzahlKnoten * sizeof(double));

    //erstelle Matrix
    //double mMatrix[g->anzahlKnoten][g->anzahlKnoten];

    double *matrix = (double*) malloc((g->anzahlKnoten * g->anzahlKnoten) * sizeof(double));

    for(int i = 0; i < g->anzahlKnoten; i++) {
        vAlt[i] = (double) (1 / (double) (g->anzahlKnoten));
        double outI = (double) g->array[i]->kanten;
        for(int j = 0; j < g->anzahlKnoten; j++) {
            if(outI <= 0) {
                //mMatrix[i][j] = 1 / ((double) g->anzahlKnoten);
                matrix[(i*g->anzahlKnoten)+j] = 1 / ((double) g->anzahlKnoten);
            } else {
                //mMatrix[i][j] = p / ((double) g->anzahlKnoten);
                //mMatrix[i][j] += (((1-p) * outTo(g->array[i], g->array[j])) / outI);
                matrix[(i*g->anzahlKnoten)+j] = p / ((double) g->anzahlKnoten);
                matrix[(i*g->anzahlKnoten)+j] += (((1-p) * outTo(g->array[i], g->array[j])) / outI);
            }
        }
    }

    //erstelle Array für zwischen Ergebnisse
    double *vNeu = (double*) malloc(g->anzahlKnoten * sizeof(double));

    for(int step = 0; step < steps; step++) {
        for(int j = 0; j < g->anzahlKnoten; j++) {
            for(int i = 0; i < g->anzahlKnoten; i++) {
                vNeu[j] += (vAlt[i] * matrix[(i*g->anzahlKnoten)+j]); //mMatrix[i][j]);
                printf("%f | ", vNeu[i]);
            }
        }
        for(int i = 0; i < g->anzahlKnoten; i++) {
            //Speicher Ergebniss im Knoten
            vAlt[i] = vNeu[i];
            //setze Zwischenergebnisse zurück auf 0
            vNeu[i] = 0.0;
        }
    }
    printf("\n");
    //gebe Ergebniss aus
    for(int i = 0; i < (g->anzahlKnoten); i++) {
        printf("%s \t\t %.10lf\n", g->array[i]->bezeichner, vAlt[i]);
    }
    //Gebe Speicher des Zwischenergebniss Arrays frei
    free(vNeu);
    return 0;
}