oqgraph-dev team mailing list archive
-
oqgraph-dev team
-
Mailing list archive
-
Message #00323
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