标签: bipartite
二分图中的最佳匹配(例如,将标签与点上的点相关联)
我试图从图形xy图中提取语义,其中绘制点并且一些或全部都有标签.标签被绘制成"靠近点",这样人类通常可以理解哪个标签与哪个点相关.例如,在该图中,清楚哪个标签(数字)属于哪个点(*),并且基于欧几里德距离的算法将起作用.(标签和点没有语义排序 - 例如散点图)
*1
*2
*3
*4
在拥挤的图中,创作软件/人可以将标签放置在不同的方向上以避免重叠.例如在
1**2
**4
3
人类读者通常可以确定哪个标签与哪个标签相关联.
我接受的一个解决方案是创建欧几里德距离矩阵并对行进行混洗以获得函数的最小值(例如,对角线或其他启发式上的距离的总和平方).在第二个例子中(从NW角顺时针标记为a,b,c,d的点),我们有一个距离矩阵(到1 dp)
a b c d
1ab2 1 1.0 2.0 2.2 1.4
dc4 2 2.0 1.0 1.4 2.2
3 3 2.0 2.2 1.4 1.0
4 2.2 1.4 1.0 2.0
我们需要贴上标签a1 b2 c4 d3.交换行3和4给出了对角线的最小总和.这是一个更复杂的例子,简单地选择最近的可能会失败
*1*2*5
**4
3 *6
如果这个问题得到解决,那么我需要去看标签数量可能小于或大于点数的情况.
如果算法是标准的,那么我会欣赏指向开源Java的指针(例如JAMA或Apache数学)
注意:这个SO答案将附近的点与路径相关联并不能作为答案,因为给出了通过点的路径.
推荐指数
解决办法
查看次数
是否可以在graphviz中将子图进一步分开
我正在graphviz中绘制一个二部图，我希望它有两列由直线连接的节点（以匹配其他地方使用的样式）。我基本上可以得到我想要的东西（见图片），但柱子靠得太近，这使得边缘不必要地难以追踪。
我试图在前两个节点之间添加一个非常低的权重连接，希望它将两个子图分开，但这不起作用（并且经常弄乱布局的其余部分）。有没有办法将右侧的节点列进一步向右移动。
这是一个示例，显示了我所看到的问题
这是我用来生成这个图的代码
graph G {
splines=false;
node[shape=circle, style=filled]
subgraph cluster_1 {
subgraph cluster_1r {
a12 [label="a",fillcolor=lightgrey]
b12 [label="b",fillcolor=lightgrey]
c12 [label="c",fillcolor=lightgrey]
d12 [label="d",fillcolor=lightgrey]
e12 [label="e",fillcolor=lightgrey]
a12--b12--c12--d12--e12 [style=invis]
}
subgraph cluster_1l {
a11 [label="a",fillcolor=white]
b11 [label="b",fillcolor=white]
c11 [label="c",fillcolor=white]
d11 [label="d",fillcolor=white]
e11 [label="e",fillcolor=white]
a11--b11--c11--d11--e11 [style=invis]
}
c11--a12 [constraint=false]
c11--b12 [constraint=false]
d11--b12 [constraint=false]
e11--a12 [constraint=false]
e11--b12 [constraint=false]
}
}
推荐指数
解决办法
查看次数
如何获得不同的最大匹配
我有一个大的二分图，我可以使用Hopcroft-Karp快速找到最大匹配。但我真正想要的是同一个图的数百个不同的最大匹配。我怎样才能得到那些？
这是一个显示最大匹配的小型二分图示例。
类似的图表可以用以下方法制作：
import igraph as ig
from scipy.sparse import random, find
from scipy import stats
from numpy.random import default_rng
import numpy as np
from igraph import Graph, plot
np.random.seed(7)
rng = default_rng()
rvs = stats.poisson(2).rvs
S = random(20, 20, density=0.35, random_state=rng, data_rvs=rvs)
triples = [*zip(*find(S))]
edges = [(triple[0], triple[1]+20) for triple in triples]
print(edges)
types = [0]*20+[1]*20
g = Graph.Bipartite(types, edges)
matching = g.maximum_bipartite_matching()
layout = g.layout_bipartite()
visual_style={}
visual_style["vertex_size"] = 10
visual_style["bbox"] = (600,300)
plot(g, bbox=(600, 200), layout=g.layout_bipartite(), …推荐指数
解决办法
查看次数
BFS检查图表是否是c ++中的二分图
我正在实现一种算法来确定无向图是否为二分图.基于这个伪代码制作了我的实现,它适用于连接的图形,但是当它被断开时,只是程序指示错误的答案.我认为如果它没有连接,那么每个不相交的子图需要一个循环.但我坚持这一点.我如何能够为我打印正确答案的代码？
#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
#define MAX 1000
int numberVertex, numberEdges;
int particion[MAX], visited[MAX];
vector< int > adjacencyMatrix[MAX];
bool bfs()
{
int i, origin, destination, begin;
queue< int > queueVertex;
begin = 0;
queueVertex.push(begin);
particion[begin] = 1; // 1 left,
visited[begin] = 1; // set adjacencyMatrixray
while(!queueVertex.empty())
{
origin = queueVertex.front(); queueVertex.pop();
for(i=0; i < adjacencyMatrix[origin].size(); i++)
{
destination = adjacencyMatrix[origin][i];
if(particion[origin] == particion[destination])
{
return false;
}
if(visited[destination] == 0) …推荐指数
解决办法
查看次数
如何将二分匹配转换为独立集
我读了《算法设计》一书，它对如何将二元匹配转换为独立集问题做了很简短的描述，但我不明白。
有人知道任何详细的材料可以描述这个过程吗？谢谢！
推荐指数
解决办法
查看次数
NetworkX - 计算断开图中的最大匹配
我有两个二分图 G 和 B，它们都有完全相同的节点，但边数不同。当我尝试nx.bipartite.maximum_matching在 G （边数较少）上运行时，我收到一个错误Disconnected graph: Ambiguous solution for bipartite sets.，该错误与我之前收到的错误类似。
这里是G.nodes(data='True')：
[(0, {'bipartite': 0}), (1, {'bipartite': 0}), (2, {'bipartite': 0}),
(3, {'bipartite': 0}), (4, {'bipartite': 0}), (5, {'bipartite': 0}),
(6, {'bipartite': 0}), (7, {'bipartite': 0}), (8, {'bipartite': 0}),
(9, {'bipartite': 0}), (10, {'bipartite': 1}), (11, {'bipartite': 1}),
(12, {'bipartite': 1}), (13, {'bipartite': 1}), (14, {'bipartite': 1}),
(15, {'bipartite': 1}), (16, {'bipartite': 1}), (17, {'bipartite': 1}),
(18, {'bipartite': 1}), (19, {'bipartite': 1})]
这与 …
推荐指数
解决办法
查看次数
在给定最大匹配的情况下找到二分图的最小顶点覆盖
我似乎找到了一个算法,但我很难理解它,我想知道你们中是否有人知道算法的通用轮廓.
这是我在第2页找到的算法的链接
推荐指数
解决办法
查看次数
欧几里得空间中完整二分匹配的最小成本流优化
要点是......我们有两组点A和B。集合A和B具有相同数量的点n。
正式问题：
在A和B中的点之间构造最小成本完全二分匹配。匹配(a, b)的成本是距离(a, b)。是否存在比O(n^3)更快的算法？
笔记：
- A中的每个点a和B中的点b都在匹配(a, b)中。
- A或B中的每个点a都恰好在一次匹配中。
- sum（ 每个（a，b）匹配的距离（a，b））被最小化。
例子：
- a 点 (0,0)
- b 点 (2,0)
- c 点 (0,1)
- 点 d (-2,2)
- 设 Z {a, d}
- 设 Y {b, c}
解决方案：
匹配1：（a，b）（d，c）
sum (距离(a, b),距离(d, c)) …
algorithm matching bipartite euclidean-distance network-flow
推荐指数
解决办法
查看次数
两组大小截然不同的顶点的最大加权二分匹配
抽象问题
我想在完整的加权二分图中找到最佳的最大匹配，其中两组顶点的大小差异很大，即一组顶点非常大，另一组非常小。
匈牙利算法不是解决此问题的好方法，因为它将虚拟顶点添加到较小的集合中，使得两个集合具有相同的大小，因此我失去了其中一个顶点集合非常小的所有潜在效率增益。
更具体地说
我已将对象（边界框）分为两组，并且有一个相似性度量（杰卡德重叠）来衡量任意两个对象的相似程度。我想产生两个集合之间的匹配，使得所有单独匹配的相似度之和最大。
问题在于，其中一组仅包含很少的对象，例如 10 个，而第二组非常大，例如 10,000 个对象。第一组中的 10 个对象中的每一个都需要与第二组中的 10,000 个对象中的一个进行匹配。
两组大小的不对称让我想知道如何有效地做到这一点。我无法使用匈牙利算法生成 10,000 x 10,000 矩阵。
推荐指数
解决办法
查看次数
为什么我们不能通过简单的迭代来确定图是否是二分图？
这就是我要解决的问题
我们想要将一组 n 人（标记为 1 到 n）分成任意大小的两组。每个人都可能不喜欢某些人，他们不应该加入同一群体。给定整数 n 和数组 dislikes，其中 dislikes[i] = [ai, bi] 表示标记为 ai 的人不喜欢标记为 bi 的人，如果可以通过这种方式将每个人分成两组，则返回 true。
这可以通过 Python 中的 BFS 相当简单地解决：
def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
graph = defaultdict(set)
for a, b in dislikes:
graph[a-1].add(b-1)
graph[b-1].add(a-1)
q = deque({0})
colors = [None]*n
for i in range(n):
if colors[i] is None:
q = deque({i})
colors[i] = 0
while q:
cur = q.popleft()
for d in graph[cur]:
if colors[d] is None:
q.append(d)
colors[d] = 1 …computer-science graph-theory breadth-first-search bipartite
推荐指数
解决办法
查看次数