← Back to team overview

oqgraph-dev team mailing list archive

Re: Reverse graph queries

 

Hi Andrew,

Thanks so much for the tip. That was it! I can't imagine it was that simple, 
would have never guessed that change on my own :(

My latest changes are here: 
https://github.com/pprkut/mariadb/commits/oqgraph-leaves

It's *almost* working now.

I created a small test graph:

INSERT INTO oq_backing (origid, destid) VALUES (0,1), (1,2), (2,3),(3,4), 
(4,5), (5,6);

On this set
- "dijkstra" forward/backward and shortest path works correctly.
- "leaves" forward and backward works as well.
- "breadth_first" backward and shortest path works also.

"breadth_first" forward, however, gives me an erroneous line:

MariaDB [oqgraph]> SELECT * FROM oq_graph WHERE latch = 'breadth_first' AND 
origid = 2;
+---------------+--------+--------+--------+------+--------+
| latch         | origid | destid | weight | seq  | linkid |
+---------------+--------+--------+--------+------+--------+
| breadth_first |      2 |   NULL |      4 |    1 |      6 |
| breadth_first |      2 |   NULL |      4 |    5 |      6 |
| breadth_first |      2 |   NULL |      3 |    4 |      5 |
| breadth_first |      2 |   NULL |      2 |    3 |      4 |
| breadth_first |      2 |   NULL |      1 |    2 |      3 |
| breadth_first |      2 |   NULL |      0 |    1 |      2 |
+---------------+--------+--------+--------+------+--------+

comparing to dijkstra:

MariaDB [oqgraph]> SELECT * FROM oq_graph WHERE latch = 'dijkstras' AND origid 
= 2;
+-----------+--------+--------+--------+------+--------+
| latch     | origid | destid | weight | seq  | linkid |
+-----------+--------+--------+--------+------+--------+
| dijkstras |      2 |   NULL |      4 |    5 |      6 |
| dijkstras |      2 |   NULL |      3 |    4 |      5 |
| dijkstras |      2 |   NULL |      2 |    3 |      4 |
| dijkstras |      2 |   NULL |      1 |    2 |      3 |
| dijkstras |      2 |   NULL |      0 |    1 |      2 |
+-----------+--------+--------+--------+------+--------+

Any idea?

Grs,
Heinz

On Wednesday, 19 October 2016 21:13:25 CEST Andrew McDonnell wrote:
> Hi Heinz,
> 
> is your code up on github or somewhere? These errors can be a bit hard to
> diagnose in isolation.
> 
> At a guess though, it looks like there is an equality operator that is a
> member function without a const suffix and its it being used to compare a
> const object.
> 
> Although operator== should nearly always be const.
> 
> i.e.
> 
> class in_edge_iterator /*...*/ {
> /*...*/
> 
>    bool operator==(const self&) { ... }               <--- wrong
> 
>    bool operator==(const self&) const { ... }         <--- correct
> 
> 
> HTH,
> Andrew
> 
> On 18/10/16 05:56, Heinz Wiesinger wrote:
> > Hi Andrew,
> > 
> > Thanks for the offer! I'm currently mostly stuck on trying to understand
> > the compile error I'm getting (attached). There's simply too much
> > information there and I don't know which is the bit I need to focus on.
> > 
> > There is
> > 
> > error: no match for ‘operator==’  (operand types are ‘const
> > oqgraph3::in_edge_iterator’ and ‘const oqgraph3::in_edge_iterator’)
> > note: candidate: bool oqgraph3::in_edge_iterator::operator==(const self&)
> > <near match>
> > 
> > and
> > 
> > error: no match for ‘operator*’ (operand type is ‘const
> > oqgraph3::in_edge_iterator’)
> > note: candidate: oqgraph3::in_edge_iterator::value_type
> > oqgraph3::in_edge_iterator::operator*() <near match>
> > 
> > and
> > 
> > note:   ‘const oqgraph3::in_edge_iterator’ is not derived from ‘const
> > boost::iterators::iterator_facade<Derived1, V1, TC1, Reference1,
> > Difference1>’
> > 
> > which look like the most-likely suspects, but there might be something
> > else I don't see currently.
> > 
> > If these are indeed the points to tackle, then I'm not really sure what to
> > do...
> > 
> > Grs,
> > Heinz
> > 
> > On Monday, 17 October 2016 18:08:57 CEST Andrew McDonnell wrote:
> >> Hi Heinz
> >> 
> >> Unfortunately I havent looked at any of this for some time.
> >> 
> >> Please do let me know areas you need help, and I can at least try and
> >> guide
> >> you through, with luck we can muddle through together
> >> 
> >> cheers,
> >> Andrew
> >> 
> >> On 08/10/16 19:45, Heinz Wiesinger wrote:
> >>> Hello all!
> >>> 
> >>> As part of finishing up the implementation of my "leaves" algorithm I
> >>> looked into reverse qraph queries and unfortunately found that none of
> >>> them work as expected :(
> >>> 
> >>> Bug filed: https://jira.mariadb.org/browse/MDEV-10980
> >>> 
> >>> I tried looking into the code and saw that a reverse graph is generated
> >>> 
> >>> reverse_graph<Graph> r(share->g);
> >>> 
> >>> but not used. Simply replacing the uses (replace share->g with r)
> >>> however
> >>> results in compiler errors about missing operator overloads in the
> >>> iterators. I can try fix this but I would need some pointers, as it is,
> >>> it is slightly beyond me :(
> >>> 
> >>> Grs,
> >>> Heinz

Attachment: signature.asc
Description: This is a digitally signed message part.


Follow ups

References