如何使用SPARQL计算有向图的最大程度? [英] How to calculate maximum degree of a directed graph using SPARQL?

问题描述

我已经通过两个单独的查询计算了有向图中每个节点的入度和出度:

I have computed the indegree and outdegree of each node in the directed graph in two separate queries:

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)  

我需要计算图的最大程度.由于有向图的最大度数是该图的最大(输入度+输出度)值，因此我想知道如何结合以上两个查询的结果来进行计算.

I need to compute the maximum degree of the graph. Since max degree of a directed graph is the maximum (indegree+outdegree) value of the graph , I want to know how to combine the results of the above two queries to compute it.

此外，如果有更有效的方法，也请提出建议.

Also, if there is a more efficient way of doing this, please suggest them as well.

推荐答案

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

You can use a pretty simply query to get the degree of each vertex ?x:

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

例如，关于此数据:

@prefix : <https://stackoverflow.com/q/24270532/1281433/> .

#     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，例如

Now, if you want the maximum one, you can simply order and use a limit of 1, e.g.,

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      |
---------------

如果只有一个顶点具有最高的度，则此方法将起作用.如果有多个具有相同最高学位的人，您将只选择其中之一.

This will work if there's only one vertex with the highest degree. If there are multiple with the same highest degree, you'll just get one of them.

如果您真的想组合您所拥有的两个查询，则类似于 Rob Hall's答案将起作用， 除外，因为子查询不返回具有0度或0度度的节点，所以它们不在最终结果中，因为它们不存在可以加入.因此，只有在确保每个节点的度数和度数都不为零的情况下，才使用该方法.他的答案还有助于举例说明如何使用Jena以编程方式构造图形并运行这些查询.

If you really want to combine the two queries that you've got, then something like Rob Hall's answer will work, except that since the subqueries don't return the nodes that have a 0 indegree or 0 outdegree, they're not present in the final results, since they're not available to join on. So only use that approach if you're guaranteed that every node has non-zero indegrees and outdegrees. His answer is also useful as an example of how to construct the graph and run these queries with Jena programmatically.

这篇关于如何使用SPARQL计算有向图的最大程度?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！