Implementation approach for Maximal Planar

[Mohit242-bit]

Hii @cvvergara @robe,
I have a design question about pgr_makeMaximalPlanar.

According to Boost 1.91.0 documentation:

• make_biconnected_planar requires a connected planar graph as input

• make_maximal_planar requires a biconnected planar graph as input.

The official Boost 1.91.0 example for make_maximal_planar (make_maximal_planar.cpp) starts with a path graph (which is connected but NOT biconnected) and calls make_biconnected_planar before calling make_maximal_planar:

So in my current implementation, pgr_makeMaximalPlanar follows this same pattern - it internally calls make_biconnected_planar first, then make_maximal_planar. If a user calls pgr_makeMaximalPlanar on a non-biconnected graph, it won’t give an error, it will silently make it biconnected first and then make it maximal planar.

However, I noticed an inconsistency in Boost’s own examples. The official example for make_biconnected_planar (make_biconnected_planar.cpp) does NOT call make_connected before calling make_biconnected_planar, even though the documentation says make_biconnected_planar requires a connected graph. Boost’s example just uses a graph that happens to already be connected.This raises the same question for pgr_makeBiconnectedPlanar: what if a user passes a disconnected graph? Should we also internally call make_connected first, or just return an error ?(give connected graph as input or empty result)

So the pattern seems inconsistent in boost :

• make_maximal_planar example → handles its prerequisite (calls make_biconnected_planar first)

• make_biconnected_planar example → does NOT handle its prerequisite (does not call make_connected first)

Also in the existing pgRouting codebase, functions do NOT enforce their prerequisites internally. For example, pgr_dagShortestPath requires the input to be a DAG (Directed Acyclic Graph), but it does NOT check this , it just calls boost::dag_shortest_paths() directly, and if the user passes a graph with cycles, they get an error from Boost.

This confuses me on which approach I should follow for my implementation:

Option A (Matches Boost’s make_maximal_planar.cpp): pgr_makeMaximalPlanar internally calls make_biconnected_planar first. But then by the same logic, shouldn’t pgr_makeBiconnectedPlanar also internally call make_connected first?

Option B (Each function does only its own job): pgr_makeMaximalPlanar only calls make_maximal_planar. If the graph is not biconnected, it returns an empty result or an error(Give biconnected graph as input) . The user must call pgr_makeBiconnectedPlanar separately first. This is consistent with how pgr_makeBiconnectedPlanar currently works (it does not call make_connected internally).

Which approach would you prefer?

Thank you !

[cvvergara]

I prefer the approach of:
It gets a graph, that probably its a forest of graphs (aka, it has sub-graphs)
you find the components, and create filtered boost graphs one per component.
then you process each graph.

You can start with:
Make It work with a connected graph first. When that is working then make it work when its more than one component by filtering the graph.

Its easier to do:

if (the graph is not connected) {
  tell the user that it can not be processed
  return;
}

than do some more preprocessing

array[G] graphs;
graphs = get_components(graph)

and get the sub-graphs

You will not ever be the first one or the last one that is not open to more options, and you will not ever be the first one or the last one that doesn’t read the documentation of what ever, and you will never be the first one or the last one the does/thinks/needs X.

Real pgRouting example (from when pgRouting was a baby) about first make it work for X, then make it work by breaking the problem (equivalent to: make it work with the one connected graph then make it work with the components of a graph);

This is an old C file, and now lets read what boost says about Dijkstra.
And do a similar objection without your bold letters (that was so rude):
The documentation on boost ONLY receives a source vertex, “The algorithm solves the single-source shortest-paths problem” there is not target vertex in the function. If you see the boost example, it does not have a target vertex. Boost calculates ALL from a single vertex.

The SQL had only one source and one target.
Following that line of thought: this is the call to boost.
The rest of the lines were just to get the path to the target.
And TADA!!! maaaaaaaagic: we have dijkstra running on pgRouting.

Next mayor sql has the what we call: one to one , one to many, many to one and many to many options for source an target.

Why?

First of all we had an abstraction of the C file tasks (based on the similarities between the functions that existed at that time), then this new C file, is shorter & cleaner, and similar to the one on driving distance and ksp which was our test bed.

Reading the boost documentation (not only the dijkstra function documentation), we found a visitor concept.

• We created a visitor that helped stopped the algorithm when all targets were found.
• The boost algorithm, still works from a single source, so the breakup of the problem to have multiple sources is here

Side effect (from the abstraction of the C file)

• From then on, GSoC contributors, did not spend 4 to 5 weeks doing the C file adjustments. they started using the abstraction.
• The majority had to create new return types.
• And could focus more on the functions they could create.

Conclusion:
There are more options than what you have posted. Like:
Make it work for one graph that holds all the prerequisites, then make it work for a a graph that has components, where for each component the rest of the prerequisites need to hold to process it. (You will need to read about filters on boost graph)

[robe]

@Mohit242-bit

Also in the existing pgRouting codebase, functions do NOT enforce their prerequisites internally. For example, pgr_dagShortestPath requires the input to be a DAG (Directed Acyclic Graph), but it does NOT check this , it just calls boost::dag_shortest_paths() directly, and if the user passes a graph with cycles, they get an error from Boost.

Regarding this, it’s always better to use non-experimental for your guidance. The experimental ones may not have been cleaned up to our new standards.

At the end of the day the pgRouting PSC decides if the code is good enough to be merged into our main code as experimental.

[Mohit242-bit]

Hi @cvvergara, @robe

First of all, I sincerely apologize for using bold text in my previous message. I thought it was a new finding for me that other algorithms use a similar pattern, so I highlighted it as an important message, I didn’t mean to put it that way.

Thank you so much for the detailed explanation and the historical context about Dijkstra and the visitor pattern. That part really helped me understand the pgRouting design philosophy much better!

I completely agree with the approach you laid out. It makes perfect sense to solve the core problem first (a single connected/biconnected component) and then break down the problem by filtering the graph into sub-graphs for disconnected components. I will start working on the implementation .

I just have one confusion in my mind regarding further implementation. The biconnected or maximal graph algorithms are basically precursors for drawing algorithms, like the Chrobak-Payne straight line drawing algorithm (boost docs). A future implementation in pgRouting might be pgr_straightLineDrawing. In the Boost docs, it states that the input must be a maximal planar graph.

If we follow the current approach and a user wants to use a big disconnected graph for this Chrobak-Payne algorithm, they would expect a single unified drawing. But if the upstream maximal planar algorithm processes separate components as different graphs, wouldn’t the drawing algorithm also process them separately and return multiple overlapping or separate drawings instead of one? I might be wrong, but I’m just brainstorming for further algorithms. If a user missed even one edge in their graph, they might expect an error so they can fix it, but instead they wouldn’t get an error and would get a fragmented drawing output this might confuse user i think. I am just curious about how this pipeline is intended to work.

Also, regarding the question you asked in the meeting about why the SQL query requires cost and reverse_cost even though our planar algorithms are purely topological ,what do we say to the user:

I was thinking about this from the user’s perspective. In pgRouting, a user typically has one edges table that they use across many different algorithms. That table looks like:

(1, 1, 2, 10.0, -1),

(2, 2, 3, 10.0, -1),

(3, 3, 1, 10.0, -1)

and they query it with SELECT id, source, target, cost, reverse_cost FROM edges.

If our makeBiconnectedPlanar and makeMaximalPlanar required a different query like SELECT id, source, target FROM edges, the user would either need to maintain a separate table without cost columns, or remember to write a different query format just for these two functions. That seems like more inconvenience for the user, not less especially since they can’t reuse that no-cost query with any other pgRouting algorithm.

I checked the codebase for other algorithms that are purely topological (they don’t use cost in their computation and don’t return cost in their output, exactly like our makeBiconnectedPlanar and makeMaximalPlanar), and they all still require cost in the input SQL. For example:

• pgr_sequentialVertexColoring — purely topological, returns (seq, node, color)

• pgr_bridges — purely topological, returns (seq, edge)

• pgr_articulationPoints — purely topological, returns (seq, node)

• pgr_connectedComponents — purely topological, returns (seq, component, node)

• pgr_biconnectedComponents — purely topological, returns (seq, component, edge)

I ran some of these :

And this is our maximal one :

All of these official functions require the standard edge query: SELECT id, source, target, cost, reverse_cost FROM edges. So our new planar algorithms are simply following the exact same pattern. I might be wrong in my understanding of question and concept as well, but this is what I concluded from reading the codebase. It would be great if you could let me know if I am in the right direction on this and am i understanding your concern properly.

Thank you again for your patience and for guiding me through this. I am learning a lot from you and I’m excited to start implementing the components filtering!