问题标签 [bipartite]

我创建了一个函数来将二分边缘列表投影到单模式边缘列表中，并且一切正常。但是，我现有的计划是将所有这些边添加到列表中，然后将该列表加载到 pandas 数据框中，并根据边权重过滤列表以创建新的数据框，然后将这些数据框写入 csv。

这一直很好，直到我的数据变得太大而无法保存在 RAM 中。

我在想，与其将单模式边缘列表添加到列表中，不如将其内容写入foldedCSV，甚至跳过将数据添加到列表中。我还想过滤我写到 CSV 的内容，只写权重大于或等于 2 的行。

数据：

如何更改我的代码以直接写入 CSV 并跳过将边添加到折叠列表中，但只添加权重大于或等于 3 的边？

下面是原样的代码，它将所有边添加到列表中，然后将列表写入 CSV：

我正在阅读增广路径或库恩算法，以在未加权的二分图中找到最大匹配大小。

该算法试图找到一条交替路径（由交替的不匹配和匹配的边组成）在不匹配的顶点处开始和结束。如果找到交替路径，则增加路径并且匹配计数增加 1。

我可以理解该算法，但是我在理解它的一般实现方式方面存在问题。这是一个参考实现 - https://sites.google.com/site/indy256/algo/kuhn_matching2。

在每个阶段，我们都应该尝试从左侧不匹配的顶点开始找到一条交替路径。然而，在给定的实现中，在每次迭代中，我们不是尝试所有不匹配的顶点作为可能的起始位置，而是只从一个不匹配的顶点开始搜索，如下面的代码所示 -

这样，在其迭代期间不匹配的左侧顶点将永远不会再次尝试。我不明白为什么这是最优的？

我最近遇到了这个问题，我想知道它是 NP-Complete 还是在多项式时间内可解：

给定一个加权二分图 G=(V,E)，其中 V 可以分为两组 A 和 B，E 是连接 A 和 B 的一组边。边 (v,u) 的权重表示为 w( v,u)。

按顺序执行以下操作：

1. 选择一个节点 v∈A，
2. 为每个 (v,u)∈E 删除所有节点 u∈B 并且，
3. 将权重 w(v,u) 添加到每个删除边的总分中。

目标是找到使总分最大化的节点序列 v1,…,vn∈A。

我已经搜索了 NP-Complete 问题库，以找到可以减少这个问题的方法，但我还没有发现任何有用的东西。任何建议都会非常有帮助！

我想知道是否有一种简单的方法可以在 R 中以有向二分图的形式绘制 2 个列表之间元素位置的变化。例如，列表 1 和 2 是字符串向量，不一定包含相同要素：

我想生成类似于：

我对使用 igraph 包有一点点 bash，但不能轻易地构建我想要的东西，我想这不应该太难。

干杯。

二部图中的最大基数是否与该图中的最大流量相同，其中两个虚拟节点一个作为源，另一个作为接收器。

源连接到一组二分图，另一组连接到接收器。

我试图找出一个好的（和快速的）解决以下问题的方法：

我有两个正在使用的模型，我们称它们为球员和团队。一个玩家可以在多个团队中，一个团队可以有多个玩家）。我正在努力在允许用户选择多个团队（复选框）的表单上创建 UI 元素。当用户选择（或取消选择）球队时，我想显示按球员分组的球队。

因此，例如：

1. 如果所选球队没有相交的球员，则每个球队都有自己的部分。

2. 如果用户选择了两支球队并且他们有相同的球员，那么会有一个部分包含两支球队和所有球员的名字。

3. 如果 TEAM_A 有球员 [1, 2, 4, 5]，而 TEAM_B 有球员 [1, 3, 5, 6]。会有以下部分：SECTION_X = [TEAM_A, TEAM_B, 1, 5], SECTION_Y = [TEAM_A, 2, 3], SECTION_Z = [TEAM_B, 3, 5]

我希望这很清楚。本质上，我想找到球员共同的球队并以此分组。我在想也许有一种方法可以通过导航二分图来做到这一点？不完全确定如何，我可能想多了。我希望通过在服务器上创建某种类型的数据结构并在客户端上使用它来做到这一点。我很想听听您的建议，并感谢您提供的任何帮助！

为了在 R 中的 igraph 包中学习社交网络理论的“基本要素”，我创建了一个基本的玩具示例，该示例是阿尔及利亚内战一年期间恐怖袭击的二分图。顶点由恐怖肇事者和目标组成，而边缘代表哪个团体攻击了哪个目标。

我可以绘制这种关系的一般单部分图（以及网络中心性的基本分析），但是在创建网络的二部分投影时遇到问题。

根据@GaborCsardi 的建议，我只将 igraph 包加载到全局环境中，以确保snaornetworks包不会与 igraph 的命令冲突。

尽管如此，问题仍然存在：

此时，RStudio 会产生以下错误：

我正在尝试解决标准的二分问题，即找到边的子集，以使输出图是二分图。我的额外限制是：

1. 每边的顶点数必须相等。
2. 每个顶点恰好有 1 条边。

事实上，知道这样的子集是否存在就足够了——我并不真的需要构造本身。最佳情况下，该算法应该很快，因为我需要为 O(400) 节点重复运行它。

我得到下图。我怎样才能使它看起来像一个适当的二部图？

我是 R 初学者，我找不到任何对我有帮助的东西。我想生成大小不同的随机矩阵。我想使用 for 循环和genweb函数，但它给了我一个向量，而不是许多矩阵。