### !! Due in 4 hours !! Recursive function

Hi!
I have an assignment it's called the Markov-Chain. In principe I have a Directed Graph with 10 nodes where each one is connected to 1, 2, 3, or 4 of the next nodes until the last nodes which are connected to the first node. The assignment asks me to make a traversal function which gives the label of each node and returns how many of them have the label "Fische".
Here's the link to the Graph: https://ibb.co/fh4mpb
In class we only worked with simple trees but this one has more connections and the next nodes are stored in a vector so I'm having some trouble figuring this out.

Below is the code; just ignore the probability and the main arguments.
 ``12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970`` `````` struct node { const char *label; vector succ; vector prob; }; int traversal(node*a){ // this is my function } void node_init(node *a, const char *label) { a->label = label; } void edge_init(node* a, node* b, double probability) { a->succ.push_back(b); a->prob.push_back(probability); } void init_graph(node *nodes) { node_init(nodes, "\n"); node_init(nodes + 1, "Affen "); // TODO: add missing nodes node_init(nodes + 2, "Fische"); node_init(nodes + 3, "faulenzen"); node_init(nodes + 4, "fischen"); node_init(nodes + 5, "lieben"); node_init(nodes + 6, "Bananen"); node_init(nodes + 7, "Fische"); node_init(nodes + 8, "Wasser"); node_init(nodes + 9, "Sonne"); edge_init(nodes, nodes + 1, 0.5); // TODO: add missing edges edge_init(nodes, nodes + 2, 0.5); edge_init(nodes + 1, nodes + 3, 0.5); edge_init(nodes + 1, nodes + 4, 0.5); edge_init(nodes + 1, nodes + 5, 0.5); edge_init(nodes + 2, nodes + 4, 0.5); edge_init(nodes + 2, nodes + 5, 0.5); edge_init(nodes + 3, nodes, 0.5); edge_init(nodes + 4, nodes + 6, 0.5); edge_init(nodes + 4, nodes + 7, 0.5); edge_init(nodes + 5, nodes + 6, 0.5); edge_init(nodes + 5, nodes + 7, 0.5); edge_init(nodes + 5, nodes + 8, 0.5); edge_init(nodes + 5, nodes + 9, 0.5); edge_init(nodes + 6, nodes, 0.5); edge_init(nodes + 7, nodes, 0.5); edge_init(nodes + 8, nodes, 0.5); edge_init(nodes + 9, nodes, 0.5); } int main(int argc, char *argv[]) { if (argc > 1) { //node *a; srand(time(0)); node *nodes = new node[12]; init_graph(nodes); int fische = traversal(nodes, atoi(argv[1])); cout << endl << "Number of fishes: " << fische << endl; delete[] nodes; } else { cout << "Call with number of steps for traversal.\n"; } return 0; }``````
 returns how many of them have the label "Fische".
? There is only one node "Fische"?

 the next nodes are stored in a vector so I'm having some trouble figuring this out.
The only difference is that you need an additional loop that goes over the vector.

 ``12345678910111213141516`` ``````node *find_node(node *a, const char *label) { node *result = nullptr; if(strcmp(a->label, label) == 0) result = a; else { for(size_t i = 0; i < a->succ.size(); ++i) { result = find_node(a->succ[i], label); if(result) break; } } return result; }``````
Not tested!
Last edited on
There are 2 "Fische". You can see this at the init_graph function at the 3rd and 8th node but also at the link I posted is the graph. Actually it wouldn't make much sense without the second parameter that I said to ignore. See the program should be called with the number of steps left to check through the graph so since it is a circular graph if I inputed 100 for example it would check the whole graph more than 1 time and output more than 2 nodes with the label "Fische". Anyhoo I'm posting the solution for future victims of this or a similar assignment and thanks for the help coder777.

 ``1234567891011121314151617181920`` ``````int traversal(node *a, int steps) { int fische = 0; if (steps > 0) { std::vector::iterator it = a->prob.begin(); std::vector::iterator next = a->succ.begin(); double p = *it; double z = static_cast(rand()) / RAND_MAX; while (p < z) { it++; next++; p += *it; } cout << a->label; if (a->label == "Fische ") { fische++; } fische += traversal(*next, steps - 1); } return fische; }``````