нужна библиотека гамильтоновых графов

[Vizard]

Здравствуйте.

Я ищу какую-нибудь библиотеку (коллекцию) гамильтоновых графов. Нужно для тестирования программы нахождения циклов. Вообще говоря, нужны произвольные графы, для которых известны г. циклы или их отсутствие. Можете что-то подсказать?

[Maslov]

Насчет готовых библиотек гамильтоновых графов не знаю, но их довольно просто в любом количестве автоматически нагенерить: берете простой цикл заданной длины -- получаете простейший гамильтонов граф; затем добавляете в него произвольное количество ребер -- вот Вам и нетривиальный пример :)

Что касается негамильтоновых графов, то можно, например, у WolframAlpha спросить: http://www.wolframalpha.com/input/?i=no ... nian+graph

[Zealint]

Никогда таких библиотек не видел. Но когда сам тестирую программы на графах, люблю использовать графы шахматных фигур, они простые и в зависимости от выбора шахматной фигуры можно получить как плотный граф (ферзь, ладья), так и неплотный (король, конь). Кроме того, для шахматной доски известны решения многих задач - поэтому есть с чем сравнить. Например, число всех простых циклов от 3 до гамильтоновых для некоторых таких небольших графов можно найти здесь. Там на 99% всё правильно, но чем чёрт не шутит...

Вы считаете только число циклов, или перечисляете их всех по одному?

[Vizard]

Maslov в сообщении #501660 писал(а):

Насчет готовых библиотек гамильтоновых графов не знаю, но их довольно просто в любом количестве автоматически нагенерить: берете простой цикл заданной длины -- получаете простейший гамильтонов граф; затем добавляете в него произвольное количество ребер -- вот Вам и нетривиальный пример :)

Что касается негамильтоновых графов, то можно, например, у WolframAlpha спросить: http://www.wolframalpha.com/input/?i=no ... nian+graph

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

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

-- 10.11.2011, 17:49 --

Zealint в сообщении #501953 писал(а):

Никогда таких библиотек не видел. Но когда сам тестирую программы на графах, люблю использовать графы шахматных фигур, они простые и в зависимости от выбора шахматной фигуры можно получить как плотный граф (ферзь, ладья), так и неплотный (король, конь). Кроме того, для шахматной доски известны решения многих задач - поэтому есть с чем сравнить. Например, число всех простых циклов от 3 до гамильтоновых для некоторых таких небольших графов можно найти здесь. Там на 99% всё правильно, но чем чёрт не шутит...

Вы считаете только число циклов, или перечисляете их всех по одному?

Спасибо за сайт, погляжу.

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

[Zealint]

Цитата:

А можно считать циклы, не перечисляя их, или имеется в виду их сохранение?

Можно, если Ваша цель - назвать их количество, а не вывести их по одному.
Например, на решётке размером $16\times16$ их количество равно 65882516522625836326159786165530572, ясно, что их не по одному перечисляли, а каким-то другим методом.

Цитата:

Вообще, цель - наиболее оптимальным образом найти все г.циклы в произвольном графе и вывести. Меня особенно интересуют большие графы.

Попробуйте подробнее описать. Вам нужно именно вывести каждый цикл? А что такое "большие графы"? Например, в полном графе порядком больше 14 вы вряд ли их сможете вывести все. А в некоторых графах циклы вообще не нужно искать полным перебором. Например, в графе $C_n$, который состоит лишь из одного гамильтонового цикла, можно сразу вывести ответ, особо не считая.

[Vizard]

Zealint в сообщении #502139 писал(а):

Цитата:

А можно считать циклы, не перечисляя их, или имеется в виду их сохранение?

Можно, если Ваша цель - назвать их количество, а не вывести их по одному.
Например, на решётке размером $16\times16$ их количество равно 65882516522625836326159786165530572, ясно, что их не по одному перечисляли, а каким-то другим методом.

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

Цитата:

Цитата:

Вообще, цель - наиболее оптимальным образом найти все г.циклы в произвольном графе и вывести. Меня особенно интересуют большие графы.

Попробуйте подробнее описать. Вам нужно именно вывести каждый цикл? А что такое "большие графы"? Например, в полном графе порядком больше 14 вы вряд ли их сможете вывести все. А в некоторых графах циклы вообще не нужно искать полным перебором. Например, в графе $C_n$, который состоит лишь из одного гамильтонового цикла, можно сразу вывести ответ, особо не считая.

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

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

Дело в том, что программа не может знать, граф какого типа она получает, даже если это $C_n$ - это все равно, что очень удачный перебор. Или нет?

Хм, а абсолютно удачный перебор - это забавно :)

[Zealint]

Vizard в сообщении #502483 писал(а):

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

Да, ошибаетесь. Я Вас уверяю, что для решётки размером $n\times n$ не существует никакой формулы. Более того, скорее всего она в принципе не может быть записана средствами имеющегося на сегодня математического аппарата так, чтобы по ней можно было что-то посчитать. Указанное мной число циклов вычислялось методом динамического программирования. А число циклов, например, в ферзевом графе размером $5\times5$, которое равно 39741746126749664, тоже вычислялось таким методом, но по немного иначе. Формулы там тоже нет. У меня по этой теме даже конкурс был, а в итогах я приводил такой алгоритм.

Цитата:

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

Ну ясно. Тогда вряд ли чем-то ещё помогу.

Цитата:

Дело в том, что программа не может знать, граф какого типа она получает, даже если это $C_n$ - это все равно, что очень удачный перебор. Или нет?

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

А по теме, нет, никаких больше идей у меня для Вас нет.

[Vizard]

Zealint в сообщении #502509 писал(а):

Vizard в сообщении #502483 писал(а):

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

Да, ошибаетесь. Я Вас уверяю, что для решётки размером $n\times n$ не существует никакой формулы. Более того, скорее всего она в принципе не может быть записана средствами имеющегося на сегодня математического аппарата так, чтобы по ней можно было что-то посчитать. Указанное мной число циклов вычислялось методом динамического программирования. А число циклов, например, в ферзевом графе размером $5\times5$, которое равно 39741746126749664, тоже вычислялось таким методом, но по немного иначе. Формулы там тоже нет. У меня по этой теме даже конкурс был, а в итогах я приводил такой алгоритм.

Понятно, интересная статья. Вопрос из любопытства: а почему Вы так считаете (что не существует формулы для числа циклов в решетке)?

Цитата:

Цитата:

Дело в том, что программа не может знать, граф какого типа она получает, даже если это $C_n$ - это все равно, что очень удачный перебор. Или нет?

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

Целей нет, есть только личный интерес пока. Позвольте спросить, почему умерло - само собой застопорилось или были какие-то конкретные результаты, которые поставили на этом крест?

Цитата:

А по теме, нет, никаких больше идей у меня для Вас нет.

В любом случае, спасибо за ответы - они помогают определиться.

Еще один вопрос из любопытства: Вы не использовали какие-то статистические методы в такого рода задачах или может быть слышали о каких-то результатах?

[Zealint]

Vizard в сообщении #502899 писал(а):

Понятно, интересная статья. Вопрос из любопытства: а почему Вы так считаете (что не существует формулы для числа циклов в решетке)?

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

Цитата:

Целей нет, есть только личный интерес пока. Позвольте спросить, почему умерло - само собой застопорилось или были какие-то конкретные результаты, которые поставили на этом крест?

Крест ставят не результаты, а то обстоятельство, что данное направление началось в 60-х годах и закончилось в конце 70-х, когда стало понятно, что заниматься перечислением циклов в произвольных графах нет никакого (научного) смысла. Всё, что за эти 20 лет можно было сделать, уже сделали. Развивать это направление дальше можно только с учётом специфики решаемой задачи. А произвольные графы - это теперь упражнения из задачника для студентов, они с точки зрения науки по сути никому больше не нужны.

Цитата:

Еще один вопрос из любопытства: Вы не использовали какие-то статистические методы в такого рода задачах или может быть слышали о каких-то результатах?

Слышал про статистические методы. Ни в одной серьёзной задаче ни один из них (что я слышал) не работает. Слышал также про то, что в некоторых чудовищно больших графах статистические методы дают неплохие решения, если циклы не слишком длинные (например, длиной 3, когда их легко пересчитать со сложностью умножения матриц, но при таких размерах это невыгодно). Короче, каждый из статистических методов нужно затачивать под конкретный класс задач. Универсальные можно сразу выбросить (ИМХО). Больше ничего сказать не могу.

[Vizard]

Кое-что нашел, спасибо вики :)

http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/

[Zealint]

Vizard в сообщении #506189 писал(а):

Кое-что нашел, спасибо вики :)

http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/

Только что-то там не очень понятно, в каких графах из предложенного списка есть гамильтоновы циклы, а в какие - нет. Формат ввода как-то тоже не очевиден. Вам удалось разобраться? Пригодилось вообще что-нибудь оттуда?

[Vizard]

Там есть описание, правда в формате постскрипта, вот есть описание в пдф:
http://www.cs.bris.ac.uk/Teaching/Resou ... rk/doc.pdf

Что касается HCP: есть файл данных (можно открыть в текстовом редакторе, упаковано гзипом, я открывал в винраре нормально), затем с тем же названием цикл (с добавкой tour)

Выглядит все хорошо, как я хотел, так что буду использовать :)

[Vizard]

вот нашел еще хороший ресурс
http://www2.research.att.com/~dsj/chtsp/index.html