Debian (Unstable)

Hi, Harry

The reason this is not returning the result you expect is because the graph links are treated directionally by OQGraph.

In this particular case, there is an edge from vertex 27 to vertex 6. There are however no edges to vertex 27 from vertex 6.

If you were to add a row with `origid=6` and `destid=27` to your backing table you will get the result you are expecting, subject to the following caveat:

Tl;DR

Because of the need to support a fixed set of result columns but different results sets having a different meaning attributable to different latch commands and where clauses, it is necessary for OQGraph to overload the meanings of the result columns.

This is hopefully accurately described in the table at https://mariadb.com/kb/en/oqgraph-examples/ ; it may not be, in which case it should be fixed, please let me know.

In the case of a BFS and destid query, the vertices that exist on all paths to the requested destid are returned in the `linkid` column, with `origid` is always returned as NULL. The `weight` column records the number of hops from destid. A 'self' row with `destid`==`linkid` and `weight`==0 is always returned provided `destid` is found in the graph; if `destid` is not found an empty result is returned.

The weight has no bearing in the basic breadth first search algorithm; the actual library used is described at http://www.boost.org/doc/libs/1_55_0/libs/graph/doc/breadth_first_search.html

Here is a longer example:

NSERT INTO graph_base(from_id, to_id, weight) VALUES (13,37,12);

INSERT INTO graph_base(from_id, to_id, weight) VALUES (7,5,5);

INSERT INTO graph_base(from_id, to_id, weight) VALUES (16,15,10);

INSERT INTO graph_base(from_id, to_id, weight) VALUES (17,1,6);

INSERT INTO graph_base(from_id, to_id, weight) VALUES (18,1,6);

INSERT INTO graph_base(from_id, to_id, weight) VALUES (19,1,6);

INSERT INTO graph_base(from_id, to_id, weight) VALUES (20,4,6);

INSERT INTO graph_base(from_id, to_id, weight) VALUES (27,6,6);

INSERT INTO graph_base(from_id, to_id, weight) VALUES (6,27,6);

INSERT INTO graph_base(from_id, to_id, weight) VALUES (6,55,5);

INSERT INTO graph_base(from_id, to_id, weight) VALUES (6,13,14);

SELECT * FROM graph WHERE latch='breadth_first' and destid=6;

latch	origid	destid	weight	seq	linkid

breadth_first	NULL	6	2	5	37

breadth_first	NULL	6	1	4	55

breadth_first	NULL	6	1	3	27

breadth_first	NULL	6	1	2	13

breadth_first	NULL	6	0	1	6

INSERT INTO graph_base(from_id, to_id, weight) VALUES (13,17,12);

SELECT * FROM graph WHERE latch='breadth_first' and destid=6;

latch	origid	destid	weight	seq	linkid

breadth_first	NULL	6	3	7	1

breadth_first	NULL	6	2	6	37

breadth_first	NULL	6	2	5	17

breadth_first	NULL	6	1	4	55

breadth_first	NULL	6	1	3	27

breadth_first	NULL	6	1	2	13

breadth_first	NULL	6	0	1	6

Note that the vertices that form a path to the requested `destid` are actually returned in the 'linkid' column, origid being unused and set to NULL. I am unsure as to why it is overloaded this way, it may be for backwards compatibility reasons, but I speculate.

HTH,
Andrew

I just noticed that djkistras with only origid or destid is not documented either.

This command seems to find all nodes connected to the requested node, and reports the sum of weights along the path to all nodes. I will update the wiki if I can.

Adding another link would ruin the directional of the graph I am working with. Do you have suggestions on how to see all vertex connected to a destination vertex, or would that require the use of the far more expensive Johnsons algorithm?

FWIW, I think this is a duplicate of MDEV-10980, which was recently fixed in 10.0, 10.1 and 10.2.