Skip to content

Commit

Permalink
added another test case to inc_pfxt.cpp
Browse files Browse the repository at this point in the history
  • Loading branch information
Randy1005 committed Sep 6, 2023
1 parent 51f2249 commit 4fab70f
Show file tree
Hide file tree
Showing 3 changed files with 84 additions and 40 deletions.
45 changes: 12 additions & 33 deletions ink/ink.cpp
Original file line number Diff line number Diff line change
Expand Up @@ -581,33 +581,6 @@ void Ink::dump_profile(std::ostream& os, bool reset) {
}


void Ink::modify_random_vertex() {
//std::uniform_int_distribution<uint32_t> uint_dist(0, num_verts());

//const size_t vid = uint_dist(_rng);
//auto vptr = _vptrs[vid];
//
//std::array<std::optional<float>, NUM_WEIGHTS> ws;

auto& v = insert_vertex("inst_83497:RN");

for (auto e : v.fanout) {
for (size_t i = 0; i < NUM_WEIGHTS; i++) {
*e->weights[i] -= 0.025f;
}
}

for (auto e : v.fanin) {
for (size_t i = 0; i < NUM_WEIGHTS; i++) {
*e->weights[i] -= 0.025f;
}
}




}

float Ink::vec_diff(
const std::vector<Path>& ps1,
const std::vector<Path>& ps2,
Expand Down Expand Up @@ -1085,34 +1058,40 @@ void Ink::_update_pfxt(Pfxt& pfxt) {

// iterate through the re-spur list
// and spur each node with their
// corresponding pruned edge + weights
// corresponding pruned edge/weights
for (const auto& r : _respurs) {
_spur_pruned(pfxt, *r.node, r.pruned);
}

// update _all_path_costs
// validate paths and update costs
_all_path_costs.clear();
auto max_dc = 0.0f;
for (const auto& n : pfxt.paths) {
if (!n->removed) {
_all_path_costs.push_back(n->detour_cost + *sfxt.dist());

// if not already spurred, spur here
if (n->num_children() == 0) {
_spur(pfxt, *n);
}

max_dc = std::max(n->detour_cost, max_dc);
}
}

// validate the priority queue
// TODO: is this part correct?
for (;;) {
auto node = pfxt.pop();
if (node == nullptr) {
break;
}

// std::cout << "node.dc=" << node->detour_cost << ", max_dc=" << max_dc << '\n';
if (node->removed) {
continue;
}
// update max detour cost
_all_path_costs.push_back(node->detour_cost + *sfxt.dist());
_all_path_costs.push_back(node->detour_cost + *sfxt.dist());
_spur(pfxt, *node);

if (node->detour_cost >= max_dc) {
Expand Down Expand Up @@ -1331,6 +1310,7 @@ void Ink::_spur_incremental(
// pfxt is in a valid state now
// if we already have enough paths (or costs)
// we can stop here
std::cout << "after update, all paths = " << _all_path_costs.size() << '\n';
if (_all_paths.size() >= K || _all_path_costs.size() >= K) {
return;
}
Expand Down Expand Up @@ -1927,5 +1907,4 @@ void PathHeap::dump(std::ostream& os) const {
}
}


} // end of namespace ink
6 changes: 0 additions & 6 deletions ink/ink.hpp
Original file line number Diff line number Diff line change
Expand Up @@ -325,12 +325,6 @@ class Ink {

void dump_profile(std::ostream& os, bool reset = false);

/**
@brief randomly pick a vertex and modify its fanin / fanouts
(for the purpose of measuring difference between queries)
*/
void modify_random_vertex();

/**
@brief outputs the percentage of difference between 2 path weight vectors
*/
Expand Down
73 changes: 72 additions & 1 deletion unittests/inc_pfxt.cpp
Original file line number Diff line number Diff line change
Expand Up @@ -110,7 +110,7 @@ TEST_CASE("Update Edges 2" * doctest::timeout(300)) {
REQUIRE(float_equal(costs[10], 20));
}

TEST_CASE("Report More Costs, Then Incrementally Update Pfxt" * doctest::timeout(300)) {
TEST_CASE("Update Edges 2 - Report More Costs, Then Report Less" * doctest::timeout(300)) {
ink::Ink ink;
ink.insert_edge("A", "B", -1);
ink.insert_edge("A", "C", 3);
Expand Down Expand Up @@ -199,6 +199,77 @@ TEST_CASE("Update Edges 2 (Update Different Edges)" * doctest::timeout(300)) {
REQUIRE(float_equal(costs[10], 16));
}

TEST_CASE("Update Edges 2 (Reporting Less Than All Possible Costs (11 Costs))" * doctest::timeout(300)) {
ink::Ink ink;
ink.insert_edge("A", "B", -1);
ink.insert_edge("A", "C", 3);
ink.insert_edge("C", "D", 1);
ink.insert_edge("C", "E", 2);
ink.insert_edge("D", "B", 3);

ink.insert_edge("B", "F", 1);
ink.insert_edge("B", "G", 2);
ink.insert_edge("F", "H", -4);
ink.insert_edge("F", "I", 8);
ink.insert_edge("I", "L", 4);
ink.insert_edge("I", "M", 11);

ink.insert_edge("G", "J", 5);
ink.insert_edge("G", "K", 7);

ink.report_incsfxt(8, true);

// modify F->I weight to -9, F->I becomes a suffix tree edge
ink.insert_edge("F", "I", -9);
ink.report_incremental(4, true, false, false);

auto costs = ink.get_path_costs();

REQUIRE(float_equal(costs[0], -5));
REQUIRE(float_equal(costs[1], -4));
REQUIRE(float_equal(costs[2], 2));
REQUIRE(float_equal(costs[3], 3));
}

TEST_CASE("Update Edges 2 (pfxt.paths validation check)" * doctest::timeout(300)) {
ink::Ink ink;
ink.insert_edge("A", "B", -1);
ink.insert_edge("A", "C", 3);
ink.insert_edge("C", "D", 1);
ink.insert_edge("C", "E", 2);
ink.insert_edge("D", "B", 3);

ink.insert_edge("B", "F", 1);
ink.insert_edge("B", "G", 2);
ink.insert_edge("F", "H", -4);
ink.insert_edge("F", "I", 8);
ink.insert_edge("I", "L", 4);
ink.insert_edge("I", "M", 11);

ink.insert_edge("G", "J", 5);
ink.insert_edge("G", "K", 7);

ink.report_incsfxt(3, true, false);

// modify F->I weight to -9, F->I becomes a suffix tree edge
ink.insert_edge("F", "I", -9);
ink.report_incremental(11, true, false, false);

auto costs = ink.get_path_costs();


REQUIRE(float_equal(costs[0], -5));
REQUIRE(float_equal(costs[1], -4));
REQUIRE(float_equal(costs[2], 2));
REQUIRE(float_equal(costs[3], 3));
REQUIRE(float_equal(costs[4], 4));
REQUIRE(float_equal(costs[5], 5));
REQUIRE(float_equal(costs[6], 6));
REQUIRE(float_equal(costs[7], 8));
REQUIRE(float_equal(costs[8], 10));
REQUIRE(float_equal(costs[9], 14));
REQUIRE(float_equal(costs[10], 16));
}

//TEST_CASE("Update Edges 3" * doctest::timeout(300)) {
// ink::Ink ink;
Expand Down

0 comments on commit 4fab70f

Please sign in to comment.