Recently I came back on the general problem of drawing the syntactic graph of a mathematical expression.
Probably some of you have already done this as students for it is a classic when you learn recursive procedures, chained lists or graphs.

I wasn't interested in doing this with Maple, because Maple had already done  a part of the job thanks to the procedure ToInert.
More of this, the package GraphTheory seemed to possess all the required features to obtain quickly this syntactic graph.
Nevertheless it took me a lot of time to fix (almost all) the problems.
The issues are mainly of two orders:

  1. ToInert is very verbose: a necessary feature when you want to have a non ambiguous syntax of an expression, but partly useless for simple visualization.
    Here is an example
    ToInert(f(x))
    _Inert_FUNCTION(_Inert_NAME("f"), _Inert_EXPSEQ(_Inert_NAME("x")))

     

  2. GraphTheory 
    Once the inert form of the expression is known, it is necessary to put it in a form that can be manipulated by the procedures of the GraphTheory package.
    More precisely one needs to transform this inert form into a set of lists [a, b], where a and b are two neighboring vertices of the syntactic graph and [a, b] the directed arc from a to b.
    As the syntactic graph is a tree, this implies using edges {a, b} instead of arcs [a, b].
    The problem is that some operators are commutative while others are not: for the latter this means that the edges and vertices on the syntactic graph must appear in an order that respects the non-commutativity.
    Here his a toy example where I manually buid the syntactic graphs of a/b and b/a: the two graphs are identical and this comes from the fact that edges in Graph( edges )  must be a set, thus an ordered structure whose order doesn't care about non-commutativity.

    restart:
    with(GraphTheory):
    # The first is aimed to represent the expression a/b
    # while the second is aimed to represent the expression b/a
    Gdiv := Graph({{"/", "a"}, {"/", "b"}}):
    g1 := DrawGraph(Gdiv, style=tree, root="/", title=a/b):
    
    Gdiv := Graph({{"/", "b"}, {"/", "a"}}):
    g2 :=DrawGraph(Gdiv, style=tree, root="/", title=b/a):
    
    plots:-display(<g1 | g2>)
    

    Download ab_ba.mw

     

After several attempts, I decided to discard the GraphTheory package, that is to deprive myself of all the interesting features one needs to manipulate a graph.

The result is given on the attached file (... and the content of the worksheet can't be loaded as usual).

Download Syntactic_Graph.mw

Here is an example


Twelve test cases are given, all the corresponding syntactic graphs are correct, but one of them (test case iexpr=1) seems incorrect because the right child of a parent P is located to the right of the left child of a parent P', even though P' is to the right of P.
This could be corrected by modifying the way the posiitons are computed in procedure Place.


PS : It doesn't seem that Maple has a built-in procedure to construct the syntactic graph of a mathematical expression.
But maybe I'm wrong?


 

 


Please Wait...