27

This is inspired by the MO question here.

Suppose I'm writing a math paper, with theorem and proofs, etc. At the end of writing, I want to design a graph of dependencies, that is, a graph containing every theorem, lemma, etc., and directed arrows for when one theorem relies on some other lemma, theorem, etc. in its proof. What would be a slick way of doing this?

I know the actual drawing of the graph will be hard, so I'm more interested in how to write this data to a file in an interesting way. Just redefining the proof environment, for example, seems to work, but how to get the actual theorem numbers/names in the graph data? It seems one would have to actually redefine the ref command in a more subtle way, and I don't know how to do that.

It would be even cooler if you could control a few parameters, like maybe instead of looking "locally" at theorems, you could be more "global" and just look at chapter dependencies (and thus generate a Leitfaden), and maybe even more gradations in between. There could also be "threshold" parameters, so that one chapter has to reference another, say, 10 or more times before it becomes important enough to include in the graph data. You could even go crazy and include bibliography references too!

I don't know the appropriate tags for this, so feel free to change them.

Improve this question
3
  • 1
    If by "graph" you imply a generalized hierarchy, then I think this would be possible using a Table of Contents-like structure. Maybe?
    – Werner ♦
    Jan 6, 2012 at 4:16
  • 1
    I'm working on this here: github.com/holdenlee/depgraph
    – Holden
    Jan 26, 2015 at 1:10
  • Heh, I wrote the original question in MO and only now I found it got moved here.
    – Jesus Martinez Garcia
    Nov 16, 2020 at 22:28

2 Answers 2

Reset to default
5

This answer outlines a solution but I don't have the time to implement the suggested solution for you.

Before I start, I'd like to point out that I don't think you can do this with table of contents (TOC) because the TOC is not aware which theorem references which other theorem.

The only solution I can see it adapting the \ref command and letting it record which theorem is referenced inside other theorems. Of course, the new command has to know which theorem it is in. Once you've collected the dependencies, drawing a graph can be done automatically with a combination of TikZ and dot, which is a program that automates graph layout. See http://www.graphviz.org/ for more information about dot and http://www.fauskes.net/code/dot2tex/ for how to convert dot to LaTeX.

Improve this answer
2
  • I think it is only necessary to record the theorems referenced when in a proof-like environment. And that makes things easy, as you could simply have ref add all the references to some buffer, then when the proof environment ends, write it all out (you wait till the proof ends to ensure you've encountered a label command). But as I mentioned on the other answer, this seems easier in theory than in practice. And of course there is the conspicuous lack of code here! :)
    – Steve D
    Jan 6, 2012 at 21:52
  • 1
    Yes, true. But again, conceptualizing this is not the hard part - it is pretty much the "obvious" way to do this. The hard part is actually implementing this by reworking ref/label.
    – Steve D
    Jan 7, 2012 at 0:03
3

You could fairly easily make \ref write out a graphviz file line that goes from the current counter value to the referenced label's value, but obviously this fails if:

  • You number lemmas and theorems differently - You must somehow account for the variation, perhaps by modifying label itself. Or perhaps by writing \ref calls into the aux file and post processing the aux file into the graphviz file.
  • You place lemmas between theorems and their proofs - You should abstract access to the label's value, probably by adding some \reallabel command that temporarily changes the desired value.

As I suggested on MO, you should probably just consider your specific use cases and work out the immediate solution.

Improve this answer
4
  • I had not thought of the case of having lemmas between the theorem and the proof, but that is probably not the worst thing in the world, since in that "real world" case, the proof always begins "Proof of Theorem 4.9", etc., so a backref to the actual theorem is included right there in the proof environment! And while I agree the approach is "fairly easy", neither answer has included any code! I don't think redefining ref is such a trivial matter - correct references take 2 passes of LaTeX for a reason. The ideal redefinition of ref would wait until it was reading from the aux file...
    – Steve D
    Jan 6, 2012 at 21:48
  • ... and then use what it reads in to write the graphviz file line. I think this is easy in theory, but not so easy in practice. Simply recording the arguments to ref will not give proper naming/numbering, unless one reworks the entire ref internals themselves.
    – Steve D
    Jan 6, 2012 at 21:49
  • Your new \ref must call the original \ref, otherwise you'll never be invariant under hyperref inclusion or non-inclusion. Yes, you must write the line "[counter value] -> [dereferenced label]" to an output file, but you could dereference the label, something like \csname r@#1\endcsname (see lagtex.ltx, hyperref looks identical).
    – Jeff Burdges
    Jan 7, 2012 at 2:39
  • You cannot detect those \begin{proof}[Proof of Theorem \ref{...}} environments if they use \ref like one normally does. Not unless you parse the whole thing using Perl or Python, which sounds reasonable too.
    – Jeff Burdges
    Jan 7, 2012 at 2:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .