2
\$\begingroup\$

I have an adjacency matrix "A" which I am using to represent a graph for a social network. Each node of the graph represents a person's name, and I am storing people's names in an 2-d array (the index of the person's name in the array is the same as the node's row index in the adjacency matrix). I wrote an algorithm to return the neighbors of node in the graph that are at most x nodes away from the node (the indices of the neighbor nodes will be stored in a binary tree and the root of the tree will be returned) but the algorithm is inefficient and takes 1-2 minutes or so to return the output, albeit a correct one. I would appreciate some advice on how to optimize this algorithm.

b_tree *get_friends(b_tree *root, int x, int y, char a_name[50] int dim) {
    /* root is root if b-tree containing pointers to the neighbors */
    /* a_name is the name of a person in the graph (want to get the neighbors of this node)*/
    /* x is maximum distance the neighbor can be from the node */
    /* y is used to keep track of x and is always 0 and dim is the length/width of matrix */
    /* M is a global variable for the matrix */
    /* name_search searches the tree and returns NULL if the index is already in the tree (to prevent duplicates) */
    /* friend_list is a global array containing the names of all the nodes in the graph (including a_name) */ 
    /* retrieve_ind returns the index of the user name in the the friend_list array */
    if (x == y - 1) return root;
    int r = retrieve_ind(a_name);
    for (int a = 0; a < dim; a++) {
        if (M[r][a] > 0) {
            if (name_search(root, a) == NULL) root = insert_in_tree(root, a);
            root = get_friends(root, x, y + 1, friend_list[a], dim);
        }
    }
    return root;
}
\$\endgroup\$
3
\$\begingroup\$

You can multiply the adjacency-matrix n times to get all paths of length n between any nodes. Therefore, if you multiply A^n * vector_with_only_your_startVertex, you can see in the resulting vector which nodes can be reached.
Make sure to also safe nodes that can be reached in less steps, because for example there may be cases where a node may be reached in 2, but not in 3 steps.
Also make sure your multyplying right-associatively, as matrix-vector multiplication is way faster than matrix-matrix multiplication.

I have no clue if this is faster though. Depends if you have a well-written matrix multiplication program that does not compute unnecessary zero-rows.

You can also always use Dijkstra's algorithm for that, in this case every edge has weight 1.
Also I don't understand why you are saving your result in a tree-structure. Unless you rely on an ordering of the elements of your result (which I guess you don't), you can use a hash-based set, which has access-time of O(1) and not O(log(N)) like trees do.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.