An algorithm that given two graphs allows you to:

• compute their similarity (or correlation);
• construct the maximum common subgraph (MCS) also called the maximum common substructure.

It is a simple solution to the maximum common sugraph problem for small graphs.

Simply install it via npm:

npm install maximum-common-subgraph

Done! You can now do:

{Graph, GraphEdge, GraphNode, Points, constructMCS} = require('maximum-common-subgraph')

Download the mcs_browser_module.js file into your working directory and then do:

<script type="module">
  import {Graph, GraphEdge, GraphNode, Points, constructMCS} from './mcs_browser_module.js';
  
  ....js code goes here....
</script>

Download the index.ts file into your working directory and then do:

import {Graph, GraphEdge, GraphNode, Points, constructMCS} from "./index";

And you're good to go.

See the two examples in the ./examples folder. They are meant to be an introduction on how to use this algorithm.

Check out these two working examples on codepen:

• Molecules Similarity
• Shank Language Model

The algorithm is written in pure functional programming style. As such it makes heavy use of recursion. However it is designed such that javascript interpreter can perform tail-call optimization (all recursive calls are at the last statement of the function) in order to prevent a maximum calls stack exceeded error. That said I still have to test the algorithm for graphs with >23 nodes.

Given two graphs, mcs is the largest graph which is structurally identical to both graphs. Constructing the mcs is fundamental in order to compute the similarity between two graphs. Indeed this correlation is a value between 0 and 1 which results from the comparison between the size of the mcs and the averaged size of the two original graphs. I'll write a more detailed mathematical explanation soon.

• Create a python version of this algorithm.

• ES6
• TypeScript
• Node.js
• Visjs (for visualizing and debugging)

Moritz F. Wurm, Ph.D. was the who kick-started this project. He has also given me fundamental feedback throughout the development of this algorithm during an internship I have done at his lab. For more details about the reason why this algorithm was created in the first place check out the readme of this example.