Постановка задачи

Есть сайт, страницы которого связаны ссылками. В общем случае связаны как попало, т.е. не соответствуют какой-нибудь структуре каталогов. Хочется получить визуализированное представление графа связей сайта.

Пути решения

Начиная с главной страницы сайта скачиваем каждую страницу, выделяем из нее ссылки, записываем их в базу данных, чтобы посетить позже. Так двигаемся по еще не посещенными ссылкам, заполняя базу. Кроме таблицы ссылок заполняем таблицу связей между ними - у нас получается ориентированный граф (орграф). Технические детали - структура таблицы страниц сайта:

@code `id` bigint(20) NOT NULL autoincrement, `site` varchar(255) NOT NULL, `ext` tinyint(1) NOT NULL, `link` tinytext NOT NULL, `data` text NOT NULL, PRIMARY KEY (`id`), KEY `site` (`site`), KEY `ext` (`ext`) @/code

Таблица связей между страницами

@code `id` bigint(20) NOT NULL autoincrement, `site` varchar(255) NOT NULL, `from` bigint(20) NOT NULL, `to` bigint(20) NOT NULL, `count` bigint(20) NOT NULL, PRIMARY KEY (`id`), KEY `from` (`from`,`to`), KEY `site` (`site`) @/code

Пояснения: чтобы иметь возможность сканировать одновременно несколько сайтов (в режиме "ставишь на ночь и уходишь") добавлено поле `site`. Все операции выполняются в рамках одного сайта без пересечений. На стадии извлечения ссылок из страницы мы определяем, внутренняя это ссылка или внешняя (поле `ext`), чтобы случайно не выкачать весь интернет :) Контент посещенных ссылок мы сохраняем в `data` (для возможных дальнейших извращений), у еще не посещенных ссылок это поле не заполнено. Во второй таблице есть поле `count`, которое содержит сколько раз встречается эта связь.

Получение страниц

Для получения страниц и извлечения ссылок удобно использовать snoopy. Поставив задачу на крон, уходим спокойно спать.

@code <?php

/ Snoopy http://sourceforge.net/projects/snoopy requireonce('Snoopy-1.2.3/Snoopy.class.php');

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

function iteration() { // init $snoopy = new Snoopy(); //$snoopy->agent = "Mozilla/4.0 (compatible; MSIE 6.0; Windows XP)";

// Ищем первую запись с пустым полем data (и чтобы ссылка была внутренней) $sql = "SELECT * FROM `".DBPREFIX.DBTBLTEST. "` WHERE ( (`data`='') AND (`ext`=0) ) LIMIT 1"; $r = mysqlquery($sql); if (false = $r) { $mydie(); } $victim = mysqlfetchassoc($r); if (empty($victim)) { / Либо таблица пуста - либо полностью заполнена / В любом случае возвращаемся return 'Либо таблица пуста - либо полностью заполнена'; };

$id = $victim['id']; $site = $victim['site']; $link = $victim['link'];

/ fetch $snoopy->fetch('http:/'.$site.$link); $d = $snoopy->results; $t = $snoopy->striptext($d);

// save data $sql = "UPDATE `".DBPREFIX.DBTBLTEST. "` SET `data`='".mysqlescapestring($t)."' WHERE `id`=$id"; $r = mysqlquery($sql); if (false = $r) { $mydie(); }

// extract links $links = $snoopy->striplinks($d);

foreach ($links as $k=>$v) {

// corrections links $v = strreplace('\"', '', $v); $v = strreplace('"', '', $v); $v = strreplace("'", '', $v); // ext flag $ext = 0; / selection if (0 = strpos($v, 'http:/')) { / Линк начинается с http:/ - т.е. претендует на то чтобы быть внешним if ( (0 = strpos($v, 'http://www.'.$site)) || (0 = strpos($v, 'http://'.$site)) ) { // Это внутренний линк - преобразуем его к нормальному виду $v = strreplace('http://www.'.$site, '', $v); $v = strreplace('http://'.$site, '', $v); } else { / Это внешний линк - ставим его на заметку (будет начинаться с http:/) $ext = 1; } } elseif (0 = strpos($v, '/')) { // Линк начинается с / - т.е. от корня сайта - так и оставляем } else { // Линк cчитается от текущей директории - обрезать подставляемую текущую директорию // до первого слеша справа и добавить линк $v = substr($link, 0, strrpos($link, '/')+1).$v; } $links[$k] = $v = unslashify($v);

if (empty($v)) { continue; }

// if not exist link $sql = "SELECT `id`, `link` FROM `".DBPREFIX.DBTBLTEST. "` WHERE `link`='".mysqlescapestring($v)."'"; $r = mysqlquery($sql); if (false = $r) { $mydie(); } $exist = mysqlfetchassoc($r);

// save links if (empty($exist)) { $sql = "INSERT INTO `".DBPREFIX.DBTBLTEST."` (`id`,`site`,`ext`,`link`) VALUES ('', '$site', '$ext', '".mysqlescapestring($v)."')"; $r = mysqlquery($sql); if (false = $r) { $mydie(); } $to = mysqlinsertid(); } else { $links[$k] = $v = '[ '.$v.' ]'; $to = $exist['id']; }

// Связи

// Проверяем связь на существование $sql = "SELECT `id`, `count` FROM `".DBPREFIX.DBTBLLINK. "` WHERE ( (`from`='$id') AND (`to`='$to') ) "; $r = mysqlquery($sql); if (false = $r) { $mydie(); } $exist = mysqlfetchassoc($r);

if (empty($exist)) { // Если связи нет - вставляем $sql = "INSERT INTO `".DBPREFIX.DBTBLLINK."` (`id`,`site`,`from`,`to`,`count`) VALUES ('', '$site', '$id', '$to', '1')"; $r = mysqlquery($sql); if (false = $r) { $mydie(); } } else { // Если связь есть - увеличиваем count $sql = "UPDATE `".DBPREFIX.DBTBLLINK."` SET `count`='".($exist['count']+1)."' WHERE `id`=".$exist['id']; $r = mysqlquery($sql); if (false = $r) { $mydie(); } } } return $links; } ?> @/code

Визуализация графов

Теперь у нас есть граф и его надо визуализировать. Визуализация графов - тема очень плохо освещенная в рунете, поэтому надо это исправить. Итак, что же делать, чтобы визуализировать граф?

Есть пакет Graphviz, с дистрибутивом под Linux и Windows, который можно скачать с официального сайта. Для представления графов он использует собственный язык, поэтому нам понадобится преобразовать данные графа в понятную ему форму.

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

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

echo ('digraph G {node [fontsize=30];<br>ranksep = .5;". "<br>nodesep = .1;<br>edge [style="setlinewidth(1)"];'); foreach ($rel as $k=>$v) { $o = '"'.$nodes[$v['from']].'" -> "'.$nodes[$v['to']].'"'; echo($o.'<br />'); } echo('}');

?> @/code

После преобразования граф выглядит так:

@code digraph G { node [fontsize=30]; ranksep = .5; nodesep = .1; edge [style="setlinewidth(1)"]; "/" -> "/rss" "/" -> "/info/about" "/" -> "/info/contacts" "/" -> "/newuser" "/" -> "/services" "/" -> "/services/wedding-photo" … "/info/about" -> "/rss" "/info/about" -> "/info/about" "/info/about" -> "/info/contacts" "/info/about" -> "/newuser" … } @/code

Запускать отрисовку графа приходится из командной строки с именем файла в качестве параметра. Для сложных графов построение может занять длительное время. В этом демонстрационном примере я уменьшил количество узлов для наглядности.

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