MeWeightMatcher.cpp File Reference

#include <xmsmesh/meshing/detail/MeWeightMatcher.h>
#include <numeric>
#include <xmscore/misc/XmError.h>
#include <xmscore/stl/vector.h>
#include <xmsmesh/meshing/detail/MeWeightMatcher.t.h>
#include <xmscore/testing/TestTools.h>
#include <xmsinterp/triangulate/TrTriangulatorPoints.h>

Go to the source code of this file.

Macros
#define	TS_ASSERT_MATCH_WEIGHTS(a_expected, a_edges, a_cardinality)   _TS_ASSERT_MATCH_WEIGHTS(__FILE__, __LINE__, a_expected, a_edges, a_cardinality)
	Helper to run matcher tests.
#define	_TS_ASSERT_MATCH_WEIGHTS(a_file, a_line, a_expected, a_edges, a_cardinality)   iMatchWeights(a_file, a_line, a_expected, a_edges, a_cardinality)
	Helper to run matcher tests.

Detailed Description

Copyright

(C) Copyright Aquaveo 2018. Distributed under FreeBSD License (See accompanying file LICENSE or https://aqaveo.com/bsd/license.txt)

Definition in file MeWeightMatcher.cpp.

Variable Documentation

m_allowEdge

VecBool m_allowEdge

private

If m_allowEdge[k] is true, edge k has zero slack in the optimization problem; if m_allowEdge[k] is false, the edge's slack may or may not be zero.

Definition at line 468 of file MeWeightMatcher.cpp.

m_bestEdge

VecIntPy m_bestEdge

private

If v is a free vertex (or an unreached vertex inside a T-blossom), m_bestEdge[v] is the edge to an S-vertex with least slack, or -1 if there is no such edge. If b is a (possibly trivial) top-level S-blossom, m_bestEdge[b] is the least-slack edge to a different S-blossom, or -1 if there is no such edge. This is used for efficient computation of delta2 and delta3.

Definition at line 443 of file MeWeightMatcher.cpp.

m_blossomBase

VecIntPy m_blossomBase

private

If b is a (sub-)blossom, m_blossomBase[b] is its base VERTEX (i.e. recursive sub-blossom). if m_nVertex is 4: [0, 1, 2, 3, -1, -1, -1, -1]

Definition at line 427 of file MeWeightMatcher.cpp.

m_blossomBestEdges

VecInt2dPy m_blossomBestEdges

private

If b is a non-trivial top-level S-blossom, m_blossomBestEdges[b] is a list of least-slack edges to neighbouring S-blossoms, or None if no such list has been computed yet. This is used for efficient computation of delta3.

Definition at line 449 of file MeWeightMatcher.cpp.

m_blossomChildren

VecInt2dPy m_blossomChildren

private

If b is a non-trivial (sub-)blossom, m_blossomChildren[b] is an ordered list of its sub-blossoms, starting with the base and going round the blossom. m_blossomChildren = (2 * m_nVertex) * [ None ]

Definition at line 422 of file MeWeightMatcher.cpp.

m_blossomEndPts

VecInt2dPy m_blossomEndPts

private

If b is a non-trivial (sub-)blossom, m_blossomEndPts[b] is a list of endpoints on its connecting edges, such that m_blossomEndPts[b][i] is the local endpoint of m_blossomChildren[b][i] on the edge that connects it to m_blossomChildren[b][wrap(i+1)].

Definition at line 434 of file MeWeightMatcher.cpp.

m_blossomParent

VecIntPy m_blossomParent

private

If b is a sub-blossom, m_blossomParent[b] is its immediate parent (sub-)blossom. If b is a top-level blossom, m_blossomParent[b] is -1.

Definition at line 416 of file MeWeightMatcher.cpp.

m_dualVar

VecIntPy m_dualVar

private

If v is a vertex, m_dualVar[v] = 2 * u(v) where u(v) is the v's variable in the dual optimization problem (multiplication by two ensures integer values throughout the algorithm if all edge weights are integers). If b is a non-trivial blossom, m_dualVar[b] = z(b) where z(b) is b's variable in the dual optimization problem. if m_nVertex is 4 and m_maxWeight is w: [w, w, w, w, 0, 0, 0, 0]

Definition at line 463 of file MeWeightMatcher.cpp.

m_endPoint

VecIntPy m_endPoint

private

Edge endpoints are numbered 0 .. (2*m_nEdge-1), such that endpoints (2*k) and (2*k+1) both belong to edge k. If p is an edge endpoint, m_endPoint[p] is the vertex to which endpoint p is attached. Not modified by the algorithm.

Definition at line 374 of file MeWeightMatcher.cpp.

m_inBlossom

VecIntPy m_inBlossom

private

If v is a vertex, m_inBlossom[v] is the top-level blossom to which v belongs. If v is a top-level vertex, v is itself a blossom (a trivial blossom) and m_inBlossom[v] == v. Initially all vertices are top-level trivial blossoms.

Definition at line 411 of file MeWeightMatcher.cpp.

m_label

VecIntPy m_label

private

If b is a top-level blossom, m_label[b] is 0 if b is unlabeled (free); 1 if b is an S-vertex/blossom; 2 if b is a T-vertex/blossom. The label of a vertex is found by looking at the label of its top-level containing blossom. If v is a vertex inside a T-blossom, m_label[v] is 2 iff v is reachable from an S-vertex outside the blossom. Labels are assigned during a stage and reset after each augmentation.

Definition at line 396 of file MeWeightMatcher.cpp.

m_labelEnd

VecIntPy m_labelEnd

private

If b is a labeled top-level blossom, m_labelEnd[b] is the remote endpoint of the edge through which b obtained its label, or -1 if b's base vertex is single. If v is a vertex inside a T-blossom and m_label[v] == 2, m_labelEnd[v] is the remote endpoint of the edge through which v is reachable from outside the blossom.

Definition at line 404 of file MeWeightMatcher.cpp.

m_mate

VecIntPy m_mate

private

If v is a vertex, m_mate[v] is the remote endpoint of its matched edge, or -1 if it is single (i.e. m_endPoint[m_mate[v]] is v's partner vertex). Initially all vertices are single; updated during augmentation.

Definition at line 385 of file MeWeightMatcher.cpp.

m_neighbEnd

VecInt2dPy m_neighbEnd

private

If v is a vertex, m_neighbEnd[v] is the list of remote endpoints of the edges attached to v. Not modified by the algorithm.

Definition at line 379 of file MeWeightMatcher.cpp.

m_unusedBlossoms

VecIntPy m_unusedBlossoms

private

List of currently unused blossom numbers. if m_nVertex is 4: [4, 5, 6, 7]

Definition at line 453 of file MeWeightMatcher.cpp.