4

有向グラフの各ノードの入次数と出次数を 2 つの個別のクエリで計算しました。

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)

グラフの最大次数を計算する必要があります。有向グラフの最大次数はグラフの最大 (indegree + outdegree) 値であるため、上記の 2 つのクエリの結果を組み合わせて計算する方法を知りたいです。

また、これを行うためのより効率的な方法があれば、それも提案してください。

4

2 に答える 2

3

非常に単純なクエリを使用して、各頂点の次数を取得できます?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 の制限を使用できます。たとえば、

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

これは、次数が最高の頂点が 1 つしかない場合に機能します。最高次数が同じものが複数ある場合は、そのうちの 1 つだけを取得します。

取得した2つのクエリを本当に組み合わせたい場合は、サブクエリが0のインデグリーまたは0のアウトデグリーを持つノードを返さないため、それらが存在しないことを除いて、ロブホールの答えのようなものが機能します参加できないため、最終結果。したがって、すべてのノードの入次数と出次数がゼロでないことが保証されている場合にのみ、そのアプローチを使用してください。彼の答えは、グラフを作成し、これらのクエリを Jena でプログラム的に実行する方法の例としても役立ちます。

于 2014-06-17T19:02:20.813 に答える