diff options
Diffstat (limited to 'storage/oqgraph')
| -rw-r--r-- | storage/oqgraph/graphcore.cc | 80 | ||||
| -rw-r--r-- | storage/oqgraph/graphcore.h | 1 | ||||
| -rw-r--r-- | storage/oqgraph/ha_oqgraph.cc | 31 | ||||
| -rw-r--r-- | storage/oqgraph/ha_oqgraph.h | 4 | ||||
| -rw-r--r-- | storage/oqgraph/mysql-test/oqgraph/general-Aria.result | 164 | ||||
| -rw-r--r-- | storage/oqgraph/mysql-test/oqgraph/general-MyISAM.result | 164 | ||||
| -rw-r--r-- | storage/oqgraph/mysql-test/oqgraph/general-innodb.result | 164 | ||||
| -rw-r--r-- | storage/oqgraph/mysql-test/oqgraph/general.inc | 94 | ||||
| -rwxr-xr-x | storage/oqgraph/mysql-test/oqgraph/generate_backing_table_tests_suite.sh | 1 | ||||
| -rw-r--r-- | storage/oqgraph/oqgraph_thunk.cc | 6 |
10 files changed, 687 insertions, 22 deletions
diff --git a/storage/oqgraph/graphcore.cc b/storage/oqgraph/graphcore.cc index 1a7df6147e7..d8f1fcc9b00 100644 --- a/storage/oqgraph/graphcore.cc +++ b/storage/oqgraph/graphcore.cc @@ -329,6 +329,40 @@ namespace open_query { }; template <typename P, typename D> + struct GRAPHCORE_INTERNAL oqgraph_visit_leaves + : public base_visitor< oqgraph_visit_leaves<P,D> > + { + typedef on_finish_vertex event_filter; + + oqgraph_visit_leaves(const P& p, const D& d, + stack_cursor *cursor) + : seq(0), m_cursor(*cursor), m_p(p), m_d(d) + { assert(cursor); } + + template<class T, class Graph> + void operator()(T u, Graph &g) + { + typename graph_traits<Graph>::out_edge_iterator ei, ei_end; + boost::tuples::tie(ei, ei_end) = out_edges(u, g); + if (ei == ei_end) + { + m_cursor.results.push(reference(++seq, u, m_d[ u ])); + } + } + private: + int seq; + stack_cursor &m_cursor; + P m_p; + D m_d; + }; + + template <typename P, typename D> + oqgraph_visit_leaves<P,D> + make_oqgraph_visit_leaves(const P& p, const D& d, stack_cursor *cursor) + { return oqgraph_visit_leaves<P,D>(p, d, cursor); } + + + template <typename P, typename D> struct GRAPHCORE_INTERNAL oqgraph_visit_dist : public base_visitor< oqgraph_visit_dist<P,D> > { @@ -828,6 +862,7 @@ namespace open_query case DIJKSTRAS | HAVE_ORIG: case BREADTH_FIRST | HAVE_ORIG: + case LEAVES | HAVE_ORIG: if ((cursor= new (std::nothrow) stack_cursor(share)) && (orig || dest)) { boost::unordered_map<Vertex, Vertex> p; @@ -878,6 +913,28 @@ namespace open_query ), make_two_bit_judy_map(get(vertex_index, share->g))); break; + case LEAVES: + breadth_first_visit(share->g, *orig, Q, + make_bfs_visitor( + std::make_pair( + record_predecessors( + boost::make_assoc_property_map(p), + on_tree_edge() + ), + std::make_pair( + record_distances( + boost::make_assoc_property_map(d), + on_tree_edge() + ), + make_oqgraph_visit_leaves( + boost::make_assoc_property_map(p), + boost::make_assoc_property_map(d), + static_cast<stack_cursor*>(cursor) + ) + )) + ), + make_two_bit_judy_map(get(vertex_index, share->g))); + break; default: abort(); } @@ -885,6 +942,7 @@ namespace open_query break; case BREADTH_FIRST | HAVE_DEST: case DIJKSTRAS | HAVE_DEST: + case LEAVES | HAVE_DEST: if ((cursor= new (std::nothrow) stack_cursor(share)) && (orig || dest)) { boost::unordered_map<Vertex, Vertex> p; @@ -936,6 +994,28 @@ namespace open_query ), make_two_bit_judy_map(get(vertex_index, r))); break; + case LEAVES: + breadth_first_visit(r, *dest, Q, + make_bfs_visitor( + std::make_pair( + record_predecessors( + boost::make_assoc_property_map(p), + on_tree_edge() + ), + std::make_pair( + record_distances( + boost::make_assoc_property_map(d), + on_tree_edge() + ), + make_oqgraph_visit_leaves( + boost::make_assoc_property_map(p), + boost::make_assoc_property_map(d), + static_cast<stack_cursor*>(cursor) + ) + )) + ), + make_two_bit_judy_map(get(vertex_index, r))); + break; default: abort(); } diff --git a/storage/oqgraph/graphcore.h b/storage/oqgraph/graphcore.h index 7fa3d4554bf..c954b8b029a 100644 --- a/storage/oqgraph/graphcore.h +++ b/storage/oqgraph/graphcore.h @@ -70,6 +70,7 @@ namespace open_query DIJKSTRAS = 1, BREADTH_FIRST = 2, NUM_SEARCH_OP = 3, + LEAVES = 4, ALGORITHM = 0x0ffff, HAVE_ORIG = 0x10000, diff --git a/storage/oqgraph/ha_oqgraph.cc b/storage/oqgraph/ha_oqgraph.cc index 66a20e9a6a1..bd2224e1ad2 100644 --- a/storage/oqgraph/ha_oqgraph.cc +++ b/storage/oqgraph/ha_oqgraph.cc @@ -39,7 +39,7 @@ #pragma implementation // gcc: Class implementation #endif -#include <my_config.h> +#include <my_global.h> #define MYSQL_SERVER 1 // to have THD /* For the moment, include code to deal with integer latches. * I have wrapped it with this #ifdef to make it easier to find and remove in the future. @@ -87,6 +87,7 @@ static const oqgraph_latch_op_table latch_ops_table[] = { { "", oqgraph::NO_SEARCH } , // suggested by Arjen, use empty string instead of no_search { "dijkstras", oqgraph::DIJKSTRAS } , { "breadth_first", oqgraph::BREADTH_FIRST } , + { "leaves", oqgraph::LEAVES }, { NULL, -1 } }; @@ -297,7 +298,7 @@ int ha_oqgraph::oqgraph_check_table_structure (TABLE *table_arg) Field **field= table_arg->field; for (i= 0; *field && skel[i].colname; i++, field++) { - DBUG_PRINT( "oq-debug", ("Column %d: name='%s', expected '%s'; type=%d, expected %d.", i, (*field)->field_name, skel[i].colname, (*field)->type(), skel[i].coltype)); + DBUG_PRINT( "oq-debug", ("Column %d: name='%s', expected '%s'; type=%d, expected %d.", i, (*field)->field_name.str, skel[i].colname, (*field)->type(), skel[i].coltype)); bool badColumn = false; bool isLatchColumn = strcmp(skel[i].colname, "latch")==0; bool isStringLatch = true; @@ -346,7 +347,7 @@ int ha_oqgraph::oqgraph_check_table_structure (TABLE *table_arg) push_warning_printf( current_thd, Sql_condition::WARN_LEVEL_WARN, HA_WRONG_CREATE_OPTION, "Column %d must be NULL.", i); } /* Check the column name */ - if (!badColumn) if (strcmp(skel[i].colname,(*field)->field_name)) { + if (!badColumn) if (strcmp(skel[i].colname,(*field)->field_name.str)) { badColumn = true; push_warning_printf( current_thd, Sql_condition::WARN_LEVEL_WARN, HA_WRONG_CREATE_OPTION, "Column %d must be named '%s'.", i, skel[i].colname); } @@ -562,7 +563,7 @@ int ha_oqgraph::open(const char *name, int mode, uint test_if_locked) init_tmp_table_share( thd, share, table->s->db.str, table->s->db.length, options->table_name, ""); // because of that, we need to reinitialize the memroot (to reset MY_THREAD_SPECIFIC flag) DBUG_ASSERT(share->mem_root.used == NULL); // it's still empty - init_sql_alloc(&share->mem_root, TABLE_ALLOC_BLOCK_SIZE, 0, MYF(0)); + init_sql_alloc(&share->mem_root, "share", TABLE_ALLOC_BLOCK_SIZE, 0, MYF(0)); // What I think this code is doing: // * Our OQGRAPH table is `database_blah/name` @@ -577,11 +578,10 @@ int ha_oqgraph::open(const char *name, int mode, uint test_if_locked) size_t tlen= strlen(options->table_name); size_t plen= (int)(p - name) + tlen + 1; - share->path.str= (char*)alloc_root(&share->mem_root, plen + 1); // MDEV-5996 space for trailing zero - // it seems there was a misunderstanding of why there is a separate length field in the String object - strmov(strnmov(share->path.str, name, (int)(p - name) + 1), options->table_name); - - share->path.str[plen] = 0; // MDEV-5996 Make sure the pointer is zero terminated. I really think this needs refactoring, soon... + share->path.str= (char*)alloc_root(&share->mem_root, plen + 1); + strmov(strnmov((char*) share->path.str, name, (int)(p - name) + 1), + options->table_name); + DBUG_ASSERT(strlen(share->path.str) == plen); share->normalized_path.str= share->path.str; share->path.length= share->normalized_path.length= plen; @@ -622,7 +622,8 @@ int ha_oqgraph::open(const char *name, int mode, uint test_if_locked) DBUG_RETURN(-1); } - if (enum open_frm_error err= open_table_from_share(thd, share, "", + if (enum open_frm_error err= open_table_from_share(thd, share, + &empty_clex_str, (uint) (HA_OPEN_KEYFILE | HA_TRY_READ_ONLY), EXTRA_RECORD, thd->open_options, edges, FALSE)) @@ -655,7 +656,7 @@ int ha_oqgraph::open(const char *name, int mode, uint test_if_locked) for (Field **field= edges->field; *field; ++field) { - if (strcmp(options->origid, (*field)->field_name)) + if (strcmp(options->origid, (*field)->field_name.str)) continue; if ((*field)->cmp_type() != INT_RESULT || !((*field)->flags & NOT_NULL_FLAG)) @@ -680,7 +681,7 @@ int ha_oqgraph::open(const char *name, int mode, uint test_if_locked) for (Field **field= edges->field; *field; ++field) { - if (strcmp(options->destid, (*field)->field_name)) + if (strcmp(options->destid, (*field)->field_name.str)) continue; if ((*field)->type() != origid->type() || !((*field)->flags & NOT_NULL_FLAG)) @@ -703,7 +704,7 @@ int ha_oqgraph::open(const char *name, int mode, uint test_if_locked) } // Make sure origid column != destid column - if (strcmp( origid->field_name, destid->field_name)==0) { + if (strcmp( origid->field_name.str, destid->field_name.str)==0) { fprint_error("Invalid OQGRAPH backing store ('%s.destid' attribute set to same column as origid attribute)", p+1, options->table_name); closefrm(edges); free_table_share(share); @@ -712,7 +713,7 @@ int ha_oqgraph::open(const char *name, int mode, uint test_if_locked) for (Field **field= edges->field; options->weight && *field; ++field) { - if (strcmp(options->weight, (*field)->field_name)) + if (strcmp(options->weight, (*field)->field_name.str)) continue; if ((*field)->result_type() != REAL_RESULT || !((*field)->flags & NOT_NULL_FLAG)) @@ -803,7 +804,7 @@ int ha_oqgraph::write_row(byte * buf) return HA_ERR_TABLE_READONLY; } -int ha_oqgraph::update_row(const byte * old, byte * buf) +int ha_oqgraph::update_row(const uchar * old, const uchar * buf) { return HA_ERR_TABLE_READONLY; } diff --git a/storage/oqgraph/ha_oqgraph.h b/storage/oqgraph/ha_oqgraph.h index 07f47bd1239..f06db8bbf14 100644 --- a/storage/oqgraph/ha_oqgraph.h +++ b/storage/oqgraph/ha_oqgraph.h @@ -84,7 +84,7 @@ public: int open(const char *name, int mode, uint test_if_locked); int close(void); int write_row(byte * buf); - int update_row(const byte * old_data, byte * new_data); + int update_row(const uchar * old_data, const uchar * new_data); int delete_row(const byte * buf); int index_read(byte * buf, const byte * key, uint key_len, enum ha_rkey_function find_flag); @@ -118,7 +118,7 @@ public: virtual const char *table_type() const { return hton_name(ht)->str; } #endif - my_bool register_query_cache_table(THD *thd, char *table_key, + my_bool register_query_cache_table(THD *thd, const char *table_key, uint key_length, qc_engine_callback *engine_callback, diff --git a/storage/oqgraph/mysql-test/oqgraph/general-Aria.result b/storage/oqgraph/mysql-test/oqgraph/general-Aria.result index e527705045f..bd0f7ed9ee8 100644 --- a/storage/oqgraph/mysql-test/oqgraph/general-Aria.result +++ b/storage/oqgraph/mysql-test/oqgraph/general-Aria.result @@ -195,6 +195,170 @@ from to SELECT linkid as `from`, destid as `to` FROM graph where latch='0' and destid = 10; from to 12 10 +# Leaves search tests +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 1; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 2; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 3; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 4; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 5; +latch origid destid weight seq linkid +leaves 5 NULL 1 1 7 +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 6; +latch origid destid weight seq linkid +leaves 6 NULL 2 1 7 +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 7; +latch origid destid weight seq linkid +leaves 7 NULL 0 1 7 +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 8; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 9; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 10; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 11; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 12; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 1; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 2; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 3; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 4; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 5; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 6; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 7; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 8; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 9; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 10; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 11; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 12; +latch origid destid weight seq linkid +INSERT INTO graph_base(from_id, to_id) VALUES (10,13); +INSERT INTO graph_base(from_id, to_id) VALUES (11,14); +INSERT INTO graph_base(from_id, to_id) VALUES (12,15); +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 10; +latch origid destid weight seq linkid +leaves 10 NULL 3 3 15 +leaves 10 NULL 2 2 14 +leaves 10 NULL 1 1 13 +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 11; +latch origid destid weight seq linkid +leaves 11 NULL 3 3 13 +leaves 11 NULL 2 2 15 +leaves 11 NULL 1 1 14 +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 12; +latch origid destid weight seq linkid +leaves 12 NULL 3 3 14 +leaves 12 NULL 2 2 13 +leaves 12 NULL 1 1 15 +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 13; +latch origid destid weight seq linkid +leaves 13 NULL 0 1 13 +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 14; +latch origid destid weight seq linkid +leaves 14 NULL 0 1 14 +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 15; +latch origid destid weight seq linkid +leaves 15 NULL 0 1 15 +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 10; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 11; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 12; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 13; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 14; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 15; +latch origid destid weight seq linkid +DELETE FROM graph_base where from_id=10 and to_id=13; +DELETE FROM graph_base where from_id=11 and to_id=14; +DELETE FROM graph_base where from_id=12 and to_id=15; +INSERT INTO graph_base(from_id, to_id) VALUES (13,10); +INSERT INTO graph_base(from_id, to_id) VALUES (14,11); +INSERT INTO graph_base(from_id, to_id) VALUES (15,12); +INSERT INTO graph_base(from_id, to_id) VALUES (16,1); +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 10; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 11; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 12; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 13; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 14; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 15; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 16; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 10; +latch origid destid weight seq linkid +leaves NULL 10 3 3 14 +leaves NULL 10 2 2 15 +leaves NULL 10 1 1 13 +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 11; +latch origid destid weight seq linkid +leaves NULL 11 3 3 15 +leaves NULL 11 2 2 13 +leaves NULL 11 1 1 14 +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 12; +latch origid destid weight seq linkid +leaves NULL 12 3 3 13 +leaves NULL 12 2 2 14 +leaves NULL 12 1 1 15 +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 13; +latch origid destid weight seq linkid +leaves NULL 13 0 1 13 +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 14; +latch origid destid weight seq linkid +leaves NULL 14 0 1 14 +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 15; +latch origid destid weight seq linkid +leaves NULL 15 0 1 15 +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 1; +latch origid destid weight seq linkid +leaves NULL 1 1 1 16 +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 2; +latch origid destid weight seq linkid +leaves NULL 2 2 1 16 +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 3; +latch origid destid weight seq linkid +leaves NULL 3 2 1 16 +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 4; +latch origid destid weight seq linkid +leaves NULL 4 3 1 16 +DELETE FROM graph_base where from_id=13 and to_id=10; +DELETE FROM graph_base where from_id=14 and to_id=11; +DELETE FROM graph_base where from_id=15 and to_id=12; +DELETE FROM graph_base where from_id=16 and to_id=1; +SELECT * FROM graph WHERE latch='leaves' AND origid=1 AND destid=2; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch='leaves' AND origid=1 AND destid=3; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch='leaves' AND origid=1 AND destid=4; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch='leaves' AND origid=6 AND destid=7; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch='leaves' AND origid=10 AND destid=11; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch='leaves' AND origid=10 AND destid=12; +latch origid destid weight seq linkid # Breadth-first search tests SELECT * FROM graph WHERE latch = 'breadth_first' AND origid = 1; latch origid destid weight seq linkid diff --git a/storage/oqgraph/mysql-test/oqgraph/general-MyISAM.result b/storage/oqgraph/mysql-test/oqgraph/general-MyISAM.result index bbf660e7db4..e5b5e958fdf 100644 --- a/storage/oqgraph/mysql-test/oqgraph/general-MyISAM.result +++ b/storage/oqgraph/mysql-test/oqgraph/general-MyISAM.result @@ -195,6 +195,170 @@ from to SELECT linkid as `from`, destid as `to` FROM graph where latch='0' and destid = 10; from to 12 10 +# Leaves search tests +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 1; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 2; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 3; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 4; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 5; +latch origid destid weight seq linkid +leaves 5 NULL 1 1 7 +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 6; +latch origid destid weight seq linkid +leaves 6 NULL 2 1 7 +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 7; +latch origid destid weight seq linkid +leaves 7 NULL 0 1 7 +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 8; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 9; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 10; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 11; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 12; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 1; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 2; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 3; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 4; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 5; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 6; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 7; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 8; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 9; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 10; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 11; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 12; +latch origid destid weight seq linkid +INSERT INTO graph_base(from_id, to_id) VALUES (10,13); +INSERT INTO graph_base(from_id, to_id) VALUES (11,14); +INSERT INTO graph_base(from_id, to_id) VALUES (12,15); +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 10; +latch origid destid weight seq linkid +leaves 10 NULL 3 3 15 +leaves 10 NULL 2 2 14 +leaves 10 NULL 1 1 13 +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 11; +latch origid destid weight seq linkid +leaves 11 NULL 3 3 13 +leaves 11 NULL 2 2 15 +leaves 11 NULL 1 1 14 +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 12; +latch origid destid weight seq linkid +leaves 12 NULL 3 3 14 +leaves 12 NULL 2 2 13 +leaves 12 NULL 1 1 15 +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 13; +latch origid destid weight seq linkid +leaves 13 NULL 0 1 13 +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 14; +latch origid destid weight seq linkid +leaves 14 NULL 0 1 14 +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 15; +latch origid destid weight seq linkid +leaves 15 NULL 0 1 15 +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 10; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 11; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 12; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 13; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 14; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 15; +latch origid destid weight seq linkid +DELETE FROM graph_base where from_id=10 and to_id=13; +DELETE FROM graph_base where from_id=11 and to_id=14; +DELETE FROM graph_base where from_id=12 and to_id=15; +INSERT INTO graph_base(from_id, to_id) VALUES (13,10); +INSERT INTO graph_base(from_id, to_id) VALUES (14,11); +INSERT INTO graph_base(from_id, to_id) VALUES (15,12); +INSERT INTO graph_base(from_id, to_id) VALUES (16,1); +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 10; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 11; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 12; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 13; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 14; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 15; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 16; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 10; +latch origid destid weight seq linkid +leaves NULL 10 3 3 14 +leaves NULL 10 2 2 15 +leaves NULL 10 1 1 13 +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 11; +latch origid destid weight seq linkid +leaves NULL 11 3 3 15 +leaves NULL 11 2 2 13 +leaves NULL 11 1 1 14 +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 12; +latch origid destid weight seq linkid +leaves NULL 12 3 3 13 +leaves NULL 12 2 2 14 +leaves NULL 12 1 1 15 +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 13; +latch origid destid weight seq linkid +leaves NULL 13 0 1 13 +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 14; +latch origid destid weight seq linkid +leaves NULL 14 0 1 14 +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 15; +latch origid destid weight seq linkid +leaves NULL 15 0 1 15 +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 1; +latch origid destid weight seq linkid +leaves NULL 1 1 1 16 +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 2; +latch origid destid weight seq linkid +leaves NULL 2 2 1 16 +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 3; +latch origid destid weight seq linkid +leaves NULL 3 2 1 16 +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 4; +latch origid destid weight seq linkid +leaves NULL 4 3 1 16 +DELETE FROM graph_base where from_id=13 and to_id=10; +DELETE FROM graph_base where from_id=14 and to_id=11; +DELETE FROM graph_base where from_id=15 and to_id=12; +DELETE FROM graph_base where from_id=16 and to_id=1; +SELECT * FROM graph WHERE latch='leaves' AND origid=1 AND destid=2; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch='leaves' AND origid=1 AND destid=3; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch='leaves' AND origid=1 AND destid=4; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch='leaves' AND origid=6 AND destid=7; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch='leaves' AND origid=10 AND destid=11; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch='leaves' AND origid=10 AND destid=12; +latch origid destid weight seq linkid # Breadth-first search tests SELECT * FROM graph WHERE latch = 'breadth_first' AND origid = 1; latch origid destid weight seq linkid diff --git a/storage/oqgraph/mysql-test/oqgraph/general-innodb.result b/storage/oqgraph/mysql-test/oqgraph/general-innodb.result index 927d856bc84..38e3e0a23b4 100644 --- a/storage/oqgraph/mysql-test/oqgraph/general-innodb.result +++ b/storage/oqgraph/mysql-test/oqgraph/general-innodb.result @@ -195,6 +195,170 @@ from to SELECT linkid as `from`, destid as `to` FROM graph where latch='0' and destid = 10; from to 12 10 +# Leaves search tests +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 1; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 2; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 3; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 4; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 5; +latch origid destid weight seq linkid +leaves 5 NULL 1 1 7 +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 6; +latch origid destid weight seq linkid +leaves 6 NULL 2 1 7 +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 7; +latch origid destid weight seq linkid +leaves 7 NULL 0 1 7 +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 8; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 9; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 10; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 11; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 12; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 1; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 2; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 3; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 4; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 5; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 6; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 7; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 8; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 9; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 10; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 11; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 12; +latch origid destid weight seq linkid +INSERT INTO graph_base(from_id, to_id) VALUES (10,13); +INSERT INTO graph_base(from_id, to_id) VALUES (11,14); +INSERT INTO graph_base(from_id, to_id) VALUES (12,15); +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 10; +latch origid destid weight seq linkid +leaves 10 NULL 3 3 15 +leaves 10 NULL 2 2 14 +leaves 10 NULL 1 1 13 +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 11; +latch origid destid weight seq linkid +leaves 11 NULL 3 3 13 +leaves 11 NULL 2 2 15 +leaves 11 NULL 1 1 14 +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 12; +latch origid destid weight seq linkid +leaves 12 NULL 3 3 14 +leaves 12 NULL 2 2 13 +leaves 12 NULL 1 1 15 +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 13; +latch origid destid weight seq linkid +leaves 13 NULL 0 1 13 +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 14; +latch origid destid weight seq linkid +leaves 14 NULL 0 1 14 +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 15; +latch origid destid weight seq linkid +leaves 15 NULL 0 1 15 +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 10; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 11; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 12; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 13; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 14; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 15; +latch origid destid weight seq linkid +DELETE FROM graph_base where from_id=10 and to_id=13; +DELETE FROM graph_base where from_id=11 and to_id=14; +DELETE FROM graph_base where from_id=12 and to_id=15; +INSERT INTO graph_base(from_id, to_id) VALUES (13,10); +INSERT INTO graph_base(from_id, to_id) VALUES (14,11); +INSERT INTO graph_base(from_id, to_id) VALUES (15,12); +INSERT INTO graph_base(from_id, to_id) VALUES (16,1); +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 10; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 11; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 12; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 13; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 14; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 15; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 16; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 10; +latch origid destid weight seq linkid +leaves NULL 10 3 3 14 +leaves NULL 10 2 2 15 +leaves NULL 10 1 1 13 +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 11; +latch origid destid weight seq linkid +leaves NULL 11 3 3 15 +leaves NULL 11 2 2 13 +leaves NULL 11 1 1 14 +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 12; +latch origid destid weight seq linkid +leaves NULL 12 3 3 13 +leaves NULL 12 2 2 14 +leaves NULL 12 1 1 15 +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 13; +latch origid destid weight seq linkid +leaves NULL 13 0 1 13 +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 14; +latch origid destid weight seq linkid +leaves NULL 14 0 1 14 +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 15; +latch origid destid weight seq linkid +leaves NULL 15 0 1 15 +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 1; +latch origid destid weight seq linkid +leaves NULL 1 1 1 16 +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 2; +latch origid destid weight seq linkid +leaves NULL 2 2 1 16 +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 3; +latch origid destid weight seq linkid +leaves NULL 3 2 1 16 +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 4; +latch origid destid weight seq linkid +leaves NULL 4 3 1 16 +DELETE FROM graph_base where from_id=13 and to_id=10; +DELETE FROM graph_base where from_id=14 and to_id=11; +DELETE FROM graph_base where from_id=15 and to_id=12; +DELETE FROM graph_base where from_id=16 and to_id=1; +SELECT * FROM graph WHERE latch='leaves' AND origid=1 AND destid=2; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch='leaves' AND origid=1 AND destid=3; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch='leaves' AND origid=1 AND destid=4; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch='leaves' AND origid=6 AND destid=7; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch='leaves' AND origid=10 AND destid=11; +latch origid destid weight seq linkid +SELECT * FROM graph WHERE latch='leaves' AND origid=10 AND destid=12; +latch origid destid weight seq linkid # Breadth-first search tests SELECT * FROM graph WHERE latch = 'breadth_first' AND origid = 1; latch origid destid weight seq linkid diff --git a/storage/oqgraph/mysql-test/oqgraph/general.inc b/storage/oqgraph/mysql-test/oqgraph/general.inc index f27b7585dd7..48960f7cadb 100644 --- a/storage/oqgraph/mysql-test/oqgraph/general.inc +++ b/storage/oqgraph/mysql-test/oqgraph/general.inc @@ -120,6 +120,100 @@ SELECT linkid as `from`, destid as `to` FROM graph where latch='0' and destid = SELECT linkid as `from`, destid as `to` FROM graph where latch='0' and destid = 9; SELECT linkid as `from`, destid as `to` FROM graph where latch='0' and destid = 10; +--echo # Leaves search tests +#-- We are asking "Are there nodes reachable from origid, from which no other nodes can be reached" +#-- We return a row for each leaf node that is reachable, with its id in 'linkid' +#-- and the weight calculated as "How many _directed_ hops to get there" +#-- If there is no path from origid to another node then there is no row for that linkid +#-- 'seq' is the counted distance of the search, thus, the loop link will always have seq 1 +#-- if there are two reachable neighbours, they will have seq 2,3 and so on +#-- linkid is the other end +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 1; +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 2; +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 3; +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 4; +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 5; +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 6; +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 7; +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 8; +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 9; +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 10; +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 11; +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 12; + +#-- now do it in reverse - using destid find originating vertices +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 1; +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 2; +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 3; +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 4; +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 5; +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 6; +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 7; +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 8; +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 9; +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 10; +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 11; +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 12; + +# Add more leaf nodes +INSERT INTO graph_base(from_id, to_id) VALUES (10,13); +INSERT INTO graph_base(from_id, to_id) VALUES (11,14); +INSERT INTO graph_base(from_id, to_id) VALUES (12,15); + +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 10; +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 11; +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 12; +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 13; +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 14; +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 15; +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 10; +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 11; +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 12; +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 13; +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 14; +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 15; + +DELETE FROM graph_base where from_id=10 and to_id=13; +DELETE FROM graph_base where from_id=11 and to_id=14; +DELETE FROM graph_base where from_id=12 and to_id=15; + +# Add some root nodes +INSERT INTO graph_base(from_id, to_id) VALUES (13,10); +INSERT INTO graph_base(from_id, to_id) VALUES (14,11); +INSERT INTO graph_base(from_id, to_id) VALUES (15,12); +INSERT INTO graph_base(from_id, to_id) VALUES (16,1); + +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 10; +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 11; +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 12; +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 13; +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 14; +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 15; +SELECT * FROM graph WHERE latch = 'leaves' AND origid = 16; +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 10; +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 11; +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 12; +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 13; +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 14; +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 15; +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 1; +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 2; +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 3; +SELECT * FROM graph WHERE latch = 'leaves' AND destid = 4; + +DELETE FROM graph_base where from_id=13 and to_id=10; +DELETE FROM graph_base where from_id=14 and to_id=11; +DELETE FROM graph_base where from_id=15 and to_id=12; +DELETE FROM graph_base where from_id=16 and to_id=1; + +# path queries yield no result with "leaves" +SELECT * FROM graph WHERE latch='leaves' AND origid=1 AND destid=2; +SELECT * FROM graph WHERE latch='leaves' AND origid=1 AND destid=3; +SELECT * FROM graph WHERE latch='leaves' AND origid=1 AND destid=4; +SELECT * FROM graph WHERE latch='leaves' AND origid=6 AND destid=7; +SELECT * FROM graph WHERE latch='leaves' AND origid=10 AND destid=11; +SELECT * FROM graph WHERE latch='leaves' AND origid=10 AND destid=12; + --echo # Breadth-first search tests #-- We are asking "Is there a path from node 'origid' to (all) other nodes?" #-- We return a row for each other node that is reachable, with its id in 'linkid' diff --git a/storage/oqgraph/mysql-test/oqgraph/generate_backing_table_tests_suite.sh b/storage/oqgraph/mysql-test/oqgraph/generate_backing_table_tests_suite.sh index 22feaab5c3a..894607fd9dc 100755 --- a/storage/oqgraph/mysql-test/oqgraph/generate_backing_table_tests_suite.sh +++ b/storage/oqgraph/mysql-test/oqgraph/generate_backing_table_tests_suite.sh @@ -30,7 +30,6 @@ EOF done # These engines need an extra check to see if thy are compiled -# Note, including innodb will also test xtradb ENGINES2="innodb" for ENGINE in $ENGINES2 ; do cat > general-$ENGINE.test <<EOF diff --git a/storage/oqgraph/oqgraph_thunk.cc b/storage/oqgraph/oqgraph_thunk.cc index 2ebd0171f9c..5e254450a2b 100644 --- a/storage/oqgraph/oqgraph_thunk.cc +++ b/storage/oqgraph/oqgraph_thunk.cc @@ -22,13 +22,12 @@ ====================================================================== */ -#include <my_config.h> +#define MYSQL_SERVER +#include <my_global.h> #include "oqgraph_thunk.h" #include <boost/tuple/tuple.hpp> -#define MYSQL_SERVER -#include <my_global.h> #include "unireg.h" #include "sql_base.h" #include "table.h" @@ -40,7 +39,6 @@ #define user_defined_key_parts key_parts #endif - static int debugid = 0; oqgraph3::vertex_id oqgraph3::edge_info::origid() const |