A graph should be traversed

Hello, I have a weighted directed graph, with 10 nodes, which begins with the node a. And the nodes are connected to each other (the specific connection is shown in the code) and the edge shows how likely (probability) it is to go to the next node. If for example the node a is connected to node b and c, and both have the same probability to got to (0.5) the first node in the list should be taken, so here b.

And the user enters the number of times the traversal function should go trough the graph. The return of the traversal function should be the number of times the node e has been accessed.

I already did some of it, if you could help me and tell me how I should access each node and check it if it's the one with the "e" or not, would be great :)


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
  #include <iostream>
#include <cstdlib>
#include <vector>

using namespace std;

// TODO: implement struct node
struct node {
        const char* label;
        vector<float> prob;
        vector<node*> succ;
};

// TODO: implement function traversal



void node_init(node* a, const char label[]  /*TODO: arguments*/) {
    a->label = label;
}

void edge_init(node* a, node* b, float probability/*TODO: arguments*/) {
    a->succ.push_back(b);
    a->prob.push_back(probability);
}

void init_graph(node* nodes   /*TODO: arguments*/) {
    node_init(nodes, "a");
    node_init(nodes+1, "b ");
    node_init(nodes+2, "c ");
    node_init(nodes+3, "d ");
    node_init(nodes+4, "e ");
    node_init(nodes+5, "f ");
    node_init(nodes+6, "g ");
    node_init(nodes+7, "h ");
    node_init(nodes+8, "i ");
    node_init(nodes+9, "j ");


    // TODO: add missing nodes
    edge_init(nodes, nodes+1, 0.5);
    edge_init(nodes, nodes+2, 0.5);
    edge_init(nodes+1, nodes+3, 0.3);
    edge_init(nodes+1, nodes+4, 0.3);
    edge_init(nodes+1, nodes+5, 0.4);
    edge_init(nodes+2, nodes+4, 0.5);
    edge_init(nodes+2, nodes+5, 0.5);
    edge_init(nodes+3, nodes, 1.0);
    edge_init(nodes+4, nodes+6, 0.5);
    edge_init(nodes+4, nodes+7, 0.5);
    edge_init(nodes+5, nodes+6, 0.25);
    edge_init(nodes+5, nodes+7, 0.25);
    edge_init(nodes+5, nodes+8, 0.25);
    edge_init(nodes+5, nodes+9, 0.25);
    edge_init(nodes+6, nodes, 1.0);
    edge_init(nodes+7, nodes, 1.0);
    edge_init(nodes+8, nodes, 1.0);
    edge_init(nodes+9, nodes, 1.0);

    // TODO: add missing edges
}

int main(int argc, char *argv[]) {
    if (argc > 1) {
        srand(time(0));
        node *nodes= new node[12];
        init_graph(nodes);
        int fische = traversal(nodes,atoi(argv[1]));
        cout << endl << "Number of e-access: " << e << endl;
        delete [] nodes;
    } else {
        cout << "Call with number of steps for traversal.\n";
    }



    return 0;
}
Last edited on
Registered users can post here. Sign in or register to post.