MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## Graph of dependencies from a Latex file [closed]

This question has been "manually migrated" to TeX-SX: http://tex.stackexchange.com/q/40200/86

Apologies if the question is not very appropiate for Mathoverflow. It seems to me more appropiate here than in the other 'exchange' sites.

Is there an IT tool to create a graph of dependencies from a Latex file? The sense is the following:

It just occurred to me that if everyone creates propositions with proofs (usually) afterwards and these proofs use \eqref, \ref \cite to call to other results it should be feasible to create a graph of dependencies of results, given a paper written in Latex.

I think such a thing would be useful for any mathematician (check dependencies, recursive arguments, that there are lemmas which have a need, possibility of suggesting equivalences, writing well-ordered documents...) so I would be surprised if this does not exist yet, but I couldn't find it anywhere.

-
You should ask this on tex.stackexchange.com or on the classical tex newsgroup—here it is quite off-topic. The answer to your question is «it is feasable to do such a thing», but in all likelyhood what you really want to know is how to do it. – Mariano Suárez-Alvarez Jan 5 2012 at 17:47
In every paper I write, I try to present the results so that a theorem never depends on anything that will only be proven later on. Of course if the graph of dependencies is a DAG (and it'd better be...), there is always such an ordering. – Federico Poloni Jan 5 2012 at 18:03
I think that this question is on-topic. I would really like to know the solution of this problem. – robot Jan 5 2012 at 18:05
It is more or less trivial —for someone who knows how to do it— to write latex code to instrument proof environments and \ref/\label commands so as to record the needed information on an auxiliary file durin compilation of a latex file, and then it is easy to massage that into something that can be fed into graphviz or whatnot. But none of this is MO material... – Mariano Suárez-Alvarez Jan 5 2012 at 18:38
I think the only hard part here is drawing the graph! Redefining the proof environment to write this data to a file would be easy. You could even redefine the various theorem environments to write bib references to the file as well. The problem is the graph. Drawing it won't be trivial, especially in an automated way. Another problem is that the runs through LaTeX will only output reference names to the file - getting the actual numbers/names from your TeX would require reading them from the other output files as well. Seems like a job for an external program. – Steve D Jan 6 2012 at 0:40

## closed as off topic by Mariano Suárez-Alvarez, Dmitri Pavlov, Bill Johnson, Mark Sapir, Andrew StaceyJan 6 2012 at 8:13

As a rule, you cannot depend upon math papers making every dependency explicit, meaning you cannot extract nearly so much information from this directed graph as you imagine. In addition, there isn't any reason this graph should be acyclic since forward references frequently get used in outlines and motivational text.

That said, there are use cases like identifying all the backwards references. For example, you could find all backwards \ref commands using this perl script I call earlyref.pl :

#!/usr/bin/perl -n
BEGIN {  %labels = ();  }
while (/\\(label|ref)\{([A-Za-z0-9_]+)\}/g) {
if ($1 eq "label") {$labels{$2} = 1; next; } next if ($labels{$2}); print "Early \\ref{$2} on line $. in$ARGV"
}
close if eof(ARGV);


You'll find this handles multiple filename arguments correctly because the last line resets the line number \$. when appropriate.

There is considerably more you can do using scripting languages with built in regular expressions. I've written a chcite script which changes all your \cite commands for switching between different co-authors .bib files, for example.

-

Well, it's probably time to learn regular expressions

More seriously, I don't know if a graphical tools already exists, but writing a small say Python script which parse every \ref, \eqref and \cite in each proof environment using regular expressions is rather easy. Maybe the only ambiguous things is to associate each proof environment with the corresponding theorem/lemma. Then it would again be easy to generate Graphviz code from that, and Graphviz will automatically produce a nice oriented graph showing all the dependencies.

-
You need to adopt the discipline of labelling enough items so that an easy implementation will produce meaningful results. Adopting and using such discipline is harder for many. Gerhard "Disciplining To Be Very Relaxed" Paseman, 2012.01.05 – Gerhard Paseman Jan 5 2012 at 18:52