Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::GreedyCycleRemoval Class Reference

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

#include <ogdf/layered/GreedyCycleRemoval.h>

+ Inheritance diagram for ogdf::GreedyCycleRemoval:

Public Member Functions

 GreedyCycleRemoval ()
 
virtual void call (const Graph &G, List< edge > &arcSet) override
 Computes the set of edges arcSet, which have to be deleted in the acyclic subgraph. More...
 
- Public Member Functions inherited from ogdf::AcyclicSubgraphModule
 AcyclicSubgraphModule ()
 Initializes an acyclic subgraph module. More...
 
virtual ~AcyclicSubgraphModule ()
 Destruction. More...
 
void callAndDelete (Graph &G)
 Makes G acyclic by removing edges. More...
 
void callAndReverse (Graph &G)
 Makes G acyclic by reversing edges. More...
 
void callAndReverse (Graph &G, List< edge > &reversed)
 Makes G acyclic by reversing edges. More...
 
void operator() (const Graph &G, List< edge > &arcSet)
 Computes the set of edges arcSet which have to be removed for obtaining an acyclic subgraph of G. More...
 

Private Member Functions

void dfs (node v, const Graph &G)
 

Private Attributes

Array< ListPure< node > > m_B
 
int m_counter
 
NodeArray< int > m_in
 
NodeArray< int > m_index
 
NodeArray< ListIterator< node > > m_item
 
int m_max
 
int m_min
 
NodeArray< int > m_out
 
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 44 of file GreedyCycleRemoval.h.

Constructor & Destructor Documentation

◆ GreedyCycleRemoval()

ogdf::GreedyCycleRemoval::GreedyCycleRemoval ( )
inline

Definition at line 46 of file GreedyCycleRemoval.h.

Member Function Documentation

◆ call()

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

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

Implements ogdf::AcyclicSubgraphModule.

◆ dfs()

void ogdf::GreedyCycleRemoval::dfs ( node  v,
const Graph G 
)
private

Member Data Documentation

◆ m_B

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

Definition at line 57 of file GreedyCycleRemoval.h.

◆ m_counter

int ogdf::GreedyCycleRemoval::m_counter
private

Definition at line 54 of file GreedyCycleRemoval.h.

◆ m_in

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

Definition at line 56 of file GreedyCycleRemoval.h.

◆ m_index

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

Definition at line 56 of file GreedyCycleRemoval.h.

◆ m_item

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

Definition at line 58 of file GreedyCycleRemoval.h.

◆ m_max

int ogdf::GreedyCycleRemoval::m_max
private

Definition at line 54 of file GreedyCycleRemoval.h.

◆ m_min

int ogdf::GreedyCycleRemoval::m_min
private

Definition at line 54 of file GreedyCycleRemoval.h.

◆ m_out

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

Definition at line 56 of file GreedyCycleRemoval.h.

◆ m_visited

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

Definition at line 59 of file GreedyCycleRemoval.h.


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