Select 一组边创建最大的图形，因为一些边与其他边互斥
Select a set of edges which create the largest graph given that some edges are mutually exclusive of others
我正在尝试确定如何最好地解决这个问题。
给定一组节点和多个相互冲突的连接方式，我需要select一组不冲突的关系，以使最大数量的节点保持连接状态。
示例。
这是一个包含忽略冲突的所有可能关系（边）的图表。例如，这张图片没有描述边缘之间的依赖关系。
连接到特定节点的所有边都相互依赖。为简单起见，每条边暗示它连接的每个节点的属性，比如 A...Z。如果连接节点 3 和 16 的边指定属性 3-B 和 16-F，则连接 16 到其他节点的所有边都必须具有属性 16-F。类似地，所有连接 3 到其他节点的边都必须具有属性 3-B。
这是将属性 F 指定给节点 16 时的同一张图。该属性删除了大部分边，留下一条连接 16-4 的边和一条连接 16-3 的边。这在 16-42 之间没有留下任何边缘。
（16 在两张图片的左侧附近。）
此图并未说明连接 3-42 的边将为节点 42 指定属性，例如 42-X。这将进一步将连接限制为 42 并进一步分解图形。我没有显示这个，因为这是我的问题。
我正在寻求建议。
- 这是一个已知问题吗？你能给我指出任何参考资料吗？
- 如何
你会解决这个问题吗？我最好的想法是迭代，
从每条边开始，遍历所有可能的属性。评价每一个
划分并找出哪个保留了最大的网络。这个
不过听起来很有挑战性，我需要一些帮助。
- 如果这是解决方案，有没有办法在 R 中使用 igraph 来指定 "edge attribute constraint" 并提取生成的碎片图。
我这里有dput图表：
df = structure(list(nodeA = c(3L, 4L, 42L, 43L, 44L, 29L, 30L, 29L, 30L, 3L, 4L, 6L, 43L, 44L, 43L, 44L, 29L, 30L, 29L, 30L, 52L, 29L, 30L, 35L, 25L, 35L, 25L, 43L, 44L, 29L, 30L, 3L, 4L, 43L, 44L, 29L, 30L, 25L, 29L, 30L, 42L, 3L, 4L, 17L, 43L, 44L, 29L, 30L, 29L, 30L, 17L, 17L, 29L, 30L, 6L, 43L, 44L, 29L, 30L, 52L, 35L, 35L, 25L, 25L, 24L, 24L, 43L, 44L, 29L, 30L, 35L, 35L, 25L, 25L, 24L, 24L, 43L, 44L, 29L, 30L, 35L, 35L, 25L, 25L, 24L, 24L, 52L, 42L, 3L, 42L, 42L, 3L, 4L, 42L, 25L, 42L, 25L, 3L, 4L, 42L, 3L, 4L, 17L, 35L, 3L, 4L, 35L, 43L, 44L, 29L, 30L, 35L, 35L, 35L, 52L, 25L, 25L, 24L, 24L, 35L, 29L, 30L, 3L, 4L, 43L, 44L, 29L, 30L, 25L, 29L, 30L, 52L, 43L, 44L, 29L, 30L, 25L, 29L, 30L, 3L, 4L, 43L, 44L, 29L, 30L, 52L, 43L, 44L, 43L, 44L, 29L, 30L, 3L, 4L, 43L, 44L, 29L, 30L, 52L, 52L, 43L, 44L, 29L, 30L, 35L, 52L, 52L, 3L, 4L, 43L, 44L, 29L, 30L, 52L, 43L, 44L, 29L, 30L, 43L, 44L, 29L, 30L, 17L, 17L, 42L, 42L, 43L, 44L, 29L, 30L, 43L, 44L, 29L, 30L, 43L, 44L, 29L, 30L, 3L, 4L, 25L, 25L, 16L, 16L, 3L, 4L, 43L, 44L, 24L, 3L, 4L, 52L, 52L, 17L, 35L, 35L, 35L, 17L, 3L, 4L, 6L, 35L, 42L, 42L, 42L, 42L, 3L, 4L, 17L, 25L, 17L, 17L, 29L, 30L, 25L, 3L, 4L, 29L, 30L, 3L, 4L, 17L, 17L, 17L, 35L, 3L, 4L, 17L, 17L, 17L, 29L, 30L, 43L, 44L, 43L, 44L, 29L, 30L, 17L, 6L, 43L, 44L, 29L, 30L, 43L, 44L, 29L, 30L, 43L, 44L, 29L, 30L, 3L, 43L, 44L, 29L, 30L, 3L, 43L, 44L, 29L, 30L, 17L, 17L, 42L, 42L, 25L, 42L, 25L, 43L, 44L, 29L, 30L, 42L, 17L, 17L, 42L, 42L, 43L, 44L, 29L, 30L, 25L, 29L, 30L, 43L, 44L, 29L, 30L, 43L, 44L, 29L, 30L, 25L, 29L, 30L, 43L, 44L, 29L, 30L, 43L, 44L, 29L, 30L, 43L, 44L, 29L, 30L, 25L, 25L, 25L, 25L), nodeB = c(16L, 16L, 17L, 24L, 24L, 25L, 25L, 35L, 35L, 16L, 16L, 17L, 24L, 24L, 24L, 24L, 25L, 25L, 25L, 25L, 35L, 35L, 35L, 43L, 43L, 44L, 44L, 24L, 24L, 25L, 25L, 16L, 16L, 24L, 24L, 25L, 25L, 35L, 35L, 35L, 16L, 16L, 16L, 24L, 24L, 24L, 25L, 25L, 35L, 35L, 43L, 44L, 52L, 52L, 17L, 24L, 24L, 25L, 25L, 35L, 43L, 44L, 29L, 30L, 43L, 44L, 24L, 24L, 25L, 25L, 43L, 44L, 29L, 30L, 43L, 44L, 24L, 24L, 25L, 25L, 43L, 44L, 29L, 30L, 43L, 44L, 17L, 24L, 42L, 43L, 44L, 16L, 16L, 17L, 35L, 17L, 35L, 16L, 16L, 52L, 16L, 16L, 6L, 25L, 16L, 16L, 52L, 24L, 24L, 25L, 25L, 43L, 44L, 25L, 25L, 29L, 30L, 43L, 44L, 17L, 42L, 42L, 16L, 16L, 24L, 24L, 25L, 25L, 35L, 35L, 35L, 35L, 24L, 24L, 25L, 25L, 35L, 35L, 35L, 16L, 16L, 24L, 24L, 25L, 25L, 35L, 17L, 17L, 24L, 24L, 25L, 25L, 16L, 16L, 24L, 24L, 25L, 25L, 25L, 35L, 24L, 24L, 25L, 25L, 25L, 29L, 30L, 16L, 16L, 24L, 24L, 25L, 25L, 35L, 24L, 24L, 25L, 25L, 24L, 24L, 25L, 25L, 43L, 44L, 3L, 4L, 24L, 24L, 25L, 25L, 24L, 24L, 25L, 25L, 24L, 24L, 25L, 25L, 16L, 16L, 35L, 35L, 3L, 4L, 16L, 16L, 17L, 17L, 17L, 16L, 16L, 29L, 30L, 6L, 25L, 29L, 30L, 42L, 16L, 16L, 25L, 52L, 16L, 16L, 16L, 16L, 16L, 16L, 24L, 35L, 43L, 44L, 52L, 52L, 35L, 16L, 16L, 52L, 52L, 16L, 16L, 24L, 43L, 44L, 25L, 16L, 16L, 24L, 43L, 44L, 52L, 52L, 17L, 17L, 24L, 24L, 25L, 25L, 52L, 42L, 24L, 24L, 25L, 25L, 24L, 24L, 25L, 25L, 24L, 24L, 25L, 25L, 42L, 24L, 24L, 25L, 25L, 42L, 24L, 24L, 25L, 25L, 43L, 44L, 4L, 17L, 35L, 17L, 35L, 24L, 24L, 25L, 25L, 16L, 43L, 44L, 4L, 4L, 24L, 24L, 25L, 25L, 35L, 35L, 35L, 24L, 24L, 25L, 25L, 24L, 24L, 25L, 25L, 35L, 35L, 35L, 24L, 24L, 25L, 25L, 24L, 24L, 25L, 25L, 24L, 24L, 25L, 25L, 35L, 35L, 35L, 35L), attributeA = c(25L, 25L, 130L, 110L, 110L, 110L, 110L, 113L, 113L, 43L, 43L, 71L, 5L, 5L, 127L, 127L, 5L, 5L, 127L, 127L, 72L, 130L, 130L, 137L, 140L, 137L, 140L, 6L, 6L, 6L, 6L, 56L, 56L, 137L, 137L, 137L, 137L, 130L, 140L, 140L, 29L, 68L, 68L, 56L, 143L, 143L, 143L, 143L, 146L, 146L, 43L, 43L, 45L, 45L, 46L, 80L, 80L, 80L, 80L, 47L, 11L, 11L, 80L, 80L, 80L, 80L, 84L, 84L, 84L, 84L, 14L, 14L, 84L, 84L, 84L, 84L, 90L, 90L, 90L, 90L, 18L, 18L, 90L, 90L, 90L, 90L, 110L, 37L, 122L, 114L, 114L, 108L, 108L, 58L, 27L, 136L, 109L, 26L, 26L, 115L, 111L, 111L, 78L, 109L, 112L, 112L, 78L, 114L, 114L, 114L, 114L, 37L, 37L, 47L, 73L, 114L, 114L, 114L, 114L, 128L, 111L, 111L, 125L, 125L, 54L, 54L, 54L, 54L, 45L, 58L, 58L, 143L, 55L, 55L, 55L, 55L, 126L, 136L, 136L, 44L, 44L, 56L, 56L, 56L, 56L, 145L, 68L, 68L, 57L, 57L, 57L, 57L, 128L, 128L, 58L, 58L, 58L, 58L, 143L, 146L, 59L, 59L, 59L, 59L, 126L, 70L, 70L, 129L, 129L, 60L, 60L, 60L, 60L, 73L, 61L, 61L, 61L, 61L, 62L, 62L, 62L, 62L, 124L, 124L, 91L, 91L, 63L, 63L, 63L, 63L, 64L, 64L, 64L, 64L, 65L, 65L, 65L, 65L, 135L, 135L, 58L, 136L, 127L, 127L, 57L, 57L, 143L, 143L, 68L, 138L, 138L, 143L, 143L, 80L, 136L, 126L, 126L, 109L, 139L, 139L, 128L, 80L, 110L, 112L, 113L, 30L, 141L, 141L, 135L, 70L, 125L, 125L, 126L, 126L, 142L, 69L, 69L, 128L, 128L, 144L, 144L, 138L, 128L, 128L, 142L, 145L, 145L, 139L, 129L, 129L, 130L, 130L, 121L, 121L, 79L, 79L, 79L, 79L, 91L, 109L, 82L, 82L, 82L, 82L, 86L, 86L, 86L, 86L, 88L, 88L, 88L, 88L, 97L, 92L, 92L, 92L, 92L, 118L, 94L, 94L, 94L, 94L, 107L, 107L, 89L, 138L, 111L, 140L, 113L, 116L, 116L, 116L, 116L, 1L, 134L, 134L, 92L, 19L, 135L, 135L, 135L, 135L, 128L, 138L, 138L, 136L, 136L, 136L, 136L, 137L, 137L, 137L, 137L, 130L, 140L, 140L, 138L, 138L, 138L, 138L, 139L, 139L, 139L, 139L, 140L, 140L, 140L, 140L, 138L, 140L, 144L, 146L), attributeB = c(1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 3L, 3L, 3L, 3L, 3L, 3L, 3L, 3L, 3L, 3L, 3L, 3L, 3L, 3L, 3L, 3L, 3L, 3L, 4L, 4L, 4L, 4L, 5L, 5L, 5L, 5L, 5L, 5L, 5L, 5L, 5L, 6L, 7L, 7L, 7L, 7L, 7L, 7L, 7L, 7L, 7L, 7L, 7L, 7L, 7L, 10L, 10L, 10L, 10L, 10L, 10L, 10L, 10L, 11L, 11L, 11L, 11L, 13L, 13L, 13L, 13L, 13L, 13L, 14L, 14L, 14L, 14L, 17L, 17L, 17L, 17L, 17L, 17L, 18L, 18L, 18L, 18L, 19L, 19L, 19L, 19L, 19L, 23L, 23L, 23L, 23L, 24L, 24L, 25L, 25L, 25L, 27L, 27L, 28L, 28L, 29L, 29L, 29L, 36L, 36L, 36L, 36L, 36L, 36L, 37L, 37L, 37L, 37L, 37L, 37L, 38L, 38L, 38L, 41L, 41L, 41L, 41L, 41L, 41L, 41L, 41L, 41L, 41L, 42L, 42L, 42L, 42L, 42L, 42L, 42L, 43L, 43L, 43L, 43L, 43L, 43L, 43L, 44L, 44L, 44L, 44L, 44L, 44L, 45L, 45L, 45L, 45L, 45L, 45L, 45L, 45L, 46L, 46L, 46L, 46L, 46L, 46L, 46L, 47L, 47L, 47L, 47L, 47L, 47L, 47L, 48L, 48L, 48L, 48L, 49L, 49L, 49L, 49L, 49L, 49L, 50L, 50L, 50L, 50L, 50L, 50L, 51L, 51L, 51L, 51L, 52L, 52L, 52L, 52L, 54L, 54L, 54L, 55L, 56L, 56L, 56L, 56L, 56L, 56L, 57L, 58L, 58L, 58L, 58L, 59L, 59L, 59L, 59L, 59L, 60L, 60L, 60L, 60L, 62L, 63L, 64L, 65L, 66L, 66L, 66L, 66L, 66L, 66L, 66L, 66L, 67L, 68L, 68L, 68L, 68L, 70L, 70L, 70L, 70L, 70L, 71L, 72L, 72L, 72L, 72L, 72L, 72L, 72L, 77L, 77L, 78L, 78L, 78L, 78L, 79L, 80L, 81L, 81L, 81L, 81L, 85L, 85L, 85L, 85L, 87L, 87L, 87L, 87L, 89L, 91L, 91L, 91L, 91L, 92L, 93L, 93L, 93L, 93L, 96L, 96L, 97L, 108L, 108L, 110L, 110L, 115L, 115L, 115L, 115L, 117L, 117L, 117L, 118L, 122L, 125L, 125L, 125L, 125L, 125L, 125L, 125L, 126L, 126L, 126L, 126L, 127L, 127L, 127L, 127L, 127L, 127L, 127L, 128L, 128L, 128L, 128L, 129L, 129L, 129L, 129L, 130L, 130L, 130L, 130L, 135L, 137L, 141L, 143L)), .Names = c("nodeA", "nodeB", "attributeA", "attributeB" ), row.names = c(3L, 4L, 5L, 7L, 8L, 9L, 10L, 12L, 13L, 18L, 19L, 20L, 24L, 25L, 26L, 27L, 28L, 29L, 31L, 32L, 35L, 36L, 37L, 38L, 39L, 40L, 41L, 52L, 53L, 54L, 55L, 59L, 60L, 62L, 63L, 64L, 65L, 71L, 72L, 73L, 78L, 82L, 83L, 86L, 87L, 88L, 89L, 90L, 96L, 97L, 98L, 99L, 108L, 109L, 112L, 114L, 115L, 116L, 117L, 120L, 121L, 122L, 129L, 131L, 134L, 135L, 141L, 142L, 143L, 144L, 146L, 147L, 153L, 154L, 156L, 157L, 163L, 164L, 165L, 166L, 168L, 169L, 175L, 176L, 178L, 179L, 183L, 186L, 187L, 188L, 189L, 196L, 197L, 198L, 201L, 204L, 206L, 208L, 209L, 213L, 216L, 217L, 221L, 222L, 225L, 226L, 230L, 241L, 242L, 243L, 244L, 248L, 249L, 255L, 256L, 259L, 260L, 264L, 265L, 272L, 276L, 277L, 284L, 285L, 287L, 288L, 289L, 290L, 292L, 293L, 294L, 295L, 303L, 304L, 305L, 306L, 308L, 309L, 310L, 315L, 316L, 318L, 319L, 320L, 321L, 325L, 333L, 334L, 336L, 337L, 338L, 339L, 347L, 348L, 350L, 351L, 352L, 353L, 354L, 359L, 365L, 366L, 367L, 368L, 369L, 373L, 374L, 381L, 382L, 384L, 385L, 386L, 387L, 390L, 395L, 396L, 397L, 398L, 406L, 407L, 408L, 409L, 411L, 412L, 416L, 417L, 421L, 422L, 423L, 424L, 430L, 431L, 432L, 433L, 438L, 439L, 440L, 441L, 447L, 448L, 450L, 452L, 454L, 455L, 456L, 457L, 458L, 459L, 468L, 472L, 473L, 476L, 477L, 481L, 483L, 484L, 485L, 488L, 493L, 494L, 495L, 501L, 504L, 508L, 511L, 512L, 513L, 514L, 516L, 518L, 519L, 520L, 523L, 524L, 526L, 528L, 529L, 534L, 535L, 538L, 539L, 540L, 543L, 544L, 550L, 555L, 556L, 558L, 561L, 562L, 564L, 565L, 576L, 577L, 582L, 583L, 584L, 585L, 590L, 594L, 596L, 597L, 598L, 599L, 605L, 606L, 607L, 608L, 613L, 614L, 615L, 616L, 620L, 622L, 623L, 624L, 625L, 629L, 631L, 632L, 633L, 634L, 643L, 644L, 647L, 657L, 660L, 665L, 666L, 673L, 674L, 675L, 676L, 691L, 692L, 693L, 696L, 700L, 705L, 706L, 707L, 708L, 711L, 712L, 713L, 720L, 721L, 722L, 723L, 728L, 729L, 730L, 731L, 733L, 734L, 735L, 741L, 742L, 743L, 744L, 750L, 751L, 752L, 753L, 759L, 760L, 761L, 762L, 772L, 777L, 787L, 790L), class = "data.frame")
library(igraph)
g = graph.data.frame(df)
plot(g, vertex.size = 6, edge.arrow.mode=1, edge.arrow.size = 0)
> head(df)
nodeA nodeB attributeA attributeB
1 3 16 25 1
4 4 16 25 1
5 42 17 130 1
7 43 24 110 1
8 44 24 110 1
9 29 25 110 1
在上面，第1行attributeA是节点3的独有属性，因此所有连接到节点3的边都必须具有属性25。同样，attributeB表示所有连接到节点的边节点16必须具有属性1。第1行不一定是边，但保留边没有冲突是必要的。
感谢阅读！
Is this a known problem? Can you point me to any references?
这是一个非常有趣的问题，而且我以前没有遇到过。
How would you approach this problem?
我会从整数规划的角度来解决这个问题。决策变量将用于 select 每个节点的属性（只允许标有两个端点属性的边）。此外，我们将 select 一个 "root node" 我们期望在大连接组件中，我们将创建从该根节点向外的流。每个其他节点都有需求 1，并且只能在有效边上流动。我们将从根节点推出的流量最大化；这将是大型组件中其他节点的数量。
为了实现这个公式，我将创建两个 类 变量：
- 节点属性变量：对于每个节点
i和属性a，我会创建一个二进制变量z_ia，如果节点 i 被分配属性 a，否则为 0。
- 流变量：对于从节点
i到j的每条边（我假设"from"是nodeA数据框，"to" 在您的数据框中是 nodeB），变量 x_ij 表示从 i 到 j 的流量（负值表示从 j 到 i).
我们还有一些不同的限制条件：
- Each node only has 1 attribute: 这可以用
\sum_{a\in A} z_ia = 1实现每个节点i，其中A是集合所有属性。
- 如果边无效，则边流为 0：对于从
i 到 j 的每条边，属性为 a 和 b，我们将分别有 x_ij <= n*z_ia、x_ij <= n*z_jb、x_ij >= -n*z_ia 和 x_ij >= -n*z_jb。在所有四个约束中，n 是节点总数。如果 z_ia=0 或 z_jb=0，这些约束将强制 x_ij=0，否则将不具有约束力。
- 流向任意非根节点的净流量落在[0, 1]：这个约束保证了所有的流出都必须来自根，所以节点只能得到流量如果它们连接到根。对于每个非根节点
i，边从节点集 I 传入，边从节点集 O 传出，这些约束的形式为 \sum_{j\in I} x_ji - \sum_{j\in O} x_ij >= 0 和 \sum_{j\in I} x_ji - \sum_{j\in O} x_ij <= 1.
objective是为了使流出根节点的流量最大化r。如果 r 有来自集合 I 中节点的传入边和指向集合 O 中节点的传出边，那么这个 objective（我们最大化）是 \sum_{j\in O} x_ji - \sum_{j\in I} x_ij。
有了这些变量和约束，您需要做的就是指定根节点r并求解；假设 r 在最大的组件中，该解决方案将指示属性到节点的最佳分配。如果您为每个根节点重新求解 r，您最终会得到全局最优分配。
以下使用 R 中的 lpSolve 包实现此方法：
library(lpSolve)
optim <- function(df, r) {
# Some book keeping
nodes = c(df$nodeA, df$nodeB)
u.nodes <- unique(nodes)
if (!r %in% u.nodes) {
stop("Invalid root node provided")
}
n.node <- length(u.nodes)
attrs = c(df$attributeA, df$attributeB)
node.attrs <- do.call(rbind, lapply(u.nodes, function(x) {
data.frame(node=x, attr=unique(attrs[nodes == x]))
}))
n.na <- nrow(node.attrs)
n.e <- nrow(df)
# Constraints limiting each node to have exactly one attribute
node.one.attr <- t(sapply(u.nodes, function(i) {
c(node.attrs$node == i, rep(0, 2*n.e))
}))
node.one.attr.dir <- rep("==", n.node)
node.one.attr.rhs <- rep(1, n.node)
# Constraints limiting edges to only be used if both attributes are selected
edge.flow <- do.call(rbind, lapply(seq_len(n.e), function(idx) {
i <- df$nodeA[idx]
j <- df$nodeB[idx]
a <- df$attributeA[idx]
b <- df$attributeB[idx]
na.i <- node.attrs$node == i & node.attrs$attr == a
na.j <- node.attrs$node == j & node.attrs$attr == b
rbind(c(-n.node*na.i, seq_len(n.e) == idx, -(seq_len(n.e) == idx)),
c(-n.node*na.j, seq_len(n.e) == idx, -(seq_len(n.e) == idx)),
c(n.node*na.i, seq_len(n.e) == idx, -(seq_len(n.e) == idx)),
c(n.node*na.j, seq_len(n.e) == idx, -(seq_len(n.e) == idx)))
}))
edge.flow.dir <- rep(c("<=", "<=", ">=", ">="), n.e)
edge.flow.rhs <- rep(0, 4*n.e)
# Constraints limiting net flow on non-root nodes
net.flow <- do.call(rbind, lapply(u.nodes, function(i) {
if (i == r) {
return(NULL)
}
rbind(c(rep(0, n.na), (df$nodeB == i) - (df$nodeA == i),
-(df$nodeB == i) + (df$nodeA == i)),
c(rep(0, n.na), (df$nodeB == i) - (df$nodeA == i),
-(df$nodeB == i) + (df$nodeA == i)))
}))
net.flow.dir <- rep(c(">=", "<="), n.node-1)
net.flow.rhs <- rep(c(0, 1), n.node-1)
# Build the model
mod <- lp(direction = "max",
objective.in = c(rep(0, n.na), (df$nodeA == r) - (df$nodeB == r),
-(df$nodeA == r) + (df$nodeB == r)),
const.mat = rbind(node.one.attr, edge.flow, net.flow),
const.dir = c(node.one.attr.dir, edge.flow.dir, net.flow.dir),
const.rhs = c(node.one.attr.rhs, edge.flow.rhs, net.flow.rhs),
binary.vec = seq_len(n.na))
opt <- node.attrs[mod$solution[1:n.na] > 0.999,]
valid.edges <- df[opt$attr[match(df$nodeA, opt$node)] == df$attributeA &
opt$attr[match(df$nodeB, opt$node)] == df$attributeB,]
list(attrs = opt,
edges = valid.edges,
objval = mod$objval)
}
它可以解决原始图中节点子集的问题，但随着节点数量的增加，它会变得相当慢：
# Limit to 5 nodes
keep <- c(3, 4, 6, 16, 42)
df.play <- df[df$nodeA %in% keep & df$nodeB %in% keep,]
(opt.play <- optim(df.play, 42))
# $attrs
# node attr
# 24 3 50
# 45 4 50
# 50 42 91
# 60 16 127
# 87 6 109
#
# $edges
# nodeA nodeB attributeA attributeB
# 416 42 3 91 50
# 417 42 4 91 50
#
# $objval
# [1] 2
那 运行 花了 15 秒。为了加快速度，您可以考虑切换到更强大的求解器，例如 cplex 或 gurobi。这些求解器可免费用于学术用途，但不免费。
If this is the solution is there a way using igraph in R to specify an "edge attribute constraint" and pull out the resulting, fragmented graph.
是的，给定属性，您可以轻松地对图形进行子集化和绘制。对于我上面解决的 5 节点示例：
g <- graph.data.frame(opt.play$edges, vertices=unique(c(df.play$nodeA, df.play$nodeB)))
plot(g, vertex.size = 6, edge.arrow.mode=1, edge.arrow.size = 0)
在解决这个问题时，我偶然发现了一个更简单的解决方案。看来我对问题的表述让答案很难看出来。
问题的核心是：当两个不同的约束应用于一个节点时，它实际上变成了两个不同的节点。
以这种方式构建挑战使我们能够为每组约束快速构建图表。然后我们可以快速检查这些，查看大小，以及（正如我最初的问题所期望的那样）select 保留最大图的约束集。
g = graph.data.frame(df); plot(g, vertex.size = 6, edge.arrow.mode=1, edge.arrow.size = 0)
# Combine the node and the rule into a new, unique node id referencing both the node and the constraint
df.split = c(df[,1:2]) + df[,3:4]*1E3
# Keep track of edge numbers in this dataset for later
df.split = cbind(df.split, row = seq(nrow(df)))
g.split = graph.data.frame(df.split); plot(g.split, vertex.size = 6, edge.arrow.mode=1, edge.arrow.size = 0)
# Decompose into unlinked sub graphs and count the edges in each
g.list = decompose.graph(g.split)
g.list.nodenum = sapply(g.list, ecount)
head(g.list.nodenum[order(g.list.nodenum, decreasing=T)])
[1] 9 8 5 5 5 5
# Select the largest subgraph
g.sub = g.list[[order(g.list.nodenum, decreasing=T)[1]]]
plot(g.sub)
# Find what edges these were in the original dataset
originaledges = E(g.sub)$row
originaledges
[1] 129 157 130 158 131 159 212 213 132
# Play with the resulting graph, the largest graph which obeys constraints at all nodes.
df.largest = df[originaledges,]
df.largest
nodeA nodeB attributeA attributeB
292 25 35 45 41
352 29 25 58 45
293 29 35 58 41
353 30 25 58 45
294 30 35 58 41
354 52 25 143 45
476 52 29 143 58
477 52 30 143 58
295 52 35 143 41
g.largest = graph.data.frame(df.largest); plot(g.largest, vertex.size = 6, edge.arrow.mode=1, edge.arrow.size = 0)
希望有一天这对某人有所帮助！
我正在尝试确定如何最好地解决这个问题。
给定一组节点和多个相互冲突的连接方式，我需要select一组不冲突的关系，以使最大数量的节点保持连接状态。
示例。
这是一个包含忽略冲突的所有可能关系（边）的图表。例如，这张图片没有描述边缘之间的依赖关系。
连接到特定节点的所有边都相互依赖。为简单起见，每条边暗示它连接的每个节点的属性，比如 A...Z。如果连接节点 3 和 16 的边指定属性 3-B 和 16-F，则连接 16 到其他节点的所有边都必须具有属性 16-F。类似地，所有连接 3 到其他节点的边都必须具有属性 3-B。
这是将属性 F 指定给节点 16 时的同一张图。该属性删除了大部分边，留下一条连接 16-4 的边和一条连接 16-3 的边。这在 16-42 之间没有留下任何边缘。
（16 在两张图片的左侧附近。）
此图并未说明连接 3-42 的边将为节点 42 指定属性，例如 42-X。这将进一步将连接限制为 42 并进一步分解图形。我没有显示这个，因为这是我的问题。
我正在寻求建议。
- 这是一个已知问题吗？你能给我指出任何参考资料吗？
- 如何 你会解决这个问题吗？我最好的想法是迭代， 从每条边开始，遍历所有可能的属性。评价每一个 划分并找出哪个保留了最大的网络。这个 不过听起来很有挑战性，我需要一些帮助。
- 如果这是解决方案，有没有办法在 R 中使用 igraph 来指定 "edge attribute constraint" 并提取生成的碎片图。
我这里有dput图表：
df = structure(list(nodeA = c(3L, 4L, 42L, 43L, 44L, 29L, 30L, 29L, 30L, 3L, 4L, 6L, 43L, 44L, 43L, 44L, 29L, 30L, 29L, 30L, 52L, 29L, 30L, 35L, 25L, 35L, 25L, 43L, 44L, 29L, 30L, 3L, 4L, 43L, 44L, 29L, 30L, 25L, 29L, 30L, 42L, 3L, 4L, 17L, 43L, 44L, 29L, 30L, 29L, 30L, 17L, 17L, 29L, 30L, 6L, 43L, 44L, 29L, 30L, 52L, 35L, 35L, 25L, 25L, 24L, 24L, 43L, 44L, 29L, 30L, 35L, 35L, 25L, 25L, 24L, 24L, 43L, 44L, 29L, 30L, 35L, 35L, 25L, 25L, 24L, 24L, 52L, 42L, 3L, 42L, 42L, 3L, 4L, 42L, 25L, 42L, 25L, 3L, 4L, 42L, 3L, 4L, 17L, 35L, 3L, 4L, 35L, 43L, 44L, 29L, 30L, 35L, 35L, 35L, 52L, 25L, 25L, 24L, 24L, 35L, 29L, 30L, 3L, 4L, 43L, 44L, 29L, 30L, 25L, 29L, 30L, 52L, 43L, 44L, 29L, 30L, 25L, 29L, 30L, 3L, 4L, 43L, 44L, 29L, 30L, 52L, 43L, 44L, 43L, 44L, 29L, 30L, 3L, 4L, 43L, 44L, 29L, 30L, 52L, 52L, 43L, 44L, 29L, 30L, 35L, 52L, 52L, 3L, 4L, 43L, 44L, 29L, 30L, 52L, 43L, 44L, 29L, 30L, 43L, 44L, 29L, 30L, 17L, 17L, 42L, 42L, 43L, 44L, 29L, 30L, 43L, 44L, 29L, 30L, 43L, 44L, 29L, 30L, 3L, 4L, 25L, 25L, 16L, 16L, 3L, 4L, 43L, 44L, 24L, 3L, 4L, 52L, 52L, 17L, 35L, 35L, 35L, 17L, 3L, 4L, 6L, 35L, 42L, 42L, 42L, 42L, 3L, 4L, 17L, 25L, 17L, 17L, 29L, 30L, 25L, 3L, 4L, 29L, 30L, 3L, 4L, 17L, 17L, 17L, 35L, 3L, 4L, 17L, 17L, 17L, 29L, 30L, 43L, 44L, 43L, 44L, 29L, 30L, 17L, 6L, 43L, 44L, 29L, 30L, 43L, 44L, 29L, 30L, 43L, 44L, 29L, 30L, 3L, 43L, 44L, 29L, 30L, 3L, 43L, 44L, 29L, 30L, 17L, 17L, 42L, 42L, 25L, 42L, 25L, 43L, 44L, 29L, 30L, 42L, 17L, 17L, 42L, 42L, 43L, 44L, 29L, 30L, 25L, 29L, 30L, 43L, 44L, 29L, 30L, 43L, 44L, 29L, 30L, 25L, 29L, 30L, 43L, 44L, 29L, 30L, 43L, 44L, 29L, 30L, 43L, 44L, 29L, 30L, 25L, 25L, 25L, 25L), nodeB = c(16L, 16L, 17L, 24L, 24L, 25L, 25L, 35L, 35L, 16L, 16L, 17L, 24L, 24L, 24L, 24L, 25L, 25L, 25L, 25L, 35L, 35L, 35L, 43L, 43L, 44L, 44L, 24L, 24L, 25L, 25L, 16L, 16L, 24L, 24L, 25L, 25L, 35L, 35L, 35L, 16L, 16L, 16L, 24L, 24L, 24L, 25L, 25L, 35L, 35L, 43L, 44L, 52L, 52L, 17L, 24L, 24L, 25L, 25L, 35L, 43L, 44L, 29L, 30L, 43L, 44L, 24L, 24L, 25L, 25L, 43L, 44L, 29L, 30L, 43L, 44L, 24L, 24L, 25L, 25L, 43L, 44L, 29L, 30L, 43L, 44L, 17L, 24L, 42L, 43L, 44L, 16L, 16L, 17L, 35L, 17L, 35L, 16L, 16L, 52L, 16L, 16L, 6L, 25L, 16L, 16L, 52L, 24L, 24L, 25L, 25L, 43L, 44L, 25L, 25L, 29L, 30L, 43L, 44L, 17L, 42L, 42L, 16L, 16L, 24L, 24L, 25L, 25L, 35L, 35L, 35L, 35L, 24L, 24L, 25L, 25L, 35L, 35L, 35L, 16L, 16L, 24L, 24L, 25L, 25L, 35L, 17L, 17L, 24L, 24L, 25L, 25L, 16L, 16L, 24L, 24L, 25L, 25L, 25L, 35L, 24L, 24L, 25L, 25L, 25L, 29L, 30L, 16L, 16L, 24L, 24L, 25L, 25L, 35L, 24L, 24L, 25L, 25L, 24L, 24L, 25L, 25L, 43L, 44L, 3L, 4L, 24L, 24L, 25L, 25L, 24L, 24L, 25L, 25L, 24L, 24L, 25L, 25L, 16L, 16L, 35L, 35L, 3L, 4L, 16L, 16L, 17L, 17L, 17L, 16L, 16L, 29L, 30L, 6L, 25L, 29L, 30L, 42L, 16L, 16L, 25L, 52L, 16L, 16L, 16L, 16L, 16L, 16L, 24L, 35L, 43L, 44L, 52L, 52L, 35L, 16L, 16L, 52L, 52L, 16L, 16L, 24L, 43L, 44L, 25L, 16L, 16L, 24L, 43L, 44L, 52L, 52L, 17L, 17L, 24L, 24L, 25L, 25L, 52L, 42L, 24L, 24L, 25L, 25L, 24L, 24L, 25L, 25L, 24L, 24L, 25L, 25L, 42L, 24L, 24L, 25L, 25L, 42L, 24L, 24L, 25L, 25L, 43L, 44L, 4L, 17L, 35L, 17L, 35L, 24L, 24L, 25L, 25L, 16L, 43L, 44L, 4L, 4L, 24L, 24L, 25L, 25L, 35L, 35L, 35L, 24L, 24L, 25L, 25L, 24L, 24L, 25L, 25L, 35L, 35L, 35L, 24L, 24L, 25L, 25L, 24L, 24L, 25L, 25L, 24L, 24L, 25L, 25L, 35L, 35L, 35L, 35L), attributeA = c(25L, 25L, 130L, 110L, 110L, 110L, 110L, 113L, 113L, 43L, 43L, 71L, 5L, 5L, 127L, 127L, 5L, 5L, 127L, 127L, 72L, 130L, 130L, 137L, 140L, 137L, 140L, 6L, 6L, 6L, 6L, 56L, 56L, 137L, 137L, 137L, 137L, 130L, 140L, 140L, 29L, 68L, 68L, 56L, 143L, 143L, 143L, 143L, 146L, 146L, 43L, 43L, 45L, 45L, 46L, 80L, 80L, 80L, 80L, 47L, 11L, 11L, 80L, 80L, 80L, 80L, 84L, 84L, 84L, 84L, 14L, 14L, 84L, 84L, 84L, 84L, 90L, 90L, 90L, 90L, 18L, 18L, 90L, 90L, 90L, 90L, 110L, 37L, 122L, 114L, 114L, 108L, 108L, 58L, 27L, 136L, 109L, 26L, 26L, 115L, 111L, 111L, 78L, 109L, 112L, 112L, 78L, 114L, 114L, 114L, 114L, 37L, 37L, 47L, 73L, 114L, 114L, 114L, 114L, 128L, 111L, 111L, 125L, 125L, 54L, 54L, 54L, 54L, 45L, 58L, 58L, 143L, 55L, 55L, 55L, 55L, 126L, 136L, 136L, 44L, 44L, 56L, 56L, 56L, 56L, 145L, 68L, 68L, 57L, 57L, 57L, 57L, 128L, 128L, 58L, 58L, 58L, 58L, 143L, 146L, 59L, 59L, 59L, 59L, 126L, 70L, 70L, 129L, 129L, 60L, 60L, 60L, 60L, 73L, 61L, 61L, 61L, 61L, 62L, 62L, 62L, 62L, 124L, 124L, 91L, 91L, 63L, 63L, 63L, 63L, 64L, 64L, 64L, 64L, 65L, 65L, 65L, 65L, 135L, 135L, 58L, 136L, 127L, 127L, 57L, 57L, 143L, 143L, 68L, 138L, 138L, 143L, 143L, 80L, 136L, 126L, 126L, 109L, 139L, 139L, 128L, 80L, 110L, 112L, 113L, 30L, 141L, 141L, 135L, 70L, 125L, 125L, 126L, 126L, 142L, 69L, 69L, 128L, 128L, 144L, 144L, 138L, 128L, 128L, 142L, 145L, 145L, 139L, 129L, 129L, 130L, 130L, 121L, 121L, 79L, 79L, 79L, 79L, 91L, 109L, 82L, 82L, 82L, 82L, 86L, 86L, 86L, 86L, 88L, 88L, 88L, 88L, 97L, 92L, 92L, 92L, 92L, 118L, 94L, 94L, 94L, 94L, 107L, 107L, 89L, 138L, 111L, 140L, 113L, 116L, 116L, 116L, 116L, 1L, 134L, 134L, 92L, 19L, 135L, 135L, 135L, 135L, 128L, 138L, 138L, 136L, 136L, 136L, 136L, 137L, 137L, 137L, 137L, 130L, 140L, 140L, 138L, 138L, 138L, 138L, 139L, 139L, 139L, 139L, 140L, 140L, 140L, 140L, 138L, 140L, 144L, 146L), attributeB = c(1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 3L, 3L, 3L, 3L, 3L, 3L, 3L, 3L, 3L, 3L, 3L, 3L, 3L, 3L, 3L, 3L, 3L, 3L, 4L, 4L, 4L, 4L, 5L, 5L, 5L, 5L, 5L, 5L, 5L, 5L, 5L, 6L, 7L, 7L, 7L, 7L, 7L, 7L, 7L, 7L, 7L, 7L, 7L, 7L, 7L, 10L, 10L, 10L, 10L, 10L, 10L, 10L, 10L, 11L, 11L, 11L, 11L, 13L, 13L, 13L, 13L, 13L, 13L, 14L, 14L, 14L, 14L, 17L, 17L, 17L, 17L, 17L, 17L, 18L, 18L, 18L, 18L, 19L, 19L, 19L, 19L, 19L, 23L, 23L, 23L, 23L, 24L, 24L, 25L, 25L, 25L, 27L, 27L, 28L, 28L, 29L, 29L, 29L, 36L, 36L, 36L, 36L, 36L, 36L, 37L, 37L, 37L, 37L, 37L, 37L, 38L, 38L, 38L, 41L, 41L, 41L, 41L, 41L, 41L, 41L, 41L, 41L, 41L, 42L, 42L, 42L, 42L, 42L, 42L, 42L, 43L, 43L, 43L, 43L, 43L, 43L, 43L, 44L, 44L, 44L, 44L, 44L, 44L, 45L, 45L, 45L, 45L, 45L, 45L, 45L, 45L, 46L, 46L, 46L, 46L, 46L, 46L, 46L, 47L, 47L, 47L, 47L, 47L, 47L, 47L, 48L, 48L, 48L, 48L, 49L, 49L, 49L, 49L, 49L, 49L, 50L, 50L, 50L, 50L, 50L, 50L, 51L, 51L, 51L, 51L, 52L, 52L, 52L, 52L, 54L, 54L, 54L, 55L, 56L, 56L, 56L, 56L, 56L, 56L, 57L, 58L, 58L, 58L, 58L, 59L, 59L, 59L, 59L, 59L, 60L, 60L, 60L, 60L, 62L, 63L, 64L, 65L, 66L, 66L, 66L, 66L, 66L, 66L, 66L, 66L, 67L, 68L, 68L, 68L, 68L, 70L, 70L, 70L, 70L, 70L, 71L, 72L, 72L, 72L, 72L, 72L, 72L, 72L, 77L, 77L, 78L, 78L, 78L, 78L, 79L, 80L, 81L, 81L, 81L, 81L, 85L, 85L, 85L, 85L, 87L, 87L, 87L, 87L, 89L, 91L, 91L, 91L, 91L, 92L, 93L, 93L, 93L, 93L, 96L, 96L, 97L, 108L, 108L, 110L, 110L, 115L, 115L, 115L, 115L, 117L, 117L, 117L, 118L, 122L, 125L, 125L, 125L, 125L, 125L, 125L, 125L, 126L, 126L, 126L, 126L, 127L, 127L, 127L, 127L, 127L, 127L, 127L, 128L, 128L, 128L, 128L, 129L, 129L, 129L, 129L, 130L, 130L, 130L, 130L, 135L, 137L, 141L, 143L)), .Names = c("nodeA", "nodeB", "attributeA", "attributeB" ), row.names = c(3L, 4L, 5L, 7L, 8L, 9L, 10L, 12L, 13L, 18L, 19L, 20L, 24L, 25L, 26L, 27L, 28L, 29L, 31L, 32L, 35L, 36L, 37L, 38L, 39L, 40L, 41L, 52L, 53L, 54L, 55L, 59L, 60L, 62L, 63L, 64L, 65L, 71L, 72L, 73L, 78L, 82L, 83L, 86L, 87L, 88L, 89L, 90L, 96L, 97L, 98L, 99L, 108L, 109L, 112L, 114L, 115L, 116L, 117L, 120L, 121L, 122L, 129L, 131L, 134L, 135L, 141L, 142L, 143L, 144L, 146L, 147L, 153L, 154L, 156L, 157L, 163L, 164L, 165L, 166L, 168L, 169L, 175L, 176L, 178L, 179L, 183L, 186L, 187L, 188L, 189L, 196L, 197L, 198L, 201L, 204L, 206L, 208L, 209L, 213L, 216L, 217L, 221L, 222L, 225L, 226L, 230L, 241L, 242L, 243L, 244L, 248L, 249L, 255L, 256L, 259L, 260L, 264L, 265L, 272L, 276L, 277L, 284L, 285L, 287L, 288L, 289L, 290L, 292L, 293L, 294L, 295L, 303L, 304L, 305L, 306L, 308L, 309L, 310L, 315L, 316L, 318L, 319L, 320L, 321L, 325L, 333L, 334L, 336L, 337L, 338L, 339L, 347L, 348L, 350L, 351L, 352L, 353L, 354L, 359L, 365L, 366L, 367L, 368L, 369L, 373L, 374L, 381L, 382L, 384L, 385L, 386L, 387L, 390L, 395L, 396L, 397L, 398L, 406L, 407L, 408L, 409L, 411L, 412L, 416L, 417L, 421L, 422L, 423L, 424L, 430L, 431L, 432L, 433L, 438L, 439L, 440L, 441L, 447L, 448L, 450L, 452L, 454L, 455L, 456L, 457L, 458L, 459L, 468L, 472L, 473L, 476L, 477L, 481L, 483L, 484L, 485L, 488L, 493L, 494L, 495L, 501L, 504L, 508L, 511L, 512L, 513L, 514L, 516L, 518L, 519L, 520L, 523L, 524L, 526L, 528L, 529L, 534L, 535L, 538L, 539L, 540L, 543L, 544L, 550L, 555L, 556L, 558L, 561L, 562L, 564L, 565L, 576L, 577L, 582L, 583L, 584L, 585L, 590L, 594L, 596L, 597L, 598L, 599L, 605L, 606L, 607L, 608L, 613L, 614L, 615L, 616L, 620L, 622L, 623L, 624L, 625L, 629L, 631L, 632L, 633L, 634L, 643L, 644L, 647L, 657L, 660L, 665L, 666L, 673L, 674L, 675L, 676L, 691L, 692L, 693L, 696L, 700L, 705L, 706L, 707L, 708L, 711L, 712L, 713L, 720L, 721L, 722L, 723L, 728L, 729L, 730L, 731L, 733L, 734L, 735L, 741L, 742L, 743L, 744L, 750L, 751L, 752L, 753L, 759L, 760L, 761L, 762L, 772L, 777L, 787L, 790L), class = "data.frame")
library(igraph)
g = graph.data.frame(df)
plot(g, vertex.size = 6, edge.arrow.mode=1, edge.arrow.size = 0)
> head(df)
nodeA nodeB attributeA attributeB
1 3 16 25 1
4 4 16 25 1
5 42 17 130 1
7 43 24 110 1
8 44 24 110 1
9 29 25 110 1
在上面，第1行attributeA是节点3的独有属性，因此所有连接到节点3的边都必须具有属性25。同样，attributeB表示所有连接到节点的边节点16必须具有属性1。第1行不一定是边，但保留边没有冲突是必要的。
感谢阅读！
Is this a known problem? Can you point me to any references?
这是一个非常有趣的问题，而且我以前没有遇到过。
How would you approach this problem?
我会从整数规划的角度来解决这个问题。决策变量将用于 select 每个节点的属性（只允许标有两个端点属性的边）。此外，我们将 select 一个 "root node" 我们期望在大连接组件中，我们将创建从该根节点向外的流。每个其他节点都有需求 1，并且只能在有效边上流动。我们将从根节点推出的流量最大化；这将是大型组件中其他节点的数量。
为了实现这个公式，我将创建两个 类 变量：
- 节点属性变量：对于每个节点
i和属性a，我会创建一个二进制变量z_ia，如果节点i被分配属性a，否则为 0。 - 流变量：对于从节点
i到j的每条边（我假设"from"是nodeA数据框，"to" 在您的数据框中是nodeB），变量x_ij表示从i到j的流量（负值表示从j到i).
我们还有一些不同的限制条件：
- Each node only has 1 attribute: 这可以用
\sum_{a\in A} z_ia = 1实现每个节点i，其中A是集合所有属性。 - 如果边无效，则边流为 0：对于从
i到j的每条边，属性为a和b，我们将分别有x_ij <= n*z_ia、x_ij <= n*z_jb、x_ij >= -n*z_ia和x_ij >= -n*z_jb。在所有四个约束中，n是节点总数。如果z_ia=0或z_jb=0，这些约束将强制x_ij=0，否则将不具有约束力。 - 流向任意非根节点的净流量落在[0, 1]：这个约束保证了所有的流出都必须来自根，所以节点只能得到流量如果它们连接到根。对于每个非根节点
i，边从节点集I传入，边从节点集O传出，这些约束的形式为\sum_{j\in I} x_ji - \sum_{j\in O} x_ij >= 0和\sum_{j\in I} x_ji - \sum_{j\in O} x_ij <= 1.
objective是为了使流出根节点的流量最大化r。如果 r 有来自集合 I 中节点的传入边和指向集合 O 中节点的传出边，那么这个 objective（我们最大化）是 \sum_{j\in O} x_ji - \sum_{j\in I} x_ij。
有了这些变量和约束，您需要做的就是指定根节点r并求解；假设 r 在最大的组件中，该解决方案将指示属性到节点的最佳分配。如果您为每个根节点重新求解 r，您最终会得到全局最优分配。
以下使用 R 中的 lpSolve 包实现此方法：
library(lpSolve)
optim <- function(df, r) {
# Some book keeping
nodes = c(df$nodeA, df$nodeB)
u.nodes <- unique(nodes)
if (!r %in% u.nodes) {
stop("Invalid root node provided")
}
n.node <- length(u.nodes)
attrs = c(df$attributeA, df$attributeB)
node.attrs <- do.call(rbind, lapply(u.nodes, function(x) {
data.frame(node=x, attr=unique(attrs[nodes == x]))
}))
n.na <- nrow(node.attrs)
n.e <- nrow(df)
# Constraints limiting each node to have exactly one attribute
node.one.attr <- t(sapply(u.nodes, function(i) {
c(node.attrs$node == i, rep(0, 2*n.e))
}))
node.one.attr.dir <- rep("==", n.node)
node.one.attr.rhs <- rep(1, n.node)
# Constraints limiting edges to only be used if both attributes are selected
edge.flow <- do.call(rbind, lapply(seq_len(n.e), function(idx) {
i <- df$nodeA[idx]
j <- df$nodeB[idx]
a <- df$attributeA[idx]
b <- df$attributeB[idx]
na.i <- node.attrs$node == i & node.attrs$attr == a
na.j <- node.attrs$node == j & node.attrs$attr == b
rbind(c(-n.node*na.i, seq_len(n.e) == idx, -(seq_len(n.e) == idx)),
c(-n.node*na.j, seq_len(n.e) == idx, -(seq_len(n.e) == idx)),
c(n.node*na.i, seq_len(n.e) == idx, -(seq_len(n.e) == idx)),
c(n.node*na.j, seq_len(n.e) == idx, -(seq_len(n.e) == idx)))
}))
edge.flow.dir <- rep(c("<=", "<=", ">=", ">="), n.e)
edge.flow.rhs <- rep(0, 4*n.e)
# Constraints limiting net flow on non-root nodes
net.flow <- do.call(rbind, lapply(u.nodes, function(i) {
if (i == r) {
return(NULL)
}
rbind(c(rep(0, n.na), (df$nodeB == i) - (df$nodeA == i),
-(df$nodeB == i) + (df$nodeA == i)),
c(rep(0, n.na), (df$nodeB == i) - (df$nodeA == i),
-(df$nodeB == i) + (df$nodeA == i)))
}))
net.flow.dir <- rep(c(">=", "<="), n.node-1)
net.flow.rhs <- rep(c(0, 1), n.node-1)
# Build the model
mod <- lp(direction = "max",
objective.in = c(rep(0, n.na), (df$nodeA == r) - (df$nodeB == r),
-(df$nodeA == r) + (df$nodeB == r)),
const.mat = rbind(node.one.attr, edge.flow, net.flow),
const.dir = c(node.one.attr.dir, edge.flow.dir, net.flow.dir),
const.rhs = c(node.one.attr.rhs, edge.flow.rhs, net.flow.rhs),
binary.vec = seq_len(n.na))
opt <- node.attrs[mod$solution[1:n.na] > 0.999,]
valid.edges <- df[opt$attr[match(df$nodeA, opt$node)] == df$attributeA &
opt$attr[match(df$nodeB, opt$node)] == df$attributeB,]
list(attrs = opt,
edges = valid.edges,
objval = mod$objval)
}
它可以解决原始图中节点子集的问题，但随着节点数量的增加，它会变得相当慢：
# Limit to 5 nodes
keep <- c(3, 4, 6, 16, 42)
df.play <- df[df$nodeA %in% keep & df$nodeB %in% keep,]
(opt.play <- optim(df.play, 42))
# $attrs
# node attr
# 24 3 50
# 45 4 50
# 50 42 91
# 60 16 127
# 87 6 109
#
# $edges
# nodeA nodeB attributeA attributeB
# 416 42 3 91 50
# 417 42 4 91 50
#
# $objval
# [1] 2
那 运行 花了 15 秒。为了加快速度，您可以考虑切换到更强大的求解器，例如 cplex 或 gurobi。这些求解器可免费用于学术用途，但不免费。
If this is the solution is there a way using igraph in R to specify an "edge attribute constraint" and pull out the resulting, fragmented graph.
是的，给定属性，您可以轻松地对图形进行子集化和绘制。对于我上面解决的 5 节点示例：
g <- graph.data.frame(opt.play$edges, vertices=unique(c(df.play$nodeA, df.play$nodeB)))
plot(g, vertex.size = 6, edge.arrow.mode=1, edge.arrow.size = 0)
在解决这个问题时，我偶然发现了一个更简单的解决方案。看来我对问题的表述让答案很难看出来。
问题的核心是：当两个不同的约束应用于一个节点时，它实际上变成了两个不同的节点。
以这种方式构建挑战使我们能够为每组约束快速构建图表。然后我们可以快速检查这些，查看大小，以及（正如我最初的问题所期望的那样）select 保留最大图的约束集。
g = graph.data.frame(df); plot(g, vertex.size = 6, edge.arrow.mode=1, edge.arrow.size = 0)
# Combine the node and the rule into a new, unique node id referencing both the node and the constraint
df.split = c(df[,1:2]) + df[,3:4]*1E3
# Keep track of edge numbers in this dataset for later
df.split = cbind(df.split, row = seq(nrow(df)))
g.split = graph.data.frame(df.split); plot(g.split, vertex.size = 6, edge.arrow.mode=1, edge.arrow.size = 0)
# Decompose into unlinked sub graphs and count the edges in each
g.list = decompose.graph(g.split)
g.list.nodenum = sapply(g.list, ecount)
head(g.list.nodenum[order(g.list.nodenum, decreasing=T)])
[1] 9 8 5 5 5 5
# Select the largest subgraph
g.sub = g.list[[order(g.list.nodenum, decreasing=T)[1]]]
plot(g.sub)
# Find what edges these were in the original dataset
originaledges = E(g.sub)$row
originaledges
[1] 129 157 130 158 131 159 212 213 132
# Play with the resulting graph, the largest graph which obeys constraints at all nodes.
df.largest = df[originaledges,]
df.largest
nodeA nodeB attributeA attributeB
292 25 35 45 41
352 29 25 58 45
293 29 35 58 41
353 30 25 58 45
294 30 35 58 41
354 52 25 143 45
476 52 29 143 58
477 52 30 143 58
295 52 35 143 41
g.largest = graph.data.frame(df.largest); plot(g.largest, vertex.size = 6, edge.arrow.mode=1, edge.arrow.size = 0)
希望有一天这对某人有所帮助！