Have ideas to improve npm?Join in the discussion! »

    @mlarocca/jsgraphs

    0.2.1 • Public • Published

    JsGraphs

    npm version Language grade: JavaScript Total alerts Follow

    A lightweight library to model graphs, run graphs algorithms, and display them on screen.

    You can use this library to create arbitrarily complex graphs and run algorithms and transformations on them, or just use it for visualization, importing graphs or even embeddings created in other languages/platforms and serialized using JSON.

    Graphs can be embedded in the plane, vertices can be positioned arbitrarily, and both vertices and edges can be styled individually.

    Getting Started

    Installation

    From the base folder:

    nvm install stable
     
    npm install

    Run tests

    From the base folder:

    npm t test/$FOLDER/$TEST

    For instance

    npm t test/geometric/test_point.js

    Bundle

    To bundle the library, I used Webpack - but you can use whatever you like.

    npm run bundle

    A word of caution, though: the combination of ECMAScript modules and advanced features (ES2019) makes configuration non-trivial.

    Check out how to configure babel plugins in webpack.config.js.

    Graph Theory

    For an introduction to Graph, feel free to take a look at "Algorithms and Data Structures in Action In particular you can check out online, on Manning's livebook site:

    • Chapter 14 for an intro to graph data structure.
    • Appendix B for an intro to Big-O notation.
    • Appendix C for a summary of core data structures like trees or linked lists.

    Tutorial

    A complete directed Graph

    To learn by example what you can do with JsGraphs and how to do it, check out this tutorial.

    Examples

    (click on the images to browse to the example)

    FSA DAG Complete GraphSame Complete Graph, with arc rather than segments Bipartite Complete Graph

    RoadMap

    Here we keep a list of the roadmap for the development of this library. If you have ideas or suggestions, feel free to open an issue (to suggest a feature or report a problem) or a Pull Request, to contribute to the development.

    Algorithms

    • BFS
    • DFS
    • Graph transpose
    • Symmetric closure
    • Connected Components
    • Strongly Connected Components
    • Topological Sorting
    • Biconnected Components
    • Dijkstra's
    • Bellman-Ford's
    • A*
    • Kruskal's
    • Prim's
    • Floyd-Warshall's
    • Transitive Closure
    • Edmonds-Karp's
    • Relabel to Front
    • Planarity Testing (naive)
    • Planarity Testing (linear-time)

    Features

    • Custom label/weights separator
    • Edge.setLabel
    • removeVertex()
    • removeEdge()
    • Add label and data fields for vertices
    • Add options to display/hide vertex name/label
    • Union of 2 disjoint graphs
    • DFS returns all cycles found

    Generators

    • Complete Graphs
    • Bipartite Complete Graphs
    • Square Mesh
    • Triangular Mesh
    • Random Graph

    License

    This library ships under GNU Affero General Public License

    Install

    npm i @mlarocca/jsgraphs

    DownloadsWeekly Downloads

    28

    Version

    0.2.1

    License

    SEE LICENSE IN https://github.com/mlarocca/jsgraphs/blob/master/LICENSE

    Unpacked Size

    1.76 MB

    Total Files

    86

    Last publish

    Collaborators

    • avatar