Skip to content

Latest commit

 

History

History
1798 lines (1067 loc) · 33.2 KB

Graph.md

File metadata and controls

1798 lines (1067 loc) · 33.2 KB

@antv/graphlib / Exports / Graph

Class: Graph<N, E>

Type parameters

Name Type
N extends PlainObject
E extends PlainObject

Hierarchy

  • default

    ↳ Graph

Table of contents

Constructors

Properties

EdgeMethods

NodeMethods

TreeMethods

Methods

Constructors

constructor

• new Graph<N, E>(options?)

Create a new Graph instance.

Type parameters

Name Type
N extends PlainObject
E extends PlainObject

Parameters

Name Type Description
options? GraphOptions<N, E> The options to initialize a graph. See GraphOptions. ts const graph = new Graph({ // Optional, initial nodes. nodes: [ // Each node has a unique ID. { id: 'A', foo: 1 }, { id: 'B', foo: 1 }, ], // Optional, initial edges. edges: [ { id: 'C', source: 'B', target: 'B', weight: 1 }, ], // Optional, called with a GraphChangedEvent. onChanged: (event) => { console.log(event); } });

Overrides

EventEmitter.constructor

Defined in

src/graph.ts:65

Properties

batchCount

• Private batchCount: number = 0

Defined in

src/graph.ts:31

bothEdgesMap

• Private bothEdgesMap: Map<ID, Set<Edge<E>>>

Defined in

src/graph.ts:27

changes

• Private changes: GraphChange<N, E>[] = []

Defined in

src/graph.ts:30

edgeMap

• Private edgeMap: Map<ID, Edge<E>>

Defined in

src/graph.ts:24

inEdgesMap

• Private inEdgesMap: Map<ID, Set<Edge<E>>>

Defined in

src/graph.ts:25

nodeMap

• Private nodeMap: Map<ID, Node<N>>

Defined in

src/graph.ts:23

onChanged

• onChanged: (event: GraphChangedEvent<N, E>) => void

Type declaration

▸ (event): void

This function is called with a GraphChangedEvent each time a graph change happened.

event.changes contains all the graph changes in order since last onChanged.

Parameters
Name Type
event GraphChangedEvent<N, E>
Returns

void

Defined in

src/graph.ts:38

outEdgesMap

• Private outEdgesMap: Map<ID, Set<Edge<E>>>

Defined in

src/graph.ts:26

treeIndices

• Private treeIndices: TreeIndices<Node<N>>

Defined in

src/graph.ts:28

EdgeMethods

addEdge

▸ addEdge(edge): void

Add a single edge pointing from source to target into the graph.

graph.addNode({ id: 'NodeA' });
graph.addNode({ id: 'NodeB' });
graph.addEdge({ id: 'EdgeA', source: 'NodeA', target: 'NodeB' });

If source or target were not found in the current graph, it throws an Error.

Parameters

Name Type
edge Edge<E>

Returns

void

Defined in

src/graph.ts:600

addEdges

▸ addEdges(edges): void

Add all edges of the given iterable(an array, a set, etc.) into the graph.

Parameters

Name Type
edges Iterable<Edge<E>>

Returns

void

Defined in

src/graph.ts:580

getEdge

▸ getEdge(id): Edge<E>

Get the edge data with given ID.

Parameters

Name Type
id ID

Returns

Edge<E>

Defined in

src/graph.ts:534

getEdgeDetail

▸ getEdgeDetail(id): Object

Get the edge, the source node, and the target node by an edge ID.

Parameters

Name Type
id ID

Returns

Object

Name Type
edge Edge<E>
source Node<N>
target Node<N>

Defined in

src/graph.ts:543

mergeEdgeData

▸ mergeEdgeData(id, patch): void

Parameters

Name Type
id ID
patch Partial<E>

Returns

void

Defined in

src/graph.ts:774

removeEdge

▸ removeEdge(id): void

Remove a single edge of the given id.

Parameters

Name Type
id ID

Returns

void

Defined in

src/graph.ts:632

removeEdges

▸ removeEdges(idList): void

Remove edges whose id was included in the given id list.

Parameters

Name Type
idList ID[]

Returns

void

Defined in

src/graph.ts:622

updateEdgeData

▸ updateEdgeData(id, data): void

Update edge data. This will replace the whole data object.

updateEdgeData(id, data); // Works like `edge.data = data`

Parameters

Name Type
id ID
data E

Returns

void

Defined in

src/graph.ts:715

▸ updateEdgeData<P>(id, propertyName, value): void

Update a single property on the edge data.

To update multiple properties, you could batch several updates or use mergeNodeData.

updateEdgeData(id, key, value); // Works like `edge.data[key] = value`

Type parameters

Name Type
P extends string | number | symbol

Parameters

Name Type
id ID
propertyName P
value E[P]

Returns

void

Defined in

src/graph.ts:727

▸ updateEdgeData(id, update): void

Update edge data by a update function.

updateEdgeData(id, oldData => newData);

Parameters

Name Type
id ID
update (data: E) => E

Returns

void

Defined in

src/graph.ts:740

updateEdgeSource

▸ updateEdgeSource(id, source): void

Change the source of an edge. The source must be found in current graph.

Parameters

Name Type
id ID
source ID

Returns

void

Defined in

src/graph.ts:640

updateEdgeTarget

▸ updateEdgeTarget(id, target): void

Change the target of an edge. The target must be found in current graph.

Parameters

Name Type
id ID
target ID

Returns

void

Defined in

src/graph.ts:665

NodeMethods

addNode

▸ addNode(node): void

Add a single node into the graph.

Parameters

Name Type
node Node<N>

Returns

void

Defined in

src/graph.ts:380

addNodes

▸ addNodes(nodes): void

Add all nodes of the given array, or iterable, into the graph.

Parameters

Name Type
nodes Iterable<Node<N>>

Returns

void

Defined in

src/graph.ts:368

areNeighbors

▸ areNeighbors(firstNodeId, secondNodeId): boolean

Tell if two nodes are neighbors.

Parameters

Name Type
firstNodeId ID
secondNodeId ID

Returns

boolean

Defined in

src/graph.ts:274

getDegree

▸ getDegree(id, direction?): number

Get the degree of the given node.

Parameters

Name Type
id ID
direction? "in" | "out" | "both"

Returns

number

Defined in

src/graph.ts:317

getNeighbors

▸ getNeighbors(id): Node<N>[]

Given a node ID, find its neighbors.

Parameters

Name Type Description
id ID ID of the node

Returns

Node<N>[]

Defined in

src/graph.ts:344

getNode

▸ getNode(id): Node<N>

Get the node data with given ID.

Parameters

Name Type
id ID

Returns

Node<N>

Defined in

src/graph.ts:284

getRelatedEdges

▸ getRelatedEdges(id, direction?): Edge<E>[]

Given a node ID, find all edges of the node.

Parameters

Name Type Description
id ID ID of the node
direction? "in" | "out" | "both" Edge direction, defaults to 'both'.

Returns

Edge<E>[]

Defined in

src/graph.ts:298

hasEdge

▸ hasEdge(id): boolean

Check if an edge exists in the graph.

Parameters

Name Type
id ID

Returns

boolean

Defined in

src/graph.ts:526

hasNode

▸ hasNode(id): boolean

Check if a node exists in the graph.

Parameters

Name Type
id ID

Returns

boolean

Defined in

src/graph.ts:266

removeNode

▸ removeNode(id): void

Remove a single node and its attached edges from the graph.

Parameters

Name Type
id ID

Returns

void

Defined in

src/graph.ts:413

removeNodes

▸ removeNodes(idList): void

Remove nodes and their attached edges from the graph.

Parameters

Name Type
idList ID[]

Returns

void

Defined in

src/graph.ts:403

updateNodeData

▸ updateNodeData(id, data): void

Update node data. This will replace the whole data object.

updateNodeData(id, data); // Works like `node.data = data`

Parameters

Name Type
id ID
data N

Returns

void

Defined in

src/graph.ts:459

▸ updateNodeData<P>(id, propertyName, value): void

Update a single property on the node data.

To update multiple properties, you could batch several updates or use mergeNodeData.

updateNodeData(id, key, value); // Works like `node.data[key] = value`

Type parameters

Name Type
P extends string | number | symbol

Parameters

Name Type
id ID
propertyName P
value N[P]

Returns

void

Defined in

src/graph.ts:471

▸ updateNodeData(id, update): void

Update node data by a update function.

updateNodeData(id, oldData => newData);

Parameters

Name Type
id ID
update (data: N) => N

Returns

void

Defined in

src/graph.ts:484

TreeMethods

addTree

▸ addTree(tree, treeKey?): void

Traverse the given tree data, add each node into the graph, then attach the tree structure.

graph.addTree({
  id: 1,
  children: [
    { id: 2 },
    { id: 3 },
  ],
}, 'Inheritance');
graph.getRoots('Inheritance'); // [1]
graph.getChildren(1, 'Inheritance'); // [2, 3]
graph.getAllNodes(); // [1, 2, 3]
graph.getAllEdges(); // []

Parameters

Name Type
tree TreeData<N> | TreeData<N>[]
treeKey? string

Returns

void

Defined in

src/graph.ts:864

attachTreeStructure

▸ attachTreeStructure(treeKey?): void

Attach a new tree structure representing the hierarchy of all nodes in the graph.

Parameters

Name Type Description
treeKey? string A unique key of the tree structure. You can attach multiple tree structures with different keys. ts const graph = new Graph({ nodes: [{ id: 1 }, { id: 2 }, { id: 3 }], }); graph.attachTreeStructure('Inheritance'); graph.setParent(2, 1, 'Inheritance'); graph.setParent(3, 1, 'Inheritance'); graph.getRoots('Inheritance'); // [1] graph.getChildren(1, 'Inheritance'); // [2,3]

Returns

void

Defined in

src/graph.ts:809

detachTreeStructure

▸ detachTreeStructure(treeKey?): void

Detach the tree structure of the given tree key from the graph.

graph.detachTreeStructure('Inheritance');
graph.getRoots('Inheritance'); // Error!

Parameters

Name Type
treeKey? string

Returns

void

Defined in

src/graph.ts:835

getChildren

▸ getChildren(id, treeKey?): Node<N>[]

Given a node ID and an optional tree key, get the children of the node in the specified tree structure.

Parameters

Name Type
id ID
treeKey? string

Returns

Node<N>[]

Defined in

src/graph.ts:957

getParent

▸ getParent(id, treeKey?): null | Node<N>

Given a node ID and an optional tree key, get the parent of the node in the specified tree structure. If the given node is one of the tree roots, this returns null.

Parameters

Name Type
id ID
treeKey? string

Returns

null | Node<N>

Defined in

src/graph.ts:970

getRoots

▸ getRoots(treeKey?): Node<N>[]

Get the root nodes of an attached tree structure.

Consider a graph with the following tree structure attached:

Tree structure:
   O     3
  / \    |
 1   2   4

graph.getRoots() takes all nodes without a parent, therefore [0, 3] was returned.

Newly added nodes are also unparented. So they are counted as roots.

graph.addNode({ id: 5 });
graph.getRoots(); // [0, 3, 5]

Here is how the tree structure looks like:

Tree structure:
   O     3  5
  / \    |
 1   2   4

By setting a parent, a root node no more be a root.

graph.setParent(5, 2);
graph.getRoots(); // [0, 3]

The tree structure now becomes:

Tree structure:
   O     3
  / \    |
 1   2   4
     |
     5

Removing a node forces its children to be unparented, or roots.

graph.removeNode(0);
graph.getRoots(); // [1, 2, 3]

You might draw the the structure as follow:

Tree structure:
 1   2  3
     |  |
     5  4

Parameters

Name Type
treeKey? string

Returns

Node<N>[]

Defined in

src/graph.ts:946

setParent

▸ setParent(id, parent, treeKey?): void

Set node parent. If this operation causes a circle, it fails with an error.

Parameters

Name Type Description
id ID ID of the child node.
parent ID ID of the parent node.
treeKey? string Which tree structure the relation is applied to.

Returns

void

Defined in

src/graph.ts:999

Methods

batch

▸ batch(fn): void

Batch several graph changes into one.

Make several changes, but dispatch only one ChangedEvent at the end of batch:

graph.batch(() => {
  graph.addNodes([]);
  graph.addEdges([]);
});

Batches can be nested. Only the outermost batch will dispatch a ChangedEvent:

graph.batch(() => {
  graph.addNodes([]);
  graph.batch(() => {
    graph.addEdges([]);
  });
});

Parameters

Name Type
fn () => void

Returns

void

Defined in

src/graph.ts:95

bfs

▸ bfs(id, fn, direction?): boolean

Parameters

Name Type Default value
id ID undefined
fn (node: Node<N>) => boolean | void undefined
direction "in" | "out" | "both" 'out'

Returns

boolean

Defined in

src/graph.ts:1057

bfsTree

▸ bfsTree(id, fn, treeKey?): boolean

Parameters

Name Type
id ID
fn (node: Node<N>) => boolean | void
treeKey? string

Returns

boolean

Defined in

src/graph.ts:1037

checkEdgeExistence

▸ Private checkEdgeExistence(id): void

Parameters

Name Type
id ID

Returns

void

Defined in

src/graph.ts:516

checkNodeExistence

▸ Private checkNodeExistence(id): void

Parameters

Name Type
id ID

Returns

void

Defined in

src/graph.ts:258

checkTreeExistence

▸ Private checkTreeExistence(treeKey): void

Parameters

Name Type
treeKey undefined | string

Returns

void

Defined in

src/graph.ts:783

clone

▸ clone(): Graph<N, E>

Returns

Graph<N, E>

Defined in

src/graph.ts:1083

commit

▸ Private commit(): void

Reset changes and dispatch a ChangedEvent.

Returns

void

Defined in

src/graph.ts:107

createView

▸ createView(options): GraphView<N, E>

Parameters

Name Type
options Omit<GraphViewOptions<N, E>, "graph">

Returns

GraphView<N, E>

Defined in

src/graph.ts:1132

dfs

▸ dfs(id, fn, direction?): boolean

Parameters

Name Type Default value
id ID undefined
fn (node: Node<N>) => boolean | void undefined
direction "in" | "out" | "both" 'out'

Returns

boolean

Defined in

src/graph.ts:1070

dfsTree

▸ dfsTree(id, fn, treeKey?): boolean

Parameters

Name Type
id ID
fn (node: Node<N>) => boolean | void
treeKey? string

Returns

boolean

Defined in

src/graph.ts:1032

doAddEdge

▸ Private doAddEdge(edge): void

Parameters

Name Type
edge Edge<E>

Returns

void

Defined in

src/graph.ts:556

doAddNode

▸ Private doAddNode(node): void

Parameters

Name Type
node Node<N>

Returns

void

Defined in

src/graph.ts:350

doRemoveEdge

▸ Private doRemoveEdge(id): void

Parameters

Name Type
id ID

Returns

void

Defined in

src/graph.ts:604

doRemoveNode

▸ Private doRemoveNode(id): void

Parameters

Name Type
id ID

Returns

void

Defined in

src/graph.ts:384

emit

▸ emit(evt, ...args): void

触发一个事件

Parameters

Name Type
evt string
...args any[]

Returns

void

Inherited from

EventEmitter.emit

Defined in

node_modules/_@[email protected]@@antv/event-emitter/lib/index.d.ts:25

getAllEdges

▸ getAllEdges(): Edge<E>[]

Get all edges in the graph as an array.

Returns

Edge<E>[]

Defined in

src/graph.ts:1053

getAllNodes

▸ getAllNodes(): Node<N>[]

Get all nodes in the graph as an array.

Returns

Node<N>[]

Defined in

src/graph.ts:1046

getAncestors

▸ getAncestors(id, treeKey?): Node<N>[]

Returns an array of all the ancestor nodes, staring from the parent to the root.

Parameters

Name Type
id ID
treeKey? string

Returns

Node<N>[]

Defined in

src/graph.ts:980

getEvents

▸ getEvents(): Record<string, EventType[]>

Returns

Record<string, EventType[]>

Inherited from

EventEmitter.getEvents

Defined in

node_modules/_@[email protected]@@antv/event-emitter/lib/index.d.ts:32

getPredecessors

▸ getPredecessors(id): Node<N>[]

Get all predecessors of the given node.

Parameters

Name Type
id ID

Returns

Node<N>[]

Defined in

src/graph.ts:333

getSuccessors

▸ getSuccessors(id): Node<N>[]

Get all successors of the given node.

Parameters

Name Type
id ID

Returns

Node<N>[]

Defined in

src/graph.ts:324

hasTreeStructure

▸ hasTreeStructure(treeKey): boolean

Parameters

Name Type
treeKey undefined | string

Returns

boolean

Defined in

src/graph.ts:789

mergeNodeData

▸ mergeNodeData(id, patch): void

Like Object.assign, merge all properties of path to the node data.

Parameters

Name Type Description
id ID Node ID.
patch Partial<N> A data object to merge.

Returns

void

Defined in

src/graph.ts:442

off

▸ off(evt?, callback?): Graph<N, E>

取消监听一个事件，或者一个channel

Parameters

Name Type
evt? string
callback? Function

Returns

Graph<N, E>

Inherited from

EventEmitter.off

Defined in

node_modules/_@[email protected]@@antv/event-emitter/lib/index.d.ts:31

on

▸ on(evt, callback, once?): Graph<N, E>

监听一个事件

Parameters

Name Type
evt string
callback Function
once? boolean

Returns

Graph<N, E>

Inherited from

EventEmitter.on

Defined in

node_modules/_@[email protected]@@antv/event-emitter/lib/index.d.ts:13

once

▸ once(evt, callback): Graph<N, E>

监听一个事件一次

Parameters

Name Type
evt string
callback Function

Returns

Graph<N, E>

Inherited from

EventEmitter.once

Defined in

node_modules/_@[email protected]@@antv/event-emitter/lib/index.d.ts:19

reduceChanges

▸ reduceChanges(changes): GraphChange<N, E>[]

Reduce the number of ordered graph changes by dropping or merging unnecessary changes.

For example, if we update a node and remove it in a batch:

graph.batch(() => {
  graph.updateNodeData('A', 'foo', 2);
  graph.removeNode('A');
});

We get 2 atomic graph changes like

[
  { type: 'NodeDataUpdated', id: 'A', propertyName: 'foo', oldValue: 1, newValue: 2 },
  { type: 'NodeRemoved', value: { id: 'A', data: { foo: 2 } },
]

Since node 'A' has been removed, we actually have no need to handle with NodeDataUpdated change.

reduceChanges() here helps us remove such changes.

Parameters

Name Type
changes GraphChange<N, E>[]

Returns

GraphChange<N, E>[]

Defined in

src/graph.ts:143

toJSON

▸ toJSON(): string

Returns

string

Defined in

src/graph.ts:1124

updateEdgeDataProperty

▸ Private updateEdgeDataProperty<P>(id, propertyName, value): void

Type parameters

Name Type
P extends string | number | symbol

Parameters

Name Type
id ID
propertyName P
value E[P]

Returns

void

Defined in

src/graph.ts:686

updateNodeDataProperty

▸ Private updateNodeDataProperty<P>(id, propertyName, value): void

Type parameters

Name Type
P extends string | number | symbol

Parameters

Name Type
id ID
propertyName P
value N[P]

Returns

void

Defined in

src/graph.ts:417