是否有用于图形操作和算法的JavaScript库？ [英] Is there any JavaScript libraries for graph operations and algorithms?

问题描述

我需要的是纯数学图的JavaScript实现。要明确我不是指像 sigma.js 或

我正在寻找的库将实现以下功能：

创建有向图和无向图对象
创建加权和未加权的图元对象

添加/删除顶点和边/来自图

向顶点和边添加标签（即附加元数据）

实现基本图搜索和遍历算法深度优先搜索，广度优先搜索， Dijkstra算法，A* 和其他。

有人知道一个是否已经存在吗？

解决方案

现在有一个库： graphlib

Graphlib是一个JavaScript库，为无向和有向多图提供数据结构以及可与它们一起使用的算法。

实现：

• 有向图和无向图（A - > B意味着B - > A）
  
• 多图（多个不同的命名边，从A - > B）
  
• 复合图（节点可以有孩子形成
  
• Dijkstra算法（最短路径）


• Floyd-Warshall算法（支持负权重的最短路径）
  
• Prim算法（最小生成树）


• Tarjan算法（强连通组件）
  
• 拓扑排序
  
• 前后遍历（每个节点回调）
  
• 查找所有循环并测试图是否是非循环的


• 查找所有连接的组件

支持NPM，Bower和浏览器， p>

What I need is a JavaScript implementation of pure mathematical graphs. To be clear I DON'T mean graph visualization libraries like sigma.js or d3.js.

The library I'm looking for would implement following features:

• creation of directed and undirected graph objects
• creation of weighted and unweighted graps objects
• adding/removing vertices and edges to/from the graph
• adding labels to vertices and edges (i.e. additional meta data)
• implementation of basic graph search and traversal algorithms like depth-first-search, breadth-first search, Dijkstra's algorithm, A* and others.

Does anyone know if one already exists?

解决方案

Now there is a library: graphlib

Graphlib is a JavaScript library that provides data structures for undirected and directed multi-graphs along with algorithms that can be used with them.

Implements:

• directed and undirected graphs (does A -> B imply B -> A)
• multigraphs (multiple distinct named edges from A -> B)
• compound graphs (nodes can have children that form a "subgraph")
• Dijkstra algorithm (shortest path)
• Floyd-Warshall algorithm (shortest path supporting negative weights)
• Prim's algorithm (minimum spanning tree)
• Tarjan's algorithm (strongly connected components)
• Topological sorting (dependency sort for directed acyclic graphs)
• Pre- and postorder traversal (callback on every node)
• Finding all cycles and testing if a graph is acyclic
• Finding all connected components

NPM, Bower and browser supported, MIT license.

这篇关于是否有用于图形操作和算法的JavaScript库？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！