Module: lang/graph

Computation over graphs. Unless otherwise specified a graph is a simple JS object whose properties are interpreted as nodes that refer to arrays whose elements describe edges.

var testGraph = {
  "a": ["b", "c"],
  "b": ["c", "d", "e", "f"],
  "d": ["c", "f"],
  "e": ["a", "f"],
  "f": []
}

Source: lively.lang/graph.js, line 1

Methods

(inner) clone(graph) → {Object.<string, Array.<string>>}

Returns a copy of graph map.

Parameters:

Name	Type	Description
`graph`	Object.<string, Array.<string>>	The map to copy.

Source: lively.lang/graph.js, line 25

Returns:

The copy of the graph.

Type:: Object.<string, Array.<string>>

(inner) hull(g, id, ignoredKeyList, maxDepthopt) → {Array.<string>}

Takes a graph in object format and a start id and then traverses the graph and gathers all nodes that can be reached from that start id. Returns a list of those nodes. Optionally use ignore list to filter out certain nodes that shouldn't be considered and maxDepth to stop early. By default a maxDepth of 20 is used.

Parameters:

Name	Type	Attributes	Description
`g`	Object.<string, Array.<string>>		The graph to traverse.
`id`	string		The id of the node to start the hull computation from.
`ignoredKeyList`	Array.<string>		The ids of the nodes to skip from the traversal.
`maxDepth`	number	<optional>	The maximum recursion depth of the traversal.

Source: lively.lang/graph.js, line 75

Returns:

The list of ids of all the nodes inside the hull.

Type:: Array.<string>

Example

var testGraph = {
"a": ["b", "c"],
"b": ["c", "d", "e", "f"],
"d": ["c", "f"],
"e": ["a", "f"],
"f": []
}
hull(testGraph, "d") // => ["c", "f"]
hull(testGraph, "e") // => ['a', 'f', 'b', 'c', 'd', 'e']
hull(testGraph, "e", ["b"]) // => ["a", "f", "c"]

(inner) invert(g) → {Object.<string, Array.<string>>}

Inverts the references of graph object g.

Parameters:

Name	Type	Description
`g`	Object.<string, Array.<string>>	The graph to invert.

Source: lively.lang/graph.js, line 156

Returns:

The inverted graph.

Type:: Object.<string, Array.<string>>

Example

invert({a: ["b"], b: ["a", "c"]})
  // => {a: ["b"], b: ["a"], c: ["b"]}

(inner) random(nKeysopt) → {Object.<string, Array.<string>>}

Generates a graph based on a given number of ids that should appear.

Parameters:

Name	Type	Attributes	Default	Description
`nKeys`	number	<optional>	10	The number of ids inside the generated graph.

Source: lively.lang/graph.js, line 277

Returns:

A graph with the provided number of ids initialized at random.

Type:: Object.<string, Array.<string>>

(inner) reduce(doFunc, graph, rootNode, carryOver, context) → {*}

Starts with rootNode and visits all (in)directly related nodes, calling doFunc at each node. The result of doFunc is passed as first argument to the next iterator call. For the first call the value carryOver is used.

Parameters:

Name	Type	Description
`doFunc`	function	The function applied to each visited node.
`graph`	Object.<string, Array.<string>>	The graph to traverse.
`rootNode`	string	The id of the node to start the traversal from.
`carryOver`	*	The value to feed into the first call of `doFunc`.
`context`	Object	The object to bind `this` to when calling the `doFunc`.

Source: lively.lang/graph.js, line 258

Returns:

The final result of the reducer. Example: var depGraph = {a: ["b", "c"],b: ["c"]} reduce((_, ea, i) => console.log("%s %s", ea, i), depGraph, "a")

Type:: *

(inner) sortByReference(depGraph, startNode) → {Array.<Array.<string>>}

Sorts graph into an array of arrays. Each "bucket" contains the graph nodes that have no other incoming nodes than those already visited. This means, we start with the leaf nodes and then walk our way up. This is useful for computing how to traverse a dependency graph: You get a sorted list of dependencies that also allows circular references.

Parameters:

Name	Type	Description
`depGraph`	Object.<string, Array.<string>>	The graph to sort into buckets.
`startNode`	string	The id of the node at the top of the dependency graph.

Source: lively.lang/graph.js, line 183

Returns:

The sorted sets of nodes.

Type:: Array.<Array.<string>>

Example

var depGraph = {a: ["b", "c"], b: ["c"], c: ["b"]};
sortByReference(depGraph, "a");
// => [["c"], ["b"], ["a"]]

(inner) subgraphReachableBy(graphMap, startId, ignore, maxDepthopt) → {Object.<string, Array.<string>>}

Like hull but returns subgraph map of graphMap.

Parameters:

Name	Type	Attributes	Description
`graphMap`	Object.<string, Array.<string>>		The graph to compute the subgraph for.
`startId`	string		The id of the node to start the subgraph computation from.
`ignore`	Array.<string>		The ids of the nodes to skip from the traversal.
`maxDepth`	number	<optional>	The maximum recursion depth of the traversal.

Source: lively.lang/graph.js, line 135
See: hull

Returns:

The subgraph reachable from id.

Type:: Object.<string, Array.<string>>

Example

subgraphReachableBy(testGraph, "e", [], 2);
// => {e: [ 'a', 'f' ], a: [ 'b', 'c' ], f: []}

(inner) without(graph, ids) → {Object.<string, Array.<string>>}

Returns a copy of graph map with the given ids removed.

Parameters:

Name	Type	Description
`graph`	Object.<string, Array.<string>>	The map to copy.
`ids`	Array.<string>	The list of ids to exclude in the copy.

Source: lively.lang/graph.js, line 37

Returns:

The (filtered) copy of the graph.

Type:: Object.<string, Array.<string>>