5
$\begingroup$

I am looking for an algorithm that clusters a directed graph into a set of clusters that form a directed acyclic graph.

For example, given: nodes: {A, B, C, D} with edges: {(A,B), (B,A), (A,C), (C,D), (D,C)}

A valid output would be: {{A,B},{C,D}) An invalid output would be: {{A,C},{B,D}} (since the node edges imply a cycle between the clusters)

Thanks for any pointers or suggestions!

$\endgroup$
3
  • 1
    $\begingroup$ Find strongly connected components (using DFS) and contract each component into a single vertex. en.wikipedia.org/wiki/Strongly_connected_component. $\endgroup$
    – Valentas
    Aug 19, 2015 at 17:32
  • $\begingroup$ @Valentas (1) How do you then establish the edges between the new vertices? (2) Is what you recommend the same as Kasra's answer below? $\endgroup$
    – Fr.
    Jan 11, 2017 at 6:14
  • $\begingroup$ My comment answers the question for a rigid rule which I interpreted from the example (that is, I would only output a set of vertex subsets). If you have a different interpretation, maybe it is best to ask a new question. $\endgroup$
    – Valentas
    Jan 11, 2017 at 7:36

1 Answer 1

1
$\begingroup$

What you are exactly looking for is a modification to the DEDICOM Algorithm (page 4). the DEDICOM itself gives you measure for relation between different components of a directed graph. You just need to be a bit creative to use it for converting a graph into DAG. Read the paper and if further help needed just drop me a comment.

$\endgroup$
3
  • $\begingroup$ Would you happen to know if that solution has already been coded in either R or Python, for instance? $\endgroup$
    – Fr.
    Jan 11, 2017 at 6:15
  • $\begingroup$ I did it myself in Python in half an hour long time ago but unfortunately almost impossible to find it. I just followed the simple algorithm in page 4 of the recommended paper and that is super easy to implement. $\endgroup$ Jan 12, 2017 at 8:41
  • $\begingroup$ @Kasra Manshaei thanks for this answer. Unfortunately the link to the paper is down. Any chance you can post the citation for the paper? $\endgroup$
    – Berk U.
    Jul 1, 2018 at 0:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.