🚀 Socket Launch Week Day 5:Introducing Repository Access Permissions and Custom Roles.Learn more
Sign In

graphinius

Package Overview
Dependencies
Maintainers
1
Versions
65
Alerts
File Explorer

Advanced tools

Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

graphinius - npm Package Compare versions

Comparing version
2.0.0
to
2.0.1
+151
lib/centralities/Betweenness.ts
import * as $G from '../core/base/BaseGraph';
import * as $FW from '../traversal/FloydWarshall';
import * as $JO from '../traversal/Johnsons';
/**
* DEMO Version of a betweenness centrality computed via Johnson's or FloydWarshall algorithm
*
* @param graph the graph to perform Floyd-Warshall/Johnsons on
* @param directed for normalization, not used at the moment
* @param sparse decides if using the FW (dense) or Johnsons (sparse)
*
* @returns m*m matrix of values (dist), m*m*m matrix of neighbors (next)
* @constructor
*
* @comment function gives the correct results but is slow.
*
* !!! DO NOT USE FOR PRODUCTION !!!
*
* @todo decide if we still need it...
* @todo in any case, make a CLASS out of it (standardize centrality signatures)
*/
function betweennessCentrality(graph: $G.IGraph, directed?: boolean, sparse?: boolean): {} {
let paths;
sparse = sparse || false;
if (sparse) {
paths = $JO.Johnsons(graph)[1];
}
else {
paths = $FW.changeNextToDirectParents($FW.FloydWarshallAPSP(graph)[1]);
}
let nodes = graph.getNodes();
//getting the nodeKeys
let nodeKeys = Object.keys(nodes);
let map = {};
for (let key in nodes) {
//initializing the map which will be returned at the end - should it contain the keys (numbers), or the node IDs?
map[key] = 0;
}
let N = paths.length;
for (var a = 0; a < N; ++a) {
for (var b = 0; b < N; ++b) {
//if self, or b is directly reachable from a and it is the only shortest path, no betweenness score is handed out
if (a != b && !(paths[a][b].length == 1 && paths[a][b][0] == b) && paths[a][b][0] != null) {
// console.log("called with a and b: "+a+" , "+b);
let tempMap = {};
let leadArray: Array<Array<number>> = [];
let pathCount = 0;
do {
//ends when all paths are traced back
let tracer = b;
let leadCounter = 0;
pathCount++;
while (true) {
//ends when one path is traced back
let previous: Array<number> = paths[a][tracer];
let terminate = false;
//no branching:
if (previous.length == 1 && previous[0] == tracer) {
break;
}
else if (previous.length == 1) {
tracer = previous[0];
//scoring on the fly
tracer in tempMap ? tempMap[tracer] += 1 : tempMap[tracer] = 1;
}
//if there is a branching:
//handle reaching the terminal node here too!
if (previous.length > 1) {
//case: leadArray is empty and we find a branch
if (leadArray.length == 0) {
//leave a trace in the leadArray
leadArray.push([0, previous.length]);
if (previous[0] == tracer) {
terminate = true;
}
else {
tracer = previous[0];
tracer in tempMap ? tempMap[tracer] += 1 : tempMap[tracer] = 1;
}
leadCounter++;
}
//case: branch is covered by the leadArray
else if (leadCounter < leadArray.length) {
let choice = leadArray[leadCounter][0];
if (previous[choice] == tracer) {
terminate = true;
}
else {
tracer = previous[choice];
tracer in tempMap ? tempMap[tracer] += 1 : tempMap[tracer] = 1;
}
leadCounter++;
}
//case: branch is beyond the leadArray (new branching encountered)
else {
//leave a trace in the leadArray
leadArray.push([0, previous.length]);
if (previous[0] == tracer) {
terminate = true;
}
else {
tracer = previous[0];
tracer in tempMap ? tempMap[tracer] += 1 : tempMap[tracer] = 1;
}
leadCounter++;
}
}
if (terminate) {
break;
}
}
// here I need to update the leadArray, if not empty
//reminder: each subarray in leadArray: [current branchpoint, length]
if (leadArray.length > 0) {
leadArray[leadArray.length - 1][0]++;
while (leadArray[leadArray.length - 1][0] == leadArray[leadArray.length - 1][1]) {
//then remove last item from leadArray
leadArray.splice(leadArray.length - 1, 1);
if (leadArray.length == 0) {
break;
}
leadArray[leadArray.length - 1][0]++;
}
}
//console.log("one round over, path count: " + pathCount);
} while (leadArray.length != 0)
//now put the correct scores into the final map
//be careful, the return map uses letters as nodekeys! - one must transform, otherwise one gets rubbish
for (let key in tempMap) {
// console.log("tempMap element " + key);
// console.log(tempMap[key]);
let mapKey = nodeKeys[key];
map[mapKey] += tempMap[key] / pathCount;
}
}
}
}
return map;
}
export {
betweennessCentrality
};
/**
* Previous version created by ru on 14.09.17 is to be found below.
* Modifications by Rita on 28.02.2018 - now it can handle branchings too.
* CONTENTS:
* Brandes: according to Brandes 2001, it is meant for unweighted graphs (+undirected according to the paper, but runs fine on directed ones, too)
* BrandesForWeighted: according to Brandes 2007, handles WEIGHTED graphs, including graphs with null edges
* PFSdictBased: an alternative for our PFS, not heap based but dictionary based, however, not faster (see BetweennessTests)
*/
import * as $G from '../core/base/BaseGraph';
import * as $N from '../core/base/BaseNode';
import * as $P from '../traversal/PFS';
import * as $BF from '../traversal/BellmanFord';
import * as $JO from '../traversal/Johnsons';
import * as $BH from '../datastructs/BinaryHeap';
import {ComputeGraph, IComputeGraph} from "../core/compute/ComputeGraph";
export interface BrandesHeapEntry {
id: string;
best: number;
}
/**
* @param _graph input graph
* @returns Dict of betweenness centrality values for each node
*/
class Brandes {
private _cg: IComputeGraph;
constructor(private _graph: $G.IGraph) {
this._cg = new ComputeGraph(this._graph);
}
computeUnweighted(normalize: boolean = false, directed: boolean = false): {} {
if (this._graph.nrDirEdges() === 0 && this._graph.nrUndEdges() === 0) {
throw new Error("Cowardly refusing to traverse graph without edges.");
}
let nodes = this._graph.getNodes();
let adjList = this._cg.adjListW();
//Variables for Brandes algorithm
let s: $N.IBaseNode, //source node
v: string, //parent of w, at least one shortest path between s and w leads through v
w: string, //neighbour of v, lies one edge further than v from s
Pred: { [key: string]: string[] } = {}, //list of Predecessors=parent nodes
sigma: { [key: string]: number } = {}, //number of shortest paths from source s to each node as goal node
delta: { [key: string]: number } = {}, //dependency of source node s on a node
dist: { [key: string]: number } = {}, //distances from source node s to each node
Q: string[] = [], //Queue of nodes - nodes to visit
S: string[] = [], //stack of nodes - nodes waiting for their dependency values
CB: { [key: string]: number } = {}; //Betweenness values for each node
//info: push element to array - last position
//array.shift: returns and removes the first element - when used, array behaves as queue
//array.pop: returns and removes last element - when used, array behaves as stack
let closedNodes: { [key: string]: boolean } = {};
for (let n in nodes) {
let node_id = nodes[n].getID();
CB[node_id] = 0;
dist[node_id] = Number.POSITIVE_INFINITY;
sigma[node_id] = 0;
delta[node_id] = 0;
Pred[node_id] = [];
closedNodes[node_id] = false;
}
for (let i in nodes) {
s = nodes[i];
//Initialization
let id = s.getID();
dist[id] = 0;
sigma[id] = 1;
Q.push(id);
closedNodes[id] = true;
let counter = 0;
while (Q.length) { //Queue not empty
v = Q.shift();
S.push(v);
let neighbors = adjList[v];
closedNodes[v] = true;
for (let w in neighbors) {
if (closedNodes[w]) {
continue;
}
//Path discovery: w found for the first time?
if (dist[w] === Number.POSITIVE_INFINITY) {
Q.push(w);
dist[w] = dist[v] + 1;
}
//Path counting: edge (v,w) on shortest path?
if (dist[w] === dist[v] + 1) {
sigma[w] += sigma[v];
Pred[w].push(v);
}
}
}
//Accumulation: back-propagation of dependencies
while (S.length >= 1) {
w = S.pop();
for (let parent of Pred[w]) {
delta[parent] += (sigma[parent] / sigma[w] * (1 + delta[w]));
}
if (w != s.getID()) {
CB[w] += delta[w];
}
// This spares us from having to loop over all nodes again for initialization
sigma[w] = 0;
delta[w] = 0;
dist[w] = Number.POSITIVE_INFINITY;
Pred[w] = [];
closedNodes[w] = false;
}
}
if (normalize) {
this.normalizeScores(CB, this._graph.nrNodes(), directed);
}
return CB;
}
computeWeighted(normalize: boolean, directed: boolean): {} {
if (this._graph.nrDirEdges() === 0 && this._graph.nrUndEdges() === 0) {
throw new Error("Cowardly refusing to traverse graph without edges.");
}
if (this._graph.hasNegativeEdge()) {
var extraNode: $N.IBaseNode = new $N.BaseNode("extraNode");
let graph: $G.IGraph = $JO.addExtraNandE(this._graph, extraNode);
let BFresult = $BF.BellmanFordDict(graph, extraNode);
if (BFresult.neg_cycle) {
throw new Error("The graph contains a negative cycle, thus it can not be processed");
}
else {
let newWeights: {} = BFresult.distances;
graph = $JO.reWeighGraph(graph, newWeights, extraNode);
graph.deleteNode(extraNode);
}
this._graph = graph;
}
let nodes = this._graph.getNodes();
let N = Object.keys(nodes).length;
let adjList = this._cg.adjListW();
const evalPriority = (nb: BrandesHeapEntry) => nb.best;
const evalObjID = (nb: BrandesHeapEntry) => nb.id;
//Variables for Brandes algorithm
let s: $N.IBaseNode, //source node,
v: BrandesHeapEntry, //parent of w, at least one shortest path between s and w leads through v
w: string, //neighbour of v, lies one edge further than v from s, type id nodeID, alias string (got from AdjListDict)
Pred: { [key: string]: string[] } = {}, //list of Predecessors=parent nodes
sigma: { [key: string]: number } = {}, //number of shortest paths from source s to each node as goal node
delta: { [key: string]: number } = {}, //dependency of source node s on a node
dist: { [key: string]: number } = {}, //distances from source node s to each node
S: string[] = [], //stack of nodeIDs - nodes waiting for their dependency values
CB: { [key: string]: number } = {}, //Betweenness values for each node
closedNodes: { [key: string]: boolean } = {},
Q: $BH.BinaryHeap = new $BH.BinaryHeap($BH.BinaryHeapMode.MIN, evalPriority, evalObjID);
for (let n in nodes) {
let currID = nodes[n].getID();
CB[currID] = 0;
dist[currID] = Number.POSITIVE_INFINITY;
sigma[currID] = 0;
delta[currID] = 0;
Pred[currID] = [];
closedNodes[currID] = false;
}
for (let i in nodes) {
s = nodes[i];
let id_s = s.getID();
dist[id_s] = 0;
sigma[id_s] = 1;
let source: BrandesHeapEntry = { id: id_s, best: 0 };
Q.insert(source);
closedNodes[id_s] = true;
while (Q.size() > 0) {
v = Q.pop();
let current_id = v.id;
S.push(current_id);
closedNodes[current_id] = true;
let neighbors = adjList[current_id];
for (let w in neighbors) {
if (closedNodes[w]) {
continue;
}
let new_dist = dist[current_id] + neighbors[w];
let nextNode: BrandesHeapEntry = { id: w, best: dist[w] };
if (dist[w] > new_dist) {
if (isFinite(dist[w])) { //this means the node has already been encountered
let x = Q.remove(nextNode);
nextNode.best = new_dist;
Q.insert(nextNode);
}
else {
nextNode.best = new_dist;
Q.insert(nextNode);
}
sigma[w] = 0;
dist[w] = new_dist;
Pred[w] = [];
}
if (dist[w] === new_dist) {
sigma[w] += sigma[current_id];
Pred[w].push(current_id);
}
}
}
// Accumulation: back-propagation of dependencies
while (S.length >= 1) {
w = S.pop();
for (let parent of Pred[w]) {
delta[parent] += (sigma[parent] / sigma[w] * (1 + delta[w]));
}
if (w != s.getID()) {
CB[w] += delta[w];
}
// reset
sigma[w] = 0;
delta[w] = 0;
dist[w] = Number.POSITIVE_INFINITY;
Pred[w] = [];
closedNodes[w] = false;
}
}
if (normalize) {
this.normalizeScores(CB, N, directed);
}
return CB;
}
/**
*
* @param graph
* @param normalize
* @param directed
*
* @todo decide to remove or not
*/
computePFSbased(normalize: boolean, directed: boolean): {} {
let nodes = this._graph.getNodes();
let adjList = this._cg.adjListW();
//Variables for Brandes algorithm
let Pred: { [key: string]: string[] } = {}, //list of Predecessors=parent nodes
sigma: { [key: string]: number } = {}, //number of shortest paths from source s to each node as goal node
delta: { [key: string]: number } = {}, //dependency of source node s on a node
S: string[] = [], //stack of nodeIDs - nodes waiting for their dependency values
CB: { [key: string]: number } = {}; //Betweenness values for each node
for (let n in nodes) {
let currID = nodes[n].getID();
CB[currID] = 0;
sigma[currID] = 0;
delta[currID] = 0;
Pred[currID] = [];
}
let specialConfig: $P.PFS_Config = $P.preparePFSStandardConfig();
var notEncounteredBrandes = function (context: $P.PFS_Scope) {
context.next.best =
context.current.best + (isNaN(context.next.edge.getWeight()) ? $P.DEFAULT_WEIGHT : context.next.edge.getWeight());
//these needed for betweenness
let next_id = context.next.node.getID();
let current_id = context.current.node.getID();
Pred[next_id] = [current_id];
sigma[next_id] += sigma[current_id];
};
specialConfig.callbacks.not_encountered.splice(0, 1, notEncounteredBrandes);
var newCurrentBrandes = function (context: $P.PFS_Scope) {
S.push(context.current.node.getID());
};
specialConfig.callbacks.new_current.push(newCurrentBrandes);
var betterPathBrandes = function (context: $P.PFS_Scope) {
let next_id = context.next.node.getID();
let current_id = context.current.node.getID();
sigma[next_id] = 0;
sigma[next_id] += sigma[current_id];
Pred[next_id] = [];
Pred[next_id].push(current_id);
};
specialConfig.callbacks.better_path.splice(0, 1, betterPathBrandes);
/**
* @param context
*
* @todo figure out a faster way than .indexOf()
*/
var equalPathBrandes = function (context: $P.PFS_Scope) {
let next_id = context.next.node.getID();
let current_id = context.current.node.getID();
sigma[next_id] += sigma[current_id];
//other approach needed to avoid duplicates
if (Pred[next_id].indexOf(current_id) === -1) {
Pred[next_id].push(current_id);
}
};
specialConfig.callbacks.equal_path.push(equalPathBrandes);
for (let i in nodes) {
let s = nodes[i];
sigma[s.getID()] = 1;
$P.PFS(this._graph, s, specialConfig)
//step: do the scoring, using S, Pred and sigma
while (S.length >= 1) {
let w = S.pop();
for (let parent of Pred[w]) {
delta[parent] += (sigma[parent] / sigma[w] * (1 + delta[w]));
}
if (w != s.getID()) {
CB[w] += delta[w];
}
//This spares us from having to loop over all nodes again for initialization
sigma[w] = 0;
delta[w] = 0;
Pred[w] = [];
}
}
if (normalize) {
this.normalizeScores(CB, this._graph.nrNodes(), directed);
}
return CB;
}
normalizeScores(CB, N, directed) {
let factor = directed ? ((N - 1) * (N - 2)) : ((N - 1) * (N - 2) / 2);
for (let node in CB) {
CB[node] /= factor;
}
}
}
export {
Brandes
}
/*
Calculates the shortest path to all others via PFS (could use Dijkstra as well...)
*/
import * as $G from '../core/base/BaseGraph';
import * as $PFS from '../traversal/PFS';
import * as $FW from '../traversal/FloydWarshall';
//Calculates all the shortest path's to all other nodes for all given nodes in the graph
//Returns a map with every node as key and the average distance to all other nodes as value
class ClosenessCentrality{
constructor() {}
getCentralityMapFW(graph: $G.IGraph): Array<Number> {
let dists = $FW.FloydWarshallArray(graph);
let ret:Array<Number> = [];
let N = dists.length;
for (let a = 0; a < N; ++a) {
let sum = 0;
for (let b = 0; b < N; ++b) {
if(dists[a][b]!=Number.POSITIVE_INFINITY)
sum += dists[a][b];
}
ret[a] = 1/sum;
}
return ret;
}
getCentralityMap(graph: $G.IGraph): {[id: string]: number} {
let pfs_config:$PFS.PFS_Config = $PFS.preparePFSStandardConfig();
let accumulated_distance = 0;
//set the config (we want the sum of all edges to become a property of result)
//a node is encountered the first time
let not_encountered = function( context : $PFS.PFS_Scope ) {
// adding the distance to the accumulated distance
accumulated_distance += context.current.best + (isNaN(context.next.edge.getWeight()) ? 1 : context.next.edge.getWeight());
};
//We found a better path, we need to correct the accumulated distance
let betterPathFound = function( context: $PFS.PFS_Scope ) {
//console.log("correcting distance "+context.current.node.getID()+"->"+context.next.node.getID()+" from " + pfs_config.result[context.next.node.getID()].distance + "to" + context.better_dist);
accumulated_distance -= pfs_config.result[context.next.node.getID()].distance - context.proposed_dist;
};
let bp = pfs_config.callbacks.better_path.pop(); //change the order, otherwise our betterPathFound would not do anything
pfs_config.callbacks.better_path.push(betterPathFound);
pfs_config.callbacks.better_path.push(bp);
pfs_config.callbacks.not_encountered.push(not_encountered);
let ret:{[id:string]: number} = {};
for (let key in graph.getNodes()) {
let node = graph.getNodeById(key);
if (node != null) {
accumulated_distance = 0;
$PFS.PFS(graph, node, pfs_config);
ret[key] = 1/accumulated_distance;
}
}
return ret;
}
}
export {
ClosenessCentrality
};
import * as $N from '../core/base/BaseNode';
import * as $G from '../core/base/BaseGraph';
import * as $SU from '../utils/StructUtils'
export enum DegreeMode {
in,
out,
und,
dir,
all
}
/**
* @todo per edge type ???
*/
export interface DegreeDistribution {
in : Uint32Array;
out : Uint32Array;
dir : Uint32Array;
und : Uint32Array;
all : Uint32Array;
}
class DegreeCentrality {
constructor(){}
getCentralityMap( graph: $G.IGraph, weighted?: boolean, conf?: DegreeMode):{[id:string]: number} {
weighted = ( weighted != null ) ? !!weighted : true;
conf = ( conf == null ) ? DegreeMode.all : conf;
let ret:{[id:string]: number} = {}; //Will be a map of [nodeID] = centrality
switch(conf){ //Switch on the outside for faster loops
case DegreeMode.in:
for(let key in graph.getNodes()) {
let node = graph.getNodeById(key);
if(node!=null) {
if(!weighted) {
ret[key] = node.in_deg;
}
else {
ret[key] = ret[key]||0;
for(let k in node.inEdges()) {
ret[key] += node.inEdges()[k].getWeight();
}
}
}
}
break;
case DegreeMode.out:
for(let key in graph.getNodes()) {
let node = graph.getNodeById(key);
if(node!=null) {
if(!weighted) {
ret[key] = node.out_deg;
}
else {
ret[key] = ret[key]||0;
for(let k in node.outEdges()) {
ret[key] += node.outEdges()[k].getWeight();
}
}
}
}
break;
case DegreeMode.und:
for(let key in graph.getNodes()) {
let node = graph.getNodeById(key);
if(node!=null) {
if(!weighted) {
ret[key] = node.deg;
}
else {
ret[key] = ret[key]||0;
for(let k in node.undEdges()) {
ret[key] += node.undEdges()[k].getWeight();
}
}
}
}
break;
case DegreeMode.dir:
for(let key in graph.getNodes()) {
let node = graph.getNodeById(key);
if(node!=null) {
if(!weighted) {
ret[key] = node.in_deg + node.out_deg;
}
else {
ret[key] = ret[key]||0;
let comb = $SU.mergeObjects([node.inEdges(), node.outEdges()]);
for(let k in comb) {
ret[key] += comb[k].getWeight();
}
}
}
}
break;
case DegreeMode.all:
for(let key in graph.getNodes()) {
let node = graph.getNodeById(key);
if(node!=null) {
if(!weighted) {
ret[key] = node.deg + node.in_deg + node.out_deg;
}
else {
ret[key] = ret[key]||0;
let comb = $SU.mergeObjects([node.inEdges(), node.outEdges(), node.undEdges()]);
for(let k in comb) {
ret[key] += comb[k].getWeight();
}
}
}
}
break;
}
return ret;
}
/**
* @TODO Weighted version !
* @TODO per edge type !
*/
degreeDistribution(graph: $G.IGraph) {
let max_deg : number = 0,
key : string,
nodes : {[id: string] : $N.IBaseNode} = graph.getNodes(),
node : $N.IBaseNode,
all_deg : number;
for ( key in nodes ) {
node = nodes[key];
all_deg = node.in_deg + node.out_deg + node.deg + 1;
max_deg = all_deg > max_deg ? all_deg : max_deg;
}
let deg_dist : DegreeDistribution = {
in: new Uint32Array(max_deg),
out: new Uint32Array(max_deg),
dir: new Uint32Array(max_deg),
und: new Uint32Array(max_deg),
all: new Uint32Array(max_deg)
};
for ( key in nodes ) {
node = nodes[key];
deg_dist.in[node.in_deg]++;
deg_dist.out[node.out_deg]++;
deg_dist.dir[node.in_deg + node.out_deg]++;
deg_dist.und[node.deg]++;
deg_dist.all[node.in_deg + node.out_deg + node.deg]++;
}
// console.dir(deg_dist);
return deg_dist;
}
}
export {
DegreeCentrality
};
import { IGraph, BaseGraph } from '../core/base/BaseGraph';
import { IBaseNode } from '../core/base/BaseNode';
import { IBaseEdge } from '../core/base/BaseEdge';
import { mergeObjects } from "../utils/StructUtils";
// import { Logger } from "../utils/Logger";
// const logger = new Logger();
const DEFAULT_WEIGHTED = false;
const DEFAULT_ALPHA = 0.15;
const DEFAULT_MAX_ITERATIONS = 1e3;
const DEFAULT_EPSILON = 1e-6;
const DEFAULT_NORMALIZE = false;
const defaultInit = (graph: IGraph) => 1 / graph.nrNodes();
export type InitMap = { [id: string]: number };
export type TeleSet = { [id: string]: number };
export type RankMap = { [id: string]: number };
/**
* Data structs we need for the array version of centralities
*
* @description we assume that nodes are always in the same order in the various arrays,
* with the exception of the pull sub-arrays, of course (which give the node index as values)
*
* @todo guarantee that the graph doesn't change during that mapping -> unmapping process
* already guaranteed by the single-threadedness of JS/Node, unless we build workers into it...
*/
export interface PRArrayDS {
curr: Array<number>;
old: Array<number>;
out_deg: Array<number>;
pull: Array<Array<number>>;
pull_weight?: Array<Array<number>>;
teleport?: Array<number>;
tele_size?: number;
}
/**
* Configuration object for PageRank class
*/
export interface PagerankRWConfig {
weighted?: boolean;
alpha?: number;
epsilon?: number;
maxIterations?: number;
normalize?: boolean;
PRArrays?: PRArrayDS;
personalized?: boolean;
tele_set?: TeleSet;
init_map?: InitMap;
}
/**
* Pagerank result type
*/
export interface PRResult {
map: RankMap;
config: PagerankRWConfig;
iters: number;
delta: number;
}
/**
* PageRank for all nodes of a given graph by performing Random Walks
* Implemented to give the same results as the NetworkX implementation, just faster!
*
* @description We assume that all necessary properties of a node's feature vector
* has been incorporated into it's initial rank or the link structure
* of the graph. This means we carefully have to construct our graph
* before interpreting Pagerank as anything meaninful for a particular
* application.
*
* @todo find a paper / article detailing this implementation (it's the networkx numpy version...)
* @todo compute a ground truth for our sample social networks (python!)
* @todo compute a ground truth for our jobs / beer / northwind / meetup sample graphs (neo4j / networkx)
*/
class Pagerank {
private readonly _weighted: boolean;
private readonly _alpha: number;
private readonly _epsilon: number;
private readonly _maxIterations: number;
private readonly _normalize: boolean;
private readonly _personalized: boolean;
/**
* Holds all the data structures necessary to compute PR in LinAlg form
*/
private readonly _PRArrayDS: PRArrayDS;
constructor(private _graph: IGraph, config?: PagerankRWConfig) {
config = config || {}; // just so we don't get `property of undefined` errors below
this._weighted = config.weighted || DEFAULT_WEIGHTED;
this._alpha = config.alpha || DEFAULT_ALPHA;
this._maxIterations = config.maxIterations || DEFAULT_MAX_ITERATIONS;
this._epsilon = config.epsilon || DEFAULT_EPSILON;
this._normalize = config.normalize || DEFAULT_NORMALIZE;
this._personalized = config.personalized ? config.personalized : false;
if (this._personalized && !config.tele_set) {
throw Error("Personalized Pagerank requires tele_set as a config argument");
}
if (config.init_map && Object.keys(config.init_map).length !== this._graph.nrNodes()) {
throw Error("init_map config parameter must be of size |nodes|");
}
this._PRArrayDS = config.PRArrays || {
curr: [],
old: [],
out_deg: [],
pull: [],
pull_weight: this._weighted ? [] : null,
teleport: config.tele_set ? [] : null,
tele_size: config.tele_set ? 0 : null
};
config.PRArrays || this.constructPRArrayDataStructs(config);
// logger.log(JSON.stringify(this._PRArrayDS));
}
getConfig() : PagerankRWConfig {
return {
weighted: this._weighted,
alpha: this._alpha,
maxIterations: this._maxIterations,
epsilon: this._epsilon,
normalize: this._normalize
}
}
getDSs() {
return this._PRArrayDS;
}
constructPRArrayDataStructs(config: PagerankRWConfig) {
let tic = +new Date;
let nodes = this._graph.getNodes();
let i = 0;
let teleport_prob_sum = 0;
let init_sum = 0;
for (let key in nodes) {
let node = this._graph.getNodeById(key);
// set identifier to re-map later..
node.setFeature('PR_index', i);
if (config.init_map) {
if (config.init_map[key] == null) {
throw Error("initial value must be given for each node in the graph.");
}
let val = config.init_map[key];
this._PRArrayDS.curr[i] = val;
this._PRArrayDS.old[i] = val;
init_sum += val;
}
else {
this._PRArrayDS.curr[i] = defaultInit(this._graph);
this._PRArrayDS.old[i] = defaultInit(this._graph);
}
this._PRArrayDS.out_deg[i] = node.out_deg + node.deg;
/**
* @todo enhance this to actual weights!?
* @todo networkX requires a dict the size of the inputs, which is cumbersome for larger graphs
* we want to do this smarter, but can we omit large parts of the (pseudo-)sparse matrix?
* - where pseudo-sparse means containing only implicit values (jump chances)
*/
if (this._personalized) {
let tele_prob_node = config.tele_set[node.getID()] || 0;
this._PRArrayDS.teleport[i] = tele_prob_node;
teleport_prob_sum += tele_prob_node;
tele_prob_node && this._PRArrayDS.tele_size++;
}
++i;
}
// normalize init values
if (config.init_map && init_sum !== 1) {
this._PRArrayDS.curr = this._PRArrayDS.curr.map(n => n /= init_sum);
this._PRArrayDS.old = this._PRArrayDS.old.map(n => n /= init_sum);
}
// normalize teleport probabilities
if (this._personalized && teleport_prob_sum !== 1) {
this._PRArrayDS.teleport = this._PRArrayDS.teleport.map(n => n /= teleport_prob_sum);
}
/**
* We can only do this once all the mappings [node_id => arr_idx] have been established!
*/
for (let key in nodes) {
let node = this._graph.getNodeById(key);
let node_idx = node.getFeature('PR_index');
// set nodes to pull from
let pull_i = [];
let pull_weight_i = [];
let incoming_edges = mergeObjects([node.inEdges(), node.undEdges()]);
for (let edge_key in incoming_edges) {
let edge: IBaseEdge = incoming_edges[edge_key];
let source: IBaseNode = edge.getNodes().a;
if (edge.getNodes().a.getID() == node.getID()) {
source = edge.getNodes().b;
}
let parent_idx = source.getFeature('PR_index');
if (this._weighted) {
pull_weight_i.push(edge.getWeight());
}
pull_i.push(parent_idx);
}
this._PRArrayDS.pull[node_idx] = pull_i;
/**
* @todo test!
*/
if (this._weighted) {
this._PRArrayDS.pull_weight[node_idx] = pull_weight_i;
}
}
let toc = +new Date;
// logger.log(`PR Array DS init took ${toc - tic} ms.`);
}
getRankMapFromArray() : RankMap {
let result: RankMap = {};
let nodes = this._graph.getNodes();
if (this._normalize) {
this.normalizePR();
}
for (let key in nodes) {
result[key] = this._PRArrayDS.curr[nodes[key].getFeature('PR_index')];
}
return result;
}
private normalizePR() {
let pr_sum = this._PRArrayDS.curr.reduce((i, j) => i + j, 0);
if (pr_sum !== 1) {
this._PRArrayDS.curr = this._PRArrayDS.curr.map(n => n / pr_sum);
}
}
pull2DTo1D(): Array<number> {
let p1d = [];
let p2d = this._PRArrayDS.pull;
for (let n in p2d) {
for (let i of p2d[n]) {
p1d.push(i);
}
+n !== p2d.length - 1 && p1d.push(-1);
}
return p1d;
}
computePR() : PRResult {
const ds = this._PRArrayDS;
const N = this._graph.nrNodes();
// debug
let visits = 0;
let delta_iter: number;
for (let i = 0; i < this._maxIterations; ++i) {
delta_iter = 0.0;
// node is number...
for (let node in ds.curr) {
let pull_rank = 0;
visits++;
let idx = 0;
for (let source of ds.pull[node]) {
visits++;
/**
* This should never happen....
* IF the data structure _PRArrayDS was properly constructed
*
* @todo properly test _PRArrayDS as well as this beauty
* (using a contrived, wrongly constructed pull 2D array)
*/
if (ds.out_deg[source] === 0) {
throw ('Encountered zero divisor!');
}
let weight = this._weighted ? ds.pull_weight[node][idx++] : 1.0;
pull_rank += ds.old[source] * weight / ds.out_deg[source];
}
let link_pr = (1 - this._alpha) * pull_rank;
if (this._personalized) {
let jump_chance = ds.teleport[node] / ds.tele_size; // 0/x = 0
ds.curr[node] = link_pr + jump_chance;
}
else {
// logger.log(`Pulling PR for node ${node}: ${link_pr + this._alpha / N}`);
ds.curr[node] = link_pr + this._alpha / N;
}
delta_iter += Math.abs(ds.curr[node] - ds.old[node]);
}
if (delta_iter <= this._epsilon) {
// logger.log(`CONVERGED after ${i} iterations with ${visits} visits and a final delta of ${delta_iter}.`);
return {
config: this.getConfig(),
map: this.getRankMapFromArray(),
iters: i,
delta: delta_iter
};
}
ds.old = [...ds.curr];
}
// logger.log(`ABORTED after ${this._maxIterations} iterations with ${visits} visits.`);
return {
config: this.getConfig(),
map: this.getRankMapFromArray(),
iters: this._maxIterations,
delta: delta_iter
};
}
}
export { Pagerank }
const CMD_ENV_LOG = 'G_LOG';
const GENERIC_TYPES = {
Node : 'GENERIC',
Edge : 'GENERIC',
Graph : 'GENERIC'
};
const LOG_LEVELS = {
debug: 'debug',
production: 'production'
};
/**
* Also checking if CMD line argument is given, which might not be the case
* when running automated test cases.
*/
function runLevel() {
let log_level = LOG_LEVELS.production;
if ( typeof window === 'undefined' && typeof process !== 'undefined' && process.env && process.env[CMD_ENV_LOG]) {
log_level = process.env[CMD_ENV_LOG]
}
return log_level;
}
export {
LOG_LEVELS,
GENERIC_TYPES,
runLevel
};
import * as $N from "./BaseNode";
import { TypedEdge } from '../typed/TypedEdge';
import * as $SU from "../../utils/StructUtils";
export interface IConnectedNodes {
a: $N.IBaseNode;
b: $N.IBaseNode;
}
export type EdgeFeatures = { [k:string]: any };
/**
* Edges are the most basic components in graphinius.
* They control no other elements below them, but hold
* references to the nodes they are connecting...
* @param _id internal id, public
* @param _label edge label, public
*/
export interface IBaseEdge {
/**
* Getters
*/
readonly id: string;
readonly label: string;
readonly features: EdgeFeatures;
getID() : string;
getLabel() : string;
setLabel(label : string) : void;
// FEATURES methods
getFeatures() : EdgeFeatures;
getFeature(key: string) : any;
f(key:string) : any | undefined; // shortcut for getFeature
setFeatures( features: EdgeFeatures ) : void;
setFeature(key: string, value: any) : void;
deleteFeature(key: string) : any;
clearFeatures() : void;
isDirected() : boolean;
isWeighted() : boolean;
getWeight() : number; // Exception if not weighted
setWeight(w:number) : void; // Exception if not weighted
getNodes() : IConnectedNodes;
clone(node_a : $N.BaseNode, node_b : $N.BaseNode) : IBaseEdge;
/**
* An edge should either be directed or not, weighted or not.
* Changing those properties on live edges is not allowed,
* rather delete the edge and construct a new one altogether
*/
// setDirected(d:boolean) : void;
// setWeighted(w:boolean) : void;
}
export interface BaseEdgeConfig {
directed? : boolean;
weighted? : boolean;
weight? : number;
label? : string;
features? : EdgeFeatures;
}
class BaseEdge implements IBaseEdge {
protected _directed : boolean;
protected _weighted : boolean;
protected _weight : number;
protected _label : string;
protected _features : EdgeFeatures;
constructor (protected _id: string,
protected _node_a: $N.IBaseNode,
protected _node_b: $N.IBaseNode,
config?: BaseEdgeConfig)
{
if( !( _node_a instanceof $N.BaseNode ) || !( _node_b instanceof $N.BaseNode ) ) {
throw new Error("cannot instantiate edge without two valid node objects");
}
config = config || {};
this._directed = config.directed || false;
this._weighted = config.weighted || false;
// @NOTE isNaN and Number.isNaN confusion...
this._weight = this._weighted ? ( isNaN(config.weight) ? 1 : config.weight ) : undefined;
this._label = config.label || this._id;
this._features = config.features != null ? $SU.clone(config.features) : {};
}
get id(): string {
return this._id;
}
get label(): string {
return this._label;
}
get features(): EdgeFeatures {
return this._features;
}
getID() : string {
return this._id;
}
getLabel() : string {
return this._label;
}
setLabel(label : string) : void {
this._label = label;
}
getFeatures() : { [k:string] : any } {
return this._features;
}
getFeature(key: string) : any | undefined {
return this._features[key];
}
f(key:string) : any | undefined {
return this.getFeature(key);
}
setFeatures( features: { [k:string]: any } ) : void {
this._features = $SU.clone(features);
}
setFeature(key: string, value: any) : void {
this._features[key] = value;
}
deleteFeature(key: string) : any {
let feat = this._features[key];
delete this._features[key];
return feat;
}
clearFeatures() : void {
this._features = {};
}
isDirected () : boolean {
return this._directed;
}
isWeighted () : boolean {
return this._weighted;
}
getWeight() : number {
return this._weight;
}
setWeight(w:number) : void {
if ( !this._weighted ) {
throw new Error("Cannot set weight on unweighted edge.");
}
this._weight = w;
}
getNodes() : IConnectedNodes {
return {a: this._node_a, b: this._node_b};
}
clone(new_node_a : $N.BaseNode, new_node_b : $N.BaseNode) : BaseEdge {
if( !( new_node_a instanceof $N.BaseNode ) || !( new_node_b instanceof $N.BaseNode ) ) {
throw new Error("refusing to clone edge if any new node is invalid");
}
return new BaseEdge(
this._id,
new_node_a,
new_node_b,
{
directed : this._directed,
weighted : this._weighted,
weight : this._weight,
label : this._label
}
);
}
static isTyped(arg: any): arg is TypedEdge {
return !!arg.type;
}
}
export { BaseEdge };
import {
DIR,
GraphMode,
GraphStats,
NextArray,
MinAdjacencyListArray,
MinAdjacencyListDict
} from '../interfaces';
import { IBaseNode, BaseNode } from './BaseNode';
import { BaseEdgeConfig, IBaseEdge, BaseEdge } from './BaseEdge';
import { prepareBFSStandardConfig, BFS, BFS_Scope } from '../../traversal/BFS';
import { DFS } from '../../traversal/DFS';
import { BellmanFordDict, BellmanFordArray } from '../../traversal/BellmanFord';
import { reWeighGraph, addExtraNandE } from '../../traversal/Johnsons';
import { TypedGraph } from "../typed/TypedGraph";
const DEFAULT_WEIGHT = 1;
export interface IGraph {
/**
* Getters
*/
readonly label: string;
readonly mode: GraphMode;
readonly stats: GraphStats;
// readonly adj_list: MinAdjacencyListArray;
// ANALYSIS
getMode(): GraphMode;
getStats(): GraphStats;
// HISTOGRAM
readonly inHist: Set<number>[];
readonly outHist: Set<number>[];
readonly connHist: Set<number>[];
// NODES
addNode(node: IBaseNode): IBaseNode;
addNodeByID(id: string, opts?: {}): IBaseNode;
hasNodeID(id: string): boolean;
getNodeById(id: string): IBaseNode;
n(id: string): IBaseNode;
getNodes(): { [key: string]: IBaseNode };
nrNodes(): number;
getRandomNode(): IBaseNode;
deleteNode(node): void;
// EDGES
addEdge(edge: IBaseEdge): IBaseEdge;
addEdgeByID(label: string, node_a: IBaseNode, node_b: IBaseNode, opts?: {}): IBaseEdge;
addEdgeByNodeIDs(label: string, node_a_id: string, node_b_id: string, opts?: {}): IBaseEdge;
hasEdgeID(id: string): boolean;
getEdgeById(id: string): IBaseEdge;
getDirEdgeByNodeIDs(node_a_id: string, node_b_id: string): IBaseEdge;
getUndEdgeByNodeIDs(node_a_id: string, node_b_id: string): IBaseEdge;
getDirEdges(): { [key: string]: IBaseEdge };
getUndEdges(): { [key: string]: IBaseEdge };
getDirEdgesArray(): Array<IBaseEdge>;
getUndEdgesArray(): Array<IBaseEdge>;
nrDirEdges(): number;
nrUndEdges(): number;
deleteEdge(edge: IBaseEdge): void;
getRandomDirEdge(): IBaseEdge;
getRandomUndEdge(): IBaseEdge;
// NEGATIVE EDGES AND CYCLES
hasNegativeEdge(): boolean
hasNegativeCycles(node?: IBaseNode): boolean;
// REINTERPRETING EDGES
toDirectedGraph(copy?): IGraph;
toUndirectedGraph(): IGraph;
// PROPERTIES
pickRandomProperty(propList): any;
pickRandomProperties(propList, amount): Array<string>;
// HANDLE ALL EDGES OF NODES
deleteInEdgesOf(node: IBaseNode): void;
deleteOutEdgesOf(node: IBaseNode): void;
deleteDirEdgesOf(node: IBaseNode): void;
deleteUndEdgesOf(node: IBaseNode): void;
deleteAllEdgesOf(node: IBaseNode): void;
// HANDLE ALL EDGES IN GRAPH
clearAllDirEdges(): void;
clearAllUndEdges(): void;
clearAllEdges(): void;
// CLONING
cloneStructure(): IGraph;
cloneSubGraphStructure(start: IBaseNode, cutoff: Number): IGraph;
// REWEIGHTING
reweighIfHasNegativeEdge(clone: boolean): IGraph;
}
class BaseGraph implements IGraph {
protected _nr_nodes = 0;
protected _nr_dir_edges = 0;
protected _nr_und_edges = 0;
protected _mode: GraphMode = GraphMode.INIT;
protected _nodes: { [key: string]: IBaseNode } = {};
protected _dir_edges: { [key: string]: IBaseEdge } = {};
protected _und_edges: { [key: string]: IBaseEdge } = {};
constructor(protected _label) { }
static isTyped(arg: any): arg is TypedGraph {
return !!arg.type;
}
get label(): string {
return this._label;
}
get mode(): GraphMode {
return this._mode;
}
get stats(): GraphStats {
return this.getStats();
}
get inHist(): Set<number>[] {
return this.degreeHist(DIR.in);
}
get outHist(): Set<number>[] {
return this.degreeHist(DIR.out);
}
get connHist(): Set<number>[] {
return this.degreeHist(DIR.und);
}
private degreeHist(dir: string): Set<number>[] {
let result = [];
for (let nid in this._nodes) {
let node = this._nodes[nid];
let deg;
switch (dir) {
case DIR.in:
deg = node.in_deg;
break;
case DIR.out:
deg = node.out_deg;
break;
default:
deg = node.deg;
}
if (!result[deg]) {
result[deg] = new Set([node]);
}
else {
result[deg].add(node);
}
}
return result;
}
/**
*
* @param clone
*
* @comment Convenience method -
* Tests to be found in test suites for
* BaseGraph, BellmanFord and Johnsons
*/
reweighIfHasNegativeEdge(clone: boolean = false): IGraph {
if (this.hasNegativeEdge()) {
let result_graph: IGraph = clone ? this.cloneStructure() : this;
let extraNode: IBaseNode = new BaseNode("extraNode");
result_graph = addExtraNandE(result_graph, extraNode);
let BFresult = BellmanFordDict(result_graph, extraNode);
if (BFresult.neg_cycle) {
throw new Error("The graph contains a negative cycle, thus it can not be processed");
}
else {
let newWeights: {} = BFresult.distances;
result_graph = reWeighGraph(result_graph, newWeights, extraNode);
result_graph.deleteNode(extraNode);
}
return result_graph;
}
}
/**
* Version 1: do it in-place (to the object you receive)
* Version 2: clone the graph first, return the mutated clone
*/
toDirectedGraph(copy = false): IGraph {
let result_graph = copy ? this.cloneStructure() : this;
// if graph has no edges, we want to throw an exception
if (this._nr_dir_edges === 0 && this._nr_und_edges === 0) {
throw new Error("Cowardly refusing to re-interpret an empty graph.")
}
return result_graph;
}
/**
* @todo implement!!!
*/
toUndirectedGraph(): IGraph {
return this;
}
/**
* what to do if some edges are not weighted at all?
* Since graph traversal algortihms (and later maybe graphs themselves)
* use default weights anyways, I am simply ignoring them for now...
* @todo figure out how to test this...
*/
hasNegativeEdge(): boolean {
let has_neg_edge = false,
edge: IBaseEdge;
// negative und_edges are always negative cycles
for (let edge_id in this._und_edges) {
edge = this._und_edges[edge_id];
if (!edge.isWeighted()) {
continue;
}
if (edge.getWeight() < 0) {
return true;
}
}
for (let edge_id in this._dir_edges) {
edge = this._dir_edges[edge_id];
if (!edge.isWeighted()) {
continue;
}
if (edge.getWeight() < 0) {
has_neg_edge = true;
break;
}
}
return has_neg_edge;
}
/**
* Do we want to throw an error if an edge is unweighted?
* Or shall we let the traversal algorithm deal with DEFAULT weights like now?
*/
hasNegativeCycles(node?: IBaseNode): boolean {
if (!this.hasNegativeEdge()) {
return false;
}
let negative_cycle = false,
start = node ? node : this.getRandomNode();
/**
* Now do Bellman Ford over all graph components
*/
DFS(this, start).forEach(comp => {
let min_count = Number.POSITIVE_INFINITY,
comp_start_node: string = "";
Object.keys(comp).forEach(node_id => {
if (min_count > comp[node_id].counter) {
min_count = comp[node_id].counter;
comp_start_node = node_id;
}
});
if (BellmanFordArray(this, this._nodes[comp_start_node]).neg_cycle) {
negative_cycle = true;
}
});
return negative_cycle;
}
getMode(): GraphMode {
return this._mode;
}
getStats(): GraphStats {
return {
mode: this._mode,
nr_nodes: this._nr_nodes,
nr_und_edges: this._nr_und_edges,
nr_dir_edges: this._nr_dir_edges,
density_dir: this._nr_dir_edges / (this._nr_nodes * (this._nr_nodes - 1)),
density_und: 2 * this._nr_und_edges / (this._nr_nodes * (this._nr_nodes - 1))
}
}
nrNodes(): number {
return this._nr_nodes;
}
nrDirEdges(): number {
return this._nr_dir_edges;
}
nrUndEdges(): number {
return this._nr_und_edges;
}
/**
*
* @param id
* @param opts
*
* @todo addNode functions should check if a node with a given ID already exists -> node IDs have to be unique...
*/
addNodeByID(id: string, opts?: {}): IBaseNode {
if (this.hasNodeID(id)) {
throw new Error("Won't add node with duplicate ID.");
}
let node = new BaseNode(id, opts);
return this.addNode(node) ? node : null;
}
addNode(node: IBaseNode): IBaseNode {
if (this.hasNodeID(node.getID())) {
throw new Error("Won't add node with duplicate ID.");
}
this._nodes[node.getID()] = node;
this._nr_nodes += 1;
return node;
}
hasNodeID(id: string): boolean {
return !!this._nodes[id];
}
getNodeById(id: string): IBaseNode {
return this._nodes[id];
}
n(id: string): IBaseNode {
return this.getNodeById(id);
}
getNodes(): { [key: string]: IBaseNode } {
return this._nodes;
}
/**
* CAUTION - This function takes linear time in # nodes
*/
getRandomNode(): IBaseNode {
return this.pickRandomProperty(this._nodes);
}
deleteNode(node): void {
let rem_node = this._nodes[node.getID()];
if (!rem_node) {
throw new Error('Cannot remove a foreign node.');
}
// Edges?
let in_deg = node.in_deg;
let out_deg = node.out_deg;
let deg = node.deg;
// Delete all edges brutally...
if (in_deg) {
this.deleteInEdgesOf(node);
}
if (out_deg) {
this.deleteOutEdgesOf(node);
}
if (deg) {
this.deleteUndEdgesOf(node);
}
delete this._nodes[node.getID()];
this._nr_nodes -= 1;
}
hasEdgeID(id: string): boolean {
return !!this._dir_edges[id] || !!this._und_edges[id];
}
getEdgeById(id: string): IBaseEdge {
let edge = this._dir_edges[id] || this._und_edges[id];
if (!edge) {
throw new Error("cannot retrieve edge with non-existing ID.");
}
return edge;
}
static checkExistanceOfEdgeNodes(node_a: IBaseNode, node_b: IBaseNode): void {
if (!node_a) {
throw new Error(`Cannot find edge. Node A does not exist (in graph).`);
}
if (!node_b) {
throw new Error("Cannot find edge. Node B does not exist (in graph).");
}
}
// get the edge from node_a to node_b (or undirected)
getDirEdgeByNodeIDs(node_a_id: string, node_b_id: string) {
const node_a = this.getNodeById(node_a_id);
const node_b = this.getNodeById(node_b_id);
BaseGraph.checkExistanceOfEdgeNodes(node_a, node_b);
// check for outgoing directed edges
let edges_dir = node_a.outEdges(),
edges_dir_keys = Object.keys(edges_dir);
for (let i = 0; i < edges_dir_keys.length; i++) {
let edge = edges_dir[edges_dir_keys[i]];
if (edge.getNodes().b.getID() == node_b_id) {
return edge;
}
}
// if we managed to arrive here, there is no edge!
throw new Error(`Cannot find edge. There is no edge between Node ${node_a_id} and ${node_b_id}.`);
}
getUndEdgeByNodeIDs(node_a_id: string, node_b_id: string) {
const node_a = this.getNodeById(node_a_id);
const node_b = this.getNodeById(node_b_id);
BaseGraph.checkExistanceOfEdgeNodes(node_a, node_b);
// check for undirected edges
let edges_und = node_a.undEdges(),
edges_und_keys = Object.keys(edges_und);
for (let i = 0; i < edges_und_keys.length; i++) {
let edge = edges_und[edges_und_keys[i]];
let b: string;
(edge.getNodes().a.getID() == node_a_id) ? (b = edge.getNodes().b.getID()) : (b = edge.getNodes().a.getID());
if (b == node_b_id) {
return edge;
}
}
}
getDirEdges(): { [key: string]: IBaseEdge } {
return this._dir_edges;
}
getUndEdges(): { [key: string]: IBaseEdge } {
return this._und_edges;
}
getDirEdgesArray(): Array<IBaseEdge> {
let edges = [];
for (let e_id in this._dir_edges) {
edges.push(this._dir_edges[e_id]);
}
return edges;
}
getUndEdgesArray(): Array<IBaseEdge> {
let edges = [];
for (let e_id in this._und_edges) {
edges.push(this._und_edges[e_id]);
}
return edges;
}
addEdgeByNodeIDs(label: string, node_a_id: string, node_b_id: string, opts?: {}): IBaseEdge {
let node_a = this.getNodeById(node_a_id),
node_b = this.getNodeById(node_b_id);
if (!node_a) {
throw new Error("Cannot add edge. Node A does not exist");
}
else if (!node_b) {
throw new Error("Cannot add edge. Node B does not exist");
}
else {
return this.addEdgeByID(label, node_a, node_b, opts);
}
}
/**
* @description now all test cases pertaining addEdge() call this one...
*/
addEdgeByID(id: string, node_a: IBaseNode, node_b: IBaseNode, opts?: BaseEdgeConfig): IBaseEdge {
let edge = new BaseEdge(id, node_a, node_b, opts || {});
return this.addEdge(edge) ? edge : null;
}
/**
* @todo test cases should be reversed / completed
* @todo make transactional
*/
addEdge(edge: IBaseEdge): IBaseEdge {
let node_a = edge.getNodes().a,
node_b = edge.getNodes().b;
if (!this.hasNodeID(node_a.getID()) || !this.hasNodeID(node_b.getID())
|| this._nodes[node_a.getID()] !== node_a || this._nodes[node_b.getID()] !== node_b
) {
throw new Error("can only add edge between two nodes existing in graph");
}
// connect edge to first node anyways
node_a.addEdge(edge);
if (edge.isDirected()) {
// add edge to second node too
node_b.addEdge(edge);
this._dir_edges[edge.getID()] = edge;
this._nr_dir_edges += 1;
this.updateGraphMode();
}
else {
// add edge to both nodes, except they are the same...
if (node_a !== node_b) {
node_b.addEdge(edge);
}
this._und_edges[edge.getID()] = edge;
this._nr_und_edges += 1;
this.updateGraphMode();
}
return edge;
}
deleteEdge(edge: IBaseEdge): void {
let dir_edge = this._dir_edges[edge.getID()];
let und_edge = this._und_edges[edge.getID()];
if (!dir_edge && !und_edge) {
throw new Error('cannot remove non-existing edge.');
}
let nodes = edge.getNodes();
nodes.a.removeEdge(edge);
if (nodes.a !== nodes.b) {
nodes.b.removeEdge(edge);
}
if (dir_edge) {
delete this._dir_edges[edge.getID()];
this._nr_dir_edges -= 1;
}
else {
delete this._und_edges[edge.getID()];
this._nr_und_edges -= 1;
}
this.updateGraphMode();
}
// Some atomicity / rollback feature would be nice here...
deleteInEdgesOf(node: IBaseNode): void {
this.checkConnectedNodeOrThrow(node);
let in_edges = node.inEdges();
let key: string,
edge: IBaseEdge;
for (key in in_edges) {
edge = in_edges[key];
edge.getNodes().a.removeEdge(edge);
delete this._dir_edges[edge.getID()];
this._nr_dir_edges -= 1;
}
node.clearInEdges();
this.updateGraphMode();
}
// Some atomicity / rollback feature would be nice here...
deleteOutEdgesOf(node: IBaseNode): void {
this.checkConnectedNodeOrThrow(node);
let out_edges = node.outEdges();
let key: string,
edge: IBaseEdge;
for (key in out_edges) {
edge = out_edges[key];
edge.getNodes().b.removeEdge(edge);
delete this._dir_edges[edge.getID()];
this._nr_dir_edges -= 1;
}
node.clearOutEdges();
this.updateGraphMode();
}
// Some atomicity / rollback feature would be nice here...
deleteDirEdgesOf(node: IBaseNode): void {
this.deleteInEdgesOf(node);
this.deleteOutEdgesOf(node);
}
// Some atomicity / rollback feature would be nice here...
deleteUndEdgesOf(node: IBaseNode): void {
this.checkConnectedNodeOrThrow(node);
let und_edges = node.undEdges();
let key: string,
edge: IBaseEdge;
for (key in und_edges) {
edge = und_edges[key];
let conns = edge.getNodes();
conns.a.removeEdge(edge);
if (conns.a !== conns.b) {
conns.b.removeEdge(edge);
}
delete this._und_edges[edge.getID()];
this._nr_und_edges -= 1;
}
node.clearUndEdges();
this.updateGraphMode();
}
// Some atomicity / rollback feature would be nice here...
deleteAllEdgesOf(node: IBaseNode): void {
this.deleteDirEdgesOf(node);
this.deleteUndEdgesOf(node);
}
/**
* Remove all the (un)directed edges in the graph
*/
clearAllDirEdges(): void {
for (let edge in this._dir_edges) {
this.deleteEdge(this._dir_edges[edge]);
}
}
clearAllUndEdges(): void {
for (let edge in this._und_edges) {
this.deleteEdge(this._und_edges[edge]);
}
}
clearAllEdges(): void {
this.clearAllDirEdges();
this.clearAllUndEdges();
}
/**
* CAUTION - This function is linear in # directed edges
*/
getRandomDirEdge(): IBaseEdge {
return this.pickRandomProperty(this._dir_edges);
}
/**
* CAUTION - This function is linear in # undirected edges
*/
getRandomUndEdge(): IBaseEdge {
return this.pickRandomProperty(this._und_edges);
}
cloneStructure(): IGraph {
let new_graph = new BaseGraph(this._label),
old_nodes = this.getNodes(),
old_edge: IBaseEdge,
new_node_a = null,
new_node_b = null;
for ( let node_id in old_nodes ) {
new_graph.addNode(old_nodes[node_id].clone());
}
[this.getDirEdges(), this.getUndEdges()].forEach((old_edges) => {
for (let edge_id in old_edges) {
old_edge = old_edges[edge_id];
new_node_a = new_graph.getNodeById(old_edge.getNodes().a.getID());
new_node_b = new_graph.getNodeById(old_edge.getNodes().b.getID());
new_graph.addEdge(old_edge.clone(new_node_a, new_node_b))
}
});
return new_graph;
}
cloneSubGraphStructure(root: IBaseNode, cutoff: Number): IGraph {
let new_graph = new BaseGraph(this._label);
let config = prepareBFSStandardConfig();
let bfsNodeUnmarkedTestCallback = function (context: BFS_Scope) {
if (config.result[context.next_node.getID()].counter > cutoff) {
context.queue = [];
} else { //This means we only add cutoff -1 nodes to the cloned graph, # of nodes is then equal to cutoff
new_graph.addNode(context.next_node.clone());
}
};
config.callbacks.node_unmarked.push(bfsNodeUnmarkedTestCallback);
BFS(this, root, config);
let old_edge: IBaseEdge,
new_node_a = null,
new_node_b = null;
[this.getDirEdges(), this.getUndEdges()].forEach((old_edges) => {
for (let edge_id in old_edges) {
old_edge = old_edges[edge_id];
new_node_a = new_graph.getNodeById(old_edge.getNodes().a.getID());
new_node_b = new_graph.getNodeById(old_edge.getNodes().b.getID());
if (new_node_a != null && new_node_b != null)
new_graph.addEdge(old_edge.clone(new_node_a, new_node_b));
}
});
return new_graph;
}
protected checkConnectedNodeOrThrow(node: IBaseNode) {
let inGraphNode = this._nodes[node.getID()];
if (!inGraphNode) {
throw new Error('Cowardly refusing to delete edges of a foreign node.');
}
}
protected updateGraphMode() {
let nr_dir = this._nr_dir_edges,
nr_und = this._nr_und_edges;
if (nr_dir && nr_und) {
this._mode = GraphMode.MIXED;
}
else if (nr_dir) {
this._mode = GraphMode.DIRECTED;
}
else if (nr_und) {
this._mode = GraphMode.UNDIRECTED;
}
else {
this._mode = GraphMode.INIT;
}
}
pickRandomProperty(propList): any {
let tmpList = Object.keys(propList);
let randomPropertyName = tmpList[Math.floor(Math.random() * tmpList.length)];
return propList[randomPropertyName];
}
/**
* In some cases we need to return a large number of objects
* in one swoop, as calls to Object.keys() are really slow
* for large input objects.
*
* In order to do this, we only extract the keys once and then
* iterate over the key list and add them to a result array
* with probability = amount / keys.length
*
* We also mark all used keys in case we haven't picked up
* enough entities for the result array after the first round.
* We then just fill up the rest of the result array linearly
* with as many unused keys as necessary
*
*
* @todo include generic Test Cases
* @todo check if amount is larger than propList size
* @todo This seems like a simple hack - filling up remaining objects
* Could be replaced by a better fraction-increasing function above...
*
* @param propList
* @param amount
* @returns {Array}
*/
pickRandomProperties(propList, amount): Array<string> {
let ids = [];
let keys = Object.keys(propList);
let fraction = amount / keys.length;
let used_keys = {};
for (let i = 0; ids.length < amount && i < keys.length; i++) {
if (Math.random() < fraction) {
ids.push(keys[i]);
used_keys[keys[i]] = i;
}
}
let diff = amount - ids.length;
for (let i = 0; i < keys.length && diff; i++) {
if (used_keys[keys[i]] == null) {
ids.push(keys[i]);
diff--;
}
}
return ids;
}
}
export { BaseGraph };
import {TypedNode} from '../typed/TypedNode';
import * as $SU from '../../utils/StructUtils';
import {IBaseEdge} from "./BaseEdge";
export interface NeighborEntry {
node : IBaseNode;
edge : IBaseEdge;
// only used (and tested) in PFS
best? : number;
}
export interface BaseNodeConfig {
label? : string;
features? : {[key: string]: any};
}
type NodeFeatures = { [k:string]: any };
export interface IBaseNode {
// BASIC
readonly id: string;
readonly label: string;
readonly features: NodeFeatures;
setLabel(label : string) : void;
/**
* @todo old method versions -> take out..
*/
getID() : string;
getLabel() : string;
// FEATURES methods
getFeatures() : NodeFeatures;
getFeature(key: string) : any;
f(key:string) : any | undefined; // shortcut for getFeature
setFeatures( features: NodeFeatures ) : void;
setFeature(key: string, value: any) : void;
deleteFeature(key: string) : any;
clearFeatures() : void;
// Degrees
readonly deg: number;
readonly in_deg: number;
readonly out_deg: number;
readonly self_deg: number;
readonly self_in_deg: number;
readonly self_out_deg: number;
// EDGE methods
addEdge(edge: IBaseEdge) : IBaseEdge;
hasEdge(edge: IBaseEdge) : boolean;
hasEdgeID(id: string) : boolean;
getEdge(id: string) : IBaseEdge;
inEdges() : {[k: string] : IBaseEdge};
outEdges() : {[k: string] : IBaseEdge};
undEdges() : {[k: string] : IBaseEdge};
dirEdges() : {[k: string] : IBaseEdge};
allEdges() : {[k: string] : IBaseEdge};
removeEdge(edge: IBaseEdge) : void;
removeEdgeByID(id: string) : void;
// Clear different types of edges
clearOutEdges() : void;
clearInEdges() : void;
clearUndEdges() : void;
clearEdges() : void;
// neighborhood methods
prevNodes() : Array<NeighborEntry>;
nextNodes() : Array<NeighborEntry>;
connNodes() : Array<NeighborEntry>;
reachNodes(identityFunc?: Function) : Array<NeighborEntry>;
allNeighbors(identityFunc?: Function) : Array<NeighborEntry>;
clone() : IBaseNode;
}
class BaseNode implements IBaseNode {
protected _label : string;
protected _in_deg = 0;
protected _out_deg = 0;
protected _deg = 0;
protected _self_in_deg = 0;
protected _self_out_deg = 0;
protected _self_deg = 0;
protected _features : NodeFeatures;
protected _in_edges : {[k: string] : IBaseEdge};
protected _out_edges : {[k: string] : IBaseEdge};
protected _und_edges : {[k: string] : IBaseEdge};
/**
* @param _id
* @param config
*/
constructor (
protected _id: string,
config: BaseNodeConfig = {}
)
{
this._in_edges = {};
this._out_edges = {};
this._und_edges = {};
this._label = config.label || _id;
this._features = config.features != null ? $SU.clone(config.features) : {};
}
static isTyped(arg: any): arg is TypedNode {
return !!arg.type;
}
get id(): string {
return this._id;
}
get label(): string {
return this._label;
}
get features(): NodeFeatures {
return this._features;
}
getID() : string {
return this._id;
}
getLabel() : string {
return this._label;
}
setLabel(label : string) : void {
this._label = label;
}
getFeatures() : { [k:string] : any } {
return this._features;
}
getFeature(key: string) : any | undefined {
return this._features[key];
}
f(key:string) : any | undefined {
return this.getFeature(key);
}
setFeatures( features: { [k:string]: any } ) : void {
this._features = $SU.clone(features);
}
setFeature(key: string, value: any) : void {
this._features[key] = value;
}
deleteFeature(key: string) : any {
let feat = this._features[key];
delete this._features[key];
return feat;
}
clearFeatures() : void {
this._features = {};
}
get deg() : number {
return this._deg;
}
get in_deg() : number {
return this._in_deg;
}
get out_deg() : number {
return this._out_deg;
}
get self_deg() : number {
return this._self_deg;
}
get self_in_deg() : number {
return this._self_in_deg;
}
get self_out_deg() : number {
return this._self_out_deg;
}
/**
* We have to:
* 1. throw an error if the edge is already attached
* 2. add it to the edge array
* 3. check type of edge (directed / undirected)
* 4. update our degrees accordingly
*/
addEdge(edge: IBaseEdge) : IBaseEdge {
let ends = edge.getNodes();
if ( ends.a !== this && ends.b !== this ) {
throw new Error("Cannot add edge that does not connect to this node");
}
const id = edge.id;
if ( edge.isDirected() ) {
// is it outgoing or incoming?
if ( ends.a === this && !this._out_edges[id]) {
this._out_edges[id] = edge;
this._out_deg += 1;
// Directed self loop ?
if ( ends.b === this && !this._in_edges[id]) {
this._in_edges[id] = edge;
this._in_deg += 1;
this._self_in_deg += 1;
this._self_out_deg += 1;
}
}
// No self loop
else if ( !this._in_edges[id] ) { // nodes.b === this
this._in_edges[id] = edge;
this._in_deg += 1;
}
}
// UNdirected
else {
if (this._und_edges[ edge.id ]) {
throw new Error("Cannot add same undirected edge multiple times.");
}
this._und_edges[id] = edge;
this._deg += 1;
if ( ends.a === ends.b ) {
this._self_deg += 1;
}
}
return edge;
}
hasEdge(edge: IBaseEdge) : boolean {
return !!this._in_edges[ edge.getID() ] || !!this._out_edges[ edge.getID() ] || !!this._und_edges[ edge.getID() ];
}
hasEdgeID(id: string) : boolean {
return !!this._in_edges[ id ] || !!this._out_edges[ id ] || !!this._und_edges[ id ];
}
getEdge(id: string) : IBaseEdge {
let edge = this._in_edges[id] || this._out_edges[id] || this._und_edges[id];
if ( !edge ) {
throw new Error("Cannot retrieve non-existing edge.");
}
return edge;
}
inEdges() : {[k: string] : IBaseEdge} {
return this._in_edges;
}
outEdges() : {[k: string] : IBaseEdge} {
return this._out_edges;
}
undEdges() : {[k: string] : IBaseEdge} {
return this._und_edges;
}
dirEdges() : {[k: string] : IBaseEdge} {
return $SU.mergeObjects([this._in_edges, this._out_edges]);
}
allEdges() : {[k: string] : IBaseEdge} {
return $SU.mergeObjects([this._in_edges, this._out_edges, this._und_edges]);
}
/**
* @description automatically takes care of self-loops (since looking up in all internal data structures)
* @param edge
*/
removeEdge(edge: IBaseEdge) : void {
if ( !this.hasEdge(edge) ) {
throw new Error("Cannot remove unconnected edge.");
}
const id = edge.id;
const ends = edge.getNodes();
let e = this._und_edges[id];
if ( e ) {
delete this._und_edges[id];
this._deg -= 1;
( ends.a === ends.b ) && ( this._self_deg -= 1 );
}
e = this._in_edges[id];
if ( e ) {
delete this._in_edges[id];
this._in_deg -= 1;
( ends.a === ends.b ) && ( this._self_in_deg -= 1 );
}
e = this._out_edges[id];
if ( e ) {
delete this._out_edges[id];
this._out_deg -= 1;
( ends.a === ends.b ) && ( this._self_out_deg -= 1 );
}
}
removeEdgeByID(id: string) : void {
if ( !this.hasEdgeID(id) ) {
throw new Error("Cannot remove unconnected edge.");
}
this.removeEdge(this.getEdge(id));
}
/**
* @description slow -> if possible, just clear ALL edges instead
*/
clearOutEdges() : void {
for ( let e of Object.values(this.outEdges()) ) {
this.removeEdge(e);
}
}
/**
* @description slow -> if possible, just clear ALL edges instead
*/
clearInEdges() : void {
for ( let e of Object.values(this.inEdges()) ) {
this.removeEdge(e);
}
}
clearUndEdges() : void {
this._und_edges = {};
this._deg = 0;
this._self_deg = 0;
}
clearEdges() : void {
this.clearUndEdges();
this._in_edges = {};
this._out_edges = {};
this._deg = this._self_deg = this._in_deg = this._self_in_deg = this._out_deg = this._self_out_deg = 0;
}
/**
* return the set of all nodes that have
* directed edges coming into this node
*/
prevNodes() : Array<NeighborEntry> {
let prevs : Array<NeighborEntry> = [];
let key : string,
edge : IBaseEdge;
for ( key in this._in_edges ) {
if ( this._in_edges.hasOwnProperty(key) ) {
edge = this._in_edges[key];
prevs.push({
node: edge.getNodes().a,
edge: edge
});
}
}
return prevs;
}
/**
* return the set of all nodes that have
* directed edges going out from this node
*/
nextNodes() : Array<NeighborEntry> {
let nexts : Array<NeighborEntry> = [];
let key : string,
edge : IBaseEdge;
for ( key in this._out_edges ) {
if ( this._out_edges.hasOwnProperty(key) ) {
edge = this._out_edges[key];
nexts.push({
node: edge.getNodes().b,
edge: edge
});
}
}
return nexts;
}
/**
* return the set of all nodes that are
* connected to this node via undirected edges
*/
connNodes() : Array<NeighborEntry> {
let conns : Array<NeighborEntry> = [];
let key : string,
edge : IBaseEdge;
for ( key in this._und_edges ) {
if ( this._und_edges.hasOwnProperty(key) ) {
edge = this._und_edges[key];
let nodes = edge.getNodes();
if ( nodes.a === this ) {
conns.push({
node: edge.getNodes().b,
edge: edge
});
}
else {
conns.push({
node: edge.getNodes().a,
edge: edge
});
}
}
}
return conns;
}
/**
* return the set of all nodes 'reachable' from this node,
* either via unconnected or outgoing edges
*
* @param identityFunc can be used to remove 'duplicates' from resulting array,
* if necessary
* @returns {Array}
*
*/
reachNodes(identityFunc?: Function) : Array<NeighborEntry> {
let identity = 0;
return $SU.mergeArrays(
[ this.nextNodes(), this.connNodes() ],
identityFunc || ( ne => identity++ )
);
}
/**
* return the set of all nodes connected to this node
*
* @param identityFunc can be used to remove 'duplicates' from resulting array,
* if necessary
* @returns {Array}
*
*/
allNeighbors(identityFunc?: Function) : Array<NeighborEntry> {
let identity = 0;
// console.log(this.nextNodes());
return $SU.mergeArrays([this.prevNodes(), this.nextNodes(), this.connNodes()],
identityFunc || function(ne) {return identity++});
}
clone() : IBaseNode {
let new_node = new BaseNode(this._id);
new_node._label = this._label;
new_node.setFeatures( $SU.clone( this.getFeatures() ) );
return new_node;
}
}
export { BaseNode };
import {MinAdjacencyListArray, MinAdjacencyListDict, NextArray} from "../interfaces";
import {IGraph} from "../base/BaseGraph";
import {Logger} from "../../utils/Logger";
import {IBaseNode} from "../base/BaseNode";
const logger = new Logger();
const DEFAULT_WEIGHT = 1;
export interface NumericHandler {
tensor2d: Function;
matMul: Function;
}
export interface IComputeGraph {
// REPRESENTATIONS
adjListW(incoming?: boolean, include_self?, self_dist?: number): MinAdjacencyListDict;
adjMatrix(): MinAdjacencyListArray;
adjMatrixW(incoming?: boolean): MinAdjacencyListArray;
nextArray(incoming?: boolean): NextArray;
// METRICS
triadCount(directed?: boolean): number;
triangleCount(directed?: boolean): Promise<number>;
globalCC(directed?: boolean): Promise<number>;
localCC(directed? : boolean) : Promise<{[key: string]: number}>;
}
class ComputeGraph implements IComputeGraph {
private adj_list_uu: Uint32Array;
private adj_list_du: Uint32Array;
private adj_list_uw: Float32Array;
private adj_list_dw: Float32Array;
constructor(private _g: IGraph, private _numeric?: NumericHandler) { }
checkNumericHandler() {
if (!this._numeric || !this._numeric.matMul) {
throw new Error("Tensorflow & TF matMul function must be present for fast numeric computations.");
}
}
/**
* @param incoming
* @todo analyze and make faster
*/
nextArray(incoming: boolean = false): NextArray {
let next = [],
node_keys = Object.keys(this._g.getNodes());
const adjDict = this.adjListW(incoming, true, 0);
for (let i = 0; i < this._g.nrNodes(); ++i) {
next.push([]);
for (let j = 0; j < this._g.nrNodes(); ++j) {
next[i].push([]);
next[i][j].push(i === j ? j : isFinite(adjDict[node_keys[i]][node_keys[j]]) ? j : null);
}
}
return next;
}
adjMatrix(): MinAdjacencyListArray {
let adjList = [],
node_keys = Object.keys(this._g.getNodes());
const adjDict = this.adjListW();
for (let i = 0; i < this._g.nrNodes(); ++i) {
adjList.push([]);
for (let j = 0; j < this._g.nrNodes(); ++j) {
adjList[i].push(i === j ? 0 : isFinite(adjDict[node_keys[i]][node_keys[j]]) ? 1 : 0);
}
}
return adjList;
}
/**
* @todo rename? it's actually a weight matrix...
*
* This function iterates over the adjDict in order to use it's advantage
* of being able to override edges if edges with smaller weights exist
*
* However, the order of nodes in the array represents the order of nodes
* at creation time, no other implicit alphabetical or collational sorting.
*
* This has to be considered when further processing the result
*
* @param incoming whether or not to consider incoming edges
* @param include_self contains a distance to itself?
* @param self_dist default distance to self
*/
adjMatrixW(incoming: boolean = false, include_self = false, self_dist = 0): MinAdjacencyListArray {
let adjList = [],
node_keys = Object.keys(this._g.getNodes());
const adjDict = this.adjListW(incoming, include_self, self_dist);
for (let i = 0; i < this._g.nrNodes(); ++i) {
adjList.push([]);
for (let j = 0; j < this._g.nrNodes(); ++j) {
adjList[i].push(i === j ? self_dist : isFinite(adjDict[node_keys[i]][node_keys[j]]) ? adjDict[node_keys[i]][node_keys[j]] : Number.POSITIVE_INFINITY);
}
}
return adjList;
}
/**
* @todo force directed / undirected
* -> take undirected edge as 2 directed ones?
* -> take directed edge as undirected?
*
* @param incoming whether or not to consider incoming edges
* @param include_self contains a distance to itself?
* @param self_dist default distance to self
*/
adjListW(incoming: boolean = false, include_self = false, self_dist = 0): MinAdjacencyListDict {
let adj_list_dict: MinAdjacencyListDict = {},
nodes = this._g.getNodes(),
cur_dist: number,
key: string,
cur_edge_weight: number;
for (key in nodes) {
adj_list_dict[key] = {};
if (include_self) {
adj_list_dict[key][key] = self_dist;
}
}
for (key in nodes) {
let neighbors = incoming ? nodes[key].reachNodes().concat(nodes[key].prevNodes()) : nodes[key].reachNodes();
neighbors.forEach((ne) => {
cur_dist = adj_list_dict[key][ne.node.getID()] || Number.POSITIVE_INFINITY;
cur_edge_weight = isNaN(ne.edge.getWeight()) ? DEFAULT_WEIGHT : ne.edge.getWeight();
if (cur_edge_weight < cur_dist) {
adj_list_dict[key][ne.node.getID()] = cur_edge_weight;
if (incoming) { // we need to update the 'inverse' entry as well
adj_list_dict[ne.node.getID()][key] = cur_edge_weight;
}
} else {
adj_list_dict[key][ne.node.getID()] = cur_dist;
if (incoming) {
adj_list_dict[ne.node.getID()][key] = cur_dist;
}
}
});
}
return adj_list_dict;
}
/**-------------------------------------------------------------
* Triad, triangle, CC & transitivity (global CC)
* @todo refactor out into own module:
* - name: `general metrics` ?
* - modularity / connectivity / CC & Trans
*-------------------------------------------------------------
*/
/**
* @description `triad`: is either a completed triangle or a potential triangle,
* meaning a connection between 3 nodes that is lacking just 1 edge.
* `triplet`: is three nodes that are connected by either two (open triplet)
* or three (closed triplet) undirected ties
* triad == triplet
* @description count all 2-triads
* UN-directed scenario for earch node: all pairwise connections could form a triangle
* directed scenario for each node: -ins could form triangles with -outs (and vice versa)
*
* @todo this only works for nodes without self-loops !!!
*
* @param directed directed or undirected
*/
triadCount(directed = false): number {
let triangle_count = 0;
const nodes = Object.values(this._g.getNodes());
let deg;
for ( let n of nodes ) {
if ( directed ) {
triangle_count += ( n.in_deg - n.self_in_deg ) * ( n.out_deg - n.self_out_deg );
}
else {
deg = n.deg - n.self_deg;
triangle_count += deg * ( deg - 1 ) / 2;
}
}
return triangle_count;
}
/**
* @description how many triangles (A-B-C, or A->B->C) are there in the graph
* In directed graphs, each triangle is seen thrice (from A, B, C)
* In undirected graphs, each triangle is seen six times (from A, B, C, but each in 2 directions)
* @param directed directed or undirected network
*/
async triangleCount(directed = false): Promise<number> {
this.checkNumericHandler();
const adj_list = this.adjMatrix();
const a = this._numeric.tensor2d(adj_list);
const aux2 = await a.matMul(a).array();
const aux3 = await a.matMul(aux2).array();
// logger.log(aux3);
let trace = 0;
for (let i = 0; i < aux3.length; i++) {
trace += aux3[i][i];
}
return directed ? trace / 3 : trace / 6;
}
/**
* @description transitivity (or global clustering coefficient, gCC) is the ratio
* of actual triangles to potential triangles, or
* (nr. of closed triplets / nr. of all triplets)
* It therefore measures the connection potential of the whole graph,
* the higher the gCC the lower the future connection potential.
* @description should equal the average (local) clustering coefficients of all nodes
*
* @todo test that avg(lCC) == gCC
* @todo there are 4 different ways to define a triplet closure in DIRECTED graphs
* @todo using the `undirected` formula results are not consistent with networkx
* @todo research & correct the $G <-> networkx inconsistency
* @param directed directed or undirected network
*/
async globalCC(directed = false): Promise<number> {
const triangles = await this.triangleCount(directed);
const triads = this.triadCount(directed);
return 3 * triangles / triads;
}
/**
* @description The CC (also `local` CC) measures how complete the neighborhood of a node is,
* i.e. (completed triangles / `potential` triangles), where a potential triangle
* could form by adding 1 edge between hitherto unconnected neighbors.
* This can be measured by
* @param directed directed or undirected network
*/
async localCC(directed = false) : Promise<{[key: string]: number}> {
this.checkNumericHandler();
const result = {};
const adj_list = this.adjMatrix();
const a = this._numeric.tensor2d(adj_list);
const aux2 = await a.matMul(a).array();
const aux3 = await a.matMul(aux2).array();
/**
* @todo ensure node order is equivalent to aux3 ordering - HOW ??
*/
let deg: number;
let node: IBaseNode;
let cc_i: number; // intermediate
const keys = Object.keys(this._g.getNodes());
for ( let i in aux3[0] ) {
node = this._g.getNodeById(keys[i]);
deg = directed ? node.in_deg + node.out_deg : node.deg;
cc_i = (aux3[i][i] / (deg * (deg-1))) || 0;
result[i] = directed ? 2 * cc_i : cc_i;
}
return result;
}
}
export {
ComputeGraph
}
import {ITypedNode} from "./typed/TypedNode";
import {ITypedEdge} from "./typed/TypedEdge";
/*----------------------------------------*/
/* BASE GRAPH */
/*----------------------------------------*/
/**
* @todo maybe refactor to more sensible value(type)s...
*/
export enum DIR {
in = "ins",
out = "outs",
und = "unds"
}
export enum GraphMode {
INIT,
DIRECTED,
UNDIRECTED,
MIXED
}
export interface GraphStats {
mode : GraphMode;
nr_nodes : number;
nr_und_edges : number;
nr_dir_edges : number;
density_dir : number;
density_und : number;
}
/**
* Only gives the best distance to a node in case of multiple direct edges
*/
export type MinAdjacencyListDict = {[id: string]: MinAdjacencyListDictEntry};
export type MinAdjacencyListDictEntry = {[id: string] : number};
export type MinAdjacencyListArray = Array<Array<number>>;
export type NextArray = Array<Array<Array<number>>>;
/*----------------------------------------*/
/* TYPED GRAPH */
/*----------------------------------------*/
export type TypedNodes = Map<string, Map<string, ITypedNode>>;
export type TypedEdges = Map<string, Map<string, ITypedEdge>>;
export interface TypedGraphStats extends GraphStats {
typed_nodes: { [key: string]: number };
typed_edges: { [key: string]: number };
}
export type ExpansionInput = ITypedNode | Set<ITypedNode> | ExpansionResult;
export interface ExpansionConfig {
k? : number;
}
export interface ExpansionResult {
set : Set<ITypedNode>;
freq : Map<ITypedNode, number>;
}
/**
* @todo make it so
*/
// export type ExpansionResult = Map<ITypedNode, number>;
/**
* For figuring out abberations to n4j expansion results (sometimes tiny)
*
* @todo maybe this is just experimental, maybe not...
*/
type Inbounds = {[key: string] : number}; // sourceID => freq of sourceNode
export type ExpansionInbounds = {[key: string] : Inbounds};
import { IBaseEdge, BaseEdge, BaseEdgeConfig } from '../base/BaseEdge';
import { GENERIC_TYPES } from '../../config/run_config';
import * as $N from "../base/BaseNode";
export interface ITypedEdge extends IBaseEdge {
readonly type: string;
}
export interface TypedEdgeConfig extends BaseEdgeConfig {
type?: string;
}
class TypedEdge extends BaseEdge implements ITypedEdge {
protected _type : string;
constructor(protected _id: string,
protected _node_a: $N.IBaseNode,
protected _node_b: $N.IBaseNode,
config: TypedEdgeConfig = {}) {
super(_id, _node_a, _node_b, config);
this._type = config.type || GENERIC_TYPES.Edge;
}
get type() {
return this._type;
}
}
export {
TypedEdge
}
import {ITypedNode, TypedNode} from './TypedNode';
import {ITypedEdge, TypedEdge, TypedEdgeConfig} from "./TypedEdge";
import {BaseEdge, IBaseEdge} from "../base/BaseEdge";
import {BaseGraph} from '../base/BaseGraph';
import {GENERIC_TYPES} from "../../config/run_config";
import {BaseNode} from "../base/BaseNode";
import {
DIR,
ExpansionInbounds,
ExpansionInput,
ExpansionConfig,
ExpansionResult,
TypedGraphStats,
TypedEdges,
TypedNodes
} from '../interfaces';
/**
* @description TypedGraph only takes TypedNodes & TypedEdges
* @description coding standard: following Neo4j / Cypher standard,
* node types should be in capital letters & edge types expressive
* two-pieces separated by underscore (except 'GENERIC')
* @todo enforce uppercase?
* @description we could couple edge type & direction in order to
* make the system more stringent, but this would result in a more
* complex setup with the possibility of too many Errors thrown.
* @solution for now, leave the type / direction combination to the
* programmer & just assume internal consistency
* @todo how to handle traversal when direction given goes against
* direction information in the edge object ?
* @todo just don't specify direction in traversal / expand and only
* follow the direction specified in edge !?
* @todo in the last case, how to handle undirected edges ?
* @todo allow 'GENERIC' edge types ? => yes!
*/
export class TypedGraph extends BaseGraph {
protected _type: string;
/**
* We don't need an extra array of registered types, since an
* acceptable recommendation graph will only contain a few single
* up to a few dozen different types, which are quickly obtained
* via Object.keys()
*/
protected _typedNodes: TypedNodes = new Map();
protected _typedEdges: TypedEdges = new Map();
constructor(public _label: string) {
super(_label);
this._type = GENERIC_TYPES.Graph;
this._typedNodes.set(GENERIC_TYPES.Node, new Map());
this._typedEdges.set(GENERIC_TYPES.Edge, new Map());
}
/**
* convenience methods
*/
n(id: string) {
return this.getNodeById(id);
}
get type(): string {
return this._type;
}
nodeTypes(): string[] {
return Array.from(this._typedNodes.keys());
}
edgeTypes(): string[] {
return Array.from(this._typedEdges.keys());
}
nrTypedNodes(type: string): number | null {
type = type.toUpperCase();
return this._typedNodes.get(type) ? this._typedNodes.get(type).size : null;
}
nrTypedEdges(type: string): number | null {
type = type.toUpperCase();
return this._typedEdges.get(type) ? this._typedEdges.get(type).size : null;
}
/**
* Neighbor nodes depending on type
*/
ins(node: ITypedNode, type: string): Set<ITypedNode> {
const targets = node.ins(type);
if (targets) {
return new Set([...targets].map(uid => this.n(TypedNode.nIDFromUID(uid)) as TypedNode));
}
}
outs(node: ITypedNode, type: string): Set<ITypedNode> {
const targets = node.outs(type);
if (targets) {
}
return new Set([...targets].map(uid => this.n(TypedNode.nIDFromUID(uid)) as TypedNode));
}
unds(node: ITypedNode, type: string): Set<ITypedNode> {
const targets = node.unds(type);
if (targets) {
return new Set([...targets].map(uid => this.n(TypedNode.nIDFromUID(uid)) as TypedNode));
}
}
/**
* @todo abomination...
*/
static convertToExpansionResult(input: ExpansionInput): ExpansionResult {
if (BaseNode.isTyped(input)) {
return {set: new Set([input]), freq: new Map<ITypedNode, number>()};
} else if (input instanceof Set) {
return {set: input as Set<ITypedNode>, freq: new Map<ITypedNode, number>()};
} else {
return input as ExpansionResult;
}
}
/**
* Neighbor nodes depending on type
* @description takes either a single TypedNode or a Set of TypedNodes as input
* @description we have to start with node objects, since dupe-checkable strings
* are only available once we deal with edge/neighborhood entries
* However, we then need to switch to an `intermediate representation`
* using those strings for dupe checking, and in the end map back to
* a node set...
* @description In case of multiple input nodes, they could reference each other...
* -> Neo4j allows that, so we allow it as well (for now ;-))
*
* @todo decide if this difference in representation between node->neighbors &
* graph->nodeNeighbors is a problem or not (also performance-wise) !?
* @todo decide if method call via [dir] is an abomination or not
* -> definitely screws up code assist / intellisense !
* -> (we all know it is...)
*
*
*
* @TODO draw a decision diagram...!
* @TODO create a small, manageable test graph for expand(K)/periphery@K scenarios
* -> and put those test cases into the SYNC suite
*/
expand(input: ExpansionInput, dir: DIR, type: string): ExpansionResult {
// const expansionInbounds : ExpansionInbounds = {};
const nodes: ExpansionResult = TypedGraph.convertToExpansionResult(input);
const resultSet = new Set<ITypedNode>();
const freqMap = new Map<ITypedNode, number>();
for (let node of nodes.set) {
const targets = node[dir](type);
if (!targets) {
continue;
}
for (let target of targets) {
let nodeRef = this.n(TypedNode.nIDFromUID(target)) as TypedNode;
if (!freqMap.has(nodeRef)) {
// if we already have a frequency entry for this source node, we'll use it for initialization
// since if #paths already led to this node, and we have a path from this node to the
// target, then we got #paths to the target from whatever original source
if (nodes.freq.get(node)) {
freqMap.set(nodeRef, nodes.freq.get(node));
} else {
freqMap.set(nodeRef, 1);
}
}
if (resultSet.has(nodeRef)) {
freqMap.set(nodeRef, freqMap.get(nodeRef) + nodes.freq.get(node));
}
resultSet.add(nodeRef);
}
}
return {set: resultSet, freq: freqMap};
}
/**
* expand over k steps
*
* @description like neo4j's `-[:REL*1..k]->`
* returning the node sets at distance <= `k`
*/
expandK(input: ExpansionInput, dir: DIR, type: string, cfg: ExpansionConfig = {}): ExpansionResult {
if (cfg.k < 0) {
throw new Error('cowardly refusing to expand a negative number of steps.');
}
let k = cfg.k && cfg.k < this._nr_nodes ? cfg.k : this._nr_nodes - 1;
let nodes: ExpansionResult = TypedGraph.convertToExpansionResult(input);
let resultSet = new Set<ITypedNode>();
const freqMap = new Map<ITypedNode, number>();
while (k--) {
nodes = this.expand(nodes, dir, type);
for (let nodeRef of nodes.set) {
if (!freqMap.has(nodeRef)) {
freqMap.set(nodeRef, nodes.freq.get(nodeRef));
}
if (resultSet.has(nodeRef)) {
freqMap.set(nodeRef, freqMap.get(nodeRef) + nodes.freq.get(nodeRef));
}
resultSet.add(nodeRef);
}
}
return {set: resultSet, freq: freqMap};
}
/**
* @description like neo4j's `-[:REL*k]->`
* only returning the node set at distance `k`
*/
peripheryAtK(input: ExpansionInput, dir: DIR, type: string, cfg: ExpansionConfig = {}): ExpansionResult {
if (cfg.k < 0) {
throw new Error('cowardly refusing to expand a negative number of steps.');
}
let nodes: ExpansionResult = TypedGraph.convertToExpansionResult(input);
let k = cfg.k && cfg.k < this._nr_nodes ? cfg.k : this._nr_nodes - 1;
for ( let it = 0; it < k; it++ ) {
nodes = this.expand(nodes, dir, type);
}
return nodes;
}
/**
* TYPED HISTOGRAMS
*/
inHistT(nType: string, eType: string): Set<number>[] {
return this.degreeHistT(DIR.in, nType, eType);
}
outHistT(nType: string, eType: string): Set<number>[] {
return this.degreeHistT(DIR.out, nType, eType);
}
connHistT(nType: string, eType: string): Set<number>[] {
return this.degreeHistT(DIR.und, nType, eType);
}
private degreeHistT(dir: string, nType: string, eType: string): Set<number>[] {
let result = [];
for (let [node_id, node] of this._typedNodes.get(nType)) {
let deg;
switch (dir) {
case DIR.in:
deg = node.ins(eType) ? node.ins(eType).size : 0;
break;
case DIR.out:
deg = node.outs(eType) ? node.outs(eType).size : 0;
break;
default:
deg = node.unds(eType) ? node.unds(eType).size : 0;
}
if (!result[deg]) {
result[deg] = new Set([node]);
} else {
result[deg].add(node);
}
}
return result;
}
/**
* @todo difference to super ??
* @param id
* @param opts
*/
addNodeByID(id: string, opts?: {}): ITypedNode {
if (this.hasNodeID(id)) {
throw new Error("Won't add node with duplicate ID.");
}
let node = new TypedNode(id, opts);
return this.addNode(node) ? node : null;
}
addNode(node: ITypedNode): ITypedNode {
if (!super.addNode(node)) {
return null;
}
// logger.log(JSON.stringify(node));
const
id = node.getID(),
type = node.type ? node.type.toUpperCase() : null;
/**
* Untyped nodes will be treated as `generic` type
*/
if (!type) {
// logger.log(`Received node type: ${type}`);
this._typedNodes.get(GENERIC_TYPES.Node).set(id, node);
} else {
if (!this._typedNodes.get(type)) {
this._typedNodes.set(type, new Map());
}
this._typedNodes.get(type).set(id, node);
}
return node;
}
getNodeById(id: string): TypedNode {
return super.getNodeById(id) as TypedNode;
}
getNodesT(type: string) {
return this._typedNodes.get(type.toUpperCase());
}
getEdgesT(type: string) {
return this._typedEdges.get(type.toUpperCase());
}
deleteNode(node: ITypedNode): void {
const id = node.getID(),
type = node.type ? node.type.toUpperCase() : GENERIC_TYPES.Node;
if (!this._typedNodes.get(type)) {
throw Error('Node type does not exist on this TypedGraph.');
}
const removeNode = this._typedNodes.get(type).get(id);
if (!removeNode) {
throw Error('This particular node is nowhere to be found in its typed set.')
}
this._typedNodes.get(type).delete(id);
if (this.nrTypedNodes(type) === 0) {
this._typedNodes.delete(type);
}
super.deleteNode(node);
}
addEdgeByID(id: string, a: ITypedNode, b: ITypedNode, opts?: TypedEdgeConfig): ITypedEdge {
let edge = new TypedEdge(id, a, b, opts || {});
return this.addEdge(edge);
}
addEdge(edge: ITypedEdge | IBaseEdge): ITypedEdge {
if (!super.addEdge(edge)) {
return null;
}
const id = edge.getID();
let type = GENERIC_TYPES.Edge;
if (BaseEdge.isTyped(edge) && edge.type) {
type = edge.type.toUpperCase();
}
// logger.log('Got edge label: ' + edge.label);
// logger.log('Got edge type: ' + type);
/**
* Same procedure as every node...
*/
if (id === type) {
this._typedEdges.get(GENERIC_TYPES.Edge).set(id, edge as ITypedEdge);
} else {
if (!this._typedEdges.get(type)) {
this._typedEdges.set(type, new Map());
}
this._typedEdges.get(type).set(id, edge as ITypedEdge);
}
return edge as ITypedEdge;
}
deleteEdge(edge: ITypedEdge | IBaseEdge): void {
const id = edge.getID();
let type = GENERIC_TYPES.Edge;
if (BaseEdge.isTyped(edge) && edge.type) {
type = edge.type.toUpperCase();
}
if (!this._typedEdges.get(type)) {
throw Error('Edge type does not exist on this TypedGraph.');
}
const removeEdge = this._typedEdges.get(type).get(id);
if (!removeEdge) {
throw Error('This particular edge is nowhere to be found in its typed set.')
}
this._typedEdges.get(type).delete(id);
if (this.nrTypedEdges(type) === 0) {
this._typedEdges.delete(type);
}
super.deleteEdge(edge);
}
getStats(): TypedGraphStats {
let typed_nodes = {},
typed_edges = {};
this._typedNodes.forEach((k, v) => typed_nodes[v] = k.size);
this._typedEdges.forEach((k, v) => typed_edges[v] = k.size);
return {
...super.getStats(),
// node_types: this.nodeTypes(),
// edge_types: this.edgeTypes(),
typed_nodes,
typed_edges
};
}
}
import {IBaseNode, BaseNode, BaseNodeConfig} from '../base/BaseNode';
import {ITypedEdge, TypedEdge} from "./TypedEdge";
import {GENERIC_TYPES} from "../../config/run_config";
export interface TypedNeighborEntry {
n: ITypedNode;
e: string; // edge entry
w: number; // weight
}
export interface TypedAdjListsEntry {
ins?: Set<string>;
outs?: Set<string>;
conns?: Set<string>;
}
export type TypedAdjSets = { [type: string]: TypedAdjListsEntry };
export interface TypedEdgesStatsEntry {
ins: number;
outs: number;
conns: number;
}
export interface TypedNodeStats {
typed_edges: { [key: string]: TypedEdgesStatsEntry };
}
export interface ITypedNode extends IBaseNode {
readonly type: string;
readonly stats: TypedNodeStats;
uniqueNID(e: ITypedEdge): string;
addEdge(edge: ITypedEdge): ITypedEdge;
removeEdge(edge: ITypedEdge): void;
// removeEdgeByID(id: string): void;
/**
* Typed neighbor methods
* @param type string identifying the edge type
* @todo also restructure BaseNode names for clarity?
*/
ins(type: string): Set<string>;
outs(type: string): Set<string>;
unds(type: string): Set<string>;
}
export interface TypedNodeConfig extends BaseNodeConfig {
type?: string;
}
class TypedNode extends BaseNode implements ITypedNode {
protected _type: string;
protected _typedAdjSets: TypedAdjSets;
constructor(protected _id: string, config: TypedNodeConfig = {}) {
super(_id, config);
this._type = config.type || GENERIC_TYPES.Node;
this._typedAdjSets = {
[GENERIC_TYPES.Edge]: {
ins: new Set<string>(),
outs: new Set<string>(),
conns: new Set<string>()
}
}
}
get type(): string {
return this._type;
}
get stats(): TypedNodeStats {
const result: TypedNodeStats = {
typed_edges: {}
};
for ( let type of Object.keys(this._typedAdjSets) ) {
result.typed_edges[type] = {ins: 0, outs: 0, conns: 0};
result.typed_edges[type].ins = this._typedAdjSets[type].ins ? this._typedAdjSets[type].ins.size : 0;
result.typed_edges[type].outs = this._typedAdjSets[type].outs ? this._typedAdjSets[type].outs.size : 0;
result.typed_edges[type].conns = this._typedAdjSets[type].conns ? this._typedAdjSets[type].conns.size : 0;
}
return result;
}
addEdge(edge: ITypedEdge): ITypedEdge {
if (!super.addEdge(edge)) {
return null;
}
const type = edge.type || GENERIC_TYPES.Edge;
const dir = edge.isDirected();
const uid = this.uniqueNID(edge);
if ( !this._typedAdjSets[type] ) {
this._typedAdjSets[type] = {}
}
if ( !dir ) {
if ( !this._typedAdjSets[type].conns ) {
this._typedAdjSets[type].conns = new Set<string>();
}
this._typedAdjSets[type].conns.add(uid);
}
else if ( edge.getNodes().a === this ) {
if ( !this._typedAdjSets[type].outs ) {
this._typedAdjSets[type].outs = new Set<string>();
}
this._typedAdjSets[type].outs.add(uid);
}
else {
if ( !this._typedAdjSets[type].ins ) {
this._typedAdjSets[type].ins = new Set<string>();
}
this._typedAdjSets[type].ins.add(uid);
}
// logger.log(this._typedAdjSets);
return edge;
}
/**
* @description we assume
* - type is present if super removes edge without throwing
* @param edge
*/
removeEdge(edge: ITypedEdge): void {
// Throws when something happens...
super.removeEdge(edge);
const type = edge.type || GENERIC_TYPES.Edge;
const dir = edge.isDirected();
const uid = this.uniqueNID(edge);
if ( !dir ) {
this._typedAdjSets[type].conns.delete(uid);
}
else if ( edge.getNodes().a === this ) {
this._typedAdjSets[type].outs.delete(uid);
}
else {
this._typedAdjSets[type].ins.delete(uid);
}
if ( type !== GENERIC_TYPES.Edge && this.noEdgesOfTypeLeft(type) ) {
delete this._typedAdjSets[type];
}
}
// removeEdgeByID(id: string): void {
// super.removeEdgeByID(id);
// }
ins(type: string): Set<string> {
return this._typedAdjSets[type] ? this._typedAdjSets[type].ins : undefined;
}
outs(type: string): Set<string> {
return this._typedAdjSets[type] ? this._typedAdjSets[type].outs : undefined;
}
unds(type: string): Set<string> {
return this._typedAdjSets[type] ? this._typedAdjSets[type].conns : undefined;
}
all(type:string): Set<string> {
const result = new Set<any>(); // spread operator has a problem with Set<string>...
if ( this._typedAdjSets[type] ) {
this._typedAdjSets[type].ins && result.add([...this._typedAdjSets[type].ins]);
this._typedAdjSets[type].outs && result.add([...this._typedAdjSets[type].outs]);
this._typedAdjSets[type].conns && result.add([...this._typedAdjSets[type].conns]);
}
return result;
}
/**
* Unique ID for Neighbor (traversal)
* @param e ITypedEdge
* @description {node} `other / target` node
* @returns unique neighbor entry ID
*/
uniqueNID(e: ITypedEdge): string {
const {a, b} = e.getNodes();
const node = a === this ? b : a;
let string = `${node.id}#${e.id}#`;
string += e.isWeighted() ? 'w#' + e.getWeight() : 'u';
return string;
}
static nIDFromUID(uid: string) {
return uid.split('#')[0];
}
private noEdgesOfTypeLeft(type: string): boolean {
return (!this._typedAdjSets[type].ins || !this._typedAdjSets[type].ins.size)
&& (!this._typedAdjSets[type].outs || !this._typedAdjSets[type].outs.size)
&& (!this._typedAdjSets[type].conns || !this._typedAdjSets[type].conns.size);
}
}
export {
TypedNode
}
export enum BinaryHeapMode {
MIN,
MAX
}
export interface PositionHeapEntry {
score: number;
position: number;
}
export interface IBinaryHeap {
// Helper methods
getMode(): BinaryHeapMode;
getArray(): Array<any>;
size(): number;
getEvalPriorityFun(): Function;
evalInputScore(obj: any): number;
getEvalObjIDFun(): Function;
evalInputObjID(obj: any): any;
// Actual heap operations
insert(obj: any): void;
// reInsert(obj: any): void;
remove(obj: any): any;
peek(): any;
pop(): any;
find(obj: any): any;
// Just temporarily, for debugging
getPositions(): any;
}
/**
* We only support unique object ID's for now !!!
* @TODO Rename into "ObjectBinaryHeap" or such...
*/
class BinaryHeap implements IBinaryHeap {
_nr_removes : number = 0; // just for debugging
private _array = [];
private _positions: { [id: string]: PositionHeapEntry } = {};
/**
* Mode of a min heap should only be set upon
* instantiation and never again afterwards...
* @param _mode MIN or MAX heap
* @param _evalObjID function to determine an object's identity
* @param _evalPriority function to determine an objects score
*/
constructor(private _mode = BinaryHeapMode.MIN,
private _evalPriority = (obj: any): number => {
if (typeof obj !== 'number' && typeof obj !== 'string') {
return NaN;
}
if (typeof obj === 'number') {
return obj | 0;
}
return parseInt(obj);
},
private _evalObjID = (obj: any): any => {
return obj;
}
) {
}
getMode(): BinaryHeapMode {
return this._mode;
}
getArray(): Array<any> {
return this._array;
}
getPositions() {
return this._positions;
}
size(): number {
return this._array.length;
}
getEvalPriorityFun(): Function {
return this._evalPriority;
}
evalInputScore(obj: any): number {
return this._evalPriority(obj);
}
getEvalObjIDFun(): Function {
return this._evalObjID;
}
evalInputObjID(obj: any): any {
return this._evalObjID(obj);
}
peek(): any {
return this._array[0];
}
pop() {
if (this.size()) {
return this.remove(this._array[0]);
}
}
find(obj: any): any {
let pos = this.getNodePosition(obj);
return this._array[pos];
}
/**
* Insert - Adding an object to the heap
* @param obj the obj to add to the heap
* @returns {number} the objects index in the internal array
*/
insert(obj: any) {
if (isNaN(this._evalPriority(obj))) {
throw new Error("Cannot insert object without numeric priority.")
}
/**
* @todo if we keep the unique ID stuff, check for it here and throw an Error if needed...
*/
this._array.push(obj);
this.setNodePosition(obj, this.size() - 1);
this.trickleUp(this.size() - 1);
}
remove(obj: any): any {
this._nr_removes++;
if (isNaN(this._evalPriority(obj))) {
throw new Error('Object invalid.');
}
let pos = this.getNodePosition(obj),
found = this._array[pos] != null ? this._array[pos] : null;
if (found === null) {
return undefined;
}
let last_array_obj = this._array.pop();
this.removeNodePosition(obj);
if ( this.size() && found !== last_array_obj ) {
this._array[pos] = last_array_obj;
this.setNodePosition(last_array_obj, pos);
this.trickleUp(pos);
this.trickleDown(pos);
}
return found;
}
private trickleDown(i: number) {
let parent = this._array[i];
while (true) {
let right_child_idx = (i + 1) * 2,
left_child_idx = right_child_idx - 1,
right_child = this._array[right_child_idx],
left_child = this._array[left_child_idx],
swap = null;
// check if left child exists && is larger than parent
if (left_child_idx < this.size() && !this.orderCorrect(parent, left_child)) {
swap = left_child_idx;
}
// check if right child exists && is larger than parent
if (right_child_idx < this.size() && !this.orderCorrect(parent, right_child)
&& !this.orderCorrect(left_child, right_child)) {
swap = right_child_idx;
}
if (swap === null) {
break;
}
// we only have to swap one child, doesn't matter which one
this._array[i] = this._array[swap];
this._array[swap] = parent;
// console.log(`Trickle down: swapping ${this._array[i]} and ${this._array[swap]}`);
this.setNodePosition(this._array[i], i);
this.setNodePosition(this._array[swap], swap);
i = swap;
}
}
private trickleUp(i: number) {
let child = this._array[i];
// Can only trickle up from positive levels
while (i) {
let parent_idx = Math.floor((i + 1) / 2) - 1,
parent = this._array[parent_idx];
if (this.orderCorrect(parent, child)) {
break;
}
else {
this._array[parent_idx] = child;
this._array[i] = parent;
// console.log(`Trickle up: swapping ${child} and ${parent}`);
this.setNodePosition(child, parent_idx);
this.setNodePosition(parent, i);
i = parent_idx;
}
}
}
private orderCorrect(obj_a, obj_b) {
let obj_a_pr = this._evalPriority(obj_a);
let obj_b_pr = this._evalPriority(obj_b);
if (this._mode === BinaryHeapMode.MIN) {
return obj_a_pr <= obj_b_pr;
}
else {
return obj_a_pr >= obj_b_pr;
}
}
/**
* Superstructure to enable search in BinHeap in O(1)
* @param obj
* @param pos
*/
private setNodePosition(obj: any, pos: number) : void {
if ( obj == null || pos == null || pos !== (pos|0) ) {
throw new Error('minium required arguments are obj and new_pos');
}
let pos_obj: PositionHeapEntry = {
score: this.evalInputScore(obj),
position: pos
};
let obj_key = this.evalInputObjID(obj);
this._positions[obj_key] = pos_obj;
}
/**
*
*/
private getNodePosition(obj: any) : number {
let obj_key = this.evalInputObjID(obj);
// console.log(obj_key);
let occurrence : PositionHeapEntry = this._positions[obj_key];
// console.log(occurrence);
return occurrence ? occurrence.position : null;
}
/**
* @param obj
* @returns {number}
*/
private removeNodePosition(obj: any) : void {
let obj_key = this.evalInputObjID(obj);
delete this._positions[obj_key];
}
}
export { BinaryHeap };
import * as $N from '../core/base/BaseNode';
import * as $E from '../core/base/BaseEdge';
import * as $G from '../core/base/BaseGraph';
import * as $MC from '../mincutmaxflow/MinCutMaxFlowBoykov';
export type EnergyFunctionTerm = (arg1: string, arg2: string) => number;
// type EnergyFunctionDataTerm = (arg1: string, ...args: any[]) => number;
// type EnergyFunction = (...args: any[]) => number;
export interface EMEConfig {
directed: boolean; // do we
labeled: boolean;
interactionTerm: EnergyFunctionTerm;
dataTerm: EnergyFunctionTerm;
}
export interface EMEResult {
graph: $G.IGraph;
}
export interface IEMEBoykov {
calculateCycle(): EMEResult;
constructGraph(): $G.IGraph;
initGraph(graph: $G.IGraph): $G.IGraph;
prepareEMEStandardConfig(): EMEConfig;
}
export interface EMEState {
expansionGraph: $G.IGraph;
labeledGraph: $G.IGraph;
activeLabel: string;
energy: number;
}
/**
*
*/
class EMEBoykov implements IEMEBoykov {
private _config: EMEConfig;
private _state: EMEState = {
expansionGraph: null,
labeledGraph: null,
activeLabel: '',
energy: Infinity
};
private _interactionTerm: EnergyFunctionTerm;
private _dataTerm: EnergyFunctionTerm;
constructor(private _graph: $G.IGraph,
private _labels: Array<string>,
config?: EMEConfig) {
this._config = config || this.prepareEMEStandardConfig();
// set the energery functions
this._interactionTerm = this._config.interactionTerm;
this._dataTerm = this._config.dataTerm;
// initialize graph => set labels
this._graph = this.initGraph(_graph);
// init state
this._state.labeledGraph = this._graph.cloneStructure();
this._state.activeLabel = this._labels[0];
}
calculateCycle() {
let success: boolean = true;
let mincut_options: $MC.MCMFConfig = { directed: true };
while (success) {
success = false;
// for each label
for (let i = 0; i < this._labels.length; i++) {
this._state.activeLabel = this._labels[i];
// find a new labeling f'=argminE(f') within one expansion move of f
this._state.expansionGraph = this.constructGraph(); // construct new expansion graph
let source: $N.IBaseNode = this._state.expansionGraph.getNodeById("SOURCE");
let sink: $N.IBaseNode = this._state.expansionGraph.getNodeById("SINK");
// logger.log("compute mincut");
let MinCut: $MC.IMCMFBoykov;
MinCut = new $MC.MCMFBoykov(this._state.expansionGraph, source, sink, mincut_options);
let mincut_result: $MC.MCMFResult = MinCut.calculateCycle();
// logger.log("done mincut");
if (mincut_result.cost < this._state.energy) {
this._state.energy = mincut_result.cost;
this._state.labeledGraph = this.labelGraph(mincut_result, source);
success = true;
}
}
// the minimum can be found in one cycle
if (this._labels.length <= 2) {
break;
}
}
let result: EMEResult = {
graph: this._state.labeledGraph
};
return result;
}
constructGraph(): $G.IGraph {
let graph: $G.IGraph = this._state.labeledGraph.cloneStructure();
// copy node information
let nodes: { [key: string]: $N.IBaseNode } = graph.getNodes();
let node_ids: Array<string> = Object.keys(nodes);
// add source (alpha) and sink (not alpha) to graph
let source: $N.IBaseNode = graph.addNodeByID("SOURCE");
let sink: $N.IBaseNode = graph.addNodeByID("SINK");
// copy edge information now -> will cause infinite loop otherwise
// let edges: {[key: string] : $E.IBaseEdge} = graph.getUndEdges();
let edge_ids: Array<string> = Object.keys(graph.getUndEdges());
let edges_length: number = edge_ids.length;
// for all nodes add
// edge to source and edge to sink
for (let i = 0; i < node_ids.length; i++) {
let node: $N.IBaseNode = nodes[node_ids[i]];
let edge_options: $E.BaseEdgeConfig = { directed: true, weighted: true, weight: 0 };
// add edge to source
edge_options.weight = this._dataTerm(this._state.activeLabel, this._graph.getNodeById(node.getID()).getLabel());
let edge_source: $E.IBaseEdge = graph.addEdgeByID(node.getID() + "_" + source.getID(), node, source, edge_options);
let edge_source_reverse: $E.IBaseEdge = graph.addEdgeByID(source.getID() + "_" + node.getID(), source, node, edge_options);
// add edge to sink
edge_options.weight = (node.getLabel() == this._state.activeLabel) ? Infinity : this._dataTerm(node.getLabel(), this._graph.getNodeById(node.getID()).getLabel());
let edge_sink: $E.IBaseEdge = graph.addEdgeByID(node.getID() + "_" + sink.getID(), node, sink, edge_options);
let edge_sink_source: $E.IBaseEdge = graph.addEdgeByID(sink.getID() + "_" + node.getID(), sink, node, edge_options);
}
// for all neighboring pixels {p, q} where label(p) != label(q) :
// add auxiliary node a_{p_q}
// add edge from auxiliary node to sink
// add edges to auxiliary node (from p and q)
// remove edge between p and q
for (let i = 0; i < edges_length; i++) {
// let edge: $E.IBaseEdge = edges[Object.keys(edges)[i]];
let edge: $E.IBaseEdge = graph.getEdgeById(edge_ids[i]);
let node_p: $N.IBaseNode = edge.getNodes().a;
let node_q: $N.IBaseNode = edge.getNodes().b;
let edge_options: $E.BaseEdgeConfig = { directed: true, weighted: true, weight: 0 };
// we don't care further for nodes of same labels
if (node_p.getLabel() == node_q.getLabel()) {
// just set the edge weight and convert to directed
edge_options.weight = this._interactionTerm(node_p.getLabel(), this._state.activeLabel);
graph.deleteEdge(edge);
graph.addEdgeByID(node_p.getID() + "_" + node_q.getID(), node_p, node_q, edge_options);
graph.addEdgeByID(node_q.getID() + "_" + node_p.getID(), node_q, node_p, edge_options);
continue;
}
// add auxiliary node
let node_aux: $N.IBaseNode = graph.addNodeByID("aux_" + node_p.getID() + "_" + node_q.getID());
// add 3 edges [{p, aux}, {aux, q}, {aux, sink}]
// add edge {p, aux}
edge_options.weight = this._interactionTerm(node_p.getLabel(), this._state.activeLabel);
let edge_p_aux: $E.IBaseEdge = graph.addEdgeByID(node_p.getID() + "_" + node_aux.getID(), node_p, node_aux, edge_options);
let edge_p_aux_reverse: $E.IBaseEdge = graph.addEdgeByID(node_aux.getID() + "_" + node_p.getID(), node_aux, node_p, edge_options);
// add edge {aux, q}
edge_options.weight = this._interactionTerm(this._state.activeLabel, node_q.getLabel());
let edge_aux_q: $E.IBaseEdge = graph.addEdgeByID(node_aux.getID() + "_" + node_q.getID(), node_aux, node_q, edge_options);
let edge_aux_q_reverse: $E.IBaseEdge = graph.addEdgeByID(node_q.getID() + "_" + node_aux.getID(), node_q, node_aux, edge_options);
// add edge {aux, sink}
edge_options.weight = this._interactionTerm(node_p.getLabel(), node_q.getLabel());
let edge_aux_sink: $E.IBaseEdge = graph.addEdgeByID(node_aux.getID() + "_" + sink.getID(), node_aux, sink, edge_options);
let edge_aux_sink_reverse: $E.IBaseEdge = graph.addEdgeByID(sink.getID() + "_" + node_aux.getID(), sink, node_aux, edge_options);
// remove the edge between p and q
graph.deleteEdge(edge);
}
return graph;
}
// label a graph based on the result of a mincut
labelGraph(mincut: $MC.MCMFResult, source: $N.IBaseNode) {
let graph: $G.IGraph = this._state.labeledGraph;
source = this._state.expansionGraph.getNodeById("SOURCE");
for (let i = 0; i < mincut.edges.length; i++) {
let edge: $E.IBaseEdge = mincut.edges[i];
let node_a: $N.IBaseNode = edge.getNodes().a;
let node_b: $N.IBaseNode = edge.getNodes().b;
if (node_a.getID() == source.getID()) {
graph.getNodeById(node_b.getID()).setLabel(this._state.activeLabel);
continue;
}
if (node_b.getID() == source.getID()) {
graph.getNodeById(node_a.getID()).setLabel(this._state.activeLabel);
}
}
return graph;
}
initGraph(graph: $G.IGraph) {
let nodes = graph.getNodes();
let node_ids: Array<string> = Object.keys(nodes);
let nodes_length: number = node_ids.length;
for (let i = 0; i < nodes_length; i++) {
// let node: $N.IBaseNode = nodes[Object.keys(nodes)[i]];
let node: $N.IBaseNode = nodes[node_ids[i]];
node.setLabel(node.getFeature('label'));
}
return graph;
}
prepareEMEStandardConfig(): EMEConfig {
// we use the potts model as standard interaction term
let interactionTerm: EnergyFunctionTerm = function (label_a: string, label_b: string) {
return (label_a == label_b) ? 0 : 1;
};
// squared difference of new label and observed label as standard data term
// label: new label; node_id is needed to get the original(observed) label
let dataTerm: EnergyFunctionTerm = function (label: string, observed: string) {
// get the label of the same node in the original graph
// let observed: string = this._graph.getNodeById(node_id).getLabel();
let label_number: number = Number(label);
let observed_number: number = Number(observed);
if (isNaN(label_number) || isNaN(observed_number)) {
throw new Error('Cannot convert labels to numbers!');
}
return 1.5 * Math.pow(label_number - observed_number, 2);
};
return {
directed: false,
labeled: false,
interactionTerm: interactionTerm,
dataTerm: dataTerm
}
}
}
export {
EMEBoykov
};
import * as $N from '../core/base/BaseNode';
import * as $E from '../core/base/BaseEdge';
import * as $G from '../core/base/BaseGraph';
export interface KROLConfig {
genMat: Array<Array<number> >;
// generator: $G.IGraph;
cycles: number;
}
export interface KROLResult {
graph: $G.IGraph;
}
export interface IKROL {
generate() : KROLResult;
prepareKROLStandardConfig() : KROLConfig;
}
class KROL implements IKROL {
private _config : KROLConfig;
// private _generator : $G.IGraph;
private _genMat : number[][];
private _cycles : number;
private _graph : $G.IGraph;
constructor( config? : KROLConfig )
{
this._config = config || this.prepareKROLStandardConfig();
// this._generator = this._config.generator;
// TODO: use the adjacency matrix form the generator graph
// as soon as the issues from computing the adjacency matrix are fixe
// this._genMat = this._generator.adjListArray();
this._genMat = this._config.genMat;
this._cycles = this._config.cycles;
this._graph = new $G.BaseGraph('synth');
}
generate() {
// var gen_dims = this._generator.nrNodes();
var gen_dims = this._genMat[0].length;
var res_dims = Math.pow(gen_dims, this._cycles+1);
for (let index = 0; index < res_dims; index++) {
this._graph.addNodeByID(index.toString());
}
var nr_edges: number = 0;
for (let node1 = 0; node1 < res_dims; node1++) {
for (let node2 = 0; node2 < res_dims; node2++) {
if (this.addEdge(node1, node2, gen_dims)) {
this._graph.addEdgeByNodeIDs(node1 + '_' + node2, node1.toString(), node2.toString());
++nr_edges;
}
}
}
var result : KROLResult = {
graph : this._graph
};
return result;
}
addEdge(node1: number, node2: number, dims: number) : boolean {
var rprob: number = Math.random();
var prob: number = 1.0;
for (let level = 0; level < this._cycles; level++) {
var id_1 = Math.floor(node1 / Math.pow(dims, level+1)) % dims;
var id_2 = Math.floor(node2 / Math.pow(dims, level+1)) % dims;
prob *= this._genMat[id_1][id_2];
if (rprob > prob) { return false; }
}
return true;
}
prepareKROLStandardConfig() : KROLConfig {
// var generator: $G.IGraph = new $G.BaseGraph('generator');
// var node_a = generator.addNodeByID('a');
// var node_b = generator.addNodeByID('b');
// var edge_ab_id: string = node_a.getID() + '_' + node_b.getID();
// var edge_ba_id: string = node_b.getID() + '_' + node_a.getID();
// var edge_aa_id: string = node_a.getID() + '_' + node_a.getID();
// var edge_bb_id: string = node_b.getID() + '_' + node_b.getID();
// generator.addEdgeByID(edge_ab_id, node_a, node_b, {weighted: true, weight: 0.9});
// generator.addEdgeByID(edge_ba_id, node_b, node_a, {weighted: true, weight: 0.5});
// generator.addEdgeByID(edge_aa_id, node_a, node_a, {weighted: true, weight: 0.5});
// generator.addEdgeByID(edge_bb_id, node_b, node_b, {weighted: true, weight: 0.1});
var genMat = [[0.9, 0.5], [0.5, 0.1]];
return {
// generator: generator,
genMat: genMat,
cycles: 5
}
}
}
export {
KROL
};
import { BaseEdge, IBaseEdge } from '../../core/base/BaseEdge';
import { TypedEdge, ITypedEdge } from '../../core/typed/TypedEdge';
import { IBaseNode, NeighborEntry } from '../../core/base/BaseNode';
import { IGraph } from '../../core/base/BaseGraph';
import { TypedGraph } from '../../core/typed/TypedGraph';
export interface PotentialEdgeInfo {
a : IBaseNode;
b : IBaseNode;
label? : string;
dir : boolean;
weighted : boolean;
weight? : number;
typed : boolean;
type? : string;
}
class EdgeDupeChecker {
constructor( private _graph: IGraph | TypedGraph ) {}
isDupe(e: PotentialEdgeInfo): boolean {
let pds = this.potentialEndpoints(e);
if ( !pds.size ) {
return false;
}
// logger.log(`Got ${pds.size} potential edge dupe`);
for ( let pd of pds.values() ) {
if ( !EdgeDupeChecker.checkTypeWeightEquality(e, pd)
|| !EdgeDupeChecker.typeWeightDupe(e, pd) ) {
pds.delete(pd);
}
}
return !!pds.size;
}
potentialEndpoints(e: PotentialEdgeInfo): Set<IBaseEdge | ITypedEdge> {
const result = new Set<IBaseEdge | ITypedEdge>();
if ( e.dir ) {
e.a.nextNodes().forEach(ne => {
(ne.node === e.b) && result.add(ne.edge);
});
}
else {
e.a.connNodes().forEach(ne => {
(ne.node === e.b) && result.add(ne.edge);
});
}
return result;
}
/**
* @todo has no effect on test cases - either
* -) test cases are not granular enough
* -) typed-weighted-equality is irrelevant
* @param e struct with potential edge info
* @param oe other edge: IBaseEdge
*/
static checkTypeWeightEquality(e: PotentialEdgeInfo, oe: IBaseEdge): boolean {
return BaseEdge.isTyped(oe) === e.typed && e.weighted === oe.isWeighted();
}
static typeWeightDupe(e: PotentialEdgeInfo, oe: IBaseEdge) : boolean {
const neitherTypedNorWeighted = !e.typed && !e.weighted;
const notTypedButWeighted = !e.typed && e.weighted;
const weightEqual = e.weight === oe.getWeight();
const typeEqual = e.typed && BaseEdge.isTyped(oe) && e.type === oe.type;
return ( neitherTypedNorWeighted || notTypedButWeighted && weightEqual || typeEqual );
}
}
export {
EdgeDupeChecker
}
import path = require('path');
import fs = require('fs');
import http = require('http');
import * as $N from '../../core/base/BaseNode';
import * as $E from '../../core/base/BaseEdge';
import * as $G from '../../core/base/BaseGraph';
import * as $R from '../../utils/RemoteUtils';
const DEFAULT_WEIGHT = 1;
const CSV_EXTENSION = ".csv";
export interface ICSVInConfig {
separator? : string;
explicit_direction? : boolean;
direction_mode? : boolean;
weighted? : boolean;
}
export interface ICSVInput {
_config : ICSVInConfig;
readFromAdjacencyListFile(filepath : string) : $G.IGraph;
readFromAdjacencyList(input : Array<string>, graph_name : string) : $G.IGraph;
readFromAdjacencyListURL(config : $R.RequestConfig, cb : Function);
readFromEdgeListFile(filepath : string) : $G.IGraph;
readFromEdgeList(input : Array<string>, graph_name: string) : $G.IGraph;
readFromEdgeListURL(config : $R.RequestConfig, cb : Function);
}
class CSVInput implements ICSVInput {
_config : ICSVInConfig;
constructor( config: ICSVInConfig = {} ) {
this._config = {
separator: config.separator != null ? config.separator : ',',
explicit_direction: config.explicit_direction != null ? config.explicit_direction : true,
direction_mode: config.direction_mode != null ? config.direction_mode : false,
weighted: config.weighted != null ? config.weighted : false
};
}
readFromAdjacencyListURL(config : $R.RequestConfig, cb : Function) {
this.readGraphFromURL(config, cb, this.readFromAdjacencyList);
}
readFromEdgeListURL(config : $R.RequestConfig, cb : Function) {
this.readGraphFromURL(config, cb, this.readFromEdgeList);
}
private readGraphFromURL(config: $R.RequestConfig, cb: Function, localFun: Function) {
let self = this,
graph_name = config.file_name,
graph : $G.IGraph,
request;
$R.checkNodeEnvironment()
$R.retrieveRemoteFile(config, function(raw_graph) {
let input = raw_graph.toString().split('\n');
graph = localFun.apply(self, [input, graph_name]);
cb(graph, undefined);
});
}
readFromAdjacencyListFile(filepath : string) : $G.IGraph {
return this.readFileAndReturn(filepath, this.readFromAdjacencyList);
}
readFromEdgeListFile(filepath : string) : $G.IGraph {
return this.readFileAndReturn(filepath, this.readFromEdgeList);
}
private readFileAndReturn(filepath: string, func: Function) : $G.IGraph {
$R.checkNodeEnvironment();
let graph_name = path.basename(filepath);
let input = fs.readFileSync(filepath).toString().split('\n');
return func.apply(this, [input, graph_name]);
}
readFromAdjacencyList(input : Array<string>, graph_name : string) : $G.IGraph {
let graph = new $G.BaseGraph(graph_name);
for ( let idx in input ) {
let line = input[idx],
elements = this._config.separator.match(/\s+/g) ? line.match(/\S+/g) : line.replace(/\s+/g, '').split(this._config.separator),
node_id = elements[0],
node : $N.IBaseNode,
edge_array = elements.slice(1),
edge : $E.IBaseEdge,
target_node_id : string,
target_node : $N.IBaseNode,
dir_char: string,
directed: boolean,
edge_id: string,
edge_id_u2: string;
if ( !node_id ) {
// end of file or empty line, just treat like an empty line...
continue;
}
node = graph.hasNodeID(node_id) ? graph.getNodeById(node_id) : graph.addNodeByID(node_id);
for ( let e = 0; e < edge_array.length; ) {
if ( this._config.explicit_direction && ( !edge_array || edge_array.length % 2 ) ) {
throw new Error('Every edge entry has to contain its direction info in explicit mode.');
}
target_node_id = edge_array[e++];
target_node = graph.hasNodeID(target_node_id) ? graph.getNodeById(target_node_id) : graph.addNodeByID(target_node_id);
/**
* The direction determines if we have to check for the existence
* of an edge in 'both' directions or only from one node to the other
* Within the CSV module this check is done simply via ID check,
* as we are following a rigorous naming scheme anyways...
*/
dir_char = this._config.explicit_direction ? edge_array[e++] : this._config.direction_mode ? 'd' : 'u';
if ( dir_char !== 'd' && dir_char !== 'u' ) {
throw new Error("Specification of edge direction invalid (d and u are valid).");
}
directed = dir_char === 'd';
edge_id = node_id + "_" + target_node_id + "_" + dir_char;
edge_id_u2 = target_node_id + "_" + node_id + "_" + dir_char;
if ( graph.hasEdgeID(edge_id) || ( !directed && graph.hasEdgeID(edge_id_u2) ) ) {
// The completely same edge should only be added once...
continue;
}
else {
edge = graph.addEdgeByID(edge_id, node, target_node, {directed: directed});
}
}
}
return graph;
}
readFromEdgeList(input : Array<string>, graph_name : string, weighted = false) : $G.IGraph {
let graph = new $G.BaseGraph(graph_name);
for ( let idx in input ) {
let line = input[idx],
elements = this._config.separator.match(/\s+/g) ? line.match(/\S+/g) : line.replace(/\s+/g, '').split(this._config.separator);
if ( ! elements ) {
// end of file or empty line, just treat like an empty line...
continue;
}
if ( elements.length < 2 || elements.length > 3 ) {
throw new Error('Edge list is in wrong format - every line has to consist of two entries (the 2 nodes)');
}
let node_id = elements[0],
node : $N.IBaseNode,
target_node : $N.IBaseNode,
edge : $E.IBaseEdge,
target_node_id = elements[1],
dir_char = this._config.explicit_direction ? elements[2] : this._config.direction_mode ? 'd' : 'u',
directed: boolean,
edge_id: string,
edge_id_u2: string,
parse_weight: number,
edge_weight: number;
node = graph.hasNodeID(node_id) ? graph.getNodeById(node_id) : graph.addNodeByID(node_id);
target_node = graph.hasNodeID(target_node_id) ? graph.getNodeById(target_node_id) : graph.addNodeByID(target_node_id);
if ( dir_char !== 'd' && dir_char !== 'u' ) {
throw new Error("Specification of edge direction invalid (d and u are valid).");
}
directed = dir_char === 'd';
edge_id = node_id + "_" + target_node_id + "_" + dir_char;
edge_id_u2 = target_node_id + "_" + node_id + "_" + dir_char;
parse_weight = parseFloat(elements[2]);
edge_weight = this._config.weighted ? (isNaN(parse_weight) ? DEFAULT_WEIGHT : parse_weight) : null;
/**
* @todo introduce Edge Dupe Checker and replace this logic
*/
if ( graph.hasEdgeID(edge_id) || ( !directed && graph.hasEdgeID(edge_id_u2) ) ) {
continue;
}
else if (this._config.weighted) {
edge = graph.addEdgeByID(edge_id, node, target_node, {directed: directed, weighted: true, weight: edge_weight});
}
else {
edge = graph.addEdgeByID(edge_id, node, target_node, {directed: directed});
}
}
return graph;
}
}
export {
CSVInput
};
import * as fs from 'fs';
import {IBaseEdge} from '../../core/base/BaseEdge';
import {IBaseNode} from "../../core/base/BaseNode";
import {ITypedNode} from "../../core/typed/TypedNode";
import {TypedGraph} from "../../core/typed/TypedGraph";
import {IGraph, BaseGraph} from '../../core/base/BaseGraph';
import * as $R from '../../utils/RemoteUtils';
import {labelKeys} from '../interfaces';
import {EdgeDupeChecker, PotentialEdgeInfo} from '../common/Dupes';
import * as uuid from 'uuid'
const v4 = uuid.v4;
import {Logger} from '../../utils/Logger';
const logger = new Logger();
const DEFAULT_WEIGHT: number = 1;
export interface JSONEdge {
to: string;
directed?: string;
weight?: string;
type?: string;
}
export interface JSONNode {
edges: Array<JSONEdge>;
coords?: { [key: string]: Number };
features?: { [key: string]: any };
}
export interface JSONGraph {
typeRLT: {nodes: {}, edges: {}};
name: string;
nodes: number;
edges: number;
data: { [key: string]: JSONNode };
}
export interface IJSONInConfig {
explicit_direction? : boolean;
directed? : boolean;
weighted? : boolean;
typed? : boolean;
dupeCheck? : boolean;
}
export interface IJSONInput {
_config: IJSONInConfig;
readFromJSONFile(file: string, graph?: IGraph): IGraph;
readFromJSON(json: {}, graph?: IGraph): IGraph;
readFromJSONURL(config: $R.RequestConfig, cb: Function, graph?: IGraph): void;
}
class JSONInput implements IJSONInput {
_config: IJSONInConfig;
constructor(config: IJSONInConfig = {}) {
this._config = {
explicit_direction: config.explicit_direction != null ? config.explicit_direction : true,
directed: config.directed != null ? config.directed : false,
weighted: config.weighted != null ? config.weighted : false,
dupeCheck: config.dupeCheck != null ? config.dupeCheck : true
};
}
readFromJSONFile(filepath: string, graph?: IGraph): IGraph {
$R.checkNodeEnvironment();
// TODO test for existing file...
let json = JSON.parse(fs.readFileSync(filepath).toString());
return this.readFromJSON(json, graph);
}
readFromJSONURL(config: $R.RequestConfig, cb: Function, graph?: IGraph): void {
const self = this;
// Assert we are in Node.js environment
$R.checkNodeEnvironment();
// Node.js
$R.retrieveRemoteFile(config, function (raw_graph) {
graph = self.readFromJSON(JSON.parse(raw_graph), graph);
cb(graph, undefined);
});
}
readFromJSON(json: JSONGraph, graph?: IGraph | TypedGraph): IGraph | TypedGraph {
graph = graph || new BaseGraph(json.name);
const edc = new EdgeDupeChecker(graph);
const rlt = json.typeRLT;
// logger.log(rlt);
this.addNodesToGraph(json, graph);
for (let node_id in json.data) {
let node = graph.getNodeById(node_id);
// Reading and instantiating edges
let edges = json.data[node_id][labelKeys.edges];
for (let e in edges) {
const edge_input = edges[e];
// BASE INFO
const target_node = this.getTargetNode(graph, edge_input);
const edge_label = edge_input[labelKeys.e_label];
const edge_type = rlt && rlt.edges[edge_input[labelKeys.e_type]] || null;
// DIRECTION
const directed = this._config.explicit_direction ? !!edge_input[labelKeys.e_dir] : this._config.directed;
// WEIGHTS
const weight_float = JSONInput.handleEdgeWeights(edge_input);
const weight_info = weight_float === weight_float ? weight_float : DEFAULT_WEIGHT;
const edge_weight = this._config.weighted ? weight_info : undefined;
// EDGE_ID creation
/**
* @todo replace with uuid v4() -> then clean up the mess... ;-)
*/
const target_node_id = edge_input[labelKeys.e_to];
const dir_char = directed ? 'd' : 'u';
const edge_id = node_id + "_" + target_node_id + "_" + dir_char;
// DUPLICATE or CREATE ??
const newEdge: PotentialEdgeInfo = {
a: node,
b: target_node,
label: edge_label,
dir: directed,
weighted: this._config.weighted,
weight: edge_weight,
typed: !!edge_type,
type: edge_type
};
if ( this._config.dupeCheck && edc.isDupe(newEdge) ) {
// Don't throw, just log
// logger.log(`Edge ${edge_id} is a duplicate according to assumptions... omitting.`);
continue;
}
graph.addEdgeByID(edge_id, node, target_node, {
label: edge_label,
directed: directed,
weighted: this._config.weighted,
weight: edge_weight,
typed: !!edge_type,
type: edge_type
});
}
}
return graph;
}
addNodesToGraph(json: JSONGraph, graph: IGraph) {
const rlt = json.typeRLT;
let
coords_json: { [key: string]: any },
coords: { [key: string]: Number },
coord_idx: string,
features: { [key: string]: any };
for (let node_id in json.data) {
const type = BaseGraph.isTyped(graph) ? rlt && rlt.nodes[json.data[node_id][labelKeys.n_type]] : null;
const label = json.data[node_id][labelKeys.n_label];
const node = graph.addNodeByID(node_id, {label, type});
// Here we set the reference...?
features = json.data[node_id][labelKeys.n_features];
if (features) {
node.setFeatures(features);
}
// Here we copy...?
coords_json = json.data[node_id][labelKeys.coords];
if (coords_json) {
coords = {};
for (coord_idx in coords_json) {
coords[coord_idx] = +coords_json[coord_idx];
}
node.setFeature(labelKeys.coords, coords);
}
}
}
/**
* @todo implicitly add nodes referenced by edge
* but not present in graph input JSON ?
*/
getTargetNode(graph, edge_input): IBaseNode | ITypedNode {
const target_node_id = edge_input[labelKeys.e_to];
const target_node = graph.getNodeById(target_node_id);
if (!target_node) {
throw new Error('Node referenced by edge does not exist');
}
return target_node;
}
/**
* Infinity & -Infinity cases are redundant, as JavaScript
* handles them correctly anyways (for now)
* @param edge_input
*/
static handleEdgeWeights(edge_input): number {
switch (edge_input[labelKeys.e_weight]) {
case "undefined":
return DEFAULT_WEIGHT;
case "Infinity":
return Number.POSITIVE_INFINITY;
case "-Infinity":
return Number.NEGATIVE_INFINITY;
case "MAX":
return Number.MAX_VALUE;
case "MIN":
return Number.MIN_VALUE;
default:
return parseFloat(edge_input[labelKeys.e_weight])
}
}
}
export {JSONInput}
export interface Abbreviations {
coords : string;
n_label : string;
n_type : string;
edges : string;
n_features : string;
e_to : string;
e_dir : string;
e_weight : string;
e_label : string;
e_type : string;
e_features : string;
}
export const labelKeys: Abbreviations = {
coords : 'c',
n_label : 'l',
n_type : 'x',
n_features : 'f',
edges : 'e',
e_to : 't', // a->b
e_dir : 'd',
e_weight : 'w',
e_label : 'l',
e_type : 'y',
e_features : 'f'
};
import fs = require('fs');
import * as $N from '../../core/base/BaseNode';
import * as $G from '../../core/base/BaseGraph';
export interface ICSVOutConfig {
separator? : string; // default => ','
explicit_direction? : boolean; // default => true
direction_mode? : boolean; // default => false
weighted? : boolean; // true => try to read weights from file, else DEFAULT WEIGHT
}
export interface ICSVOutput {
_config: ICSVOutConfig;
writeToAdjacencyListFile(filepath : string, graph : $G.IGraph) : void;
writeToAdjacencyList(graph : $G.IGraph) : string;
writeToEdgeListFile(filepath : string, graph : $G.IGraph, weighted: boolean) : void;
writeToEdgeList(graph : $G.IGraph, weighted: boolean) : string;
}
class CSVOutput implements ICSVOutput {
_config: ICSVOutConfig;
constructor(config?: ICSVOutConfig) {
this._config = config || {
separator: config && config.separator || ',',
explicit_direction: config && config.explicit_direction || true,
direction_mode: config && config.direction_mode || false
// weighted: config && config.weighted || false
};
}
writeToAdjacencyListFile(filepath : string, graph : $G.IGraph) : void {
if ( typeof window !== 'undefined' && window !== null ) {
throw new Error('cannot write to File inside of Browser');
}
fs.writeFileSync(filepath, this.writeToAdjacencyList(graph));
}
writeToAdjacencyList(graph : $G.IGraph) : string {
let graphString = "";
let nodes = graph.getNodes(),
node : $N.IBaseNode = null,
adj_nodes : Array<$N.NeighborEntry> = null,
adj_node : $N.IBaseNode = null;
// TODO make generic for graph mode
for ( let node_key in nodes ) {
node = nodes[node_key];
graphString += node.getID();
adj_nodes = node.reachNodes(this.mergeFunc);
for ( let adj_idx in adj_nodes ) {
adj_node = adj_nodes[adj_idx].node;
graphString += this._config.separator + adj_node.getID();
}
graphString += "\n";
}
return graphString;
}
writeToEdgeListFile(filepath : string, graph : $G.IGraph, weighted : boolean = false) : void {
if ( typeof window !== 'undefined' && window !== null ) {
throw new Error('cannot write to File inside of Browser');
}
fs.writeFileSync(filepath, this.writeToEdgeList(graph, weighted));
}
/**
* Directed before undirected
*
* @param graph
* @param weighted
*/
writeToEdgeList(graph : $G.IGraph, weighted : boolean = false) : string {
let graphString = "",
nodes = graph.getNodes(),
node : $N.IBaseNode = null,
adj_nodes : Array<$N.NeighborEntry> = null,
adj_entry : $N.NeighborEntry,
adj_node : $N.IBaseNode = null,
weight_str: string;
for ( let node_key in nodes ) {
node = nodes[node_key];
adj_nodes = node.reachNodes(this.mergeFunc);
for ( let adj_idx in adj_nodes ) {
adj_entry = adj_nodes[adj_idx];
adj_node = adj_entry.node;
weight_str = '';
if ( weighted ) {
weight_str = this._config.separator;
weight_str += adj_entry.edge.isWeighted() ? adj_entry.edge.getWeight() : 1;
}
graphString += node.getID() + this._config.separator + adj_node.getID() + weight_str + '\n';
}
}
return graphString;
}
private mergeFunc(ne: $N.NeighborEntry) {
return ne.node.getID();
}
}
export { CSVOutput };
import fs = require('fs');
import * as $N from '../../core/base/BaseNode';
import * as $E from '../../core/base/BaseEdge';
import * as $G from '../../core/base/BaseGraph';
import {labelKeys} from '../interfaces';
import {BaseEdge} from "../../core/base/BaseEdge";
import {BaseNode} from "../../core/base/BaseNode";
import {TypedGraph} from "../../core/typed/TypedGraph";
import {BaseGraph} from "../../core/base/BaseGraph";
export interface IJSONOutput {
writeToJSONFile(filepath: string, graph: $G.IGraph): void;
writeToJSONString(graph: $G.IGraph): string;
}
export interface TypeLUT {
nodes: { [key: string]: string };
edges: { [key: string]: string };
}
const startChar: number = 64;
class JSONOutput implements IJSONOutput {
// constructor() {}
constructTypeRLUT(g: TypedGraph): [TypeLUT, TypeLUT] {
let nchar = startChar;
let echar = startChar;
const lut: TypeLUT = {
nodes: {},
edges: {}
};
const rlut: TypeLUT = {
nodes: {},
edges: {}
};
const ntypes = g.nodeTypes();
for (let t of ntypes) {
lut.nodes[t] = String.fromCharCode(nchar);
rlut.nodes[String.fromCharCode(nchar++)] = t;
}
const etypes = g.edgeTypes();
for ( let t of etypes ) {
lut.edges[t] = String.fromCharCode(echar);
rlut.edges[String.fromCharCode(echar++)] = t;
}
return [lut, rlut];
}
writeToJSONFile(filepath: string, graph: $G.IGraph): void {
if (typeof window !== 'undefined' && window !== null) {
throw new Error('cannot write to File inside of Browser');
}
fs.writeFileSync(filepath, this.writeToJSONString(graph));
}
writeToJSONString(graph: $G.IGraph): string {
let lut: TypeLUT = null;
let rlt: TypeLUT = null;
let nodes: { [key: string]: $N.IBaseNode },
node: $N.IBaseNode,
node_struct,
und_edges: { [key: string]: $E.IBaseEdge } | {},
dir_edges: { [key: string]: $E.IBaseEdge } | {},
edge: $E.IBaseEdge,
coords;
let result = {
name: graph.label,
nodes: graph.nrNodes(),
dir_e: graph.nrDirEdges(),
und_e: graph.nrUndEdges(),
data: {}
};
if ( BaseGraph.isTyped(graph) ) {
[lut, rlt] = this.constructTypeRLUT(graph);
}
if ( rlt ) {
result['typeRLT'] = rlt;
}
// Go through all nodes
nodes = graph.getNodes();
for (let node_key in nodes) {
node = nodes[node_key];
node_struct = result.data[node.getID()] = {
[labelKeys.edges]: []
};
if (node.getID() !== node.getLabel()) {
node_struct[labelKeys.n_label] = node.label;
}
if (BaseNode.isTyped(node)) {
node_struct[labelKeys.n_type] = lut && lut.nodes[node.type];
}
/* -------------------------------------- */
/* UNDIRECTED edges */
/* -------------------------------------- */
und_edges = node.undEdges();
for (let edge_key in und_edges) {
edge = und_edges[edge_key];
let endPoints = edge.getNodes();
let edgeStruct = {
[labelKeys.e_to]: endPoints.a.getID() === node.getID() ? endPoints.b.getID() : endPoints.a.getID(),
[labelKeys.e_dir]: edge.isDirected() ? 1 : 0,
[labelKeys.e_weight]: JSONOutput.handleEdgeWeight(edge)
};
if ( Object.keys(edge.getFeatures()).length ) {
edgeStruct[labelKeys.e_features] = JSON.stringify(edge.getFeatures())
}
if (edge.getID() !== edge.getLabel()) {
edgeStruct[labelKeys.e_label] = edge.getLabel();
}
if (BaseEdge.isTyped(edge)) {
edgeStruct[labelKeys.e_type] = lut && lut.edges[edge.type];
}
node_struct[labelKeys.edges].push(edgeStruct);
}
/* -------------------------------------- */
/* DIRECTED edges */
/* -------------------------------------- */
dir_edges = node.outEdges();
for (let edge_key in dir_edges) {
edge = dir_edges[edge_key];
let endPoints = edge.getNodes();
let edgeStruct = {
[labelKeys.e_to]: endPoints.b.getID(),
[labelKeys.e_dir]: edge.isDirected() ? 1 : 0,
[labelKeys.e_weight]: JSONOutput.handleEdgeWeight(edge)
};
if ( Object.keys(edge.getFeatures()).length ) {
edgeStruct[labelKeys.e_features] = JSON.stringify(edge.getFeatures())
}
if (edge.getID() !== edge.getLabel()) {
edgeStruct[labelKeys.e_label] = edge.getLabel();
}
if (BaseEdge.isTyped(edge)) {
edgeStruct[labelKeys.e_type] = lut && lut.edges[edge.type];
}
node_struct[labelKeys.edges].push(edgeStruct);
}
// Features
node_struct[labelKeys.n_features] = node.getFeatures();
// Coords (shall we really?)
if ((coords = node.getFeature(labelKeys.coords)) != null) {
node_struct[labelKeys.coords] = coords;
}
}
return JSON.stringify(result);
}
static handleEdgeWeight(edge: $E.IBaseEdge): string | number {
if (!edge.isWeighted()) {
return undefined;
}
switch (edge.getWeight()) {
case Number.POSITIVE_INFINITY:
return 'Infinity';
case Number.NEGATIVE_INFINITY:
return '-Infinity';
case Number.MAX_VALUE:
return 'MAX';
case Number.MIN_VALUE:
return 'MIN';
default:
return edge.getWeight();
}
}
}
export {JSONOutput}
import * as $N from '../core/base/BaseNode';
import * as $E from '../core/base/BaseEdge';
import * as $G from '../core/base/BaseGraph';
import { Logger } from '../utils/Logger';
// const logger = new Logger();
export interface MCMFConfig {
directed: boolean; // do we
}
export interface MCMFResult {
edges : Array<$E.IBaseEdge>;
edgeIDs: Array<string>;
cost : number;
}
export interface IMCMFBoykov {
calculateCycle() : MCMFResult;
convertToDirectedGraph(graph : $G.IGraph) : $G.IGraph;
prepareMCMFStandardConfig() : MCMFConfig;
}
export interface MCMFState {
residGraph : $G.IGraph;
activeNodes : {[key:string] : $N.IBaseNode};
orphans : {[key:string] : $N.IBaseNode};
treeS : {[key:string] : $N.IBaseNode};
treeT : {[key:string] : $N.IBaseNode};
parents : {[key:string] : $N.IBaseNode};
path : Array<$N.IBaseNode>;
tree : {[key:string] : string};
}
class MCMFBoykov implements IMCMFBoykov {
private _config : MCMFConfig;
private _state : MCMFState = {
residGraph : null,
activeNodes : {},
orphans : {},
treeS : {},
treeT : {},
parents : {},
path : [],
tree : {}
// undGraph : null
};
constructor( private _graph : $G.IGraph,
private _source : $N.IBaseNode,
private _sink : $N.IBaseNode,
config? : MCMFConfig )
{
this._config = config || this.prepareMCMFStandardConfig();
if (this._config.directed) {
this.renameEdges(_graph);
}
this._state.residGraph = this._graph;
if (!this._config.directed) {
// convert the undirected graph to a directed one
this._state.residGraph = this.convertToDirectedGraph(this._state.residGraph);
// update source and sink
this._source = this._state.residGraph.getNodeById(this._source.getID());
this._sink = this._state.residGraph.getNodeById(this._sink.getID());
}
}
calculateCycle() {
const result: MCMFResult = {
edges: [],
edgeIDs: [],
cost: 0
};
// init
this._state.treeS[this._source.getID()] = this._source;
this._state.tree[this._source.getID()] = "S";
this._state.treeT[this._sink.getID()] = this._sink;
this._state.tree[this._sink.getID()] = "T";
this._state.activeNodes[this._source.getID()] = this._source;
this._state.activeNodes[this._sink.getID()] = this._sink;
let nrCycles = 0;
while(true) {
// logger.log("grow");
this.grow();
if (!this._state.path.length) {
break;
}
// logger.log("augment");
this.augmentation();
// logger.log("adopt");
this.adoption();
++nrCycles;
// logger.log(nrCycles);
}
// compute the cut edges and the total cost of the cut
// let tree_ids = Object.keys(this._state.tree);
// let tree_length = tree_ids.length;
// let size_S = 0;
// for (let i = 0; i < tree_length; i++) {
// if (this._state.tree[tree_ids[i]] == "S") {
// ++size_S;
// }
// }
/**
* computing result
*/
const smallTree = (Object.keys(this._state.treeS).length < Object.keys(this._state.treeT).length) ? this._state.treeS : this._state.treeT;
const smallTree_size: number = Object.keys(smallTree).length;
const smallTree_ids: Array<string> = Object.keys(smallTree);
for (let i = 0; i < smallTree_size; i++) {
// let node_id: string = smallTree[Object.keys(smallTree)[i]].getID();
const node_id: string = smallTree_ids[i];
const node: $N.IBaseNode = this._graph.getNodeById(node_id);
// if undirected
if (!this._config.directed) {
const undEdges: { [keys: string]: $E.IBaseEdge } = node.undEdges();
const undEdges_size: number = Object.keys(undEdges).length;
const undEdges_ids: Array<string> = Object.keys(undEdges);
for (let i = 0; i < undEdges_size; i++) {
// let edge: $E.IBaseEdge = undEdges[Object.keys(undEdges)[i]];
let edge: $E.IBaseEdge = undEdges[undEdges_ids[i]];
let neighbor: $N.IBaseNode = (edge.getNodes().a.getID() == node.getID()) ? edge.getNodes().b : edge.getNodes().a;
// if (this.tree(neighbor) != this.tree(node)) {
if (this._state.tree[neighbor.getID()] != this._state.tree[node.getID()]) {
// we found a an edge which is part of the Cut
result.edges.push(edge);
result.edgeIDs.push(edge.getID());
result.cost += edge.getWeight();
}
}
}
else {
/*TODO refactor! object.keys is fucking slow... see above!
*/
/* if directed
*/
const outEdges_ids: Array<string> = Object.keys(node.outEdges());
const outEdges_length: number = outEdges_ids.length;
const inEdges_ids: Array<string> = Object.keys(node.inEdges());
const inEdges_length: number = inEdges_ids.length;
// check outEdges
for (let i = 0; i < outEdges_length; i++) {
// let edge: $E.IBaseEdge = outEdges[Object.keys(outEdges)[i]];
let edge: $E.IBaseEdge = this._graph.getEdgeById(outEdges_ids[i]);
let neighbor: $N.IBaseNode = edge.getNodes().b;
// if (this.tree(neighbor) != this.tree(node)) {
if (this._state.tree[neighbor.getID()] != this._state.tree[node.getID()]) {
// we found a an edge which is part of the Cut
result.edges.push(edge);
result.edgeIDs.push(edge.getID());
result.cost += edge.getWeight();
}
}
// check inEdges
for (let i = 0; i < inEdges_length; i++) {
// let edge: $E.IBaseEdge = inEdges[Object.keys(inEdges)[i]];
let edge: $E.IBaseEdge = this._graph.getEdgeById(inEdges_ids[i]);
let neighbor: $N.IBaseNode = edge.getNodes().a;
if (this.tree(neighbor) != this.tree(node)) {
// we found a an edge which is part of the Cut
result.edges.push(edge);
result.edgeIDs.push(edge.getID());
result.cost += edge.getWeight();
}
}
}
}
//logger.log(result.edges);
// logger.log("Cost => " +result.cost);
// logger.log("# cycles => " + nrCycles);
// logger.log(result.edges);
return result;
}
renameEdges(graph: $G.IGraph) {
const edges = graph.getDirEdges();
const edges_ids: Array<string> = Object.keys(edges);
const edges_length = edges_ids.length;
for (let i = 0; i < edges_length; i++) {
const edge: $E.IBaseEdge = edges[edges_ids[i]];
const weight: number = edge.getWeight();
graph.deleteEdge(edge);
const node_a: $N.IBaseNode = edge.getNodes().a;
const node_b: $N.IBaseNode = edge.getNodes().b;
const options = {directed: true, weighted: true, weight: weight};
const new_edge = graph.addEdgeByID(node_a.getID() + "_" + node_b.getID(), node_a, node_b, options);
}
}
convertToDirectedGraph(uGraph: $G.IGraph) : $G.IGraph {
const dGraph: $G.IGraph = new $G.BaseGraph(uGraph.label + "_directed");
// copy all nodes
const nodes: { [keys: string]: $N.IBaseNode } = uGraph.getNodes();
const nodes_ids: Array<string> = Object.keys(nodes);
const nodes_length: number = nodes_ids.length;
// logger.log("#nodes: " + Object.keys(nodes).length);
for (let i = 0; i < nodes_length; i++) {
// let node: $N.IBaseNode = nodes[Object.keys(nodes)[i]];
const node: $N.IBaseNode = nodes[nodes_ids[i]];
dGraph.addNodeByID(node.getID());
}
// create one in and one out edge for each undirected edge
const edges: { [keys: string]: $E.IBaseEdge } = uGraph.getUndEdges();
const edges_ids: Array<string> = Object.keys(edges);
const edges_length: number = edges_ids.length;
for (let i = 0; i < edges_length; i++) {
// let und_edge: $E.IBaseEdge = edges[Object.keys(edges)[i]];
const und_edge: $E.IBaseEdge = edges[edges_ids[i]];
const node_a_id: string = und_edge.getNodes().a.getID();
const node_b_id: string = und_edge.getNodes().b.getID();
const options: $E.BaseEdgeConfig = {directed: true, weighted: true, weight: und_edge.getWeight()};
dGraph.addEdgeByID(node_a_id + "_" + node_b_id, dGraph.getNodeById(node_a_id), dGraph.getNodeById(node_b_id), options);
dGraph.addEdgeByID(node_b_id + "_" + node_a_id, dGraph.getNodeById(node_b_id), dGraph.getNodeById(node_a_id), options);
}
// logger.log(dGraph);
return dGraph;
}
tree(node: $N.IBaseNode) {
let tree: string = "";
if (node.getID() in this._state.treeS) {
tree = "S";
return tree;
}
if (node.getID() in this._state.treeT) {
tree = "T";
return tree;
}
return tree;
}
getPathToRoot(node: $N.IBaseNode) {
const path_root: Array<$N.IBaseNode> = [];
let node_id = node.getID();
path_root.push(this._graph.getNodeById(node_id));
const sink_id: string = this._sink.getID();
const source_id: string = this._source.getID();
while ((node_id != sink_id) && (node_id != source_id)) {
if (this._state.parents[node_id] == null) { // this happens when the root of this path is a free node
return path_root;
}
node_id = this._state.parents[node_id].getID();
path_root.push(this._graph.getNodeById(node_id));
}
return path_root;
}
getBottleneckCapacity() {
let min_capacity: number = 0;
// set first edge weight
min_capacity = this._state.residGraph.getEdgeById(this._state.path[0].getID() + "_" + this._state.path[1].getID()).getWeight();
const path_length = this._state.path.length - 1;
for (let i = 0; i < path_length; i++) {
const node_a: $N.IBaseNode = this._state.path[i];
const node_b = this._state.path[i + 1];
// let edge = this._state.residGraph.getEdgeByNodeIDs(node_a.getID(), node_b.getID());
const edge = this._state.residGraph.getEdgeById(node_a.getID() + "_" + node_b.getID());
if (edge.getWeight() < min_capacity) {
min_capacity = edge.getWeight();
}
}
return min_capacity;
}
grow() {
// as long as there are active nodes
let nr_active_nodes: number = Object.keys(this._state.activeNodes).length;
const active_nodes_ids: Array<string> = Object.keys(this._state.activeNodes);
while (nr_active_nodes) {
// take an active node
// let activeNode: $N.IBaseNode = this._state.activeNodes[Object.keys(this._state.activeNodes)[0]];
const activeNode: $N.IBaseNode = this._state.activeNodes[active_nodes_ids[0]];
// let edges: {[k: string] : $E.IBaseEdge} = (this.tree(activeNode) == "S") ? activeNode.outEdges() : activeNode.inEdges();
const edges: { [k: string]: $E.IBaseEdge } = (this._state.tree[activeNode.getID()] == "S") ? activeNode.outEdges() : activeNode.inEdges();
const edges_ids: Array<string> = Object.keys(edges);
const edges_length: number = edges_ids.length;
// for all neighbors
for (let i = 0; i < edges_length; i++) {
// let edge: $E.IBaseEdge = edges[(Object.keys(edges)[i])];
const edge: $E.IBaseEdge = edges[edges_ids[i]];
const neighborNode: $N.IBaseNode = (this._state.tree[activeNode.getID()] == "S") ? edge.getNodes().b : edge.getNodes().a;
if (edge.getWeight() <= 0) {
continue;
}
if (!(this._state.tree[neighborNode.getID()])) {
// add neighbor to corresponding tree
if (this._state.tree[activeNode.getID()] == "S") {
this._state.treeS[neighborNode.getID()] = neighborNode;
this._state.tree[neighborNode.getID()] = "S";
}
else {
this._state.treeT[neighborNode.getID()] = neighborNode;
this._state.tree[neighborNode.getID()] = "T";
}
// set active node as parent to neighbor node
this._state.parents[neighborNode.getID()] = activeNode;
// add neighbor to active node set
this._state.activeNodes[neighborNode.getID()] = neighborNode;
active_nodes_ids.push(neighborNode.getID());
++nr_active_nodes;
}
else if(this._state.tree[neighborNode.getID()] != this._state.tree[activeNode.getID()]) {
// constructing path
let complete_path: Array<$N.IBaseNode>;
let nPath: Array<$N.IBaseNode> = this.getPathToRoot(neighborNode);
let aPath: Array<$N.IBaseNode> = this.getPathToRoot(activeNode);
const root_node_npath: $N.IBaseNode = nPath[nPath.length - 1];
if (this._state.tree[root_node_npath.getID()] == "S") {
nPath = nPath.reverse();
complete_path = nPath.concat(aPath);
}
else {
aPath = aPath.reverse();
complete_path = aPath.concat(nPath);
}
this._state.path = complete_path;
// return; this._state.path;
return;
}
}
delete this._state.activeNodes[activeNode.getID()];
active_nodes_ids.shift();
--nr_active_nodes;
}
this._state.path = [];
return; //empty path
}
augmentation() {
const min_capacity = this.getBottleneckCapacity();
for (let i = 0; i < this._state.path.length - 1; i++) {
const node_a = this._state.path[i], node_b = this._state.path[i + 1];
// let edge = this._state.residGraph.getEdgeByNodeIDs(node_a.getID(), node_b.getID());
let edge = this._state.residGraph.getEdgeById(node_a.getID() + "_" + node_b.getID());
// let reverse_edge = this._state.residGraph.getEdgeByNodeIDs(node_b.getID(), node_a.getID());
const reverse_edge = this._state.residGraph.getEdgeById(node_b.getID() + "_" + node_a.getID());
// update the residual capacity in the graph
this._state.residGraph.getEdgeById(edge.getID()).setWeight(edge.getWeight() - min_capacity);
this._state.residGraph.getEdgeById(reverse_edge.getID()).setWeight(reverse_edge.getWeight() + min_capacity);
// for all saturated edges
edge = this._state.residGraph.getEdgeById(edge.getID());
if (!edge.getWeight()) {
if (this._state.tree[node_a.getID()] == this._state.tree[node_b.getID()]) {
if (this._state.tree[node_b.getID()] == "S") {
delete this._state.parents[node_b.getID()];
this._state.orphans[node_b.getID()] = node_b;
}
if (this._state.tree[node_a.getID()] == "T") {
delete this._state.parents[node_a.getID()];
this._state.orphans[node_a.getID()] = node_a;
}
}
}
}
}
adoption() {
const orphans_ids = Object.keys(this._state.orphans);
let orphans_size = orphans_ids.length;
while (orphans_size) {
// let orphan: $N.IBaseNode = this._state.orphans[Object.keys(this._state.orphans)[0]];
const orphan: $N.IBaseNode = this._state.orphans[orphans_ids[0]];
delete this._state.orphans[orphan.getID()];
orphans_ids.shift();
--orphans_size;
// try to find a new valid parent for the orphan
const edges: { [k: string]: $E.IBaseEdge } = (this._state.tree[orphan.getID()] == "S") ? orphan.inEdges() : orphan.outEdges();
const edge_ids: Array<string> = Object.keys(edges);
const edge_length: number = edge_ids.length;
let found = false;
for (let i = 0; i < edge_length; i++) {
// let edge: $E.IBaseEdge = edges[Object.keys(edges)[i]];
let edge: $E.IBaseEdge = edges[edge_ids[i]];
let neighbor: $N.IBaseNode = (this._state.tree[orphan.getID()] == "S") ? edge.getNodes().a : edge.getNodes().b;
// check for same tree and weight > 0
if ((this._state.tree[orphan.getID()] == this._state.tree[neighbor.getID()]) && edge.getWeight()) {
const neighbor_root_path: Array<$N.IBaseNode> = this.getPathToRoot(neighbor);
const neighbor_root: $N.IBaseNode = neighbor_root_path[neighbor_root_path.length - 1];
// check for root either source or sink
if ((neighbor_root.getID() == this._sink.getID()) || (neighbor_root.getID() == this._source.getID())) {
// we found a valid parent
this._state.parents[orphan.getID()] = neighbor;
found = true;
break;
}
}
}
if (found) {
continue;
}
// let edge_ids: Array<string> = Object.keys(edges);
// let edge_length: number = edge_ids.length;
// we could not find a valid parent
for (let i = 0; i < edge_length; i++) {
// let edge: $E.IBaseEdge = edges[Object.keys(edges)[i]];
let edge: $E.IBaseEdge = edges[edge_ids[i]];
let neighbor: $N.IBaseNode = (this._state.tree[orphan.getID()] == "S") ? edge.getNodes().a : edge.getNodes().b;
if (this._state.tree[orphan.getID()] == this._state.tree[neighbor.getID()]) {
// set neighbor active
if (edge.getWeight()) {
this._state.activeNodes[neighbor.getID()] = neighbor;
}
if (this._state.parents[neighbor.getID()] == null) {
continue;
}
// set neighbor to orphan if his parent is the current orphan
if (this._state.parents[neighbor.getID()].getID() == orphan.getID()) {
this._state.orphans[neighbor.getID()] = neighbor;
orphans_ids.push(neighbor.getID());
++orphans_size;
delete this._state.parents[neighbor.getID()];
}
}
}
// remove from current tree and from activeNodes
const orphan_tree = this._state.tree[orphan.getID()];
if (orphan_tree == "S") {
delete this._state.treeS[orphan.getID()];
delete this._state.tree[orphan.getID()];
}
else if(orphan_tree == "T") {
delete this._state.treeT[orphan.getID()];
delete this._state.tree[orphan.getID()];
}
delete this._state.activeNodes[orphan.getID()];
}
}
prepareMCMFStandardConfig() : MCMFConfig {
return {
directed: true
}
}
}
export {
MCMFBoykov
};
import { IBaseNode } from '../core/base/BaseNode';
export interface GraphPartitioning {
partitions : Map<number, Partition>
nodePartMap : Map<string, number>;
cut_cost : number;
}
export interface Partition {
nodes : Map<string, IBaseNode>;
}
import { IBaseNode } from '../core/base/BaseNode';
import { IGraph } from '../core/base/BaseGraph';
import * as $SU from '../utils/StructUtils';
import { GraphPartitioning, Partition } from './Interfaces';
export class KCut {
private _partitioning : GraphPartitioning;
constructor(private _graph : IGraph) {
this._partitioning = {
partitions: new Map<number, Partition>(),
nodePartMap: new Map<string, number>(),
cut_cost: 0
};
}
cut(k: number, shuffle: boolean = false) : GraphPartitioning {
const nodes = this._graph.getNodes(),
keys = Object.keys(nodes),
n = keys.length,
nr_parts = k;
let nr_rest = n%k;
let node_ids = Object.keys(this._graph.getNodes());
shuffle && $SU.shuffleArray( node_ids );
let node_idx = 0;
let nodePartMap = new Map<string, number>();
// In maths, partition numbers start with "1"
for ( let i = 1; i <= nr_parts; i++ ) {
let part_size = Math.floor(n/k);
let partition : Partition = {
nodes: new Map<string, IBaseNode>()
}
// Adding nodes, either in order or shuffled
while ( part_size-- ) {
let node = this._graph.getNodeById(node_ids[node_idx++]);
partition.nodes.set(node.getID(), node);
nodePartMap.set(node.getID(), i);
}
// Distributing 'rest' nodes to earliest 'rest' partitions
if ( nr_rest ) {
let node = this._graph.getNodeById(node_ids[node_idx++]);
partition.nodes.set(node.getID(), node);
nodePartMap.set(node.getID(), i);
nr_rest--;
}
this._partitioning.partitions.set(i, partition);
}
this._partitioning.nodePartMap = nodePartMap;
return this._partitioning;
}
}
import { IGraph } from '../core/base/BaseGraph';
import { IBaseNode } from '../core/base/BaseNode';
import { GraphPartitioning, Partition } from './Interfaces';
import { KCut } from './KCut';
import { BinaryHeap, BinaryHeapMode } from '../datastructs/BinaryHeap';
import { Logger, LogColors } from '../utils/Logger';
import {ComputeGraph, IComputeGraph} from "../core/compute/ComputeGraph";
const logger = new Logger();
const DEFAULT_WEIGHT = 1;
export type GainEntry = {
id: string,
source: IBaseNode,
target: IBaseNode,
gain: number
};
export interface KL_Costs {
internal: {[key:string]: number};
external: {[key:string]: number};
}
export interface KL_Config {
initShuffle? : boolean;
directed? : boolean;
weighted? : boolean;
}
export interface KL_Open_Sets {
partition_a : Map<string, boolean>;
partition_b : Map<string, boolean>;
}
/**
* We require node features to have partition entries 1 & 2, EXACTLY!
*
* @todo make it less brittle? Is this brittle at all? Or a sound assumption?
*/
export class KLPartitioning {
public _partitionings : Map<number, GraphPartitioning>;
public _costs : KL_Costs;
public _gainsHeap : BinaryHeap;
public _bestPartitioning : number;
public _currentPartitioning : number;
public _open_sets : KL_Open_Sets;
public _adjList : {};
// for faster iteration, as long as we're not using Maps
private _keys : Array<string>;
private _config : KL_Config;
private _gainsHash : Map<string, GainEntry>; // {[key: string]: GainEntry};
private _cg : IComputeGraph;
constructor(private _graph : IGraph, config? : KL_Config) {
this._config = config || {
initShuffle: false,
directed: false,
weighted: false
};
this._bestPartitioning = 1;
this._currentPartitioning = 1;
this._partitionings = new Map<number, GraphPartitioning>();
this._gainsHash = new Map<string, GainEntry>();
this._costs = {
internal: {},
external: {},
};
this._open_sets = {
partition_a : new Map<string, boolean>(),
partition_b : new Map<string, boolean>()
};
this._cg = new ComputeGraph(this._graph);
this._adjList = this._cg.adjListW();
this._keys = Object.keys(this._graph.getNodes());
this.initPartitioning(this._config.initShuffle);
let nr_parts = this._partitionings.get(this._currentPartitioning).partitions.size;
if ( nr_parts !== 2 ) {
throw new Error(`KL partitioning works on 2 initial partitions only, got ${nr_parts}.`);
}
this.initCosts();
this.initGainsHeap();
}
private initPartitioning(initShuffle) {
// logger.log(`Init Shuffle: ${initShuffle}`);
if ( initShuffle ) {
this._partitionings.set(this._currentPartitioning, new KCut(this._graph).cut(2, true));
let part_it = this._partitionings.get(this._currentPartitioning).partitions.values();
// Redundant?
part_it.next().value.nodes.forEach( node => {
this._open_sets.partition_a.set(node.getID(), true);
});
part_it.next().value.nodes.forEach( node => {
this._open_sets.partition_b.set(node.getID(), true);
});
} else {
let partitioning = {
partitions: new Map<number, Partition>(),
nodePartMap: new Map<string, number>(),
cut_cost: 0
};
this._partitionings.set(this._currentPartitioning, partitioning);
for (let key of this._keys) {
let node = this._graph.getNodeById(key);
// assume we have a node feature 'partition'
let node_part = node.getFeature('partition');
if ( node_part == null ) {
throw new Error('no node feature "partition" encountered - you need to set initShuffle to true');
} else {
partitioning.nodePartMap.set(key, node_part);
if ( !partitioning.partitions.get(node_part) ) {
partitioning.partitions.set(node_part, {
nodes: new Map<string, IBaseNode>()
});
}
partitioning.partitions.get(node_part).nodes.set(key, node);
}
// fill open sets
if (node_part === 1) {
this._open_sets.partition_a.set(key, true);
}
else {
this._open_sets.partition_b.set(key, true);
}
}
}
}
private initCosts() {
let partitioning = this._partitionings.get(this._currentPartitioning),
nodePartMap = partitioning.nodePartMap;
for (let source of Object.keys(this._graph.getNodes())) {
// logger.write(source + ' : ');
// Initialize internal & external cost arrays
this._costs.external[source] = 0;
this._costs.internal[source] = 0;
Object.keys(this._adjList[source]).forEach( target => {
logger.write(`[${nodePartMap.get(source)}, ${nodePartMap.get(target)}]`);
/**
* @todo just use node.allNeighbors() instead of adjList ??
* @todo decide after implementing node & edge types
*/
let edge_weight = this._config.weighted ? this._adjList[source][target] : DEFAULT_WEIGHT;
if ( nodePartMap.get(source) === nodePartMap.get(target) ) {
logger.write('\u2713' + ' ', LogColors.FgGreen, true);
this._costs.internal[source] += edge_weight;
} else {
logger.write('\u2717' + ' ', LogColors.FgRed, true);
this._costs.external[source] += edge_weight;
partitioning.cut_cost += edge_weight;
}
});
logger.log('');
}
// we counted every edge twice in the nested loop above...
partitioning.cut_cost /= 2;
}
initGainsHeap() {
let partitioning = this._partitionings.get(this._currentPartitioning),
partition_iterator = partitioning.partitions.values(),
first_partition = partition_iterator.next().value,
second_partition = partition_iterator.next().value;
let evalID = (obj: GainEntry) => obj.id,
evalPriority = (obj: GainEntry) => obj.gain;
this._gainsHeap = new BinaryHeap( BinaryHeapMode.MAX, evalPriority, evalID );
/**
* We only calculate for node pairs in different partitions
*/
first_partition.nodes.forEach( source => {
let source_id = source.getID();
// logger.write(source_id + ': ');
second_partition.nodes.forEach( target => {
let target_id = target.getID();
// logger.write(target_id + ', ');
let edge_weight = 0;
let adj_weight = parseFloat(this._adjList[source_id][target_id]);
if ( !isNaN(adj_weight) ) {
edge_weight = this._config.weighted ? adj_weight : DEFAULT_WEIGHT;
}
let pair_gain = this._costs.external[source_id] - this._costs.internal[source_id] + this._costs.external[target_id] - this._costs.internal[target_id] - 2*edge_weight;
// logger.log(`Pair gain for (${source_id}, ${target_id}): ${pair_gain}`);
let gain_entry : GainEntry = {
id: `${source_id}_${target_id}`,
source: source,
target: target,
gain: pair_gain
}
this._gainsHeap.insert(gain_entry);
this._gainsHash.set(gain_entry.id, gain_entry);
});
// logger.log('');
});
}
performIteration() {
let ge = this.doSwapAndDropLockedConnections();
this.updateCosts( ge );
// make a new partitioning for the next cycle / iteration
this._currentPartitioning++;
}
updateCosts(swap_ge: GainEntry) : void {
this._gainsHash.forEach( (k, v) => {
logger.log(k.id);
});
let partitioning = this._partitionings.get(this._currentPartitioning);
partitioning.cut_cost -= swap_ge.gain;
let partition_iterator = partitioning.partitions.keys(),
first_partition = partition_iterator.next().value,
second_partition = partition_iterator.next().value;
[swap_ge.source, swap_ge.target].forEach( source => {
let influencer = source.getID();
source.allNeighbors().forEach( ne => {
let source_id = ne.node.getID();
logger.log(`Cost update for node ${source_id}`);
/**
* We need to update all gains that involve nodes hitherto
* connected to the swapped nodes, which means all entries
* on the heap array those nodes are part of!
*
* @comment We cannot use the adjList however, since we need
* to update ALL possible future swaps, not only their connections...
*
* @todo Find a way to look up those pairs efficiently
*/
// how to build source_target string (always part1_part2)...
let gain_id;
if ( partitioning.nodePartMap.get(influencer) === first_partition ) {
gain_id = `${influencer}_${source_id}`;
}
else {
gain_id = `${source_id}_${influencer}`;
}
// logger.log(`Pair gain for (${gain_id}): ${gain_entry.gain}`);
// this._gainsHeap.insert( gain_entry );
});
});
}
doSwapAndDropLockedConnections() : GainEntry{
let gain_entry : GainEntry = this._gainsHeap.pop(),
source_id = gain_entry.id.split('_')[0],
target_id = gain_entry.id.split('_')[1];
// remove gain_entry from hash map
this._gainsHash.delete(gain_entry.id);
let partitioning = this._partitionings.get(this._currentPartitioning),
partition_iterator = partitioning.partitions.values(),
first_partition = partition_iterator.next().value.nodes,
second_partition = partition_iterator.next().value.nodes;
// Swap partitions
logger.log(`Swapping node pair (${source_id}, ${target_id})`);
first_partition.delete(source_id);
first_partition.set(target_id, gain_entry.target);
second_partition.delete(target_id);
second_partition.set(source_id, gain_entry.source);
/**
* Go over all possible gains involving the
* swapped nodes & remove from heap
*
* Non-existing (duplicate) gain entries don't matter,
* since the heap will simply find nothing / return undefined
*
* @comment: Gain_Entry id's are always structured in the form
* `${1st_partition_node}_${2nd_partition_node}` , so =>
* @comment Connections from source_id can only go to second partition
* @comment Connections to target_id can only come from first partition
* @comment Always runs in O(n) with initial n...
*/
second_partition.forEach( target => {
let target_id = target.getID();
// logger.log(`${source_id}_${target_id}`);
this.removeGainsEntry(`${source_id}_${target_id}`);
});
first_partition.forEach( source => {
let source_id = source.getID();
// logger.log(`${source_id}_${target_id}`);
this.removeGainsEntry(`${source_id}_${target_id}`);
});
return gain_entry;
}
private removeGainsEntry(heap_id: string) : void {
if ( this._gainsHash.has(heap_id) ) {
this._gainsHeap.remove(this._gainsHash.get(heap_id));
this._gainsHash.delete(heap_id);
}
}
}
import * as $N from '../core/base/BaseNode';
import * as $E from '../core/base/BaseEdge';
import * as $G from '../core/base/BaseGraph';
import * as uuid from 'uuid';
const v4 = uuid.v4;
/**
* EITHER generate new edges via specified degree span
* OR via probability of edge creation from a specified
* set of nodes to all others
*/
export interface NodeDegreeConfiguration {
und_degree?: number;
dir_degree?: number;
min_und_degree?: number;
max_und_degree?: number;
min_dir_degree?: number;
max_dir_degree?: number;
probability_dir?: number;
probability_und?: number;
}
export interface ISimplePerturber {
// CREATE EDGES PER NODE
createEdgesProb(probability: number, directed?: boolean, setOfNodes?: { [key: string] : $N.IBaseNode} ) : void;
createEdgesSpan(min: number, max: number, directed?: boolean, setOfNodes?: { [key: string] : $N.IBaseNode} ) : void;
// ADD NODES
addNodesPercentage(percentage: number, config?: NodeDegreeConfiguration ) : void;
addNodesAmount(amount: number, config?: NodeDegreeConfiguration ) : void;
// ADD EDGES
addUndEdgesPercentage(percentage: number ) : void;
addDirEdgesPercentage(percentage: number ) : void;
addEdgesAmount(amount: number, config?: $E.BaseEdgeConfig ) : void;
// DELETE NODES AND EDGES
deleteNodesPercentage(percentage: number ) : void;
deleteUndEdgesPercentage(percentage: number ) : void;
deleteDirEdgesPercentage(percentage: number ) : void;
deleteNodesAmount(amount: number ) : void;
deleteUndEdgesAmount(amount: number ) : void;
deleteDirEdgesAmount(amount: number ) : void;
}
class SimplePerturber implements ISimplePerturber {
constructor(private _graph: $G.IGraph) {}
/**
*
* @param percentage
*/
deleteNodesPercentage(percentage: number ) : void {
if ( percentage < 0 ) {
throw new Error('Cowardly refusing to remove a negative amount of nodes');
}
if ( percentage > 100 ) {
percentage = 100;
}
let nr_nodes_to_delete = Math.ceil(this._graph.nrNodes() * percentage/100);
this.deleteNodesAmount( nr_nodes_to_delete );
}
/**
*
* @param percentage
*/
deleteUndEdgesPercentage(percentage: number ) : void {
if ( percentage > 100 ) {
percentage = 100;
}
let nr_edges_to_delete = Math.ceil(this._graph.nrUndEdges() * percentage/100);
this.deleteUndEdgesAmount( nr_edges_to_delete );
}
/**
*
* @param percentage
*/
deleteDirEdgesPercentage(percentage: number ) : void {
if ( percentage > 100 ) {
percentage = 100;
}
let nr_edges_to_delete = Math.ceil(this._graph.nrDirEdges() * percentage/100);
this.deleteDirEdgesAmount( nr_edges_to_delete );
}
/**
*
*/
deleteNodesAmount(amount: number ) : void {
if ( amount < 0 ) {
throw 'Cowardly refusing to remove a negative amount of nodes';
}
if ( this._graph.nrNodes() === 0 ) {
return;
}
for ( let nodeID = 0, randomNodes = this._graph.pickRandomProperties(this._graph.getNodes(), amount); nodeID < randomNodes.length; nodeID++ ) {
this._graph.deleteNode( this._graph.getNodes()[randomNodes[nodeID]] );
}
}
/**
*
*/
deleteUndEdgesAmount(amount: number ) : void {
if ( amount < 0 ) {
throw 'Cowardly refusing to remove a negative amount of edges';
}
if ( this._graph.nrUndEdges() === 0 ) {
return;
}
for ( let edgeID = 0, randomEdges = this._graph.pickRandomProperties(this._graph.getUndEdges(), amount); edgeID < randomEdges.length; edgeID++ ) {
this._graph.deleteEdge( this._graph.getUndEdges()[randomEdges[edgeID]] );
}
}
/**
*
*/
deleteDirEdgesAmount(amount: number ) : void {
if ( amount < 0 ) {
throw 'Cowardly refusing to remove a negative amount of edges';
}
if ( this._graph.nrDirEdges() === 0 ) {
return;
}
for ( let edgeID = 0, randomEdges = this._graph.pickRandomProperties(this._graph.getDirEdges(), amount); edgeID < randomEdges.length; edgeID++ ) {
this._graph.deleteEdge( this._graph.getDirEdges()[randomEdges[edgeID]] );
}
}
/**
*
*/
addUndEdgesPercentage(percentage: number ) : void {
let nr_und_edges_to_add = Math.ceil(this._graph.nrUndEdges() * percentage/100);
this.addEdgesAmount( nr_und_edges_to_add, {directed: false} );
}
/**
*
*/
addDirEdgesPercentage(percentage: number ) : void {
let nr_dir_edges_to_add = Math.ceil(this._graph.nrDirEdges() * percentage/100);
this.addEdgesAmount( nr_dir_edges_to_add, {directed: true} );
}
/**
*
* DEFAULT edge direction: UNDIRECTED
*/
addEdgesAmount(amount: number, config?: $E.BaseEdgeConfig ) : void {
if ( amount <= 0 ) {
throw new Error('Cowardly refusing to add a non-positive amount of edges')
}
let node_a : $N.IBaseNode,
node_b : $N.IBaseNode,
nodes : {[key: string] : $N.IBaseNode};
let direction = ( config && config.directed ) ? config.directed : false,
dir = direction ? "_d" : "_u";
// logger.log("DIRECTION of new edges to create: " + direction ? "directed" : "undirected");
while ( amount > 0 ) {
node_a = this._graph.getRandomNode();
while ( ( node_b = this._graph.getRandomNode() ) === node_a ) {}
let edge_id = `${node_a.getID()}_${node_b.getID()}${dir}`;
if ( node_a.hasEdgeID( edge_id ) ) {
// TODO: Check if the whole duplication prevention is really necessary!
// logger.log("Duplicate edge creation, continuing...");
continue;
}
else {
/**
* Enable random weights for edges ??
*/
this._graph.addEdgeByID(edge_id, node_a, node_b, {directed: direction});
--amount;
}
}
// logger.log(`Created ${amount} ${direction ? "directed" : "undirected"} edges...`);
}
/**
*
*/
addNodesPercentage(percentage: number, config?: NodeDegreeConfiguration ) : void {
if ( percentage < 0 ) {
throw 'Cowardly refusing to add a negative amount of nodes';
}
let nr_nodes_to_add = Math.ceil(this._graph.nrNodes() * percentage/100);
this.addNodesAmount( nr_nodes_to_add, config );
}
/**
* If the degree configuration is invalid
* (negative or infinite degree amount / percentage)
* the nodes will have been created nevertheless
*
* @todo is this `perturbation` since it is not `random` ?
*/
addNodesAmount(amount: number, config?: NodeDegreeConfiguration ) : void {
if ( amount < 0 ) {
throw 'Cowardly refusing to add a negative amount of nodes';
}
let new_nodes : { [key: string] : $N.IBaseNode } = {};
while ( --amount >= 0 ) {
let new_node_id = v4();
new_nodes[new_node_id] = this._graph.addNodeByID( new_node_id );
}
if ( config == null ) {
return;
}
else {
this.createEdgesByConfig( config, new_nodes );
}
}
/**
* Go through the degree_configuration provided and create edges
* as requested by config
*/
private createEdgesByConfig( config: NodeDegreeConfiguration, new_nodes: {[key: string] : $N.IBaseNode} ) {
let degree,
min_degree,
max_degree,
deg_probability;
if ( config.und_degree != null ||
config.dir_degree != null ||
config.min_und_degree != null && config.max_und_degree != null ||
config.min_dir_degree != null && config.max_dir_degree != null )
{
// Ignore min / max undirected degree if specific amount is given
if ( ( degree = config.und_degree ) != null ) {
this.createEdgesSpan(degree, degree, false, new_nodes);
}
else if ( ( min_degree = config.min_und_degree) != null
&& ( max_degree = config.max_und_degree ) != null ) {
this.createEdgesSpan(min_degree, max_degree, false, new_nodes);
}
// Ignore min / max directed degree if specific amount is given
if ( degree = config.dir_degree ) {
this.createEdgesSpan(degree, degree, true, new_nodes);
}
else if ( ( min_degree = config.min_dir_degree) != null
&& ( max_degree = config.max_dir_degree ) != null ) {
this.createEdgesSpan(min_degree, max_degree, true, new_nodes);
}
}
else {
if ( config.probability_dir != null ) {
this.createEdgesProb( config.probability_dir, true, new_nodes );
}
if ( config.probability_und != null ) {
this.createEdgesProb( config.probability_und, false, new_nodes );
}
}
}
/**
* Simple edge generator:
* Go through all node combinations, and
* add an (un)directed edge with
* @param probability and
* @param directed true or false
* @param new_nodes set of nodes that were added
* CAUTION: this algorithm takes quadratic runtime in #nodes
*/
createEdgesProb(probability: number, directed?: boolean,
new_nodes?: { [key: string] : $N.IBaseNode} ) : void {
if (0 > probability || 1 < probability) {
throw new Error("Probability out of range.");
}
directed = directed || false;
new_nodes = new_nodes || this._graph.getNodes();
let
all_nodes = this._graph.getNodes(),
node_a,
node_b,
edge_id,
dir = directed ? '_d' : '_u';
for (node_a in new_nodes) {
for (node_b in all_nodes) {
if (node_a !== node_b && Math.random() <= probability) {
edge_id = all_nodes[node_a].getID() + "_" + all_nodes[node_b].getID() + dir;
this._graph.addEdgeByID(edge_id, all_nodes[node_a], all_nodes[node_b], {directed: directed});
}
}
}
}
/**
* Simple edge generator:
* Go through all nodes, and
* add [min, max] (un)directed edges to
* a randomly chosen node
* CAUTION: this algorithm could take quadratic runtime in #nodes
* but should be much faster
*/
createEdgesSpan(min: number, max: number, directed?: boolean,
setOfNodes?: { [key: string] : $N.IBaseNode} ) : void {
if (min < 0) {
throw new Error('Minimum degree cannot be negative.');
}
if (max >= this._graph.nrNodes()) {
throw new Error('Maximum degree exceeds number of reachable nodes.');
}
if (min > max) {
throw new Error('Minimum degree cannot exceed maximum degree.');
}
directed = directed || false;
// Do we need to set them integers before the calculations?
var min = min | 0,
max = max | 0,
new_nodes = setOfNodes || this._graph.getNodes(),
all_nodes = this._graph.getNodes(),
idx_a,
node_a,
node_b,
edge_id,
// we want edges to all possible nodes
// TODO: enhance with types / filters later on
node_keys = Object.keys(all_nodes),
keys_len = node_keys.length,
rand_idx,
rand_deg,
dir = directed ? '_d' : '_u';
for (idx_a in new_nodes) {
node_a = new_nodes[idx_a];
rand_idx = 0;
rand_deg = (Math.random()*(max-min)+min)|0;
while (rand_deg) {
rand_idx = (keys_len*Math.random())|0; // should never reach keys_len...
node_b = all_nodes[node_keys[rand_idx]];
if (node_a !== node_b) {
edge_id = node_a.getID() + "_" + node_b.getID() + dir;
// Check if edge already exists
if (node_a.hasEdgeID(edge_id)) {
continue;
}
this._graph.addEdgeByID(edge_id, node_a, node_b, {directed: directed});
--rand_deg;
}
}
}
}
}
export {
SimplePerturber
}
/**
* @todo 2020-12-12: What is this thing doing !?
*/
import {TypedEdge, ITypedEdge} from '../core/typed/TypedEdge';
import {TypedNode, ITypedNode} from '../core/typed/TypedNode';
import {setSimFuncs} from '../similarities/SetSimilarities';
import {TypedGraph} from '../core/typed/TypedGraph';
import * as $I from '../similarities/interfaces';
import {knnNodeArray} from '../similarities/SimilarityCommons';
interface SubSetConfig extends $I.SortCutFuncs {
rtype: string; // name of edge TYPE to use
knn?: number;
cutoff?: number;
}
class TheAugments {
constructor(private _g: TypedGraph) { }
/**
* @todo implement
*/
addSubsetRelationship(algo: Function, sets: $I.SetOfSets, cfg: SubSetConfig) : Set<ITypedEdge> {
const edgeSet = new Set<ITypedEdge>();
let edge: ITypedEdge;
const g = this._g;
const sims = knnNodeArray(algo, sets, {knn: cfg.knn || 1, cutoff: cfg.cutoff || 0});
sims.forEach(e => {
if ( sets[e.from].size <= sets[e.to].size ) {
edge = g.addEdgeByID('ontheedge', g.n(e.from), g.n(e.to), {directed: true, type: cfg.rtype});
}
else {
edge = g.addEdgeByID('ontheedge', g.n(e.to), g.n(e.from), {directed: true, type: cfg.rtype});
}
edgeSet.add(edge);
});
return edgeSet;
}
}
export {
TheAugments
}
import {DIR} from '../core/interfaces';
/*----------------------------------*/
/* INTERFACES, TYPES & ENUMS */
/*----------------------------------*/
export type SetOfSets = {[key: string]: Set<any>};
export interface Similarity {
isect?: number; // intersection (# of items)
sim : number; // similarity
}
export interface SimilarityEntry extends Similarity {
from : string;
to : string;
}
export type SimilarityResult = SimilarityEntry[];
export interface TopKEntry extends Similarity {
from: string;
to: string;
}
export type TopKArray = TopKEntry[];
export type TopKDict = {[key:string]: TopKEntry[]};
export interface SortCutFuncs {
sort?: (e1: SimilarityEntry, e2: SimilarityEntry) => number
cutFunc?: (sim: number, thres: number) => boolean
}
export interface SimilarityConfig extends SortCutFuncs {
cutoff?: number;
knn?: number;
dup?: boolean;
}
/**
* @param t1 type of node set 1
* @param t2 type of node set 2
* @param d1 traversal direction for t1
* @param d2 traversal direction for t2
* @param e1 edge type to follow for t1
* @param e2 edge type to follow for t2
* @param co cutoff below which entry will be omitted
*/
export interface SimPerSharedPrefConfig extends SortCutFuncs {
t1: string;
t2: string;
d1: DIR;
d2: DIR;
e1: string;
e2: string;
co?: number;
}
import * as $I from './interfaces';
import {IBaseNode} from '../core/base/BaseNode';
const PRECISION = 5;
export const scoreSimFuncs = {
cosine,
cosineSets,
euclidean,
euclideanSets,
pearson,
pearsonSets
};
/*----------------------------------*/
/* SET SIMILARITY MEASURES */
/*----------------------------------*/
function euclidean(a: number[], b: number[]) {
if (a.length !== b.length) {
throw new Error('Vectors must be of same size');
}
const at = a.length < 1e4 ? a : new Float32Array(a);
const bt = b.length < 1e4 ? b : new Float32Array(b);
let sum = 0, diff = 0;
for (let i = 0; i < at.length; i++) {
diff = at[i] - bt[i];
sum += diff * diff;
}
let sim = +Math.sqrt(sum).toPrecision(PRECISION);
// console.log(sim);
return {sim};
}
/**
*
* @param a
* @param b
*/
function cosine(a: number[], b: number[]) {
if (a.length !== b.length) {
throw new Error('Vectors must be of same size');
}
const fa1 = new Float32Array(a);
const fa2 = new Float32Array(b);
let numerator = 0;
for (let i = 0; i < fa1.length; i++) {
numerator += fa1[i] * fa2[i];
}
let dena = 0, denb = 0;
for (let i = 0; i < fa1.length; i++) {
dena += fa1[i] * fa1[i];
denb += fa2[i] * fa2[i];
}
dena = Math.sqrt(dena);
denb = Math.sqrt(denb);
return {sim: +(numerator / (dena * denb)).toPrecision(PRECISION)};
}
/**
*
* @param a scores of user A for common targets
* @param b scores of user B for common targets
* @param a_mean avg rating for user a across ALL their ratings
* @param b_mean avg rating for user b across ALL their ratings
*/
function pearson(a: number[], b: number[], a_mean?: number, b_mean?: number) {
if (a.length !== b.length) {
throw new Error('Vectors must be of same size');
}
let sum_a = 0,
sum_b = 0,
mean_a = a_mean || 0,
mean_b = b_mean || 0,
numerator = 0,
diff_a_sq = 0,
diff_b_sq = 0,
denominator,
a_diff,
b_diff,
sim;
if (!a_mean || !b_mean) {
for (let i = 0; i < a.length; i++) {
sum_a += a[i];
sum_b += b[i];
}
mean_a = sum_a / a.length;
mean_b = sum_b / b.length;
}
for (let i = 0; i < a.length; i++) {
a_diff = a[i] - mean_a;
b_diff = b[i] - mean_b;
numerator += a_diff * b_diff;
diff_a_sq += a_diff * a_diff;
diff_b_sq += b_diff * b_diff;
}
denominator = Math.sqrt(diff_a_sq) * Math.sqrt(diff_b_sq);
sim = +(numerator / denominator).toPrecision(PRECISION);
return {sim};
}
/**
* @description first extract
* @param a
* @param b
*/
function cosineSets(a: Set<string>, b: Set<string>) {
const [aa, ba] = extractCommonTargetScores(a, b);
if (!aa.length || !ba.length) {
return {sim: 0};
}
return cosine(aa, ba);
}
function euclideanSets(a: Set<string>, b: Set<string>) {
const [aa, ba] = extractCommonTargetScores(a, b);
if (!aa.length || !ba.length) {
return {sim: 0};
}
return euclidean(aa, ba);
}
/**
*
* @param a
* @param b
*/
function pearsonSets(a: Set<string>, b: Set<string>) {
const [aa, ba, a_mean, b_mean] = extractCommonTargetScores(a, b);
// console.log(aa, ba);
if (!aa.length || !ba.length) {
return {sim: 0};
}
return pearson(aa, ba, a_mean, b_mean);
}
/**
* @description this method implicitly ensures that sets given to cosine
* are always of the same length
* @param a
* @param b
*/
function extractCommonTargetScores(a: Set<string>, b: Set<string>): [number[], number[], number, number] {
// we need to extract the target IDs first
let a_id = new Set(), b_id = new Set();
for (let e of a) a_id.add(e.split('#')[0]);
for (let e of b) b_id.add(e.split('#')[0]);
// now we collect the scores for common targets (in the same order)
let score, a_map = new Map(), b_map = new Map(), a_vec = [], b_vec = [], earr, a_mean = 0, b_mean = 0;
for (let e of a) {
earr = e.split('#'); // we can assume 0 is the target...
score = +earr[earr.length - 1];
a_mean += score;
if (b_id.has(earr[0])) {
a_map.set(earr[0], score);
}
}
for (let e of b) {
const earr = e.split('#');
score = +earr[earr.length - 1];
b_mean += score;
if (a_id.has(earr[0])) {
b_map.set(earr[0], score);
}
}
// Maps preserve the order in which items were entered
// console.log(a_map, b_map);
let a_keys = Array.from(a_map.keys()).sort();
for ( let key of a_keys ) {
a_vec.push(a_map.get(key));
}
let b_keys = Array.from(b_map.keys()).sort();
for ( let key of b_keys ) {
b_vec.push(b_map.get(key));
}
return [a_vec, b_vec, a_mean / a.size, b_mean / b.size];
}
import * as $I from './interfaces';
/*----------------------------------*/
/* CONSTS */
/*----------------------------------*/
export const setSimFuncs = {
jaccard,
overlap
};
const PRECISION = 5;
/*----------------------------------*/
/* SET SIMILARITY MEASURES */
/*----------------------------------*/
/**
* @param a set A
* @param b set B
*/
function jaccard(a: Set<any>, b: Set<any>) : $I.Similarity {
const ui = unionIntersect(a, b);
return {
isect: ui.isectSize,
sim: +(ui.isectSize / ui.unionSize).toPrecision(PRECISION)
}
}
/**
* @description commonly used to detect sub/super relationships
* @param a
* @param b
*/
function overlap(a: Set<any>, b: Set<any>) : $I.Similarity {
const ui = unionIntersect(a, b);
return {
isect: ui.isectSize,
sim: +(ui.isectSize / Math.min(a.size, b.size)).toPrecision(PRECISION)
}
}
function unionIntersect(a: Set<any>, b: Set<any>) {
const unionSize = new Set([...a, ...b]).size;
const isectSize = a.size + b.size - unionSize;
return {unionSize, isectSize};
}
import * as $I from './interfaces';
import {TypedGraph} from '../core/typed/TypedGraph';
import { ITypedNode } from '../core/typed/TypedNode';
export const sortFuncs = {
asc: (se1: $I.SimilarityEntry, se2: $I.SimilarityEntry) => se1.sim - se2.sim,
desc: (se1: $I.SimilarityEntry, se2: $I.SimilarityEntry) => se2.sim - se1.sim
};
export const cutFuncs = {
above: (sim: number, threshold: number) => sim >= threshold,
below: (sim: number, threshold: number) => sim <= threshold
};
/*----------------------------------*/
/* SIMILARITY FUNCTIONS */
/*----------------------------------*/
export function sim(algo: Function, a: Set<any>, b: Set<any>) {
return algo(a, b);
}
/**
* @description similarity between set & particular node
* sorted by similarity DESC
*
* @param algo similarity function to use
* @param s source set
* @param t target sets to measure similarity to
* @param cfg object
*/
export function simSource(algo: Function, s: string, t: $I.SetOfSets, cfg: $I.SimilarityConfig = {}) : $I.SimilarityResult {
const sort = cfg.sort || sortFuncs.desc;
const cutFunc = cfg.cutFunc || cutFuncs.above;
let result: $I.SimilarityResult = [];
const start = t[s];
for ( let [k,v] of Object.entries(t)) {
if ( k === s ) {
continue;
}
const sim: $I.Similarity = algo(start, v);
if ( cfg.cutoff == null || cutFunc(sim.sim, cfg.cutoff ) ) {
result.push({from: s, to: k, ...sim});
}
}
result.sort(sort);
if ( cfg.knn != null && cfg.knn <= result.length ) {
result = result.slice(0, cfg.knn);
}
return result;
}
/**
* @description pairwise is a *symmetrical* algorithm, so we only need to
* compute similarities in one direction
*
* @param algo similarity function to use
* @param s all sets
* @param cfg object
*/
export function simPairwise(algo: Function, s: $I.SetOfSets, cfg: $I.SimilarityConfig = {}) : $I.SimilarityResult {
const sort = cfg.sort || sortFuncs.desc;
const cutFunc = cfg.cutFunc || cutFuncs.above;
let result: $I.SimilarityResult = [];
const keys = Object.keys(s);
for ( let i in keys ) {
for ( let j = 0; j < +i; j++) {
const from = keys[i];
const to = keys[j];
if ( from === to ) {
continue;
}
const sim = algo(s[keys[i]], s[keys[j]], i, j);
if ( cfg.cutoff == null || cutFunc(sim.sim, cfg.cutoff ) ) {
result.push({from, to, ...sim});
}
}
}
result.sort(sort);
if ( cfg.knn != null && cfg.knn <= result.length ) {
result = result.slice(0, cfg.knn);
}
return result;
}
/**
* @description similarity of individuals of one subset to another
* @description kNN relates to each s1-node's subset
*
* @param algo
* @param s1
* @param s2
* @param cfg
*
* @returns an array of Similarity entries
*/
export function simSubsets(algo: Function, s1: $I.SetOfSets, s2: $I.SetOfSets, cfg: $I.SimilarityConfig = {}) : $I.SimilarityResult {
const sort = cfg.sort || sortFuncs.desc;
const cutFunc = cfg.cutFunc || cutFuncs.above;
let result: $I.SimilarityResult = [];
const keys1 = Object.keys(s1);
const keys2 = Object.keys(s2);
for ( let i in keys1 ) {
let subRes = [];
for ( let j in keys2 ) {
const from = keys1[i];
const to = keys2[j];
if ( from === to ) {
continue;
}
const sim = algo(s1[keys1[i]], s2[keys2[j]]);
if ( cfg.cutoff == null || cutFunc(sim.sim, cfg.cutoff) ) {
subRes.push({from, to, ...sim});
}
}
subRes.sort(sort);
if ( cfg.knn != null && cfg.knn <= subRes.length ) {
subRes = subRes.slice(0, cfg.knn);
}
result = result.concat(subRes);
}
return result.sort(sort);
}
// /**
// * @description similarity of two groups to one another
// * just collects sets & calls sim()
// *
// * @param algo
// * @param s1
// * @param s2
// * @param config
// *
// * @returns an array of Similarity entries
// */
// export function simGroups(algo: Function, s1: $I.SetOfSets, s2: $I.SetOfSets, config: $I.SimilarityConfig = {}) : $I.Similarity {
// throw new Error('not implemented yet');
// return {isect: 0, sim: 0};
// }
/**
* @description top-K per node
*
* @param algo similarity function to use
* @param s all sets
* @param cfg
*
* @returns most similar neighbor per node
*
* @todo there are no duplicates in this array, similarities might differ in different directions -> adapt!
*/
export function knnNodeArray(algo: Function, s: $I.SetOfSets, cfg: $I.SimilarityConfig) : $I.TopKArray {
const sort = cfg.sort || sortFuncs.desc;
const c = cfg.cutoff || 0;
const topK: $I.TopKArray = [];
const dupes = {};
for ( let node of Object.keys(s) ) {
const topKEntries: $I.SimilarityEntry[] = simSource(algo, node, s, {knn: cfg.knn || 1, sort: cfg.sort});
topKEntries.forEach(e => {
// console.log(e);
if ( c == null || e.sim < c ) {
return;
}
if (!cfg.dup && ( dupes[e.from] && dupes[e.from][e.to] || dupes[e.to] && dupes[e.to][e.from] ) ) {
return;
}
topK.push(e);
dupes[e.from] = dupes[e.from] || {};
dupes[e.from][e.to] = true;
});
}
return topK.sort(sort);
}
/**
*
* @param algo
* @param s
* @param cfg
*/
export function knnNodeDict(algo: Function, s: $I.SetOfSets, cfg: $I.SimilarityConfig) {
const sort = cfg.sort || sortFuncs.desc;
const c = cfg.cutoff || 0;
const topK: $I.TopKDict = {};
for ( let node of Object.keys(s) ) {
const topKEntries: $I.SimilarityEntry[] = simSource(algo, node, s, {knn: cfg.knn || 1, sort: cfg.sort});
topKEntries.forEach(e => {
if ( c == null || e.sim < c) {
return;
}
delete e.from;
topK[node] = topK[node] || [];
topK[node].push(e);
});
for ( let arr of Object.values(topK) ) {
arr.sort(sort);
}
}
return topK;
}
/**
* @description Returns similarities of 2 node sets depending on shared preferences
* @description default cutoff similarity is 1e-6
*
* @param g graph
* @param algo similarity function to use
* @param cfg config object of type SimPerSharedPrefConfig
*
* @returns something
*
* @todo type return value
* @todo get rid of graph somehow (transfer method to other class...!)
*/
export function viaSharedPrefs(g: TypedGraph, algo: Function, cfg: $I.SimPerSharedPrefConfig ) {
const sort = cfg.sort || sortFuncs.desc;
const cutoff = cfg.co == null ? 1e-6 : cfg.co;
const cutFunc = cfg.cutFunc || cutFuncs.above;
const sims = [];
const t1Set = g.getNodesT(cfg.t1);
const t2Set = g.getNodesT(cfg.t2);
const prefCache = new Map<string, Set<ITypedNode>>();
for ( let [t1Name, t1Node] of t1Set.entries() ) {
for ( let [t2Name, t2Node] of t2Set.entries() ) {
let
prefSet1: Set<ITypedNode>,
prefSet2: Set<ITypedNode>;
if ( prefCache.get(t1Node.id) ) {
prefSet1 = prefCache.get(t1Node.id);
}
else {
prefSet1 = g[cfg.d1](t1Node, cfg.e1.toUpperCase());
prefCache.set(t1Node.id, prefSet1);
}
if ( prefCache.get(t2Node.id) ) {
prefSet2 = prefCache.get(t2Node.id);
}
else {
prefSet2 = g[cfg.d2](t2Node, cfg.e2.toUpperCase());
prefCache.set(t2Node.id, prefSet2);
}
if ( !prefSet1 || !prefSet2 || prefSet1.size === 0 || prefSet2.size === 0 ) {
continue;
}
const sim = algo(prefSet1, prefSet2);
if ( cutFunc(sim.sim, cutoff) ) {
sims.push({from: t1Name, to: t2Name, ...sim});
}
}
}
return sims.sort(sort);
}
/**
* @description returns Set of elements in B that are not in A
* @param a
* @param b
*/
export function getBsNotInA(a: Set<ITypedNode>, b: Set<ITypedNode>) : Set<ITypedNode> {
let result = new Set<ITypedNode>();
let sa = new Set(), sb = new Set();
for ( let e of a ) sa.add(e.label);
// for ( let e of b ) sb.add(e.label);
for ( let e of b ) {
if ( !sa.has(e.label) ) {
result.add(e);
}
}
return result;
}
/**
* @description works, but we would have to completely re-vamp $G typed traversals
* in order to speed the code up by a factor of ~2...
* @todo Fuck speed for the moment -> concern yourself with optimization ->
* !!! AFTER THE FUCKING DEMO !!!
* @todo I think this doesn't pay off in any way...
*/
// function simUint32(a: Uint32Array, b: Uint32Array) : Similarity {
// a = a.sort();
// b = b.sort();
// const union = [];
// let
// i = 0,
// j = 0;
// while ( i < a.length || j < b.length ) {
// if ( i >= a.length ) {
// union.push(b[j++]);
// }
// else if ( j >= b.length ) {
// union.push(a[i++]);
// }
// else {
// union.push(a[i]);
// if (a[i++] !== b[j]) {
// union.push(b[j++]);
// }
// else {
// j++;
// }
// }
// }
// const intersectSize = a.length + b.length - union.length;
// return {isect: intersectSize, sim: intersectSize / union.length};
// }
import * as $G from '../core/base/BaseGraph';
import * as $E from '../core/base/BaseEdge';
import * as $N from '../core/base/BaseNode';
import { DEFAULT_WEIGHT } from "./PFS";
export interface BFArrrayResult {
distances: Array<number>;
neg_cycle: boolean;
}
export interface BFDictResult {
distances: {};
neg_cycle: boolean;
}
/**
*
* @param graph
* @param start
*/
function BFSanityChecks(graph: $G.IGraph, start: $N.IBaseNode) {
if (graph == null || start == null) {
throw new Error('Graph as well as start node have to be valid objects.');
}
if (graph.nrDirEdges() === 0 && graph.nrUndEdges() === 0) {
throw new Error('Cowardly refusing to traverse a graph without edges.');
}
if (!graph.hasNodeID(start.getID())) {
throw new Error('Cannot start from an outside node.');
}
}
function BellmanFordArray(graph: $G.IGraph, start: $N.IBaseNode): BFArrrayResult {
BFSanityChecks(graph, start);
let distances: Array<number> = [],
nodes = graph.getNodes(),
edge: $E.IBaseEdge,
node_keys = Object.keys(nodes),
node: $N.IBaseNode,
id_idx_map: {} = {},
bf_edge_entry,
new_weight: number,
neg_cycle: boolean = false;
for (let n_idx = 0; n_idx < node_keys.length; ++n_idx) {
node = nodes[node_keys[n_idx]];
distances[n_idx] = (node === start) ? 0 : Number.POSITIVE_INFINITY;
id_idx_map[node.getID()] = n_idx;
}
// Initialize an edge array just holding the node indices, weight and directed
let graph_edges = graph.getDirEdgesArray().concat(graph.getUndEdgesArray());
let bf_edges = [];
for (let e_idx = 0; e_idx < graph_edges.length; ++e_idx) {
edge = graph_edges[e_idx];
let bf_edge_entry =
bf_edges.push([
id_idx_map[edge.getNodes().a.getID()],
id_idx_map[edge.getNodes().b.getID()],
isFinite(edge.getWeight()) ? edge.getWeight() : DEFAULT_WEIGHT,
edge.isDirected()
]);
}
for (let i = 0; i < node_keys.length - 1; ++i) {
for (let e_idx = 0; e_idx < bf_edges.length; ++e_idx) {
edge = bf_edges[e_idx];
updateDist(edge[0], edge[1], edge[2]);
!edge[3] && updateDist(edge[1], edge[0], edge[2]);
}
}
for (let e_idx = 0; e_idx < bf_edges.length; ++e_idx) {
edge = bf_edges[e_idx];
if (betterDist(edge[0], edge[1], edge[2]) || (!edge[3] && betterDist(edge[1], edge[0], edge[2]))) {
neg_cycle = true;
break;
}
}
function updateDist(u, v, weight) {
new_weight = distances[u] + weight;
if (distances[v] > new_weight) {
distances[v] = new_weight;
}
}
function betterDist(u, v, weight) {
return (distances[v] > distances[u] + weight);
}
return { distances, neg_cycle };
}
/**
*
* @param graph
* @param start
*/
function BellmanFordDict(graph: $G.IGraph, start: $N.IBaseNode): BFDictResult {
BFSanityChecks(graph, start);
let distances = {},
edges: Array<$E.IBaseEdge>,
edge: $E.IBaseEdge,
a: string,
b: string,
weight: number,
new_weight: number,
nodes_size: number,
neg_cycle: boolean = false;
distances = {}; // Reset dists, TODO refactor
edges = graph.getDirEdgesArray().concat(graph.getUndEdgesArray());
nodes_size = graph.nrNodes();
for (let node in graph.getNodes()) {
distances[node] = Number.POSITIVE_INFINITY;
}
distances[start.getID()] = 0;
for (let i = 0; i < nodes_size - 1; ++i) {
for (let e_idx = 0; e_idx < edges.length; ++e_idx) {
edge = edges[e_idx];
a = edge.getNodes().a.getID();
b = edge.getNodes().b.getID();
weight = isFinite(edge.getWeight()) ? edge.getWeight() : DEFAULT_WEIGHT;
updateDist(a, b, weight);
!edge.isDirected() && updateDist(b, a, weight);
}
}
for (let edgeID in edges) {
edge = edges[edgeID];
a = edge.getNodes().a.getID();
b = edge.getNodes().b.getID();
weight = isFinite(edge.getWeight()) ? edge.getWeight() : DEFAULT_WEIGHT;
if (betterDist(a, b, weight) || (!edge.isDirected() && betterDist(b, a, weight))) {
neg_cycle = true;
}
}
function updateDist(u, v, weight) {
new_weight = distances[u] + weight;
if (distances[v] > new_weight) {
distances[v] = new_weight;
}
}
function betterDist(u, v, weight) {
return (distances[v] > distances[u] + weight);
}
return {distances, neg_cycle};
}
export {
BellmanFordDict,
BellmanFordArray
};
import {GraphMode, GraphStats, MinAdjacencyListDict} from '../core/interfaces';
import * as $N from '../core/base/BaseNode';
import * as $E from '../core/base/BaseEdge';
import * as $G from '../core/base/BaseGraph';
import * as $CB from '../utils/CallbackUtils';
export interface BFS_Config {
result : {[id: string]: BFS_ResultEntry};
callbacks : BFS_Callbacks;
dir_mode : GraphMode;
messages? : {};
filters? : any;
}
export interface BFS_ResultEntry {
distance : number;
parent : $N.IBaseNode;
counter : number; // order of discovery
}
export interface BFS_Callbacks {
init_bfs? : Array<Function>;
node_unmarked? : Array<Function>;
node_marked? : Array<Function>;
sort_nodes? : Function;
}
export interface BFS_Scope {
// marked : {[id: string] : boolean};
nodes : {[id: string] : $N.IBaseNode};
queue : Array<$N.IBaseNode>;
current : $N.IBaseNode;
next_node : $N.IBaseNode;
next_edge : $E.IBaseEdge;
root_node : $N.IBaseNode;
adj_nodes : Array<$N.NeighborEntry>;
}
/**
* Breadth first search - usually performed to see
* reachability etc. Therefore we do not want 'segments'
* or 'components' of our graph, but simply one well
* defined result segment covering the whole graph.
*
* @param graph the graph to perform BFS on
* @param v the vertex to use as a start vertex
* @param config an optional config object, will be
* automatically instantiated if not passed by caller
* @returns {{}}
* @constructor
*/
function BFS(graph : $G.IGraph,
v : $N.IBaseNode,
config? : BFS_Config) : {[id: string] : BFS_ResultEntry} {
config = config || prepareBFSStandardConfig();
let callbacks = config.callbacks;
let dir_mode = config.dir_mode;
/**
* We are not traversing an empty graph...
*/
if ( graph.getMode() === GraphMode.INIT ) {
throw new Error('Cowardly refusing to traverse graph without edges.');
}
/**
* We are not traversing a graph taking NO edges into account
*/
if ( dir_mode === GraphMode.INIT ) {
throw new Error('Cannot traverse a graph with dir_mode set to INIT.');
}
// scope to pass to callbacks at different stages of execution
let bfsScope : BFS_Scope = {
// marked: {},
nodes: graph.getNodes(),
queue: [],
current: null,
next_node: null,
next_edge: null,
root_node: v,
adj_nodes: []
};
/**
* HOOK 1: BFS INIT
*/
if ( callbacks.init_bfs ) {
$CB.execCallbacks(callbacks.init_bfs, bfsScope);
}
bfsScope.queue.push(v);
let i = 0;
while ( i < bfsScope.queue.length ) {
bfsScope.current = bfsScope.queue[i++];
/**
* Do we move only in the directed subgraph,
* undirected subgraph or complete (mixed) graph?
*/
if ( dir_mode === GraphMode.MIXED ) {
bfsScope.adj_nodes = bfsScope.current.reachNodes();
}
else if ( dir_mode === GraphMode.UNDIRECTED ) {
bfsScope.adj_nodes = bfsScope.current.connNodes();
}
else if ( dir_mode === GraphMode.DIRECTED ) {
bfsScope.adj_nodes = bfsScope.current.nextNodes();
}
else {
bfsScope.adj_nodes = [];
}
/**
* HOOK 2 - Sort adjacent nodes
*/
if ( typeof callbacks.sort_nodes === 'function' ) {
callbacks.sort_nodes(bfsScope);
}
for ( let adj_idx in bfsScope.adj_nodes ) {
bfsScope.next_node = bfsScope.adj_nodes[adj_idx].node;
bfsScope.next_edge = bfsScope.adj_nodes[adj_idx].edge;
/**
* HOOK 3 - Node unmarked
*/
if ( config.result[bfsScope.next_node.getID()].distance === Number.POSITIVE_INFINITY ) {
if ( callbacks.node_unmarked ) {
$CB.execCallbacks(callbacks.node_unmarked, bfsScope);
}
}
else {
/**
* HOOK 4 - Node marked
*/
if ( callbacks.node_marked ) {
$CB.execCallbacks(callbacks.node_marked, bfsScope);
}
}
}
}
return config.result;
}
function prepareBFSStandardConfig() {
let config : BFS_Config = {
result: {},
callbacks: {
init_bfs: [],
node_unmarked: [],
node_marked: [],
sort_nodes: undefined
},
dir_mode: GraphMode.MIXED,
messages: {},
filters: {}
},
result = config.result,
callbacks = config.callbacks;
let count = 0;
let counter = function() {
return count++;
};
/**
* Standard INIT callback
*/
let initBFS = function( context : BFS_Scope ) {
for ( let key in context.nodes ) {
config.result[key] = {
distance : Number.POSITIVE_INFINITY,
parent : null,
counter : -1
};
}
// initialize root node entry
config.result[context.root_node.getID()] = {
distance : 0,
parent : context.root_node,
counter : counter()
};
};
callbacks.init_bfs.push( initBFS );
// Standard Node unmarked callback
// have to populate respective result entry
let nodeUnmarked = function( context: BFS_Scope ) {
config.result[context.next_node.getID()] = {
distance : result[context.current.getID()].distance + 1,
parent : context.current,
counter : counter()
};
context.queue.push(context.next_node);
};
callbacks.node_unmarked.push( nodeUnmarked );
return config;
}
export { BFS, prepareBFSStandardConfig };
import {GraphMode, GraphStats, MinAdjacencyListDict} from '../core/interfaces';
import * as $N from '../core/base/BaseNode';
import * as $G from '../core/base/BaseGraph';
import * as $CB from '../utils/CallbackUtils';
export interface DFS_Config {
visit_result: {};
callbacks: DFS_Callbacks;
dir_mode: GraphMode;
dfs_visit_marked: {[id: string] : boolean};
messages?: {};
filters?: any;
}
export interface DFS_Callbacks {
init_dfs? : Array<Function>;
init_dfs_visit? : Array<Function>;
node_popped? : Array<Function>;
node_marked? : Array<Function>;
node_unmarked? : Array<Function>;
adj_nodes_pushed? : Array<Function>;
sort_nodes? : Function;
}
export interface StackEntry {
node : $N.IBaseNode;
parent : $N.IBaseNode;
weight? : number;
}
export interface DFSVisit_Scope {
stack : Array<StackEntry>;
adj_nodes : Array<$N.NeighborEntry>;
stack_entry : StackEntry;
current : $N.IBaseNode;
current_root : $N.IBaseNode;
}
export interface DFS_Scope {
marked : {[id: string] : boolean};
nodes : {[id: string] : $N.IBaseNode};
}
/**
* DFS Visit - one run to see what nodes are reachable
* from a given "current" root node
*
* @param graph
* @param current_root
* @param config
* @returns {{}}
* @constructor
*/
function DFSVisit(graph : $G.IGraph,
current_root : $N.IBaseNode,
config? : DFS_Config) {
// scope to pass to callbacks at different stages of execution
let dfsVisitScope : DFSVisit_Scope = {
stack : [],
adj_nodes : [],
stack_entry : null,
current : null,
current_root : current_root
};
config = config || prepareDFSVisitStandardConfig();
let callbacks = config.callbacks,
dir_mode = config.dir_mode;
/**
* We are not traversing an empty graph...
*/
if ( graph.getMode() === GraphMode.INIT ) {
throw new Error('Cowardly refusing to traverse graph without edges.');
}
/**
* We are not traversing a graph taking NO edges into account
*/
if ( dir_mode === GraphMode.INIT ) {
throw new Error('Cannot traverse a graph with dir_mode set to INIT.');
}
/**
* HOOK 1 - INIT (INNER DFS VISIT):
* Initializing a possible result object,
* possibly with the current_root;
*/
if ( callbacks.init_dfs_visit ) {
$CB.execCallbacks(callbacks.init_dfs_visit, dfsVisitScope);
}
// Start by pushing current root to the stack
dfsVisitScope.stack.push({
node : current_root,
parent : current_root,
weight : 0 // initial weight cost from current_root
});
while ( dfsVisitScope.stack.length ) {
dfsVisitScope.stack_entry = dfsVisitScope.stack.pop();
dfsVisitScope.current = dfsVisitScope.stack_entry.node;
/**
* HOOK 2 - AQUIRED CURRENT NODE / POPPED NODE
*/
if ( callbacks.node_popped ) {
$CB.execCallbacks(callbacks.node_popped, dfsVisitScope);
}
if ( !config.dfs_visit_marked[dfsVisitScope.current.getID()] ) {
config.dfs_visit_marked[dfsVisitScope.current.getID()] = true;
/**
* HOOK 3 - CURRENT NODE UNMARKED
*/
if ( callbacks.node_unmarked ) {
$CB.execCallbacks(callbacks.node_unmarked, dfsVisitScope);
}
/**
* Do we move only in the directed subgraph,
* undirected subgraph or complete (mixed) graph?
*/
if ( dir_mode === GraphMode.MIXED ) {
dfsVisitScope.adj_nodes = dfsVisitScope.current.reachNodes();
}
else if ( dir_mode === GraphMode.UNDIRECTED ) {
dfsVisitScope.adj_nodes = dfsVisitScope.current.connNodes();
}
else if ( dir_mode === GraphMode.DIRECTED ) {
dfsVisitScope.adj_nodes = dfsVisitScope.current.nextNodes();
}
/**
* HOOK 4 - SORT ADJACENT NODES
*/
if ( typeof callbacks.sort_nodes === 'function' ) {
callbacks.sort_nodes(dfsVisitScope);
}
for ( let adj_idx in dfsVisitScope.adj_nodes ) {
/**
* HOOK 5 - NODE OR EDGE TYPE CHECK...
* LATER !!
*/
if ( callbacks ) {
}
dfsVisitScope.stack.push({
node: dfsVisitScope.adj_nodes[adj_idx].node,
parent: dfsVisitScope.current,
weight: dfsVisitScope.adj_nodes[adj_idx].edge.getWeight()
});
}
/**
* HOOK 6 - ADJACENT NODES PUSHED - LEAVING CURRENT NODE
*/
if ( callbacks.adj_nodes_pushed ) {
$CB.execCallbacks(callbacks.adj_nodes_pushed, dfsVisitScope);
}
}
else {
/**
* HOOK 7 - CURRENT NODE ALREADY MARKED
*/
if ( callbacks.node_marked ) {
$CB.execCallbacks(callbacks.node_marked, dfsVisitScope);
}
}
}
return config.visit_result;
}
/**
* Depth first search - used for reachability / exploration
* of graph structure and as a basis for topological sorting
* and component / community analysis.
* Because DFS can be used as a basis for many other algorithms,
* we want to keep the result as generic as possible to be
* populated by the caller rather than the core DFS algorithm.
*
* @param graph
* @param root
* @param config
* @returns {{}[]}
* @constructor
*/
function DFS( graph : $G.IGraph,
root : $N.IBaseNode,
config? : DFS_Config) {
config = config || prepareDFSStandardConfig();
let callbacks = config.callbacks,
dir_mode = config.dir_mode;
if ( graph.getMode() === GraphMode.INIT ) {
throw new Error('Cowardly refusing to traverse graph without edges.');
}
if ( dir_mode === GraphMode.INIT ) {
throw new Error('Cannot traverse a graph with dir_mode set to INIT.');
}
let dfsScope : DFS_Scope = {
marked : {},
nodes : graph.getNodes()
};
/**
* HOOK 1 - INIT (OUTER DFS)
*/
if ( callbacks.init_dfs ) {
$CB.execCallbacks(callbacks.init_dfs, dfsScope);
}
callbacks.adj_nodes_pushed = callbacks.adj_nodes_pushed || [];
let markNode = function ( context : DFSVisit_Scope ) {
dfsScope.marked[context.current.getID()] = true;
};
callbacks.adj_nodes_pushed.push(markNode);
// We need to put our results into segments
// for easy counting of 'components'
// TODO refactor for count & counter...
let dfs_result = [{}];
let dfs_idx = 0;
let count = 0;
let counter = function() {
return count++;
};
/**
* We not only add new nodes to the result object
* of DFSVisit, but also to it's appropriate
* segment of the dfs_result object
*/
let addToProperSegment = function( context: DFSVisit_Scope ) {
dfs_result[dfs_idx][context.current.getID()] = {
parent : context.stack_entry.parent,
counter : counter()
};
};
// check if a callbacks object has been instantiated
if ( callbacks && callbacks.node_unmarked ) {
callbacks.node_unmarked.push(addToProperSegment);
}
// Start with root node, no matter what
DFSVisit(graph, root, config);
// Now take the rest in 'normal' order
for( let node_key in dfsScope.nodes ) {
if ( !dfsScope.marked[node_key] ) {
// Next segment in dfs_results
dfs_idx++;
dfs_result.push({});
// Explore and fill next subsegment
DFSVisit(graph, dfsScope.nodes[node_key], config);
}
}
// console.dir(config.visit_result);
return dfs_result;
}
/**
* This is the only place in which a config object
* is instantiated (except manually, of course)
*
* Therefore, we do not take any arguments
*/
function prepareDFSVisitStandardConfig() {
let config : DFS_Config = {
visit_result: {},
callbacks: {},
messages: {},
dfs_visit_marked: {},
dir_mode: GraphMode.MIXED
},
result = config.visit_result,
callbacks = config.callbacks;
// internal letiable for order of visit
// during DFS Visit
let count = 0;
let counter = function() {
return count++;
};
callbacks.init_dfs_visit = callbacks.init_dfs_visit || [];
let initDFSVisit = function( context : DFSVisit_Scope ) {
result[context.current_root.getID()] = {
parent : context.current_root
};
};
callbacks.init_dfs_visit.push(initDFSVisit);
callbacks.node_unmarked = callbacks.node_unmarked || [];
let setResultEntry = function( context : DFSVisit_Scope ) {
result[context.current.getID()] = {
parent : context.stack_entry.parent,
counter : counter()
};
};
callbacks.node_unmarked.push(setResultEntry);
return config;
}
/**
* First instantiates config file for DFSVisit, then
* enhances it with outer DFS init callback
*/
function prepareDFSStandardConfig() {
// First prepare DFS Visit callbacks
let config = prepareDFSVisitStandardConfig(),
callbacks = config.callbacks;
// result = config.visit_result;
// Now add outer DFS INIT callback
callbacks.init_dfs = callbacks.init_dfs || [];
let setInitialResultEntries = function( context : DFS_Scope ) {
// for ( let node_id in context.nodes ) {
// result[node_id] = {
// parent: null,
// counter: -1
// }
// }
};
callbacks.init_dfs.push(setInitialResultEntries);
return config;
}
export { DFSVisit,
DFS,
prepareDFSVisitStandardConfig,
prepareDFSStandardConfig
};
import * as $N from '../core/base/BaseNode';
import * as $G from '../core/base/BaseGraph';
import * as $PFS from '../traversal/PFS';
/**
* @todo Consider target node callbacks / messages
* @param graph
* @param source
* @param target
*/
function Dijkstra( graph : $G.IGraph,
source : $N.IBaseNode,
target? : $N.IBaseNode ) : {[id: string] : $PFS.PFS_ResultEntry}
{
let config = $PFS.preparePFSStandardConfig();
if ( target ) {
config.goal_node = target;
}
return $PFS.PFS( graph, source, config );
}
export {
Dijkstra
};
import {MinAdjacencyListArray, NextArray} from '../core/interfaces';
import * as $SU from '../utils/StructUtils'
import {IGraph} from "../core/base/BaseGraph";
import {ComputeGraph} from "../core/compute/ComputeGraph";
const DEFAULT_WEIGHT = 1;
/**
* @todo FW directed mode...
*/
/**
* Floyd-Warshall - we mostly use it to get the Betweenness
* of a graph. We use the standard algorithm and save all
* the shortest paths we find.
*
* @param graph the graph to perform Floyd-Warshall on
* @returns m*m matrix of values, m*m*m matrix of neighbors
* @constructor
*/
function FloydWarshallAPSP(graph: IGraph): {} {
if (graph.nrDirEdges() === 0 && graph.nrUndEdges() === 0) {
throw new Error("Cowardly refusing to traverse graph without edges.");
}
const cg = new ComputeGraph(graph);
let dists: MinAdjacencyListArray = cg.adjMatrixW();
let next: NextArray = cg.nextArray();
let N = dists.length;
for (let k = 0; k < N; ++k) {
for (let i = 0; i < N; ++i) {
for (let j = 0; j < N; ++j) {
if (k != i && k != j && i != j && dists[i][j] == (dists[i][k] + dists[k][j]) ) {
//if a node is unreachable, the corresponding value in next should not be updated, but stay null
if (dists[i][j] !== Number.POSITIVE_INFINITY) {
next[i][j] = $SU.mergeOrderedArraysNoDups(next[i][j], next[i][k]);
}
}
if (k != i && k != j && i != j && dists[i][j] > dists[i][k] + dists[k][j]) {
next[i][j] = next[i][k].slice(0);
dists[i][j] = dists[i][k] + dists[k][j];
}
}
}
}
return [dists, next];
}
/**
* Floyd-Warshall - we mostly use it for Closeness centrality.
* This is the array version, which means the returned matrix
* is not accessible with node IDs but rather with their indices.
* It also is faster than the dict version.
*
* @param graph the graph to perform Floyd-Warshall on
* @returns m*m matrix of values
* @constructor
*/
function FloydWarshallArray(graph: IGraph): MinAdjacencyListArray {
if (graph.nrDirEdges() === 0 && graph.nrUndEdges() === 0) {
throw new Error("Cowardly refusing to traverse graph without edges.");
}
const cg = new ComputeGraph(graph);
let dists = cg.adjMatrixW();
let N = dists.length;
for (let k = 0; k < N; ++k) {
for (let i = 0; i < N; ++i) {
for (let j = 0; j < N; ++j) {
if (k != i && k != j && i != j && dists[i][j] > dists[i][k] + dists[k][j]) {
dists[i][j] = dists[i][k] + dists[k][j];
}
}
}
}
return dists;
}
function changeNextToDirectParents(input: NextArray): NextArray {
let output: Array<Array<Array<number>>> = [];
for (let a = 0; a < input.length; a++) {
output.push([]);
for (let b = 0; b < input.length; b++) {
output[a].push([]);
output[a][b] = input[a][b];
}
}
for (let a = 0; a < input.length; a++) {
for (let b = 0; b < input.length; b++) {
if ( input[a][b][0] != null
&& a != b && !(input[a][b].length === 1
&& input[a][b][0] === b))
{
output[a][b] = [];
findDirectParents(a, b, input, output);
}
}
}
return output;
}
function findDirectParents(u, v, inNext, outNext): void {
let nodesInTracking = [u];
let counter = 0;
while (nodesInTracking.length > 0) {
let currNode = nodesInTracking.pop();
if (currNode == u && counter > 0) {
continue;
}
else {
for (let e = 0; e < inNext[currNode][v].length; e++) {
if (inNext[currNode][v][e] == v && counter == 0) {
outNext[u][v] = $SU.mergeOrderedArraysNoDups(outNext[u][v], [v]);
}
else if (inNext[currNode][v][e] == v) {
outNext[u][v] = $SU.mergeOrderedArraysNoDups(outNext[u][v], [currNode]);
}
else {
nodesInTracking = $SU.mergeOrderedArraysNoDups(nodesInTracking, [inNext[currNode][v][e]]);
}
}
}
counter++;
}
}
export {
FloydWarshallAPSP,
FloydWarshallArray,
changeNextToDirectParents
};
import {NextArray} from '../core/interfaces';
import * as $N from '../core/base/BaseNode';
import * as $G from '../core/base/BaseGraph';
import * as $PFS from '../traversal/PFS';
import * as $BF from '../traversal/BellmanFord';
import * as $SU from '../utils/StructUtils'
import {ComputeGraph} from "../core/compute/ComputeGraph";
function Johnsons(graph: $G.IGraph): {} {
if (graph.nrDirEdges() === 0 && graph.nrUndEdges() === 0) {
throw new Error("Cowardly refusing to traverse graph without edges.");
}
if (graph.hasNegativeEdge()) {
let extraNode: $N.IBaseNode = new $N.BaseNode("extraNode");
graph = addExtraNandE(graph, extraNode);
let BFresult = $BF.BellmanFordDict(graph, extraNode);
//reminder: output of the BellmanFordDict is BFDictResult
//contains a dictionary called distances, format: {[nodeID]:dist}, and a boolean called neg_cycle
if (BFresult.neg_cycle) {
throw new Error("The graph contains a negative cycle, thus it can not be processed");
}
else {
let newWeights: {} = BFresult.distances;
graph = reWeighGraph(graph, newWeights, extraNode);
//graph still has the extraNode
//reminder: deleteNode function removes its edges, too
graph.deleteNode(extraNode);
return PFSFromAllNodes(graph);
}
}
return PFSFromAllNodes(graph);
}
/**
*
* @param target
* @param nodeToAdd
*
* @todo check if
*/
function addExtraNandE(target: $G.IGraph, nodeToAdd: $N.IBaseNode): $G.IGraph {
let allNodes: { [key: string]: $N.IBaseNode } = target.getNodes();
target.addNode(nodeToAdd);
let tempCounter = 0;
//now add a directed edge from the extranode to all graph nodes, excluding itself
for (let nodeKey in allNodes) {
if (allNodes[nodeKey].getID() != nodeToAdd.getID()) {
target.addEdgeByNodeIDs("temp" + tempCounter, nodeToAdd.getID(), allNodes[nodeKey].getID(),
{ directed: true, weighted: true, weight: 0 });
tempCounter++;
}
}
return target;
}
function reWeighGraph(target: $G.IGraph, distDict: {}, tempNode: $N.IBaseNode): $G.IGraph {
//reminder: w(e)'=w(e)+dist(a)-dist(b), a and b the start and end nodes of the edge
let edges = target.getDirEdgesArray().concat(target.getUndEdgesArray());
for (let edge of edges) {
let a = edge.getNodes().a.getID();
let b = edge.getNodes().b.getID();
/**
* no need to re-weigh the temporary edges starting from the extraNode, they will be deleted anyway
* assuming that the node keys in the distDict correspond to the nodeIDs
*/
if (a !== tempNode.getID() && edge.isWeighted) {
let oldWeight = edge.getWeight();
let newWeight = oldWeight + distDict[a] - distDict[b];
edge.setWeight(newWeight);
}
else {
let newWeight = $PFS.DEFAULT_WEIGHT + distDict[a] - distDict[b];
//collecting edgeID and directedness for later re-use
let edgeID: string = edge.getID();
let dirNess: boolean = edge.isDirected();
// one does not simply change an edge to being weighted
target.deleteEdge(edge);
target.addEdgeByNodeIDs(edgeID, a, b, { directed: dirNess, weighted: true, weight: newWeight });
}
}
return target;
}
function PFSFromAllNodes(graph: $G.IGraph): {} {
const cg = new ComputeGraph(graph);
let dists: Array<Array<number>> = cg.adjMatrixW();
let next: NextArray = cg.nextArray();
let nodesDict = graph.getNodes();
let nodeIDIdxMap = {};
let i = 0;
for (let key in nodesDict) {
nodeIDIdxMap[nodesDict[key].getID()] = i++;
}
let specialConfig: $PFS.PFS_Config = $PFS.preparePFSStandardConfig();
/**
* @todo should we just assume that edges at this point are all weighted?
*/
let notEncounteredJohnsons = function (context: $PFS.PFS_Scope) {
context.next.best = context.current.best + context.next.edge.getWeight();
// context.current.best + (isNaN(context.next.edge.getWeight()) ? $PFS.DEFAULT_WEIGHT : context.next.edge.getWeight());
let i = nodeIDIdxMap[context.root_node.getID()],
j = nodeIDIdxMap[context.next.node.getID()];
if (context.current.node == context.root_node) {
dists[i][j] = context.next.best;
next[i][j][0] = j;
}
else {
dists[i][j] = context.next.best;
next[i][j][0] = nodeIDIdxMap[context.current.node.getID()];
}
};
specialConfig.callbacks.not_encountered.splice(0, 1, notEncounteredJohnsons);
let betterPathJohnsons = function (context: $PFS.PFS_Scope) {
let i = nodeIDIdxMap[context.root_node.getID()],
j = nodeIDIdxMap[context.next.node.getID()];
dists[i][j] = context.proposed_dist;
if (context.current.node !== context.root_node) {
next[i][j].splice(0, next[i][j].length, nodeIDIdxMap[context.current.node.getID()]);
}
};
specialConfig.callbacks.better_path.splice(0, 1, betterPathJohnsons);
let equalPathJohnsons = function (context: $PFS.PFS_Scope) {
let
i = nodeIDIdxMap[context.root_node.getID()],
j = nodeIDIdxMap[context.next.node.getID()];
if (context.current.node !== context.root_node) {
next[i][j] = $SU.mergeOrderedArraysNoDups(next[i][j], [nodeIDIdxMap[context.current.node.getID()]]);
}
};
specialConfig.callbacks.equal_path.push(equalPathJohnsons);
for (let key in nodesDict) {
$PFS.PFS(graph, nodesDict[key], specialConfig);
}
return [dists, next];
}
export {
Johnsons,
addExtraNandE,
reWeighGraph,
PFSFromAllNodes
};
import {GraphMode, GraphStats, MinAdjacencyListDict} from '../core/interfaces';
import * as $N from '../core/base/BaseNode';
import * as $E from '../core/base/BaseEdge';
import * as $G from '../core/base/BaseGraph';
import * as $CB from '../utils/CallbackUtils';
import * as $BH from '../datastructs/BinaryHeap';
export const DEFAULT_WEIGHT: number = 1;
export interface PFS_Config {
result: { [id: string]: PFS_ResultEntry };
callbacks: PFS_Callbacks;
dir_mode: GraphMode;
goal_node: $N.IBaseNode;
messages?: PFS_Messages;
filters?: any;
evalPriority: any;
evalObjID: any;
}
export interface PFS_ResultEntry {
distance: number; // evaluated by a
parent: $N.IBaseNode;
counter: number; // order of discovery
}
export interface PFS_Callbacks {
init_pfs?: Array<Function>;
new_current?: Array<Function>;
not_encountered?: Array<Function>;
node_open?: Array<Function>;
node_closed?: Array<Function>;
better_path?: Array<Function>;
equal_path?: Array<Function>;
goal_reached?: Array<Function>;
}
export interface PFS_Messages {
init_pfs_msgs?: Array<string>;
new_current_msgs?: Array<string>;
not_enc_msgs?: Array<string>;
node_open_msgs?: Array<string>;
node_closed_msgs?: Array<string>;
better_path_msgs?: Array<string>;
equal_path_msgs?: Array<string>;
goal_reached_msgs?: Array<string>;
}
export interface PFS_Scope {
// OPEN is the heap we use for getting the best choice
OPEN_HEAP: $BH.BinaryHeap;
OPEN: { [id: string]: $N.NeighborEntry };
CLOSED: { [id: string]: $N.NeighborEntry };
nodes: { [id: string]: $N.IBaseNode };
root_node: $N.IBaseNode;
current: $N.NeighborEntry;
adj_nodes: Array<$N.NeighborEntry>;
next: $N.NeighborEntry;
proposed_dist: number;
}
/**
* Priority first search
*
* Like BFS, we are not necessarily visiting the
* whole graph, but only what's reachable from
* a given start node.
*
* @param graph the graph to perform PFS only
* @param v the node from which to start PFS
* @param config a config object similar to that used
* in BFS, automatically instantiated if not given..
*/
function PFS(graph: $G.IGraph,
v: $N.IBaseNode,
config?: PFS_Config): { [id: string]: PFS_ResultEntry } {
config = config || preparePFSStandardConfig();
let callbacks = config.callbacks,
dir_mode = config.dir_mode,
evalPriority = config.evalPriority,
evalObjID = config.evalObjID;
/**
* We are not traversing an empty graph...
*/
if (graph.getMode() === GraphMode.INIT) {
throw new Error('Cowardly refusing to traverse graph without edges.');
}
/**
* We are not traversing a graph taking NO edges into account
*/
if (dir_mode === GraphMode.INIT) {
throw new Error('Cannot traverse a graph with dir_mode set to INIT.');
}
// Root NeighborEntries
let start_ne: $N.NeighborEntry = {
node: v,
edge: new $E.BaseEdge('virtual start edge', v, v, { weighted: true, weight: 0 }),
best: 0
};
let scope: PFS_Scope = {
OPEN_HEAP: new $BH.BinaryHeap($BH.BinaryHeapMode.MIN, evalPriority, evalObjID),
OPEN: {},
CLOSED: {},
nodes: graph.getNodes(),
root_node: v,
current: start_ne,
adj_nodes: [],
next: null,
proposed_dist: Number.POSITIVE_INFINITY,
};
/**
* HOOK 1: PFS INIT
*/
callbacks.init_pfs && $CB.execCallbacks(callbacks.init_pfs, scope);
//initializes the result entry, gives the start node the final values, and default values for all others
scope.OPEN_HEAP.insert(start_ne);
scope.OPEN[start_ne.node.getID()] = start_ne;
/**
* Main loop
*/
while (scope.OPEN_HEAP.size()) {
scope.current = scope.OPEN_HEAP.pop();
// console.log(`node: ${scope.current.node.getID()}`); //LOG!
// console.log(`best: ${scope.current.best}`); //LOG!
/**
* HOOK 2: NEW CURRENT
*/
callbacks.new_current && $CB.execCallbacks(callbacks.new_current, scope);
if (scope.current == null) {
console.log("HEAP popped undefined - HEAP size: " + scope.OPEN_HEAP.size());
}
// remove from OPEN
scope.OPEN[scope.current.node.getID()] = undefined;
// add it to CLOSED
scope.CLOSED[scope.current.node.getID()] = scope.current;
// TODO what if we already reached the goal?
if (scope.current.node === config.goal_node) {
/**
* HOOK 3: Goal node reached
*/
config.callbacks.goal_reached && $CB.execCallbacks(config.callbacks.goal_reached, scope);
// If a goal node is set from the outside & we reach it, we stop.
return config.result;
}
/**
* Extend the current node, also called
* "create n's successors"...
*/
// TODO: Reverse callback logic to NOT merge anything by default!!!
if (dir_mode === GraphMode.MIXED) {
scope.adj_nodes = scope.current.node.reachNodes();
}
else if (dir_mode === GraphMode.UNDIRECTED) {
scope.adj_nodes = scope.current.node.connNodes();
}
else if (dir_mode === GraphMode.DIRECTED) {
scope.adj_nodes = scope.current.node.nextNodes();
}
else {
throw new Error('Unsupported traversal mode. Please use directed, undirected, or mixed');
}
/**
* EXPAND AND EXAMINE NEIGHBORHOOD
*/
for (let adj_idx in scope.adj_nodes) {
scope.next = scope.adj_nodes[adj_idx];
// console.log("scopeNext now:"); //LOG!
// console.log(scope.next.node.getID());
if (scope.CLOSED[scope.next.node.getID()]) {
/**
* HOOK 4: Goal node already closed
*/
config.callbacks.node_closed && $CB.execCallbacks(config.callbacks.node_closed, scope);
continue;
}
if (scope.OPEN[scope.next.node.getID()]) {
// First let's recover the previous best solution from our OPEN structure,
// as the node's neighborhood-retrieving function cannot know it...
// console.log("MARKER - ALREADY OPEN"); //LOG!
scope.next.best = scope.OPEN[scope.next.node.getID()].best;
/**
* HOOK 5: Goal node already visited, but not yet closed
*/
config.callbacks.node_open && $CB.execCallbacks(config.callbacks.node_open, scope);
scope.proposed_dist = scope.current.best + (isNaN(scope.next.edge.getWeight()) ? DEFAULT_WEIGHT : scope.next.edge.getWeight());
/**
* HOOK 6: Better path found
*/
if (scope.next.best > scope.proposed_dist) {
config.callbacks.better_path && $CB.execCallbacks(config.callbacks.better_path, scope);
// HEAP operations are necessary for internal traversal,
// so we handle them here in the main loop
// removing next with the old weight and re-adding it with updated value
scope.OPEN_HEAP.remove(scope.next);
// console.log("MARKER - BETTER DISTANCE");
// console.log(scope.OPEN_HEAP);
scope.next.best = scope.proposed_dist;
scope.OPEN_HEAP.insert(scope.next);
scope.OPEN[scope.next.node.getID()].best = scope.proposed_dist;
}
/**
* HOOK 7: Equal path found (same weight)
*/
//at the moment, this callback array is empty here in the PFS and in the Dijkstra, but used in the Johnsons
else if (scope.next.best === scope.proposed_dist) {
config.callbacks.equal_path && $CB.execCallbacks(config.callbacks.equal_path, scope);
}
continue;
}
// NODE NOT ENCOUNTERED
config.callbacks.not_encountered && $CB.execCallbacks(config.callbacks.not_encountered, scope);
// HEAP operations are necessary for internal traversal,
// so we handle them here in the main loop
scope.OPEN_HEAP.insert(scope.next);
scope.OPEN[scope.next.node.getID()] = scope.next;
// console.log("MARKER-NOT ENCOUNTERED"); //LOG!
}
}
return config.result;
}
function preparePFSStandardConfig(): PFS_Config {
let config: PFS_Config = {
result: {},
callbacks: {
init_pfs: [],
new_current: [],
not_encountered: [],
node_open: [],
node_closed: [],
better_path: [],
equal_path: [],
goal_reached: []
},
messages: {
init_pfs_msgs: [],
new_current_msgs: [],
not_enc_msgs: [],
node_open_msgs: [],
node_closed_msgs: [],
better_path_msgs: [],
equal_path_msgs: [],
goal_reached_msgs: []
},
dir_mode: GraphMode.MIXED,
goal_node: null,
evalPriority: function (ne: $N.NeighborEntry) {
return ne.best || DEFAULT_WEIGHT;
},
evalObjID: function (ne: $N.NeighborEntry) {
return ne.node.getID();
}
};
let callbacks = config.callbacks;
let count = 0;
let counter = function () {
return count++;
};
// Standard INIT callback
let initPFS = function (context: PFS_Scope) {
// initialize all nodes to infinite distance
for (let key in context.nodes) {
config.result[key] = {
distance: Number.POSITIVE_INFINITY,
parent: null,
counter: -1
};
}
// initialize root node entry
// maybe take heuristic into account right here...??
config.result[context.root_node.getID()] = {
distance: 0,
parent: context.root_node,
counter: counter()
};
};
callbacks.init_pfs.push(initPFS);
// Node not yet encountered callback
let notEncountered = function (context: PFS_Scope) {
// setting it's best score to actual distance + edge weight
// and update result structure
context.next.best = context.current.best + (isNaN(context.next.edge.getWeight()) ? DEFAULT_WEIGHT : context.next.edge.getWeight());
config.result[context.next.node.getID()] = {
distance: context.next.best,
parent: context.current.node,
counter: undefined
};
};
callbacks.not_encountered.push(notEncountered);
// Callback for when we find a better solution
let betterPathFound = function (context: PFS_Scope) {
config.result[context.next.node.getID()].distance = context.proposed_dist;
config.result[context.next.node.getID()].parent = context.current.node;
};
callbacks.better_path.push(betterPathFound);
return config;
}
export { PFS, preparePFSStandardConfig };
{
"compilerOptions": {
"target": "es6",
"module": "commonjs",
"moduleResolution": "node",
"sourceMap": false,
"lib": [
"es2017",
"dom"
],
"removeComments": true
},
"compileOnSave": false,
"include": [
"./**/*.ts"
]
}
/**
* @param cbs
* @param context this pointer to the DFS or DFSVisit function
*/
function execCallbacks(cbs : Array<Function>, context?) {
cbs.forEach( function(cb) {
if ( typeof cb === 'function' ) {
cb(context);
}
else {
throw new Error('Provided callback is not a function.');
}
});
}
export { execCallbacks };
import {LOG_LEVELS, runLevel} from '../config/run_config';
export interface LOG_CONFIG {
log_level: string;
}
export enum LogColors {
FgBlack = 30,
FgRed = 31,
FgGreen = 32,
FgYellow = 33,
FgBlue = 34,
FgMagenta = 35,
FgCyan = 36,
FgWhite = 37,
BgBlack = 40,
BgRed = 41,
BgGreen = 42,
BgYellow = 43,
BgBlue = 44,
BgMagenta = 45,
BgCyan = 46,
BgWhite = 47
}
const DEFAULT_COLOR = 37; // white
class Logger {
public config: LOG_CONFIG;
constructor(config?) {
this.config = config || {
log_level: runLevel()
};
}
log(msg, color?, bright = false): boolean {
if (this.config.log_level === LOG_LEVELS.debug) {
if ( color ) {
console.log.call(console, Logger.colorize(DEFAULT_COLOR, msg, bright));
}
else {
console.log.call(console, msg);
}
return true;
}
return false;
}
error(err, color?, bright = false): boolean {
if (this.config.log_level === LOG_LEVELS.debug) {
if ( color ) {
console.error.call(console, Logger.colorize(color, err, bright));
}
else {
console.error.call(console, err);
}
return true;
}
return false;
}
dir(obj, color?, bright = false): boolean {
if (this.config.log_level === LOG_LEVELS.debug) {
if ( color ) {
console.dir.call(console, Logger.colorize(DEFAULT_COLOR, obj, bright));
}
else {
console.dir.call(console, obj);
}
return true;
}
return false;
}
info(msg, color?, bright = false): boolean {
if (this.config.log_level === LOG_LEVELS.debug) {
if ( color ) {
console.info.call(console, Logger.colorize(DEFAULT_COLOR, msg, bright));
}
else {
console.info.call(console, msg);
}
return true;
}
return false;
}
warn(msg, color?, bright = false): boolean {
if (this.config.log_level === LOG_LEVELS.debug) {
if ( color ) {
console.warn.call(console, Logger.colorize(DEFAULT_COLOR, msg, bright));
}
else {
console.warn.call(console, msg);
}
return true;
}
return false;
}
write(msg, color?, bright = false): boolean {
if (this.config.log_level === LOG_LEVELS.debug) {
if ( color ) {
process.stdout.write.call(process.stdout, Logger.colorize(DEFAULT_COLOR, msg, bright));
}
else {
process.stdout.write.call(process.stdout, msg);
}
return true;
}
return false;
}
/**
* @todo this one prevents objects from being output in detail ([object Object])
* @param color
* @param output
* @param bright
*/
static colorize(color, output, bright) {
let out_bright = bright ? '\x1b[1m' : null;
return [out_bright, '\x1b[', color, 'm', output, '\x1b[0m'].join('');
}
}
export {Logger};
import * as http from 'http';
import * as https from 'https';
import { Logger } from './Logger';
const logger = new Logger();
const SSL_PORT = '443';
export interface RequestConfig {
remote_host: string,
remote_path: string,
file_name: string
}
/**
* @TODO: Test it !!!
*
* @param url
* @param cb
* @returns {ClientRequest}
*/
export function retrieveRemoteFile(config: RequestConfig, cb: Function) {
if ( typeof cb !== 'function' ) {
throw new Error('Provided callback is not a function.');
}
logger.log(`Requesting file via NodeJS request: ${config.remote_host}${config.remote_path}${config.file_name}`);
let options : https.RequestOptions = {
host: config.remote_host,
port: SSL_PORT,
path: config.remote_path + config.file_name,
method: 'GET'
};
let req = https.get(options, response => {
// Continuously update stream with data
var body = '';
response.setEncoding('utf8');
response.on('data', function(d) {
body += d;
});
response.on('end', function() {
// Received data in body...
cb(body);
});
});
req.on('error', e => {
logger.log(`Request error: ${e.message}`);
});
return req;
}
export function checkNodeEnvironment(): void {
if (typeof window !== 'undefined') {
throw new Error('When in Browser, do as the Browsers do! (use fetch and call readFromJSON() directly...) ')
}
}
import {BaseGraph} from '../core/base/BaseGraph'
import {BaseNode} from '../core/base/BaseNode';
import {BaseEdge} from '../core/base/BaseEdge';
/**
* Method to deep clone an object
*
* @param obj
* @returns {*}
*
*/
function clone(obj: any): any {
if (obj === null || typeof obj !== 'object') {
return obj;
}
/**
* @description for the sake of cloning graph structures, we have specialized
* clone methods within the BaseGraph, BaseNode & BaseEdge classes
*/
if (obj instanceof BaseGraph || obj instanceof BaseNode || obj instanceof BaseEdge) {
return null;
}
let cloneObj = Array.isArray(obj) ? [] : {};
for (let attribute in obj) {
if ( !obj.hasOwnProperty(attribute) ) {
continue;
}
if (typeof obj[attribute] === "object") {
cloneObj[attribute] = clone(obj[attribute]);
} else {
cloneObj[attribute] = obj[attribute];
}
}
return cloneObj;
}
/**
*
* @param arr
*
* @todo it's obvious, nevertheless needs some testing...
*/
function shuffleArray(arr: Array<any>): Array<any> {
for (let i = arr.length - 1; i >= 0; i--) {
let randomIndex = Math.floor(Math.random() * (i + 1));
let itemAtIndex = arr[randomIndex];
arr[randomIndex] = arr[i];
arr[i] = itemAtIndex;
}
return arr;
}
/**
* @args an Array of any kind of objects
* @cb callback to return a unique identifier;
* if this is duplicate, the object will not be stored in result.
* @returns {Array}
*
* @todo
*/
function mergeArrays(args: Array<Array<any>>, cb: Function = undefined) {
for (let arg_idx in args) {
if (!Array.isArray(args[arg_idx])) {
throw new Error('Will only mergeArrays arrays');
}
}
let seen = {},
result = [],
identity;
for (let i = 0; i < args.length; i++) {
for (let j = 0; j < args[i].length; j++) {
identity = typeof cb !== 'undefined' ? cb(args[i][j]) : args[i][j];
if (seen[identity] !== true) {
result.push(args[i][j]);
seen[identity] = true;
}
}
}
return result;
}
/**
* Overwrites obj1's values with obj2's and adds obj2's if non existent in obj1
* @param args Array of all the object to take keys from
* @returns result object
*/
function mergeObjects(args: Array<Object>) {
for (let i = 0; i < args.length; i++) {
if (Object.prototype.toString.call(args[i]) !== '[object Object]') {
throw new Error('Will only take objects as inputs');
}
}
let result = {};
for (let i = 0; i < args.length; i++) {
for (let key in args[i]) {
if (args[i].hasOwnProperty(key)) {
result[key] = args[i][key];
}
}
}
return result;
}
/**
* Takes two ordered number arrays and merges them. The returned array is
* also ordered and does not contain any duplicates.
*
* @param a: first array
* @param b: second array
*/
function mergeOrderedArraysNoDups(a: Array<number>, b: Array<number>): Array<number> {
let ret: Array<number> = [];
let idx_a = 0;
let idx_b = 0;
if (a[0] != null && b[0] != null) {
while (true) {
if (idx_a >= a.length || idx_b >= b.length) {
break;
}
if (a[idx_a] == b[idx_b]) {
if (ret[ret.length - 1] != a[idx_a]) {
ret.push(a[idx_a]);
}
idx_a++;
idx_b++;
continue;
}
if (a[idx_a] < b[idx_b]) {
ret.push(a[idx_a]);
idx_a++;
continue;
}
if (b[idx_b] < a[idx_a]) {
ret.push(b[idx_b]);
idx_b++;
}
}
}
while (idx_a < a.length) {
if (a[idx_a] != null) {
ret.push(a[idx_a]);
}
idx_a++;
}
while (idx_b < b.length) {
if (b[idx_b] != null) {
ret.push(b[idx_b]);
}
idx_b++;
}
return ret;
}
export {
clone,
shuffleArray,
mergeArrays,
mergeObjects,
mergeOrderedArraysNoDups
};
+33
-33
// Core (why is compute graph here !?)
export * from './src/core/interfaces';
export * from './src/core/compute/ComputeGraph';
export * from './lib/core/interfaces';
export * from './lib/core/compute/ComputeGraph';
// Base
export * from './src/core/base/BaseEdge';
export * from './src/core/base/BaseNode';
export * from './src/core/base/BaseGraph';
export * from './lib/core/base/BaseEdge';
export * from './lib/core/base/BaseNode';
export * from './lib/core/base/BaseGraph';
// Typed
export * from './src/core/typed/TypedEdge';
export * from './src/core/typed/TypedNode';
export * from './src/core/typed/TypedGraph';
export * from './lib/core/typed/TypedEdge';
export * from './lib/core/typed/TypedNode';
export * from './lib/core/typed/TypedGraph';
// Centralities
export * from './src/centralities/Betweenness';
export * from './src/centralities/Brandes';
export * from './src/centralities/Closeness';
export * from './src/centralities/Degree';
export * from './src/centralities/Pagerank';
export * from './lib/centralities/Betweenness';
export * from './lib/centralities/Brandes';
export * from './lib/centralities/Closeness';
export * from './lib/centralities/Degree';
export * from './lib/centralities/Pagerank';
// IO
export * from './src/io/input/CSVInput';
export * from './src/io/input/JSONInput';
export * from './src/io/output/CSVOutput';
export * from './src/io/output/JSONOutput';
export * from './lib/io/input/CSVInput';
export * from './lib/io/input/JSONInput';
export * from './lib/io/output/CSVOutput';
export * from './lib/io/output/JSONOutput';
// Traversal
export * from './src/traversal/BFS';
export * from './src/traversal/DFS';
export * from './src/traversal/PFS';
export * from './src/traversal/Dijkstra';
export * from './src/traversal/BellmanFord';
export * from './src/traversal/FloydWarshall';
export * from './src/traversal/Johnsons';
export * from './lib/traversal/BFS';
export * from './lib/traversal/DFS';
export * from './lib/traversal/PFS';
export * from './lib/traversal/Dijkstra';
export * from './lib/traversal/BellmanFord';
export * from './lib/traversal/FloydWarshall';
export * from './lib/traversal/Johnsons';
// Similarities
export * from './src/similarities/SimilarityCommons';
export * from './src/similarities/SetSimilarities';
export * from './src/similarities/ScoreSimilarities';
export * from './lib/similarities/SimilarityCommons';
export * from './lib/similarities/SetSimilarities';
export * from './lib/similarities/ScoreSimilarities';
// Utils
export * from './src/utils/StructUtils';
export * from './src/utils/RemoteUtils';
export * from './src/utils/CallbackUtils';
export * from './lib/utils/StructUtils';
export * from './lib/utils/RemoteUtils';
export * from './lib/utils/CallbackUtils';
// Datastructs
export * from './src/datastructs/BinaryHeap';
export * from './lib/datastructs/BinaryHeap';
// Perturbation
export * from './src/perturbation/SimplePerturbations';
export * from './lib/perturbation/SimplePerturbations';
// Generators
export * from './src/generators/KroneckerLeskovec';
export * from './lib/generators/KroneckerLeskovec';
+4
-199

@@ -1,202 +0,7 @@

Apache License
Version 2.0, January 2004
http://www.apache.org/licenses/
Copyright 2020 Bernd Malle
TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION
Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
1. Definitions.
The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
"License" shall mean the terms and conditions for use, reproduction,
and distribution as defined by Sections 1 through 9 of this document.
"Licensor" shall mean the copyright owner or entity authorized by
the copyright owner that is granting the License.
"Legal Entity" shall mean the union of the acting entity and all
other entities that control, are controlled by, or are under common
control with that entity. For the purposes of this definition,
"control" means (i) the power, direct or indirect, to cause the
direction or management of such entity, whether by contract or
otherwise, or (ii) ownership of fifty percent (50%) or more of the
outstanding shares, or (iii) beneficial ownership of such entity.
"You" (or "Your") shall mean an individual or Legal Entity
exercising permissions granted by this License.
"Source" form shall mean the preferred form for making modifications,
including but not limited to software source code, documentation
source, and configuration files.
"Object" form shall mean any form resulting from mechanical
transformation or translation of a Source form, including but
not limited to compiled object code, generated documentation,
and conversions to other media types.
"Work" shall mean the work of authorship, whether in Source or
Object form, made available under the License, as indicated by a
copyright notice that is included in or attached to the work
(an example is provided in the Appendix below).
"Derivative Works" shall mean any work, whether in Source or Object
form, that is based on (or derived from) the Work and for which the
editorial revisions, annotations, elaborations, or other modifications
represent, as a whole, an original work of authorship. For the purposes
of this License, Derivative Works shall not include works that remain
separable from, or merely link (or bind by name) to the interfaces of,
the Work and Derivative Works thereof.
"Contribution" shall mean any work of authorship, including
the original version of the Work and any modifications or additions
to that Work or Derivative Works thereof, that is intentionally
submitted to Licensor for inclusion in the Work by the copyright owner
or by an individual or Legal Entity authorized to submit on behalf of
the copyright owner. For the purposes of this definition, "submitted"
means any form of electronic, verbal, or written communication sent
to the Licensor or its representatives, including but not limited to
communication on electronic mailing lists, source code control systems,
and issue tracking systems that are managed by, or on behalf of, the
Licensor for the purpose of discussing and improving the Work, but
excluding communication that is conspicuously marked or otherwise
designated in writing by the copyright owner as "Not a Contribution."
"Contributor" shall mean Licensor and any individual or Legal Entity
on behalf of whom a Contribution has been received by Licensor and
subsequently incorporated within the Work.
2. Grant of Copyright License. Subject to the terms and conditions of
this License, each Contributor hereby grants to You a perpetual,
worldwide, non-exclusive, no-charge, royalty-free, irrevocable
copyright license to reproduce, prepare Derivative Works of,
publicly display, publicly perform, sublicense, and distribute the
Work and such Derivative Works in Source or Object form.
3. Grant of Patent License. Subject to the terms and conditions of
this License, each Contributor hereby grants to You a perpetual,
worldwide, non-exclusive, no-charge, royalty-free, irrevocable
(except as stated in this section) patent license to make, have made,
use, offer to sell, sell, import, and otherwise transfer the Work,
where such license applies only to those patent claims licensable
by such Contributor that are necessarily infringed by their
Contribution(s) alone or by combination of their Contribution(s)
with the Work to which such Contribution(s) was submitted. If You
institute patent litigation against any entity (including a
cross-claim or counterclaim in a lawsuit) alleging that the Work
or a Contribution incorporated within the Work constitutes direct
or contributory patent infringement, then any patent licenses
granted to You under this License for that Work shall terminate
as of the date such litigation is filed.
4. Redistribution. You may reproduce and distribute copies of the
Work or Derivative Works thereof in any medium, with or without
modifications, and in Source or Object form, provided that You
meet the following conditions:
(a) You must give any other recipients of the Work or
Derivative Works a copy of this License; and
(b) You must cause any modified files to carry prominent notices
stating that You changed the files; and
(c) You must retain, in the Source form of any Derivative Works
that You distribute, all copyright, patent, trademark, and
attribution notices from the Source form of the Work,
excluding those notices that do not pertain to any part of
the Derivative Works; and
(d) If the Work includes a "NOTICE" text file as part of its
distribution, then any Derivative Works that You distribute must
include a readable copy of the attribution notices contained
within such NOTICE file, excluding those notices that do not
pertain to any part of the Derivative Works, in at least one
of the following places: within a NOTICE text file distributed
as part of the Derivative Works; within the Source form or
documentation, if provided along with the Derivative Works; or,
within a display generated by the Derivative Works, if and
wherever such third-party notices normally appear. The contents
of the NOTICE file are for informational purposes only and
do not modify the License. You may add Your own attribution
notices within Derivative Works that You distribute, alongside
or as an addendum to the NOTICE text from the Work, provided
that such additional attribution notices cannot be construed
as modifying the License.
You may add Your own copyright statement to Your modifications and
may provide additional or different license terms and conditions
for use, reproduction, or distribution of Your modifications, or
for any such Derivative Works as a whole, provided Your use,
reproduction, and distribution of the Work otherwise complies with
the conditions stated in this License.
5. Submission of Contributions. Unless You explicitly state otherwise,
any Contribution intentionally submitted for inclusion in the Work
by You to the Licensor shall be under the terms and conditions of
this License, without any additional terms or conditions.
Notwithstanding the above, nothing herein shall supersede or modify
the terms of any separate license agreement you may have executed
with Licensor regarding such Contributions.
6. Trademarks. This License does not grant permission to use the trade
names, trademarks, service marks, or product names of the Licensor,
except as required for reasonable and customary use in describing the
origin of the Work and reproducing the content of the NOTICE file.
7. Disclaimer of Warranty. Unless required by applicable law or
agreed to in writing, Licensor provides the Work (and each
Contributor provides its Contributions) on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
implied, including, without limitation, any warranties or conditions
of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A
PARTICULAR PURPOSE. You are solely responsible for determining the
appropriateness of using or redistributing the Work and assume any
risks associated with Your exercise of permissions under this License.
8. Limitation of Liability. In no event and under no legal theory,
whether in tort (including negligence), contract, or otherwise,
unless required by applicable law (such as deliberate and grossly
negligent acts) or agreed to in writing, shall any Contributor be
liable to You for damages, including any direct, indirect, special,
incidental, or consequential damages of any character arising as a
result of this License or out of the use or inability to use the
Work (including but not limited to damages for loss of goodwill,
work stoppage, computer failure or malfunction, or any and all
other commercial damages or losses), even if such Contributor
has been advised of the possibility of such damages.
9. Accepting Warranty or Additional Liability. While redistributing
the Work or Derivative Works thereof, You may choose to offer,
and charge a fee for, acceptance of support, warranty, indemnity,
or other liability obligations and/or rights consistent with this
License. However, in accepting such obligations, You may act only
on Your own behalf and on Your sole responsibility, not on behalf
of any other Contributor, and only if You agree to indemnify,
defend, and hold each Contributor harmless for any liability
incurred by, or claims asserted against, such Contributor by reason
of your accepting any such warranty or additional liability.
END OF TERMS AND CONDITIONS
APPENDIX: How to apply the Apache License to your work.
To apply the Apache License to your work, attach the following
boilerplate notice, with the fields enclosed by brackets "{}"
replaced with your own identifying information. (Don't include
the brackets!) The text should be enclosed in the appropriate
comment syntax for the file format. We also recommend that a
file or class name and description of purpose be included on the
same "printed page" as the copyright notice for easier
identification within third-party archives.
Copyright {2016} {Bernd Malle}
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

@@ -6,3 +6,3 @@ {

"clean": "rm -rf coverage docs",
"doc": "typedoc --out docs src",
"doc": "typedoc --out docs lib",
"test:all": "jest -c jest.config.all.js",

@@ -38,3 +38,3 @@ "test:sync": "jest -c jest.config.js",

"name": "graphinius",
"version": "2.0.0",
"version": "2.0.1",
"description": "Generic graph library in Typescript",

@@ -41,0 +41,0 @@ "main": "index.ts",