algorithm - 二分图中边的均匀分布

Question

我得到了一个二分图和有向图，最初没有边。一组节点称为主题，另一组称为对象。边只能从主体到客体构建。 分别给出了主体数 (numSubj) 和客体数 (numObj)。 此外，还给出了可用边的数量 (numEdges)。

目标是将边缘从主体均匀分布到物体。这意味着所有主体都应该有相似数量的出边，类似地所有对象都应该有相似数量的入边。每个主题和对象都必须至少有一个连接边。

请提出解决方案(例如伪代码)

Answer 1

首先让我们索引每组节点中的所有项目，从 1 到 numSubj从 1 到 numObj .我们还假设 numSubj < numObj (如果这不是真的，那么简单地翻转集合，解决并再次翻转它们)。

现在计算边的总数，即lcm在这些数字之后，您可以通过将结果除以 numObj 来得出传出边的数量。 ( A ) 并通过除以 numSubj 找到传入(B)。

在为每个主题计算之后，为计算出的主题数量创建一条边，其中传入边的数量，A , 小于计算出的第二个数字 - B .

这个过程可以这样进行:
i连接到 [i * B, i * B + 1, ... , i * (B + 1) - 1 ] mod numObj

With 2 and 5:

LCM = 10  
Ingoing = 10 / 5 = 2  
Outgoing = 10 / 2 = 5   
1 -> 1, 2, 3, 4, 5   
2 -> 1, 2, 3, 4, 5

With 4 and 8:

LCM = 8  
Ingoing = 8 / 8 = 1   
Outgoing = 8 / 4 = 2   
1 -> 1, 2   
2 -> 3, 4 
3 -> 5, 6  
4 -> 7, 8  

With 4 and 6:

LCM = 12 
Ingoing = 12 / 6 = 2   
Outgoing = 12 / 4 = 3   
1 -> 1, 2, 3   
2 -> 4, 5, 6 
3 -> 1, 2, 3  
4 -> 4, 5, 6