admin管理员组

文章数量:1294460

I'm searching for an algorithm to solve a graphing problem. I would like to code it in C++ and it should have an acceptable runtime

The problem has the following setup:

  • We have a directed acyclic graph of around 1000 nodes
  • Every node has a certain type. We could also call them colours in a general sense
  • I would like to partition the graph into a minimal amount of subgraph. Or at least do a best effort/greedy approach to minimise the subgraphs
  • Every subgraph can only contain nodes of the same type/colour
  • The new graph consisting of these subgraph should also be acyclic. Meaning that I don't want any circular dependencies between these subgraph
  • Small detail is that the Graph only has 1 root node

I was thinking about the following approach:

  • Start from the topologically sorted graph
  • Iterate over all the nodes starting from the root node
    • Try to add the node to the last subgraph of that colour
    • Check if that node has any connection to nodes outside the current subgraph. If so, check that we don't introduce any cycle. This check become tricky since we have to traverse the leftover nodes together with the already existing subgraphs. But I assume an adapted cycle detection algorithm will do the trick
    • If we can't add the node to the current subgraph, we create a new subgraph for that type/colour of node

本文标签：

版权声明：本文标题：partitioning - How to minimise graph partitions while every subgraph contains only 1 type of node and no cycles exist between su 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.betaflare.com/web/1741603426a2387834.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。