Рубрика «графы» - 7

Компоненты связности в динамическом графе за один проход - 1
Люди встречаются, люди ссорятся, добавляются и удаляют друзей в социальных сетях. Этот пост о математике и алгоритмах, красивой теории, любви и ненависти в этом непостоянном мире. Этот пост о поиске компонент связности в динамических графах.

Большой мир генерирует большие данные. Вот и на нашу голову свалился большой граф. Настолько большой, что мы можем удержать в памяти его вершины, но не ребра. Кроме того, относительно графа приходят обновления – какое ребро добавить, какое удалить. Можно сказать, что каждое такое обновление мы видим в первый и последний раз. В таких условиях необходимо найти компоненты связности.

Поиск в глубину/ширину здесь не пройдут просто потому, что весь граф в памяти не удержать. Система неперескающихся множеств могла бы сильно помочь, если бы ребра в графе только добавлялись. Что же делать в общем случае?

Читать полностью »

Рассмотрим такую задачу: есть 1000 новостных сайтов, например: engadget.com, huffingtonpost.com, sbnation.com. Их нужно распределить по классам про игры, про бизнес и финансы, про IT, про кино и музыку, например. Как это сделать? Можно просто брать один сайт за другим и назначать ему класс, но чтобы обработать таким образом 1000 сайтов нужно иметь крепкую психику и уйму времени. Можно сделать более технично: взять граф похожих сайтов, выделить интересующий подграф на 1000 вершин и кластеризовать его. Про граф похожих сайтов было написано несколько месяцев назад мной и ребятами из DCA. Граф про новостные сайты будет выглядеть примерно так:
Полуавтоматическая классификация сайтов - 1

Действительно, некоторые классы получается выделить автоматически, например «игры» и «технологии»:
Полуавтоматическая классификация сайтов - 2
Читать полностью »

В прошлые выходные в Музее Москвы проходила выставка, в рамках которой Билайн проводил хакатон. Я, на всякий случай, решил сходить. Была предложена интересная задача: дан граф, в вершинах абоненты, в рёбрах записано число звонков одного абонента другому, их продолжительность и число смсок. Данные выглядели вот так:

A,B,x_A,x_B,c_AB,d_AB,c_BA,d_BA,s_AB,s_BA
941235,666804,0,1,1,20,1,22,0,0
604328,367223,1,0,0,0,5,1364,0,0
932768,977234,0,0,1,168,0,0,0,0
395101,677107,0,1,1,160,0,0,0,0
250712,102647,0,0,0,0,3,456,0,0
510653,896558,0,0,139,50954,22,2990,0,0
...

Читать полностью »

Построение диаграмм и графов в Doxygen - 1

Данная статья продолжает цикл статей о системе документации Doxygen (статья о самой системе, статья об оформлении документации). На этот раз статья посвящена построению различных диаграмм и графов в Doxygen. В ней мы рассмотрим основные их виды, различные способы их настройки и оформления, а также приведём ряд примеров и советов по их использованию.
Читать полностью »

Поиск самых длинных цепочек слов в русском языке с помощью языка Wolfram Language (Mathematica) - 1

Скачать перевод в виде документа Mathematica, который содержит весь код использованный в статье, можно здесь (архив, ~5 МБ).

Введение

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

Предположим, что у нас есть несколько последовательных метаграмм, скажем:

мнение-мление-тление-трение-прение-поение-роение-рдение-бдение-биение

они образуют цепь метаграмм, или цепочку слов.

Отсюда проистекает игра под названием цепь слов (word ladder), которую придумал в далеком 1879 году Льюис Кэрролл.

Ясно, что далеко не для каждого начального слова может быть составлена такого рода цепь, а некоторые слова, по-видимому, должны порождать довольно длинные цепи.

В этом посте мы постараемся проанализировать цепочки слов, которые могут быть построены в русском языке, а также найдем цепочки наибольшей длины.
Читать полностью »

Мы ввели на «Тостере» понятие «близких тегов». Для любого заданного тега мы научились определять те теги, которые ему «близки», а именно чаще других тегов встречаются в одних и тех же вопросах наряду с заданным. Это можно использовать для самых разных задач, пока же мы применили эту технологию вот для чего.

20 близких тегов

У каждого тега появился подраздел, в котором выводится 20 близких тегов. Попасть в этот подраздел можно из контекстного блока «Близкие теги», который выводится в правой колонке на всех подразделах тега. Этот подраздел призван улучшить качество и точность подписки на темы, которые интересуют каждого конкретного участника нашего сообщества. Пользуясь вдобавок дополнительным инструментом «Усиленной подписки», можно отслеживать вопросы по самым узким и специальным темам, не боясь ничего пропустить.

Тостер. Близкие теги, страница первой подписки на теги - 1
Читать полностью »

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

Оригинал на английском dmitra.com/graphiy/general-purpose-tree-editor/

Начиналось все с простой потребности в наведении порядка в файлах. Почему уже 2014 год, а до сих пор нет простого и удобного редактора деревьев хотя бы?
Текстовых редакторов — несметное множество и все равно появляются новые. Редакторов таблиц — поменьше, но жаловаться приходится только когда количество данных исчисляется тысячами.
А ведь самих-то способов представления информации не так много:
Строка, Список, Таблица, График, Диаграмма, Карта, 3d
Разумеется, есть огромное множество разновидностей этих видов, но количество достаточно популярных не превышает десятка.
По своей сути эти способы можно подразделить по количеству одновременно отображаемых характеристик.
Одномерные: список, временная шкала, хронометраж и т.п.
Двумерные: таблица, карта, график, гистрограмма и т.п.
Трехмерные: в основном нестандартные сложные научные 3d-визуализации
Многомерные: деревья, графы, сети

Визуализаций данных уже создано в избытке и продолжают изобретать новые. Для одних только деревьев известно под 3 сотни вариантов: treevis.net
А вот редакторы существуют для весьма малого количества самых популярных.
И в отношении многомерных данных существует огромный пробел.
Читать полностью »

Число Бейкона

Немного история, Кевин Бейкон американский актёр сыгравший во множествах фильмам, в 1994 отметил что актёры, с которыми снимался он, работали со всеми голливудскими (и не только) актёрами. Общественность тут же отреагировала и создала игру “назвать имя актёра и связать его с Кевином Бейконом”. Корпорация добра даже встроила игру в свой поисковик, например Число Бейкона для актёра Джона Траволты равно 2 (Джон снимался с Оливией Ньютон-Джон в фильме Бриолин, она же, в свою очередь, сыграла с Кевином Бейконом в фильме “У нее будет ребенок”).

А теперь давайте поговорим о том как это игру можно представить и как можно вычислить число Бейкона при помощи графа.
Читать полностью »

Не так давно наткнулся на статью о том, как Michael Kozakov не смог решить алгоритмическую задачу на собеседовании в Twitter. Решение этой задачи — почти в чистом виде один из самых стандартных алгоритмов на графах, а именно, алгоритм Дейкстры.
В этой статье я постараюсь рассказать алгоритм Дейкстры на примере решения этой задачи в несколько усложненном виде. Всех, кому интересно, прошу под кат. Читать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js