Bağlı bir grafiği var (aksi maksimum mesafe sonsuz) ve tüm düğüm noktaları numaraları varsayarsak ....

(From_node, to_node, 1), (mesafe nedeniyle, itibaren) bir tablo tohum. Her demet için, from_node değeri her zaman to_node değerinden daha az olduğundan emin olmalısınız

CREATE TABLE hops (
    from_node int not null,
    to_node int not null,
    distance int not null default 0,
    primary key (from_node, to_node, distance)
)

-- first load:
INSERT INTO hops (from_node, to_node)
SELECT from_node, to_node FROM rel;

-- iterative step
INSERT INTO hops (from_node, to_node, distance)
SELECT a.from_node, b.to_node, min(a.distance+b.distance)
FROM hops a, hops b
WHERE a.to_node = b.from_node
  AND a.from_node <> b.from_node  -- not self
  AND a.to_node <> b.to_node      -- still not self
  AND a.from_node <> b.from_node  -- no loops
  AND NOT EXISTS (                -- avoid duplicates
          SELECT * FROM hops c
          WHERE c.from_node = a.from_node
            AND c.to_node = b.to_node
            AND c.distance = a.distance+b.distance)
GROUP BY a.from_node, b.to_node

Hiçbir satır eklenir kadar art arda ekleme yürütmek. Sonra çapı almak için maksimum mesafe seçin.

EDIT: ağırlıklı köşeler ile bir grafik için, sadece yerine 1 kullanarak daha ağırlıkları ile mesafe alan tohum olacaktır.

Mesafe ve çapı ile ilgili Wikipedia article grafiğinde (ağ) terimlerini görmek. Bu çapını bulmak için nasıl bir kaç not bahseder. This section grafikler bağlı bileşenleri yazının da size grafiğin çapını anlatmak çok kolay adapte olabilir bunların bağlı bileşenleri, keşfetmek için bir algoritma önerir. (Birden fazla bileşenleri varsa o çap inanıyorum sonsuzdur.) Algoritması bir ekmek / derinlik ilk arama dayalı basit bir, yani uygulamak çok sorun olmamalı ve verimlilik olmamalı büyük bir sorun ya.

Yukarı bu yazı için (ben o kadar çaba alacağını sanmıyorum ama) değilseniz, iyi bir network / grafik analizi kitaplığı bakarak öneririz. Ben PHP kullanarak bakmak isterdim hangilerinin emin değilim ama birkaç, orada var. (Muhtemelen birlikte çalışma çeşit kullanmak zorunda.)

O zaten, Umut olur.

Ben gerçekten size cluster coefficient, bir ağ bulmak istedim geliyordu düşünüyorum. Ayrıca, PHP bunu yapmak istiyorum. Ben iyi ağ analizi kitaplıkları PHP uzantıları taşıdık edilmiştir kaç bilmiyorum.

Eğer makaleyi takip ederseniz Ancak, kendi ile gelip (çok) zor olmamalı. Sen güzel grafikler üretmek gerekmez, sadece katsayısını bulmak zorunda.

Size ne demek değilse, lütfen güncelleme / Sorunuzu netleştirmek.

Ağ bağlı bir grafiktir. Peki neden bazı verilere grafik gösterimi oluşturmak ve bu konuda BFS veya DFS gerçekleştirmek denemiyorsunuz? Eğer aradığınız tam olarak alırsınız.

Bu kadar basit:

• Prepare
  • Adlı bir colum ekleme distance
  • Tüm düğümlere -1 mesafesini ver
• First Iteration
  • Herhangi bir düğümü seçin (örneğin, ilk)
  • o 1 mesafesini verir
  • Now iterate until there are nodes with distance -1
    • UPDATE table SET distance=:i+1 WHERE from_node IN (SELECT to_node FROM table WHERE distance=:i)
• Second Iteration
  • Maksimum mesafe (herhangi) olan bir düğüm pick - hatırlıyorum
  • Lütfen -1 tüm mesafeleri ayarla
  • 1 için remebered düğümü ayarlayın
  • Yinelemenin ikinci kez diyoruz

Bu kez maksimum mesafe sizin grafik / ağ çapı.

Örnekte her düğüm diğer düğüme bağlantılar olduğunu göstermektedir. Bu kurulum boyunca durumda ise, o zaman çapı 1'dir.

Kur doğrusal oluşumunda şöyle bir satır varsa:

n=1, n = 2, n = 3, ... n

Sonra çapı (n +1) / 3.

Kur N sayıda düğüm ve link K sayıda bir dizi, daha düzensiz ise, o zaman da çapı at least logN/LogK

Edit: Ben düğümler çiftleri arasındaki ortalama kısa mesafeyi hesap yapıyorum, açıklığa kavuşturmak için.

n1 - n2 - n3
(n+1)/3 = 4/3

n1-n2 = 1 hop
n2 - n3 = 1 hop
n1- n2 - n3 = 2 hops
(1+1+2)/3 = 4/3