pure-graph (WIP)
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.
;;; const empty = gEMPTY_GRAPH; // initialize an empty graph const testGraph = _empty; // assertions ;; ;assert; ;assert; // removal assert; assert; assert; // data access assert; assert;assert;assert; assert; // error handling try g; catch e assert; console;
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: getEdgeWithId
throws 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 = EMPTY_GRAPH; console; /* { "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; /* { "nodes": { "0": true, "1": true, "2": true }, "edges": { "2-1": { "f": "2", "t": "1" }, "0-1": { "f": "0", "t": "1" } } } */