y.algo
Class GraphChecker

java.lang.Object
  y.algo.GraphChecker

public final class GraphChecker
extends 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