Существуют ли библиотеки JavaScript для операций и алгоритмов графа?
Мне нужна реализация JavaScript математических математических графиков. Чтобы быть ясным, я НЕ имею в виду библиотеки визуализации графа, такие как sigma.js или d3.js.
В библиотеке, которую я ищу, будут реализованы следующие функции:
- создание направленных и неориентированных объектов графа
- создание взвешенных и невзвешенных грасс-объектов
- добавление/удаление вершин и ребер в/из графика
- добавление меток к вершинам и ребрам (т.е. дополнительные метаданные)
- реализация основных алгоритмов поиска графа и обхода, таких как поиск по глубине в первый раз, поиск в ширину, Dijkstra algorithm, A * и другие.
Кто-нибудь знает, если он уже существует?
Ответы
Ответ 1
Теперь есть библиотека: graphlib
Graphlib - это библиотека JavaScript, которая предоставляет структуры данных для неориентированных и направленных многографов вместе с алгоритмами, которые могут быть использованы с ними.
Реализует:
- направленные и неориентированные графы (значит, A → B означает B → A)
- мультиграфы (несколько различных именованных ребер из A → B)
- составные графики (узлы могут иметь дочерние элементы, которые образуют "подграф" )
- Алгоритм Дейкстры (кратчайший путь)
- Алгоритм Флойда-Варшалла (самый короткий путь, поддерживающий отрицательные веса)
- Алгоритм Prim (минимальное остовное дерево)
- Таржанский алгоритм (сильно связанные компоненты)
- Топологическая сортировка (сортировка зависимостей для ориентированных ациклических графов)
- Предпросмотр и послепорядок (обратный вызов для каждого node)
- Поиск всех циклов и тестирование, если граф ацикличен
- Поиск всех подключенных компонентов
Поддержка NPM, Bower и браузера, лицензия MIT.
Ответ 2
До нескольких месяцев я создал репозиторий с реализацией различных алгоритмов CS в JavaScript. Существует также несколько алгоритмов с графиками. Я планирую расширить его (охватывая деревья, эвристические алгоритмы, вероятно, хроматические графы), но с тех пор я думаю, что есть еще несколько алгоритмов, которые могли бы вам помочь.
Ответ 3
С помощью рекомендаций StackOverflow аналогичные вопросы я нашел пару вопросов с аналогичной темой.
Первая, Javascript направлена на ациклическую библиотеку графа? (Графическая визуализация НЕ необходима), близок. Там nrabinowitz предлагает проверить data.js. Я быстро просмотрел источник данных .js. Это действительно дает интерфейс для обработки графиков, но только в очень простой форме. Нет алгоритмов обхода. Также кажется, что цель data.js - это нечто иное, чем всеобъемлющая библиотека графов.
Вторая, Javascript-библиотека для операций с графами, почти такой же вопрос, как и у этого, но пока нет реальных ответов (в 2013-01-23 17:32). Автор c0dem4gnetic ссылается на NetworkX, что очень важно, что я но, к сожалению, реализована только в Python.
Я был бы взволнован, чтобы реализовать такую библиотеку самостоятельно. Графы настолько классные.
Ответ 4
Я создал библиотеку алгоритмов графа https://github.com/devenbhooshan/graph.js в javascript. Библиотека чистая и очень простая. Он очень прост в использовании. Просто вставьте файл graph.js в свой проект и начните его использовать.
Ответ 5
У нас есть algos в нашей Java-библиотеке, мы просто пытаемся найти свободный слот, чтобы добавить их в наш библиотека JavaScript. Это не поможет вам сейчас, но может быть полезно для более поздних зрителей.