generate algebraic expression from cyclic graph #736
Conversation
|
|
||
| // Scans the graph in a DFS fashion, keeps track after the longest path length. | ||
| static void __DFSMaxDepth(QGNode *n, int level, int *max_depth, rax *visited) { | ||
| if(level > *max_depth) *max_depth = level; |
There was a problem hiding this comment.
else level=*max_depth +1
if we are going to allow cycles, consider the following query:
MATCH (a)-[]->(b)-[]->(c)-[]->(b)-[]->(d)
<level, max_len> values in this variation of dfs traversal:
a-0,0
b-1,1
c-2,2
b-3,3
returning to c
c-2, 3
returning to b
b-1,3
going to d
d-3,3
the path will end at b as start and end of the loop and will have wrong increments.
should be
a-0,0
b-1,1
c-2,2
b-3,3
d-4,4
src/algorithms/detect_cycle.c
Outdated
| @@ -13,7 +13,7 @@ | |||
| bool IsAcyclicGraph(const QueryGraph *qg) { | |||
| assert(qg); | |||
|
|
|||
| bool cycle = false; // Return value. | |||
| bool acycle = true; | |||
There was a problem hiding this comment.
I think acyclic is a more obvious variable name.
| @@ -524,20 +509,30 @@ AlgebraicExpression **AlgebraicExpression_FromQueryGraph(const QueryGraph *qg, u | |||
| return NULL; | |||
| } | |||
|
|
|||
| bool acyclic = IsAcyclicGraph(qg); | |||
There was a problem hiding this comment.
I hadn't thought of this before, but both our BFS and DFS routines are direction-agnostic, traversing incoming edges as well as outgoing. I would expect that IsAcyclicGraph needs to act similarly, no?
There was a problem hiding this comment.
No IsAcyclicGraph should conclude on the original user pattern.
(a)-[]->(b) doesn't contains a cycle, but if you like you can traverse from b to a on a reversed edge.
| uint node_count = QueryGraph_NodeCount(g); | ||
|
|
||
| // Run DFS from each node. | ||
| for(uint i = 0; i < node_count; i++) { |
There was a problem hiding this comment.
Since we're not respecting edge direction, I think that checking every node is excessive - all nodes are reachable from all other nodes. Can't we simply check all leaf nodes (either no outgoing edges or no incoming), and if no nodes match that criteria, the starting point makes no difference?
There was a problem hiding this comment.
if for every node n in degree > 0 and out degree > 0, we're dealing with a cycle and any node can be a candidate for detecting the longest path.
Otherwise there should be a node with in degree = 0 or out degree = 0, in which case this node is not part of a cycle, but leads into one.
I believe you are correct and we can reduce the number of candidates we inspect.
swilly22
force-pushed
the
longest_path_length
branch
from
f61653f
to
7776524
Compare
There was a problem hiding this comment.
This all looks good to me, approving! Dvir had a question at #736 (comment) , I'm not sure if you have a reached a consensus on that?
* generate algebraic expression from cyclic graph * improved longest path starting point candidate nomination
#726