Social network graph of characters in a novel

Question

I wrote a C program that builds a social network graph of characters in a novel. The program takes two text files as input: a list of the names of the characters in the novel, and the file of the novel itself. The output is a list of name pairs, representing times where those two names occurred within five lines of each other in the text. A graph visualisation program like Gephi can use this data to build a social network graph, where the strength of the relationship between two characters is determined by the number of times their names co-occurred.

Any feedback on my implementation would be much appreciated. In particular I would like feedback on the find_co_occurrences function, since I feel like it could be more readable, but I'm not sure how to go about achieving that.

/*
 * Name: SocialNetwork.c
 * Author: Cathal W.
 *
 * Description:
 *
 *  Program to generate a list of co-occurrences of characters in a novel.
 *  This can be used by the Gephi program to generate a social network
 *  graph displaying the relationships between the characters.
 *
 *  A co-occurrence is defined as an occurrence of one character's name,
 *  followed by the other character's name within the next 5 lines.
 *
 *  Two files are required as input: a names file and a novel file.
 *    The names file contains the names of each character, one on a new line.
 *      e.g.
 *      "Valjean
 *       Gavroche
 *       Marius"
 *
 *    The novel file contains the entire text of the novel being analysed.
 *
 *  The output produced is a .csv file with a list of co-occurrences in the
 *  following format:
 *    ""Valjean"    "Gavroche"
 *     "Valjean"    "Marius"
 *     "Gavroche"   "Marius""
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_NAMES 200
#define MAX_NAME_LEN 80
#define MAX_LINE_LEN 300
#define THRESHOLD 5 // co-occurrence threshold (in number of lines)

struct node {
    /* Node for linked list. */
    int val;
    struct node *next;
};

struct name_data {
    /* Stores the array of names, and linked lists of name occurrences. */
    char names[MAX_NAMES][MAX_NAME_LEN];
    struct node* heads[MAX_NAMES]; // the head nodes of each of the linked lists
    struct node* currs[MAX_NAMES]; // the current nodes of each of the linked lists
    int n_names;
};

const char *NAMES_FILE = "./InputFiles/Les-Mis-Names.txt";
const char *NOVEL_FILE = "./InputFiles/Les-Mis-Full-Text.txt";
const char *OUTPUT_FILE = "./co-occurences.csv";

void read_names(struct name_data *name_data, const char *names_file);
void add_occurrence(int line_num, int name_id, struct name_data *name_data);
void find_occurrences(struct name_data *name_data, const char *novel_file);
void find_co_occurrences(struct name_data *name_data, const char *output_file);

int main(void) {
    struct name_data *name_data = (struct name_data*)malloc(sizeof(struct name_data));

    read_names(name_data, NAMES_FILE);
    find_occurrences(name_data, NOVEL_FILE);
    find_co_occurrences(name_data, OUTPUT_FILE);

    return 0;
}

void read_names(struct name_data *name_data, const char *names_file) {
    /*
     * Read in the names from the file.
     *
     * Stores the array of names in name_data. If the names_file cannot be
     * opened, this function exits the program.
     */
    int i = 0;

    FILE *fp = fopen(names_file, "r+");
    if (fp == NULL) {
        perror("Error opening names file");
        exit(-1);
    }

    while (fscanf(fp, "%s", name_data->names[i++]) != EOF); // read the names
    name_data->n_names = i-1;

    fclose(fp);
}

void add_occurrence(int line_num, int name_id, struct name_data *name_data) {
    /*
     * Record the line number of an occurrence of a particular name.
     *
     * Adds the line_num to the linked list corresponding to this name (denoted
     * by name_id). If the linked list is empty, it first initialises it.
     */
    struct node *ptr = (struct node*)malloc(sizeof(struct node));
    ptr->val = line_num;
    ptr->next = NULL;

    if (name_data->heads[name_id] == NULL) { // if the list is uninitialised
        name_data->heads[name_id] = name_data->currs[name_id] = ptr;
    }
    else {
        name_data->currs[name_id]->next = ptr;
        name_data->currs[name_id] = ptr;
    }
}

void find_occurrences(struct name_data *name_data, const char *novel_file) {
    /*
     * For each name, record a linked list of the line numbers of its occurrences
     * in the novel.
     *
     * This function assumes that the names array in name_data has already been
     * generated.
     * If the novel_file cannot be opened, this function exits the program.
     */
    int line_num = 0, name_id;
    char *name, line[MAX_LINE_LEN];

    FILE *fp = fopen(novel_file, "r+");
    if (fp == NULL) {
        perror("Error opening novel file");
        exit(-1);
    }

    while (fgets(line, MAX_LINE_LEN, fp) != NULL) {
        for (name_id = 0; name_id < name_data->n_names; name_id++) {
            name = name_data->names[name_id];
            /* if the name occurs in this line */
            if (strstr(line, name) != NULL) {
                add_occurrence(line_num, name_id, name_data);
            }
        }
        line_num++;
    }

    fclose(fp);
}

void find_co_occurrences(struct name_data *name_data, const char *output_file) {
    /*
     * Generate and output a list of co-occurrences of names in the text.
     *
     * This function assumes that the linked lists in name_data have already
     * been generated.
     * If the output_file cannot be opened, this function exits the program.
     */
    int i, j;
    struct node *ptr1, *ptr2;

    FILE *fp = fopen(output_file, "w+");
    if (fp == NULL) {
        perror("Error opening output file");
        exit(-1);
    }

    /* get every pair of names */
    for (i = 0; i < name_data->n_names; i++) {
        for (j = i+1; j < name_data->n_names; j++) {
            /* then find their co-occurrences */
            ptr1 = name_data->heads[i];
            while (ptr1 != NULL) {
                ptr2 = name_data->heads[j];
                while (ptr2 != NULL) {
                    if (abs(ptr2->val - ptr1->val) <= THRESHOLD) {
                        /* output the co-occurrence */
                        fprintf(fp, "\"%s\"\t\"%s\"\n", name_data->names[i], name_data->names[j]);
                    }
                    ptr2 = ptr2->next;
                }
                ptr1 = ptr1->next;
            }
        }
    }
}

Answer 1

I see a number of things that may help you improve your code, but first let me compliment you on the nice structure and commenting of this code. It makes it much easier to understand and review and will pay dividends in the future as you (or others) maintain and/or expand the code.

Avoid scanf if you can

There are so many well known problems with scanf that you're usually better off avoiding it. The usual approach is to read in user input into a string using something like fgets to allow specifying the input buffer size (and therefore avoiding buffer overrun vulnerabilities).

Consider dynamic arrays

Rather than having fixed sizes for names and lengths of names, consider instead dynamically allocating space. Rather than the current parallel arrays structure, you might instead consider a struct for each (literary) character and then creating an array (or perhaps a linked list?) of those:

struct name_data {
    char *name;
    struct node* head;
    struct node* curr;
}

Don't hardcode file names

I undersand that it's probably just demo code, but there really isn't a good reason to hardcode the file names. Instead, it would be nice to be able to specify the file names on the command line.

Think of the user

Right now, the names are limited to single names with no space. This means that names such as "Madame Thénardier" and her husband "Thénardier" can't easily be differentiated by the user, leading to strange and frustrating results.

Don't leak memory

The program allocates memory with malloc but never calls free, resulting in a memory leak. It's better to free memory as soon as it's no longer needed by the program.

Check return values of standard functions

Many standard functions, including malloc can fail and return values that can help in detecting those failures. To write robust software, you should get into the habit of checking the return values and dealing intelligently with the potential failures. The code does a good job of cheking the return value of fopen but not fscanf, malloc, etc.

Casts are not needed for malloc

The advantage to malloc and calloc returning a void * is that no explicit cast is needed and it may be safely omitted.

Consider an alternative algorithm

Instead of going through the the entire linked list for all pairs of names in find_co_occurrences, an alternative approach might be to sweep through all linked lists more or less at the same time. By doing it this way, only a single sweep through each linked list is needed rather than many as with the current algorithm.

Another completely different possibility is to construct a N by N matrix of integers (where N is the number of names). For each intersection (or really just the upper triangle), maintain the count of co-located names. Start them all at zero and then read in threshold lines (5 in this case). Count all name pairs within these lines. Discard the first line and read the next. Count all name pairs which include names in the last line and keep going until all lines have been read.

Close the output file explicitly

Both of the functions that read input data explicitly close the file before returning, but the find_co_occurrences routine does not follow that pattern. I'd recommend adding fclose(fp); to the end of that routine.

Eliminate return 0 at the end of main

Since C99, the compiler automatically generates the code corresponding to return 0 at the end of main so there is no need to explicitly write it.