C

GraphStructureAnalyzer

Show Usages
This class provides methods that check structural properties of a given graph.
Inheritance Hierarchy

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 multi-edges.
  • Planar graph – A graph that can be drawn on the plane without edge crossings.
  • Multi-Edges – Multi-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)

See Also

Developer's Guide

Members

No filters for this type

Constructors

GraphStructureAnalyzer

(graph: IGraph)
Creates a new instance for the given graph.

Parameters

graph: IGraph
The graph to provide analysis methods for.

Properties

subgraphEdges

: ItemCollection<IEdge>
Gets or sets the collection of edges which define an induced subgraph for the algorithms to work on.

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 that 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.

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

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()

subgraphNodes

: ItemCollection<INode>
Gets or sets the collection of nodes which define an induced subgraph for the algorithms to work on.

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.

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

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
algorithm.subgraphNodes = graphComponent.selection.nodes
Ignoring all group nodes
algorithm.subgraphNodes.excludes = (n) => graph.isGroupNode(n)
Considering selected nodes but ignoring group nodes
algorithm.subgraphNodes = graphComponent.selection.nodes
algorithm.subgraphNodes.excludes = (n) => graph.isGroupNode(n)

Methods

getAverageDegree

(directed?: boolean): number
Computes the average degree of the graph.
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
Multi-edges and self-loops are both included in the calculation. Graphs with edges at edges are not supported.
final

Parameters

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

Return Value

number
The average degree of the given graph.

Complexity

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

getAverageWeightedDegree

(edgeWeights: IMapper<IEdge, number>, directed?: boolean): number
Computes the average weighted degree of the graph.
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
Multi-edges and self-loops are both included in the calculation.
final

Parameters

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.

Return Value

number
The average weighted degree of the given graph

Complexity

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

getDensity

(directed?: boolean): number
Computes the density of the graph.
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
This algorithm ignores self-loops and multi-edges.
final

Parameters

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

Return Value

number
The density of the given graph.

getDiameter

(edgeCosts: IMapper<IEdge, number>, directed?: boolean): number
Computes the diameter of the graph.
The diameter is the maximum eccentricity of any node in the graph and equals the length of the longest of the shortest paths between any two nodes.
Multi-edges are also included in the calculation.
For the calculation, an algorithm that solves 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.
final

Parameters

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.

Return Value

number
The diameter of the given graph.

getMultiEdges

(directed?: boolean): IEnumerable<IEnumerable<IEdge>>
Determines the multi-edges of the directed or undirected graph.
Multi-edges connect the same two port owners.
final

Parameters

directed?: boolean
Whether to respect the direction of the edges.

Return Value

IEnumerable<IEnumerable<IEdge>>
A collection of multi-edges.

Throws

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

Complexity

O(|V| + |E|)

getMultiEdges

(node: INode, directed?: boolean): IEnumerable<IEnumerable<IEdge>>
Determines the multi-edges adjacent to the given node of the directed or undirected graph.
Multi-edges connect the same two port owners.
final

Parameters

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

Return Value

IEnumerable<IEnumerable<IEdge>>
A collection of multi-edges.

Throws

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

getMultiEdges

(edge: IEdge, directed?: boolean): IEnumerable<IEdge>
Determines the multi-edges between the source and target node of the given edge of the directed or undirected graph.
Multi-edges connect the same two port owners. The given edge is not part of the result.
final

Parameters

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.

Return Value

IEnumerable<IEdge>
The multi-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.
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.
final

Return Value

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

Complexity

O(|V| + |E|)

hasMultiEdges

(directed?: boolean): boolean
Determines whether the directed or undirected graph contains multi-edges.
Multi-edges connect the same two port owners.
final

Parameters

directed?: boolean
Whether to respect the direction of the edges.

Return Value

boolean
true if the graph contains multi-edges, false otherwise

Examples

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

Sample Graphs

ShownSetting: Directed graph with multi-edges

hasSelfLoops

(): boolean
Determines whether or not the graph has self-loops.
Self-loops connect a port owner with itself.
final

Return Value

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.
A directed (undirected) graph is called acyclic if it contains no directed (undirected) cycle.
final

Parameters

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

Return Value

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

ShownSetting: Acyclic graph (edge directions are considered)

See Also

API
isCyclic

isBiconnected

(): boolean
Determines whether or not the undirected graph is biconnected.
A graph is called biconnected if it has no cut vertex or articulation point, i.e., no node whose removal disconnects the graph.
final

Return Value

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

ShownSetting: Biconnected graph

isBipartite

(): boolean
Determines whether or not the undirected graph is bipartite.
A graph is called bipartite if its nodes can be partitioned into two sets such that each edge connects two nodes of different sets.
final

Return Value

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

ShownSetting: Bipartite graph. Circular and rectangular nodes represent the two sets.

isConnected

(): boolean
Determines whether or not the graph is connected.
A graph is called connected if there exists an undirected path of edges between every pair of nodes.
final

Return Value

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

ShownSetting: Connected graph

isCyclic

(directed?: boolean): boolean
Determines whether the graph is cyclic.
A directed (undirected) graph is called cyclic if it contains a directed (undirected) cycle.
final

Parameters

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

Return Value

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

ShownSetting: Acyclic graph (edge directions are considered)

See Also

API
isAcyclic

isForest

(directed?: boolean): boolean
Determines whether the graph is a directed (undirected) forest.
A graph is a forest if its connected components are trees.
final

Parameters

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

Return Value

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

ShownSetting: Forest graph

See Also

Developer's Guide

isNaryTree

(maxChildCount: number): boolean
Determines whether the graph is a directed rooted tree where each node has a maximum of maxChildCount children.
final

Parameters

maxChildCount: number
The maximum number of children allowed per node in the tree.

Return Value

boolean
true if the graph is a directed rooted tree where each node has at most maxChildCount 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

ShownSetting: N-ary tree graph with maximum 3 children

See Also

Developer's Guide

isPlanar

(): boolean
Determines whether or not the graph is planar.
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.
final

Return Value

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

ShownSetting: Planar graph

isSimple

(): boolean
Determines whether or not the given undirected graph is simple.

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.

final

Return Value

boolean
true if the graph is simple, false otherwise

Examples

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

Sample Graphs

ShownSetting: Non-simple graph

isStronglyConnected

(): boolean
Determines whether or not the directed graph is strongly connected.
A graph is called strongly connected if there exists a directed path between each pair of nodes.
final

Return Value

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

ShownSetting: Strongly connected graph

isTree

(directed?: boolean): boolean
Determines whether or not the graph is a directed (undirected) tree.
final

Parameters

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

Return Value

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)

Sample Graphs

ShownSetting: Rooted tree graph

See Also

Developer's Guide