1
$\begingroup$

I would like to implement the following algorithm for finding strongly connected components in Mathematica:

enter image description here

I would prefer to keep the structure of the pseudo-algorithm, and would like each of the procedures in the pseudo-algorithm to be its own compiled function (in order to speed up computation on large graphs), i.e. procedure visit(v) in the pseudo-algorithm should look something along the lines:

 visit = 
Compile[{{v, _Integer}}, Module[{(*local variables*)},
(* specific code needed*)
], 
CompilationOptions -> {"ExpressionOptimization" -> Automatic, 
"InlineCompiledFunctions" -> Automatic, 
"InlineExternalDefinitions" -> Automatic}, 
CompilationTarget -> "C", RuntimeAttributes -> {Listable},
Parallelization -> True, RuntimeOptions -> "Speed"]

in Mathematica.

As can be seen from the pseudocode, these compiled functions would have to modify "global variables" like rindex array and integer index. How could it be possible to achieve such code structure in Mathematica?

$\endgroup$
8
  • $\begingroup$ It is possible to modify global variables but it is defanitely not a good idea since this will slow down execution so much that you'd better not compiled it. $\endgroup$ – Henrik Schumacher Jul 24 '18 at 11:28
  • $\begingroup$ It seems that this is the territory where a "hacked" solution will be needed. Is there then a potential workaround where rindex and index would be defined as local variables inside, say, compiled PEE_FIND_SCC3 procedure, and then all the other compiled functions would have access to it / would be able to modify it and finally return it to the top level function (line 5 in pseudocode)? $\endgroup$ – montyynis Jul 24 '18 at 11:33
  • $\begingroup$ Maybe. But Compile is really not made for inplace manipulations. Btw. Of course there is a very efficient implemenation available form within Mathematica. If G is your Graph, just call SparseArray`StronglyConnectedComponents[AdjacencyMatrix[G]]. $\endgroup$ – Henrik Schumacher Jul 24 '18 at 11:37
  • $\begingroup$ Moreover, there is no efficient stack data structure available from within Compile. Maybe you shoud use lists of constant and sufficiently large) size along with pointer indices to implement vS and iS. $\endgroup$ – Henrik Schumacher Jul 24 '18 at 11:39
  • $\begingroup$ I know that - ConnectedComponents[G] would do the trick too. My goal is to implement the algorithm described in pseudo-code, test it correctness / performance against Mathematica's ConnectedComponents method, and then port it to Java. $\endgroup$ – montyynis Jul 24 '18 at 11:40
2
$\begingroup$

I tried the following and it seems to work. Instead of rolling out all definitions by hand (inlining), we can do it as follows.

I am going to use a simplyfied problem here. Let's consider the following compiled function that modifies a global variable.

submodule = Compile[{}, ++c];

We want to call it from another compiled function main.

main = With[{submodule = submodule},
  Compile[{},
   Block[{c = 0},
    Do[submodule[], {100}];
    c
    ],
   CompilationTarget -> "C",
   CompilationOptions -> {"InlineCompiledFunctions" -> True}
   ]
  ]

The important point here: The previously global variable c becomes now local to main. And this is why

CompiledFunctionTools`CompilePrint[main]

does not show any calls to MainEvalulate. That's good for performance.

$\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.