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

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:

• include/ogdf/graphalg/steiner_tree/FullComponentDecisions.h