Определения

В этой статье я опишу способы создания, и использования рубрикаторов, в основе которых лежит структура графа.
Рубрикатор, категоризатор, каталог категорий, предметный указатель, индекс. Для удобства будем считать, что все эти термины описывают примерно одно и то же. А там, где будут существенные отличия, мы будем явно на них указывать.
Информационный элемент – чаще всего файл, но в общем случае любая информация представленная как единое целое.

Введение

Рубрикаторы используются для решения самых разнообразных задач:

• Для ускорения поиска и облегчения навигации по большим массивам информации.
• Для пометки (тегирования) информации с целью организации выборок по определенным рубрикам
• Для сортировки информации по:
  областям знаний (физика, математика, биология)
  способам использования (Книги — читать, музыка — слушать, фильмы — смотреть)
  принадлежности (папки мои и общие документы)
  важности (папки inbox и spam) и т.п.
  

Алгоритм Флойда — Уоршелла — алгоритм для нахождения кратчайших расстояний между всеми вершинами взвешенного графа без циклов с отрицательными весами с использованием метода динамического программирования. Это базовый алгоритм, так что тем кто его знает — можно дальше не читать.

Этот алгоритм был одновременно опубликован в статьях Роберта Флойда (Robert Floyd) и Стивена Уоршелла (Stephen Warshall) в 1962 г., хотя в 1959 г. Бернард Рой (Bernard Roy) опубликовал практически такой же алгоритм, но это осталось незамеченным.

Многие достаточно часто сталкиваются с необходимостью создания различных диаграмм, графов, деревьев для удобного представления информации. Особенно важным этот вопрос может оказаться при создании презентаций. Большинство офисных пакетов предоставляют возможность создавать красивые диаграммы при помощи интерактивного интерфейса. А если нужно создать большую диаграмму? Или записать в ней математические формулы? Сосредоточиться на содержании, а не оформлении и расположении элементов на экране?

Преимущества использования LaTeX уже неоднократно обсуждались. Так же как и способы создания презентаций при помощи beamer и векторная графика из пакета PGF/Tikz. Но возможно ли получить в LaTeX диаграммы, не уступающие по внешнему виду полученным в больших и сложных пакетах? Один из способов предложен ниже.

Количество американских патентных заявок связанных с социальными сетями последние 5 лет росло на 250% каждый год (ссылка). Так, например, одна корпорация подала патентную заявку на метод ценообразования который учитывает положение покупателя в социальном графе (обсуждение на Slashdot). Другая корпорация недавно воплотила максимально упрощенный вариант этой схемы, продавая свои новые телефоны влиятельным узлам социального графа за $0, а остальным за $530.

Анализ социальных сетей (Social Network Analysis) существовал задолго до Интернета, но в последнее время набирает обороты.

Мне было интересно посмотреть, как эффективно алгоритм, выделяющий кластеры в графах, сработает для некоторых групп в Twitter, которые представляют для меня интерес.

23 января в Запорожье пройдет #UKRTWEET — первый всеукраинский баркэмп посвященный Twitter. Граф выше показывает, кто из его участников, с кем разговаривает и кого упоминает.

Заметка ниже посвящена анализу этого графа. Весь код используемых здесь скриптов лежит на github. Изложение, в какой-то мере, вдохновлено недавно упомянутой на Хабре книгой Тоби Сегаран «Программируем коллективный разум», код примеров которой доступен на сайте автора.

Также о data mining в Twitter я говорил 16 января на первой в этом году донецкой встрече "Кофе и код". Поэтому здесь параллельно проведу анализ группы людей из Донецка, которые пишут в Twitter. Кстати, в этом году донецкие встречи будут регулярными — каждую третью субботу месяца (следующая 20 февраля). Следите за группой.

Вступление

Как оказалось тема алгоритмов интересна Хабра-сообществу. Поэтому я как и обещал, начну серию обзоров «классических» алгоритмов на графах.
Так как публика на Хабре разная, а тема интересна многим, я должен начать с нулевой части. В этой части я расскажу что такое граф, как он представлен в компьютере и зачем он используется. Заранее прошу прощения у тех кто это все уже прекрасно знает, но для того чтобы объяснять алгоритмы на графах, нужно сначала объяснить что такое граф. Без этого никак.

Введение

Всем привет, пишу данный топик как логическое продолжение данной статьи о максимальном потоке минимальной стоимости, в конце которой был затронут алгоритм Дейксты. Соглашусь с автором, что описание и различные реализации алгоритма можно найти без проблем, и «колесо» я не изобретаю, но тем не менее опишу здесь практическую реализацию на языке C#. Кстати отмечу, что использую LINQ, так что для работы необходим NET 3.5.

UPDНаконец-то подчистил код :)

Немного теории

Чтобы сразу не кидали камни в мой огород дам ссылку на очень хорошее описание алгоритма на таком незаметном ресурсе как Википедия :). Там вполне доступно описан алгоритм и особенно рекомендую посмотреть пример. Копировать оттуда материал считаю бессмысленно. Все, считаем что теорию изучили.

Начало

Данный код представляет реализацию алгоритма на взвешенном неориентированном графе. Рассмотрим реализацию этого алгоритма.
Объектами данного алгоритма являются три класса:
• Apoint – класс, реализующий вершину графа
• Rebro – класс, реализующий ребро графа
• DekstraAlgoritm – класс, реализующий алгоритм Дейкстры.
Рассмотрим подробнее данные классы и самые важные методы.
APoint
Данный класс содержит в себе 5 полей:
•public float ValueMetka { get; set; } данное поле отвечает за хранение значений метки данной вершины. В программе под бесконечностью берется очень большое число, например 99999.
•public string Name { get; set; } – имя метки. Данное поле необходимо лишь для выведения удобно читаемого результата.
•public bool IsChecked { get; set; } – означает помечена метка или нет
•public APoint predPoint { get; set; } – «предок» точки, т.е. та точка которая является предком текущей в кратчайшем маршруте.
•public object SomeObj { get; set; } – некий объект
Каких-либо значимых методов данный класс не содержит.
Rebro
Данный класс содержит 3 поля:
•public APoint FirstPoint { get; set; } – начальная вершина ребра
•public APoint SecondPoint { get; set; } – конечная вершина ребра
•public float Value { get; set; } – весовой коэффициент.
Каких-либо значимых методов данный класс не содержит.
DekstraAlgorim
Данный класс представляет собой граф и реализацию алгоритма Дейкстры. Содержит 2 поля:
•public APoint[] points { get; set; } – массив вершин
•public Rebro[] rebra { get; set; }- массив ребер
Таким образом, эти 2 массива отражают граф. Рассмотрим методы:
•private APoint GetAnotherUncheckedPoint()
Данный метод возвращает очередную неотмеченную вершину, наименее удаленную, согласно алгоритму.
•public void OneStep(APoint beginpoint)
Данный метод делает один шаг алгоритма для заданной точке.
•private IEnumerable Pred(APoint currpoint)
Данный метод ищет соседей для заданной точки и возвращает коллекцию точек.
•public string MinPath(APoint begin,APoint end)
Данный метод возвращает кратчайший путь, найденный в алгоритме от начальной точке до конечной. Этот метод используется для наглядного отображения пути
•public void AlgoritmRun(APoint beginp)
Данный метод запускает алгоритм и принимает в качестве входа начальную точку.
Все основные методы описаны, представим процесс работы алгоритма в целом на рис.1. Основной метод OneStep представлен на рисунке 2.

Рис.1. Работа алгоритма в целом

Рис.2. Работа метода OneStep

Код

Наконец, рассмотрим сам код. В каждом классе написал подробные комментарии.

Последние пару дней я был погружен в задачу красивого ографления текстов. Идею я поймал, когда прочитал пост про граф ключевых слов для статей с сайта от alexwolf.
Мне же захотелось создать такие графы для произвольных текстов и посмотреть, насколько красивыми и интересными они могут быть. Не уверен, что все, кто меня сейчас читают, разделяют мое программистское понимание красоты, но все равно хочу сказать, что по-моему получилось красиво и забавно.

В прошлой заметке я поделился результатами своих экспериментов по построению графа ключевых слов. В ней я совершенно не касался «технических аспектов» построения графов. В комментариях меня попросили пролить свет и на техническую составляющую моих экспериментов. По здравому размышлению я решил вынести их в отдельную заметку, поскольку они могут сгодится для построения любого графа средствами набора утилит graphviz.

В начале мая этого года в разговоре с коллегой по работе (в ходе обсуждения одной задачи на практическое применение множеств) вспыл вопрос о построении связей между объектами одного сайта. Этот сайт представлял собой каталог аналогов Windows и Linux программ, и одной из «фишек» этого каталога была выборка ПО по разделам а-ля фасет (визуально фасет, а внутри все на множествах реализовано насколько я понял из обсуждения (реализацию сайта делал другой человек – нужно будет еще и с ним обсудить этот вопрос)). В общем говоря я несколько удивился задаче и… заявил, что она довольно тривиальна, и если при проектировании базы данных связи между таблицами делать как многое-к-многому, то решается все одним запросом. Поговорили и разошлись, но идея сидела в подсознании и долбила «можно же и лучше сделать».