CODEWITHSUNDEEP
credundancy
user11125533
user11125533

Reputation: 39

How would I make this algorithm less redundant?

I am fairly new to C and cannot figure out how to make the function number_within_k_degrees() less redundant. It visits the same nodes of the graph again and again, even though they may have already been visited. I thought to remove the initial setting of all values to false to reduce it somewhat, however I don't think that does much. Any tips on how to reduce or eliminate the redundant work would be very helpful. Thanks

void find_reachable_recursive(struct person *current, int steps_remaining,
                              bool *reachable){
    // mark current root person as reachable
    reachable[person_get_index(current)] = true;
    // now deal with this person's acquaintances
    if (steps_remaining > 0){
        int num_known = person_get_num_known(current);
        for (int i = 0; i < num_known; i++){
            struct person *acquaintance = person_get_acquaintance(current, i);
            find_reachable_recursive(acquaintance, steps_remaining - 1, reachable);
        }
    }
}

// computes the number of people within k degrees of the start person
int number_within_k_degrees(struct person *start, int total_people, int k){
    bool *reachable;
    int count;

    // maintain a boolean flag for each person indicating if they are visited
    reachable = malloc(sizeof(bool) * total_people);
    for (int i = 0; i < total_people; i++){
        reachable[i] = false;
    }

    // now search for all people who are reachable with k steps
    find_reachable_recursive(start, k, reachable);

    // all visited people are marked reachable, so count them
    count = 0;
    for (int i = 0; i < total_people; i++){
        if (reachable[i] == true){
            count++;
        }
    }
    return count;
}

Upvotes: 1

Views: 73

Answers (1)

Konrad Rudolph
Konrad Rudolph

Reputation: 546005

I thought to remove the initial setting of all values to false to reduce it somewhat

That’s obviously a very bad idea: it needs to be initialised (to false) for correctness.

The real problem is that you never test whether a node has been visited yet. Since a note that was already visited does not need to be processed again, you can abort immediately:

void find_reachable_recursive(struct person *current, int steps_remaining,
                              bool *reachable){
    const int pindex = person_get_index(current);
    if (reachable[pindex]) return;
    // mark current root person as reachable
    reachable[pindex] = true;
    … rest of the code

Some further suggestions for improvements:

  1. Don’t declare variables at the beginning of your functions, declare them where you initialise them. This improves readability by pulling declaration and usage of variables together.
  2. Rather than calling malloc followed by setting values to false in a a loop, use calloc.
  3. Don’t use boolean literals in tests. Code such as if (reachable[i] == true) is redundant, and should be written as if (reachable[i]) instead.

Upvotes: 1

Related Questions