Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

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. More...
 
void contract (node &v, node t)
 Contracts node v and terminal t into v. More...
 
template<typename NODELIST >
void contract (NODELIST &nodes)
 Contracts nodes. More...
 
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. More...
 
void delEdges (ArrayBuffer< edge > edges)
 Removes edges in edges. More...
 
edge findRootEdge (node v)
 Finds the root node of a component given by v, an arbitrary inner nonterminal of the component. More...
 
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. More...
 
void removeBasis (node v)
 Removes a basis and cleans up. More...
 
void removeIsolatedTerminals ()
 Removes isolated terminals. More...
 
void updateSpecialCapacities ()
 Updates capacities from source to terminals and terminals to pseudotarget. More...
 
Getters for the blow-up graph (without core edges and witness sets)
const GraphgetGraph () const
 
node getSource () const
 Returns the source node. More...
 
node getPseudotarget () const
 Returns the pseudotarget node. More...
 
node getTarget () const
 Returns the target node. More...
 
int getCapacity (edge e) const
 Returns the capacity of e. More...
 
const EdgeArray< int > & capacities () const
 Returns a reference to the edge array containing all capacities. More...
 
getCost (edge e) const
 Returns the cost of e. More...
 
node getOriginal (node v) const
 Returns the original node of v. More...
 
int getLCM () const
 Returns the least common multiple of all denominators. More...
 
int getY () const
 Returns the y-value of all terminals. More...
 
const List< node > & terminals () const
 Returns a reference to the list containing all terminals in the blowup graph. More...
 
bool isTerminal (node v) const
 Returns true if and only if v is a terminal. More...
 
Getters for core edges
getCoreCapacity (node v) const
 Get capacity of a core edge. More...
 
getCoreCost (node v) const
 Get cost of a core edge. More...
 
double computeCoreWeight (node v) const
 Compute the weight of a core edge. More...
 

Protected Member Functions

void computeLCM ()
 Computes the least common multiple of the values assigned to the full components. More...
 
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. More...
 
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. More...
 
node initNode (node v)
 
void initPseudotarget ()
 Connects pseudotarget. More...
 
void initSource (ArrayBuffer< std::pair< node, int >> &roots)
 Connects source to component roots. More...
 
void initTarget ()
 Connects target. More...
 
node initTerminal (node t)
 Inserts a terminal. More...
 
void setCapacity (edge e, int capacity)
 
int updateSourceAndTargetArcCapacities (const node v)
 Updates arc capacities s->v and v->t. More...
 

Private Attributes

EdgeArray< int > m_capacity
 
const CoreEdgeModule< T > & m_ceModule
 
List< nodem_coreEdges
 the core edges as nodes More...
 
EdgeArray< T > m_cost
 
const double m_eps
 epsilon for double operations More...
 
const FullComponentWithExtraStore< T, double > & m_fullCompStore
 all enumerated full components, with solution More...
 
Graph m_graph
 
NodeArray< bool > m_isTerminal
 Incidence vector for the blowup graph terminals. More...
 
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. More...
 
node m_pseudotarget
 
node m_source
 
node m_target
 
List< nodem_terminals
 The terminals in the blowup graph. More...
 
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. More...
 
void addWitness (node e, edge f)
 Adds e to W(f) More...
 
void initCoreWitness ()
 Finds a "random" set of core edges and "replace" found edges by nodes, also find the witness sets for the core edges. More...
 
void makeCWCopy (const HashArray< edge, edge > &edgeMap)
 Copies witness sets and core edges for a given copy map. More...
 
const List< node > & core () const
 Return list of core edges (implemented by nodes) More...
 
void delCore (node e)
 Remove a core edge. More...
 
int numberOfWitnesses (edge e) const
 Return the number of witnesses of an edge. More...
 
const ArrayBuffer< edge > & witnessList (node e) const
 Return list of loss edges f in W(e) More...
 

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 463 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 356 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 361 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 523 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 578 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 621 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 640 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 730 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 765 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 771 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 614 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 708 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 518 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 562 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 568 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 528 of file BlowupGraph.h.

◆ getGraph()

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

Definition at line 498 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 538 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 533 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 508 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 503 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 513 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 543 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 190 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 371 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 222 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 254 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 553 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 434 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 606 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 785 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 653 of file BlowupGraph.h.

◆ removeIsolatedTerminals()

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

Removes isolated terminals.

Definition at line 697 of file BlowupGraph.h.

◆ setCapacity()

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

Definition at line 347 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 548 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 268 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 590 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 790 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: