C/C++ graph interface for representation of partial order

Question

In my code I use a class which represents a directed acyclic graph. I wrote the code myself, it wasn't hard. But later I realized my app has more requirements: the graph must be transitive-reduced, i.e. unique representation of a partial ordrer. Every time the user does drag-n-drop or cut/copy/paste on the visual GUI representation of the graph, it has to be validated and adapted to this requirement. Now things become more complicated. So I did plan how to perform all graph operations safely, etc., but before I really dive into the code, I'd like to know:

Is there a known C/C++ interface for partial orders? (Preferably C++)

I found many many libraries for graphs, but I already have my simple acyclic digraph code. I couldn't find anything which deals specifically with transitively-reduced graphs (I don't need an adjacency matrix, the data comes from the user so it would be inefficient here... It's a small graph for user data, not something for mathematical use)

I'm looking for an interface which automatically detects unnecessary connections and removes them, does tests to see if a node copy/move operation would be valid partial-order-wise, i.e. preserve the properties of a partial order, etc.

Answer 1

As far as I know, usually programs have their own graph classes when used for non-mathematical purposes. This happens because graphs may be much more complicated than linear containers such as the STL containers (vector, list, etc.).

Since you don't have any special needs in the field of math or algorithms (a search algorithm in your case would be a simple loop, in most cases you don't need more than that, and certainly not in the case of (premature) optimization). If you do, you have boost::graph, but I suspect it would complicate things more than help you.

So I say, write a good graph/node class, and if it's good enough and written for general-purpose, we can all benefit from that. Nobody is answering the question because there's really no existing public code which matches your needs. Write good libre code once, and it can then be used everywhere. Good luck.

P.S your own search algorithm may be much faster than ones written for general-purpose graph libraries, e.g. boost::graph, because you can take an advantage of the known restrictions and rules of you specific graph, thus making seraches much faster. For example, in a transitively-reduced graph, if A is a parent of B, then A cannot also have b as a non-child decendant (e.g. grand-child), so you can optimize your search using this knowledge. The price you pay is doing lots of tests when changing the graph, but you gain a lot back because searching/scanning can become much faster.

Answer 2

I would recommend adding a partial-order validation method. When an edit is being made, make a copy of the whole graph apply the edit to one copy, then validate it. If it passes, keep the modified copy. If it doesn't pass, revert to the saved copy.

Perhaps the validator could find all bottom nodes, for each one, build a multiset of its ancestors (or descendants if you call them that) and check for duplicate entries. I would revert to recursion for the search if you expect only small graphs.