editor › Globals › Graph

Class: Graph ‹T›

This Class provides functionality needed to perform a connectivity test on a Graph. It is used to calculate MinCuts up to a fixed size in the plate graph It uses an adjacency matrix to allow performant delete and re-insert operations.

Type parameters

▪ T

Hierarchy

• Graph

Index

Constructors

• constructor

Properties

• adjMatrix
• backingObjects
• isDeleted
• nodeCountCurrent
• nodeCountWithDeleted

Methods

• _existingIndex
• _minCutNodes
• _nodes
• _readdNode
• _removeNode
• addEdge
• asBackingObjects
• connectedComponents
• fromBackingObject
• fromBackingObjects
• isConnected
• isCut
• nodeCount
• nodeCut
• nodesInComponent
• readdNodes
• removeNodes
• _permutation
• fromJsGraph

Constructors

constructor

+ new Graph(backingObjects: T[]): Graph

Defined in src/modules/kyub.core.reinforcement/src/Graph.ts:73

Parameters:

Name	Type
backingObjects	T[]

Returns: Graph

Properties

Private Readonly adjMatrix

• adjMatrix: number[][]

Defined in src/modules/kyub.core.reinforcement/src/Graph.ts:69

---

Private Readonly backingObjects

• backingObjects: T[]

Defined in src/modules/kyub.core.reinforcement/src/Graph.ts:71

---

Private Readonly isDeleted

• isDeleted: boolean[]

Defined in src/modules/kyub.core.reinforcement/src/Graph.ts:70

---

Private nodeCountCurrent

• nodeCountCurrent: number

Defined in src/modules/kyub.core.reinforcement/src/Graph.ts:72

---

Private Readonly nodeCountWithDeleted

• nodeCountWithDeleted: number

Defined in src/modules/kyub.core.reinforcement/src/Graph.ts:73

Methods

Private _existingIndex

▸ _existingIndex(): number

Defined in src/modules/kyub.core.reinforcement/src/Graph.ts:219

Returns: number

---

Private _minCutNodes

▸ _minCutNodes(maxSize: number): number[]

Defined in src/modules/kyub.core.reinforcement/src/Graph.ts:205

Parameters:

Name	Type
maxSize	number

Returns: number[]

---

Private _nodes

▸ _nodes(): number[]

Defined in src/modules/kyub.core.reinforcement/src/Graph.ts:226

return all node indices that are currently not deleted

Returns: number[]

---

Private _readdNode

▸ _readdNode(node: number): void

Defined in src/modules/kyub.core.reinforcement/src/Graph.ts:237

Parameters:

Name	Type
node	number

Returns: void

---

Private _removeNode

▸ _removeNode(node: number): void

Defined in src/modules/kyub.core.reinforcement/src/Graph.ts:230

Parameters:

Name	Type
node	number

Returns: void

---

addEdge

▸ addEdge(from: number, to: number): void

Defined in src/modules/kyub.core.reinforcement/src/Graph.ts:200

inserts an edge into the graph runs in O(1) because of adjacency matrix

Parameters:

Name	Type	Description
from	number	-
to	number

Returns: void

---

asBackingObjects

▸ asBackingObjects(nodes: number[]): T[]

Defined in src/modules/kyub.core.reinforcement/src/Graph.ts:90

Parameters:

Name	Type
nodes	number[]

Returns: T[]

---

connectedComponents

▸ connectedComponents(): object

Defined in src/modules/kyub.core.reinforcement/src/Graph.ts:143

splits the graph in two not connected parts if the graph was connected before component 2 will be empty if the graph consists of more than one component all component except the first one will be together in the second component.

Runs in O(V)

Returns: object

• nodesInPartition1: number[]

• nodesInPartition2: number[]

---

fromBackingObject

▸ fromBackingObject(backingObject: T): number

Defined in src/modules/kyub.core.reinforcement/src/Graph.ts:98

Parameters:

Name	Type
backingObject	T

Returns: number

---

fromBackingObjects

▸ fromBackingObjects(backingObjects: T[]): number[]

Defined in src/modules/kyub.core.reinforcement/src/Graph.ts:94

Parameters:

Name	Type
backingObjects	T[]

Returns: number[]

---

isConnected

▸ isConnected(): boolean

Defined in src/modules/kyub.core.reinforcement/src/Graph.ts:175

Returns: boolean

---

isCut

▸ isCut(cutCandidate: number[]): boolean

Defined in src/modules/kyub.core.reinforcement/src/Graph.ts:187

Parameters:

Name	Type
cutCandidate	number[]

Returns: boolean

---

nodeCount

▸ nodeCount(): number

Defined in src/modules/kyub.core.reinforcement/src/Graph.ts:103

Returns: number

---

nodeCut

▸ nodeCut(maxSize: number): object

Defined in src/modules/kyub.core.reinforcement/src/Graph.ts:166

Finds a min node (!) cut with size up to maxSize This runs in O(V^maxSize * V). If you use this with maxSize > 2, you should be careful because this gets costly (Exponential runtime in the amount of nodes in the graph) There is a reduction to minimum (edge) cut problem but this is fast enough for maxSize <= 2 so there should not be need to do more here In case this gets to slow consider implementing Karger Stein here

Parameters:

Name	Type	Description
maxSize	number

Returns: object

• nodesInCut: number[]

• nodesInPartition1: number[]

• nodesInPartition2: number[]

---

nodesInComponent

▸ nodesInComponent(startNode: number): number[]

Defined in src/modules/kyub.core.reinforcement/src/Graph.ts:107

Parameters:

Name	Type
startNode	number

Returns: number[]

---

readdNodes

▸ readdNodes(nodes: number[]): void

Defined in src/modules/kyub.core.reinforcement/src/Graph.ts:183

Parameters:

Name	Type
nodes	number[]

Returns: void

---

removeNodes

▸ removeNodes(nodes: number[]): void

Defined in src/modules/kyub.core.reinforcement/src/Graph.ts:179

Parameters:

Name	Type
nodes	number[]

Returns: void

---

Static Private _permutation

▸ _permutation(array: number[], length: number): number[][]

Defined in src/modules/kyub.core.reinforcement/src/Graph.ts:52

Calculates all permutations of a given array with a fixed length The maximum length that is supported is 2

Parameters:

Name	Type
array	number[]
length	number

Returns: number[][]

---

Static fromJsGraph

▸ fromJsGraph‹U›(inputGraph: IJsgraph, backingObjects: U[]): Graph‹U›

Defined in src/modules/kyub.core.reinforcement/src/Graph.ts:17

Type parameters:

▪ U

Parameters:

Name	Type
inputGraph	IJsgraph
backingObjects	U[]

Returns: Graph‹U›