Open
Graph Drawing
Framework

 v. 2020.02 (Catalpa)
 

ogdf::EdgeIndependentSpanningTrees Class Reference

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. More...
 

Public Member Functions

 EdgeIndependentSpanningTrees ()
 Creates an instance of edge-independent spanning tree withou associated graph and root. More...
 
 EdgeIndependentSpanningTrees (const Graph &G)
 Creates an instance of edge-independent spanning tree and sets the graph. More...
 
 EdgeIndependentSpanningTrees (const Graph &G, node root)
 Creates an instance of edge-independent spanning tree and sets the graph and root node. More...
 
 ~EdgeIndependentSpanningTrees ()=default
 Destructor. More...
 
List< SolutionfindAll (unsigned int k) const
 Finds all k edge-independent spanning trees in graph m_G rooted at m_root. More...
 
List< SolutionfindAllPerm (unsigned int k) const
 Finds all k edge-independent spanning trees in graph m_G rooted at m_root, including permutations. More...
 
bool findOne (unsigned int k, Solution &f) const
 Finds k edge-independent spanning trees in graph m_G rooted at m_root. More...
 
const GraphgetGraph () const
 Returns a pointer to the associated graph. More...
 
node getRoot () const
 Returns the associated root node. More...
 
void setGraph (const Graph &G)
 Sets the associated graph. More...
 
void setRoot (node root)
 Sets the associated root node. More...
 

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. More...
 

Private Member Functions

bool checkIndependence (const std::vector< NodeArray< adjEntry >> &parents, unsigned int k) const
 Checks k spanning trees for independence. More...
 
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. More...
 
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. More...
 
bool checkTwoPathIndependence (const std::vector< NodeArray< adjEntry >> &parents, node v, unsigned int p1, unsigned int p2) const
 Checks two paths for independence. More...
 
void clearTree (Solution &f, unsigned int j) const
 Clears the j-th Tree from f. More...
 
bool createInitialSpanningTrees (Solution &f, unsigned int k) const
 Creates first k spanning trees. More...
 
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. More...
 
unsigned int createVals (const Solution &f, unsigned int k, std::vector< edge > &tree) const
 Creates the values needed for nextSpanningTree from f. More...
 
bool findAndInsertNextTree (Solution &f, unsigned int &t, unsigned int j, std::vector< edge > &tree) const
 Iterates using nextSpanningTree until insertNewTree succeeds. More...
 
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. More...
 
bool isInSubGraph (const std::vector< edge > &sub, const edge &e, unsigned int t) const
 Checks whether e is in the subgraph. More...
 
bool iterate (Solution &f, unsigned int j, unsigned int k) const
 Iterates over all subgraphs. More...
 
bool nextSpanningTree (unsigned int &t, std::vector< edge > &tree) const
 Calculates the next spanning tree after tree using backtracking. More...
 
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. More...
 

Private Attributes

const Graphm_G
 The associated graph. More...
 
node m_root
 The associated root node. More...
 

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 48 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 58 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 61 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 64 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 67 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 82 of file EdgeIndependentSpanningTrees.h.

◆ getRoot()

node ogdf::EdgeIndependentSpanningTrees::getRoot ( ) const
inline

Returns the associated root node.

Definition at line 93 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 87 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 108 of file EdgeIndependentSpanningTrees.h.

◆ m_root

node ogdf::EdgeIndependentSpanningTrees::m_root
private

The associated root node.

Definition at line 109 of file EdgeIndependentSpanningTrees.h.


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