Хабр Курсы для всех
РЕКЛАМА
Большая витрина: от крупнейших школ до частных авторов. Сравнивайте по цене, длительности, формату и выбирайте самый подходящий курс!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 19
Тема глубока что омут, в своё время интересовался, даже приобрёл у букиниста «Перечисления графов» Ф. Харари. Произвольный граф, с мудрёной группой автоморфизмов фиг упорядочишь, но, насколько я понимаю, для практики типа индексирования химических формул такое не нужно совсем, графы в математике и в приложениях совсем разные вещи.
Граф — он везде граф, а химия тут просто как пример, тысячи их — мест приложения для всего этого.
Ну вот вы претендуете на то, что разрабатываете общее решение, но применяли ли вы его к конкретной задаче, с внедрением как?
да нет, это — частное решение математической задачи, которая (задача) имеет разные применения.
а тема, да, большая.
а тема, да, большая.
Здравствуйте.
Вот дошли руки выложить примеры.
Итак
1. О проверке изоморфности 2 графов (ориентированных и неориентированных).
Примеры графов (сгенерированы случайно) и время работы тут:
github.com/chernouhov/CBioInfCpp-0-/tree/master/TestsGraphIsomorphismInfo
Да, работать могло бы и быстрее (хотя уже можно пользоваться), тут проблема, скорее в программной реализации.
Также подчеркну, что время работы сильно зависит от самого графа. Если он — одна цепь — одно, а если это — снежинка и много лучиков длиной по 1 ребру — другое.
2. О поиске в графе А подграфов, изоморфных графу В.
Находит не все (свойство метода), но многие.
Тут пример: github.com/chernouhov/CBioInfCpp-0-/tree/master/TestsIsomorphicSubGraphsFinding
Графы рассматриваются и как ориентированные (выдает 36 подграфов А, изоморфных графу В) и неориентированные (находит 216 штук).
Вот дошли руки выложить примеры.
Итак
1. О проверке изоморфности 2 графов (ориентированных и неориентированных).
Примеры графов (сгенерированы случайно) и время работы тут:
github.com/chernouhov/CBioInfCpp-0-/tree/master/TestsGraphIsomorphismInfo
Да, работать могло бы и быстрее (хотя уже можно пользоваться), тут проблема, скорее в программной реализации.
Также подчеркну, что время работы сильно зависит от самого графа. Если он — одна цепь — одно, а если это — снежинка и много лучиков длиной по 1 ребру — другое.
2. О поиске в графе А подграфов, изоморфных графу В.
Находит не все (свойство метода), но многие.
Тут пример: github.com/chernouhov/CBioInfCpp-0-/tree/master/TestsIsomorphicSubGraphsFinding
Графы рассматриваются и как ориентированные (выдает 36 подграфов А, изоморфных графу В) и неориентированные (находит 216 штук).
Я не видел лучшей псевдонаучной статьи. Вы хотя бы честно попытались разработать алгоритм и даже написали код, за что респект. Вижу, что алгоритм реализован в вашей библиотеке CBioInfCpp. Но для таких библиотек есть стандарт качества — стресс-тесты. Попробуйте сделать следующее: напишите простой генератор графов, который генерит (1..n) вершин и случайно раскидывает между ними ребра. Поиграйтесь с параметрами, чтобы можно было генерить и пустые графы, и плотные, и деревья. Подключите существующую библиотеку для поиска изоморфизма. После этого 10 000 раз сгенерируйте случайный граф, его копию с переставленными вершинами и сравните результаты работы своей библиотеки и существующей. Иначе как мы можем верить, что алгоритм и код работают?
Хорошей идей было бы провести анализ сложности вашего алгоритма или хотя бы замерить работу и сравнить ее с временем работы настоящей библиотеки.
Ну и уверен, статья была бы намного понятней, если бы вы написали определение максимально протяженного неразветвляющегося пути, потому что я никогда не видел определения «разветвляющегося пути»
Хорошей идей было бы провести анализ сложности вашего алгоритма или хотя бы замерить работу и сравнить ее с временем работы настоящей библиотеки.
Ну и уверен, статья была бы намного понятней, если бы вы написали определение максимально протяженного неразветвляющегося пути, потому что я никогда не видел определения «разветвляющегося пути»
Проверялось. Ясно-понятно, гонялось на разных датасетах. Сюда их наверно цеплять не нужно. Скорость поиска очень ситуативна и зависит от конфигурации каждого из графов. И от «уникальности», непохожести разных ребер в графе по разных критериям. Некоторые случаи ищет очень быстро, другие приводят к «полету в космос».
На какое-то сверхоткрытие тут и нет претензий (вижу, это надо подчеркнуть особо).
Псевдо-не псевдо, но в тексте честно говорится о путях применения — в первую очередь, в качестве экспресс-тестов ограниченного времени (кое-что может найти быстро, как сказано ранее). И также при проработке и других алгоритмов — с т.зр. проверки условий раннего отсечения неподходящих, например.
Про "… пути" — вообще термин введен не мной, но он более англоязычный. Так уж сложилось, к сожалению. По термину «maximal non-branching path» — см., например, следующее ссылки:
dodona.ugent.be/nl/exercises/746374412
rosalind.info/problems/ba3m
mathoverflow.net/questions/135488/terminology-question-maximal-non-branching-directed-paths
arxiv.org/pdf/1602.05856.pdf
www.cnblogs.com/YBWS/p/4609117.html (раздел Splitting the genome into contigs)
Надеюсь, эти источники более авторитетны.
На какое-то сверхоткрытие тут и нет претензий (вижу, это надо подчеркнуть особо).
Псевдо-не псевдо, но в тексте честно говорится о путях применения — в первую очередь, в качестве экспресс-тестов ограниченного времени (кое-что может найти быстро, как сказано ранее). И также при проработке и других алгоритмов — с т.зр. проверки условий раннего отсечения неподходящих, например.
Про "… пути" — вообще термин введен не мной, но он более англоязычный. Так уж сложилось, к сожалению. По термину «maximal non-branching path» — см., например, следующее ссылки:
dodona.ugent.be/nl/exercises/746374412
rosalind.info/problems/ba3m
mathoverflow.net/questions/135488/terminology-question-maximal-non-branching-directed-paths
arxiv.org/pdf/1602.05856.pdf
www.cnblogs.com/YBWS/p/4609117.html (раздел Splitting the genome into contigs)
Надеюсь, эти источники более авторитетны.
Кстати, если у кого-то есть интересные датасеты: проверить изоморфизм, либо поискать в большом графе изоморфные некоторому образцу подграфы — присылайте (графы мы понимаем в виде списка ребер), прогоним через библиотеку.
Здравствуйте. Удалось адаптировать метод для поиска любых (а не только вписанных) подграфов в графе по образцу. Для этого вместо non-branching paths (нет короткого аналога термина по русски) были взяты ребра графов.
При текущей реализации работает очень долго для графов с простой структурой, но со сложной (например, содержит кольцо с одним из ребер кратности 3, или еще какие-то «усложнения») приемлемо. И с т.зр. скорости применимо более для орграфов, нежели для неориентированных.
Тут результаты опытов 5.12.2020:
github.com/chernouhov/CBioInfCpp-0-/tree/master/TestsIsomorphicSubGraphsFinding
Для орграфов например нашел аж 82546 совпадений с образцом размера (25 вершин-35 ребер) в графе размером (2500-3500) менее чем за 2 мин.
При текущей реализации работает очень долго для графов с простой структурой, но со сложной (например, содержит кольцо с одним из ребер кратности 3, или еще какие-то «усложнения») приемлемо. И с т.зр. скорости применимо более для орграфов, нежели для неориентированных.
Тут результаты опытов 5.12.2020:
github.com/chernouhov/CBioInfCpp-0-/tree/master/TestsIsomorphicSubGraphsFinding
Для орграфов например нашел аж 82546 совпадений с образцом размера (25 вершин-35 ребер) в графе размером (2500-3500) менее чем за 2 мин.
Спасибо!
Работаю над хим. приложениями графов (и не только химическим) не один десяток лет — про представления графов писал здесь на Хабре ранее. В статье предложено еще одно возможное представление — «NB-Paths». Ok.
У статьи две части: 1) задача изоморфизма и 2) поиск подграфов. Я буду говорить только об (1), т.к. пока (1) не доказана, про (2) говорить преждевременно.
М.б. мне показалось, что автор сделал аккуратный намек на решение задачи изоморфизма за полиномиальное время от числа вершин? — Возникает такое впечатление. Но где строгие определения, теоремы и доказательства? — Я не про данную статью — на Хабре допустим популярный стиль, я про препринт, упомянутый в статье. Интересно, что в статье сказано:
А в препринте:
Определение. NB-путями (maximal non-branching paths) мы будем называть последовательности максимально протяженных неразветвляющихся путей.
Далее:
Теорема (или Лемма). Если два графа изоморфны друг другу, то для любого
представления первого графа в виде NB-путей всегда существует соответствующее ему такое же представление второго графа.
Доказательство. [...] Что и требовалось доказать.
Далее нужно привести алгоритм поиска NB-путей в графе на псевдокоде. Читатель может не знать языка Х, который в реализации, и не должен разбираться с полным текстом программы. Оценку теоретического времени исполнения по псевдокоду вести легче. Приведите эту оценку для наихудшего случая. На этом ИМХО можно закончить. Но в сетке есть прекрасные БД «патологических графов», забраковавших многие предложенные решения задачи изоморфизма. Я постараюсь найти в своих архивах ссылки.
Если данный алгоритм справится с этими БД — это будет явным достижением, которое нужно отметить. Думаю, что препринт нужно направить в arXiv.org.
Сказанное выше не мои придирки, а многолетние впечатления от изданий типа J of Graph Theory.
Работаю над хим. приложениями графов (и не только химическим) не один десяток лет — про представления графов писал здесь на Хабре ранее. В статье предложено еще одно возможное представление — «NB-Paths». Ok.
У статьи две части: 1) задача изоморфизма и 2) поиск подграфов. Я буду говорить только об (1), т.к. пока (1) не доказана, про (2) говорить преждевременно.
М.б. мне показалось, что автор сделал аккуратный намек на решение задачи изоморфизма за полиномиальное время от числа вершин? — Возникает такое впечатление. Но где строгие определения, теоремы и доказательства? — Я не про данную статью — на Хабре допустим популярный стиль, я про препринт, упомянутый в статье. Интересно, что в статье сказано:
NB-путями (и не из англомании, а просто потому, что так – короче) мы будем называть maximal non-branching paths, т.е. максимально протяженные неразветвляющиеся пути некоторого графа.
А в препринте:
Последовательности максимально протяженных неразветвляющихся путей(maximal non-branching paths)Ну так зачем наводить тень на плетень. Напишите в препринте:
Определение. NB-путями (maximal non-branching paths) мы будем называть последовательности максимально протяженных неразветвляющихся путей.
Далее:
Теорема (или Лемма). Если два графа изоморфны друг другу, то для любого
представления первого графа в виде NB-путей всегда существует соответствующее ему такое же представление второго графа.
Доказательство. [...] Что и требовалось доказать.
Далее нужно привести алгоритм поиска NB-путей в графе на псевдокоде. Читатель может не знать языка Х, который в реализации, и не должен разбираться с полным текстом программы. Оценку теоретического времени исполнения по псевдокоду вести легче. Приведите эту оценку для наихудшего случая. На этом ИМХО можно закончить. Но в сетке есть прекрасные БД «патологических графов», забраковавших многие предложенные решения задачи изоморфизма. Я постараюсь найти в своих архивах ссылки.
Если данный алгоритм справится с этими БД — это будет явным достижением, которое нужно отметить. Думаю, что препринт нужно направить в arXiv.org.
Сказанное выше не мои придирки, а многолетние впечатления от изданий типа J of Graph Theory.
PS В препринте оговорка:
Означает ли это, что не всякий изоморфизм будет найден?
Применение данного подхода для поиска подграфов графа A, изоморфных
некоторому графу B, сможет находить лишь «вписанные» подграфы.
Означает ли это, что не всякий изоморфизм будет найден?
Уже нет. Теперь — с декабря 2020 — ищет все подграфы, изоморфные заданному образцу.
Работает как по графам без пометок вершин, так и по графам с помеченными вершинами (поиск по образцу с пометками вершин в графе с пометками вершин).
Скорость очень зависит от входных данных, разброс очень большой. Так что нет, намека на полиноминальное время нет. В ряде случаев очень быстро, в ряде — напротив. Время здесь лучше оценивать статистически, а не граничной величиной, т.к. — в зависимости от исходных данных — от нее мы можем уйти как очень далеко в лучшую сторону, так и оказаться на ней же. Пока применяю с искусственным ограничением по времени: если нашел за некоторое t (что бывает быстро, а бывает и нет), то хорошо, нет — стоп-машина.
Практическое внедрение также уже имеется.
Также обращаю внимание, что это — подход. Он реализован, как смог. Однако предполагаю, что (1) можно реализовать лучше и (2) использовать отдельные элементы в других методах для сокращения пространства вариантов.
Работает как по графам без пометок вершин, так и по графам с помеченными вершинами (поиск по образцу с пометками вершин в графе с пометками вершин).
Скорость очень зависит от входных данных, разброс очень большой. Так что нет, намека на полиноминальное время нет. В ряде случаев очень быстро, в ряде — напротив. Время здесь лучше оценивать статистически, а не граничной величиной, т.к. — в зависимости от исходных данных — от нее мы можем уйти как очень далеко в лучшую сторону, так и оказаться на ней же. Пока применяю с искусственным ограничением по времени: если нашел за некоторое t (что бывает быстро, а бывает и нет), то хорошо, нет — стоп-машина.
Практическое внедрение также уже имеется.
Также обращаю внимание, что это — подход. Он реализован, как смог. Однако предполагаю, что (1) можно реализовать лучше и (2) использовать отдельные элементы в других методах для сокращения пространства вариантов.
Очень жаль!
Получается, что фактически Вы описали эвристический алгоритм, но не приводя сам алгоритм — он только, м.б., у Вас в голове. Непонятно, чем Ваш подход лучше знаменитого инструмента NAUTY, который сделал Brendan D. McKay? Напомню, что я обсуждаю только первую часть Вашей статьи — изоморфизм графов. При таком подходе этот подход останется на уровне препринтов, т.е. его никто из спецов не заметит и не оценит.
Получается, что фактически Вы описали эвристический алгоритм, но не приводя сам алгоритм — он только, м.б., у Вас в голове. Непонятно, чем Ваш подход лучше знаменитого инструмента NAUTY, который сделал Brendan D. McKay? Напомню, что я обсуждаю только первую часть Вашей статьи — изоморфизм графов. При таком подходе этот подход останется на уровне препринтов, т.е. его никто из спецов не заметит и не оценит.
Да нет, это неверно. Он не только есть (и приведен выше в популярной форме), но реализован в коде, а не «в голове», и ищет точно — именно все подграфы, изоморфные данному образцу. Даже примеры результатов такого поиска приведены. А задача проверки изоморфизма тут есть частный случай, что-то обсуждать по частям смысла нет. Другое дело, что время поиска очень сильно зависит от исходных данных (чем больше неоднородностей в графах, тем быстрее). Да и в заметке об этом все есть, как и по ряду других приведенных вопросов (например, ищет ли он все подграфы — см. раздел 8, и т.д.).
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Проверка изоморфности двух графов и поиск изоморфных подграфов: подход на основе анализа NB-Paths