# Automatically generating a dependency graph of an arbitrary Mathematica function?

Has anyone written a function to pull the function dependencies of a function? That is, it would be nice to have a function that returns a list of function dependencies as a set of rules, terminating with built-in functions, which could then be passed straight to GraphPlot or LayeredGraphPlot. I am kind of surprised that the such a dependencies function isn't already built in.

Edit: Alright, in an attempt to contribute a little value of my own to the discussion, let me modify Szabolcs' functions:

SetAttributes[functionQ, HoldAll]
functionQ[
sym_Symbol] := (DownValues[sym] =!= {}) && (OwnValues[sym] === {})

SetAttributes[terminalQ, HoldAll]
terminalQ[sym_Symbol] := MemberQ[Attributes[sym], Protected]

SetAttributes[dependencies, HoldAll]
dependencies[sym_Symbol] :=
List @@ Select[
Union@Level[(Hold @@ DownValues[sym])[[All, 2]], {-1}, Hold,
Heads -> True], functionQ[#] || terminalQ[#] &]

SetAttributes[dependencyGraphB, HoldAll]
dependencyGraphB[sym_Symbol] :=
Module[{vertices, edges},
vertices =
FixedPoint[Union@Flatten@Join[#, dependencies /@ #] &, {sym}];
edges = Flatten[Thread[Rule[#, dependencies[#]]] & /@ vertices];
GraphPlot[edges,
VertexRenderingFunction -> (If[MemberQ[Attributes[#2], Protected],
StyleForm[Framed[#2, FrameMargins -> 1, Background -> Pink],
FontSize -> 7], "paclet:ref/" <> ToString[#2]], #1],
Text[Framed[Style[DisplayForm[#2], Black, 8],
Background -> LightBlue, FrameStyle -> Gray,
FrameMargins -> 3], #1]] &)]]


Now that I think about it, there should be precisely this sort of dependency function built in to all of the Parallel functions, so that MMA knows what definitions to send to the kernels. Unfortunately I think they avoid this more elegant method and just send every darned thing that is in the Context, which is probably overkill.

• This should be relatively easy to do. Once I made a half-working implementation inspired by this blog post. I'll try to dig up the code later and will show you how to get started. If you implement it, do come back by all means and post the full code. I'm sure many would like to try it. Jan 15, 2012 at 8:02
• Agree with @NasserM.Abbasi . It will be very hard to deal with something like ToExpression["boo"]. The only way gets into my mind is to actually run the code and to trace it. Jan 15, 2012 at 9:33
• @szabolcs: yes, thanks, this is what I was getting at. I'd be interested in the code; I am certainly too lazy to write it myself. Jan 15, 2012 at 16:01
• @Nasser Your example with ToExpression is one of the reasons why I think that ToExpression and related things (which lead to parsing at run-time) must be avoided whenever possible - they reduce the power of introspective features in Mathematica. There are cases when they may be necessary, but at least these things must be then isolated so that not many functions use them. In most cases however, creating functions at run-time is possible within the fully parsed Mathematica code. The code-analysis problem is still well-formulated though, even counting ToExpression and friends. Jan 15, 2012 at 16:51
• There is now a SymbolDependencyGraph resource function available for this: resources.wolframcloud.com/FunctionRepository/resources/… Aug 7, 2019 at 14:09

### Preamble

The problem is not as trivial as it may seem on the first glance. The main problem is that many symbols are localized by (lexical) scoping constructs and should not be counted. To fully solve this, we need a parser for Mathematica code, that would take scoping into account.

One of the most complete treatments of this problem was given by David Wagner in his Mathematica Journal article, and replicated partially in his book. I will follow his ideas but show my own implementation. I will implement a sort of a simplistic recusrive descent parser which would take scoping into account. This is not a complete thing, but it will illustrate certain subtleties involved (in particular, we should prevent premature evaluation of pieces of code during the analysis, so this is a good excercise in working with held/unevaluated expressions).

### Implementation (for illustration only, does not pretend to be complete)

Here is the code:

ClearAll[getDeclaredSymbols, getDependenciesInDeclarations, $OneStepDependencies, getSymbolDependencies, getPatternSymbols,inSymbolDependencies,$inDepends];

SetAttributes[{getDeclaredSymbols, getDependenciesInDeclarations,
getSymbolDependencies, getPatternSymbols,inSymbolDependencies}, HoldAll];

$OneStepDependencies = False; inSymbolDependencies[_] = False; globalProperties[] = {DownValues, UpValues, OwnValues, SubValues, FormatValues, NValues, Options, DefaultValues}; getDeclaredSymbols[{decs___}] := Thread@Replace[HoldComplete[{decs}], HoldPattern[a_ = rhs_] :> a, {2}]; getDependenciesInDeclarations[{decs___}, dependsF_] := Flatten@Cases[Unevaluated[{decs}], HoldPattern[Set[a_, rhs_]] :> dependsF[rhs]]; getPatternSymbols[expr_] := Cases[ Unevaluated[expr], Verbatim[Pattern][ss_, _] :> HoldComplete[ss], {0, Infinity}, Heads -> True]; getSymbolDependencies[s_Symbol, dependsF_] := Module[{result}, inSymbolDependencies[s] = True; result = Append[ Replace[ Flatten[Function[prop, prop[s]] /@ globalProperties[]], { (HoldPattern[lhs_] :> rhs_) :> With[{excl = getPatternSymbols[lhs]}, Complement[ Join[ withExcludedSymbols[dependsF[rhs], excl], Module[{res}, (* To avoid infinite recursion *) depends[s] = {HoldComplete[s]}; res = withExcludedSymbols[dependsF[lhs], excl]; depends[s] =.; res ] ], excl] ], x_ :> dependsF[x] }, {1} ], HoldComplete[s] ]; inSymbolDependencies[s] =.; result] /; ! TrueQ[inSymbolDependencies[s]]; getSymbolDependencies[s_Symbol, dependsF_] := {}; (* This function prevents leaking symbols on which global symbols colliding with ** the pattern names (symbols) may depend *) ClearAll[withExcludedSymbols]; SetAttributes[withExcludedSymbols, HoldFirst]; withExcludedSymbols[code_, syms : {___HoldComplete}] := Module[{result, alreadyDisabled }, SetAttributes[alreadyDisabled, HoldAllComplete]; alreadyDisabled[_] = False; Replace[syms, HoldComplete[s_] :> If[! inSymbolDependencies[s], inSymbolDependencies[s] = True, (* else *) alreadyDisabled[s] = True ], {1}]; result = code; Replace[syms, HoldComplete[s_] :> If[! alreadyDisabled[s], inSymbolDependencies[s] =.], {1} ]; ClearAll[alreadyDisabled]; result ]; (* The main function *) ClearAll[depends]; SetAttributes[depends, HoldAll]; depends[(RuleDelayed | SetDelayed)[lhs_, rhs_]] := With[{pts = getPatternSymbols[lhs]}, Complement[ Join[ withExcludedSymbols[depends[lhs], pts], withExcludedSymbols[depends[rhs], pts] ], pts] ]; depends[Function[Null, body_, atts_]] := depends[body]; depends[Function[body_]] := depends[body]; depends[Function[var_, body_]] := depends[Function[{var}, body]]; depends[Function[{vars__}, body_]] := Complement[depends[body], Thread[HoldComplete[{vars}]]]; depends[(With | Module)[decs_, body_]] := Complement[ Join[ depends[body], getDependenciesInDeclarations[decs, depends] ], getDeclaredSymbols[decs] ]; depends[f_[elems___]] := Union[depends[Unevaluated[f]], Sequence @@ Map[depends, Unevaluated[{elems}]]]; depends[s_Symbol /; Context[s] === "System"] := {}; depends[s_Symbol] /; !$OneStepDependencies || ! TrueQ[$inDepends] := Block[{$inDepends = True},
Union@Flatten@getSymbolDependencies[s, depends ]
];
depends[s_Symbol] := {HoldComplete[s]};
depends[a_ /; AtomQ[Unevaluated[a]]] := {};


### Illustration

First, a few simple examples:

In[100]:= depends[Function[{a,b,c},a+b+c+d]]
Out[100]= {HoldComplete[d]}

In[101]:= depends[With[{d=e},Function[{a,b,c},a+b+c+d]]]
Out[101]= {HoldComplete[e]}

In[102]:= depends[p:{a_Integer,b_Integer}:>Total[p]]
Out[102]= {}

In[103]:= depends[p:{a_Integer,b_Integer}:>Total[p]*(a+b)^c]
Out[103]= {HoldComplete[c]}


Now, a power example:

In[223]:= depends[depends]
Out[223]=
{HoldComplete[depends],HoldComplete[getDeclaredSymbols],
HoldComplete[getDependenciesInDeclarations],HoldComplete[getPatternSymbols],
HoldComplete[getSymbolDependencies],HoldComplete[globalProperties],
HoldComplete[inSymbolDependencies],HoldComplete[withExcludedSymbols],
HoldComplete[$inDepends],HoldComplete[$OneStepDependencies]}


As you can see, my code can handle recursive functions. The code of depends has many more symbols, but we only found those which are global (not localized by any of the scoping constructs).

Note that by default, all dependent symbols on all levels are included. To only get the "first-level" functions / symbols on which a given symbol depends, one has to set the variabe $OneStepDependencies to True: In[224]:=$OneStepDependencies =True;
depends[depends]

Out[225]= {HoldComplete[depends],HoldComplete[getDeclaredSymbols],
HoldComplete[getDependenciesInDeclarations],HoldComplete[getPatternSymbols],
HoldComplete[getSymbolDependencies],HoldComplete[withExcludedSymbols],
HoldComplete[$inDepends],HoldComplete[$OneStepDependencies]}


This last regime can be used to reconstruct the dependency tree, as for example suggested in the answer by @Szabolcs.

### Applicability

This answer is considerably more complex than the one by @Szabolcs, and probably also (considerably) slower, at least in some cases. When should one use it? The answer I think depends on how critical it is to find all dependencies. If one just needs to have a rough visual picture for the dependencies, then @Szabolcs's suggestion should work well in most cases. The present asnwer may have advantages when:

• You want to analyze dependencies in an arbitrary piece of code, not necessarily placed in a function (this one is easily if not super-conveniently circumvented in @Szabolcs's approach by first creating a dummy zero-argument function with your code and then analyzing that)

• It is critical for you to find all dependencies.

Things like

$functionDoingSomething = Function[var,If[test[var],f[var],g[var]]] myFunction[x_,y_]:= x+$functionDoingSomething [y]


will escape from the dependencies found by the @Szabolcs's code (as he mentioned himself in the comments), and can therefore cut away whole dependency sub-branches (for f, g and test here). There are other cases, for example related to UpValues, dependencies through Options and Defaults, and perhaps other possibilities as well.

There may be several situations when finding all dependencies correctly is critical. One is when you are using introspection programmatically, as one of the meta-programming tools - in such case you must be sure everything is correct, since you are building on top of this functionality. To generalize, you might need to use something like what I suggested (bug-free though :)), every time when the end user of this functionality will be someone (or something, like other function) other than yourself.

It may also be that you need the precise dependency picture for yourself, even if you don't intend to use it programmatically further.

In many cases however, all this is not very critical, and the suggestion by @Szabolcs may represent a better and easier alternative. The question is basically - do you want to create user-level or system-level tools.

### Limitations, flaws and subtleties

EDIT

The current version of the code certainly contains bugs. For example, it can not handle the GraphEdit example from the answer of @Szabolcs without errors. While I hope to get these bugs fixed soon, I invite anyone interested to help me debugging the code. Feel free to update the answer, once you are sure that you correctly identified and truly fixed some bugs.

END EDIT

I did not intend this to be complete, so things like UpSetDelayed and TagSetDelayed are not covered, as well as probably some others. I did not also cover dynamic scoping (Block, Table, Do, etc), because in most cases dynamic scoping still means dependencies. The code above can however be straightforwardly extended to cover the cases missed here (and I might do that soon).

The code can be refactored further to have a more readable / nicer form. I intend to do this soon.

• This is a lot more general than what I was trying to do. (I didn't try to handle generic symbols, only "functions", whatever that may mean. My approach doesn't even handle things like f = Function[...].) LanguageExtendedDefinition and LanguageExtendedFullDefinition might be useful here. Note that even LanguageExtendedFullDefinition doesn't attempt to identify localized symbols. The intended use of these functions is described here. Jan 15, 2012 at 13:56
• @Szabolcs I just fixed several bugs in the process. You can look at revision history, or just the latest code. I also added the possibility to have one-step dependencies only, rather than a full list of all symbols on which a given one depends, arbitrarily deep in the def. tree (which is what my code was initially doing). As to the generality - I find this to be absolutely essential for this problem, since otherwise you either get meaningless symbols, or run into a possibility of missing some, since people may define things like f:=.... Functions may also be defined through SubValues etc. Jan 15, 2012 at 14:01
• @Szabolcs I was using some simple version similar to what you suggested, in the past (about 3 years ago, I attempted to implement a FE-based mma IDE, but had to cancel the project due to time limitations. I used this to track dependent functions there). It was working reasonably well, so I guess in many cases the approach you suggested will suffice. You just never know :) Jan 15, 2012 at 14:04
• @berniethejet This is a very important question, and I was using this as a pretext to return some old debt to myself :). Beware that this contains bugs and is not complete yet (I hope to fix bugs and make it more complete soon, this is an important tool). Thanks for asking this, by the way. Jan 15, 2012 at 16:15
• @berniethejet I am not sure if such a function already exists, but I am sure it can be programmed based on what exists already. Some time ago, I did something silimar for TreePlot, so that one can hide the sub-trees. But, I am sure now I did it in a very sub-optimal way, plus the case of graphs would be somewhat harder. Ayways, lots of room for creativity, for someone with enough free time :) Jan 17, 2012 at 9:55

The answers from @LeonidShifrin and @Szabolcs are great, so I just want to share some incomplete thing I wrote for analyzing and visualizing Compiled "WVM" code. It's for compiler of Mathematica 7.0.1. Sorry if the code looks messy, it has been abandoned long ago.. (for the compiler version always got updated before I could figure out all the codes meaning..) If someone feel interested in it, please feel free to modify it.

(testCode = Compile[{{data, _Real, 1}, {y, _Real, 1}},
Module[{n, z, testdata},
n = Length[data];
z = (data - y)/Sqrt[Abs[y]];
testdata = 1/2 (Erf[#/Sqrt[2]] + 1) & /@ z;
(Sqrt[n] + .12 + .11/Sqrt[n]) Max[
Abs[Range[n]/n - Sort[testdata]]]
]
]) // CodeShow


btw I'm still wondering if it would be convenient to analyze the code by simulatively running and tracing it.

• Whoah, dude! That is very impressive. Am I right that you had difficulty controlling the placement of your 'Input' node in the LayeredGraphPlot so that it would stay at the top of the diagram? Jan 16, 2012 at 15:01
• @berniethejet while my answer is a little off topic, I'm glad you like its appearance.^^ In fact I just leave the layout being automatically decided by LayeredGraphPlot because guessing the code made me tired of it.. But I guess there are well developed algorithms for better arrangement of the layout. Jan 17, 2012 at 21:03
• Yeah, I am totally surprised that LayeredGraphPlot gives such good results out of the box. I have used it to plot some flowcharts but they inevitably have the 'Start' somewhere in the middle of the damned page. Jan 18, 2012 at 1:46
• @berniethejet The curves generated by LayeredGraphPlot are too arbitrary, and they're not spline! So I think a totally user-defined Graph plot function specified for flowchats will be great. Jan 19, 2012 at 1:08

I didn't find my original code, but here's a start for implementing this:

First, let's say that a "function" is a symbol that has DownValues but no OwnValues (this latter requirement is just for safety now). This needs a lot more work to get right: for example, many built-ins have no visible DownValues at all, yet they are not inert (e.g. check that DownValues[Table] === {}). I am completely ignoring any SubValues (f[a][b] := ... type definitions) for now, which should probably be considered, and I didn't even think about how UpValues can cause any trouble. Also, I didn't verify whether it causes stubs to be loaded or not.

SetAttributes[functionQ, HoldAll]
functionQ[
sym_Symbol] := (DownValues[sym] =!= {}) && (OwnValues[sym] === {})


This function will find all dependencies of the function passed to it.

SetAttributes[dependencies, HoldAll]
dependencies[sym_Symbol] := List @@ Select[
Union@Level[(Hold @@ DownValues[sym])[[All, 2]], {-1}, Hold,
functionQ
]


This one will build a graph using a very-inefficient algorithm (memoization in dependencies[] could help a lot in speeding this up, but then I'd make dependencies a localized symbol in Module below):

SetAttributes[dependencyGraph, HoldAll]
dependencyGraph[sym_Symbol] :=
Module[{vertices, edges},
vertices =
FixedPoint[Union@Flatten@Join[#, dependencies /@ #] &, {sym}];
edges =
Flatten[Thread[# \[DirectedEdge] dependencies[#]] & /@ vertices];
Graph[Tooltip[#, #] & /@ ToString /@ vertices,
Map[ToString, edges, {2}]]
]


Let's try it on some package functions. Hover the nodes to see function names as tooltips.

<< GraphUtilities

dependencyGraph[MinCut]


dependencyGraph[WeakComponents]


Or on itself:

dependencyGraph[dependecyGraph]

Show@HighlightGraph[
dependencyGraph[dependencyGraph], {"dependencyGraph"},
VertexLabels -> "Name"]


(Show here is a workaround for cutting off vertex labels)

This is just a starting point and needs a lot more work to make it useful. functionQ needs a lot more improvement, and there should be a way to limit how many dependencies are being followed (this could be implemented by checking symbol contexts: the dependency walker should stop as soon as it reaches a System or perhaps non-Global symbol. I'd make it possible to pass the dependency walker function a list of either blacklisted or whitelisted contexts, and specify a default.)

Note: Please feel free to build on this code and post an improved version as an answer.

Warning: Be careful with this function because it won't stop when it sees a System symbol and it might produce a huge graph that's slow to lay out and show:

Several people have commented above that what the OP is asking for is impossible or too difficult. I strongly disagree. These arguments could be brought up for any dynamic language (or in fact even for C itself, as it has a preprocessor and macros). You could say we shouldn't even have any code analysis in e.g. a Python IDE because it can't easily be done perfectly. Does that really mean we shouldn't do it at all, even if in the vast majority of cases a simple approach works and gives useful results?

I believe even a simple and imperfect approach can often prove very useful in practice.

• I completely agree with your last sentence (that an imperfect approach is not hard in this case, and practically useful). Perfect is the enemy of the good.
– acl
Jan 15, 2012 at 13:53
• I agree with you all also, I wasn't thinking of something perfect either. Jan 15, 2012 at 16:05
• Thanks Szabolcs, this is what I was thinking of, a nice graphic representation of the dependency network. Jan 15, 2012 at 17:25
• This will be of much help... thanks!
– CHM
Apr 17, 2012 at 2:35
• I think we'd better delete possible options like this DeleteCases[Hold @@ DownValues[sym], _ -> _, Infinity]. Because something like functionQ[PlotRange] is also True Feb 7, 2018 at 5:34

I needed something to investigate a structure of a large prototype and I needed flexibility in terms of filtering based on context/name/symbol or to capture more than symbols.

None of given answers solved my problem so I prototyped mine. Once it is production ready I will probably move it to GitHub. Meanwhile: (definitions at the bottom)

# Examples:

Needs@"GeneralUtilities";


## Basic usage

DependencyGraph[PrintDefinitions, "MaxDepth" -> 2,  GraphLayout -> "LayeredEmbedding"]


## Filter out System symbols and those starting with lower case letters

DependencyGraph[PrintDefinitions
, "MaxDepth" -> 2
, "ContextGuard" -> Not@*StringStartsQ["System"]
, "NameGuard" -> StringStartsQ[_?UpperCaseQ]
]


## By default DownValues are scanned but this can be customized:

DependencyGraph[PrintDefinitions
, "DefinitionFunction" -> Function[sym
, LanguageExtendedFullDefinition[sym, "ExcludedContexts" -> {}]
, HoldAll
]
, "NameGuard" -> StringStartsQ[_?UpperCaseQ]
]


# Source code

BeginPackage["CodeTools"];

DependencyGraph;
Dependencies;

ClearAll["*","**"];

Begin["Private"];

DependencyGraph // Attributes={HoldFirst};

DependencyGraph[symbol_Symbol, opts___Rule]:=Module[{edges}
, edges = Dependencies[symbol, Sequence @@ FilterRules[{opts},Options@Dependencies]]
; Graph[
edges,
Sequence @@ FilterRules[{opts}, Options@Graph],
VertexShapeFunction -> expressionVertexFunction
]
]

expressionVertexFunction[pos_, name_, size_]:= With[
{ label = Block[{Internal$ContextMarks = False}, RawBoxes @ ToBoxes @ Apply[HoldForm] @ name] , tooltip = Block[{Internal$ContextMarks = True}, RawBoxes @ ToBoxes @ Apply[HoldForm] @ name]
}
, Inset[Tooltip[Rotate[Style[label, Black,Bold,15],25 Degree], tooltip], pos ]
]

Dependencies//Attributes={HoldFirst};

Dependencies//Options={
"MaxDepth"     -> 1,
"SymbolGuard"  -> Function[sym, Length[DownValues[sym]] > 0, HoldFirst],
"NameGuard"    -> Function[True],
"ContextGuard" -> Function[True],
"Alternatives" -> PatternSequence[],
"DefinitionFunction" -> DownValues
};

Dependencies[symbol_Symbol, OptionsPattern[]]:=
InternalInheritedBlock[
{dependencyCollector},
Block[
{ $$maxDepth = OptionValue["MaxDepth"] ,$$additionalPattern = OptionValue["Alternatives"]
, $$symbolCheck = OptionValue["SymbolGuard"] ,$$nameCheck         = OptionValue["NameGuard"]
, $$contextCheck = OptionValue["ContextGuard"] ,$$values            = OptionValue["DefinitionFunction"]
, $symbolPattern } , $$symbolPattern = (s_Symbol /;$$contextCheck[ Context @ Unevaluated @ s ] && $$symbolCheck[ s ] &&$$nameCheck[ SymbolName @ Unevaluated @ s ] ) ; DeleteCases[n_->n_] @ DeleteDuplicates @ Flatten @ Last @ Reap @ dependencyCollector[symbol, 0] ]]; dependencyCollector[symbol_Symbol, lvl_]:= dependencyCollector[symbol, lvl] = Module[ {collector,cases} , cases = Cases[ $$values[symbol] , (found :$$additionalPattern | Except[Verbatim[Symbol][_] , _Symbol]) :> HoldComplete[found] , Infinity , Heads->True ] ; cases = DeleteCases[ HoldComplete[symbol] ] @ DeleteDuplicates @ cases ; cases = Cases[ cases, Verbatim[HoldComplete][$$additionalPattern |$$symbolPattern]] ; Sow[ HoldComplete[symbol] -> #]& /@ cases ; If[lvl + 1 >=$maxDepth, Return[Null,Module]]

; ReleaseHold @
Map[Function[expr, dependencyCollector[expr, lvl+1],HoldFirst]] @
Apply[Join] @
Cases[cases,HoldComplete[_Symbol] ]

; Null
];

End[];

EndPackage[];
`
• Thanks @Kuba, this is great. You are right that having some control over contexts is a very important aspect of this, as well as being able to control the depth/breadth of the search. May 15, 2019 at 12:11
• @berniethejet Thanks! I have more ideas but it needs to wait once I finish more important things.
– Kuba
May 15, 2019 at 12:13