Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
ogdf::steiner_tree::FullComponentDecisions Struct Reference

Contains rules of thumb to decide which (sub-)algorithms to use for the generation of full components. More...

#include <ogdf/graphalg/steiner_tree/FullComponentDecisions.h>

Static Public Member Functions

static double computeDensity (int n, int m)
 Computes the ratio of edges to potential edges in a simple graph.
 
static bool shouldUseAllNodeDijkstra (int n, int m)
 Returns true iff the rule of thumb predicts to call Dijkstra on all nodes instead of the algorithm by Floyd.
 
static bool shouldUseAllTerminalDijkstra (int n, int m, int t)
 Returns true iff the rule of thumb predicts to call Dijkstra on all terminals instead of the algorithm by Floyd.
 
static bool shouldUseDijkstra (int k, int n, int m, int t)
 Returns true iff the rule of thumb predicts to use multiple Dijkstra calls instead of the algorithm by Floyd.
 
static bool shouldUseErickson (int n, int m)
 Returns true iff the rule of thumb predicts to use the algorithm by Erickson et al instead of the Dreyfus-Wagner algorithm.
 

Detailed Description

Contains rules of thumb to decide which (sub-)algorithms to use for the generation of full components.

Definition at line 39 of file FullComponentDecisions.h.

Member Function Documentation

◆ computeDensity()

static double ogdf::steiner_tree::FullComponentDecisions::computeDensity ( int  n,
int  m 
)
inlinestatic

Computes the ratio of edges to potential edges in a simple graph.

Parameters
nnumber of nodes
mnumber of edges

Definition at line 45 of file FullComponentDecisions.h.

◆ shouldUseAllNodeDijkstra()

static bool ogdf::steiner_tree::FullComponentDecisions::shouldUseAllNodeDijkstra ( int  n,
int  m 
)
inlinestatic

Returns true iff the rule of thumb predicts to call Dijkstra on all nodes instead of the algorithm by Floyd.

Parameters
nnumber of nodes
mnumber of edges

Definition at line 82 of file FullComponentDecisions.h.

◆ shouldUseAllTerminalDijkstra()

static bool ogdf::steiner_tree::FullComponentDecisions::shouldUseAllTerminalDijkstra ( int  n,
int  m,
int  t 
)
inlinestatic

Returns true iff the rule of thumb predicts to call Dijkstra on all terminals instead of the algorithm by Floyd.

Parameters
nnumber of nodes
mnumber of edges
tnumber of terminals

Definition at line 59 of file FullComponentDecisions.h.

◆ shouldUseDijkstra()

static bool ogdf::steiner_tree::FullComponentDecisions::shouldUseDijkstra ( int  k,
int  n,
int  m,
int  t 
)
inlinestatic

Returns true iff the rule of thumb predicts to use multiple Dijkstra calls instead of the algorithm by Floyd.

Parameters
kmaximum number of terminals in components
nnumber of nodes
mnumber of edges
tnumber of terminals

Definition at line 94 of file FullComponentDecisions.h.

◆ shouldUseErickson()

static bool ogdf::steiner_tree::FullComponentDecisions::shouldUseErickson ( int  n,
int  m 
)
inlinestatic

Returns true iff the rule of thumb predicts to use the algorithm by Erickson et al instead of the Dreyfus-Wagner algorithm.

Parameters
nnumber of nodes
mnumber of edges

Definition at line 108 of file FullComponentDecisions.h.


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