GraphStructureAnalyzer

This class provides methods that check structural properties of a given graph.

Inheritance Hierarchy

GraphStructureAnalyzer

Remarks

Definitions

Cycle – An edge path with nodes n0, n1, n2, ... , nk forms a cycle if n0 = nk and consists of at least one edge.
Acyclic graph – A graph that contains no directed cycle.
Cyclic graph – A graph that contains a directed cycle.
Connected graph – A graph in which there exists an undirected path of edges between every pair of nodes.
Strongly connected graph – A graph in which there exists a directed path between each pair of nodes.
Biconnected graph – A graph that has no cut vertex or articulation point (i.e., a node whose removal disconnects the graph).
Bipartite graph – A graph whose nodes can be partitioned into two sets such that each edge connects two nodes of different sets.
Tree – A acyclic graph, in which any pair of nodes is connected through a path. If one node of a tree is distinguished from the other nodes, then the tree is called rooted tree.
N-ary tree – A directed rooted tree where each node has a maximum of n children.
Forest – A graph whose connected components are trees.
Simple graph – An undirected graph that contains no self-loops or parallel edges.
Planar graph – A graph that can be drawn on the plane without edge crossings.
Multiple Edges – Multiple edges are edges that are incident to the same two nodes.

subgraphNodes and subgraphEdges can be used to run the analysis on an induced subgraph, only. Note that the subgraph will be reevaluated for each analysis.

Examples

An instance of GraphStructureAnalyzer is valid for an IGraph instance.

const analyzer = new GraphStructureAnalyzer(graph)

Type Details

yfiles module: view-layout-bridge
yfiles-umd modules: view-layout-bridge
Legacy UMD name: yfiles.analysis.GraphStructureAnalyzer

Constructors

GraphStructureAnalyzer

(graph: IGraph)

Creates a new instance for the given graph.

ParametersOptions Overload

options - Object
A map of options to pass to the method.

graph - IGraph: The graph to provide analysis methods for.
subgraphNodes - ItemCollection<INode>: The collection of nodes which define an induced subgraph for the algorithms to work on. This option sets the subgraphNodes property on the created object.
subgraphEdges - ItemCollection<IEdge>: The collection of edges which define an induced subgraph for the algorithms to work on. This option sets the subgraphEdges property on the created object.

Properties

subgraphEdges

: ItemCollection<IEdge>

Gets or sets the collection of edges which define an induced subgraph for the algorithms to work on.

Remarks

If nothing is set, all edges of the graph will be considered.

If only the excludes are set all edges in the graph except those provided in the excludes are processed.

Note that edges which start or end at nodes which are not in the subgraphNodes are automatically not considered by the algorithms.

ItemCollection<T> instances may be shared among algorithm instances and will be (re-)evaluated upon (re-)execution of the algorithms.

Examples

Determining connectedness on a subset of the graph

const isConnectedViaBlueEdges = new GraphStructureAnalyzer({
  graph,
  subgraphEdges: {
    delegate: (edge) =>
      edge.style instanceof PolylineEdgeStyle &&
      edge.style.stroke === Stroke.BLUE
  }
}).isConnected()

The edges provided here must be part of the graph which was set in the GraphStructureAnalyzer constructor.

subgraphNodes

: ItemCollection<INode>

Gets or sets the collection of nodes which define an induced subgraph for the algorithms to work on.

Remarks

If nothing is set, all nodes of the graph will be considered.

If only the excludes are set all nodes in the graph except those provided in the excludes are processed.

ItemCollection<T> instances may be shared among algorithm instances and will be (re-)evaluated upon (re-)execution of the algorithms.

Examples

Determining the average degree of nodes on a subgraph.

const averageDegreeOfLabeledSubgraph = new GraphStructureAnalyzer({
  graph,
  subgraphNodes: { delegate: (node) => node.labels.size > 0 }
}).getAverageDegree()

Considering only selected nodes

const subset = new ItemCollection(
  graphComponent.selection.selectedNodes
)

Ignoring all group nodes

const subset = new ItemCollection()
subset.excludes = (n) => graph.isGroupNode(n)const subset = new ItemCollection<INode>()
subset.excludes = (n) => graph.isGroupNode(n)

Considering selected nodes but ignoring group nodes

const subset = new ItemCollection(
  graphComponent.selection.selectedNodes,
  (n) => graph.isGroupNode(n)
)

The nodes provided here must be part of the graph which was set in the GraphStructureAnalyzer constructor.

Methods

getAverageDegree

(directed?: boolean) : number

Computes the average degree of the graph.

Remarks

The average degree measures the number of edges in comparison to the number of nodes and is defined as:

|E| / |V| for directed graphs
2 * |E| / |V| for undirected graphs

Complexity

O(1), O(|V| + |E|) when subgraph filtering is enabled.

Parameters

options - Object
A map of options to pass to the method.

directed - boolean: Whether or not to respect the direction of the edges.

Returns

↪number: The average degree of the given graph.

Parallel edges and self-loops are both included in the calculation. Graphs with edges at edges are not supported.

getAverageWeightedDegree

(edgeWeights: IMapper<IEdge,number>, directed?: boolean) : number

Computes the average weighted degree of the graph.

Remarks

The average weighted degree measures the sum of the edge weights in comparison to the number of nodes and is defined as:

edge_weight_sum / |V| for directed graphs
2 * edge_weight_sum / |V| for undirected graphs

Complexity

O(|E|), O(|V| + |E|) when subgraph filtering is enabled

Parameters

options - Object
A map of options to pass to the method.

edgeWeights - IMapper<IEdge,number>: The mapping that provides the weights of the edges.
directed - boolean: Whether or not to respect the direction of the edges.

Returns

↪number: The average weighted degree of the given graph

Parallel edges and self-loops are both included in the calculation.

getDensity

(directed?: boolean) : number

Computes the density of the graph.

Remarks

The density is the ratio of edges of the graph to the maximum possible number of edges and equals to:

|E| / (|N| * (|N| - 1)) for directed simple graphs
2 * |E| / (|N| * (|N| - 1)) for undirected simple graphs

Parameters

options - Object
A map of options to pass to the method.

directed - boolean: Whether or not to respect the direction of the edges.

Returns

↪number: The density of the given graph.

This algorithm ignores self-loops and parallel edges.

getDiameter

(edgeCosts: IMapper<IEdge,number>, directed?: boolean) : number

Computes the diameter of the graph.

Remarks

The diameter is the maximum eccentricity of any node in the graph and equals to the length of the longest of the shortest path between any two nodes.

Parameters

options - Object
A map of options to pass to the method.

edgeCosts - IMapper<IEdge,number>: The mapping that provides the costs of the edges.
directed - boolean: Whether or not to respect the direction of the edges.

Returns

↪number: The diameter of the given graph.

Parallel edges are also included in the calculation.

For the calculation, an algorithm that solved the all-pairs shortest path problem is used. Depending on the structure of the given graph and the values of the given edge costs, the algorithm internally delegates its work to the algorithm with the theoretically best running time. Please note that theory does not necessarily reflect practice.

getMultipleEdges

(directed?: boolean) : IEnumerable<IEnumerable<IEdge>>

Determines the multiple edges of the directed or undirected graph.

Remarks

Multiple edges connect the same two port owners.

Complexity

O(|V| + |E|)

Parameters

options - Object
A map of options to pass to the method.

directed - boolean: Whether or not to respect the direction of the edges.

Returns

↪IEnumerable<IEnumerable<IEdge>>: A collection of multiple edges.

Throws

Exception({ name: 'InvalidOperationError' }): If the graph has edge to edge connections.

getMultipleEdges

(node: INode, directed?: boolean) : IEnumerable<IEnumerable<IEdge>>

Determines the multiple edges adjacent to the given node of the directed or undirected graph.

Remarks

Multiple edges connect the same two port owners.

Parameters

options - Object
A map of options to pass to the method.

node - INode: The node that is adjacent to the multiple edge to determine.
directed - boolean: Whether or not to respect the direction of the edges.

Returns

↪IEnumerable<IEnumerable<IEdge>>: A collection of multiple edges.

Throws

Exception({ name: 'InvalidOperationError' }): If the graph has edge to edge connections.

getMultipleEdges

(edge: IEdge, directed?: boolean) : IEnumerable<IEdge>

Determines the multiple edges between the source and target node of the given edge of the directed or undirected graph.

Remarks

Multiple edges connect the same two port owners. The given edge ist not part of the result.

Parameters

options - Object
A map of options to pass to the method.

edge - IEdge: The edge with the same source and target as the edges to determine.
directed - boolean: Whether or not to respect the direction of the edges.

Returns

↪IEnumerable<IEdge>: The multiple edges.

Throws

Exception({ name: 'InvalidOperationError' }): If the graph has edge to edge connections.

getTopologicalOrder

() : IEnumerable<INode>

Gets the nodes of the graph in topological order.

Remarks

A topological ordering of the nodes of a directed acyclic graph is a linear ordering of the nodes such that for each directed edge (u, v), the node u lies before v in the ordering.

Complexity

O(|V| + |E|)

Preconditions

The graph must be .

Returns

↪IEnumerable<INode>: The nodes of the graph in topological order.

hasMultipleEdges

(directed?: boolean) : boolean

Determines whether or not the directed or undirected graph contains multiple edges.

Remarks

Multiple edges connect the same two port owners.

Returns

↪boolean: true if the graph contains multiple edges, false otherwise

Examples

const isMultipleEdgeFree = new GraphStructureAnalyzer(graph).isSimple()

Sample Graphs

hasSelfLoops

() : boolean

Determines whether or not the graph has self-loops.

Remarks

Self-loops connect a port owner with itself.

Returns

↪boolean: true if the graph contains self-loops, false otherwise

Examples

const hasSelfLoops = new GraphStructureAnalyzer(graph).hasSelfLoops()

isAcyclic

(directed?: boolean) : boolean

Determines whether the graph is acyclic.

Remarks

A directed (undirected) graph is called acyclic if it contains no directed (undirected) cycle.

Parameters

options - Object
A map of options to pass to the method.

directed - boolean: Whether or not to respect the direction of the edges.

Returns

↪boolean: true if the graph is acyclic, false, otherwise

Throws

Exception({ name: 'InvalidOperationError' }): If the graph has edge to edge connections.

Examples

const isAcyclic = new GraphStructureAnalyzer(graph).isAcyclic(true)

Sample Graphs

isBiconnected

() : boolean

Determines whether or not the undirected graph is biconnected.

Remarks

A graph is called biconnected if it has no cut vertex or articulation point, i.e., no node whose removal disconnects the graph.

Returns

↪boolean: true if the graph is biconnected, false otherwise

Throws

Exception({ name: 'InvalidOperationError' }): If the graph has edge to edge connections.

Examples

const isBiconnected = new GraphStructureAnalyzer(graph).isBiconnected()

Sample Graphs

isBipartite

() : boolean

Determines whether or not the undirected graph is bipartite.

Remarks

A graph is called bipartite if its nodes can be partitioned into two sets such that each edge connects two nodes of different sets.

Returns

↪boolean: true if the graph is bipartite, false otherwise

Throws

Exception({ name: 'InvalidOperationError' }): If the graph has edge to edge connections.

Examples

const isBipartite = new GraphStructureAnalyzer(graph).isBipartite()

Sample Graphs

isConnected

() : boolean

Determines whether or not the graph is connected.

Remarks

A graph is called connected if there exists an undirected path of edges between every pair of nodes.

Returns

↪boolean: true if the graph is connected, false otherwise

Throws

Exception({ name: 'InvalidOperationError' }): If the graph has edge to edge connections.

Examples

const isConnected = new GraphStructureAnalyzer(graph).isConnected()

Sample Graphs

isCyclic

(directed?: boolean) : boolean

Determines whether the graph is cyclic.

Remarks

A directed (undirected) graph is called cyclic if it contains a directed (undirected) cycle.

Parameters

options - Object
A map of options to pass to the method.

directed - boolean: Whether or not to respect the direction of the edges.

Returns

↪boolean: true if the graph is cyclic, false, otherwise

Throws

Exception({ name: 'InvalidOperationError' }): If the graph has edge to edge connections.

Examples

const isCyclic = new GraphStructureAnalyzer(graph).isCyclic(true)

Sample Graphs

isForest

(directed?: boolean) : boolean

Determines whether the graph is a directed (undirected) forest.

Remarks

A graph is a forest if its connected components are trees.

Parameters

options - Object
A map of options to pass to the method.

directed - boolean: Whether or not to respect the direction of the edges.

Returns

↪boolean: true if the graph is a forest, false otherwise

Throws

Exception({ name: 'InvalidOperationError' }): If the graph has edge to edge connections.

Examples

const isForest = new GraphStructureAnalyzer(graph).isForest(true)

Sample Graphs

isNaryTree

(n: number) : boolean

Determines whether or not the graph is a directed rooted tree where each node has a maximum of n children.

Returns

↪boolean: true if the graph is a directed rooted tree where each node has at most n children, false otherwise

Throws

Exception({ name: 'InvalidOperationError' }): If the graph has edge to edge connections.

Examples

const isNaryTree = new GraphStructureAnalyzer(graph).isNaryTree(3)

Sample Graphs

isPlanar

() : boolean

Determines whether or not the graph is planar.

Remarks

A graph is called planar if it can be drawn on the plane without edge crossings. Note that this is a property of the graph, not necessarily of the drawing, so the graph can still have crossing edges, despite being a planar graph.

Returns

↪boolean: true if the graph is planar, false, otherwise.

Throws

Exception({ name: 'InvalidOperationError' }): If the graph has edge to edge connections.

Examples

const isPlanar = new GraphStructureAnalyzer(graph).isPlanar()

Sample Graphs

isSimple

() : boolean

Determines whether or not the given undirected graph is simple.

Remarks

An undirected graph is called simple if there are no two edges that connect the same nodes as well as no self-loops.

Since an IGraph can have edges ending at other edges, a graph containing those constructs will also not be simple.

Returns

↪boolean: true if the graph is simple, false otherwise

Examples

const isSimple = new GraphStructureAnalyzer(graph).isSimple()

Sample Graphs

isStronglyConnected

() : boolean

Determines whether or not the directed graph is strongly connected.

Remarks

A graph is called strongly connected if there exists a directed path between each pair of nodes.

Returns

↪boolean: true if the graph is strongly connected, false, otherwise

Throws

Exception({ name: 'InvalidOperationError' }): If the graph has edge to edge connections.

Examples

const isStronglyConnected = new GraphStructureAnalyzer(
  graph
).isStronglyConnected()

Sample Graphs

isTree

(directed?: boolean) : boolean

Determines whether or not the graph is a directed (undirected) tree.

Parameters

options - Object
A map of options to pass to the method.

directed - boolean: Whether or not to respect the direction of the edges.

Returns

↪boolean: true if the graph is a tree, false otherwise

Throws

Exception({ name: 'InvalidOperationError' }): If the graph has edge to edge connections.

Examples

const isTree = new GraphStructureAnalyzer(graph).isTree(false)

GraphStructureAnalyzer

Remarks

Definitions

Examples

Type Details

See Also

Constructors

GraphStructureAnalyzer

ParametersOptions Overload

Properties

subgraphEdges

Remarks

Examples

subgraphNodes

Remarks

Examples

Methods

getAverageDegree

Remarks

Complexity

Parameters

Returns

getAverageWeightedDegree

Remarks

Complexity

Parameters

Returns

getDensity

Remarks

Parameters

Returns

getDiameter

Remarks

Parameters

Returns

getMultipleEdges

Remarks

Complexity

Parameters

Returns

Throws

getMultipleEdges

Remarks

Parameters

Returns

Throws

getMultipleEdges

Remarks

Parameters

Returns

Throws

getTopologicalOrder

Remarks

Complexity

Preconditions

Returns

hasMultipleEdges

Remarks

Returns

Examples

Sample Graphs

hasSelfLoops

Remarks

Returns

Examples

isAcyclic

Remarks

Parameters

Returns

Throws

Examples

See Also

Sample Graphs

isBiconnected

Remarks

Returns

Throws

Examples

Sample Graphs

isBipartite