pure-graph

    3.1.3 • Public • Published

    pure-graph (WIP)

    Build Status Coverage Status npm package

    Simple library for working with directed graphs, built using a functional approach. (Work in progress)

    Motivation

    The approach used in this library is to store the graph data as plain JS objects, and only use the provided pure functions to manipulate it. In this way, testing for the equality of two graphs, sending and receiving them through the wire, and composing their transformations (by just using a composition of functions) is conceptually simple and straightforward.

    Example

    note: the published code is compiled to ES5, so using ES6 is not obligatory.

    import g from 'pure-graph';
    import _ from 'ramda';
    import assert from 'assert';
     
     
    const empty = g.EMPTY_GRAPH;        // initialize an empty graph
      
    const testGraph = _.compose(        // add nodes with '0' and '1' id's, and an edge between them
      g.addEdge('0-1', '0', '1'),       // (composed functions are applied from the last to the first)
      g.addNode('1'),
      g.addNode('0')
    )(empty);
     
     
    // assertions
     
    assert(g.hasNode('0', testGraph), `has a node with id '0'`);
    assert(g.hasNode('1', testGraph), `has a node with id '1'`);
     
    assert(g.hasEdgesFromTo('0', '1', testGraph), `has an edge from '0' to '1'`);
    assert.equal(g.hasEdgesFromTo('0', '2', testGraph), false, `doesn't have an edge from '0' to '2'`);
     
    assert(g.hasEdgeWithId('0-1', testGraph), `has an edge with id '0-1'`);
    assert.equal(g.hasEdgeWithId('0-2', testGraph), false, `doesn't have an edge with id '0-2'`);
     
     
    // removal
     
    assert.equal(
      _.compose(
        g.hasEdgesFromTo('0', '1'),
        g.removeEdgeWithId('0-1')
      )(testGraph), false, 'removes the edge between nodes'
    );
     
    assert.equal(
      _.compose(
        g.hasNode('0'),
        g.removeNode('0')
      )(testGraph), false, 'removes the node'
    );
     
    assert.equal(
      _.compose(
        g.hasEdgesFromTo('0', '1'),
        g.removeNode('0')
      )(testGraph), false, 'removes the edge after removing one of adjacent nodes'
    );
     
     
    // data access
     
    assert.deepEqual(g.getEdges(testGraph), [ {id: '0-1', from: '0', to: '1'} ], 'gets an edges array');
     
    assert.deepEqual(g.getEdgesFromNode('0', testGraph), [ {id: '0-1', from: '0', to: '1'} ], 'gets edges from the node');
    assert.deepEqual(g.getEdgesIncidentToNode('1', testGraph), [ {id: '0-1', from: '0', to: '1'} ], 'gets edges incident to the node');
    assert.deepEqual(g.getEdges(testGraph), [ {id: '0-1', from: '0', to: '1'} ], 'gets an edges array');
     
    assert.deepEqual(g.removeNode('0', testGraph), _.compose(
      g.addNode('1')
    )(empty), 'removes the node correctly');
     
     
    // error handling
     
    try {
      g.addEdge('10-20', '10', '20', testGraph);    
    } catch (e) {
      assert.equal(e.message, 'addEdge: nodes 10 and 20 do not exist');
    }
     
     
    console.log('all safe and sound!');
     
     
     

    Installing

    npm i pure-graph

    Development

    npm run build builds

    npm test builds the code and runs the tests on the code being published (/lib folder)

    npm run dev starts a files watching builder and test runner

    API

    note: all the functions are curried by default.

    Adding

    addNode : NodeId -> GraphData -> GraphData

    Adds a node with NodeId id.

    addEdge : EdgeId -> NodeId -> NodeId -> GraphData -> GraphData

    Adds an edge between nodes with the given id's. If one of the nodes has not been found, throws an error.

    Asserting

    hasNode : NodeId -> GraphData -> Boolean

    hasEdgesFromTo : NodeId -> NodeId -> GraphData -> Boolean

    hasEdgesBetween : NodeId -> NodeId -> GraphData -> Boolean

    hasEdgeWithId : EdgeId -> GraphData -> Boolean

    Retrieving

    getNodes: GraphData -> [ NodeId ]

    getNodesAdjacentTo : NodeId -> GraphData -> [ NodeId ]

    getNodesTo : NodeId -> GraphData -> [ NodeId ]

    getNodesFrom : NodeId -> GraphData -> [ NodeId ]

    getEdges : GraphData -> [ {id: EdgeId, from: NodeId, to: NodeId} ]

    getEdgeWithId : EdgeId -> GraphData -> {id: EdgeId, from: NodeId, to: NodeId}

    note: getEdgeWithIdthrows an error if the edge has not been found.

    getEdgesFromTo : NodeId -> NodeId -> GraphData -> [ {id: EdgeId, from: NodeId, to: NodeId} ]

    getEdgesBetween : NodeId -> NodeId -> GraphData -> [ {id: EdgeId, from: NodeId, to: NodeId} ]

    getEdgesFromNode: NodeId -> GraphData -> [ {id: EdgeId, from: NodeId, to: NodeId} ]

    Gets the edges incident to the node with the given id, directed from the node.

    getEdgesToNode: NodeId -> GraphData -> [ {id: EdgeId, from: NodeId, to: NodeId} ]

    Gets the edges incident to the node with the given id, directed towards the node.

    getEdgesIncidentToNode: NodeId -> GraphData -> [ {id: EdgeId, from: NodeId, to: NodeId} ]

    Gets all of the edges incident to the node with the given id.

    Removing

    removeNode : NodeId -> GraphData -> GraphData

    Removes a node with NodeId id and all of the incident edges from the graph. Returns an unmodified graph if the node hasn't been found.

    removeEdgeWithId : EdgeId -> GraphData -> GraphData

    Removes the edge with the given id.

    removeEdgesFromTo : NodeId -> NodeId -> GraphData -> GraphData

    removeEdgesBetween : NodeId -> NodeId -> GraphData -> GraphData

    removeEdgesToNode : NodeId -> GraphData -> GraphData

    removeEdgesFromNode : NodeId -> GraphData -> GraphData

    removeEdgesIncidentToNode : NodeId -> GraphData -> GraphData

    Utils

    EMPTY_GRAPH: GraphData

    An empty graph constant.

    Conversion

    For cases when it is important to efficiently store and send the graph data, the library provides a utility to convert the graph to the incidence form, removing data duplication.

    convertToIncidentForm: GraphData -> IncidentGraphData

    convertFromIncidentForm: IncidentGraphData -> GraphData

    example:

      const graph = compose(
        addEdge('0-1', '0', '1'),
        addEdge('2-1', '2', '1'),
        addNode('2'),
        addNode('1'),
        addNode('0') 
      )(EMPTY_GRAPH);
     
      console.log(JSON.stringify(graph, null, '  '));
     
      /*
        {
          "nodes": {
            "0": { "id": "0", "edgesFrom": { "0-1": true }, "edgesTo": {} },
            "1": { "id": "1", "edgesFrom": {},              "edgesTo": { "2-1": true, "0-1": true } },
            "2": { "id": "2", "edgesFrom": { "2-1": true }, "edgesTo": {} }
          },
          "edges": {
            "2-1": { "id": "2-1", "from": "2", "to": "1" },
            "0-1": { "id": "0-1", "from": "0", "to": "1" }
          }
        }
      */
     
     
      console.log(JSON.stringify(g.convertToIncidentForm(graph), null, '  '));
     
      /*
        {
          "nodes": { "0": true, "1": true, "2": true },
          "edges": {
            "2-1": { "f": "2", "t": "1" },
            "0-1": { "f": "0", "t": "1" }
          }
        }
      */
     
     

    Install

    npm i pure-graph

    DownloadsWeekly Downloads

    2

    Version

    3.1.3

    License

    ISC

    Last publish

    Collaborators

    • naissur