comp526::stable_matching 命名空间参考

类
class	Company
class	Solution
class	Student

函数
vector< vector< int > >	convert_prefs_to_matrix (const vector< vector< int > > &prefs)
	TEST (StableMatchingTest, MultiRound3x3)
	TEST (StableMatchingTest, Simple2x2)
	TEST (StableMatchingTest, Wikipedia3x3Example)
	TEST (StableMatchingTest, WorstCaseForStudents)

函数说明

convert_prefs_to_matrix()

vector< vector< int > > comp526::stable_matching::convert_prefs_to_matrix

(

const vector< vector< int > > &

prefs

)

在文件 comp526_test.cpp 第 14 行定义.

                                                                                      {
            int n = prefs.size();
            vector<vector<int>> matrix(n, vector<int>(n));
            for(int i = 0; i < n; ++i) {
                for(int rank = 0; rank < n; ++rank) {
                    int partner_id        = prefs[i][rank];
                    matrix[i][partner_id] = rank;
                }
            }
            return matrix;
        }

被这些函数引用 TEST(), TEST(), TEST() , 以及 TEST().

TEST() [1/4]

comp526::stable_matching::TEST	(	StableMatchingTest	,
		MultiRound3x3	)

在文件 comp526_test.cpp 第 71 行定义.

                                                {
            // A case designed to require multiple rounds of proposals and rejections.
            // Students:
            //  S0: C0 > C1 > C2
            //  S1: C1 > C0 > C2
            //  S2: C0 > C1 > C2
            // Companies:
            //  C0: S1 > S2 > S0
            //  C1: S0 > S1 > S2
            //  C2: S0 > S1 > S2
            // Expected Student-Optimal Matching: (S0, C1), (S1, C0), (S2, C2)
            // Trace:
            // 1. S0->C0, S1->C1, S2->C0. C0 keeps S2 (better rank), rejects S0. Matches: (S2,C0), (S1,C1).
            // 2. S0 (free) -> C1. C1 has S1, prefers S0. C1 keeps S0, rejects S1. Matches: (S2,C0), (S0,C1).
            // 3. S1 (free) -> C0. C0 has S2, prefers S1. C0 keeps S1, rejects S2. Matches: (S1,C0), (S0,C1).
            // 4. S2 (free) -> C1. C1 has S0, prefers S0. Rejects S2.
            // 5. S2 (free) -> C2. C2 is free, accepts S2.
            // Final: (S0,C1), (S1,C0), (S2,C2)
            vector<vector<int>> s_prefs = {{0, 1, 2}, {1, 0, 2}, {0, 1, 2}};
            vector<vector<int>> c_prefs = {{1, 2, 0}, {0, 1, 2}, {0, 1, 2}};
 
            vector<vector<int>> s2c = convert_prefs_to_matrix(s_prefs);
            vector<vector<int>> c2s = convert_prefs_to_matrix(c_prefs);
 
            Solution sol;
            vector<int> expected_matches = {1, 0, 2};// ans[0]=C1, ans[1]=C0, ans[2]=C2
            ASSERT_EQ(sol.match(s2c, c2s), expected_matches);
        }

引用了 convert_prefs_to_matrix() , 以及 comp526::stable_matching::Solution::match().

TEST() [2/4]

comp526::stable_matching::TEST	(	StableMatchingTest	,
		Simple2x2	)

在文件 comp526_test.cpp 第 26 行定义.

                                            {
            // A simple case where both students prefer Company 0.
            // Students:
            //  S0: C0 > C1
            //  S1: C0 > C1
            // Companies:
            //  C0: S1 > S0
            //  C1: S0 > S1
            // Expected Student-Optimal Matching: (S0, C1), (S1, C0)
            // S0 proposes to C0, S1 proposes to C0. C0 prefers S1 and rejects S0.
            // S0 then proposes to C1, who is free and accepts.
            vector<vector<int>> s_prefs = {{0, 1}, {0, 1}};
            vector<vector<int>> c_prefs = {{1, 0}, {0, 1}};
 
            vector<vector<int>> s2c = convert_prefs_to_matrix(s_prefs);
            vector<vector<int>> c2s = convert_prefs_to_matrix(c_prefs);
 
            Solution sol;
            vector<int> expected_matches = {1, 0};// ans[0]=C1, ans[1]=C0
            ASSERT_EQ(sol.match(s2c, c2s), expected_matches);
        }

引用了 convert_prefs_to_matrix() , 以及 comp526::stable_matching::Solution::match().

TEST() [3/4]

comp526::stable_matching::TEST	(	StableMatchingTest	,
		Wikipedia3x3Example	)

在文件 comp526_test.cpp 第 48 行定义.

                                                      {
            // This is the classic example from the Stable Marriage Problem Wikipedia page.
            // Students (Men): A=0, B=1, C=2
            // Companies (Women): X=0, Y=1, Z=2
            // Prefs:
            //  A: Y > X > Z  -> {1, 0, 2}
            //  B: Z > Y > X  -> {2, 1, 0}
            //  C: X > Z > Y  -> {0, 2, 1}
            //  X: B > A > C  -> {1, 0, 2}
            //  Y: C > B > A  -> {2, 1, 0}
            //  Z: A > C > B  -> {0, 2, 1}
            // Expected Student-Optimal (Men-Optimal) Matching: (A,Y), (B,Z), (C,X)
            vector<vector<int>> s_prefs = {{1, 0, 2}, {2, 1, 0}, {0, 2, 1}};
            vector<vector<int>> c_prefs = {{1, 0, 2}, {2, 1, 0}, {0, 2, 1}};
 
            vector<vector<int>> s2c = convert_prefs_to_matrix(s_prefs);
            vector<vector<int>> c2s = convert_prefs_to_matrix(c_prefs);
 
            Solution sol;
            vector<int> expected_matches = {1, 2, 0};// ans[0]=C1, ans[1]=C2, ans[2]=C0
            ASSERT_EQ(sol.match(s2c, c2s), expected_matches);
        }

引用了 convert_prefs_to_matrix() , 以及 comp526::stable_matching::Solution::match().

TEST() [4/4]

comp526::stable_matching::TEST	(	StableMatchingTest	,
		WorstCaseForStudents	)

在文件 comp526_test.cpp 第 100 行定义.

                                                       {
            // A case where every student gets their last choice.
            // Students:
            //  S0: C0 > C1
            //  S1: C0 > C1
            // Companies:
            //  C0: S1 > S0
            //  C1: S1 > S0
            // Expected Student-Optimal Matching: (S0, C1), (S1, C0)
            // S0 proposes to C0, S1 proposes to C0. C0 takes S1, rejects S0.
            // S0 proposes to C1. C1 takes S0. Final: (S0,C1), (S1,C0).
            // S0 gets 2nd choice. S1 gets 1st choice.
            vector<vector<int>> s_prefs = {{0, 1}, {0, 1}};
            vector<vector<int>> c_prefs = {{1, 0}, {1, 0}};
 
            vector<vector<int>> s2c = convert_prefs_to_matrix(s_prefs);
            vector<vector<int>> c2s = convert_prefs_to_matrix(c_prefs);
 
            Solution sol;
            vector<int> expected_matches = {1, 0};
            ASSERT_EQ(sol.match(s2c, c2s), expected_matches);
        }

引用了 convert_prefs_to_matrix() , 以及 comp526::stable_matching::Solution::match().