Search this API

y.algo
Class GraphChecker

java.lang.Object
  extended by y.algo.GraphChecker

public final class GraphChecker
extends java.lang.Object

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

Definitions

 

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:

 
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:

 
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:

 
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

© Copyright 2000-2022,
yWorks GmbH.
All rights reserved.