oqgraph-dev team mailing list archive

[Heinz Wiesinger <HMWiesinger@xxxxxxxxxxx>]

Hi Andrew!

I figured it out! :)
I followed your suggestion to implement the tests, but decided to first 
reorder the commits (so verify the bugfix independently from the new 
algorithm), and found that the fix itself was actually working. It was the new 
algorithm that broke things again, and then found the missing "break" 
statement in the switch clause....

Fixed that, added some more tests and now both the fix and the new algorithm 
look rather solid :)

With both of them in good state now I'd like to open pull requests with 
MariaDB. Any objections? :)

Grs,
Heinz

On Thursday, 20 October 2016 21:56:05 CEST Heinz Wiesinger wrote:
> 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.