I wonder if you could help reviewing the patches and perhaps suggest a way to fix the last part of it which is just a workaround? The patches solves the problem, but I’m very uncertain if they are the best or even the correct way to solve them.
The neatopack program is meant to take an input graph, compute its connected components, lay out each using neato, pack each layout into a single graph, and render that graph in PostScript. The code is ancient. I suspect it worked at one time but we made some changes to libgvc and didn’t fix neatopack to conform. I find it odd that the tracebacks in the bug report indicate two separate failure points. Indeed, when I used lldb on the program, I came up with a third failure point. And the fix in neatopack.c just comments out the call to gvFreeLayout. The change in ccomps.c is not necessary; the documentation notes that ccomps assumes each node already has an Agnodeinfo_t structure attached. As for neatopack itself, I would just remove it. Fixing it to work correctly with libgvc probably isn’t worth it. Let me delve into the changes to gvlayout.c. Clearly, the assumption is that gvLayoutJobs should work with subgraphs. I need to check if this is really true and, if so, are there any assumptions tied to the subgraph. Thanks for looking into this.
Thank you so much for the answers. I’m going to dig in a little deeper into the documentation. I do want to get neatopack.c working. I’ve taken this as an exercise to get better acquainted with the code and I don’t mind spending a lot more time to get it right. Also, we really need all test cases we can get.
Regarding the different backtraces; I could get different ones just by running the program many times. Also, compiling with -fsanitize=address affected the backtrace. Since the problems were caused by using uninitialized memory as a pointer, the consequences could be rather unpredictable. It was much more deterministic when using -fsanitize=address. Before fixing the first problem I got one backtrace, after that another and after fixing the second problem, a third. I wouldn’t pay that much attention to the exact backtrace.
Please note this comment in gvlayout.c: “Check that the root graph has been initialized. If not, initialize it” which was the reason I made the first fix there. Perhaps this wouldn’t be necessary either if some kind of initialization is made in neatopack.c before calling ccomps?
Also note that I consider the commented out call to gvFreeLayout in neatopack.c a workaround to get the program to finish and produce output, not a fix.
@erg I’ve updated the MR based on your input with what I think is the correct initialization. The gvFreeLayout workaround is still there though since I don’t know how it’s supposed to work for subgraphs.
@erg I’ve revisited this from the perspective of understanding how subgraph layout should work (without bothering about neatopack itself) . I’ve created a small test case and wonder if you could look at it and tell me whether it’s correct and a good representation of what subgraph layout is all about. If it’s not; could you please tell me what you’re supposed to be able to do with subgraph layout?
#include <catch2/catch.hpp>
#include <cgraph/cgraph.h>
#include <gvc/gvc.h>
TEST_CASE("subgraph layout of two subgraphs using neato") {
// NOTE: This test does not check anything yet. The purpose it just to serve
// as an example of my current understanding of how subgraph layout should
// work and see that it runs under ASan without any errors or leaking memory
// (which it currently doesn't).
auto gvc = gvContextPlugins(lt_preloaded_symbols, false);
const auto dot = R"(
graph {
subgraph {a -- b}
subgraph {c -- d}
}
)";
auto g = agmemread(dot);
for (Agraph_t *subg = agfstsubg(g); subg; subg = agnxtsubg(subg)) {
gvLayout(gvc, subg, "neato");
char *result = nullptr;
unsigned length = 0;
gvRenderData(gvc, subg, "svg", &result, &length);
gvFreeRenderData(result);
}
for (Agraph_t *subg = agfstsubg(g); subg; subg = agnxtsubg(subg)) {
gvFreeLayout(gvc, subg);
}
agclose(g);
gvFreeContext(gvc);
}
I’m more interested in understanding how subgraph layout should work, so any comments on the testcase would be much appreciated.
Yes, we have lots of code that refers to agroot(g), but it’s unclear to me if it needs to be fixed or not. Don’t we have many attributes that are valid only on root graphs? Perhaps you can elaborate on what you mean by “fix it”?
In any case, I think I’ve understood enough to be able to do the bare minimum to make it work. See:
I’m not sure how well this is documented, but we assume in various places that a root graph is being rendered. This made sense particularly when we just thought of graphviz as providing command line tools, but then people made an API out of it. But what if a subgraph is rendered instead of a root graph? Right now it probably just breaks. I’m not sure what should be done, though. Just pointing out this decision might be reconsidered.
I apologize for the delay in responding. (My health prevents me from participating as much I would like.) One would like to be able to manipulate subgraphs as though they were root graphs, especially as regards laying them out. There are (at least) two problems with this. The superficial one is that subgraphs in dot are very general, so that two subgraphs can contain the same vertices, which could be problematic in the code above. The more significant problem, which I suspect is what is causing problems now with the neatopack demo, is that there are lots of places in the graphviz layout engines where it is assumed that the graph being worked on is a root graph. Thus, my earlier recommendation to ditch demos that cause problems until someone can analyze the code to understand and fix the base problems, rather than just attaching records to avoid memory faults. There are two motivating examples for neatopack. The first is the pipeline ccomps -x graph.gv | neato | gvpack | neato -n2 This splits a graph into its connected components (thus avoiding any of the subgraph problems I alluded to above), emits them each as a root graph, lays out each individually, packs them together into a single graph, and then renders that graph. By working just with components and root graphs, one avoids the potential problems in neatopack. The other example is the code in dot (doDot() in dotinit.c) and neato/fdp/sfpd/etc. (*_layout() or *Layout() in *init.c) where each connected component is laid out individually and then everything is combined together using the function packSubgraphs(). These code snippets are much closer in spirit to the neatopack demo. Indeed, it would be interesting to take a graph that trips up neatopack and run it through neato or one of the other layout engines and see why the latter works (if it does) when the former doesn’t. Emden
What DOT source would make an interesting difference?
Not clear, as I suggested, the pipeline version and the internal neato code are roughly equivalent, using basically the same code for computing the components and later packing the components. By the way, the original neato layout (still available via mode=KK) builds packing into the layout by setting a large distance between nodes in separate components. To be honest, I’m not sure this was ever documented.
except for the single nodes x, y and z.
