SWI Dependency Graph

Are there any tools that can produce a dependency graph between predicates?

For example,

foo :- bar.

would result in an edge from foo to bar. It doesn’t seem like it would be very difficult to create, which leads me to wonder if someone already has done it.

I know logtalk can do this via the diagrams tool, but my application lives in a bunch of different files, and that doesn’t seem like it would be easy to load in logtalk.

SWI-Prolog XREF — Cross-Referencing Tool

Thanks @EricGT. The exact tool did not help, but it did lead me to find library(prolog_xref) and library(prolog_codewalk) which I think should do the trick.

Using prolog_walk_code/1 to identify meta predicate calls? also looks relevant.

I was able to use call_graph.pl in the other thread to accomplish what I wanted.

Yes, both library(prolog_xref) and library(prolog_codewalk) can create the data. Generate a .dot file and call graphviz and you are done. Knowing your program, I doubt it will be possible to make sense of the enormous graph. I recently wrote a similar thing for a moderate size s(CASP) program. That was barely manageable after tweaking the rules to omit a lot of stuff we considered irrelevant.

IMO a general call graph is not so useful. A dependency graph at the file/module level can work (gxref/0 can make that). Specific partial graphs may also be (the connections between a (small) set of predicates, mutual recursive loops, etc.).

edit, might be that the PDT plugin for the Eclipse IDE can do graphs?

Of related interest:

Generating Cytoscape.js graphs with SWI-Prolog

The wiki and related info still need a lot of polishing so unless you have the time to work past the glossed over parts just keep it in mind for later. :slightly_smiling_face:

1 Like

Cytoscape that @EricGT mentioned might be another way to handle those enormous graphs. It outgrew its origins long ago and seems to be a really nifty tool.

Be warned that Cytoscape is a different code base than Cytoscape.js. I have not used Cytoscape which uses Java. Cytoscape.js obviously uses JavaScript and needs a running server to present web pages.

The most complete example of using Cytoscape.js that I posted is found in this reply, click Details - Click triangle to expand. to see the code. Note that that example uses a Node.js server but IIRC I was also able to swap that out for an SWI-Prolog HTTP server thus obviating the need for node.js. The nice thing about that example is that it uses JSON data files which are easily created from SWI-Prolog dictionaries using IIRC json_write_dict/N. See
Json_dict/2 - Helpful for learning how to use JSON with SWI-Prolog dict for caveats. :slightly_smiling_face:

Thanks for all the advice.

Wow, the full Cytoscape example in Prolog is impressive :slight_smile: It makes me think perhaps I should try https://adventofcode.com/ in Prolog.

@jan I may be able to constrain the graph enough that GraphViz can handle it… we’ll see. This is actually related to better understanding rule ordering and negations.

It is not so much the tool I’m worried about, but the human trying to read and understand such enormous graphs :slight_smile: Technically, both Graphviz and Cytoscape can probably render the graph. You need to zoom in very deep to get the labels readable though, loosing all overview. In the mentioned project we used Cytoscape.js. It is less good at compact placements of nodes with varying size labels and routing edges around nodes than Graphviz. It is a lot easier to add some interactivity to the graph. So, we added search to highlight and enlarge matching nodes and their (direct) dependencies and hovering the graph with similar effects. Hopefully that will at some point become available.

When I used it (but this was a more than 10 years ago) Cytoscape was able to show only parts of the network, among many other things. My memory is not what it used to be though, I might be wrong. The filtering was based on node/edge properties so this might not be immediately available with a call graph. Maybe best ignore me on the topic :slight_smile: I most definitely used Cytoscape for different kinds of networks.

Is there a way to create IDs based on structural equivalence? I’m trying to put these terms as graph nodes, but they contain free variables.

variant_sha1/2 looks like a good candidate. Another way would be to use numbervars/4 with the option singleton(true) and write to an atom with the option numbervars(true). That is more complex, but provides a readable identifier.

You might find this of value:

Structurally equivalent (=@=) and numbervars/1

Also Graph Theory FAQs: 03. Isomorphism Using Adjacency Matrix

Jan, I am curious …

When a graph / program gets so large that become hard to understand even with a dependency graph tool – does it mean that its architectural / modular design is rather at fault …

What would best practice be …

An program easily consists of thousands of predicates … A hundred labeled predicate nodes with edges between them is already getting hard to grasp.

I guess that depends on the size, structure and what you want to know about the program. Typically being able to navigate to callers and callees satisfies for me. Very infrequently I have harder questions where my solution was to write Prolog queries over the dependency graph.

Wouldn’t modules help in limiting the interconnections, allowing “zooming” in or out to get different levels of granularity? Also, one would want to remove links to “utility” predicates, such as maplist/3 or select/3.

(For myself, I haven’t found much use for graphic tools … if the program is well-structured, the graph doesn’t add much; if it’s not well-structured, the graph is a mess)

1 Like

My case is probably very unusual. The application is a reverse engineering system that applies many interconnected rules. The rules are dictated by the system being reverse engineered and so are not “well structured”.

I’ve been trying to identify cycles of negations, ala well-founded semantics, to better understand where the system is not well defined.

Here is the graph I produced, in case anyone is curious. It’s already quite simplified.


Each edge indicates a negative dependence, i.e., an edge from A to B might be caused by A :- not(B).

Can you point to a paper(s) or blog(s) that explain those terms i.e. well-founded semantics in more detail, in particular when I read well defined I am thinking the code is expected to halt, there are no competing locks, the results are of a specific type, etc.

While I have not used sCASP I have to wonder if that might not be of use to your problem.

Well-Founded Semantics

I would say very informally that well defined indicates whether there is an unambiguous solution for the predicates as a result of negation.

I am completely unfamiliar with ASP. But the first example is quite intriguing, and seems similar to WFS:

p(A) :- not q(A).
q(A) :- not p(A).
?- p(A).
Answer 1	(in 0.09 ms):
p(A) ,  not q(A)

 ? ;

Whereas WFS describes the solution space, maybe ASP enumerates it?

I’ll have to read up more on ASP. Thank you for the link.

1 Like