Продолжение и, скорее всего, окончание моего исследования про графы из текстов.
Мне подсказали страницу, где есть реализация одного алгоритма (QuickSort) на разных языках программирования, а значит есть отличная возможность сравнить графы этих «одинаковых» программ.
Под катом полученные графы для языков: C, C++, Java, Visual Basic, Delphi, Python, Php, Prolog, Fortran, Ruby, Haskell, Algol, Mathematica, Asm.
Попробуйте не заглядывая под кат угадать, какой граф будет наиболее красивым и какой самым страшным?

Недавно на Хабре была статья, посвященная алгоритмам на графах. С позволения автора, мой первый хабратопик продолжит цикл.

Хотелось бы осветить вопросы применения некоторых алгоритмов, для решения задач программирования.
Достаточно жизненный пример, с которым сталкивался не один разработчик — это deadlock. По сути deadlock – это взаимоблокировка, в результате которой система, или какие-то отдельные процессы начинают конкурировать за один ресурс.
В жизни такие ситуации встречаются, например, когда два человека желают пропустить друг друга на входе, предположим, в аудиторию. Однако после 3-4 фраз «только после вас!», кто-нибудь всё же пройдет первым.
На уровне программного обеспечения всё сложнее, пока программы не способны думать, машинный аналог фразы «только после вас!» будет повторяться вплоть до перезагрузки.
Как исполняющая система может повлиять на этот процесс? Вот тут нам на помощь и приходят алгоритмы на графах.
Для начала определимся, что же будет элементами нашего графа, и как его составить.

Пролог

В продолжение опубликованной на выходных статьи.

Компиляторы — пожалуй одна из самых интересных тем системного программирования.
Эта статья не расскажет как написать идеальный, или, хотя бы, работающий компилятор, но она поможет прояснить пару аспектов его работы, при помощи метода топологической сортировки сети.

Недавно я опубликовал серию постов на тему визуализации данных в интернете. Данная проблема для меня является актуальной в связи с возникшей задачей визуализации связей между веб-сайтами по поисковому запросу.

Был сделан небольшой прототип под названием Einstein, позволяющий решить поставленную задачу.

Server-side: asp.net 3.5 + data extracting sdk + google.
Client side: JavaScript InfoVis Toolkit

Возможно, кому-то будет интересно поиграться с разными запросами.

Введение

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

Да и простого любопытствующего обывателя, не отягощённого подробностями органической химии, подобные вопросы не обходят стороной.

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



Такой предельно упрощённой и наглядной моделью могут оказаться «Живые графы» — конечные автоматы на графе, каждый узел которого содержит некое исполняющее устройство (автомат) с конечным числом состояний и с набором примитивных правил, управляющих созданием или изменением новых связей между узлами.

Из многих алгоритмов поиска кратчайших маршрутов на графе, на Хабре я нашел только описание алгоритма Флойда-Уоршалла. Этот алгоритм находит кратчайшие пути между всеми вершинами графа и их длину. В этой статье я опишу принцип работы алгоритма Дейкстры, который находит оптимальные маршруты и их длину между одной конкретной вершиной (источником) и всеми остальными вершинами графа. Недостаток данного алгоритма в том, что он будет некорректно работать если граф имеет дуги отрицательного веса.

Для примера возьмем такой ориентированный граф G:

Продолжаем публикацию наиболее интересных глав из книги Magnus Lie Hetland «Python Algorithms». Предыдущая статья расположена по адресу habrahabr.ru/blogs/algorithm/111858. Сегодня же речь пойдет об эффективной работе с графами и деревьями и особенностях их реализации в Python. Базовая терминология теории графов уже обсуждалась (например здесь: habrahabr.ru/blogs/algorithm/65367), так что я не включил часть главы о терминах в эту статью.

Реализация графов и деревьев

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

Иногда полезно представить граф в графической форме, так чтобы была видна структура. Можно привести десятки примеров, где это может пригодиться: визуализация иерархии классов и пакетов исходного кода какой-нибудь программы, визуализация социального графа (тот же Twitter или Facebook) или графа цитирования (какие публикации на кого ссылаются) и т.д. Но вот незадача: количество ребер в графе зачастую настолько велико, что нарисованный граф просто невозможно разобрать. Взгляните на эту картинку:



Это граф зависимостей некой программной системы. Он представляет собой дерево разбиения на пакеты (серые шарики — пакеты, белые — классы), на которое поверх наложены ребра зависимости одних классов от других. Чтобы не рисовать стрелки направления, ребра нарисованы в виде градиентных линий, где зеленый — это начало, а красный — конец ребра. Как видите, граф настолько визуально перегружен, что архитектуру программы невозможно проследить.
Под катом описание метода, решающего эту проблему.

Приветствую всех читателей Хабра! Решив написать эту статью, я обнаружил на Хабре много материалов по графам и, в частности, по топологической сортировке. Например, здесь довольно подробно описана теоретическая часть и приведены примеры основных алгоритмов. Поэтому не буду повторяться, а расскажу о практической области применения Topological sorting, а точнее, хочу поделиться личным опытом применения этого метода при разработке продуктов DevExpress. Из статьи станут понятны мотивы и причины, побудившие к использованию этого алгоритма. В конце я приведу наш вариант реализации алгоритма для сортировки зависимых объектов.

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

Сформулируем определения и задачу.
Графом будем называть несколько точек (вершин), некоторые пары которых соединены отрезками (рёбрами). Граф связный, если от каждой вершины можно дойти до любой другой по этим отрезкам. Циклом назовём какой-то путь по рёбрам графа, начинающегося и заканчивающегося в одной и той же вершине. И ещё граф называется взвешенным, если каждому ребру соответствует какое-то число (вес). Не может быть двух рёбер, соединяющих одни и те же вершины.
Каждый из алгоритмов будет решать какую-то задачу о кратчайших путях на взвешенном связном. Кратчайший путь из одной вершины в другую — это такой путь по рёбрам, что сумма весов рёбер, по которым мы прошли будет минимальна.
Для ясности приведу пример такой задачи в реальной жизни. Пусть, в стране есть несколько городов и дорог, соединяющих эти города. При этом у каждой дороги есть длина. Вы хотите попасть из одного города в другой, проехав как можно меньший путь.

Доброго времени суток, уважаемое Хабрасообщество.

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

Я хочу рассказать вам основы теории Игр, доказать функцию Шпрага-Гранди, разобрать несколько классических impartial-задач и проиллюстрировать их кодом на python.

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

Листая на Хабре раздел Python наткнулся на интересную статью о библиотеке NetworkX. Впечатлившись красивыми графами, решил повысить свой python-скилл и покопаться в networkx.

Пролог

Первый вопрос — откуда взять данные для визуализации? Генерировать случайные не интересно, они и в комплекте модуля были. Тут вспомнилась Dos утилитка tree, выводящая каталоги файловой системы в виде дерева. Решено было написать красивый аналог на Python и нарисовать все в networkx с помощью matplotlib.

Исследователи из Мадридского университета имени Карлоса III (Universidad Carlos III de Madrid, UC3M) разработали алгоритм, основанный на поведении муравьёв при поиске еды. Данный алгоритм, как утверждают авторы, ускоряет поиск связей между элементами социальных сетей.

Если вам интересно, какие знания можно извлечь из большого массива данных, насколько большими бывают графы и какие задачи по анализу социальных графов предлагают Facebook, Twitter и др., то эта статья именно для вас.

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

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

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

UPD: Добавил сравнение производительности

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

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

В предыдущем посте рассказывалось об обходе графа в глубину. Сегодня я бы хотел рассказать о не менее важном алгоритме теории графов — об обходе в ширину.
В прошлый раз мы уже научились искать какой-нибудь путь сквозь лабиринт. Всех желающих найти кратчайший путь прошу под кат.