ogdf::DynamicBacktrack Class Reference

Extracts all possible paths with backtracking using given edges and special constraints. More...

#include <ogdf/planarity/ExtractKuratowskis.h>

List of all members.

Public Types
enum	enumKuratowskiFlag { externalPath = 0x00001, pertinentPath = 0x00002, singlePath = 0x00004 }
	Marks an edge with three Flags: externalPath, pertinentPath and/or singlePath. More...

Public Member Functions
	DynamicBacktrack (const Graph &g, const NodeArray< int > &dfi, const EdgeArray< int > &flags)
	Constructor.
bool	addNextPath (SListPure< edge > &list, node &endnode)
	Returns next possible path from start- to endnode, if exists.
bool	addNextPathExclude (SListPure< edge > &list, node &endnode, const NodeArray< int > &nodeflags, int exclude, int exceptOnEdge)
	Returns next possible path under constraints from start- to endnode, if exists.
void	init (const node start, const node end, const bool less, const int flag, const int startFlag, const edge startInclude, const edge startExlude)
	Reinitializes backtracking with new constraints. All paths will be traversed again.
DynamicBacktrack &	operator= (const DynamicBacktrack &)
	Assignment is not defined!

Protected Attributes
node	end
	Identifies endnodes.
int	flag
	Every traversed edge has to be signed with this flag.
bool	less
	Iff true, DFI of endnodes has to be < DFI[end], otherwise the only valid endnode is end.
const NodeArray< int > &	m_dfi
	The one and only DFI-NodeArray.
const EdgeArray< int > &	m_flags
	Flags, that partition the edges into pertinent and external subgraphs.
NodeArray< adjEntry >	m_parent
	Saves the parent edge for each node in path.
StackPure< adjEntry >	stack
	Backtracking stack. A NULL-element indicates a return from a child node.
node	start
	Start node of backtracking.

---

Detailed Description

Extracts all possible paths with backtracking using given edges and special constraints.

Definition at line 60 of file ExtractKuratowskis.h.

---

Member Enumeration Documentation

enum ogdf::DynamicBacktrack::enumKuratowskiFlag

Marks an edge with three Flags: externalPath, pertinentPath and/or singlePath.

Enumerator:

externalPath
pertinentPath
singlePath

Definition at line 112 of file ExtractKuratowskis.h.

---

Constructor & Destructor Documentation

ogdf::DynamicBacktrack::DynamicBacktrack ( const Graph &  g, const NodeArray< int > &  dfi, const EdgeArray< int > &  flags  )

inline

Constructor.

Definition at line 63 of file ExtractKuratowskis.h.

---

Member Function Documentation

bool ogdf::DynamicBacktrack::addNextPath	(	SListPure< edge > &	list,
		node &	endnode
	)

Returns next possible path from start- to endnode, if exists.

The path is returned to list. After that a process image is made, allowing to pause backtracking and extracting further paths later. Endnode returns the last traversed node.

bool ogdf::DynamicBacktrack::addNextPathExclude	(	SListPure< edge > &	list,
		node &	endnode,
		const NodeArray< int > &	nodeflags,
		int	exclude,
		int	exceptOnEdge
	)

Returns next possible path under constraints from start- to endnode, if exists.

All paths avoid exclude-edges, except if on an edge with flag exceptOnEdge. The NodeArray nodeflags is used to mark visited nodes. Only that part of the path, which doesn't contain exclude-edges is finally added. The path is returned to list. After that a process image is made, allowing to pause backtracking and extracting further paths later. Endnode returns the last traversed node.

void ogdf::DynamicBacktrack::init	(	const node	start,
		const node	end,
		const bool	less,
		const int	flag,
		const int	startFlag,
		const edge	startInclude,
		const edge	startExlude
	)

Reinitializes backtracking with new constraints. All paths will be traversed again.

Startedges are either only startInclude or not startExclude, all startedges have to contain the flag startFlag, if startFlag != 0. The start- and endnode of extracted paths is given, too.

DynamicBacktrack& ogdf::DynamicBacktrack::operator=

(

const DynamicBacktrack &

)

Assignment is not defined!

---

Member Data Documentation

node ogdf::DynamicBacktrack::end

protected

Identifies endnodes.

Definition at line 127 of file ExtractKuratowskis.h.

int ogdf::DynamicBacktrack::flag

protected

Every traversed edge has to be signed with this flag.

Definition at line 131 of file ExtractKuratowskis.h.

bool ogdf::DynamicBacktrack::less

protected

Iff true, DFI of endnodes has to be < DFI[end], otherwise the only valid endnode is end.

Definition at line 129 of file ExtractKuratowskis.h.

const NodeArray<int>& ogdf::DynamicBacktrack::m_dfi

protected

The one and only DFI-NodeArray.

Definition at line 122 of file ExtractKuratowskis.h.

const EdgeArray<int>& ogdf::DynamicBacktrack::m_flags

protected

Flags, that partition the edges into pertinent and external subgraphs.

Definition at line 120 of file ExtractKuratowskis.h.

NodeArray<adjEntry> ogdf::DynamicBacktrack::m_parent

protected

Saves the parent edge for each node in path.

Definition at line 134 of file ExtractKuratowskis.h.

StackPure<adjEntry> ogdf::DynamicBacktrack::stack

protected

Backtracking stack. A NULL-element indicates a return from a child node.

Definition at line 137 of file ExtractKuratowskis.h.

node ogdf::DynamicBacktrack::start

protected

Start node of backtracking.

Definition at line 125 of file ExtractKuratowskis.h.

---

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

• ogdf/planarity/ExtractKuratowskis.h