bearded-graph
v0.1.0
Published
A basic graph data type
Downloads
4
Readme
#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.