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

#include <ogdf/planarity/ExtractKuratowskis.h>

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.
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.
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.
DynamicBacktrack &	operator= (const DynamicBacktrack &)
	Assignment is not defined!
Protected Attributes
const EdgeArray< int > &	m_flags
	Flags, that partition the edges into pertinent and external subgraphs.
const NodeArray< int > &	m_dfi
	The one and only DFI-NodeArray.
node	start
	Start node of backtracking.
node	end
	Identifies endnodes.
bool	less
	Iff true, DFI of endnodes has to be < DFI[end], otherwise the only valid endnode is end.
int	flag
	Every traversed edge has to be signed with this flag.
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.

Detailed Description

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

Definition at line 69 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 121 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 72 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!