如何使用SPARQL计算有向图的最大度？

Question

我在两个单独的查询中计算了有向图中每个节点的入度和出度：

SELECT ?s (COUNT(*) AS ?outdegree) 
{ ?s ?p ?o }
GROUP BY ?s
ORDER BY DESC(?outdegree) 

SELECT ?o (COUNT(*) AS ?indegree) 
{ ?s ?p ?o }
GROUP BY ?o
ORDER BY DESC(?indegree)  

我需要计算图的最大度数。由于有向图的最大度是图的最大（入度+出度）值，我想知道如何组合上述两个查询的结果来计算它。

另外，如果有更有效的方法来做到这一点，也请提出建议。

Answer 1

您可以使用非常简单的查询来获取每个顶点的度数?x：

select ?x (count(*) as ?degree) { 
  { ?x ?p ?o } union
  { ?s ?p ?x }
}
group by ?x

例如，根据此数据：

@prefix : </sf/ask/1698937271/> .

#     a
#     |
#     V
# b<--c-->d
#     |
#     V  
#     e

:a :p :c .
:c :p :b, :d, :e .

你会得到结果：

---------------
| x  | degree |
===============
| :a | 1      |
| :b | 1      |
| :c | 4      |
| :d | 1      |
| :e | 1      |
---------------

现在，如果您想要最大的一个，您可以简单地订购并使用限制 1，例如，

select ?x (count(*) as ?degree) { 
  { ?x ?p ?o } union
  { ?s ?p ?x }
}
group by ?x
order by desc(?degree)
limit 1

---------------
| x  | degree |
===============
| :c | 4      |
---------------

如果只有一个具有最高度数的顶点，这将起作用。如果有多个具有相同最高学位的，您将只获得其中之一。

如果你真的想组合你得到的两个查询，那么像Rob Hall 的答案这样的东西就会起作用，除了因为子查询不返回具有 0 入度或 0 出度的节点，所以它们不存在于最终结果，因为他们无法加入。因此，只有在保证每个节点都有非零入度和出度时才使用该方法。他的答案对于如何构建图表并以编程方式使用 Jena 运行这些查询的示例也很有用。