7
\$\begingroup\$

Background

The code below is (obviously minimally) ripped out of a current live project. The project does reasonably sized data extraction, cleaning, analysis, clustering and visualisation (on a budget, and that's why we are not using graphistry or similar for the visualisation part).

So for our sins, we are using graphviz's very mature neato engine which implements the Kamada Kawai algorithm which has been shown to work well for our purpose (after researching many many algorithms), although it does not scale very well. We chose to interface with graphviz rather than use the Boost Graph Library. (possibly a mistake).

For this code review I am going to focus on a slim slice, which is the C++ wrapper class of the graphviz lib. And specifically on one aspect of that. How to sanely and safely interface with the many many char* params which the C-API expects.

Your friend the char*

I have included the (slimmed down) wrapper class below together with an improvised main() to show usage. The wrapper just does RAII and "method => function shoveling".

Most of graphviz's API uses char*. Are they const (i.e. are they modified when we call their API)? Who knows. They don't appear to get modified, but without reading all their source, we can't know for sure.

Do we want const std::string& or std::string_view or even, at worst const char* APIs? Yes we do.

We pass in a bunch of string (sorry char*) constants for attributes and colour names etc, small sample below.

The code as shown works fine. It's messy, I don't like it, because it uses a bunch of C-Style casts to cast away the constness. Yes I could use static_cast or reinterpret_cast or const_cast for some of these cases. Very painful syntax. In this encapsulated API I choose the C-style casts for terseness.

Is it safe and correct?

What's worse is that I believe the behaviour is not super well defined when using std:string_view. I have chosen std::string_view as my C++-end API type for all those mini-strings. There are several possible alternatives, I tried a few, but this seems reasonable given I need to store C++-end tables of, for example, colour constants (see short extract in code). -- std::string seems like heavy overkill here.

But std::string_view should not be passed to a char* because it is not guaranteed to terminate with '\0'. -- maybe that's not UB, but it's potentially bad! So does that eliminate the otherwise possibly best solution we have in modern C++?

As I said it works fine, because I know that all the strings end with '\0', but it doesn't make me happy.

Feedback wanted.

  • General on legacy C-API encapsulation class
  • Specifically on this option and alternatives for the char* API - Is my best option to deal with [const] char* in C++ too, rather than std::string_view?
#include <cgraph.h> // these 2 includes are the graphiz cgraph lib
#include <gvc.h>

#include <array>

using size_t = std::size_t;

class Graph {
public:
  Graph() {
    gvc_ = gvContext();

    static const char* fargv[] = {"neato", "-Tsvg"}; // NOLINT
    gvParseArgs(gvc_, 2, (char**)fargv);             // NOLINT

    graph_ = agopen((char*)"g", Agundirected, nullptr); // NOLINT

    // clang-format off
    set_graph_attr_def("splines",   "none");
    set_graph_attr_def("ratio",     "1.25");

    set_node_attr_def("tooltip",    "");
    set_node_attr_def("fillcolor",  "grey");
    set_node_attr_def("shape",      "point");
    set_node_attr_def("width",      "0.05");
    set_node_attr_def("penwidth",   "0");

    set_edge_attr_def("weight",     "1");
    // clang-format on
  }

  Graph(const Graph& other) = delete;
  Graph& operator=(const Graph& other) = delete;

  Graph(Graph&& other) = delete;
  Graph& operator=(Graph&& other) = delete;

  ~Graph() {
    if (graph_ != nullptr) {
      if (gvc_ != nullptr) gvFreeLayout(gvc_, graph_);
      agclose(graph_);
    }
    if (gvc_ != nullptr) gvFreeContext(gvc_);
  }

  void set_graph_attr_def(std::string_view name, std::string_view value) {
    agattr(graph_, AGRAPH, (char*)name.data(), (char*)value.data()); // NOLINT
  }

  void set_node_attr_def(std::string_view name, std::string_view value) {
    agattr(graph_, AGNODE, (char*)name.data(), (char*)value.data()); // NOLINT
  }

  void set_edge_attr_def(std::string_view name, std::string_view value) {
    agattr(graph_, AGEDGE, (char*)name.data(), (char*)value.data()); // NOLINT
  }

  void set_node_attr(Agnode_t* node, std::string_view name, std::string_view value) { // NOLINT
    agset(node, (char*)name.data(), (char*)value.data());                             // NOLINT
  }

  void set_edge_attr(Agedge_t* edge, std::string_view name, std::string_view value) { // NOLINT
    agset(edge, (char*)name.data(), (char*)value.data());                             // NOLIN
  }

  Agedge_t* add_edge(Agnode_t* src, Agnode_t* dest, std::string_view weight_str) {
    auto edge = agedge(graph_, src, dest, nullptr, 1);
    set_edge_attr(edge, "weight", weight_str);
    return edge;
  }

  Agnode_t* add_node(std::string_view node_name) {
    auto node = agnode(graph_, (char*)node_name.data(), 1); // NOLINT
    set_node_attr(node, "tooltip", node_name);
    return node;
  }

  void layout() {
    gvLayoutJobs(gvc_, graph_);
  }

  void render() {
    gvRenderJobs(gvc_, graph_);
  }

private:
  Agraph_t* graph_ = nullptr;
  GVC_t*    gvc_   = nullptr;
};

static constexpr const size_t max_colours = 30;

static constexpr const std::array<std::string_view, max_colours> colours = {
    "blue",           "green",         "red",        "gold",
    "black",          "magenta",       "brown",      "pink",
    "khaki",          "cyan",          "tan",        "blueviolet",
    "burlywood",      "cadetblue",     "chartreuse", "chocolate",
    "coral",          "darkgoldenrod", "darkgreen",  "darkkhaki",
    "darkolivegreen", "darkorange",    "darkorchid", "darksalmon",
    "darkseagreen",   "dodgerblue",    "lavender",   "mediumpurple",
    "plum",           "yellow"};

int main() {
  auto graph = Graph{}; // initializes instace of a graphviz graph

  // build node list by loading data from a mongo database

  auto node1 = graph.add_node("1");
  auto node2 = graph.add_node("2");
  // ...  10,000 + nodes  (that's all neato can handle, we would like more)

  // 2.3 is the "weight" and it's a double in our code but graphiz wants a string
  // there is a reason that the Graph::add_edge API takes the string
  // the double -> string conversion is quite expensive (we use Ryu)
  // and we need it twice. Once for graphviz and once for the cluster
  // both as a string
  graph.add_edge(node1, node2, "2.3");
  //... 2 - 25 million edges

  // run clustering algorithm on separate thread

  graph.layout(); // graphviz neato: slowest part of whole program

  // clustering has finished by now, update the colours
  graph.set_node_attr(node1, "fillcolor", colours[0]); // NOLINT
  graph.set_node_attr(node1, "fillcolor", colours[1]); // NOLINT
  // ...

  graph.render(); // sends svg to stdout
}
\$\endgroup\$
  • \$\begingroup\$ Can you provide a link to where I can get the header files? \$\endgroup\$ – pacmaninbw Jan 23 at 16:55
  • \$\begingroup\$ graphviz.org/download \$\endgroup\$ – Oliver Schönrock Jan 23 at 17:14
  • \$\begingroup\$ The graph class is following a Facade Pattern, you can do real conversions within each function, up to and including char* = new char[type.size+];. \$\endgroup\$ – pacmaninbw Jan 24 at 13:07
3
\$\begingroup\$

I see a few things that may help you improve your program.

Reconsider the tool

The graphviz package seems designed for more human-scale output graphics than your project is intending to use. The problem, as you have discovered, is that the layout does not scale linearly with the number of nodes, so your desire to process more than 10,000 nodes and millions of edges might not be a good match for graphviz, or for human consumption as a single diagram. Might GIS software such as GRASS or QGIS might be more appropriate for your use?

Use a different layout engine

The neato engine has limitations that the sfdp engine does not. If you change

static const char* fargv[] = {"neato", "-Tsvg"}; // NOLINT

to this:

static const char* fargv[] = {"sfdp", "-Tsvg"}; // NOLINT

the layout will be a bit different, but perhaps still acceptable and likely faster.

Check the fine print

You may already be aware, but in fact, the dot requires the weights to be integer values. For the reasons mentioned in the comments of your code, you may not want to change anything anyway, but it's probably useful to be aware of it and maybe also insert a comment saying "yes, I know" if that's the case.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ thanks! I tried sfdp it's much faster than neato, but the layout is next to useless for our purposes. I haven't tried "geo type" type software as this is not geo info, and I didn't make this link. This is company data, for researchers to spot clusters of companies. Not sure if that will fit, but I'll look into it. We looked at open-ord, which is very fast, but useless layout for us. Fruchterman-Reingold is good, but not faster than Kamada Kawai (neato). \$\endgroup\$ – Oliver Schönrock Jan 25 at 22:49
  • \$\begingroup\$ We can "layout, cluster and render" 10,000 nodes in a "reasonable" < 1min for the complete process. So what we do when we have more data, is we "random sample it" and then "zoom in on interesting clusters". I agree the docs say "dot expects integers" , but neato seems to work well with floats. Is there a possible performance gain with ints? I don't know, haven't tried that. But I am always open to new ideas for engines. The clustering algo we use is written in java and it is lightning fast. So we just call it with pstream. No point rewriting it. \$\endgroup\$ – Oliver Schönrock Jan 25 at 22:53
  • \$\begingroup\$ This post here was mostly about the annoying char* interface. And I solved that after getting some ideas from SO: See comments under here: stackoverflow.com/questions/59902007/… \$\endgroup\$ – Oliver Schönrock Jan 25 at 22:54
  • 1
    \$\begingroup\$ I tried it and noticed no difference with integers vs. float with neato in terms of either layout or performance, but I didn't look very closely. As for the suspected UB, it seemed to me that you have a usable answer. I'd consider re-implementing the Kamanda Kawai algorithm if performance is critical and graphviz is not delivering. Like you, I generally prefer to recycle rather than reimplement, but sometimes it's needed. \$\endgroup\$ – Edward Jan 25 at 23:11
  • 1
    \$\begingroup\$ Yes, many thanks for your time. I am currently looking into Boost graph who have a Kamada Kawei implementation. And there is some quite new research (from Asia I think) which seems to suggest that by chaining several of the historically known algorithms(tweaked a bit) you can get a 2 orders of magnitude gain. That would be great, but of course the whole thing is bascically O(n^2) so 2 orders is actually just 1, but still! \$\endgroup\$ – Oliver Schönrock Jan 25 at 23:15
3
\$\begingroup\$

Basically the code is well thought out and written.

A major observation about the code is that it is totally focused on performance/speed of execution, and not very flexible or extensible. A user of the graph class may want to add arguments to the argv through a call to a member function or an alternate version of the constructor that accepts a list of arguments. Hard coding the number of arguments in arvg (farvg) makes this impossible. It is very easy to calculate argc from argv:

        gvParseArgs(gvc_, sizeof(fargv)/ sizeof(*fargv), (char**)fargv);             // NOLINT

The variable fargv might be made into a class member variable to allow extensibility.

The use of std::array over std::vector is another place where the code is not extensible. The use of std::array also forces the creation of a constant that is only used in the initialization of the array. I understand that the use of std::vector prevents the use of constexpr but I value extensibility over optimization. Some of us old school programs say that the first rule of optimization is don't. The real first rule is find the bottle necks before optimizing.

Minor Nit

I generally put the closing }; of an std::array or std::vector initialization on a new line that is indented to the beginning of the array, it makes it a little more readable and easier to edit.

static const std::vector<std::string_view> colours = {
        "blue",           "green",         "red",        "gold",
        "black",          "magenta",       "brown",      "pink",
        "khaki",          "cyan",          "tan",        "blueviolet",
        "burlywood",      "cadetblue",     "chartreuse", "chocolate",
        "coral",          "darkgoldenrod", "darkgreen",  "darkkhaki",
        "darkolivegreen", "darkorange",    "darkorchid", "darksalmon",
        "darkseagreen",   "dodgerblue",    "lavender",   "mediumpurple",
        "plum",           "yellow"
};

Missing Header

Somehow #include <string_view> seems to have been dropped from the code.

|improve this answer|||||
\$\endgroup\$
  • 1
    \$\begingroup\$ Thanks for your feedback. Which #include is missing? Your points are well made. Clearly the fargs thing is almost a "hack". The cgraph lib is tightly coupled to their command line programmes (dot, neato etc). So the way you "configure" the main instance is you call gvParseArgs. I find it a bit weird..?! Anyway my wrapper is not designed to be run by the user with command line args etc. It's spawned from another process and the mongodb query is piped in json format, etc etc. the real argv[] is not for graphviz. But that's what the lib gives me. So I hacked it for what I need. \$\endgroup\$ – Oliver Schönrock Jan 23 at 19:23
  • \$\begingroup\$ I actually wasn't focused on performance. Well I am, but only in the very inner loop, which creates edges (2-250million of them). So you are suggesting that I should store the 200+ little colour constants (above is just an extract) in a std::vector<std::string> ? As a static class member and then make the method APIs what? std::string_view or const std::string&? \$\endgroup\$ – Oliver Schönrock Jan 23 at 19:27
  • \$\begingroup\$ many thanks for the #include...sorry about that \$\endgroup\$ – Oliver Schönrock Jan 23 at 19:27
  • \$\begingroup\$ I would find it very difficult to count 200+ colors (us) and create a constant for them. \$\endgroup\$ – pacmaninbw Jan 23 at 19:29
  • 1
    \$\begingroup\$ Thanks, but that would be a bit much. :) \$\endgroup\$ – pacmaninbw Jan 23 at 19:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.