Table of Contents

На <a href="/articles/php-site-graph">предыдущем этапе</a> мы получили визуализированное представление графа переходов внутри сайта http://gehirn.ru/. Однако при увеличении размеров сайта количество узлов и связей возрастает и граф становится ненаглядным. Граф хорошего (с точки зрения поисковых систем) сайта вообще приближается к полносвязному.

Метод

Хочется большей наглядности. Чтобы ее достичь мы можем сократить количество связей, выбрав среди них те, которые встречаются чаще - по ним вероятность прохода поискового бота выше. На предыдущей итерации мы получили сведения о том, сколько раз встречается данная связь между двумя страницами, но эти сведения справедливы для ориентированного графа. Остовное дерево же строится в неориентированном графе, поэтому мы должны преобразовать граф в неориентированный, сложив для каждой пары узлов их показатели весов.

@code <?php

define('DBPREFIX', 'Префикс таблиц'); define('DBTBLTEST', 'Таблица страниц сайта'); define('DBTBLLINK', 'Таблица связей между страницами');

$sql = "SELECT `from`, `to`, `count` FROM `". DBPREFIX.DBTBLLINK."` WHERE `site`='mycoolsite.ru'"; $r = mysqlquery($sql); if (false = $r) { $mydie(); } while ($row = mysqlfetchassoc($r)) { if ( (isset($nodes[$row['from']])) && (isset($nodes[$row['to']])) ) { $rel[] = $row; } }

$neor = array();

function hashto($v) { global $neor; $hash = md5($v['from']).md5($v['to']); if (!isset($neor[$hash])) { $neor[$hash] = $v; } else { $neor[$hash]['count'] += $v['count']; } }

foreach ($rel as $k=>$v) { if ($v['from'] < $v['to']) { hashto($v); } else { $w = array(); $w['from'] = $v['to']; $w['to'] = $v['from']; $w['count'] = $v['count']; hashto($w); } }

?> @/code

Построение

Теперь приступим собственно к построению остовного дерева. Наша задача - по возможности оставить те ребра, которые имеют наибольший вес. Алгоритм следующий:

@code • Выделяем одну вершину, которая будет началом нашего дерева (корень) • Далее на каждой итерации: ‣ Случайным образом выбираем вершину из строящегося дерева. ‣ Ищем ребра графа ведущие к любой вершине пока не входящей в дерево. ‣ Среди этих ребер выбираем ребро с максимальным весом. ‣ Добавляем это ребро и его вершину в дерево. • Итерации повторяем до тех пор, пока все вершины не будут входить в дерево. @/code

@code <?php

// Строим список узлов на основе связей $unmarkednodes = array(); foreach ($neor as $k=>$v) { if (!isset($unmarkednodes[$v['from']])) { $unmarkednodes[$v['from']] = ''; } if (!isset($unmarkednodes[$v['to']])) { $unmarkednodes[$v['to']] = ''; } } $countnodes = count($unmarkednodes); // Промаркированные узлы $markednodes = array(1=>'');

// Пока все вершины не стали помеченными while (count($markednodes) != $countnodes) { // Положить в U любую из помеченных вершин $U = arrayrand($markednodes); // Находим все ребра… $ulinkskey = ''; $ulinkscount = 0; $ulinksto = 0; foreach ($neor as $k=>$v) { // …которые из нее или в нее идут… if ( ($v['from'] = $U) || ($v['to'] = $U) ) { // …к непомеченным вершинам.. $to = ($v['from'] == $U)?$v['to']:$v['from']; if (!isset($markednodes[$to])) { // … и выбираем самое тяжелое ребро if ($v['count'] > $ulinkscount) { $ulinkskey = $k; $ulinkscount = $v['count']; $ulinksto = $to; } } } } / Если переменные поиска не изменились - значит для этой / вершины нет (больше) ребер, связывающих ее с непомеченными // вершинами. Можно переходить на следующую итерацию if ( ($ulinkskey = '') && ($u_links_count = 0) ) { continue; } // Помечаем ребро, чтобы потом построить конденсацию из помеченных ребер $neor[$ulinkskey]['tag'] = ''; // Помечаем вершину, чтобы исключить ее из поиска $markednodes[$ulinksto] = ''; }

?> @/code

Теперь перед нами стоит задача визуализации остовного дерева. В этом нам поможет Стендфорд :) Точнее, разработка Тамары Мюнзнер (Tamara Munzner), визуализирущая наше дерево в гиперболическом пространстве. Визуализацию можно даже вращать. Само приложение и сопроводительная документаци лежит здесь: <a href="http://graphics.stanford.edu/~munzner/h3/"> http://graphics.stanford.edu/~munzner/h3/ </a> Ниже - код, который создает представление графа, понятное H3Viewer`у

@code <?php

$sql = "SELECT `id`, `link` FROM `".DBPREFIX.DBTBLTEST. "` WHERE ((`ext`=0) AND (`site`='gehirn.ru'))"; $r = mysqlquery($sql); if (false = $r) { $mydie(); } while ($row = mysqlfetchassoc($r)) { $nodes[$row['id']] = $row['link']; }

$childs = array(); createchilds();

function createchilds($p=1) { global $childs, $rel; if (!isset($childs[$p])) { $childs[$p] = array(); } foreach ($rel as $k=>$v) { if ( ($v['from'] = $p) || ($v['to'] = $p) ) { $pair = ($v['from'] == $p)?$v['to']:$v['from']; if (!isset($childs[$pair])) { $childs[$p][] = ($v['from'] == $p)?$v['to']:$v['from']; } } } foreach ($childs[$p] as $v) { createchilds($v); } }

$massive = array(0=>array()); $level=array(0); $f = true;

h3v(1);

function h3v($in, $key='') { global $childs, $massive, $level; if (!isarray($in)) { // write $s = '$massive'; foreach ($level as $w) { $s .='["'.$w.'"]'; } eval($s.'["'.$in.'"] = array();'); //get array from childs $afromchild = $childs[$in]; h3v($afromchild, $in); } else { arraypush($level, $key); foreach ($in as $k=>$v) { h3v($v); } arraypop($level); } }

$level = 0; recout(current($massive));

function recout($v) { global $level, $nodes; if (!empty($v)) { foreach ($v as $k=>$w) { echo($level.' '.$nodes[$k].' 1 html<br>'); $level++; recout($w); $level–; } } }

?> @/code

Примерно так выглядят исходные данные: @code 0 / 1 html 1 /info/contacts 1 html 2 /info 1 html 1 /postid/3 1 html 2 /rss 1 html 3 /services/advert-photo 1 html 4 /portfolio/photo-wedding 1 html 4 /articles/inside-flash 1 html 5 /articles/focalsize 1 html 6 /articles/easy-portrait 1 html 3 /articles/model-work 1 html 4 /articles/hi-key 1 html 2 /info/about 1 html 3 /services 1 html 3 /services/wedding-photo 1 html 4 /services/art-portfolio 1 html 5 /articles/wedding-light 1 html 6 /articles/photo-theatre 1 html 3 /articles 1 html 3 /sitemap 1 html 4 /portfolio/photo-studio 1 html 4 /articles/portrait-light 1 html 1 /postid/2 1 html 2 /newuser 1 html 3 /services/portrait-photo 1 html 4 /services/reportage-photo 1 html 5 /articles/wedding-dress 1 html 6 /articles/wedding-makeup 1 html 6 /articles/find-photographer 1 html 4 /services/classic-portfolio 1 html 3 /portfolio 1 html 3 /articles/color-correction 1 html 2 /articles/flash-photo 1 html 3 /articles/speed-aperture 1 html 2 /articles/photoeye 1 html 3 /articles/studio-light 1 html 2 /articles/4rules 1 html 3 /postid/1 1 html @/code

А вот так выглядит собственно представление. Скачав программу и загрузив в нее эти данные можно представление покрутить.

<center><img src="/img/h3v.gif"/></center>