bearded-graph

#Bearded Graph

We've only just begun

This is a simple Graph data structure along with a Node data structure. This is for creating a bi-directional graph where nodes are connected individually and can have an associated weight which defaults to 1 if not given.

This package is written with flow types and uses ES6/7/8 stuff. You will need to transpile/compile it yourself to use along with stripping flow types. I use the babel package for testing and use the following .babelrc file, with node version being v7.4.0:

{
  "presets": [
    ["env",{
      "targets": {
        "node": "current"
      },
      "loose": true,
      "useBuiltIns": true
    }]
  ],
  "plugins": [
    "transform-flow-strip-types",
    "transform-object-rest-spread",
    "transform-class-properties"
  ]
}

The purpose of this package is to conform to the wikipedia definition of what a graph is, which is the following:

The basic operations provided by a graph data structure G usually include:[1]

adjacent(G, x, y): tests whether there is an edge from the vertices x to y;

neighbors(G, x): lists all vertices y such that there is an edge from the vertices x to y;

add_vertex(G, x): adds the vertex x, if it is not there;

remove_vertex(G, x): removes the vertex x, if it is there;

add_edge(G, x, y): adds the edge from the vertices x to y, if it is not there;

remove_edge(G, x, y): removes the edge from the vertices x to y, if it is there;

get_vertex_value(G, x): returns the value associated with the vertex x;

set_vertex_value(G, x, v): sets the value associated with the vertex x to v.

Structures that associate values to the edges usually also provide:[1]

get_edge_value(G, x, y): returns the value associated with the edge (x, y);

set_edge_value(G, x, y, v): sets the value associated with the edge (x, y) to v.

While the API is not an exact match, it should do all of the things that the above says a graph should be able to do. Below you will find the basic signature of each data type's method (Node and Graph) and below each of that a tad more detailed explanation of the method along with the data structures properties. You can also look at the flow signatures for a standard definition of the methods and types.

##Basic API Signature

###Node

method	arguments	return
addEdge	node: Node, weight: number	undefined
removeEdge	node: Node	undefined
updateEdge	node: Node, newWeight: number	undefined
connectedTo	node: Node	boolean
find	node: Node	Edge/undefined
weightTo	node: Node	number/undefined

###Node Details

A Node is a singleton of data inside of our graph. The Node data type is a class and must be called with new. A node has two properties:

data: The data that this node represents. This can be any type

edges: This is a list of Edge data types that have the signature of {node: Node, weight: Number}

A node also has several methods:

addEdge: this takes in a node and an optional weight for the connection and makes a single connection between the node you are calling the method on and the node you are passing to the method. This does not add a connection from the passed node to the node you are calling the method on.

Example:

const tim = new Node(...),
      ryan = new Node(...)
tim.addEdge(ryan)

This will make an edge between the node tim and ryan but will not create an edge from ryan to tim. You will have to call ryan.addEdge(tim) in order to create that edge (See: Graph.connect).

removeEdge: this removes the edge (if any) from the node you called the method on and the node passed in. Similar rules apply as addEdge.

updateEdge: this updates the weight between the called node and the passed node. If the edge/connection does not exist, it creates it with addEdge and used the passed in newWeight as the initial weight.

connectedTo: this returns boolean if the node passed in is connected to the node that called this method.

find: this returns the Edge that corresponds to the passed in node or returns undefined/void 0 if no connection is found

weightTo: this returns the weight of the edge between the callee and the node passed in or returns undefined/void 0 if no edge found.

###Graph

method	arguments	return
connect	a: Node, b: Node, weight: number	undefined
update	a: Node, b: Node, weight: number	undefined
contains	node: Node	boolean
removeNode	node: Node	undefined
cost	a: Node, b: Node	number/undefined

###Graph Details

A graph has two properties:

root: the root node of this graph. Unsure if needed but I wanted a root so we have one. This is set during the construction of the data and will be set to an empty Node if no data is passed

nodes: an array of Node type data of all of the nodes that are included inside of this graph. It will always be initially set to [root].

A graph has methods to interact with the data held inside:

connect: a way to create an edge between two nodes with the given weight. If the nodes are not inside of graph.nodes, they get added to the list.

update: this updates the weight between node a and node b. This does not update both weights and will need to be called on both nodes if that is wanted.

contains: this checks to see if graph.nodes contains the given node and returns a boolean.

removeNode: this removes a passed node from graph.nodes and then removes any and all edges to that node. If no node is found, it does nothing.

cost: this returns the weightTo from node a to node b.