非线性降维的经典算法Isomap

//*************************************************************************** // FIBTEST.CPP // // Test program for the F-heap implementation. // Copyright (c) 1996 by John Boyer. // See header file for free usage information. //*************************************************************************** #include <math.h> #include "mex.h" extern void _main(); #include <stdlib.h> #include <iostream.h> #include <stdio.h> #include <conio.h> #include <ctype.h> #include <memory.h> #include <time.h> #include "fibheap.h" #define _FIBHEAP_CPP //*************************************************************************** // This Fibonacci heap implementation is Copyright (c) 1996 by John Boyer. // See the header file for free usage information. //*************************************************************************** //*************************************************************************** // The classes in this package are designed to allow the package user // to quickly and easily develop applications that require a heap data // structure. Using amortized analysis, the asymptotically fastest heap // data structure is the Fibonacci heap. The constants are a little // high so the real speed gain will not be seen until larger data sets // are required, but in most cases, if the data set is small, then the // run-time will be neglible anyway. // // To use this heap class you need do only two things. First, subclass // the FibHeapNode class to create the class of objects that you'd // like to store in a heap. Second, create an instance of the FibHeap // class, which can then be used to Insert(), ExtractMin(), etc., // instances of your FibHeapNode subclass. Notice that you don't need // to create a subclass of the FibHeap class. // // The application-specific data object that you'd like to store in a heap // will have a key value. In the class that you derive from FibHeapNode, // you will need to define the key structure then provide assignment (=), // equality (==) and less-than operators and a destructor. These functions // are declared virtual so that the code in the FibHeap class can compare, // assign and destroy your objects by calling on your code. // // The overloaded operators in your defined class MUST call functions in // the Fibonacci heap node class first. For assignment, the function // FHN_Assign() should be called before code that deals with the copy of // the key value. For comparison operators, the function FHN_Cmp() should // appear first. If it returns 0, then keys can be compared as normal. // The following indicates what the three most common operators must do // based on the return value of FHN_Cmp() // // For ==, if zero returned, then compare keys // if non-zero X returned, then return 0 // For <, if zero returned, then compare keys // if non-zero X returned, then return X<0?1:0 // For >, if zero returned, then compare keys // if non-zero X returned, then return X>0?1:0 //*************************************************************************** #include <stdlib.h> #include <iostream.h> #include <stdio.h> #include <conio.h> #include "fibheap.h" //*************************************************************************** //========================================================= // FibHeapNode Constructor //========================================================= //*************************************************************************** FibHeapNode::FibHeapNode() { Left = Right = Parent = Child = NULL; Degree = Mark = NegInfinityFlag = 0; } //========================================================= // FibHeapNode Destructor // // Body is empty, but declaration is required in order to // force virtual. This will ensure that FibHeap class // calls derived class destructors. //========================================================= FibHeapNode::~FibHeapNode() { } //========================================================= // FHN_Assign() // // To be used as first step of an assignment operator in a // derived class. The derived class will handle assignment // of key value, and this function handles copy of the // NegInfinityFlag (which overrides the key value if it is // set). //========================================================= void FibHeapNode::FHN_Assign(FibHeapNode& RHS) { NegInfinityFlag = RHS.NegInfinityFlag; } //========================================================= // FHN_Cmp() // // To be used as the first step of ALL comparators in a // derived class. // // Compares the relative state of the two neg. infinity // flags. Note that 'this' is the left hand side. If // LHS neg. infinity is set, then it will be less than (-1) // the RHS unless RHS neg. infinity flag is also set. // Only if function returns 0 should the key comparison // defined in the derived class be performed, e.g. // // For ==, if zero returned, then compare keys // if non-zero X returned, then return 0 // For <, if zero returned, then compare keys // if non-zero X returned, then return X<0?1:0 // For >, if zero returned, then compare keys // if non-zero X returned, then return X>0?1:0 //========================================================= int FibHeapNode::FHN_Cmp(FibHeapNode& RHS) { if (NegInfinityFlag) return RHS.NegInfinityFlag ? 0 : -1; return RHS.NegInfinityFlag ? 1 : 0; } //======================================================================== // We do, on occasion, compare and assign objects of type FibHeapNode, but // only when the NegInfinityFlag is set. See for example FibHeap::Delete(). // // Also, these functions exemplify what a derived class should do. //======================================================================== void FibHeapNode::operator =(FibHeapNode& RHS) { FHN_Assign(RHS); // Key assignment goes here in derived classes } int FibHeapNode::operator ==(FibHeapNode& RHS) { if (FHN_Cmp(RHS)) return 0; // Key compare goes here in derived classes return 1; } int FibHeapNode::operator <(FibHeapNode& RHS) { int X; if ((X=FHN_Cmp(RHS)) != 0) return X < 0 ? 1 : 0; // Key compare goes here in derived classes return 0; } //========================================================= // Print() //========================================================= void FibHeapNode::Print() { if (NegInfinityFlag) cout << "-inf."; } //*************************************************************************** //=========================================================================== // FibHeap Constructor //=========================================================================== //*************************************************************************** FibHeap::FibHeap() { MinRoot = NULL; NumNodes = NumTrees = NumMarkedNodes = 0; ClearHeapOwnership(); } //=========================================================================== // FibHeap Destructor //=========================================================================== FibHeap::~FibHeap() { FibHeapNode *Temp; if (GetHeapOwnership()) { while (MinRoot != NULL) { Temp = ExtractMin(); delete Temp; } } } //=========================================================================== // Insert() - O(1) actual; O(2) amortized // // I am using O(2) here to indicate that although Insert() is // constant time, its amortized rating is more costly because some // of the work of inserting is done by other operations such as // ExtractMin(), which is where tree-balancing occurs. // // The child pointer is deliberately not set to NULL because Insert() // is also used internally to help put whole trees onto the root list. //=========================================================================== void FibHeap::Insert(FibHeapNode *NewNode) { if (NewNode == NULL) return; // If the heap is currently empty, then new node becomes s