Посты с тэгом графы


[Из песочницы] Стажировка аналитиком в Яндексе: разбор тестовых задач



Привет, Хабр!

Однажды, штудируя очередную книгу по пресловутой Data Science, я пришел к мысли, что пора бы применить накопленные знания на практике и увидеть жизнь отдела аналитики своими глазами. К моему счастью, Яндекс запустил отбор на полугодичную стажировку по соответствующему направлению, и я не мог пройти мимо. Приём заявок 2020 уже закончился, поэтому в этой статье я с чистой совестью разберу задачи, которые Яндекс предлагал решить соискателям на первом этапе. Будет и код на Python. Спойлер: сложно, но интересно.
Читать дальше →


[Из песочницы] Ключевые навыки Python-программиста

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

Я уже около двух лет программирую на Python, и сейчас наступил момент осознанно подойти к освоению новых навыков. Для этого я решил проанализировать вакансии и представить востребованные навыки в виде графа. Я ожидал увидеть, что навыки будут образовывать кластеры, соответствующие разным специальностям: backend разработке, data science и др. А как же обстоят дела на самом деле? Обо всём по порядку.
Читать дальше →



[Из песочницы] SciPy, алгоритмы на графах


SciPy (произносится как сай пай) — это пакет прикладных математических процедур, основанный на расширении Numpy Python. Он значительно расширяет возможности Python, предоставляя в распоряжение пользователя команды и классы высокого уровня для управления данными и их визуализацией. С SciPy интерактивный сеанс Python превращается в такую же полноценную среду обработки данных и прототипирования сложных систем, как MATLAB, IDL, Octave, R-Lab и SciLab.

Читать дальше →


Анализ дружеских связей VK с помощью Python. Продолжение


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


Пример использования WxPython для создания нодового интерфейса. Часть 2: Обработка событий мыши

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

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

Часть 1: Учимся рисовать

Кому интересно, добро пожаловать под кат…
Читать дальше →



Пример использования WxPython для создания нодового интерфейса. Часть 1: Учимся рисовать

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

А начиналось все так: понадобилось мне для одного проекта сделать UI, где надо последовательность обработки сообщений редактировать. Что-то наподобии Simulink'а. Соответственно, полез искать готовые либы/фреймворки. Поначалу подумал, что задачка популярная и кто-нибудь уже сделал это велосипед, поискал, поискал и… не нашел. Точнее нашел много антикварных велосипедов, но кто же будет пользоваться чужим старым велосипедом, если можно сделать свой новый. Но раз уж делать новый велосипед, почему бы не сделать его универсальным, мало ли, где еще пригодится.

Так что попробую в нескольких статья



Python / [Из песочницы] Визуализация каталогов на Python средствами NetworkX

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

Пролог


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


Топологическая сортировка


 

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

Существует несколько способов топологической сортировки — из наиболее известных:

  • Алгоритм Демукрона
  • Метод сортировки для представления графа в виде нескольких уровней
  • Метод топологической сортировки с помощью обхода в глубин


Топологическая сортировка



 

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


Бинарные деревья


Бинарное дерево представляет собой структуру, в которой каждый узел (или вершина) имеет не более двух узлов-потомков и в точности одного родителя. Самый верхний узел дерева является единственным узлом без родителей; он называется корневым узлом. Бинарное дерево
с N узлами имеет не меньше [log2N + 1] уровней (при максимально плотной упаковке узлов).
Если уровни дерева занумеровать, считая что корень лежит на уровне 1, то на уровне с номером К лежит 2К-1 узел. У полного бинарного дерева с j уровнями (занумерованными от 1 до j) все листья лежат на уровне с номером j, и у каждого узла на уровнях с первого по j — 1
в точности два непосредственных потомка. В полном бинарном дереве с j уровнями 2j — 1 узел.