Example on how to use SPQR trees

[Matheus Ota]

Hi guys,

I'm working in a problem where we need to decompose the graph in its triconnected components. In order to do this, I'm trying to use OGDF SPQR-trees, but I'm kinda lost here. Do someone have an example on how to use it?

I took a look at the documentation (http://www.ogdf.net/doc-ogdf/classogdf_1_1_s_p_q_r_tree.html) but I could not figure out how can I input a graph and get back the SPQR-tree.

Thanks,

Matheus

[Simone Ceccarelli]

Hello Matheus,

I worked a lot with this data structure in ogdf (also with one of the two inventors of this structure).

The class you linked is an Abstract class, so you can't obvously instantiate an object of that type,

but something that you can do is to instantiate an object of a subclass, 

essentially you can have a DynamicSPQRTree or a PlanarSPQRTree or a StaticSPQRTree.

I'll show you an example of use:

Graph G;

randomBiconnectedGraph(G, 50, 130);

DynamicSPQRTree spqrTreeOfG = DynamicSPQRTree(G);

I hope it helps you.

I'd like to know what you want to do with an SPQRTree, you can also write to me in private.

Bye,

Simone.

--
You received this message because you are subscribed to the Google Groups "ogdf" group.
To unsubscribe from this group and stop receiving emails from it, send an email to ogdf+uns...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/ogdf/c047da44-2f60-412c-ba85-3e6e71a73121%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Matheus Ota]

Hi Simone,

Thanks you very much for the example!

Basically, I'm trying to implement the algorithm mentioned in the paper "Processor efficient parallel algorithms for the two disjoint paths problem, and for finding a Kuratowski homeomorph". I'm just focused on the decision part, that is, given s1, t1, s2, t2, determine if there are paths pi from si to ti, i = 1,2, such that they do not intersect. In order to do this, we can decompose the original graph G into its triconnected components.

Thanks again!

Matheus

To view this discussion on the web visit https://groups.google.com/d/msgid/ogdf/CAM-T2x54n0nc3uwS-U%3DMa_M9ooP%3DLtfJisxmRE2yNSeMWv9H1g%40mail.gmail.com.

[Simone Ceccarelli]

Hi Matheus,

I really never read that paper, but as you said, maybe you can just consider the biconnected components of a specific graph, so the block cut vertex tree of a graph,

because in a biconnected block you have this property:

        - for each pair of nodes the are at least two distinct paths

        - to disconnect the graph in different parts you have to remove at least two nodes

thank you for your confidentiality,

Simone

To view this discussion on the web visit https://groups.google.com/d/msgid/ogdf/CAL0UnZ0-mtEOg%3DWh3OOmyzc99B9q3q2%2B3rFBR%2BO10O0c1ypx6w%40mail.gmail.com.