Manifold Geometry blog and AAG

[blobfish]

@Quaoar I recently found your blog and finally took the time to read it all. Great info and thanks so much for putting it out there.

One subject that grabbed my attention was the Attributed Adjacency Graph (AAG) as I have done quite a bit of similar work. Out of curiosity, I took a peek at the AnalysisSitus, AAG code. I based my work off of boost::graph and I spent a lot of time frustrated and confused, but at this point I am glad I did. What I like:
Constant time graph adapters, like reverse_graph, filtered_graph.
graphviz generation is supported and a must for me to reason and debug complicated graphs. picture attached.
Numerous built in algos and visitor pattern for custom DFS and BFS.
What I don't like, typical for heavily template libraries:
ugly code.
long compiles.
never ending compiler error messages.
boost graph has additional quirks that are hard work through.
Anyway I am curious about your decision to create your own graph structure. Did you look at others?

 

[Quaoar]

Hey @blobfish thanks for the kind words about the blog.

As you noticed, AAG is indeed a custom implementation of a graph data structure via an adjacency matrix. I do not have that much of an argument why I haven't used any well-proven implementation, but here is my touch:

1. Too many dependencies are something I'd like to avoid in general. Since there's no boost in AnalysisSitus, I did not want to put there boost only because I needed an undirected graph: a data structure one can put together in a couple of hours.
2. The real complexity here, in my opinion, is not in a graph, but in the feature recognition. AAG is an easy thing, although it evolved quite a bit over the years. But finding isomorphous subgraphs is probably less straightforward, and I wanted to have its native implementation as it's coupled with geometry (although one might argue that it should not).
3. I generally prefer writing things from scratch if I could, to have full control over them.

But again, in my case, I do not need any sophisticated stuff and all this graph business is straightforward to implement. For visualization, I use VTK graphs which are interactive and nice. I do not like Graphviz but having dot outcome is something one can make easily, no need in boost for that.