maximal-independent-set
Maximal independent vertex sets
npm install maximal-independent-set
Want to see pretty graphs? Log in now!
1 | downloads in the last week |
8 | downloads in the last month |
Last Published By | |
---|---|
Version | 0.0.0 last updated a year ago |
License | MIT |
Keywords | maximal, independent, set, vertex, graph, simplicial, complex, edge, adjacency, maximum |
Repository | git://github.com/mikolalysenko/maximal-independent-set.git (git) |
Dependencies | None |
Dependents | mikolalysenko-hoarders |
maximal-independent-set
Finds a maximal independent vertex set. No guarantees that it is maximum.
Install
npm install maximal-independent-set
Example
var independetSet = require("maximal-independent-set")
//Generate a graph
console.log(independentSet(
[[1, 3],
[0, 2],
[3, 1],
[0, 2]]))
require("maximal-independent-set")(adjacency_list[, result])
Given a graph encoded as an adjacency list, compute a maximal independent vertex set (aka vertex packing).
adjacency_list
is an array with length = number of vertices, where each ith entry is an array representing the neighbors of vertex i. If your graph is encoded as an edge list instead of an adjacency list, you can use thestars
npm module to make the necessary conversion.result
is an optional array that gets the result of the independent set. If not specified, a new Uint8Array is created.
Returns A vector whose ith entry determines whether the vertex is contained in the independent set or not
Credits
(c) 2013 Mikola Lysenko. MIT License