DEV Community

loading...
Cover image for Create and Draw Graphs in JavaScript with JsGraphs

Create and Draw Graphs in JavaScript with JsGraphs

mlarocca profile image Marcello La Rocca ・21 min read

JsGraphs is a lightweight library to model graphs, run graph algorithms, and display graphs in the browser.

In this post we'll see how you can use this library to create arbitrarily complex graphs and run algorithms and transformations on them, or just use visualize them in the browser, or save the drawing as an SVG. It's also possible to import 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

First things first: let's see how you can get started using this library.

NPM

JsGraphs is available on npm: assuming you have you do have npm installed, you just need to run
npm install -g @mlarocca/jsgraphs, to install it globally, or even better add it as a dependency in your project's package.json, and then run npm install (from the project's folder).

Once that's done, to import the library in your scripts, you can use either

import {default as jsgraphs} from '@mlarocca/jsgraphs';
Enter fullscreen mode Exit fullscreen mode

or

const jsgraphs = require('@mlarocca/jsgraphs');`
Enter fullscreen mode Exit fullscreen mode

depending on the module system you employ.

Local Clone

You can also clone/fork JsGraph's repo on GitHub and build the library from the source code.

Installation

From the base folder:

nvm install stable

npm install
Enter fullscreen mode Exit fullscreen mode

Run tests

From the base folder:

npm t test/$FOLDER/$TEST
Enter fullscreen mode Exit fullscreen mode

For instance

npm t test/geometric/test_point.js
Enter fullscreen mode Exit fullscreen mode

Bundle

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

npm run bundle
Enter fullscreen mode Exit fullscreen mode

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

How do you feel about graph theory? For an introduction to Graphs, 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.

Overview

There are two main entities that can be created in this library: graphs (class Graph) and embeddings (Embedding).

The former focuses on modeling data and transforming it through algorithms, the latter is used to represent graphs on display (or paper!).

The rest of this post is a tutorial, showing how to programmatically create graphs and embeddings with just a few lines of code.

Graph

A graph is a data structure that allows modeling interconnected data, where heterogeneous entities (the graph's vertices) can be in relation among them; these relationships are modeled by the graph's edges.

In JsGraphs, creating a graph is quite simple:

import Graph from '/src/graph/graph.mjs';

let graph = new Graph();
Enter fullscreen mode Exit fullscreen mode

The instance variable graph now has been created, without any vertex or edge. Of course, these entities are also modeled in the library:

Vertices

Class Vertex implement the first basic component of any graph, in turn modeling the entities (data) part of a graph.

Create a Vertex

import Vertex from '/src/graph/vertex.mjs';

const u = new Vertex('u');
const v = new Vertex('vertex name', {weight: 3, label: 'I am a label', data: [1, 2, 3]});
Enter fullscreen mode Exit fullscreen mode

A vertex' name is forever, it can never be changed: it uniquely identifies a vertex, and in fact a vertex' ID is computed from its name.

On creation, you must add a name for the vertex, and optionally you can include:

  • A weight: the default weight for a vertex is 1, and generally you don't have to worry about this weight, but some graph applications can use it.
  • A label: an optional string that can be changed over time and used to convey non-identifying, mutable info about the vertex.
  • Data: this is the most generic field for a vertex, it can include any serializable object, even another graph: this way, for instance, it's possible to create meta-graphs (graphs where each vertex is another graph) and run specific algorithms where whenever a vertex is visited, the graph it holds is also traversed (one example could be the graph of strongly connected components: breaking G into its SCCs, and then representing it with a new meta-graph, the SCC graph, whose vertices hold the actual components).

A vertex's name can either be a string or a number: any other type will be considered invalid.

It is possible to use the static method Vertex.isValidName to check if a value is a valid name:

Vertex.isValidName(1);   // true
Vertex.isValidName('abc');   // true
Vertex.isValidName([1, 2, true, 'a']);   // false
Vertex.isValidName({a: [1, 2, 3], b: {x: -1, y: 0.5}});   // false
Vertex.isValidName(new Map());   // false
Vertex.isValidName(new Vertex('test'));   // false
Enter fullscreen mode Exit fullscreen mode

Likewise, there are methods Vertex.isValidLabel and Vertex.isValidData. Labels must be strings (they are optional, so null and undefined are accepted to encode the absence of a value, and the empty string is also a valid label).
Data, instead, doesn't have to be a string, it can be any object that can be serialized to the JSON format: strings, numbers, arrays, plain JS objects, or custom objects that have a toJson() method.

Vertex.isValidData(1);   // true
Vertex.isValidData('abc');   // true
Vertex.isValidData([1, 2, true, 'a']);   // true
Vertex.isValidData({a: [1, 2, 3], b: {x: -1, y: 0.5}});   // true
Vertex.isValidData(new Vertex('test'));   // true, Vertex has a toJson() method
Vertex.isValidData(new Graph());   // true!! Graph has a toJson() method

Vertex.isValidData(new Map());   // false
Vertex.isValidData(new Set());   // false
Vertex.isValidData(() => true));   // false, functions can't be serialized to JSON
Enter fullscreen mode Exit fullscreen mode

Existing vertices can be added to graphs: notice that it's NOT possible to add two vertices with the same name to the same graph.

let graph = new Graph();
const v = new Vertex('v', {weight: 3});
const u = new Vertex('u');

graph.addVertex(v);
graph.addVertex(u);
// graph.addVertex(new Vertex('u)) // ERROR, duplicated vertex 'u'
Enter fullscreen mode Exit fullscreen mode

A simple graph

There is also a shortcut to create those vertices directly on the graph, without first creating them as a separate variable; besides being shorter, this way is also more efficient, because vertices (and edges) added to a graph are actually cloned beforehand (meaning that, in the example above, a clone of v and u is actually added to graph).

let graph = new Graph();

const vId = graph.createVertex(['I', 'am', 'a', 'valid', 'name'], {weight: 3});
const uId = graph.createVertex('u');
// graph.createVertex('u) // ERROR, duplicated vertex 'u'
Enter fullscreen mode Exit fullscreen mode

Vertex ID

As you can see in the snippet above, createVertex (as well as addVertex) returns the ID of the vertex created (NOT a reference to the actual instance held by the graph).

Each vertex, in fact, has an id property that uniquely identifies it in a graph: as mentioned, there can't be two vertices with the same name, so there is a 1:1 correspondence between names and IDs. This means that the IDs of two instances of Vertex can clash even if they are different objects, or if they have different properties.

const u1 = new Vertex('u', {weight: 3});
const u2 = new Vertex('u');

console.log(u1.equals(u2));     // false
console.log(u1.id === u2.id);   // true
Enter fullscreen mode Exit fullscreen mode

Retrieve a Vertex

You might want to hold to the id of a vertex, because you will need it to retrieve a reference to the actual vertex from the graph, and even to create a new edge (as we'll see in the next section).

const u = graph.getVertex(uId);
const v = graph.getVertex(vId);
Enter fullscreen mode Exit fullscreen mode

Most of the methods on graphs can take either an id, or a copy of the object to retrieve (namely a vertex or an edge).
For instance:

graph.getVertex(uId);
graph.getVertex(graph.getVertex(uId));
Enter fullscreen mode Exit fullscreen mode

both work and return a reference to vertex u (although the latter does that very inefficiently!).

Once you get ahold of a reference to a graph's vertex, you can read all its fields, but you can only update its weight.

Although having vertices as perfectly immutable entities would have been desirable, this would have had repercussions on the performance of the graph, because updating a vertex v's weight would have meant replacing v in the graph with a new instance of Vertex, and also updating all the references to v in (potentially, up to ) all the edges in the graph.
As a compromise, a vertex' name and id are kept immutable and impossible to change, while weight is mutable. Similar compromises will be made for embedded vertices and edges.
Switching to TypeScript, or whenever a future EcmaScript specification will include protected fields, would allow for more flexibility and possibly this aspect will be reviewed. For now, changing the mutable attributes of a graph's vertices and edges directly is discouraged: the forward-compatible way is going to be changing them through the Graph and Embedding's methods.

Edges

The other fundamental entity on which graphs are based are edges, implemented in class Edge.

Creating a new edge is as simple as creating a new vertex, except that we need to pass two instances of Vertex to the edge's constructor, for its source and destination:

import Vertex from '/src/graph/vertex.mjs';
import Edge from '/src/graph/edge.mjs';

const v = new Vertex('vertex name', {weight: 3});
const u = new Vertex('u');

const e = new Edge(u, v, {weight: 0.4, label: "I'm an edge!"});
Enter fullscreen mode Exit fullscreen mode

Like vertices, Edges are only mutable for what concerns their weight: it's the only field of an edge that can be changed after it's created.

And likewise, edges also have an id field, that uniquely identify them in a graph: in simple graphs (like the ones implemented in classes Graph and UndirectedGraph), there can be at most a single edge between two vertices, so an edge's ID is based on the IDs of its source and destination, and can uniquely identify an edge within a graph.

Notice that two edges detached from any graph, or belonging to two different graphs, could be different while having the same ID (because, for instance, they have a different label or weight), but this is not possible within any individual graph.

Create an Edge

You can add an existing edge to a graph with method addEdge, or equivalently (and perhaps more easily), you can create the new edge directly through an instance of graph:

import Vertex from '/src/graph/vertex.mjs';
import Edge from '/src/graph/edge.mjs';
import Graph from '/src/graph/graph.mjs';

let g = new Graph();
const v = g.createVertex('v', {weight: 1.5});
const u = g.createVertex('u', {weight: 1.5});

const e = g.createEdge(u, v, {weight: 0.4, label: "I'm an edge!"});
Enter fullscreen mode Exit fullscreen mode

An edge

Directed vs Undirected

While the vertices at the two ends of an edge uniquely determine the edge's ID, it has to be clear that their order matters, at least in directed graphs.

In directed graphs, in fact, each edge has a direction associated, from its source to its destination, and so an edge from vertex 'u' to vertex 'v' is different than one from 'v' to 'u'.

let g = new Graph();
const v = g.createVertex('v', {weight: 1.5});
const u = g.createVertex('u', {weight: 1.5});

const e1 = g.createEdge(u, v, {weight: 0.4, label: "back"});
const e2 = g.createEdge(v, u, {weight: 1.4, label: "and forth"});
Enter fullscreen mode Exit fullscreen mode

A couple of edges

Weight Matters

While for vertices we saw that weight is something useful in niche situations, it's much more common to set a weight for edges: many graph's algorithms like Dijkstra's or A* make sense only on weighted graphs (while for unweighted graphs, i.e. graphs whose edges have no weights associated, we can likely make do with BFS).

In many applications we'll need to update the weight of graph edges after its creation: like for vertices, it is possible to retrieve an edge and update its weight, but the safest way to do so is by using the setEdgeWeight method on an instance of Graph.

let g = new Graph();
const v = g.createVertex('v', {weight: 1.5});
const u = g.createVertex('u', {weight: 1.5});

const e = g.createEdge(u, v, {weight: 0.4, label: "back"});
g.setEdgeWeight(e, 1.5);
g.setEdgeWeight(e.id, -3.1);
Enter fullscreen mode Exit fullscreen mode

Retrieving an Edge

The easiest way to get ahold of a reference to a graph's edge is through its ID:

let e = g.getEdge(e.id);
e = g.getEdge(edgeID);  // Assuming you have the ID stored in this variable
Enter fullscreen mode Exit fullscreen mode

If you don't have the edge's ID at hand, though, do not despair! You can also retrieve an edge by passing its source and destination to method getEdgeBetween (since, as mentioned, there can only be one vertex in a simple graph from a source to a destination).

let e = g.getEdgeBetween(u, v);
// You can also pass vertices' IDs
e = g.getEdgeBetween(u.id, v.id);
// ... and even mix them
e = g.getEdgeBetween(u, v.id);
e = g.getEdgeBetween(u.id, v);
Enter fullscreen mode Exit fullscreen mode

Loops

Last but not least, so far we have always assumed that the source and the destination of an edge are distinct: this doesn't necessarily need to be true. In other words, it's possible to have an edge starting from and ending to the same vertex: in this case, the edge is called a loop.

let loop = g.createEdge(u, u, {label: 'Loop'});
Enter fullscreen mode Exit fullscreen mode

An edge and a loop

Graph class

The only thing that still needs to be said about class Graph as a data structure is that it implements an undirected graph.

Class Graph implements directed graphs, where the direction of an edge matters.

If, instead, we don't care about that, and edges can be traveled in both directions, then the right class to use is UndirectedGraph.

Let's explore the difference with a couple of examples.

Generators

Both classes offer generators to simplify the creation of some of the most common classes of graphs; in the following sections, we'll explore the available ones, and lay out the roadmap to implement more of these.

Complete Graphs

In a complete graph, each vertex is connected by an edge to each other vertex in the graph; in these graphs, the number of edges is maximal for simple graphs, quadratic with respect to the number of vertices.

Notice that a complete graph doesn't contain loops.

Creating complete graphs is easy, you just need to pass the number of vertices that the graph will hold:

import { UndirectedGraph } from '/src/graph/graph.mjs';

let g = Graph.completeGraph(12);
let ug = UndirectedGraph.completeGraph(12);
Enter fullscreen mode Exit fullscreen mode

Of course, the names for the vertices are standard, just the numbers between 1 and n.
The representation of such graphs is cool for both directed and undirected ones:

A complete directed GraphA complete undirected Graph

We'll discuss how to get these drawings later, in the section about embeddings.

Bipartite Complete Graphs

In a bipartite graph vertices can be partitioned in two groups, such that vertices in each group are only connected with vertices in the other group (in other words, each vertex in group A can't have any edge to another vertex within group A, and likewise for the other group).

A complete bipartite graph just has all the possible edges between the two groups: check the figures to get an idea.

let g = Graph.completeBipartiteGraph(4, 6);   // Just pass the sizes of the two groups
let ug = UndirectedGraph.completeBipartiteGraph(7, 3);
Enter fullscreen mode Exit fullscreen mode

A complete bipartite directed GraphA complete bipartite undirected Graph

Serialization

Well, turns out there is another important thing to mention: serialization. All the entities in JsGraphs are serializable to JSON, and can be created back from a JSON file.

let g = new Graph();
// ...
const json = g.toJson();
let g1 = Graph.fromJSON(json);
Enter fullscreen mode Exit fullscreen mode

This is an important property (and the reason why we restricted the type of valid names), because it allows you to create a graph in any other platform/language, possibly run algorithms or transformations on it, and then export it to a JSON file, pick it up in you web app with JsGraphs, and display it.

Or, vice versa, create it in JS (perhaps with an ad-hoc tool: stay tuned!), and then import it in your application written in any other language, or just store it in a database and retrieve it later.

As long as you adhere by the (simple) format used, compatibility is assured.

Embedding

While many graphs' applications are interested in the result of applying one of the algorithms above, there are many, probably just as many, for which either the visual feedback or the actual way we lay out vertices and edges on a plane (or in a 3D space) are fundamental.

An embedding, and in particular a planar embedding, is technically an isomorphism...
but to keep things simple here, we can describe it as a way to assign a position to each vertex and draw each edge with a curve or polyline.

In this library, we will restrict the way in which we draw edges; they will be either:

  • Straight line segments;
  • Quadratic Bézier curves, with their control point lying on a line perpendicular to the edge and passing through its middle point.

This, obviously, restricts the set of possible ways to draw a graph (for instance, polylines or higher order curves are not allowed), but it allows a simpler approach, while still leaving plenty of options for nice and effective drawings.

We'll see how this simplification is important when we get to automatic embedding generators.

Of Appearance and Essence

This dualism is common in computer science, so much so that there is one of the fundamental design patterns, MVC, that guides how the former should be separated from the latter.

Applied to graphs, the substance is the graph data structure, which has the maximum level of abstraction: it's a perfect candidate for the Model part of MVC pattern.

In a way, an embedding is partly more about the form than the graph itself: we arrange vertices and edges as a way to display a graph, to make it easier to comprehend to humans.

An embedding, however, can also be substance: for instance if vertices are electronic components on a circuit board, and edges are connective tracks, then their position is not just about appearance.

For our Embedding class, we have thus tried to separate form and substance accordingly: all the attributes that we can associate with an embedding's structure (its substance) can be passed to the constructor and modified using setters.

The form, for class Embedding, is the way we can later represent it: this is a separate concern, in line with MVC; regardless of whether we provide methods inside this class to generate the view, it's possible to write separate classes taking an embedding and generating a view.

The build-in methods to generate a view for an Embedding are toJson, to produce a JSON representation of the embedding (and serialize/deserialize it), and - perhaps more interestingly - toSvg that generates SVG markup for vertices and edges.

Again, this method is provided so that you have an out-of-the-box default way to display a graph, but it's decoupled from the model, relying on its public interface only, so that you can also write your own class to handle the view part.

This decoupling also translates to the fact that you will need to pass everything that is related to the View (i.e. the form) to method toSvg directly (and each time you call it). More on this in a few lines...

Create an Embedding...

Embeddings creation works following the same logic as graphs: an embedding, in particular, is a collection of embedded vertices (class EmbeddedVertex), meaning graph's vertices to which we assigned a position with respect to some coordinate system, and embedded edges (class EmbeddedEdge), whose position is determined by the vertices at their ends, but for which we can still decide how they are drawn.

You should never worry about these two classes: although they are public classes and you can retrieve a reference to either through an instance of Embedding, you should never need to interact with those classes directly.

While it is true that the constructor for Embedding takes two collections as input, one of embedded vertices and one of embedded edges, there are easier ways to create an embedding from a graph.

... From a Graph

The easiest way is to create an embedding starting from an existing graph:

import Embedding from '/src/graph/embedding/embedding.mjs';

let g = new Graph();
const v = g.createVertex('v', {weight: 1.5});
const u = g.createVertex('u', {weight: 1.5});

const e = g.createEdge(u, v, {weight: 0.4, label: "back"});

let embedding = Embedding.forGraph(g, {width: 640, height: 480});
Enter fullscreen mode Exit fullscreen mode

This will create an embedding for graph g, where the positions of the vertices are chosen randomly within a canvas of the specified size (in this case, a box spanning from (0, 0) to (639, 479)).

To control how the vertices and edges are laid out, we can pass two optional arguments to the static method forGraph:

  • vertexCoordinates, a map between vertices' IDs and Point2D objects specifying where the vertex center will lie in the embedding;
  • edgeArcControlDistances, another map, this time between edges' IDs and a parameter regulating how the edge is drawn (more on this later).
let g = new Graph();
const v = g.createVertex('v', {weight: 1.5});
const u = g.createVertex('u', {weight: 1.5});

const e = g.createEdge(u, v, {weight: 0.4, label: "back"});

let embedding = Embedding.forGraph(g, {
  width: 640,
  height: 480,
  vertexCoordinates: {
    [v]: new Point2D(100, 100),
    [u]: new Point2D(400, 300)
  },
  edgeArcControlDistances: {
    [e]: -60
  }
});
Enter fullscreen mode Exit fullscreen mode

Alternatively, it's possible to change a vertex' position or an edge's control distance at any time, using:

// Depending on your coordinate system, real (or even negative) coordinates can make sense
embedding.setVertexPosition(v, new Point2D(-1, -1));
embedding.setEdgeControlPoint(e, 3.14);
Enter fullscreen mode Exit fullscreen mode

... or, with Generators

The other suggested way to create embeddings is through generators. We have already seen how to speed up the creation of graphs for some of the most common types, like complete graphs for instance.

It is totally possible to create a graph first and then the embedding manually, like this:

let g = Graph.completeGraph(9);
let embedding = Embedding.forGraph(g, {width: 480, height: 480});
Enter fullscreen mode Exit fullscreen mode

The result, however, is not as appalling as you might expect, because the positions of the vertices are assigned randomly.

A complete directed Graph

It's still possible to manually set the position of each vertex... but it's quite tedious, right?
Instead, we can use the matching generators provided by class Embedding, that will also automatically assign positions to the vertices in order to obtain a nice drawing.

let embedding = Embedding.completeGraph(9, 480, false);
Enter fullscreen mode Exit fullscreen mode

An embedding for complete directed Graph

About Edge Drawing

As already mentioned, we only allow edges to be drawn as line segments or arcs, in the form of quadratic Bézier curves.
If you need a primer on drawing arcs with Bézier curves, you can check out this section of "Algorithms and Data Structures in Action".

These curves are a subset of second order polynomials whose trajectory is determined by a control point, that is going to be the third vertex in a triangle including the two ends of the curve.

The curve will then be the interpolation of the two linear Bézier curves between the first end and the control point, and between the control point and the second end of the curve.

For JsGraphs we further restrict to only the quadratic Bézier curves whose control point lies on a line perpendicular to the segment connecting the two edge's ends, and passing in the middle point of said segment: the following figure illustrates this case:

![Using a quadratic curve to draw an edge](https://dev-to-uploads.s3.amazonaws.com/i/p5bajyp20flpqss63ur9.png

Notice that the distance between the control point and the two ends will always be the same, so the arc drawn for the edge will be symmetrical.

We can control the curvature of the arc by setting the distance of the control point from the segment on which the two ends lie, i.e. parameter d in the figure above: that's exactly the value set by method setEdgeControlPoint.

If we set this distance to 0, we will draw the arc as a straight line segment; positive values will cause the edge's curve to point up, while negative values will make the curve point down.

let g = new Graph();
const v = g.createVertex('v', {weight: 1.5});
const u = g.createVertex('u', {weight: 1.5});

const e = g.createEdge(u, v);

let embedding = Embedding.forGraph(g);

embedding.setVertexPosition(u, new Point2D(30, 60));
embedding.setVertexPosition(v, new Point2D(270, 60));

embedding.setEdgeControlPoint(e, 70);
// Draw 1
embedding.setEdgeControlPoint(e, 0);
// Draw 2
embedding.setEdgeControlPoint(e, -70);
// Draw 3
Enter fullscreen mode Exit fullscreen mode

Using a quadratic curve to draw an edge

You can also find a deeper explanation of Bézier curves on Wikipedia, and of how they work in SVG on Mozilla's developer blog.

Styling

Styling, i.e. the appearance part, is mainly specified through CSS: each vertex and each edge can individually be assigned one or more CSS classes, at the moment the SVG is generated.

Additionally, there are a few parameters that can be tuned to enable/disable features, like displaying edges' labels and weights, or disabling arcs in favor of line segments.

It's also possible to assign CSS classes to the group containing the whole graph.

let embedding = Embedding.forGraph(g);
// [...]
embedding.toSvg(700, 550, {
  graphCss: ['FSA'],          // This class is added to the whole graph, can be used as a selector
  verticesCss: {[u]: ['source'], [v]: ['dest', 'error'],
  edgesCss: {[e]: ['test1', 'test2']},
  drawEdgesAsArcs: true,      // Display edges as curves or segments
  displayEdgesLabel: false,  //  No label added to edges
  displayEdgesWeight: false   // Weights are not displayed either
})
Enter fullscreen mode Exit fullscreen mode

The output will look something like:

<svg width="300" height="120">

  <defs>
    <marker id="arrowhead" markerWidth="14" markerHeight="12" markerUnits="userSpaceOnUse" refX="13" refY="6" orient="auto">
      <polygon points="0 0, 14 6, 0 12" style="fill:var(--color-arrow)"/>
    </marker>
    <linearGradient id="linear-shape-gradient" x2="0.35" y2="1">
      <stop offset="0%" stop-color="var(--color-stop)" />
      <stop offset="30%" stop-color="var(--color-stop)" />
      <stop offset="100%" stop-color="var(--color-bot)" />
    </linearGradient>
    <radialGradient id="radial-shape-gradient" cx="50%" cy="50%" r="50%" fx="50%" fy="50%">
      <stop offset="0%" stop-color="var(--color-inner)" style="stop-opacity:1" />
      <stop offset="50%" stop-color="var(--color-mid)" style="stop-opacity:1" />
      <stop offset="100%" stop-color="var(--color-outer)" style="stop-opacity:1" />
    </radialGradient>
  </defs>
  <g class="graph FSA">
    <g class="edges">
      <g class="edge test1 test2" transform="translate(30,60)">
        <path d="M0,0 Q120,70 218,0"
        marker-end="url(#arrowhead)"/>
      </g>
    </g>
    <g class="vertices">
      <g class="vertex dest error" transform="translate(270,60)">
        <circle cx="0" cy="0" r="22.5" />
        <text x="0" y="0" text-anchor="middle" dominant-baseline="central">v</text>
      </g>
      <g class="vertex source" transform="translate(30,60)">
        <circle cx="0" cy="0" r="22.5" />
        <text x="0" y="0" text-anchor="middle" dominant-baseline="central">u</text>
      </g>
    </g>
  </g>
</svg>
Enter fullscreen mode Exit fullscreen mode

Finally, an example of how a combination of different visualization styles and different structural changes (directed vs undirected edges) can impact how a graph is perceived:

Different styles for a complete graph

Graph Algorithms

The most interesting part about graphs is that, once we have created one, we can run a ton of algorithms on it.

Here there is a list of algorithms that are implemented (or will be implemented) in JsGraphs:

BFS

It's possible to run the Breadth First Search algorithm on both directed and undirected graphs.

import { range } from '/src/common/numbers.mjs';

let g = new Graph();
range(1, 8).forEach(i => g.createVertex(`${i}`, {weight: 1.5})); // Create vertices "1" to "7"

g.createEdge(v1, v2);
g.createEdge(v1, v3);
g.createEdge(v2, v4);
g.createEdge(v3, v5);
g.createEdge(v3, v4);
g.createEdge(v4, v6);
g.createEdge(v6, v7);

const bfs = g.bfs('"1"');
Enter fullscreen mode Exit fullscreen mode

If we print out the result of running bfs, we obtain an object with both the distance and predecessor of each vertex in the graph (at least, each one reachable from the start vertex, "1" in this case).

{
  distance: {"1": 0, "2": 1, "3": 1, "4": 2, "5": 2, "6": 3, "7": 4},
  predecessor: {"1": null, "2": '"1"', "3": '"1"', "5": '"3"', "4": '"3"', "6": '"4"', "7": '"6"'}
}
Enter fullscreen mode Exit fullscreen mode

That's not the easiest to visualize, though. One thing we can do is reconstruct the path from the start vertex to any of the reachable vertices (in this case, any other vertex in the graph, because they are all reachable from "1").

The result of the Graph.bfs method, in fact, is an object, an instance of class BfsResult, that in turn offers an interesting method: reconstructPathTo. This method takes a destination vertex, and returns the shortest path (if any) from the starting point.

bfs.reconstructPathTo('"7"');   // [""1"", ""3"", ""4"", ""6"", ""7""]
Enter fullscreen mode Exit fullscreen mode

That's better, right? But how cooler would it be if we could also visualize it?
Well, luckily we can! Remember, from the Embedding section, that we can assign custom CSS classes to edges and vertices? Well, this is a good time to use that feature!

Let's start by creating an embedding for the graph:

let embedding = Embedding.forGraph(g, {width: 480, height: 320});

embedding.setVertexPosition('"1"', new Point2D(30, 180));
embedding.setVertexPosition('"2"', new Point2D(120, 40));
embedding.setVertexPosition('"3"', new Point2D(150, 280));
embedding.setVertexPosition('"4"', new Point2D(200, 150));
embedding.setVertexPosition('"5"', new Point2D(300, 280));
embedding.setVertexPosition('"6"', new Point2D(350, 220));
embedding.setVertexPosition('"7"', new Point2D(450, 150));

embedding.setEdgeControlPoint('["2"]["4"]', 20);
embedding.toSvg(480, 320, {drawEdgesAsArcs: true, displayEdgesWeight: false});
Enter fullscreen mode Exit fullscreen mode

At this point, the result of drawing the embedding is more or less the following:

A directed graph

Now, we want to highlight that path, starting at vertex "1" and ending at vertex "7". The issue with the result of reconstructPathTo is that it returns the sequence of vertices in the path, and while that does help us highlighting vertices, we would also like to assign a different css class to the edges in the path.

To do so, we also need to use method Graph.getEdgesInPath, that given a sequence of vertices, returns the edges connecting each adjacent pair.

Then, it's just up to us to choose the classes to assign to edges and vertices in the path.

const path = bfs.reconstructPathTo('"7"');
const edges = g.getEdgesInPath(path);
let vCss = {};
path.forEach(v => vCss[v] = ['inpath']);
vCss['"1"'].push('start');
vCss['"7"'].push('end');

let eCss = {};
edges.forEach(e => eCss[e.id] = ['inpath']);

embedding.toSvg(480, 320, {
  drawEdgesAsArcs: true,
  displayEdgesWeight: false,
  verticesCss: vCss,
  edgesCss: eCss,
  graphCss: ['bfs']
});
Enter fullscreen mode Exit fullscreen mode

This is the final result:

A graph, with a shortest path highlighted

Although aesthetically questionable 😉, it is significant of what can be achieved!
Of course, to get the style right, we need to add a few CSS rules, for instance:

.graph.bfs g.vertex.inpath circle {
  stroke: crimson;
}
.graph.bfs g.vertex.start circle, .graph.bfs g.vertex.end circle {
  fill: darkorange;
  stroke-width: 7;
}
.graph.bfs g.vertex.start circle, .graph.bfs g.vertex.end text {
  fill: white;
}
.graph,bfs g.edge path {
  fill: none;
  stroke: black;
  stroke-width: 3;
}
.graph.bfs g.edge.inpath path {
  fill: none;
  stroke: crimson;
  stroke-width: 5;
}
Enter fullscreen mode Exit fullscreen mode

Going Forward

There are many more algorithms that can be implemented and run on graphs, and much more that can be done with JsGraphs.

The library is still being developed, and if you feel like contributing, how about starting by taking a look at the open issues on GitHub?

Discussion (0)

pic
Editor guide