"Best-Effort" Topological Sort

user_592678 0
Viewed 100

I'm looking to organize some items based on inheritance, with the goal of identifying which items are the most densely-connected parents, and also just seeing the connections formed.

Normally this would be done with a topological sort, but my graph has cycles. Is there something like a "best-effort" topological sort, which can attempt to determine the "most important" parents based on things like number of connections or something analogous?

As an example, given the graph below, I'd like for 1 and 2 to be the top-level parents. 1 has no parents; and while 2 is in a cycle, it is the parent of more children than it inherits from.

enter image description here

topological-sort graph algorithm
2 Answers

One way to achieve something like that would be to compute for each node how many other nodes are accessible from it, and then sort the nodes based on that number.

Alternatively, you can reverse that logic. For each node compute how many nodes have access to it, then sort nodes in ascending order.

user_8214970

Google's pagerank-Algorithm evaluates websites, whose hyperlinks are represented as directed edges. Websites with many and important incoming links are rated highly.
In your case it seems to be the opposite. You want few/no incoming edge.
You could therefore try the pagerank-algorithm, but reverse its results in the way, that the nodes with the highst page-rank get the lowest inheritance-rating and the other way around.

user_97276740
Related