C

StarSubstructures

Show Usages
Detects SubstructureItems that represent isolated stars in the specified graph.
Inheritance Hierarchy

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 nodeTypes, 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.

Examples

Finding the stars in a graph
// prepare the star detection algorithm
const algorithm = new StarSubstructures()
// run the algorithm
const result = algorithm.run(graph)

// highlight the stars
for (const star of result.stars) {
  for (const node of star.nodes) {
    graph.setStyle(node, highlightNodeStyle)
  }
  for (const edge of star.edges) {
    graph.setStyle(edge, highlightEdgeStyle)
  }
}
Finding only the stars in a graph whose nodes are of the same type
// prepare the star detection algorithm
const algorithm = new StarSubstructures({
  // only nodes with the same tags can be a star
  nodeTypes: (node: INode): any => node.tag,
})
// run the algorithm
const result = algorithm.run(graph)

// highlight the stars
for (const star of result.stars) {
  for (const node of star.nodes) {
    graph.setStyle(node, highlightNodeStyle)
  }
  for (const edge of star.edges) {
    graph.setStyle(edge, highlightEdgeStyle)
  }
}

See Also

Developer's Guide

Members

No filters for this type

Constructors

StarSubstructures

()

Parameters

Properties

edgeDirectedness

: ItemMapping<IEdge, number>
Gets or sets a mapping that stores the directedness of the edges.
If a value is provided here, the algorithm only considers a substructure if all edges are either undirected or consistently directed with respect to the specified directedness.
  • the edge's directedness is greater than 0.0 and the edge is incoming (i.e. n is the edge's target),
  • the edge's directedness is smaller than 0.0 and the edge is outgoing (i.e. n is the edge's source),
  • or the edge's directedness is 0.0 (i.e. the edge is considered to be undirected).
conversionfinal

minimumSize

: number
Gets or sets the minimum size of a star.

Stars with fewer nodes are ignored.

Default is 2.

The smallest minimumSize value that could be considered is 2.
final

nodeTypes

: ItemMapping<INode, any>
Gets or sets a mapping which maps the type of each node.

An arbitrary object. Nodes returning equal objects are considered to be of the same type.

If none is provided, all nodes are considered as equal.

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

subgraphEdges

: ItemCollection<IEdge>
Gets or sets the collection of edges which define a subset of the graph for the algorithms to work on.

If nothing is set, all edges of the graph will be processed.

If only the excludes are set all edges in the graph except those provided in the excludes are processed.

Note that edges which start or end at nodes which are not in the subgraphNodes are automatically not considered by the algorithm.

ItemCollection<T> instances may be shared among algorithm instances and will be (re-)evaluated upon (re-)execution of the algorithm.

The edges provided here must be part of the graph which is passed to the run method.
conversionfinal

Examples

Finding the stars of a subset of the graph
// prepare the star detection algorithm
const algorithm = new StarSubstructures({
  // Ignore edges without target arrow heads
  subgraphEdges: {
    excludes: (edge: IEdge): boolean =>
      edge.style instanceof PolylineEdgeStyle &&
      edge.style.targetArrow instanceof Arrow &&
      edge.style.targetArrow.type === ArrowType.NONE,
  },
})
// run the algorithm
const result = algorithm.run(graph)

// highlight the stars
for (const star of result.stars) {
  for (const node of star.nodes) {
    graph.setStyle(node, highlightNodeStyle)
  }
  for (const edge of star.edges) {
    graph.setStyle(edge, highlightEdgeStyle)
  }
}

subgraphNodes

: ItemCollection<INode>
Gets or sets the collection of nodes which define a subset of the graph for the algorithms to work on.

If nothing is set, all nodes of the graph will be processed.

If only the excludes are set, all nodes in the graph except those provided in the excludes are processed.

ItemCollection<T> instances may be shared among algorithm instances and will be (re-)evaluated upon (re-)execution of the algorithm.

The nodes provided here must be part of the graph which is passed to the run method.
conversionfinal

Examples

Finding the stars of a subset of the graph
// prepare the star detection algorithm
const algorithm = new StarSubstructures({
  subgraphNodes: {
    // only consider elliptical nodes in the graph
    includes: (node: INode): boolean =>
      node.style instanceof ShapeNodeStyle &&
      node.style.shape === ShapeNodeShape.ELLIPSE,
    // but ignore the first node, regardless of its shape
    excludes: graph.nodes.first()!,
  },
})
// run the algorithm
const result = algorithm.run(graph)

// highlight the stars
for (const star of result.stars) {
  for (const node of star.nodes) {
    graph.setStyle(node, highlightNodeStyle)
  }
  for (const edge of star.edges) {
    graph.setStyle(edge, highlightEdgeStyle)
  }
}

Methods

run

(graph: IGraph): StarSubstructuresResult
Returns a list of SubstructureItems that represent isolated stars in the specified graph.

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 nodeTypes, a root may be associated with different stars. In this case, the algorithm only returns the largest star.

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

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.
A chain or star structure is also considered to be a tree.
If no edgeDirectedness is specified, all edges are treated as undirected. Furthermore, if no nodeTypes are specified, all nodes are considered to be of the same type.
The result obtained from this algorithm is a snapshot which is no longer valid once the graph has changed, e.g. by adding or removing nodes or edges.
final

Parameters

graph: IGraph
The graph to find the substructures in.

Return Value

StarSubstructuresResult
A list of SubstructureItems that represent the stars.

Throws

Exception ({ name: 'InvalidOperationError' })
If the algorithm can't create a valid result due to an invalid graph structure or wrongly configured properties.

Examples

Finding the stars in a graph
// prepare the star detection algorithm
const algorithm = new StarSubstructures()
// run the algorithm
const result = algorithm.run(graph)

// highlight the stars
for (const star of result.stars) {
  for (const node of star.nodes) {
    graph.setStyle(node, highlightNodeStyle)
  }
  for (const edge of star.edges) {
    graph.setStyle(edge, highlightEdgeStyle)
  }
}
Finding only the stars in a graph whose nodes are of the same type
// prepare the star detection algorithm
const algorithm = new StarSubstructures({
  // only nodes with the same tags can be a star
  nodeTypes: (node: INode): any => node.tag,
})
// run the algorithm
const result = algorithm.run(graph)

// highlight the stars
for (const star of result.stars) {
  for (const node of star.nodes) {
    graph.setStyle(node, highlightNodeStyle)
  }
  for (const edge of star.edges) {
    graph.setStyle(edge, highlightEdgeStyle)
  }
}