Missing, and recursive, graph dependency.

[grafikrobot]

This commit (805ff65) added a dependency to Boost.Graph to the CML. But it did not make the equivalent change to build.jam. If that had been done, it would have become clear (because of build errors) that the new dependency creates a dependency cycle.

[barendgehrels]

I'm curious, what is the new dependency cycle?

[grafikrobot]

https://pdimov.github.io/boostdep-report/develop/graph.html#geometry

[grafikrobot]

https://pdimov.github.io/boostdep-report/develop/geometry.html#graph

[jeremy-murphy]

Hi @barendgehrels. I recently added a dependency on Boost.Geometry to Boost.Graph to replace the custom geometry code we had in a planar graph algorithm (which to your credit fixed the problems in it straight away), and I remember thinking "Maybe I should let them know that now we depend on them..." but here are. :)

[jeremy-murphy]

At the moment it's only a single algorithm where we use some predicates, so although we have a recursive dependency at the library level it's (obviously) not recursive at the headers. So, although it's not ideal, do we actually need to do anything to fix it?
Off the cuff, it would require splitting the parts of each library that depend on the other out into new libraries that depend on both. I mean, like new library Boost.Graph.Planar would depend on Boost.Graph and Boost.Geometry, and ... oh, I just realized that you've actually got a whole new graph directory of code. I don't have time to look through it all right now, but is it specific to geometry or can we generalize it and put it in Boost.Graph? Anyway, I'm happy to work together to find a great solution.

[barendgehrels]

hi @jeremy-murphy , sorry for my delayed reaction.

By big chance - so you added a dependency on Boost.Geometry in Dec 2024 (indeed I didn't notice) and in Jan 2025 I started revising our graph traversal using a real graph ;-) My efforts were merged in or around April 2024.

do we actually need to do anything to fix it?
Ideally yes, probably. We mainly use the algorithm biconnected_components.
But of course also the graph type boost::adjacency_list and the functions to fill it, and traverse through it.

Within our team we discussed if we should another dependency, for using one algorithm only. But because it's a real graph algorithm, we thought we should, and not implement it ourselves again.

And it turned out quite well, greatly simplifying the algorithm and fixing many existing problems (though later a few others came back, still to be investigated - probably not graph related).

Hopefully that is some info to think about how to solve it.

Anyway, I'm happy to work together to find a great solution.

Very nice! Yes, I'm also happy - but that will not be this year, I'm afraid, due to other occupancies at this moment...

[jeremy-murphy]

Oh, looks like I was foolishly optimistic, because of course CMake resolves dependencies at the library level and that breaks with a cycle in the dependency graph: https://github.com/boostorg/graph/actions/runs/18480093442/job/53707423023?pr=441
The quickest, slightly hacky solution is that I'll put our planar graph algorithms into a separate library in the CMake build, moving the geometry dependency out of the main Graph library.

[jeremy-murphy]

Ah, and now I know that it is actually a problem for b2 as well: https://github.com/boostorg/graph/actions/runs/18858148168/job/53810760440?pr=441

[jeremy-murphy]

I wonder if it might be possible to actually move the function that Graph uses Geometry for, into Geometry? Or would it be too unrelated to everything else?

[barendgehrels]

I wonder if it might be possible to actually move the function that Graph uses Geometry for, into Geometry? Or would it be too unrelated to everything else?

I looked into it, interesting idea. But it won't solve the mutual dependency? Because you still will call that new function from Boost.Geometry...
Actually, it might create another one (as long as the Graph is in that function), unless we revise it.

[jeremy-murphy]

Oh, it would actually solve it, because that function is a 'leaf' algorithm us, it doesn't get used by anything else. It only exists for users to, optionally, validate answers given by the Chrobak-Payne Straight Line Drawing algorithm. So if we moved it to Geometry, then we would update our documentation to say, "See Boost.Geometry for an algorithm that can validate the geometry of the straight line drawing." We would still depend on Boost.Geometry existing, but no longer a code dependency. :)