I have a question on the implementation of the Johnson's algorithm in C that is actually at the interface of theory and practice.

Link to Johnson's paper

I already implemented this algorithm in R without any issue and did the same in C but I now have only one issue with the latter implementation.

Precisely I am struggling to understand why the B-lists (the ones that keep track of the nodes that were already visited and that did not yield any circuit) don't have the same structure as the adjacency list of the initial (i.e. not the subgraphs thereafter) directed graph. With same structure I mean that each node in the B-lists should have, according to me, at most the same number of neighbours as the same node in the initial adjacency list has.

However in practice, in a sample of 300+ directed graphs, I noticed this is not the case (overflow errors and not the right number of circuits) for a very few graphs with a quite high number of circuits (1,000+) but I don't understand why (theoretical problem).

As a consequence, my initial implementation (storing the B-lists on the stack as a unique big array of length equal to the total number of edges from the initial graph) doesn't work (practical problem) but I have first to understand the underlying theory so that I can implement it in a correct way. Of course knowning the maximum size of the big array beforehand would be much better to avoid memory reallocations in C and the related loss in execution speed.

BTW in R I didn't encounter/notice this issue because you (usually) don't have to worry about memory management issues in this kind of language - the B-lists could grow and shrink dynamically without any problem.

My question is: Do you know whether there exists a non-trivial (a trivial one being the number of distinct nodes for each individual B-list) upper bound either for the length of each B-list (individual upper bound) or for the sum of all B-lists (i.e. over all the vertices - collective upper bound) and why is this collective upper bound not equal to the number of edges of the initial graph?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.