Planar representation


Enumerations

enum  abstractMixedGraph::TOptExtractEmbedding {
  abstractMixedGraph::PLANEXT_DEFAULT = 0,
  abstractMixedGraph::PLANEXT_GROW = 1,
  abstractMixedGraph::PLANEXT_DUAL = 2,
  abstractMixedGraph::PLANEXT_CONNECT = 3
}

Functions

TNode abstractMixedGraph::ExtractEmbedding (TOptExtractEmbedding option=PLANEXT_DEFAULT, void *pArg=NULL) throw (ERRejected)
void abstractMixedGraph::SetExteriorArc (TArc a) throw (ERRange,ERRejected)
void abstractMixedGraph::MarkExteriorFace (TArc a) throw (ERRange,ERRejected)
TNode abstractMixedGraph::Face (TArc a) throw (ERRange)
TArc abstractMixedGraph::ExteriorArc () const throw ()
bool abstractMixedGraph::ExteriorNode (TNode v, TNode thisFace=NoNode) const throw (ERRange)
void abstractMixedGraph::ReleaseEmbedding () throw ()

Enumeration Type Documentation

enum TOptExtractEmbedding [inherited]
 

Method options for ExtractEmbedding().

Enumerator:
PLANEXT_DEFAULT  Assign a left-hand face index to every arc.
PLANEXT_GROW  Manipulate the incidence order to achieve as many exterior nodes as possible.
PLANEXT_DUAL  Generate the dual graph explicitly.
PLANEXT_CONNECT  Minimal augmentation to a planar connected graph.

Function Documentation

TArc ExteriorArc (   )  const throw () [inherited]
 

Retrieve an exterior arc.

Returns:
An arc index in the range [0,1,..,2m-1] or NoArc

bool ExteriorNode (  TNode  v,
TNode  thisFace = NoNode
)  const throw (ERRange) [inherited]
 

Retrieve the left-hand face index of a given arc.

Parameters:
v A node index in the range [0,1..,n-1]
thisFace A face index in the range [0,1..,ND()-1] or NoNode
Return values:
true If thisFace is exterior and v is on thisFace
If thisFace==NoNode, the procedure indeed checks whether v is an exterior node. This works correctly if MarkExteriorFace() has been called in advance.

If thisFace!=NoNode, the check runs on this face. And the First() indicces must be set accordingly.

TNode ExtractEmbedding (  TOptExtractEmbedding  option = PLANEXT_DEFAULT,
void *  pArg = NULL
)  throw (ERRejected) [inherited]
 

Check if the current node incidence ordering constitutes a planar representation.

Parameters:
option Specifies additional operations on the found dual representation
pArg Occasionally, computational results are exported by this pointer
Return values:
NoNode The current node incidence ordering does not encode a planar representation
Returns:
The number of faces (as in the Euler formula, but only if the graph is connected)
In the case of option=PLANEXT_DEFAULT, the left-hand face indices can be exported to a TNode[m-n+2] array. In the case of option=PLANEXT_DUAL, a pointer to an empty graph must be passed, which is then filled with the dual incidence structure. The other options manipulate the original graph.

TNode Face (  TArc  a  )  throw (ERRange) [inherited]
 

Retrieve the left-hand face index of a given arc.

Parameters:
a An arc index in the range [0,1..,2m-1]
Returns:
A node index in the range [0,1..,n-1] or NoNode

void MarkExteriorFace (  TArc  a  )  throw (ERRange,ERRejected) [inherited]
 

Adjust the First() incidences according to an exterior arc.

Parameters:
a An arc index in the range [0,1..,2m-1] or NoArc
If the arc a is defined, loop around the left-hand face of a and adjust the First() incidences so that these arcs defined the counter-clockwise cycle

void ReleaseEmbedding (   )  throw () [inherited]
 

Release the mapping of arcs to left-hand face indices.

void SetExteriorArc (  TArc  a  )  throw (ERRange,ERRejected) [protected, inherited]
 

Assign an exterior arc in the attribute pool.

Parameters:
a An arc index in the range [0,1..,2m-1] or NoArc