Graphviz: VPSC Struct Reference

Searching...

No Matches

#include <solve_VPSC.h>

Inheritance diagram for VPSC:

Collaboration diagram for VPSC:

Public Member Functions
virtual void	satisfy ()

virtual void	solve ()

	VPSC (const unsigned n, Variable vs[], const unsigned m, Constraint cs[])

virtual	~VPSC ()=default

Protected Member Functions
void	printBlocks ()

Protected Attributes
Blocks	bs

Constraint **	cs

unsigned	m

Detailed Description

Variable Placement with Separation Constraints problem instance

Definition at line 29 of file solve_VPSC.h.

Constructor & Destructor Documentation

◆ VPSC()

VPSC::VPSC	(	const unsigned	n,
		Variable *	vs[],
		const unsigned	m,
		Constraint *	cs[]
	)

Definition at line 47 of file solve_VPSC.cpp.

References printBlocks(), and RECTANGLE_OVERLAP_LOGGING.

Here is the call graph for this function:

◆ ~VPSC()

virtual VPSC::~VPSC ( )

virtualdefault

Member Function Documentation

◆ printBlocks()

void VPSC::printBlocks ( )

protected

Definition at line 56 of file solve_VPSC.cpp.

References bs, cs, LOGFILE, m, and RECTANGLE_OVERLAP_LOGGING.

Referenced by IncVPSC::satisfy(), and VPSC().

Here is the caller graph for this function:

◆ satisfy()

void VPSC::satisfy ( )

virtual

Produces a feasible - though not necessarily optimal - solution by examining blocks in the partial order defined by the directed acyclic graph of constraints. For each block (when processing left to right) we maintain the invariant that all constraints to the left of the block (incoming constraints) are satisfied. This is done by repeatedly merging blocks into bigger blocks across violated constraints (most violated first) fixing the position of variables inside blocks relative to one another so that constraints internal to the block are satisfied.

Reimplemented in IncVPSC.

Definition at line 77 of file solve_VPSC.cpp.

References bs, Blocks::cleanup(), cs, LOGFILE, m, Blocks::mergeLeft(), RECTANGLE_OVERLAP_LOGGING, and Blocks::totalOrder().

Referenced by satisfyVPSC(), and solve().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ solve()

void VPSC::solve ( )

virtual

Calculate the optimal solution. After using satisfy() to produce a feasible solution, refine() examines each block to see if further refinement is possible by splitting the block. This is done repeatedly until no further improvement is possible.

Reimplemented in IncVPSC.

Definition at line 134 of file solve_VPSC.cpp.

References satisfy().

Referenced by solveVPSC().

Here is the call graph for this function:

Here is the caller graph for this function: