This class allows to detect different substructures within the input graph, for example, tree, star, chain and cycle structures.
Type Details
- yfiles module
- algorithms
- yfiles-umd modules
- All layout modules, view-layout-bridge
- Legacy UMD name
- yfiles.algorithms.Substructures
Static Methods
getChains
(graph: Graph, minimumSize: number, nodeType?: IDataProvider, edgeDirectedness?: IDataProvider) : IList<any>Returns a list of Substructures that represent the chains in the specified graph with at least minimumSize nodes.
Remarks
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
1indicates that the edge is considered to be directed from source to target. - A directedness value of
-1indicates that the edge is considered to be directed from target to source. - A directedness value of
0indicates that the edge is considered to be undirected.
Parameters
A map of options to pass to the method.
- graph - Graph
- the input graph
- minimumSize - number
- the minimum number of nodes of a chain (chains with less nodes are ignored)
- nodeType - IDataProvider
- the type of each node (nodes returning equal objects are considered to be of the same type). If none is provided, all nodes are considered to be of the same type
Domain YNode Values Object the type of each node - edgeDirectedness - IDataProvider
- the directedness of each edge
Domain Edge Values number the directedness of each edge
Returns
- ↪IList<any>
- a list of Substructures that represent the chains
minimumSize value that could be considered is 3.edgeDirectedness is specified, all edges are treated as undirected. Furthermore, if no nodeType is specified, all node are considered to be of the same type.Returns a list of Substructures that represent the (undirected) cliques in the specified graph with at least minimumSize nodes.
Remarks
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.
Parameters
A map of options to pass to the method.
- graph - Graph
- the input graph
- minimumSize - number
- the minimum size of a clique (cliques with less nodes are ignored)
- nodeType - IDataProvider
- the type of each node (nodes returning equal objects are considered to be of the same type). If none is provided, all nodes are considered to be of the same type
Domain YNode Values Object the type of each node
Returns
- ↪IList<any>
- a list of Substructures that represent the cliques
nodeType, i.e., nodes associated with equal objects. If no nodeType is specified, all node are considered to be of the same type.minimumSize value that could be considered is 3.getCycles
(graph: Graph, minimumSize: number, nodeType?: IDataProvider, edgeDirectedness?: IDataProvider) : IList<any>Returns a list of Substructures that represent the cycles in the specified graph with at least minimumSize nodes.
Remarks
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
1indicates that the edge is considered to be directed from source to target. - A directedness value of
-1indicates that the edge is considered to be directed from target to source. - A directedness value of
0indicates that the edge is considered to be undirected.
Parameters
A map of options to pass to the method.
- graph - Graph
- the input graph
- minimumSize - number
- the minimum number of nodes of a cycle (cycles with less nodes are ignored)
- nodeType - IDataProvider
- the type of each node (nodes returning equal objects are considered to be of the same type). If none is provided, all nodes are considered to be of the same type
Domain YNode Values Object the type of each node - edgeDirectedness - IDataProvider
- the directedness of each edge
Domain Edge Values number the directedness of each edge
Returns
- ↪IList<any>
- a list of Substructures that represent the cycles
minimumSize value that could be considered is 3.edgeDirectedness is specified, all edges are treated as undirected. Furthermore, if no nodeType is specified, all node are considered to be of the same type.getStars
(graph: Graph, minimumSize: number, nodeType?: IDataProvider, edgeDirectedness?: IDataProvider) : IList<any>Returns a list of Substructures that represent the stars in the specified graph with at least minimumSize nodes.
Remarks
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
1indicates that the edge is considered to be directed from source to target. - A directedness value of
-1indicates that the edge is considered to be directed from target to source. - A directedness value of
0indicates that the edge is considered to be undirected.
Parameters
A map of options to pass to the method.
- graph - Graph
- the input graph
- minimumSize - number
- the minimum number of degree one nodes of a star (stars with less nodes are ignored)
- nodeType - IDataProvider
- the type of each node (nodes returning equal objects are considered to be of the same type). If none is provided, all nodes are considered to be of the same type
Domain YNode Values Object the type of each node - edgeDirectedness - IDataProvider
- the directedness of each edge
Domain Edge Values number the directedness of each edge
Returns
- ↪IList<any>
- a list of Substructures that represent the stars
minimumSize value that could be considered is 2.edgeDirectedness is specified, all edges are treated as undirected. Furthermore, if no nodeType is specified, all node are considered to be of the same type.getTrees
(graph: Graph, minimumSize: number, nodeType?: IDataProvider, edgeDirectedness?: IDataProvider) : IList<any>Returns a list of Substructures that represent the trees in the specified graph with at least minimumSize nodes.
Remarks
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
1indicates that the edge is considered to be directed from source to target. - A directedness value of
-1indicates that the edge is considered to be directed from target to source. - A directedness value of
0indicates that the edge is considered to be undirected.
Parameters
A map of options to pass to the method.
- graph - Graph
- the input graph
- minimumSize - number
- the minimum size of a tree (trees with less nodes are ignored)
- nodeType - IDataProvider
- the type of each node (nodes returning equal objects are considered to be of the same type). If none is provided, all nodes are considered to be of the same type
Domain YNode Values Object the type of each node - edgeDirectedness - IDataProvider
- the directedness of each edge
Domain Edge Values number the directedness of each edge
Returns
- ↪IList<any>
- a list of Substructures that represent the subtrees
minimumSize value that could be considered is 3.edgeDirectedness is specified, all edges are treated as undirected. Furthermore, if no nodeType is specified, all node are considered to be of the same type.