C

Bipartition

Show Usages
Calculates a bipartition of the given graph, if one exists.
Inheritance Hierarchy

Remarks

A graph is bipartite if its nodes can be divided into two partitions where no edges are between nodes of the same partition. Instead, every edge connects a node from the first with a node from the second partition.

Other Graph Connectivity Algorithms

yFiles for HTML supports a number of other analysis algorithms that partition the graph into components, based on various criteria.

  • ConnectedComponents – Determines components defined by the existence of an undirected path between nodes
  • StronglyConnectedComponents – Determines components defined by the existence of a directed path between nodes
  • BiconnectedComponents – Determines components defined by the existence of at least two separate undirected paths between all nodes
  • IndependentSets – Divides a graph into partitions where no nodes are connected within a partition
  • KCoreComponents – Calculates the k-cores of an undirected input graph. The k-core of an undirected input graph consists of the subgraph components where each node has at least degree k.

Complexity

O(|V| + |E|)

Examples

Calculating the two partitions of a bipartite graph
// prepare the bipartition algorithm
const algorithm = new Bipartition()
// run the algorithm
const result = algorithm.run(graph)

// highlight the nodes of the partitions with different styles
if (result.isBipartite) {
  for (const node of result.firstPartition.nodes) {
    graph.setStyle(node, firstPartitionStyle)
  }
  for (const node of result.secondPartition.nodes) {
    graph.setStyle(node, secondPartitionStyle)
  }
}

See Also

Developer's Guide

API

bipartition

Members

No filters for this type

Constructors

Bipartition

()

Parameters

Properties

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 ItemCollection<TItem>.excludes are set, all edges in the graph except those provided in the ItemCollection<TItem>.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

Calculating a bipartition on a subset of the graph
// configure the bipartition algorithm
const algorithm = new Bipartition({
  // 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 nodes of the partitions with different styles
if (result.isBipartite) {
  for (const node of result.firstPartition.nodes) {
    graph.setStyle(node, firstPartitionStyle)
  }
  for (const node of result.secondPartition.nodes) {
    graph.setStyle(node, secondPartitionStyle)
  }
}

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 ItemCollection<TItem>.excludes are set, all nodes in the graph except those provided in the ItemCollection<TItem>.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

Calculating a bipartition on a subset of the graph
// configure the bipartition algorithm
const algorithm = new Bipartition({
  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 nodes of the partitions with different styles
if (result.isBipartite) {
  for (const node of result.firstPartition.nodes) {
    graph.setStyle(node, firstPartitionStyle)
  }
  for (const node of result.secondPartition.nodes) {
    graph.setStyle(node, secondPartitionStyle)
  }
}

Methods

run

(graph: IGraph): BipartitionResult
Calculates a bipartition of the given graph, if one exists.
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 input graph to run the algorithm on.

Return Value

BipartitionResult
A BipartitionResult containing both partitions of graph. If the graph is not bipartite, the resulting partitions are empty and BipartitionResult.isBipartite is false.

Throws

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

Complexity

O(|V| + |E|)