GraphChecker

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

Inheritance Hierarchy

GraphChecker

Remarks

Note: Methods of this class work with instances of Graph. To analyze structural properties of IGraph instances use GraphStructureAnalyzer instead.

Definitions

Cycle: An edge path with vertices v0, v1, v2, ... , vk forms a cycle if v0 = vk 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 graph: An acyclic graph, in which any pair of vertices is connected through a path. If one vertex of a tree is distinguished from the other vertices, then the tree is called rooted tree.
N-ary tree graph: A directed rooted tree where each node has a maximum of n children.
Forest graph: A graph whose connected components are trees.
Simple graph: A graph that contains no self-loops and parallel edges.
Planar graph: A graph that can be drawn on the plane without edge crossings.
Average degree: The number of edges in comparison to the number of nodes.
Average weighted degree: The sum of the edge weights in comparison to the number of nodes.
Diameter:The maximum eccentricity of any vertex in the graph i.e., the length of the longest shortest path between any two vertices.
Density: The ratio of edges of the graph to the maximum possible number of edges.

Type Details

yfiles module: algorithms
yfiles-umd modules: All layout modules, view-layout-bridge
Legacy UMD name: yfiles.algorithms.GraphChecker

Static Methods

getAverageDegree

(graph: Graph, directed: boolean) : number

Computes the average degree of a given graph.

Remarks

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

graph.E() / graph.N() for directed graphs
2 * graph.E() / graph.N() for undirected graphs

Parameters

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

graph - Graph: the input graph
directed - boolean: true if the graph should be considered as directed, false otherwise

Returns

↪number: the average degree of the given graph

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

getAverageWeightedDegree

(graph: Graph, directed: boolean, edgeWeight: IDataProvider) : number

Computes the average weighted degree of a given 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 / graph.N() for directed graphs
2 * edge_weight_sum / graph.N() for undirected graphs

Complexity

O(graph.E())

Parameters

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

graph - Graph

the input graph

directed - boolean

true if the graph should be considered as directed, false otherwise

edgeWeight - IDataProvider

IDataProvider that provides the weights of the edges

Domain	Edge
Values	number	the weight of an edge

Returns

↪number: the average weighted degree of the given graph

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

getDensity

(graph: Graph, directed: boolean) : number

Computes the density of a given simple graph.

Remarks

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

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

Parameters

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

graph - Graph: the input graph
directed - boolean: true if the graph should be considered as directed, false otherwise

Returns

↪number: the density of the given graph

This algorithm ignores self-loops and parallel edges.

getDiameter

(graph: Graph, directed: boolean, edgeCost: IDataProvider) : number

Computes the diameter of a given graph.

Remarks

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

Parameters

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

graph - Graph

the input graph

directed - boolean

true if the graph should be considered as directed, false otherwise

edgeCost - IDataProvider

IDataProvider that provides the costs of the edges

Domain	Edge
Values	number	the cost of an edge

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.

isAcyclic

(graph: Graph) : boolean

Checks whether or not the given directed graph is acyclic.

Remarks

Note: This method works with instances of Graph. To determine whether an IGraph is acyclic use isAcyclic instead.

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

Parameters

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

graph - Graph: the given graph

Returns

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

Sample Graphs

isAcyclic(graph) <=> !isCyclic(graph).

isBiconnected

(graph: Graph) : boolean

Checks whether or not the given undirected graph is biconnected.

Remarks

Note: This method works with instances of Graph. To determine whether an IGraph is biconnected use isBiconnected instead.

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

Parameters

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

graph - Graph: the given undirected graph

Returns

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

Sample Graphs

isBipartite

(graph: Graph) : boolean

Checks whether or not the given undirected graph is bipartite.

Remarks

Note: This method works with instances of Graph. To determine whether an IGraph is bipartite use isAcyclic instead.

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

Parameters

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

graph - Graph: the given undirected graph

Returns

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

Sample Graphs

isConnected

(graph: Graph) : boolean

Checks whether or not the given graph is connected.

Remarks

Note: This method works with instances of Graph. To determine whether an IGraph is connected use isConnected instead.

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

Parameters

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

graph - Graph: the given graph

Returns

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

Sample Graphs

isCyclic

(graph: Graph) : boolean

Checks whether or not the given directed graph is cyclic.

Remarks

Note: This method works with instances of Graph. To determine whether an IGraph is cyclic use isCyclic instead.

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

Parameters

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

graph - Graph: the given graph

Returns

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

Sample Graphs

isCyclic(graph) <=> !isAcyclic(graph).

isForest

(graph: Graph) : boolean

Checks whether the given graph is a forest.

Remarks

Note: This method works with instances of Graph. To determine whether an IGraph is a forest use isForest instead.

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

Parameters

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

graph - Graph: the given graph

Returns

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

Sample Graphs

isMultipleEdgeFree

(graph: Graph) : boolean

Checks whether or not the given undirected graph contains no multiple edges.

Remarks

Note: This method works with instances of Graph. To determine whether an IGraph has multiple edges use hasMultipleEdges instead.

The method returns true if the graph contains no two distinct edges e1, e2 that connect the same pairs of nodes in either direction.

Parameters

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

graph - Graph: the given undirected graph

Returns

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

Sample Graphs

isMultipleEdgeFree(graph) => isSimple(graph).

isNaryTree

(graph: Graph, n: number) : boolean

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

Remarks

Note: This method works with instances of Graph. To determine whether an IGraph is an n-ary tree use isNaryTree instead.

Parameters

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

graph - Graph: the given graph
n - number

Returns

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

Sample Graphs

isRootedTree

(graph: Graph) : boolean

Checks whether or not the given directed graph is a directed rooted tree.

Remarks

Note: This method works with instances of Graph. To determine whether an IGraph is a directed tree use isTree instead.

Parameters

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

graph - Graph: the given graph

Returns

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

Sample Graphs

isRootedTree(graph) => isTree(graph)

isSelfLoopFree

(graph: Graph) : boolean

Checks whether or not the given graph contains no self-loops.

Remarks

Note: This method works with instances of Graph. To determine whether an IGraph has self-loops use hasSelfLoops instead.

Parameters

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

graph - Graph: the given graph

Returns

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

!isSelfLoopFree(graph) => !isAcyclic(graph)

isSimple

(graph: Graph) : boolean

Checks whether or not the given directed graph is simple.

Remarks

Note: This method works with instances of Graph. To determine whether an IGraph is simple use isAcyclic instead.

A graph is called simple if it contains no two distinct edges e1, e2 where e1.source() == e2.source() && e1.target() == e2.target().

Parameters

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

graph - Graph: the given directed graph

Returns

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

Sample Graphs

isMultipleEdgeFree(graph) => isSimple(graph).

isStronglyConnected

(graph: Graph) : boolean

Checks whether or not the given directed graph is strongly connected.

Remarks

Note: This method works with instances of Graph. To determine whether an IGraph is strongly connected use isStronglyConnected instead.

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

Parameters

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

graph - Graph: the given directed graph

Returns

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

Sample Graphs

isTree

(graph: Graph) : boolean

Checks whether or not the given graph is an undirected tree.

Remarks

Note: This method works with instances of Graph. To determine whether an IGraph is an undirected tree use isTree instead.

Parameters

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

graph - Graph: the given graph

Returns

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

Sample Graphs

isRootedTree(graph) => isTree(graph)