Open
Graph Drawing
Framework

  v. 2025.10-dev (Foxglove)
 
Overview Class Hierarchy Class Index Class List Members Namespaces Source Files
 

Loading...
Searching...
No Matches
Classes | Public Member Functions | Static Public Member Functions | Private Member Functions | Private Attributes | List of all members
ogdf::oneplan_backtracking::EdgePairPartition Class Reference

A partial solution for a 1-Planarity instance, representing a node in the backtracking tree. More...

#include <ogdf/k-planarity/1-planarity_backtracking/EdgePairPartition.h>

Classes

struct  UndoInformation
 

Public Member Functions

 EdgePairPartition (const EdgePairPartition &other)
 Creates a new EdgePairPartition as a copy of other, but does not copy its transaction stack.
 
 EdgePairPartition (const Graph &g, OneplanMode m=OneplanMode::Normal)
 Creates a new EdgePairPartition, where all pairs of independent edges are crossable.
 
void crossEdgePair (const EdgePair &pair)
 Crosses pair and computes the corresponding kite edges.
 
const std::set< EdgePair > & crossingEdgePairs () const
 Returns the set of all crossed edge pairs.
 
EdgePair getNextTodoCrossing ()
 Removes and returns the next stored crossing that should be considered.
 
const Graph & graph () const
 Returns the associated graph.
 
bool hasTodoCrossing ()
 Returns whether there are crossings that should be branched over.
 
bool isCrossed (edge e) const
 Returns whether e is part of a crossing.
 
bool isFree (const EdgePair &pair) const
 Returns whether pair is still allowed to cross.
 
bool isFree (edge e) const
 Returns whether there exists an edge that e may cross.
 
const std::set< VertexPair > & kiteEdges () const
 Returns the set of kite edges.
 
void setNonCrossing (const EdgePair &pair)
 Marks pair as non-crossing.
 
void startTransaction ()
 Starts a new transaction that can later be undone.
 
void startTransaction (std::vector< EdgePair > &todoCrossings)
 Starts a new transaction and associates an exhaustive set of crossings that will be branched over.
 
void undoTransaction ()
 Reverts the previous transaction.
 

Static Public Member Functions

static edge getEdgeBetween (node a, node b)
 Returns an edge between a and b, or null.
 

Private Member Functions

void addKiteEdge (const VertexPair &vp)
 
void addKiteEdge (edge e)
 
void computeKiteEdges (const EdgePair &crossedPair)
 

Private Attributes

EdgeSet m_crossedEdges
 
std::set< EdgePair > m_crossingEdgePairs
 
std::set< EdgePair > m_freeEdgePairs
 
const Graph & m_graph
 
std::set< VertexPair > m_kiteEdges
 
OneplanMode m_mode = OneplanMode::Normal
 
std::stack< UndoInformation > m_undoInformation
 

Detailed Description

A partial solution for a 1-Planarity instance, representing a node in the backtracking tree.

All independent pairs of the input graph are partitioned into crossing, uncrossable, and free (i.e., still allowed to cross). Maintains a stack of transactions that can be later undone.

Definition at line 117 of file EdgePairPartition.h.

Constructor & Destructor Documentation

◆ EdgePairPartition() [1/2]

ogdf::oneplan_backtracking::EdgePairPartition::EdgePairPartition ( const Graph &  g,
OneplanMode  m = OneplanMode::Normal 
)
inlineexplicit

Creates a new EdgePairPartition, where all pairs of independent edges are crossable.

Parameters
gThe input graph.
mThe kind of 1-Planarity represented

Definition at line 142 of file EdgePairPartition.h.

◆ EdgePairPartition() [2/2]

ogdf::oneplan_backtracking::EdgePairPartition::EdgePairPartition ( const EdgePairPartition &  other)
inline

Creates a new EdgePairPartition as a copy of other, but does not copy its transaction stack.

Definition at line 154 of file EdgePairPartition.h.

Member Function Documentation

◆ addKiteEdge() [1/2]

void ogdf::oneplan_backtracking::EdgePairPartition::addKiteEdge ( const VertexPair &  vp)
inlineprivate

Definition at line 267 of file EdgePairPartition.h.

◆ addKiteEdge() [2/2]

void ogdf::oneplan_backtracking::EdgePairPartition::addKiteEdge ( edge  e)
inlineprivate

Definition at line 260 of file EdgePairPartition.h.

◆ computeKiteEdges()

void ogdf::oneplan_backtracking::EdgePairPartition::computeKiteEdges ( const EdgePair &  crossedPair)
private

◆ crossEdgePair()

void ogdf::oneplan_backtracking::EdgePairPartition::crossEdgePair ( const EdgePair &  pair)

Crosses pair and computes the corresponding kite edges.

◆ crossingEdgePairs()

const std::set< EdgePair > & ogdf::oneplan_backtracking::EdgePairPartition::crossingEdgePairs ( ) const
inline

Returns the set of all crossed edge pairs.

Definition at line 169 of file EdgePairPartition.h.

◆ getEdgeBetween()

static edge ogdf::oneplan_backtracking::EdgePairPartition::getEdgeBetween ( node  a,
node  b 
)
inlinestatic

Returns an edge between a and b, or null.

Definition at line 248 of file EdgePairPartition.h.

◆ getNextTodoCrossing()

EdgePair ogdf::oneplan_backtracking::EdgePairPartition::getNextTodoCrossing ( )
inline

Removes and returns the next stored crossing that should be considered.

Definition at line 192 of file EdgePairPartition.h.

◆ graph()

const Graph & ogdf::oneplan_backtracking::EdgePairPartition::graph ( ) const
inline

Returns the associated graph.

Definition at line 163 of file EdgePairPartition.h.

◆ hasTodoCrossing()

bool ogdf::oneplan_backtracking::EdgePairPartition::hasTodoCrossing ( )
inline

Returns whether there are crossings that should be branched over.

Definition at line 184 of file EdgePairPartition.h.

◆ isCrossed()

bool ogdf::oneplan_backtracking::EdgePairPartition::isCrossed ( edge  e) const
inline

Returns whether e is part of a crossing.

Definition at line 238 of file EdgePairPartition.h.

◆ isFree() [1/2]

bool ogdf::oneplan_backtracking::EdgePairPartition::isFree ( const EdgePair &  pair) const
inline

Returns whether pair is still allowed to cross.

Definition at line 212 of file EdgePairPartition.h.

◆ isFree() [2/2]

bool ogdf::oneplan_backtracking::EdgePairPartition::isFree ( edge  e) const
inline

Returns whether there exists an edge that e may cross.

Definition at line 225 of file EdgePairPartition.h.

◆ kiteEdges()

const std::set< VertexPair > & ogdf::oneplan_backtracking::EdgePairPartition::kiteEdges ( ) const
inline

Returns the set of kite edges.

Definition at line 166 of file EdgePairPartition.h.

◆ setNonCrossing()

void ogdf::oneplan_backtracking::EdgePairPartition::setNonCrossing ( const EdgePair &  pair)
inline

Marks pair as non-crossing.

Definition at line 204 of file EdgePairPartition.h.

◆ startTransaction() [1/2]

void ogdf::oneplan_backtracking::EdgePairPartition::startTransaction ( )
inline

Starts a new transaction that can later be undone.

Definition at line 172 of file EdgePairPartition.h.

◆ startTransaction() [2/2]

void ogdf::oneplan_backtracking::EdgePairPartition::startTransaction ( std::vector< EdgePair > &  todoCrossings)
inline

Starts a new transaction and associates an exhaustive set of crossings that will be branched over.

Definition at line 175 of file EdgePairPartition.h.

◆ undoTransaction()

void ogdf::oneplan_backtracking::EdgePairPartition::undoTransaction ( )

Reverts the previous transaction.

Member Data Documentation

◆ m_crossedEdges

EdgeSet ogdf::oneplan_backtracking::EdgePairPartition::m_crossedEdges
private

Definition at line 129 of file EdgePairPartition.h.

◆ m_crossingEdgePairs

std::set<EdgePair> ogdf::oneplan_backtracking::EdgePairPartition::m_crossingEdgePairs
private

Definition at line 131 of file EdgePairPartition.h.

◆ m_freeEdgePairs

std::set<EdgePair> ogdf::oneplan_backtracking::EdgePairPartition::m_freeEdgePairs
private

Definition at line 132 of file EdgePairPartition.h.

◆ m_graph

const Graph& ogdf::oneplan_backtracking::EdgePairPartition::m_graph
private

Definition at line 128 of file EdgePairPartition.h.

◆ m_kiteEdges

std::set<VertexPair> ogdf::oneplan_backtracking::EdgePairPartition::m_kiteEdges
private

Definition at line 130 of file EdgePairPartition.h.

◆ m_mode

OneplanMode ogdf::oneplan_backtracking::EdgePairPartition::m_mode = OneplanMode::Normal
private

Definition at line 127 of file EdgePairPartition.h.

◆ m_undoInformation

std::stack<UndoInformation> ogdf::oneplan_backtracking::EdgePairPartition::m_undoInformation
private

Definition at line 134 of file EdgePairPartition.h.

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