Существуют ли библиотеки 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. Это не поможет вам сейчас, но может быть полезно для более поздних зрителей.