Openmvg: [graph] Add an openMVG graph module

[pmoulon]

Goal:

• remove the lemon dependency

Algorithm to implement:

• adjacency list
• connected component listing (largest CC)
• MST
• Biedge graph component

@ORNis, @rperrot
Here some information, if we want to implement Biedege connectivity checking and so try to remove the lemon dependency:

1. we must detect articulation point
   http://www.geeksforgeeks.org/articulation-points-or-cut-vertices-in-a-graph/
2. we must remove edge that connect articulation point to make some CC appear
3. for each CC check if it is biedge connected or not
   http://www.geeksforgeeks.org/biconnectivity-in-a-graph/

here some information regarding MST algorithms:
Computing the MST will be also a required feature. (Minimum Spanning Tree)
See Kruskal http://www.geeksforgeeks.org/greedy-algorithms-set-2-kruskals-minimum-spanning-tree-mst/ or Prim http://www.geeksforgeeks.org/greedy-algorithms-set-5-prims-minimum-spanning-tree-mst-2/ or Boruvka http://www.geeksforgeeks.org/greedy-algorithms-set-9-boruvkas-algorithm/

[rjanvier]

Hi Pierre,
very interesting doc. I will try to look at this closer soon (?). Romuald (@rperrot) are you interested by implementing something in particular? Maybe MST can be a good exercise for me.

[rperrot]

I already have a beggining of a graph implementation (early early alpha), everything is in my repository. Feel free to use it if you want and implement everything you want/need (I think, the more we have in openMVG, the best).

https://github.com/rperrot/openMVG/tree/graph/src/openMVG/graph

As it is an active development branch, I cannot garantee the stability of the basis structures but, internal structure will remain an adjacency list. The idea is that a graph will hold a list/vector of nodes, each nodes contains a list of edges that links them to the other nodes. I already have :

• Empty graph creation ;
• Graph copy construction (not fully tested) ;
• Node/Edge addition ;
• Node/Edge removal ;
• Clear a graph ;
• Connected components finding (need some utility functions) ;
• DFS traversal ;
• Exporting to a dot (graphviz) string.

Graph is undirected and generic enough to hold Generic data on nodes/edge through template. If you don't want to hold any data, I provided a NullData structure in graph_utility.hpp for this purpose (Just a note : in my oppinion it'is not the good location for this structure, it would be better to save it in an openMVG/utility folder, but we can do it latter).

That all for now (I only started on saturday). It needs a lots of testing to unsure everything is correct (destructor is not yet implemented for example), but it can be a starting point for more advanced use (or not ;-) ).

@ORNis My goal is to have enough algorithms to replace lemon in openMVG. Latter, I'd like to have basic graph algorithms (shortest paths, graph cut, min/max flow, ...), the idea is to have more algorithms to implement other utility/applications in openMVG (texture synthesis, SLAM loop closure, ...). So, basically I wanted to do everything but days are 24h long and I don't have enough time to do it, so as I said before, if you want to implement something in particular, just do it and it will makes me happy too ! I have almost everything in head so if I can help you on something, just ask me.

As we often say with Pierre, open source is here to do things we like, so do things you want/like to do (I will not feel angry if you do something I planned, rather the opposite), but if it becomes a headache, stop ;-) !

@pmoulon I also suggest the Cormen book, which has clear documentation on graph (and far more than graph) :

https://mitpress.mit.edu/books/introduction-algorithms

[rjanvier]

:+1 Ok thanks a lot @rperrot, I totally agree with you. The only big problem with the proposal I made is that I'm a kind of hobbyist and I can not guarantee delay. So feel free to implement MST on yourself if I'm not fast enough for you :) I neither won't be angry! We keep in touch.

[rperrot]

@ORNis I added a (too) simple implementation of a spanning tree, using Kruskal algorithm :

https://github.com/rperrot/openMVG/blob/graph/src/openMVG/graph/graph_spanning_tree.hpp#L71

It needs lots of improvement to get it more performant, and some tests using some special cases (I don't check if the graph is connected before, it's mandatory if we want to run it). We also need a specialized data structure to handle the heap of edges (I used std::priority_queue for a PoC), I was thinking on the pairing-heap that seems really performant (more that fibo trees).

I had to create a specialized Union Find structure (because my nodes are two general, and not indexed by int), it uses a std::map to map from nodes pointer to the correct (UnionFind) tree nodes. It adds an overhead, but I don't want to work more on UnionFind now, we'll see when integrating into openMVG if there's something to improve or if the use is marginal in the whole reconstruction process (I don't mind if our process is 10ms longer than lemon, particularly if the whole process tooks hours ;-) ).

An implementation of Prim algo would be an interesting idea to compare with the Kruskal one.

[pmoulon]

@rperrot You are right I thing it's bad to have two UFind implementation.
We could use the OpenMVG one. We have just to create the mapping from node* to int and then use the OpenMVG UFind https://github.com/rperrot/openMVG/blob/graph/src/openMVG/tracks/union_find.hpp#L30.

Or perhaps yours can be a wrapper around the existing one.. https://github.com/rperrot/openMVG/blob/graph/src/openMVG/graph/graph_union_find.hpp.
Just say that in order to try to do not duplicate the code.

[rperrot]

@pmoulon I totally agree. I think the best thing is to do it using your implementation and using a map to it. My implementation is just a utility one for my specific implementation. It's not generic enough to use it everywhere (even if I don't need the m_cc_size field).

I also think it's time to have a openMVG/datastructures (or openMVG/common) in order to store at least UnionFind and our future PriorityQueue data structures ? Since they should be generic enough to be used in all openMVG parts. I think we could list all the structures we specified for specific usage and move them in that directory. Do you agree ?

[rperrot]

Just a few questions about bi connectivity. What do we need exactly in openMVG ?

• Find articulation points ?
• Test if graph is bi-connected ?
• Extract bi-connected components ?

EDIT: forget my question, I implemented the three ones ;-)

[pmoulon]

Now we just need time to merge and test your graph implementation!