Skip to content

Exploring the structure of geodesic paths between nodes in a graph.

License

Notifications You must be signed in to change notification settings

micahscopes/graph-hops-js

Repository files navigation

graph-hops-js

A tool for analyzing and exploring the structure of geodesic paths between nodes in a graph.

Click here for a demo.

What does it do?

It generates a series of "n-hop graphs" representing the graph-geodesic distances between the nodes of a given input graph.

Hops

Imagine yourself traversing a graph made of nodes and edges. To get around you hop from node to node, following the edges of the graph.

What's the shortest number of hops it takes to get from one node to another? The shortest path from node A to node B is called a geodesic path.

n-hop graphs

An n-hop graph's edges reflect all length n geodesics of the original graph.

Directed or undirected?

For directed graphs, the minimum distance between nodes A and B might be different depending on which one you start on. For undirected graphs it will be the same either way.

Usage

Basic usage

import { graphHops } from "graph-hops";

// the graph `A --> B --> C --> D`
const nodes = ["A", "B", "C", "D"];
const edges = [
  { source: "A", target: "B" },
  { source: "B", target: "C" },
  { source: "C", target: "D" },
];

const hops = graphHops(nodes, edges);

console.log(hops);

Will print:

[
  1: [
    { source: "A", target: "B", hopDistance: 1 },
    { source: "B", target: "C", hopDistance: 1 },
    { source: "C", target: "D", hopDistance: 1 },
  ],
  2: [
    { source: "A", target: "C", hopDistance: 2 },
    { source: "B", target: "D", hopDistance: 2 },
  ],
  3: [
    { source: "A", target: "D", hopDistance: 3 },
  ],
]

Input and output formats

You can use different graph formats by passing in any or all of four interface functions: getNodeId, getEdgeSource, getEdgeTarget and makeHop.

// The default interface matches the format commonly used in D3 examples
const graphInterface = {
  // how to interpret input elements
  getNodeId: (node) => node,
  getEdgeSource: (edge) => edge.source,
  getEdgeTarget: (edge) => edge.target,

  // how to make output objects
  makeHop: (source, target, hopDistance, getNodeId) => ({
    source: getNodeId(source),
    target: getNodeId(target),
    hopDistance,
  }),
};

// you can pass these functions in via a `graphInterface` object
graphHops(nodes, edges, { graphInterface })

// or directly pass only the functions you want to override
graphHops(nodes, edges, { getNodeId: (node) => node.id, makeHop: ...})

Directed or undirected?

The input graph is assumed to be directed by default, but undirected input and output can be handled by passing directed: false in the options object:

graphHops(nodes, edges, { directed: false, ... })

Alternative auto-curried interface

The hopFinder interface allows quick re-use of the same options with different node/edge sets.

import { hopFinder, graphInterfaceVisJS } from "graph-hops";
const graphHops = hopFinder({ graphInterface: graphInterfaceVisJS });

graphHops(A.nodes, A.edges);
graphHops(B.nodes, B.edges);

API

Functions

hopsFinder(options, nodes, edges)object | function

Generates n-hop graph edges from the given graph's geodesics (auto-curried interface).

graphHops(nodes, edges, [options])object

Generates n-hop graph edges from the given graph's geodesics.

Typedefs

NodeValue : string | integer

A value representing a graph node.

NodeObject : object

An object containing information about a graph node.

EdgeObject : object | string

An object containing information about a graph edge. Can take any form but the default is { source, target }.

getNodeIdFunction : function

A function that returns a node's ID.

getEdgeSourceFunctionNodeObject | NodeValue

A function that gets an edge's source node.

getEdgeTargetFunctionNodeObject | NodeValue

A function that gets an edge's target node.

makeHopFunctionobject

A function that returns information about a geodesic relationship

GraphInterface : Object
Options : Object

hopsFinder(options, nodes, edges) ⇒ object | function

Generates n-hop graph edges from the given graph's geodesics (auto-curried interface).

Kind: global function
Returns: object | function - An object containing lists of n-hop graph edges keyed by the lengths of their associated geodesics.

Param Type
options Options
nodes Array.<NodeObject> | Array.<NodeValue>
edges Array.<EdgeObject>

graphHops(nodes, edges, [options]) ⇒ object

Generates n-hop graph edges from the given graph's geodesics.

Kind: global function
Returns: object - An object containing lists of n-hop graph edges keyed by the lengths of their associated geodesics.

Param Type
nodes Array.<NodeObject> | Array.<NodeValue>
edges Array.<EdgeObject>
[options] Options

NodeValue : string | integer

A value representing a graph node.

Kind: global typedef

NodeObject : object

An object containing information about a graph node.

Kind: global typedef

Param Type
[id] string | object

EdgeObject : object | string

An object containing information about a graph edge. Can take any form but the default is { source, target }.

Kind: global typedef

Param Type Description
[source] string | object The default source key for an edge object.
[target] string | object The default target key for an edge object.

getNodeIdFunction : function

A function that returns a node's ID.

Kind: global typedef

Param Type
node NodeObject | NodeValue

getEdgeSourceFunction ⇒ NodeObject | NodeValue

A function that gets an edge's source node.

Kind: global typedef

Param Type
edge EdgeObject

getEdgeTargetFunction ⇒ NodeObject | NodeValue

A function that gets an edge's target node.

Kind: global typedef

Param Type
edge EdgeObject

makeHopFunction ⇒ object

A function that returns information about a geodesic relationship

Kind: global typedef

Param Type Description
source NodeObject | NodeValue The source node.
target NodeObject | NodeValue The target node.
hopDistance number The length of the geodesic path from the source node to the target node.
getNodeId function The function that gets a node's ID.

GraphInterface : Object

Kind: global typedef
Properties

Name Type Description
[getNodeId] getNodeIdFunction A function that returns a node's ID.
[getEdgeSource] getEdgeSourceFunction A function that gets an edge's source node.
[getEdgeTarget] getEdgeTargetFunction A function that gets an edge's target node.
[makeHop] makeHopFunction A function that returns information about a geodesic relationship.

Options : Object

Kind: global typedef
Properties

Name Type Default Description
[directed] boolean true Whether or not to treat this as a directed graph.
[graphInterface] GraphInterface An object containing graph interface functions.
[getNodeId] getNodeIdFunction A function that returns a node's ID.
[getEdgeSource] getEdgeSourceFunction A function that gets an edge's source node.
[getEdgeTarget] getEdgeTargetFunction A function that gets an edge's target node.
[makeHop] makeHopFunction A function that returns information about a geodesic relationship.

About

Exploring the structure of geodesic paths between nodes in a graph.

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Sponsor this project

 

Packages

No packages published