Search this API

y.algo Class GraphChecker

```java.lang.Object
y.algo.GraphChecker
```

`public final class GraphCheckerextends java.lang.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.
• 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.

Method Summary
`static double` ```getAverageDegree(Graph graph, boolean directed)```
Computes the average degree of a given graph.
`static double` ```getAverageWeightedDegree(Graph graph, boolean directed, DataProvider edgeWeight)```
Computes the average weighted degree of a given graph.
`static double` ```getDensity(Graph graph, boolean directed)```
Computes the density of a given simple graph.
`static double` ```getDiameter(Graph graph, boolean directed, DataProvider edgeCost)```
Computes the diameter of a given graph.
`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 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
Sample Graphs:
 Acyclic graph (edge directions are considered) Cyclic graph. Marked edges form a directed cycle.

isCyclic

`public static 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
Sample Graphs:
 Acyclic graph (edge directions are considered) Cyclic graph. Marked edges form a directed cycle.

isPlanar

`public static 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.
Sample Graphs:
 Planar graph Non-planar graph `K3,3`

isConnected

`public static 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
Sample Graphs:
 Connected graph Non-connected graph

isStronglyConnected

`public static 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
Sample Graphs:
 Strongly connected graph Non-strongly connected graph

isBiconnected

`public static 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
Sample Graphs:
 Biconnected graph Non-biconnected graph

isBipartite

`public static 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
Sample Graph:
 Bipartite graph. Circular and rectangular nodes represent the two sets.

isNaryTree

```public 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.

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
Sample Graph:
 N-ary tree graph with maximum `3` children

isRootedTree

`public static 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
Sample Graph:
 Rooted tree graph

isTree

`public static 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
Sample Graph:
 Tree graph

isForest

`public static 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
Sample Graph:
 Forest graph

isSelfLoopFree

`public static 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 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
Sample Graphs:
 Non-simple graph Simple graph

isMultipleEdgeFree

`public static 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
Sample Graphs:
 Mon-multiple edge free graph Multiple edge free graph

getAverageDegree

```public static double getAverageDegree(Graph graph,
boolean directed)```
Computes the average degree of a given graph.

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

Parallel edges and self-loops are both included in the calculation.
Parameters:
`graph` - the input graph
`directed` - `true` if the graph should be considered as directed, `false` otherwise
Returns:
the average degree of the given graph

getAverageWeightedDegree

```public static double getAverageWeightedDegree(Graph graph,
boolean directed,
DataProvider edgeWeight)```
Computes the average weighted degree of a given 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 / graph.N()` for directed graphs
• `2 * edge_weight_sum / graph.N()` for undirected graphs
• .

Parallel edges and self-loops are both included in the calculation.
Complexity:
`O(graph.E())`
Parameters:
`graph` - the input graph
`directed` - `true` if the graph should be considered as directed, `false` otherwise
`edgeWeight` - `DataProvider` that provides the weights of the edges
Returns:
the average weighted degree of the given graph

getDiameter

```public static double getDiameter(Graph graph,
boolean directed,
DataProvider edgeCost)```
Computes the diameter of a given graph.

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.

Parallel edges are also included in the calculation.
Parameters:
`graph` - the input graph
`directed` - `true` if the graph should be considered as directed, `false` otherwise
`edgeCost` - `DataProvider` that provides the costs of the edges
Returns:
the diameter of the given graph

getDensity

```public static double getDensity(Graph graph,
boolean directed)```
Computes the density of a given simple graph.

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
• , or
• `2 * graph.E() / (graph.N() * (graph.N() - 1))` for undirected simple graphs
• .

This algorithm ignores self-loops and parallel edges.
Parameters:
`graph` - the input graph
`directed` - `true` if the graph should be considered as directed, `false` otherwise
Returns:
the density of the given graph