0

原始数据表为

+--------+--------+--------+
| 节点_1 | 节点_2 | 重量 |
+--------+--------+--------+
| 1 | 2 | 5 |
| 1 | 3 | 10 |
| 2 | 1 | 21 |
| 1 | 4 | 15 |
+--------+--------+--------+

这是一个有向加权图。我想要的是将有向图转换为无向图，例如

+--------+--------+--------+
| 节点_1 | 节点_2 | 重量 |
+--------+--------+--------+
| 1 | 2 | 26 |
| 1 | 3 | 10 |
| 1 | 4 | 15 |
+--------+--------+--------+

拥有一条边（1,3）并不意味着存在一条边（3,1）。

如何解决这个问题呢？

4

3 回答 3

2

看起来您想对无向节点的权重求和。您的示例不清楚同一节点之间是否可以有多个有向边（即 1->2、1->2、1->2），但在这里我假设它们也应该合并

我没有方便的 PSQL 数据库来测试它，但这是非常普通的 SQL，所以你应该没问题。

免责声明：请先在测试台上使用 ROLLBACK 进行尝试。不要相信你的真实数据相信互联网上陌生人的建议，特别是如果他们有 1-rep :-)

这里的技巧是很难将可互换的两列（node_1，node_2）分组，所以我首先将它们重新排列为不可互换/有序

BEGIN TRANSACTION

  -- 1a) Make a temporary place to hold our values
  CREATE TEMP TABLE tempnodes (int low_node, int high_node, int weight)
    ON COMMIT DROP;

  -- 1b) consistently write the nodes to temp
  -- making sure node_1 always <= node_2
  -- this ordering helps our grouping in the next step
  INSERT INTO temptable (low_node, high_node, weight)
    SELECT least(node_1, node_2), greatest(node_1, node_2), weight
    FROM oldtable;

  -- 2a) Create a place for our new data
  -- Alternatively, you could truncate the old table
  -- and write the new values back there
  -- however, this way we can go back if/when we make a mistake
  CREATE TABLE newtable(int low_node, int high_node, int summed_weight);

  -- 2b) merge the edges 
  INSERT INTO newtable( low_node, high_node, summed_weight)
    SELECT low_node, high_node, sum(weight)
    FROM temptable
    GROUP BY low_node, high_node;

ROLLBACK TRANSACTION;
--COMMIT TRANSACTION;
于 2013-11-15T07:49:16.827 回答
2

如果您不想（或需要）实际更改数据，则可以通过一次选择来执行此操作：

select least(node_1, node_2) as node_1, 
       greatest(node_2, node_1) as node_2, 
       sum(weight) as weight
from graph
group by least(node_1, node_2), greatest(node_2, node_1)
order by 1,2;

如果你需要有向图和无向图，你可以把上面的变成一个视图。

与 pratik 的回答类似，这可以组合成一个更改基础表的语句：

with directed_graph as (
  select least(node_1, node_2) as node_1, 
         greatest(node_2, node_1) as node_2, 
         sum(weight) as weight
  from graph
  group by least(node_1, node_2), greatest(node_2, node_1)
), 
new_graph as (
  update graph 
    set weight = dg.weight
  from directed_graph dg
  where (graph.node_1, graph.node_2) = (dg.node_1, dg.node_2)
  returning graph.*
)
delete from graph 
where not exists (select 1 
                  from new_graph ng
                  where ng.node_1 = graph.node_1 
                    and ng.node_2 = graph.node_2);

这是一个 SQLFiddle 演示：http ://sqlfiddle.com/#!15/ad5b7/1

于 2013-11-15T08:14:15.147 回答
1

您需要使用 update 和 delete 这两个语句来解决这个问题。

UPDATE test_prit_1 t_1
   SET weight = weight + coalesce((SELECT t_2.weight
                               FROM test_prit_1 t_2
                              WHERE t_2.node_1 = t_1.node_2
                                AND t_2.node_2 = t_1.node_1
                                AND t_2.node_1 > t_2.node_2),
                             0)

然后 delete 语句删除多余的行（在给定的示例 node_1 = 2 和 node_2 = 1 中）

DELETE FROM test_prit_1 t_1
 WHERE EXISTS (SELECT 1
          FROM test_prit_1 t_2
         WHERE t_2.node_1 = t_1.node_2
           AND t_2.node_2 = t_1.node_1
           AND t_2.node_2 > t_2.node_1)
于 2013-11-15T07:42:41.597 回答