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