Dulmage-Mendelsohn-Decomposition. More...

#include <ogdf/graphalg/PlanarSeparatorModule.h>

Inheritance diagram for ogdf::planar_separators::DMDecomposer:

Public Member Functions
bool	apply (const Graph &G, List< node > &separator, List< node > &first, List< node > &second) override
	Applies the postprocessor to a given separation.

std::string	getName () const override
	Returns the human-readable identifier of this postprocessor.

Public Member Functions inherited from ogdf::planar_separators::Postprocessor
	Postprocessor ()

virtual	~Postprocessor ()

Private Member Functions
bool	alternatingBFS (const Graph &G, const List< node > &startNodes, List< node > &reachableSep, List< node > &reachableB)
	Performs an alternating breadth first search to find all nodes in the separator that are reachable, and all those in the larger component B that are reachable.

void	bipartiteGraph (Graph &graph, const List< node > &separator)
	Creates a bipartite graph from the nodes in the separator and those in the bigger component.

void	calculateRemainders (const Graph &graph)
	Calculates the subset SR and BR once SI / SX and BI / BX have been found.

void	chooseBalancedDecomposition (const Graph &G, List< node > &separator, List< node > &first, List< node > &second)
	Given the subsets SI / SX / SR and BI / BX / BR, creates a separator with minimal size so that the two components are as balanced as possible.

void	decompose (const Graph &graph, const List< node > &bipart, List< node > &reachableSep, List< node > &reachableB)
	Given all nodes in the bipartite graph, selects starting points for the BFS and finds the reachable nodes in the separator and in B.

void	reset ()
	Resets the component so it can be reused.

void	setupAssignments (const Graph &G, const List< node > &separator, const List< node > &first, const List< node > &second)
	Fills a the NodeArray `assignments` with the values 0, 1 and 2 to represent the assignments of nodes to the separator / first / second component, respectively.

void	translateAssignments (const Graph &G, List< node > &separator, List< node > &first, List< node > &second) const
	Translates the assignments stored in the NodeArray assignments back to the lists, which can then be returned.

Private Attributes
NodeArray< short >	assignments

List< node >	BI

List< node >	bipartB

List< node >	bipartSep

List< node >	BR

List< node >	BX

NodeArray< node >	clone

EdgeArray< bool >	flow

NodeArray< bool >	isInS

List< node >	SI

List< node >	SR

List< node >	SX

NodeArray< node >	unclone

Detailed Description

Dulmage-Mendelsohn-Decomposition.

Improves a separation by creating a bipartite graph out of the separator and the larger of the two components, finding a maximal matching in this graph, and combining certain subsets of the two components to form a new separator in a way that is provably optimal.

Definition at line 413 of file PlanarSeparatorModule.h.

Member Function Documentation

◆ alternatingBFS()

bool ogdf::planar_separators::DMDecomposer::alternatingBFS	(	const Graph &	G,
		const List< node > &	startNodes,
		List< node > &	reachableSep,
		List< node > &	reachableB
	)

private

Performs an alternating breadth first search to find all nodes in the separator that are reachable, and all those in the larger component B that are reachable.

Parameters

G	the graph
startNodes	starting points for the BFS
reachableSep	nodes in the separator that could be reached
reachableB	nodes in component B that could be reached

Returns: true if everything worked

◆ apply()

bool ogdf::planar_separators::DMDecomposer::apply	(	const Graph &	G,
		List< node > &	separator,
		List< node > &	first,
		List< node > &	second
	)

overridevirtual

Applies the postprocessor to a given separation.

Parameters

G	the graph
separator	list of separator nodes
first	first half of nodes
second	second half of nodes

Returns: true if everything worked

Implements ogdf::planar_separators::Postprocessor.

◆ bipartiteGraph()

void ogdf::planar_separators::DMDecomposer::bipartiteGraph	(	Graph &	graph,
		const List< node > &	separator
	)

private

Creates a bipartite graph from the nodes in the separator and those in the bigger component.

Parameters

graph	the graph
separator	the nodes in the separator

◆ calculateRemainders()

void ogdf::planar_separators::DMDecomposer::calculateRemainders ( const Graph & graph )

private

Calculates the subset SR and BR once SI / SX and BI / BX have been found.

Parameters

graph the graph

◆ chooseBalancedDecomposition()

void ogdf::planar_separators::DMDecomposer::chooseBalancedDecomposition	(	const Graph &	G,
		List< node > &	separator,
		List< node > &	first,
		List< node > &	second
	)

private

Given the subsets SI / SX / SR and BI / BX / BR, creates a separator with minimal size so that the two components are as balanced as possible.

Parameters

G	the graph
separator	the separator nodes
first	the first component
second	the second component

◆ decompose()

void ogdf::planar_separators::DMDecomposer::decompose	(	const Graph &	graph,
		const List< node > &	bipart,
		List< node > &	reachableSep,
		List< node > &	reachableB
	)

private

Given all nodes in the bipartite graph, selects starting points for the BFS and finds the reachable nodes in the separator and in B.

Parameters

graph	the graph
bipart	the bipartite graph
reachableSep	the reachable nodes from the separator
reachableB	the reachable nodes in the bigger component B

◆ getName()

std::string ogdf::planar_separators::DMDecomposer::getName ( ) const

inlineoverridevirtual

Returns the human-readable identifier of this postprocessor.

Returns: the name

Implements ogdf::planar_separators::Postprocessor.

Definition at line 417 of file PlanarSeparatorModule.h.

◆ reset()

void ogdf::planar_separators::DMDecomposer::reset ( )

private

Resets the component so it can be reused.

◆ setupAssignments()

void ogdf::planar_separators::DMDecomposer::setupAssignments	(	const Graph &	G,
		const List< node > &	separator,
		const List< node > &	first,
		const List< node > &	second
	)

private

Fills a the NodeArray assignments with the values 0, 1 and 2 to represent the assignments of nodes to the separator / first / second component, respectively.

Parameters

G	the graph
separator	the separator nodes
first	the first component
second	the second component

◆ translateAssignments()

void ogdf::planar_separators::DMDecomposer::translateAssignments	(	const Graph &	G,
		List< node > &	separator,
		List< node > &	first,
		List< node > &	second
	)		const

private

Translates the assignments stored in the NodeArray assignments back to the lists, which can then be returned.

Parameters

G	the graph
separator	the separator nodes
first	the first component
second	the second component

Member Data Documentation

◆ assignments

NodeArray<short> ogdf::planar_separators::DMDecomposer::assignments

private

Definition at line 420 of file PlanarSeparatorModule.h.

◆ BI

List<node> ogdf::planar_separators::DMDecomposer::BI

private

Definition at line 438 of file PlanarSeparatorModule.h.

◆ bipartB

List<node> ogdf::planar_separators::DMDecomposer::bipartB

private

Definition at line 423 of file PlanarSeparatorModule.h.

◆ bipartSep

List<node> ogdf::planar_separators::DMDecomposer::bipartSep

private

Definition at line 422 of file PlanarSeparatorModule.h.

◆ BR

List<node> ogdf::planar_separators::DMDecomposer::BR

private

Definition at line 440 of file PlanarSeparatorModule.h.

◆ BX

List<node> ogdf::planar_separators::DMDecomposer::BX

private

Definition at line 439 of file PlanarSeparatorModule.h.

◆ clone

NodeArray<node> ogdf::planar_separators::DMDecomposer::clone

private

Definition at line 427 of file PlanarSeparatorModule.h.

◆ flow

EdgeArray<bool> ogdf::planar_separators::DMDecomposer::flow

private

Definition at line 431 of file PlanarSeparatorModule.h.

◆ isInS

NodeArray<bool> ogdf::planar_separators::DMDecomposer::isInS

private

Definition at line 426 of file PlanarSeparatorModule.h.

◆ SI

List<node> ogdf::planar_separators::DMDecomposer::SI

private

Definition at line 434 of file PlanarSeparatorModule.h.

◆ SR

List<node> ogdf::planar_separators::DMDecomposer::SR

private

Definition at line 436 of file PlanarSeparatorModule.h.

◆ SX

List<node> ogdf::planar_separators::DMDecomposer::SX

private

Definition at line 435 of file PlanarSeparatorModule.h.

◆ unclone

NodeArray<node> ogdf::planar_separators::DMDecomposer::unclone

private

Definition at line 430 of file PlanarSeparatorModule.h.

The documentation for this class was generated from the following file:

include/ogdf/graphalg/PlanarSeparatorModule.h

OpenGraph DrawingFramework

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Member Function Documentation

◆ alternatingBFS()

◆ apply()

◆ bipartiteGraph()

◆ calculateRemainders()

◆ chooseBalancedDecomposition()

◆ decompose()

◆ getName()

◆ reset()

◆ setupAssignments()

◆ translateAssignments()

Member Data Documentation

◆ assignments

◆ BI

◆ bipartB

◆ bipartSep

◆ BR

◆ BX

◆ clone

◆ flow

◆ isInS

◆ SI

◆ SR

◆ SX

◆ unclone

Open
Graph Drawing
Framework