Class: GraphAlgorithmUtils

Kekule. GraphAlgorithmUtils

new GraphAlgorithmUtils()

Util class to do common algorithms on graph.
Source:

Methods

(static) analysisRings(graphOrGraphPart) → {Array}

Returns ring system details of graph or cycle block.
Parameters:
Name Type Description
graphOrGraphPart Variant A instance of Kekule.Graph or a graph cycle block ({vertexes, edsges}) found by Kekule.GraphAlgorithmUtils.findCycleBlocks.
Source:
Returns:
An array, each items is a cycle block detail. Item containing a series of hash with fields: { vertexes: Array of all vertexes in cycle block. edges: Array of all edges in cycle block. sssrRings: Array, each item containing edges and vertexes in a SSSR member ring. }
Type
Array

(static) createSpanningTrees(graph, traverseMode) → {Array}

Creating a depth first spanning tree (child graph) of graph.
Parameters:
Name Type Description
graph Kekule.Graph
traverseMode int Depth or breadth first.
Source:
Returns:
Items are hashes that contains the follow fields: { vertexes: Array of all found vertexes. edges: Array of all found edges. } which indicate a spanning tree in graph. As the graph may not be connected, so several spanning trees may exists.
Type
Array

(static) findAllRings(graphOrGraphPart) → {Array}

Returns all rings in a graph.
Parameters:
Name Type Description
graphOrGraphPart Variant A instance of Kekule.Graph or a graph cycle part ({vertexes, edsges}) found by Kekule.GraphAlgorithmUtils.findCycleBlocks.
Source:
Returns:
An array containing a series of hash with fields: { vertexes: Array of all found vertexes. edges: Array of all found edges. } Each array item marks a ring.
Type
Array

(static) findBridgeChains(graph) → {Hash}

Returns all vertexes and edges in bridge chain of a graph. Note: this function must be called after (@link Kekule.GraphAlgorithmUtils.removeEndChains}.
Parameters:
Name Type Description
graph Kekule.Graph
Source:
Returns:
A hash that contains the follow fields: { vertexes: Array of all found vertexes. edges: Array of all found edges. }
Type
Hash

(static) findCycleBlocks(graph) → {Array}

Returns all vertexes and edges in cylce block.
Parameters:
Name Type Description
graph Kekule.Graph
Source:
Returns:
An array containing a series of hash with fields: { vertexes: Array of all found vertexes. edges: Array of all found edges. } Each array item marks a cycle block.
Type
Array

(static) findEndChains(graph) → {Hash}

Returns all vertexes and edges in end chain of a graph.
Parameters:
Name Type Description
graph Kekule.Graph
Source:
Returns:
A hash that contains the follow fields: { vertexes: Array of all found vertexes. edges: Array of all found edges. }
Type
Hash

(static) findSSSR(graphOrGraphPart, allRings) → {Array}

Returns Smallest set of smallest rings of graph or cycle part.
Parameters:
Name Type Description
graphOrGraphPart Variant A instance of Kekule.Graph or a graph cycle part ({vertexes, edsges}) found by Kekule.GraphAlgorithmUtils.findCycleBlocks.
allRings Array All rings of cycle block, input this param can reduce the calculation time. Note: this param will only be used when the previous param is a graph part.
Source:
Returns:
An array containing a series of hash with fields: { vertexes: Array of all found vertexes. edges: Array of all found edges. } Each array item marks a SSSR ring.
Type
Array

(static) removeBridgeChains(graph) → {Hash}

Removes all vertexes and edges in bridge chain of a graph. Note: this function must be called after (@link Kekule.GraphAlgorithmUtils.removeEndChains}.
Parameters:
Name Type Description
graph Kekule.Graph
Source:
Returns:
A hash that contains the follow fields: { vertexes: Array of all removed vertexes. edges: Array of all removed edges. }
Type
Hash

(static) removeEndChains(graph) → {Hash}

Removes all side end chains from graph.
Parameters:
Name Type Description
graph Kekule.Graph
Source:
Returns:
A hash that contains the follow fields: { vertexes: Array of all removed vertexes. edges: Array of all removed edges. } which stores vertexes and edges been removed.
Type
Hash