ogdf: ogdf::GreedyCycleRemoval Class Reference

Greedy algorithm for computing a maximal acyclic subgraph. More...

#include <ogdf/layered/GreedyCycleRemoval.h>

Inheritance diagram for ogdf::GreedyCycleRemoval:

List of all members.

Public Member Functions
void	call (const Graph &G, List< edge > &arcSet)
	Computes the set of edges arcSet, which have to be deleted in the acyclic subgraph.
Private Member Functions
void	dfs (node v, const Graph &G)
Private Attributes
int	m_min
int	m_max
int	m_counter
NodeArray< int >	m_in
NodeArray< int >	m_out
NodeArray< int >	m_index
Array< ListPure< node > >	m_B
NodeArray< ListIterator< node > >	m_item
NodeArray< bool >	m_visited

Detailed Description

Greedy algorithm for computing a maximal acyclic subgraph.

The algorithm applies a greedy heuristic to compute a maximal acyclic subgraph and works in linear-time.

Definition at line 74 of file GreedyCycleRemoval.h.

Member Function Documentation

void ogdf::GreedyCycleRemoval::call	(	const Graph &	G,
		List< edge > &	arcSet
	)			`[virtual]`

Computes the set of edges arcSet, which have to be deleted in the acyclic subgraph.

Implements ogdf::AcyclicSubgraphModule.

void ogdf::GreedyCycleRemoval::dfs	(	node	v,
		const Graph &	G
	)			`[private]`

Member Data Documentation

Array<ListPure<node> > ogdf::GreedyCycleRemoval::m_B [private]

Definition at line 85 of file GreedyCycleRemoval.h.

int ogdf::GreedyCycleRemoval::m_counter [private]

Definition at line 82 of file GreedyCycleRemoval.h.

NodeArray<int> ogdf::GreedyCycleRemoval::m_in [private]

Definition at line 84 of file GreedyCycleRemoval.h.

NodeArray<int> ogdf::GreedyCycleRemoval::m_index [private]

Definition at line 84 of file GreedyCycleRemoval.h.

NodeArray<ListIterator<node> > ogdf::GreedyCycleRemoval::m_item [private]

Definition at line 86 of file GreedyCycleRemoval.h.

int ogdf::GreedyCycleRemoval::m_max [private]

Definition at line 82 of file GreedyCycleRemoval.h.

int ogdf::GreedyCycleRemoval::m_min [private]

Definition at line 82 of file GreedyCycleRemoval.h.

NodeArray<int> ogdf::GreedyCycleRemoval::m_out [private]

Definition at line 84 of file GreedyCycleRemoval.h.

NodeArray<bool> ogdf::GreedyCycleRemoval::m_visited [private]

Definition at line 87 of file GreedyCycleRemoval.h.

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

ogdf/layered/GreedyCycleRemoval.h