1

Does anyone know how to get all existing cycles in a geotools graph? The CycleDetector object that exists merely identifies if there are any cirlces in the graph, and nothing more.

Ilias Koritsas
  • 33
  • 1
  • 5

1 Answers1

0

I think your question is a little vague. Are you modeling your graphs as directed or undirected graphs? Also, if you want a handle on 'all' cycles, you likely need a notion of 'minimal' cycles. (Otherwise, one could say that A->B->C->A, A->B->C->A->B->C->A, and A->B->C->A->B->C->A->B->C->A are all cycles in the graph.)

As a helpful piece of code, I'd recommend checking out the GraphPartitioner. If your graph consists of disjoint components, this class will break the larger graph into disjoint pieces.

For each of those pieces, you could run the CycleDetector (or the Directed version DirectedCycleDetector) to see if there is any work to be done on the connected sub-graph.

Looks like this question is also relevant: Finding all cycles in undirected graphs.

Community
  • 1
  • 1
GeoJim
  • 1,320
  • 7
  • 12
  • Thanks for your answer! The truth is I was a little vague about my problem indeed. I know about the cycle detector but I was thinking something like the triangle in delauny triangulation. Like geting objects for minimum closed paths from a graph. Nevertheless, your answer helped my understand what GraphPartitioner does. I hadn't noticed that in order to work the graph should have disjoint components and I was struggling in vain all this time! So thanks! – Ilias Koritsas Oct 16 '16 at 20:15