CODEWITHSUNDEEP
algorithmgraphtopological-sort
Teknophilia
Teknophilia

Reputation: 778

"Best-Effort" Topological Sort

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

Upvotes: 3

Views: 206

Answers (2)

ciamej
ciamej

Reputation: 7068

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.

Upvotes: 2

Moritz Groß
Moritz Groß

Reputation: 1490

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.

Upvotes: 0

Related Questions