I'm struggling to define this problem exactly, which is part of the reason I cannot solve it. Basically, I want to assign numbers to nodes that provides a kind of topological sorting, but if there is a cycle in the graph, which I want to allow, it should assign values to the nodes that essentially count up the distance from nearest non-cycle nodes.

eg, If there were another non-cyclic dependency, the numbers assigned to the nodes may look more like this.

Currently, the numbers assigned are just based on total dependencies, which creates less-than-ideal layouts.

I have a feeling that I might need to use some algorithm involving Strongly Connected Components, but I'm not sure how to apply it to get the desired result. Any help clarifying this issue would be greatly appreciated!

CodePudding user response：

Well, just a general idea: I would try to find the longest possible shortest path (I mean, max( shortest_path(node1, node2) for node1 in nodes, node2 in nodes). So "longest shortest" is not an oxymoron here), in the undirected graph (so ignoring arrows).

And I would chose index along that longest path.

And then, for all other nodes, you have to choose (arbitrarily) between index of closest node with index, index of closest node with index - distance or index of closest node with index distance.

CodePudding user response：

not too bad!