
Search this API  
PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 
java.lang.Object y.algo.GraphChecker
public final class GraphChecker
This class provides methods that check structural properties of a given graph.
v0, v1, v2, ... , vk
forms a
cycle if v0 = vk
and consists of at least one edge.
n
children.
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 selfloops. 
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 

public static boolean isAcyclic(Graph graph)
A graph is called acyclic if it contains no directed cycle.
public static boolean isCyclic(Graph graph)
A graph is called cyclic if it contains a directed cycle.
public static boolean isPlanar(Graph graph)
A graph is called planar if it can be drawn on the plane without edge crossings.
public static boolean isConnected(Graph graph)
A graph is called connected if there exists an undirected path of edges between every pair of nodes.
public static boolean isStronglyConnected(Graph graph)
A graph is called strongly connected if there exists a directed path between each pair of nodes.
public static boolean isBiconnected(Graph graph)
A graph is called biconnected if it has no cut vertex or articulation point, i.e., no node whose removal disconnects the graph.
public static boolean isBipartite(Graph graph)
A graph is called bipartite if its nodes can be partitioned into two sets such that each edge connects two nodes of different sets.
public static boolean isNaryTree(Graph graph, int n)
n
children.
public static boolean isRootedTree(Graph graph)
public static boolean isTree(Graph graph)
public static boolean isForest(Graph graph)
A graph is a forest if its connected components are trees.
public static boolean isSelfLoopFree(Graph graph)
!isSelfLoopFree(graph) => !isAcyclic(graph)
graph
 the given graph
true
if the graph contains no selfloops, false
otherwisepublic static boolean isSimple(Graph graph)
A graph is called simple if it contains no two distinct edges e1, e2
where
e1.source() == e2.source() && e1.target() == e2.target()
.
public static boolean isMultipleEdgeFree(Graph graph)
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.
public static double getAverageDegree(Graph graph, boolean directed)
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 graphs2 * graph.E() / graph.N()
for undirected graphs
graph
 the input graphdirected
 true
if the graph should be considered as directed, false
otherwise
public static double getAverageWeightedDegree(Graph graph, boolean directed, DataProvider edgeWeight)
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 graphs2 * edge_weight_sum / graph.N()
for undirected graphs
O(graph.E())
graph
 the input graphdirected
 true
if the graph should be considered as directed, false
otherwiseedgeWeight
 DataProvider
that provides the weights of the edges
public static double getDiameter(Graph graph, boolean directed, DataProvider edgeCost)
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.
graph
 the input graphdirected
 true
if the graph should be considered as directed, false
otherwiseedgeCost
 DataProvider
that provides the costs of the edges
public static double getDensity(Graph graph, boolean directed)
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 graphs2 * graph.E() / (graph.N() * (graph.N()  1))
for undirected simple graphs
graph
 the input graphdirected
 true
if the graph should be considered as directed, false
otherwise

© Copyright 20002022, yWorks GmbH. All rights reserved. 

PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 