A special-purpose blowup graph for gammoid computation: directed, with special source and target, with core edges (implemented as nodes) More...

#include <ogdf/graphalg/steiner_tree/goemans/BlowupGraph.h>

Public Member Functions
	BlowupGraph (const EdgeWeightedGraph< T > &G, const List< node > &terminals, const FullComponentWithExtraStore< T, double > &fullCompStore, const CoreEdgeModule< T > &ceModule, double eps=1e-8)
	Initializes a blowup graph including core edges and witness sets.

void	contract (node &v, node t)
	Contracts node `v` and terminal `t` into `v`.

template<typename NODELIST >
void	contract (NODELIST &nodes)
	Contracts `nodes`.

void	copyComponent (const edge origEdge, const int origCap, const int copyCap)
	Copy a component in the blowup graph and set original capacity to `origCap` and capacity of copy to `copyCap`.

void	delEdges (ArrayBuffer< edge > edges)
	Removes edges in `edges`.

edge	findRootEdge (node v)
	Finds the root node of a component given by `v`, an arbitrary inner nonterminal of the component.

edge	newEdge (node v, node w, T cost, int capacity)
	Adds and returns a new edge between `v` and `w` of specified `cost` and `capacity`.

void	removeBasis (node v)
	Removes a basis and cleans up.

void	removeIsolatedTerminals ()
	Removes isolated terminals.

void	updateSpecialCapacities ()
	Updates capacities from source to terminals and terminals to pseudotarget.

Getters for the blow-up graph (without core edges and witness sets)
const Graph &	getGraph () const

node	getSource () const
	Returns the source node.

node	getPseudotarget () const
	Returns the pseudotarget node.

node	getTarget () const
	Returns the target node.

int	getCapacity (edge e) const
	Returns the capacity of `e`.

const EdgeArray< int > &	capacities () const
	Returns a reference to the edge array containing all capacities.

T	getCost (edge e) const
	Returns the cost of `e`.

node	getOriginal (node v) const
	Returns the original node of `v`.

int	getLCM () const
	Returns the least common multiple of all denominators.

int	getY () const
	Returns the y-value of all terminals.

const List< node > &	terminals () const
	Returns a reference to the list containing all terminals in the blowup graph.

bool	isTerminal (node v) const
	Returns true if and only if `v` is a terminal.

Getters for core edges
T	getCoreCapacity (node v) const
	Get capacity of a core edge.

T	getCoreCost (node v) const
	Get cost of a core edge.

double	computeCoreWeight (node v) const
	Compute the weight of a core edge.

Protected Member Functions
void	computeLCM ()
	Computes the least common multiple of the values assigned to the full components.

node	initBlowupGraphComponent (const NodeArray< node > &copy, adjEntry start, int cap)
	Does a bfs of the component tree to add directed components with the first terminal as root.

void	initBlowupGraphComponents (const EdgeWeightedGraph< T > &originalGraph, const List< node > &terminals)
	Initializes all components in the blowup graph as well as core edges and witness sets.

node	initNode (node v)

void	initPseudotarget ()
	Connects pseudotarget.

void	initSource (ArrayBuffer< std::pair< node, int > > &roots)
	Connects source to component roots.

void	initTarget ()
	Connects target.

node	initTerminal (node t)
	Inserts a terminal.

void	setCapacity (edge e, int capacity)

int	updateSourceAndTargetArcCapacities (const node v)
	Updates arc capacities s->v and v->t.

Private Attributes
EdgeArray< int >	m_capacity

const CoreEdgeModule< T > &	m_ceModule

List< node >	m_coreEdges
	the core edges as nodes

EdgeArray< T >	m_cost

const double	m_eps
	epsilon for double operations

const FullComponentWithExtraStore< T, double > &	m_fullCompStore
	all enumerated full components, with solution

Graph	m_graph

NodeArray< bool >	m_isTerminal
	Incidence vector for the blowup graph terminals.

int	m_lcm

NodeArray< node >	m_original
	Mapping of blowup graph nodes to original nodes. If a node in a blowup graph represents more than one (contracted), it maps just to one original node. If it maps to nullptr, there is no original node, i.e. we have a core edge, a source, pseudotarget or target.

node	m_pseudotarget

node	m_source

node	m_target

List< node >	m_terminals
	The terminals in the blowup graph.

NodeArray< ArrayBuffer< edge > >	m_witness

EdgeArray< int >	m_witnessCard

int	m_y

Core edges and witness set management
void	addCore (node e)
	Adds a core edge.

void	addWitness (node e, edge f)
	Adds `e` to W(`f`)

void	initCoreWitness ()
	Finds a "random" set of core edges and "replace" found edges by nodes, also find the witness sets for the core edges.

void	makeCWCopy (const HashArray< edge, edge > &edgeMap)
	Copies witness sets and core edges for a given copy map.

const List< node > &	core () const
	Return list of core edges (implemented by nodes)

void	delCore (node e)
	Remove a core edge.

int	numberOfWitnesses (edge e) const
	Return the number of witnesses of an edge.

const ArrayBuffer< edge > &	witnessList (node e) const
	Return list of loss edges f in W(e)

Detailed Description

template<typename T>
class ogdf::steiner_tree::goemans::BlowupGraph< T >

A special-purpose blowup graph for gammoid computation: directed, with special source and target, with core edges (implemented as nodes)

Definition at line 50 of file BlowupGraph.h.

Constructor & Destructor Documentation

◆ BlowupGraph()

template<typename T >

ogdf::steiner_tree::goemans::BlowupGraph< T >::BlowupGraph	(	const EdgeWeightedGraph< T > &	G,
		const List< node > &	terminals,
		const FullComponentWithExtraStore< T, double > &	fullCompStore,
		const CoreEdgeModule< T > &	ceModule,
		double	eps = `1e-8`
	)

inline

Initializes a blowup graph including core edges and witness sets.

Definition at line 449 of file BlowupGraph.h.

Member Function Documentation

◆ addCore()

template<typename T >

void ogdf::steiner_tree::goemans::BlowupGraph< T >::addCore ( node e )

inlineprotected

Adds a core edge.

Remarks: Note that core edges are implemented by nodes in the blowup graph

Definition at line 344 of file BlowupGraph.h.

◆ addWitness()

template<typename T >

void ogdf::steiner_tree::goemans::BlowupGraph< T >::addWitness	(	node	e,
		edge	f
	)

inlineprotected

Adds e to W(f)

Definition at line 347 of file BlowupGraph.h.

◆ capacities()

template<typename T >

const EdgeArray< int > & ogdf::steiner_tree::goemans::BlowupGraph< T >::capacities ( ) const

inline

Returns a reference to the edge array containing all capacities.

Definition at line 498 of file BlowupGraph.h.

◆ computeCoreWeight()

template<typename T >

double ogdf::steiner_tree::goemans::BlowupGraph< T >::computeCoreWeight ( node v ) const

inline

Compute the weight of a core edge.

Definition at line 539 of file BlowupGraph.h.

◆ computeLCM()

template<typename T >

void ogdf::steiner_tree::goemans::BlowupGraph< T >::computeLCM ( )

inlineprotected

Computes the least common multiple of the values assigned to the full components.

Definition at line 104 of file BlowupGraph.h.

◆ contract() [1/2]

template<typename T >

void ogdf::steiner_tree::goemans::BlowupGraph< T >::contract	(	node &	v,
		node	t
	)

inline

Contracts node v and terminal t into v.

Definition at line 582 of file BlowupGraph.h.

◆ contract() [2/2]

template<typename T >

template<typename NODELIST >

void ogdf::steiner_tree::goemans::BlowupGraph< T >::contract ( NODELIST & nodes )

inline

Contracts nodes.

Definition at line 601 of file BlowupGraph.h.

◆ copyComponent()

template<typename T >

void ogdf::steiner_tree::goemans::BlowupGraph< T >::copyComponent	(	const edge	origEdge,
		const int	origCap,
		const int	copyCap
	)

inline

Copy a component in the blowup graph and set original capacity to origCap and capacity of copy to copyCap.

Definition at line 692 of file BlowupGraph.h.

◆ core()

template<typename T >

const List< node > & ogdf::steiner_tree::goemans::BlowupGraph< T >::core ( ) const

inline

Return list of core edges (implemented by nodes)

Definition at line 728 of file BlowupGraph.h.

◆ delCore()

template<typename T >

void ogdf::steiner_tree::goemans::BlowupGraph< T >::delCore ( node e )

inline

Remove a core edge.

Note: the blowup graph is not affected

Definition at line 732 of file BlowupGraph.h.

◆ delEdges()

template<typename T >

void ogdf::steiner_tree::goemans::BlowupGraph< T >::delEdges ( ArrayBuffer< edge > edges )

inline

Removes edges in edges.

Definition at line 575 of file BlowupGraph.h.

◆ findRootEdge()

template<typename T >

edge ogdf::steiner_tree::goemans::BlowupGraph< T >::findRootEdge ( node v )

inline

Finds the root node of a component given by v, an arbitrary inner nonterminal of the component.

Definition at line 670 of file BlowupGraph.h.

◆ getCapacity()

template<typename T >

int ogdf::steiner_tree::goemans::BlowupGraph< T >::getCapacity ( edge e ) const

inline

Returns the capacity of e.

Definition at line 495 of file BlowupGraph.h.

◆ getCoreCapacity()

template<typename T >

T ogdf::steiner_tree::goemans::BlowupGraph< T >::getCoreCapacity ( node v ) const

inline

Get capacity of a core edge.

Definition at line 523 of file BlowupGraph.h.

◆ getCoreCost()

template<typename T >

T ogdf::steiner_tree::goemans::BlowupGraph< T >::getCoreCost ( node v ) const

inline

Get cost of a core edge.

Definition at line 529 of file BlowupGraph.h.

◆ getCost()

template<typename T >

T ogdf::steiner_tree::goemans::BlowupGraph< T >::getCost ( edge e ) const

inline

Returns the cost of e.

Definition at line 501 of file BlowupGraph.h.

◆ getGraph()

template<typename T >

const Graph & ogdf::steiner_tree::goemans::BlowupGraph< T >::getGraph ( ) const

inline

Definition at line 483 of file BlowupGraph.h.

◆ getLCM()

template<typename T >

int ogdf::steiner_tree::goemans::BlowupGraph< T >::getLCM ( ) const

inline

Returns the least common multiple of all denominators.

Definition at line 507 of file BlowupGraph.h.

◆ getOriginal()

template<typename T >

node ogdf::steiner_tree::goemans::BlowupGraph< T >::getOriginal ( node v ) const

inline

Returns the original node of v.

Definition at line 504 of file BlowupGraph.h.

◆ getPseudotarget()

template<typename T >

node ogdf::steiner_tree::goemans::BlowupGraph< T >::getPseudotarget ( ) const

inline

Returns the pseudotarget node.

Definition at line 489 of file BlowupGraph.h.

◆ getSource()

template<typename T >

node ogdf::steiner_tree::goemans::BlowupGraph< T >::getSource ( ) const

inline

Returns the source node.

Definition at line 486 of file BlowupGraph.h.

◆ getTarget()

template<typename T >

node ogdf::steiner_tree::goemans::BlowupGraph< T >::getTarget ( ) const

inline

Returns the target node.

Definition at line 492 of file BlowupGraph.h.

◆ getY()

template<typename T >

int ogdf::steiner_tree::goemans::BlowupGraph< T >::getY ( ) const

inline

Returns the y-value of all terminals.

Definition at line 510 of file BlowupGraph.h.

◆ initBlowupGraphComponent()

template<typename T >

node ogdf::steiner_tree::goemans::BlowupGraph< T >::initBlowupGraphComponent	(	const NodeArray< node > &	copy,
		adjEntry	start,
		int	cap
	)

inlineprotected

Does a bfs of the component tree to add directed components with the first terminal as root.

Returns: the root of the component

Definition at line 145 of file BlowupGraph.h.

◆ initBlowupGraphComponents()

template<typename T >

void ogdf::steiner_tree::goemans::BlowupGraph< T >::initBlowupGraphComponents	(	const EdgeWeightedGraph< T > &	originalGraph,
		const List< node > &	terminals
	)

inlineprotected

Initializes all components in the blowup graph as well as core edges and witness sets.

Definition at line 189 of file BlowupGraph.h.

◆ initCoreWitness()

template<typename T >

void ogdf::steiner_tree::goemans::BlowupGraph< T >::initCoreWitness ( )

inlineprotected

Finds a "random" set of core edges and "replace" found edges by nodes, also find the witness sets for the core edges.

Definition at line 357 of file BlowupGraph.h.

◆ initNode()

template<typename T >

node ogdf::steiner_tree::goemans::BlowupGraph< T >::initNode ( node v )

inlineprotected

Definition at line 137 of file BlowupGraph.h.

◆ initPseudotarget()

template<typename T >

void ogdf::steiner_tree::goemans::BlowupGraph< T >::initPseudotarget ( )

inlineprotected

Connects pseudotarget.

Definition at line 220 of file BlowupGraph.h.

◆ initSource()

template<typename T >

void ogdf::steiner_tree::goemans::BlowupGraph< T >::initSource ( ArrayBuffer< std::pair< node, int > > & roots )

inlineprotected

Connects source to component roots.

Definition at line 173 of file BlowupGraph.h.

◆ initTarget()

template<typename T >

void ogdf::steiner_tree::goemans::BlowupGraph< T >::initTarget ( )

inlineprotected

Connects target.

Definition at line 252 of file BlowupGraph.h.

◆ initTerminal()

template<typename T >

node ogdf::steiner_tree::goemans::BlowupGraph< T >::initTerminal ( node t )

inlineprotected

Inserts a terminal.

Definition at line 126 of file BlowupGraph.h.

◆ isTerminal()

template<typename T >

bool ogdf::steiner_tree::goemans::BlowupGraph< T >::isTerminal ( node v ) const

inline

Returns true if and only if v is a terminal.

Definition at line 516 of file BlowupGraph.h.

◆ makeCWCopy()

template<typename T >

void ogdf::steiner_tree::goemans::BlowupGraph< T >::makeCWCopy ( const HashArray< edge, edge > & edgeMap )

inlineprotected

Copies witness sets and core edges for a given copy map.

Definition at line 420 of file BlowupGraph.h.

◆ newEdge()

template<typename T >

edge ogdf::steiner_tree::goemans::BlowupGraph< T >::newEdge	(	node	v,
		node	w,
		T	cost,
		int	capacity
	)

inline

Adds and returns a new edge between v and w of specified cost and capacity.

Definition at line 567 of file BlowupGraph.h.

◆ numberOfWitnesses()

template<typename T >

int ogdf::steiner_tree::goemans::BlowupGraph< T >::numberOfWitnesses ( edge e ) const

inline

Return the number of witnesses of an edge.

Definition at line 746 of file BlowupGraph.h.

◆ removeBasis()

template<typename T >

void ogdf::steiner_tree::goemans::BlowupGraph< T >::removeBasis ( node v )

inline

Removes a basis and cleans up.

Parameters

v	a core edge node of the basis (to determine the basis)

Definition at line 614 of file BlowupGraph.h.

◆ removeIsolatedTerminals()

template<typename T >

void ogdf::steiner_tree::goemans::BlowupGraph< T >::removeIsolatedTerminals ( )

inline

Removes isolated terminals.

Definition at line 659 of file BlowupGraph.h.

◆ setCapacity()

template<typename T >

void ogdf::steiner_tree::goemans::BlowupGraph< T >::setCapacity	(	edge	e,
		int	capacity
	)

inlineprotected

Definition at line 337 of file BlowupGraph.h.

◆ terminals()

template<typename T >

const List< node > & ogdf::steiner_tree::goemans::BlowupGraph< T >::terminals ( ) const

inline

Returns a reference to the list containing all terminals in the blowup graph.

Definition at line 513 of file BlowupGraph.h.

◆ updateSourceAndTargetArcCapacities()

template<typename T >

int ogdf::steiner_tree::goemans::BlowupGraph< T >::updateSourceAndTargetArcCapacities ( const node v )

inlineprotected

Updates arc capacities s->v and v->t.

Definition at line 264 of file BlowupGraph.h.

◆ updateSpecialCapacities()

template<typename T >

void ogdf::steiner_tree::goemans::BlowupGraph< T >::updateSpecialCapacities ( )

inline

Updates capacities from source to terminals and terminals to pseudotarget.

Definition at line 551 of file BlowupGraph.h.

◆ witnessList()

template<typename T >

const ArrayBuffer< edge > & ogdf::steiner_tree::goemans::BlowupGraph< T >::witnessList ( node e ) const

inline

Return list of loss edges f in W(e)

Definition at line 749 of file BlowupGraph.h.

Member Data Documentation

◆ m_capacity

template<typename T >

EdgeArray<int> ogdf::steiner_tree::goemans::BlowupGraph< T >::m_capacity

private

Definition at line 67 of file BlowupGraph.h.

◆ m_ceModule

template<typename T >

const CoreEdgeModule<T>& ogdf::steiner_tree::goemans::BlowupGraph< T >::m_ceModule

private

Definition at line 75 of file BlowupGraph.h.

◆ m_coreEdges

template<typename T >

List<node> ogdf::steiner_tree::goemans::BlowupGraph< T >::m_coreEdges

private

the core edges as nodes

Definition at line 77 of file BlowupGraph.h.

◆ m_cost

template<typename T >

EdgeArray<T> ogdf::steiner_tree::goemans::BlowupGraph< T >::m_cost

private

Definition at line 66 of file BlowupGraph.h.

◆ m_eps

template<typename T >

const double ogdf::steiner_tree::goemans::BlowupGraph< T >::m_eps

private

epsilon for double operations

Definition at line 54 of file BlowupGraph.h.

◆ m_fullCompStore

template<typename T >

const FullComponentWithExtraStore<T, double>& ogdf::steiner_tree::goemans::BlowupGraph< T >::m_fullCompStore

private

all enumerated full components, with solution

Definition at line 53 of file BlowupGraph.h.

◆ m_graph

template<typename T >

Graph ogdf::steiner_tree::goemans::BlowupGraph< T >::m_graph

private

Definition at line 52 of file BlowupGraph.h.

◆ m_isTerminal

template<typename T >

NodeArray<bool> ogdf::steiner_tree::goemans::BlowupGraph< T >::m_isTerminal

private

Incidence vector for the blowup graph terminals.

Definition at line 57 of file BlowupGraph.h.

◆ m_lcm

template<typename T >

int ogdf::steiner_tree::goemans::BlowupGraph< T >::m_lcm

private

Definition at line 69 of file BlowupGraph.h.

◆ m_original

template<typename T >

NodeArray<node> ogdf::steiner_tree::goemans::BlowupGraph< T >::m_original

private

Mapping of blowup graph nodes to original nodes. If a node in a blowup graph represents more than one (contracted), it maps just to one original node. If it maps to nullptr, there is no original node, i.e. we have a core edge, a source, pseudotarget or target.

Definition at line 64 of file BlowupGraph.h.

◆ m_pseudotarget

template<typename T >

node ogdf::steiner_tree::goemans::BlowupGraph< T >::m_pseudotarget

private

Definition at line 72 of file BlowupGraph.h.

◆ m_source

template<typename T >

node ogdf::steiner_tree::goemans::BlowupGraph< T >::m_source

private

Definition at line 71 of file BlowupGraph.h.

◆ m_target

template<typename T >

node ogdf::steiner_tree::goemans::BlowupGraph< T >::m_target

private

Definition at line 73 of file BlowupGraph.h.

◆ m_terminals

template<typename T >

List<node> ogdf::steiner_tree::goemans::BlowupGraph< T >::m_terminals

private

The terminals in the blowup graph.

Definition at line 56 of file BlowupGraph.h.

◆ m_witness

template<typename T >

NodeArray<ArrayBuffer<edge> > ogdf::steiner_tree::goemans::BlowupGraph< T >::m_witness

private

Definition at line 100 of file BlowupGraph.h.

◆ m_witnessCard

template<typename T >

EdgeArray<int> ogdf::steiner_tree::goemans::BlowupGraph< T >::m_witnessCard

private

Definition at line 99 of file BlowupGraph.h.

◆ m_y

template<typename T >

int ogdf::steiner_tree::goemans::BlowupGraph< T >::m_y

private

Definition at line 70 of file BlowupGraph.h.

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

include/ogdf/graphalg/steiner_tree/goemans/BlowupGraph.h

OpenGraph DrawingFramework

Public Member Functions

Protected Member Functions

Private Attributes

Core edges and witness set management

Detailed Description

Constructor & Destructor Documentation

◆ BlowupGraph()

Member Function Documentation

◆ addCore()

◆ addWitness()

◆ capacities()

◆ computeCoreWeight()

◆ computeLCM()

◆ contract() [1/2]

◆ contract() [2/2]

◆ copyComponent()

◆ core()

◆ delCore()

◆ delEdges()

◆ findRootEdge()

◆ getCapacity()

◆ getCoreCapacity()

◆ getCoreCost()

◆ getCost()

◆ getGraph()

◆ getLCM()

◆ getOriginal()

◆ getPseudotarget()

◆ getSource()

◆ getTarget()

◆ getY()

◆ initBlowupGraphComponent()

◆ initBlowupGraphComponents()

◆ initCoreWitness()

◆ initNode()

◆ initPseudotarget()

◆ initSource()

◆ initTarget()

◆ initTerminal()

◆ isTerminal()

◆ makeCWCopy()

◆ newEdge()

◆ numberOfWitnesses()

◆ removeBasis()

◆ removeIsolatedTerminals()

◆ setCapacity()

◆ terminals()

◆ updateSourceAndTargetArcCapacities()

◆ updateSpecialCapacities()

◆ witnessList()

Member Data Documentation

◆ m_capacity

◆ m_ceModule

◆ m_coreEdges

◆ m_cost

◆ m_eps

◆ m_fullCompStore

◆ m_graph

◆ m_isTerminal

◆ m_lcm

◆ m_original

◆ m_pseudotarget

◆ m_source

◆ m_target

◆ m_terminals

◆ m_witness

◆ m_witnessCard

◆ m_y

Open
Graph Drawing
Framework