
Search this API  
PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 
java.lang.Object y.algo.Substructures
public class Substructures
This class allows to detect different substructures within the input graph, for example, tree, star, chain and cycle structures.
Method Summary  

static java.util.List 
getChains(Graph graph,
int minimumSize)
Returns a list of Substructure s that represent the undirected chains in the specified graph with at least
minimumSize nodes. 
static java.util.List 
getChains(Graph graph,
int minimumSize,
DataProvider nodeType,
DataProvider edgeDirectedness)
Returns a list of Substructure s that represent the chains in the specified graph with at least
minimumSize nodes. 
static java.util.List 
getCliques(Graph graph,
int minimumSize)
Returns a list of Substructure s that represent the (undirected) cliques in the specified graph with at
least minimumSize nodes. 
static java.util.List 
getCliques(Graph graph,
int minimumSize,
DataProvider nodeType)
Returns a list of Substructure s that represent the (undirected) cliques in the specified graph with at
least minimumSize nodes. 
static java.util.List 
getCycles(Graph graph,
int minimumSize)
Returns a list of Substructure s that represent the undirected cycles in the specified graph with at least
minimumSize nodes. 
static java.util.List 
getCycles(Graph graph,
int minimumSize,
DataProvider nodeType,
DataProvider edgeDirectedness)
Returns a list of Substructure s that represent the cycles in the specified graph with at least
minimumSize nodes. 
static java.util.List 
getStars(Graph graph,
int minimumSize)
Returns a list of Substructure s that represent the undirected stars in the specified graph with at least
minimumSize nodes. 
static java.util.List 
getStars(Graph graph,
int minimumSize,
DataProvider nodeType,
DataProvider edgeDirectedness)
Returns a list of Substructure s that represent the stars in the specified graph with at least
minimumSize nodes. 
static java.util.List 
getTrees(Graph graph,
int minimumSize)
Returns a list of Substructure s that represent the undirected trees in the specified graph with at least
minimumSize nodes. 
static java.util.List 
getTrees(Graph graph,
int minimumSize,
DataProvider nodeType,
DataProvider edgeDirectedness)
Returns a list of Substructure s that represent the trees in the specified graph with at least
minimumSize nodes. 
Methods inherited from class java.lang.Object 

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

public static java.util.List getCliques(Graph graph, int minimumSize)
Substructure
s that represent the (undirected) cliques in the specified graph with at
least minimumSize
nodes.
A clique is a subset of nodes that are all adjacent (i.e., connected) to each other.
Note that finding a maximum clique is NPhard. Hence, we only use a simple heuristic approach that doesn't guarantee to find all/the largest clique. It only identifies cliques that have at least one node with at most one nonclique neighbor. Furthermore, a node can only be contained in a single clique, i.e., the returned cliques are nonoverlapping.
minimumSize
value that could be considered is 3
.graph
 the input graphminimumSize
 the minimum size of a clique (cliques with less nodes are ignored)
Substructure
s that represent the cliquespublic static java.util.List getCliques(Graph graph, int minimumSize, DataProvider nodeType)
Substructure
s that represent the (undirected) cliques in the specified graph with at
least minimumSize
nodes. A clique is a subset of nodes of the same type (see nodeType
)
that are all adjacent (i.e., connected) to each other.
Note that finding a maximum clique is NPhard. Hence, we only use a simple heuristic approach that doesn't guarantee to find all/the largest clique. It only identifies cliques that have at least one node with at most one nonclique neighbor. Furthermore, a node can only be contained in a single clique, i.e., the returned cliques are nonoverlapping.
nodeType
, i.e., nodes associated
with equal objects. If no nodeType
is specified, all node are considered to be of the same type.graph
 the input graphminimumSize
 the minimum size of a clique (cliques with less nodes are ignored)nodeType
 the type of each node (nodes returning equal objects are considered to be of the same type)
Substructure
s that represent the cliquespublic static java.util.List getTrees(Graph graph, int minimumSize)
Substructure
s that represent the undirected trees in the specified graph with at least
minimumSize
nodes.
The chosen root
of a subtree is the only node which may have nontree edges.
minimumSize
value that could be considered is 3
.graph
 the input graphminimumSize
 the minimum size of a tree (trees with less nodes are ignored)
Substructure
s that represent the subtreespublic static java.util.List getTrees(Graph graph, int minimumSize, DataProvider nodeType, DataProvider edgeDirectedness)
Substructure
s that represent the trees in the specified graph with at least
minimumSize
nodes.
The root
of a subtree is the only node which may have nontree edges. Furthermore, a subtree only
consists of elements with the same nodeType
.
The edgeDirectedness
is considered as follows:
A substructure is only identified as such if all edges are either undirected or consistently directed with
respect to the specified directedness.
1
indicates that the edge is considered to be
directed from source to target.
1
indicates that the edge is considered to be
directed from target to source.
0
indicates that the edge is considered to be
undirected.
minimumSize
value that could be considered is 3
.graph
 the input graphminimumSize
 the minimum size of a tree (trees with less nodes are ignored)nodeType
 the type of each node (nodes returning equal objects are considered to be of the same type)edgeDirectedness
 the directedness of each edge
Substructure
s that represent the subtreespublic static java.util.List getStars(Graph graph, int minimumSize)
Substructure
s that represent the undirected stars in the specified graph with at least
minimumSize
nodes.
A star consists of a root
that is connected to multiple nodes with degree one.
minimumSize
value that could be considered is 2
.graph
 the input graphminimumSize
 the minimum number of degree one nodes of a star (stars with less nodes are ignored)
Substructure
s that represent the starspublic static java.util.List getStars(Graph graph, int minimumSize, DataProvider nodeType, DataProvider edgeDirectedness)
Substructure
s that represent the stars in the specified graph with at least
minimumSize
nodes.
A star consists of a root
that is connected to multiple nodes with degree one.
Since a star only consists of elements with the same edgeDirectedness
and nodeType
, a root may be associated with different
stars. In this case, the algorithm only returns the largest star.
The edgeDirectedness
is considered as follows:
A substructure is only identified as such if all edges are either undirected or consistently directed with
respect to the specified directedness.
1
indicates that the edge is considered to be
directed from source to target.
1
indicates that the edge is considered to be
directed from target to source.
0
indicates that the edge is considered to be
undirected.
minimumSize
value that could be considered is 2
.graph
 the input graphminimumSize
 the minimum number of degree one nodes of a star (stars with less nodes are ignored)nodeType
 the type of each node (nodes returning equal objects are considered to be of the same type)edgeDirectedness
 the directedness of each edge
Substructure
s that represent the starspublic static java.util.List getCycles(Graph graph, int minimumSize)
Substructure
s that represent the undirected cycles in the specified graph with at least
minimumSize
nodes.
A cycle is a simple edge path in which the first and last nodes are identical. The algorithm only considers cycles in which at most one edge connects a cycle node with the rest of the graph (i.e. isolated cycles that are connected with one edge).
minimumSize
value that could be considered is 3
.graph
 the input graphminimumSize
 the minimum number of nodes of a cycle (cycles with less nodes are ignored)
Substructure
s that represent the cyclespublic static java.util.List getCycles(Graph graph, int minimumSize, DataProvider nodeType, DataProvider edgeDirectedness)
Substructure
s that represent the cycles in the specified graph with at least
minimumSize
nodes.
A cycle is a simple edge path in which the first and last nodes are identical. The algorithm only considers
cycles in which at most one edge connects a cycle node with the rest of the graph (i.e. isolated cycles that are
connected with one edge). Furthermore, a cycle only consists of elements with the same edgeDirectedness
and nodeType
.
The edgeDirectedness
is considered as follows:
A substructure is only identified as such if all edges are either undirected or consistently directed with
respect to the specified directedness.
1
indicates that the edge is considered to be
directed from source to target.
1
indicates that the edge is considered to be
directed from target to source.
0
indicates that the edge is considered to be
undirected.
minimumSize
value that could be considered is 3
.graph
 the input graphminimumSize
 the minimum number of nodes of a cycle (cycles with less nodes are ignored)nodeType
 the type of each node (nodes returning equal objects are considered to be of the same type)edgeDirectedness
 the directedness of each edge
Substructure
s that represent the cyclespublic static java.util.List getChains(Graph graph, int minimumSize)
Substructure
s that represent the undirected chains in the specified graph with at least
minimumSize
nodes.
minimumSize
value that could be considered is 3
.graph
 the input graphminimumSize
 the minimum number of nodes of a chain (chains with less nodes are ignored)
Substructure
s that represent the chainspublic static java.util.List getChains(Graph graph, int minimumSize, DataProvider nodeType, DataProvider edgeDirectedness)
Substructure
s that represent the chains in the specified graph with at least
minimumSize
nodes.
A chain only consists of elements with the same edgeDirectedness
and nodeType
.
More precisely, the edgeDirectedness
is considered as follows:
A substructure is only identified as such if all edges are either undirected or consistently directed with
respect to the specified directedness.
1
indicates that the edge is considered to be
directed from source to target.
1
indicates that the edge is considered to be
directed from target to source.
0
indicates that the edge is considered to be
undirected.
minimumSize
value that could be considered is 3
.graph
 the input graphminimumSize
 the minimum number of nodes of a chain (chains with less nodes are ignored)nodeType
 the type of each node (nodes returning equal objects are considered to be of the same type)edgeDirectedness
 the directedness of each edge
Substructure
s that represent the chains

© Copyright 20002022, yWorks GmbH. All rights reserved. 

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