postgresql - 递归搜索拓扑网络表中的死胡同

Question

我已经尝试了几个星期来解决这个问题:我需要递归搜索一个拓扑网络，在本例中为 OpenStreetMap 街道，寻找死胡同，以及仅与网络其余部分相距一条边的社区。如果您所在的城市考虑周全，这些地方可能会出现禁止导出标志。

我的表有网络中每条边的记录。每条边都有一个“目标”和“源”字段，标识边的那一侧所连接的节点。我添加了一个名为“悬挂”的二进制列，以指示边缘是否已被识别为结束段。我假设最好的情况下将此列初始化为 FALSE。

到目前为止，我已经能够使用以下 SQL 简单地识别分支死胡同

WITH node_counts AS ( -- get all unique nodes
SELECT target AS node FROM edge_table WHERE NOT dangling
UNION ALL
SELECT source AS node FROM edge_table WHERE NOT dangling),
single_nodes AS ( -- select only those that occur once
SELECT node 
FROM node_counts
GROUP BY node
HAVING count(*) = 1
) -- 
UPDATE edge_table SET dangling = true 
FROM single_nodes
WHERE node = target OR node = source;

我只是继续运行这个查询，直到没有行被更新。结果看起来像这样(红色悬空 = 真):

http://i.stack.imgur.com/OE1rZ.png

太棒了!这工作得很好......但是如果你愿意的话，仍然有死胡同社区，它们只通过一个边缘连接到更大的网络。我如何识别这些？

我最好的猜测是我将在某个时候需要一个 WITH RECURSIVE，但这大约是我非数学思维的极限。谁能指出我正确的方向？

Answer 1

好的。我是这样想的:

我认为没有办法，或者至少没有简单的方法可以单独在 SQL 中实现它。我最终在 PHP 和 SQL 中实现了 Tarjan 的算法，创建了一个临时节点表，将每个节点链接到图形的强连接子组件。完成后，我将接触不属于最大子组件的节点的任何段更新为“悬挂”。所有在属于最大子组件的节点处开始和结束的边都属于主要街道网络(不是悬挂的)。

这是代码。请注意，在大图上运行可能需要很长时间。这对工作内存也很困难，但它对我的目的有用。

<?php
$username = '';
$password = '';
$database = '';

$edge_table = 'cincy_segments';
$v1 = 'target';
$v2 = 'source';

$dangling_boolean_field = 'dangling';
$edge_id_field = 'edge_id';

//global variables declared
$index = 0;
$component_index = 0;
$nodes = array();
$stack = array();

pg_connect("host=localhost dbname=$database user=$username password=$password");

// get vertices
echo "getting data from database\n";
$neighbors_query = pg_query("
WITH nodes AS (
    SELECT DISTINCT $v1 AS node FROM $edge_table
    UNION
    SELECT DISTINCT $v2 AS node FROM $edge_table
), 
edges AS (
SELECT 
    node,
    $edge_id_field AS edge
FROM nodes JOIN $edge_table
    ON node = $v1 OR node = $v2
)
SELECT
    node,
    array_agg(CASE WHEN node = $v2 THEN $v1 
    WHEN node = $v1 THEN $v2
    ELSE NULL
    END) AS neighbor    
FROM edges JOIN $edge_table ON 
    (node = $v2 AND edge = $edge_id_field) OR 
    (node = $v1 AND edge = $edge_id_field)
GROUP BY node");

// now make the results into php results
echo "putting the results in an array\n";
while($r = pg_fetch_object($neighbors_query)){ // for each node record
    $nodes[$r->node]['id'] = $r->node;
    $nodes[$r->node]['neighbors'] = explode(',',trim($r->neighbor,'{}'));
}

// create a temporary table to store results
pg_query("
    DROP TABLE IF EXISTS temp_nodes;
    CREATE TABLE temp_nodes (node integer, component integer);
");

// the big traversal
echo "traversing graph (this part takes a while)\n";
foreach($nodes as $id => $values){
    if(!isset($values['index'])){
        tarjan($id, 'no parent');
    }
}

// identify dangling edges
echo "identifying dangling edges\n";
pg_query("
    UPDATE $edge_table SET $dangling_boolean_field = FALSE; 
    WITH dcn AS ( -- DisConnected Nodes
        -- get nodes that are NOT in the primary component
        SELECT node FROM temp_nodes WHERE component != (
            -- select the number of the largest component
            SELECT component
            FROM temp_nodes 
            GROUP BY component 
            ORDER BY count(*) DESC
            LIMIT 1)
    ),
    edges AS (
        SELECT DISTINCT e.$edge_id_field AS disconnected_edge_id
        FROM 
            dcn JOIN $edge_table AS e ON dcn.node = e.$v1 OR dcn.node = e.$v2
    )
    UPDATE $edge_table SET $dangling_boolean_field = TRUE
    FROM edges WHERE $edge_id_field = disconnected_edge_id;
");

// clean up after ourselves
echo "cleaning up\n";
pg_query("DROP TABLE IF EXISTS temp_nodes;");
pg_query("VACUUM ANALYZE;");

 // the recursive function definition
//
function tarjan($id, $parent)
{
    global $nodes;
    global $index;
    global $component_index;
    global $stack;

    // mark and push
    $nodes[$id]['index'] = $index;
    $nodes[$id]['lowlink'] = $index;
    $index++;
    array_push($stack, $id);

    // go through neighbors
    foreach ($nodes[$id]['neighbors'] as $child_id) {
        if ( !isset($nodes[$child_id]['index']) ) { // if neighbor not yet visited
            // recurse
            tarjan($child_id, $id);
            // find lowpoint
            $nodes[$id]['lowlink'] = min(
                $nodes[$id]['lowlink'],
                $nodes[$child_id]['lowlink']
            );
        } else if ($child_id != $parent) { // if already visited and not parent
            // assess lowpoint
            $nodes[$id]['lowlink'] = min(
                $nodes[$id]['lowlink'],
                $nodes[$child_id]['index']
            );
        }
    }
    // was this a root node?
    if ($nodes[$id]['lowlink'] == $nodes[$id]['index']) {
        do {
            $w = array_pop($stack);
            $scc[] = $w;
        } while($id != $w);
        // record results in table
        pg_query("
            INSERT INTO temp_nodes (node, component)
            VALUES (".implode(','.$component_index.'),(',$scc).",$component_index) 
        ");
        $component_index++;
    }
    return NULL;
}

?>