!! 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.
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
  struct node {
	const char *label;
	vector<node*> succ;
	vector<double> 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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int traversal(node *a, int steps) {
	int fische = 0;
	if (steps > 0) {
		std::vector<double>::iterator it = a->prob.begin();
		std::vector<node*>::iterator next = a->succ.begin();
		double p = *it;
		double z = static_cast<double>(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;
	}
Topic archived. No new replies allowed.