Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
ogdf::steiner_tree::goemans::BlowupGraph< T > Class Template Reference

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 GraphgetGraph () 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.
 
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
getCoreCapacity (node v) const
 Get capacity of a core edge.
 
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< intm_capacity
 
const CoreEdgeModule< T > & m_ceModule
 
List< nodem_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< boolm_isTerminal
 Incidence vector for the blowup graph terminals.
 
int m_lcm
 
NodeArray< nodem_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< nodem_terminals
 The terminals in the blowup graph.
 
NodeArray< ArrayBuffer< edge > > m_witness
 
EdgeArray< intm_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,
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
va 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

epsilon for double operations

Definition at line 54 of file BlowupGraph.h.

◆ m_fullCompStore

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

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: