ogdf::MaxAdjOrdering Class Reference

Calculate one or all Maximum Adjacency Ordering(s) of a given simple undirected graph. More...

#include <ogdf/graphalg/MaxAdjOrdering.h>

Public Member Functions
	MaxAdjOrdering ()
	Standard constructor.
	~MaxAdjOrdering ()
	Standard destructor.
void	calc (const Graph *G, ListPure< node > *MAO)
	Calculates one MAO starting with the node with index 0.
void	calc (const Graph *G, ListPure< node > *MAO, ListPure< ListPure< edge > > *Forests)
	Calculates one MAO starting with the node with index 0.
void	calc (const Graph *G, node s, ListPure< node > *MAO)
	Calculates one MAO starting with a given node.
void	calc (const Graph *G, node s, ListPure< node > *MAO, ListPure< ListPure< edge > > *Forests)
	Calculates one MAO starting with a given node.
void	calcAll (const Graph *G, ListPure< ListPure< node > > *MAOs)
	Calculates all MAOs of a given graph.
void	calcAll (const Graph *G, ListPure< ListPure< node > > *MAOs, ListPure< ListPure< ListPure< edge > > > *Fs)
	Calculates all MAOs including their associated forest decompositions of a given graph.
void	calcBfs (const Graph *G, ListPure< node > *MAO)
	Calculates one MAO starting with the node with index 0 and lex-bfs tie breaking.
void	calcForest (const Graph &G, const ListPure< node > &MAO, ListPure< ListPure< edge > > *F)
	Calculates the associated forest decomposition of a given MAO of a graph.
void	calcForest (const Graph &G, ListPure< node > *MAO, ListPure< ListPure< edge > > *F)
	Calculates the associated forest decomposition of a given MAO of a graph.
bool	testIfAllMAOs (const Graph *G, ListPure< ListPure< node > > *Orderings, ListPure< ListPure< node > > *Perms)
	testIfAllMAOs checks all permutations (must be provided) if they are a MAO and if yes searches this ordering in the provided list.
bool	testIfMAO (const Graph *G, ListPure< node > *Ordering)
	Test if a given ordering is a MAO.
bool	testIfMAOBfs (const Graph *G, ListPure< node > *Ordering)
	Test if a given ordering is a MAO that follows lex-bfs tie breaking.
void	visualize (GraphAttributes *GA, const ListPure< node > &MAO, ListPure< ListPure< edge > > *F)
	Convenient way to visualize a MAO with the LinearLayout class.
void	visualize (GraphAttributes *GA, ListPure< node > *MAO)
	Convenient way to visualize a MAO with the LinearLayout class.
void	visualize (GraphAttributes *GA, ListPure< node > *MAO, ListPure< ListPure< edge > > *F)
	Convenient way to visualize a MAO with the LinearLayout class.

Private Member Functions
void	m_calcAllMAOs_recursion (int n, ListPure< node > currentOrder, ListPure< ListPure< edge > > currentForest, ListPure< node > currentUnsorted, NodeArray< int > r, ListPure< ListPure< node > > *MAOs, ListPure< ListPure< ListPure< edge > > > *Fs)
	This method gets called recursively to generate all MAOs and their induced forest decompositions of the edges via backtracking.
void	m_calcAllMAOs_recursion (int n, ListPure< node > currentOrder, ListPure< node > currentUnsorted, NodeArray< int > r, ListPure< ListPure< node > > *MAOs)
	This method gets called recursively to generate all MAOs via backtracking.

Detailed Description

Calculate one or all Maximum Adjacency Ordering(s) of a given simple undirected graph.

The class MaxAdjOrdering provides one algorithm to calculate a MAO or all MAOs of a given graph. It returns a ListPure of nodes or a list of ListPures that contain the ordering.

Definition at line 53 of file MaxAdjOrdering.h.

Constructor & Destructor Documentation

MaxAdjOrdering()

ogdf::MaxAdjOrdering::MaxAdjOrdering

(

)

Standard constructor.

~MaxAdjOrdering()

ogdf::MaxAdjOrdering::~MaxAdjOrdering

(

)

Standard destructor.

Member Function Documentation

calc() [1/4]

void ogdf::MaxAdjOrdering::calc	(	const Graph *	G,
		ListPure< node > *	MAO
	)

Calculates one MAO starting with the node with index 0.

Parameters

G	is the Graph to work on
MAO	is the pointer to a list that stores the MAO

calc() [2/4]

void ogdf::MaxAdjOrdering::calc	(	const Graph *	G,
		ListPure< node > *	MAO,
		ListPure< ListPure< edge > > *	Forests
	)

Calculates one MAO starting with the node with index 0.

Parameters

G	is the Graph to work on
MAO	is the pointer to a list that stores the MAO
Forests	is the pointer to a list that stores the forest decomposition associated with the MAO

calc() [3/4]

void ogdf::MaxAdjOrdering::calc	(	const Graph *	G,
		node	s,
		ListPure< node > *	MAO
	)

Calculates one MAO starting with a given node.

Parameters

G	is the Graph to work on
s	Node to start the MAO with
MAO	is the pointer to a list that stores the MAO

calc() [4/4]

void ogdf::MaxAdjOrdering::calc	(	const Graph *	G,
		node	s,
		ListPure< node > *	MAO,
		ListPure< ListPure< edge > > *	Forests
	)

Calculates one MAO starting with a given node.

Parameters

G	is the Graph to work on
s	Node to start the MAO with
MAO	is the pointer to a list that stores the MAO
Forests	is the pointer to a list that stores the forest decomposition associated with the MAO

calcAll() [1/2]

void ogdf::MaxAdjOrdering::calcAll	(	const Graph *	G,
		ListPure< ListPure< node > > *	MAOs
	)

Calculates all MAOs of a given graph.

Parameters

G	is the Graph to work on
MAOs	List of all MAOs. So it must be a list of lists

calcAll() [2/2]

void ogdf::MaxAdjOrdering::calcAll	(	const Graph *	G,
		ListPure< ListPure< node > > *	MAOs,
		ListPure< ListPure< ListPure< edge > > > *	Fs
	)

Calculates all MAOs including their associated forest decompositions of a given graph.

Parameters

G	is the graph to work on
MAOs	List of all MAOs. So it must be a list of lists of vertices.
Fs	List of all forest decompositions. So it must be a list of lists of lists of edges.

calcBfs()

void ogdf::MaxAdjOrdering::calcBfs	(	const Graph *	G,
		ListPure< node > *	MAO
	)

Calculates one MAO starting with the node with index 0 and lex-bfs tie breaking.

Parameters

G	is the Graph to work on
MAO	is the pointer to a list that stores the MAO

calcForest() [1/2]

void ogdf::MaxAdjOrdering::calcForest	(	const Graph &	G,
		const ListPure< node > &	MAO,
		ListPure< ListPure< edge > > *	F
	)

Calculates the associated forest decomposition of a given MAO of a graph.

Parameters

G	is the given graph
MAO	contains the MAO of G, given as a list of vertices
F	stores the computed forest decomposition and is a list of edge lists

calcForest() [2/2]

void ogdf::MaxAdjOrdering::calcForest	(	const Graph &	G,
		ListPure< node > *	MAO,
		ListPure< ListPure< edge > > *	F
	)

Calculates the associated forest decomposition of a given MAO of a graph.

Parameters

G	is the given graph
MAO	contains the MAO of G, given as a list of vertices
F	stores the computed forest decomposition and is a list of edge lists

m_calcAllMAOs_recursion() [1/2]

void ogdf::MaxAdjOrdering::m_calcAllMAOs_recursion ( int  n, ListPure< node >  currentOrder, ListPure< ListPure< edge > >  currentForest, ListPure< node >  currentUnsorted, NodeArray< int >  r, ListPure< ListPure< node > > *  MAOs, ListPure< ListPure< ListPure< edge > > > *  Fs  )

private

This method gets called recursively to generate all MAOs and their induced forest decompositions of the edges via backtracking.

Parameters

n	Number of nodes
currentOrder	The partial MAO to this point
currentForest	The partial forest decomposition to this point
currentUnsorted	Nodes that are still left to sort
r	Values on the nodes that count the edges to the partial MAO
MAOs	The list of all MAOs to this point
Fs	The list of all forests to this point

m_calcAllMAOs_recursion() [2/2]

void ogdf::MaxAdjOrdering::m_calcAllMAOs_recursion ( int  n, ListPure< node >  currentOrder, ListPure< node >  currentUnsorted, NodeArray< int >  r, ListPure< ListPure< node > > *  MAOs  )

private

This method gets called recursively to generate all MAOs via backtracking.

Parameters

n	Number of nodes
currentOrder	The partial MAO to this point
currentUnsorted	Nodes that are still left to sort
r	Values on the nodes that count the edges to the partial MAO
MAOs	The list of all MAOs to this point

testIfAllMAOs()

bool ogdf::MaxAdjOrdering::testIfAllMAOs	(	const Graph *	G,
		ListPure< ListPure< node > > *	Orderings,
		ListPure< ListPure< node > > *	Perms
	)

testIfAllMAOs checks all permutations (must be provided) if they are a MAO and if yes searches this ordering in the provided list.

If one permutation is no MAO it still gets searched to rule out any false elements in Perms. So we make sure we generated all MAOs of G.

Parameters

G	is the graph to work on
Orderings	contains Lists that are supposedly MAOs
Perms	contains all permutations of a graph with the same size as G

Returns

testIfMAO()

bool ogdf::MaxAdjOrdering::testIfMAO	(	const Graph *	G,
		ListPure< node > *	Ordering
	)

Test if a given ordering is a MAO.

Parameters

G	is the graph to work on
Ordering	is a ListPure that contains a permutation of the nodes

testIfMAOBfs()

bool ogdf::MaxAdjOrdering::testIfMAOBfs	(	const Graph *	G,
		ListPure< node > *	Ordering
	)

Test if a given ordering is a MAO that follows lex-bfs tie breaking.

Parameters

G	is the graph to work on
Ordering	is a ListPure that contains a permutation of the nodes

visualize() [1/3]

void ogdf::MaxAdjOrdering::visualize	(	GraphAttributes *	GA,
		const ListPure< node > &	MAO,
		ListPure< ListPure< edge > > *	F
	)

Convenient way to visualize a MAO with the LinearLayout class.

Parameters

GA	Graphattributes of the Graph to paint
MAO	Mao to use for ordering the nodes
F	A forest decomposition that is also visualized

visualize() [2/3]

void ogdf::MaxAdjOrdering::visualize	(	GraphAttributes *	GA,
		ListPure< node > *	MAO
	)

Convenient way to visualize a MAO with the LinearLayout class.

Parameters

GA	Graphattributes of the Graph to paint
MAO	Mao to use for ordering the nodes

visualize() [3/3]

void ogdf::MaxAdjOrdering::visualize	(	GraphAttributes *	GA,
		ListPure< node > *	MAO,
		ListPure< ListPure< edge > > *	F
	)

Convenient way to visualize a MAO with the LinearLayout class.

Parameters

GA	Graphattributes of the Graph to paint
MAO	Mao to use for ordering the nodes
F	A forest decomposition that is also visualized

---

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

• include/ogdf/graphalg/MaxAdjOrdering.h