Calculates k edge-independent spanning trees of a graph. More...

#include <ogdf/graphalg/EdgeIndependentSpanningTrees.h>

Public Types
using	Solution = EdgeArray< std::pair< unsigned int, unsigned int > >
	The solution type.

Public Member Functions
	EdgeIndependentSpanningTrees ()
	Creates an instance of edge-independent spanning tree withou associated graph and root.

	EdgeIndependentSpanningTrees (const Graph &G)
	Creates an instance of edge-independent spanning tree and sets the graph.

	EdgeIndependentSpanningTrees (const Graph &G, node root)
	Creates an instance of edge-independent spanning tree and sets the graph and root node.

	~EdgeIndependentSpanningTrees ()=default
	Destructor.

List< Solution >	findAll (unsigned int k) const
	Finds all k edge-independent spanning trees in graph m_G rooted at m_root.

List< Solution >	findAllPerm (unsigned int k) const
	Finds all k edge-independent spanning trees in graph m_G rooted at m_root, including permutations.

bool	findOne (unsigned int k, Solution &f) const
	Finds k edge-independent spanning trees in graph m_G rooted at m_root.

const Graph *	getGraph () const
	Returns a pointer to the associated graph.

node	getRoot () const
	Returns the associated root node.

void	setGraph (const Graph &G)
	Sets the associated graph.

void	setRoot (node root)
	Sets the associated root node.

Protected Member Functions
void	findDo (unsigned int k, std::function< bool(Solution &)> func) const
	Finds k edge-independent spanning trees and invokes `func` for each one, The search is stopped if `func` returns false.

Private Member Functions
bool	checkIndependence (const std::vector< NodeArray< adjEntry > > &parents, unsigned int k) const
	Checks k spanning trees for independence.

bool	checkNewTree (const Solution &f1, const Solution &f2, unsigned int k) const
	Takes two edge-independent spanning trees and checks for them being unequal under all permutations.

bool	checkOnePermUnequal (const Solution &f1, const Solution &f2, const std::vector< unsigned int > &perm) const
	Takes two edge-independent spanning trees, permutes one and checks for them being unequal.

bool	checkTwoPathIndependence (const std::vector< NodeArray< adjEntry > > &parents, node v, unsigned int p1, unsigned int p2) const
	Checks two paths for independence.

void	clearTree (Solution &f, unsigned int j) const
	Clears the j-th Tree from `f`.

bool	createInitialSpanningTrees (Solution &f, unsigned int k) const
	Creates first k spanning trees.

bool	createParentRel (const Solution &f, unsigned int j, NodeArray< adjEntry > &parent) const
	Creates a parent relation, which for each node in the associated graph contains the adjEntry pointing towards the root node.

unsigned int	createVals (const Solution &f, unsigned int k, std::vector< edge > &tree) const
	Creates the values needed for nextSpanningTree from `f`.

bool	findAndInsertNextTree (Solution &f, unsigned int &t, unsigned int j, std::vector< edge > &tree) const
	Iterates using nextSpanningTree until insertNewTree succeeds.

bool	insertNewTree (Solution &f, unsigned int t, unsigned int j, std::vector< edge > &tree) const

bool	isFinished (const Solution &f, unsigned int k) const
	Checks whether iteration is finished.

bool	isInSubGraph (const std::vector< edge > &sub, const edge &e, unsigned int t) const
	Checks whether `e` is in the subgraph.

bool	iterate (Solution &f, unsigned int j, unsigned int k) const
	Iterates over all subgraphs.

bool	nextSpanningTree (unsigned int &t, std::vector< edge > &tree) const
	Calculates the next spanning tree after tree using backtracking.

bool	pathExists (const std::vector< edge > &tree, node v1, node v2, unsigned int t) const
	Checks whether `v1` and `v2` are connected in the subgraph.

Private Attributes
const Graph *	m_G
	The associated graph.

node	m_root
	The associated root node.

Detailed Description

Calculates k edge-independent spanning trees of a graph.

Given a root note, a set of k edge-independent spanning trees of a graph G is a set of k spanning trees, for which for each two trees the paths from any node to the root are edge-disjoint.

Definition at line 51 of file EdgeIndependentSpanningTrees.h.

Member Typedef Documentation

◆ Solution

using ogdf::EdgeIndependentSpanningTrees::Solution = EdgeArray<std::pair<unsigned int, unsigned int> >

The solution type.

Since each edge of the associated graph can be contained in up to two different spanning trees (traversed in opposite directions), the first and second members stored for each edge in the solution indicates the IDs of spanning trees containing them (0 meaning none).

Definition at line 61 of file EdgeIndependentSpanningTrees.h.

Constructor & Destructor Documentation

◆ EdgeIndependentSpanningTrees() [1/3]

ogdf::EdgeIndependentSpanningTrees::EdgeIndependentSpanningTrees ( )

inline

Creates an instance of edge-independent spanning tree withou associated graph and root.

Definition at line 64 of file EdgeIndependentSpanningTrees.h.

◆ EdgeIndependentSpanningTrees() [2/3]

ogdf::EdgeIndependentSpanningTrees::EdgeIndependentSpanningTrees ( const Graph & G )

inline

Creates an instance of edge-independent spanning tree and sets the graph.

Definition at line 67 of file EdgeIndependentSpanningTrees.h.

◆ EdgeIndependentSpanningTrees() [3/3]

ogdf::EdgeIndependentSpanningTrees::EdgeIndependentSpanningTrees	(	const Graph &	G,
		node	root
	)

inline

Creates an instance of edge-independent spanning tree and sets the graph and root node.

Definition at line 71 of file EdgeIndependentSpanningTrees.h.

◆ ~EdgeIndependentSpanningTrees()

ogdf::EdgeIndependentSpanningTrees::~EdgeIndependentSpanningTrees ( )

default

Destructor.

Member Function Documentation

◆ checkIndependence()

bool ogdf::EdgeIndependentSpanningTrees::checkIndependence	(	const std::vector< NodeArray< adjEntry > > &	parents,
		unsigned int	k
	)		const

private

Checks k spanning trees for independence.

◆ checkNewTree()

bool ogdf::EdgeIndependentSpanningTrees::checkNewTree	(	const Solution &	f1,
		const Solution &	f2,
		unsigned int	k
	)		const

private

Takes two edge-independent spanning trees and checks for them being unequal under all permutations.

◆ checkOnePermUnequal()

bool ogdf::EdgeIndependentSpanningTrees::checkOnePermUnequal	(	const Solution &	f1,
		const Solution &	f2,
		const std::vector< unsigned int > &	perm
	)		const

private

Takes two edge-independent spanning trees, permutes one and checks for them being unequal.

◆ checkTwoPathIndependence()

bool ogdf::EdgeIndependentSpanningTrees::checkTwoPathIndependence	(	const std::vector< NodeArray< adjEntry > > &	parents,
		node	v,
		unsigned int	p1,
		unsigned int	p2
	)		const

private

Checks two paths for independence.

◆ clearTree()

void ogdf::EdgeIndependentSpanningTrees::clearTree	(	Solution &	f,
		unsigned int	j
	)		const

private

Clears the j-th Tree from f.

◆ createInitialSpanningTrees()

bool ogdf::EdgeIndependentSpanningTrees::createInitialSpanningTrees	(	Solution &	f,
		unsigned int	k
	)		const

private

Creates first k spanning trees.

◆ createParentRel()

bool ogdf::EdgeIndependentSpanningTrees::createParentRel	(	const Solution &	f,
		unsigned int	j,
		NodeArray< adjEntry > &	parent
	)		const

private

Creates a parent relation, which for each node in the associated graph contains the adjEntry pointing towards the root node.

◆ createVals()

unsigned int ogdf::EdgeIndependentSpanningTrees::createVals	(	const Solution &	f,
		unsigned int	k,
		std::vector< edge > &	tree
	)		const

private

Creates the values needed for nextSpanningTree from f.

◆ findAll()

List< Solution > ogdf::EdgeIndependentSpanningTrees::findAll ( unsigned int k ) const

Finds all k edge-independent spanning trees in graph m_G rooted at m_root.

◆ findAllPerm()

List< Solution > ogdf::EdgeIndependentSpanningTrees::findAllPerm ( unsigned int k ) const

Finds all k edge-independent spanning trees in graph m_G rooted at m_root, including permutations.

◆ findAndInsertNextTree()

bool ogdf::EdgeIndependentSpanningTrees::findAndInsertNextTree	(	Solution &	f,
		unsigned int &	t,
		unsigned int	j,
		std::vector< edge > &	tree
	)		const

private

Iterates using nextSpanningTree until insertNewTree succeeds.

◆ findDo()

void ogdf::EdgeIndependentSpanningTrees::findDo	(	unsigned int	k,
		std::function< bool(Solution &)>	func
	)		const

protected

Finds k edge-independent spanning trees and invokes func for each one, The search is stopped if func returns false.

◆ findOne()

bool ogdf::EdgeIndependentSpanningTrees::findOne	(	unsigned int	k,
		Solution &	f
	)		const

Finds k edge-independent spanning trees in graph m_G rooted at m_root.

◆ getGraph()

const Graph * ogdf::EdgeIndependentSpanningTrees::getGraph ( ) const

inline

Returns a pointer to the associated graph.

Definition at line 86 of file EdgeIndependentSpanningTrees.h.

◆ getRoot()

node ogdf::EdgeIndependentSpanningTrees::getRoot ( ) const

inline

Returns the associated root node.

Definition at line 95 of file EdgeIndependentSpanningTrees.h.

◆ insertNewTree()

bool ogdf::EdgeIndependentSpanningTrees::insertNewTree	(	Solution &	f,
		unsigned int	t,
		unsigned int	j,
		std::vector< edge > &	tree
	)		const

private

◆ isFinished()

bool ogdf::EdgeIndependentSpanningTrees::isFinished	(	const Solution &	f,
		unsigned int	k
	)		const

private

Checks whether iteration is finished.

◆ isInSubGraph()

bool ogdf::EdgeIndependentSpanningTrees::isInSubGraph	(	const std::vector< edge > &	sub,
		const edge &	e,
		unsigned int	t
	)		const

private

Checks whether e is in the subgraph.

◆ iterate()

bool ogdf::EdgeIndependentSpanningTrees::iterate	(	Solution &	f,
		unsigned int	j,
		unsigned int	k
	)		const

private

Iterates over all subgraphs.

◆ nextSpanningTree()

bool ogdf::EdgeIndependentSpanningTrees::nextSpanningTree	(	unsigned int &	t,
		std::vector< edge > &	tree
	)		const

private

Calculates the next spanning tree after tree using backtracking.

◆ pathExists()

bool ogdf::EdgeIndependentSpanningTrees::pathExists	(	const std::vector< edge > &	tree,
		node	v1,
		node	v2,
		unsigned int	t
	)		const

private

Checks whether v1 and v2 are connected in the subgraph.

◆ setGraph()

void ogdf::EdgeIndependentSpanningTrees::setGraph ( const Graph & G )

inline

Sets the associated graph.

Definition at line 89 of file EdgeIndependentSpanningTrees.h.

◆ setRoot()

void ogdf::EdgeIndependentSpanningTrees::setRoot ( node root )

inline

Sets the associated root node.

Definition at line 98 of file EdgeIndependentSpanningTrees.h.

Member Data Documentation

◆ m_G

const Graph* ogdf::EdgeIndependentSpanningTrees::m_G

private

The associated graph.

Definition at line 106 of file EdgeIndependentSpanningTrees.h.

◆ m_root

node ogdf::EdgeIndependentSpanningTrees::m_root

private

The associated root node.

Definition at line 107 of file EdgeIndependentSpanningTrees.h.

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

include/ogdf/graphalg/EdgeIndependentSpanningTrees.h

OpenGraph DrawingFramework

Public Types

Public Member Functions

Protected Member Functions

Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ Solution

Constructor & Destructor Documentation

◆ EdgeIndependentSpanningTrees() [1/3]

◆ EdgeIndependentSpanningTrees() [2/3]

◆ EdgeIndependentSpanningTrees() [3/3]

◆ ~EdgeIndependentSpanningTrees()

Member Function Documentation

◆ checkIndependence()

◆ checkNewTree()

◆ checkOnePermUnequal()

◆ checkTwoPathIndependence()

◆ clearTree()

◆ createInitialSpanningTrees()

◆ createParentRel()

◆ createVals()

◆ findAll()

◆ findAllPerm()

◆ findAndInsertNextTree()

◆ findDo()

◆ findOne()

◆ getGraph()

◆ getRoot()

◆ insertNewTree()

◆ isFinished()

◆ isInSubGraph()

◆ iterate()

◆ nextSpanningTree()

◆ pathExists()

◆ setGraph()

◆ setRoot()

Member Data Documentation

◆ m_G

◆ m_root

Open
Graph Drawing
Framework