y.algo
Class Substructures

java.lang.Object
  y.algo.Substructures

public class Substructures
extends java.lang.Object

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 Substructures 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 Substructures 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 Substructures 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 Substructures 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 Substructures 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 Substructures 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 Substructures 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 Substructures 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 Substructures 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 Substructures 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

getCliques

public static java.util.List getCliques(Graph graph,
                                        int minimumSize)

Returns a list of Substructures 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 NP-hard. 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 non-clique neighbor. Furthermore, a node can only be contained in a single clique, i.e., the returned cliques are non-overlapping.

The smallest minimumSize value that could be considered is 3.

Parameters:

graph - the input graph

minimumSize - the minimum size of a clique (cliques with less nodes are ignored)

Returns:

a list of Substructures that represent the cliques

getCliques

public static java.util.List getCliques(Graph graph,
                                        int minimumSize,
                                        DataProvider nodeType)

Returns a list of Substructures 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 NP-hard. 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 non-clique neighbor. Furthermore, a node can only be contained in a single clique, i.e., the returned cliques are non-overlapping.

A clique only consists of elements with the same nodeType, i.e., nodes associated with equal objects. If no nodeType is specified, all node are considered to be of the same type.

Parameters:

graph - the input graph

minimumSize - 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)

Returns:

a list of Substructures that represent the cliques

getTrees

public static java.util.List getTrees(Graph graph,
                                      int minimumSize)

Returns a list of Substructures 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 non-tree edges.

The smallest minimumSize value that could be considered is 3.

Parameters:

graph - the input graph

minimumSize - the minimum size of a tree (trees with less nodes are ignored)

Returns:

a list of Substructures that represent the subtrees

getTrees

public static java.util.List getTrees(Graph graph,
                                      int minimumSize,
                                      DataProvider nodeType,
                                      DataProvider edgeDirectedness)

Returns a list of Substructures 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 non-tree 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.

• A directedness value of 1 indicates that the edge is considered to be directed from source to target.
• A directedness value of -1 indicates that the edge is considered to be directed from target to source.
• A directedness value of 0 indicates that the edge is considered to be undirected.

The smallest minimumSize value that could be considered is 3.

Parameters:

graph - the input graph

minimumSize - 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

Returns:

a list of Substructures that represent the subtrees

getStars

public static java.util.List getStars(Graph graph,
                                      int minimumSize)

Returns a list of Substructures 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.

The smallest minimumSize value that could be considered is 2.

Parameters:

graph - the input graph

minimumSize - the minimum number of degree one nodes of a star (stars with less nodes are ignored)

Returns:

a list of Substructures that represent the stars

getStars

public static java.util.List getStars(Graph graph,
                                      int minimumSize,
                                      DataProvider nodeType,
                                      DataProvider edgeDirectedness)

Returns a list of Substructures 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.

• A directedness value of 1 indicates that the edge is considered to be directed from source to target.
• A directedness value of -1 indicates that the edge is considered to be directed from target to source.
• A directedness value of 0 indicates that the edge is considered to be undirected.

The smallest minimumSize value that could be considered is 2.

Parameters:

graph - the input graph

minimumSize - 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

Returns:

a list of Substructures that represent the stars

getCycles

public static java.util.List getCycles(Graph graph,
                                       int minimumSize)

Returns a list of Substructures 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).

The smallest minimumSize value that could be considered is 3.

Parameters:

graph - the input graph

minimumSize - the minimum number of nodes of a cycle (cycles with less nodes are ignored)

Returns:

a list of Substructures that represent the cycles

getCycles

public static java.util.List getCycles(Graph graph,
                                       int minimumSize,
                                       DataProvider nodeType,
                                       DataProvider edgeDirectedness)

Returns a list of Substructures 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.

• A directedness value of 1 indicates that the edge is considered to be directed from source to target.
• A directedness value of -1 indicates that the edge is considered to be directed from target to source.
• A directedness value of 0 indicates that the edge is considered to be undirected.

The smallest minimumSize value that could be considered is 3.

Parameters:

graph - the input graph

minimumSize - 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

Returns:

a list of Substructures that represent the cycles

getChains

public static java.util.List getChains(Graph graph,
                                       int minimumSize)

Returns a list of Substructures that represent the undirected chains in the specified graph with at least minimumSize nodes.

The smallest minimumSize value that could be considered is 3.

Parameters:

graph - the input graph

minimumSize - the minimum number of nodes of a chain (chains with less nodes are ignored)

Returns:

a list of Substructures that represent the chains

getChains

public static java.util.List getChains(Graph graph,
                                       int minimumSize,
                                       DataProvider nodeType,
                                       DataProvider edgeDirectedness)

Returns a list of Substructures 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.

• A directedness value of 1 indicates that the edge is considered to be directed from source to target.
• A directedness value of -1 indicates that the edge is considered to be directed from target to source.
• A directedness value of 0 indicates that the edge is considered to be undirected.

The smallest minimumSize value that could be considered is 3.

Parameters:

graph - the input graph

minimumSize - 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

Returns:

a list of Substructures that represent the chains