npm package discovery and stats viewer.

Discover Tips

  • General search

    [free text search, go nuts!]

  • Package details

    pkg:[package-name]

  • User packages

    @[username]

Sponsor

Optimize Toolset

I’ve always been into building performant and accessible sites, but lately I’ve been taking it extremely seriously. So much so that I’ve been building a tool to help me optimize and monitor the sites that I build to make sure that I’m making an attempt to offer the best experience to those who visit them. If you’re into performant, accessible and SEO friendly sites, you might like it too! You can check it out at Optimize Toolset.

About

Hi, 👋, I’m Ryan Hefner  and I built this site for me, and you! The goal of this site was to provide an easy way for me to check the stats on my npm packages, both for prioritizing issues and updates, and to give me a little kick in the pants to keep up on stuff.

As I was building it, I realized that I was actually using the tool to build the tool, and figured I might as well put this out there and hopefully others will find it to be a fast and useful way to search and browse npm packages as I have.

If you’re interested in other things I’m working on, follow me on Twitter or check out the open source projects I’ve been publishing on GitHub.

I am also working on a Twitter bot for this site to tweet the most popular, newest, random packages from npm. Please follow that account now and it will start sending out packages soon–ish.

Open Software & Tools

This site wouldn’t be possible without the immense generosity and tireless efforts from the people who make contributions to the world and share their work via open source initiatives. Thank you 🙏

© 2024 – Pkg Stats / Ryan Hefner

graph-isomorphisms

v0.1.0

Published

Small library to count the number of isomorphisms between two graphs

Downloads

6

Readme

Are two graphs isomorphic?

This is a small JS library that can check how many isomorphisms exists between two graphs.

// npm install --save graph-isomorphisms
var computeIsomorphisms = require('graph-isomorphisms')

It is implement using unification (based on datascript) and runtime is exponential in the number of nodes. In other words, you can only check very small graphs.

Examples

example graphs, g_1, g_2

var G = [ [1, 2], [2, 3], [3, 1] ]
// three isomorphims between G and itself
computeIsomorphisms(G, G).length === 3 //=> true

// G not isomorphic to H
var H = [ [1, 2], [2, 1], [1, 3] ]
computeIsomorphisms(G, H).length > 0 //=> false

// G is same graph as I, but with different node identifiers
var I = [ [42, 666], [666, 1], [1, 42] ]
computeIsomorphisms(G, I).length > 0 //=> true

Note on runtime complexity.

Graph Isomorphism is a famous problem in computer science, on which some recent progress has been made by László Babai, giving an algorithm that runs in "quasi-polynomial-time", e.g. efficient. We don't implement this algorithm, obviously.

https://www.quantamagazine.org/20151214-graph-isomorphism-algorithm/

API

A graph is specified as an edge list, an array of pairs of numbers specifying a directed edge from the first to the second node.

For example, take these two graphs.

example graphs, g_1, g_2

var g_1 = [[0, 1], [1, 2], [2, 0]]
var g_2 = [[5, 6], [5, 8], [6, 8]]

You can now ask if these two are isomorphic (they shouldn't be).

if (computeIsomorphisms(g_1, g_2).length === 0) {
  console.log('g_1 and g_2 are not isomorphic!')
}

example graphs, g_3, g_4

Actually, if they are isomorphic, you will get proofs: a mapping between the edges (negative numbers) and nodes.

var g_3 = [[0, 1], [1, 2], [1, 3]]
var g_4 = [[6, 7], [5, 6], [6, 8]]
console.log(computeIsomorphisms(g_3, g_4))
// [
//   [ -1, -3, -0, -2, 3, 1, 2 ],
//   [ -1, -2, -0, -3, 2, 1, 3 ]
// ]

Notice the negative zero, LOL floating point numbers

That's it.