com.yworks.yfiles.algorithms

Class GraphChecker

java.lang.Object

com.yworks.yfiles.algorithms.GraphChecker

public final class GraphChecker
extends Object

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

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.

Method Summary

Modifier and Type	Method and Description
static boolean	isAcyclic(Graph graph) Checks whether or not the given directed graph is acyclic.
static boolean	isBiconnected(Graph graph) Checks whether or not the given undirected graph is biconnected.
static boolean	isBipartite(Graph graph) Checks whether or not the given undirected graph is bipartite.
static boolean	isConnected(Graph graph) Checks whether or not the given graph is connected.
static boolean	isCyclic(Graph graph) Checks whether or not the given directed graph is cyclic.
static boolean	isForest(Graph graph) Checks whether the given graph is a forest.
static boolean	isMultipleEdgeFree(Graph graph) Checks whether or not the given undirected graph contains no multiple edges.
static boolean	isNaryTree(Graph graph, int n) Checks whether or not the given graph is a directed rooted tree where each node has a maximum of n children.
static boolean	isPlanar(Graph graph) Checks whether or not the given graph is planar.
static boolean	isRootedTree(Graph graph) Checks whether or not the given directed graph is a directed rooted tree.
static boolean	isSelfLoopFree(Graph graph) Checks whether or not the given graph contains no self-loops.
static boolean	isSimple(Graph graph) Checks whether or not the given directed graph is simple.
static boolean	isStronglyConnected(Graph graph) Checks whether or not the given directed graph is strongly connected.
static boolean	isTree(Graph graph) Checks whether or not the given graph is an undirected tree.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Detail

isAcyclic

public static final boolean isAcyclic(Graph graph)

Checks whether or not the given directed graph is acyclic.

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

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

Parameters:

graph - the given graph

Returns:

true if the graph is acyclic, false, otherwise

isBiconnected

public static final boolean isBiconnected(Graph graph)

Checks whether or not the given 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.

Parameters:

graph - the given undirected graph

Returns:

true if the graph is biconnected, false otherwise

isBipartite

public static final boolean isBipartite(Graph graph)

Checks whether or not the given 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.

Parameters:

graph - the given undirected graph

Returns:

true if the graph is bipartite, false otherwise

isConnected

public static final boolean isConnected(Graph graph)

Checks whether or not the given graph is connected.

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

Parameters:

graph - the given graph

Returns:

true if the graph is connected, false otherwise

isCyclic

public static final boolean isCyclic(Graph graph)

Checks whether or not the given directed graph is cyclic.

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

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

Parameters:

graph - the given graph

Returns:

true if the graph is cyclic, false, otherwise

isForest

public static final boolean isForest(Graph graph)

Checks whether the given graph is a forest.

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

Parameters:

graph - the given graph

Returns:

true if the graph is a forest, false otherwise

isMultipleEdgeFree

public static final boolean isMultipleEdgeFree(Graph graph)

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

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

isMultipleEdgeFree(graph) => isSimple(graph).

Parameters:

graph - the given undirected graph

Returns:

true if the graph contains no multiple edges, false otherwise

isNaryTree

public static final boolean isNaryTree(Graph graph,
                                       int n)

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

Parameters:

graph - the given graph

Returns:

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

isPlanar

public static final boolean isPlanar(Graph graph)

Checks whether or not the given graph is planar.

A graph is called planar if it can be drawn on the plane without edge crossings.

Parameters:

graph - the given graph

Returns:

true if the graph is planar, false, otherwise.

isRootedTree

public static final boolean isRootedTree(Graph graph)

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

isRootedTree(graph) => isTree(graph)

Parameters:

graph - the given graph

Returns:

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

isSelfLoopFree

public static final boolean isSelfLoopFree(Graph graph)

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

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

Parameters:

graph - the given graph

Returns:

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

isSimple

public static final boolean isSimple(Graph graph)

Checks whether or not the given directed graph is simple.

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

isMultipleEdgeFree(graph) => isSimple(graph).

Parameters:

graph - the given directed graph

Returns:

true if the graph is simple, false otherwise

isStronglyConnected

public static final boolean isStronglyConnected(Graph graph)

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

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

Parameters:

graph - the given directed graph

Returns:

true if the graph is strongly connected, false, otherwise

isTree

public static final boolean isTree(Graph graph)

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

isRootedTree(graph) => isTree(graph)

Parameters:

graph - the given graph

Returns:

true if the graph is an undirected tree, false otherwise