OpenGraph DrawingFramework

v. 2023.09 (Elderberry)

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.

◆ 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
 n number of nodes m number 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
 n number of nodes m number 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
 n number of nodes m number of edges t number 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
 k maximum number of terminals in components n number of nodes m number of edges t number 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
 n number of nodes m number of edges

Definition at line 108 of file FullComponentDecisions.h.

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