Python-сообщество

Есть необходимость решать 2 задачи:
1) Находить на не взвешенном графе кратчайший путь, избегая заданных вершин, а если избежать их невозможно - с минимальным количеством таких вершин.
вершин около 7000, рёбер 14000

2) Находить кратчайший путь на графе между двумя точками, ребра которого имеют вес.
вершин 4000, а вот ребёр 2 миллиона

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

Далась вам эта серебрянная пуля…
Берите алгоритм Форда- и вперед

Отредактировано (Авг. 24, 2010 08:16:18)

Я использовал networkx. Впечатления положительные. Но если бы эта задача стояла передо мной, то я бы просто протестировал все возможное. В том числе и свою реализацию.

Еще народ хвалит igraph. Он должен по идее быть быстрее - написан на С.
Вот тут тред про сравнение networkx и igraph: http://groups.google.com/group/networkx-discuss/browse_frm/thread/7597ca97abbb3f90?hl=en

Попробовал networkx, библиотека очень хорошая и простая, много алгоритмов есть.
Только вот мой второй граф в памяти занимал 500мб.
Поэтому сделал сам, через словари. В памяти занимает 170мб. Но всё равно много - база из которой импортируются рёбра весит 40мб. Как можно уменьшить количество занимаемой памяти?

Отредактировано (Авг. 26, 2010 15:12:49)

igraph пробовали? Поскольку он на Си написан, то по идее хранить данные должен компактнее, чем Питон.
Покажите как Вы сделали через словари. Без кода очень трудно что-либо советовать.