How to implement "vector of vectors" structures while not using vector pointer?

Hi. I am trying to convert the Python codes for “antichains” into igraph C codes. Below are some parts of the original Python codes:

if topo_order is None:
        topo_order = list(nx.topological_sort(G))
    TC = nx.transitive_closure_dag(G, topo_order)
    antichains_stacks = [([], list(reversed(topo_order)))]
    while antichains_stacks:
        (antichain, stack) = antichains_stacks.pop()
        # Invariant:
        #  - the elements of antichain are independent
        #  - the elements of stack are independent from those of antichain
        yield antichain
        while stack:
            x = stack.pop()
            new_antichain = antichain + [x]
            new_stack = [t for t in stack if not ((t in TC[x]) or (x in TC[t]))]
            antichains_stacks.append((new_antichain, new_stack))

but the issue is that there are some parts that require to use “list of lists” functionality along with generator. There is no equivalent functionality in igraph C to “list of lists” but there is a “igraph_vector_ptr_t” which allows to insert the vector pointer, so I tried to insert two igraph vectors into a vector pointer, which is also inserted into another vector pointer. But when I tried to do this as shown below, I have got errors and could not get the appropriate results:

int find_elem(int elem, igraph_vector_t *array) {

	int i;
	int size;

	size = igraph_vector_size(array);

   	for (i = 0; i < size; i++) {

    	if ((int)VECTOR(*array)[i] == elem) {
     		return 1;
       	}
   	}

   	if ((int)VECTOR(*array)[i] != elem) {
       	return 0;
   	}
  	return 0;
}


igraph_vector_init(&topo_order, 0);
igraph_topological_sorting(L, &topo_order, IGRAPH_OUT);
TC = transitive_closure_dag(L, &topo_order);

igraph_vector_ptr_init(&antichains_stacks, 0);

igraph_vector_ptr_init(&as_list, 0);

igraph_vector_init(&antichain, 0);

igraph_vector_init(&stack, 0);
igraph_vector_copy(&stack, &topo_order);

igraph_vector_ptr_push_back(&as_list, &antichain);
igraph_vector_ptr_push_back(&as_list, &stack);

igraph_vector_ptr_push_back(&antichains_stacks, &as_list);

while (igraph_vector_ptr_size(&antichains_stacks) != 0) {
	as_list_res = igraph_vector_ptr_pop_back(&antichains_stacks);

	stack_w = igraph_vector_ptr_pop_back(as_list_res);
	antichain_w = igraph_vector_ptr_pop_back(as_list_res);

	while (igraph_vector_empty(stack_w) == 0) {
	   	igraph_vector_init(&new_antichain, 0);
		igraph_vector_init(&new_stack, 0);  

		x_w = igraph_vector_pop_back(stack_w);
		igraph_vector_push_back(antichain_w, x_w);

		igraph_vector_copy(&new_antichain, antichain_w);

		if (igraph_vector_empty(stack_w) == 0) {
			for (t = 0; t < igraph_vector_size(stack_w); t++) {
				igraph_vector_init(&tcx_eids, 0);
				igraph_vector_init(&tct_eids, 0);
			igraph_incident(&TC, &tcx_eids, x_w, IGRAPH_OUT);
			igraph_incident(&TC, &tct_eids, VECTOR(stack_w_2)[t], IGRAPH_OUT);

			if (find_elem(VECTOR(*stack_w)[t], &tcx_eids) == 0 && find_elem(x_w, &tct_eids) == 0) {
				igraph_vector_push_back(&new_stack, VECTOR(*stack_w)[t]);
			}
		}
	}

	igraph_vector_ptr_push_back(as_list_res, &new_antichain);
	igraph_vector_ptr_push_back(as_list_res, &new_stack);
	igraph_vector_ptr_push_back(&antichains_stacks, as_list_res);

	igraph_vector_ptr_destroy(as_list_res);
	igraph_vector_destroy(&new_antichain);
	igraph_vector_destroy(&new_stack);
	igraph_vector_destroy(&tcx_eids);
	igraph_vector_destroy(&tct_eids);
	igraph_vector_destroy(stack_w);
	igraph_vector_destroy(antichain_w);
}

Do you have any ideas on this? Or I hope that someone could develop “list of lists” or “vector of vectors” functionality in igraph C. Thanks in advance!

1 Like

Great to see you are trying to translate this in igraph C code!

In principle you are on the right track. However, you essentially seem to have only one pointer (i.e. only one memory address) for your vectors (e.g. stack, antichain). Instead of defining igraph_vector_t stack you should work with pointers, igraph_vector_t *stack and allocate a new igraph_vector_t using malloc. That way, you generate new pointers every time you need it, otherwise all elements of the vector_ptr essentially are the same pointers, i.e. they all refer to the same memory address. If you need more detailed explanation about this, we’d be glad to help out!

1 Like

By the way, if you are thinking of contributing this to the igraph library, feel free to open a draft PR, we can then more easily provide feedback. If you need help setting this up, we would again be happy to help out!

2 Likes

Before delving into this deep, we should think about how to deal with the fact that there may be a very large number of antichains. networkx handles this by using generators instead of returning all of them. A similar approach may not be a bad idea in igraph either, but implementing it may be a lot of extra work.

Here are the possible approaches:

  1. Return all of them in a vector_ptr—this is just not feasible.
  2. The function should take a callback, which will run for each antichain. The callback function should be able to request the termination of the search. Several igraph functions do this. This is a good option, but not as flexible as a generator, because there is no way to resume the search once interrupted.
  3. Create an object which works roughly equivalently to a Python generator. This is the best solution in my opinion, but it may be (a lot) more work to implement than 2. because we need to save all the intermediate states in it, and ideally we need to provide a serialization for higher-level languages.

Generally, igraph uses approach 2 at this moment. I would like to see it use approach 3 instead for all cases where a potentially very large number of combinatorial objects are generated.

1 Like

Good points @szhorvat! Your possibility 3 sounds really good. It would be nice to come up with a general framework for that possibility that could also be used in other contexts.

However, it also depends what @swhan is interested in. If it is meant to become part of igraph we will need to start to think about those questions. If is just meant as a user’s implementation, without becoming part of the library, this might require less attention. Of course, the issue of memory won’t go away, but this might not be a problem for him/her.

1 Like

Thank you for your helpful comments. I am trying to translate networkx’s antichains parts into igraph C because I am working on new measures for “bipartite” version of k_components or cohesive_blocks. I will let you know if this functionality is worth being contributed to igraph C library!

By the way, I am totally new to C language, so I am not relatively familiar with allocating memories using malloc. As shown below, I tried to follow your comments, but it didn’t work. Would you mind if you look at the codes below and give some more detail explanations for solving the issues? Thanks!

igraph_vector_ptr_t antichains(igraph_t *L) {
	igraph_t TC;
	igraph_vector_t topo_order, *antichain, *stack, *antichain_w, *stack_w, *new_antichain, *new_stack, tcx_eids, tct_eids;
	igraph_vector_ptr_t antichains_stacks, antichains_stacks_res, *as_list, *as_list_res;
    int x_w;
    long int t;

    igraph_vector_init(&topo_order, 0);
   	igraph_topological_sorting(L, &topo_order, IGRAPH_OUT);
   	TC = transitive_closure_dag(L, &topo_order);
    igraph_vector_ptr_init(&antichains_stacks, 0);
    igraph_vector_ptr_init(&antichains_stacks_res, 0);

    as_list = (igraph_vector_ptr_t*)malloc(sizeof(igraph_vector_ptr_t));
   	igraph_vector_ptr_init(as_list, 0);

    antichain = (igraph_vector_t*)malloc(sizeof(igraph_vector_t));
   	igraph_vector_init(antichain, 0);

   	stack = (igraph_vector_t*)malloc(sizeof(igraph_vector_t));
   	igraph_vector_init(stack, 0);
   	igraph_vector_copy(stack, &topo_order);

   	igraph_vector_ptr_push_back(as_list, antichain);
    igraph_vector_ptr_push_back(as_list, stack);
    igraph_vector_ptr_push_back(&antichains_stacks, as_list);
    igraph_vector_ptr_push_back(&antichains_stacks_res, as_list);


    while (igraph_vector_ptr_size(&antichains_stacks) != 0) {
        as_list_res = (igraph_vector_ptr_t*)malloc(sizeof(igraph_vector_ptr_t));
        as_list_res = igraph_vector_ptr_pop_back(&antichains_stacks);

		stack_w = (igraph_vector_t*)malloc(sizeof(igraph_vector_t));
		stack_w = igraph_vector_ptr_pop_back(as_list_res);
		antichain_w = (igraph_vector_t*)malloc(sizeof(igraph_vector_t));
		antichain_w = igraph_vector_ptr_pop_back(as_list_res);

   		while (igraph_vector_empty(stack_w) == 0) {
   			new_antichain = (igraph_vector_t*)malloc(sizeof(igraph_vector_t));
   		   	igraph_vector_init(new_antichain, 0);
   		    new_stack = (igraph_vector_t*)malloc(sizeof(igraph_vector_t));
   			igraph_vector_init(new_stack, 0);  

   			x_w = igraph_vector_pop_back(stack_w);
   			igraph_vector_push_back(antichain_w, x_w);

   			igraph_vector_copy(new_antichain, antichain_w);

   			if (igraph_vector_empty(stack_w) == 0) {
   				for (t = 0; t < igraph_vector_size(stack_w); t++) {
   					igraph_vector_init(&tcx_eids, 0);
   					igraph_vector_init(&tct_eids, 0);
					igraph_incident(&TC, &tcx_eids, x_w, IGRAPH_OUT);
					igraph_incident(&TC, &tct_eids, VECTOR(*stack_w)[t], IGRAPH_OUT);

					if (find_elem(VECTOR(*stack_w)[t], &tcx_eids) == 0 && find_elem(x_w, &tct_eids) == 0) {
						igraph_vector_push_back(new_stack, VECTOR(*stack_w)[t]);
					}
   				}
   			}

  			igraph_vector_ptr_push_back(as_list_res, new_antichain);
   			igraph_vector_ptr_push_back(as_list_res, new_stack);
   			igraph_vector_ptr_push_back(&antichains_stacks, as_list_res);
   			igraph_vector_ptr_push_back(&antichains_stacks_res, as_list_res);

   			// igraph_vector_ptr_destroy(as_list_res);
   			// igraph_vector_destroy(new_antichain);
   			// igraph_vector_destroy(new_stack);
   			igraph_vector_destroy(&tcx_eids);
   			igraph_vector_destroy(&tct_eids);
   			// igraph_vector_destroy(stack_w);
   			// igraph_vector_destroy(antichain_w);
   		}

	}

    return antichains_stacks_res;
}

Do you have this in GitHub somewhere? That might make it easier to provide feedback line by line.

In essence you need to do something like the following:

    
igraph_vector_ptr_t antichains;
igraph_vector_ptr_t stacks;
igraph_vector_ptr_t resulting_antichains;

igraph_vector_t *current_antichain, *current_stack, *new_antichain, *new_stack;

igraph_vector_ptr_init(&antichains, 0);
igraph_vector_ptr_init(&stacks, 0);
igraph_vector_ptr_init(&resulting_antichains, 0);

/* Initialise new stack with topological order */
new_stack = malloc(sizeof(igraph_vector_t));
igraph_vector_init(&new_stack, 0);
igraph_topological_sorting(L, new_stack, IGRAPH_OUT);

/* Push new_stack to stacks */
igraph_vector_ptr_push_back(&stacks, new_stack);

/* Add empty antichain */
new_antichain = malloc(sizeof(igraph_vector_t));
igraph_vector_init(new_antichain, 0);
igraph_vector_ptr_push_back(&antichains, new_antichain);

while (!igraph_vector_ptr_empty(&stacks))
{
    /* Pop antichain and stack from list. */
    current_antichain = igraph_vector_ptr_pop_back(&antichains);
    current_stack = igraph_vector_ptr_pop_back(&stacks);

    /* Yield antichain, i.e. store in resulting antichains list */
    igraph_vector_ptr_push(&resulting_antichains, current_antichain);

    while (!igraph_vector_empty(current_stack))
    {
        /* Create new vectors for stack and antichain */

        new_antichain = malloc(sizeof(igraph_vector_t));
        new_stack = malloc(sizeof(igraph_vector_t));

        /* Initialize new vectors */
        igraph_vector_init(new_antichain, 0);
        igraph_vector_init(new_stack, 0);

        /* Update the new_antichain*/
        igraph_vector_copy(current_antichain, new_antichain);

        igraph_real_t x = igraph_vector_pop_back(current_stack);
        igraph_vector_push_back(new_antichain, x);

        /*************************
         *form new_stack
         *************************/

        igraph_vector_ptr_push_back(&antichains, new_antichain);
        igraph_vector_ptr_push_back(&stacks, new_stack);

        /* Now point current_antichain to new_antichain, so that
         * we can use it to update the next antichain */
        current_antichain = new_antichain;
    }

    /* Free memory of current stack */
    igraph_vector_destroy(current_stack);
    free(current_stack);

    /* Do not free memory for antichain, because these are to be returned */
}
igraph_vector_ptr_destroy(stacks);
igraph_vector_ptr_destroy(antichains);
/* Result is stored in resulting_antichains, do not destroy */

The point is that you need to create a new pointer for every result that you want to store. I here left the formation of new_stack out, because it distracts from the essence about how to deal with pointers.

Note that after every iteration the current_stack is destroyed and freed. Since every stack that was allocated is always pushed to stacks, this ensures that all those vectors are correctly destroyed at the end. The current_antichain should not be destroyed/freed, because you still want to access those results afterwards.

It might be instructive to read a bit more about pointers in C, this is quite a tricky concept. See for example this tutorial.

1 Like

If you finish your code, it would be nice to see it @swhan ! Perhaps we can use it to build on it in some way to implement it immediately within igraphitself.

First of all, thank you for your help. I basically followed your code format, and revised some of the parts as shown below (including deleting NULL pointer, which keep producing segmentation fault). But there seems to exist other problems for producing antichains pointer vectors. Before assigning the pointer vector results into final output, the code correctly returns the size of the final pointer vector, which is 1, but after being assigned, the code wrongly produces a garbage value for the size of the final pointer vector.

igraph_vector_ptr_t antichains(igraph_t *L) {
	igraph_vector_ptr_t antichains, stacks, resulting_antichains;
	igraph_vector_t *current_antichain, *current_stack, *new_antichain, *new_stack, *new_antichain_w, *new_stack_w, tcx_eids, tct_eids;
	igraph_integer_t x_w;
	igraph_t TC;
	long int t;

	igraph_vector_ptr_init(&antichains, 0);
	igraph_vector_ptr_init(&stacks, 0);
	igraph_vector_ptr_init(&resulting_antichains, 0);

	new_stack = malloc(sizeof(igraph_vector_t));
	igraph_vector_init(new_stack, 0);
	igraph_topological_sorting(L, new_stack, IGRAPH_OUT);
	TC = transitive_closure_dag(L, new_stack);

	igraph_vector_ptr_push_back(&stacks, new_stack);

	new_antichain = malloc(sizeof(igraph_vector_t));
	igraph_vector_init(new_antichain, 0);
	//igraph_vector_ptr_push_back(&antichains, NULL);

	while (igraph_vector_ptr_empty(&stacks) == 0) {

		if (igraph_vector_ptr_size(&antichains) > 0) {
			current_antichain = igraph_vector_ptr_pop_back(&antichains);
			igraph_vector_ptr_push_back(&resulting_antichains, current_antichain);
		}
		current_stack = igraph_vector_ptr_pop_back(&stacks);

		while (igraph_vector_empty(current_stack) == 0) {
			new_antichain_w = malloc(sizeof(igraph_vector_t));
			new_stack_w = malloc(sizeof(igraph_vector_t));

			igraph_vector_init(new_antichain_w, 0);
			igraph_vector_init(new_stack_w, 0);

			if (igraph_vector_ptr_size(&antichains) > 0) {
				igraph_vector_copy(new_antichain_w, current_antichain);
			}

			x_w = igraph_vector_pop_back(current_stack);
			igraph_vector_push_back(new_antichain_w, x_w);

   			if (igraph_vector_empty(current_stack) == 0) {
   				for (t = 0; t < igraph_vector_size(current_stack); t++) {
   					igraph_vector_init(&tcx_eids, 0);
   					igraph_vector_init(&tct_eids, 0);
					igraph_incident(&TC, &tcx_eids, x_w, IGRAPH_OUT);
					igraph_incident(&TC, &tct_eids, VECTOR(*current_stack)[t], IGRAPH_OUT);

					if (find_elem(VECTOR(*current_stack)[t], &tcx_eids) == 0 && find_elem(x_w, &tct_eids) == 0) {
						igraph_vector_push_back(new_stack, VECTOR(*current_stack)[t]);
					}
   				}
   			}

			igraph_vector_ptr_push_back(&antichains, new_antichain_w);
			igraph_vector_ptr_push_back(&stacks, new_stack_w);

			igraph_vector_copy(current_antichain, new_antichain_w);

		}

		igraph_vector_destroy(current_stack);
		igraph_free(current_stack);
	}

	igraph_vector_ptr_destroy(&stacks);
	igraph_vector_ptr_destroy(&antichains);


	printf("antichains size: %d\n", igraph_vector_ptr_size(&resulting_antichains));

	igraph_vector_t *antichain_print;

   	for (i = 0; i < igraph_vector_ptr_size(&resulting_antichains); i++) {
   		antichain_print = igraph_vector_ptr_e(&resulting_antichains, i);
   		printf("antichain print:\n");
   		print_vector(antichain_print);

	}	

	return resulting_antichains;
}

int main(void) {

   	antichains_res = antichains(&L);

   	printf("final antichains_res size: %d\n", igraph_vector_ptr_size(&antichains_res));
}

The corresponding results are shown as follows:

antichains size: 1
antichain print:
 0
final antichains_res size: -536070100

Do you have any ideas on this?

I will upload all the codes onto GitHub as soon as I finalize the first parts of the bipartite k-components.

My apologies! There was still an error in my code. Initially I first pushed a NULL pointer, because I thought we wouldn’t need it later on. However, we do build on it later on, so the first initial new_antichain had to be pushed to antichains pointer vector. This is now corrected in the code above:

Perfectly fine to upload at some later stage, but as you are now finding out, we are copy-pasting code all the time to illustrate our points, which is less convenient and makes it more difficult to keep track of changes. It is no problem putting code on GitHub that is still being drafted, it simply makes it easier to comment on.

1 Like

Thank you so much @vtraag! I uploaded all the igraph C codes for finding all the node cuts at k connectivity level, which is the first part of my ‘bipartite’ cohesive blocking codes, onto my GitHub. But the issue is when I run the codes one by one for each case, it doesn’t have any problem at all, but when I run with the for loop, it produces segmentation fault or similar issues. @vtraag or any others, could you look at the codes and see where the errors come from? Thank you in advance!

By the way, you can find the original Python codes for “all node cuts” functionality in networkx which I translate into igraph C here. Thanks!