Graphs - Detecting Cycles

Question: Define a function 'hasCycle' that takes in a graph and vertex, and returns true if the graph contains a cycle from that vertex, or false if it does not.

Example

                                
                                q)g:`a`b`c`d`e!(`b`c;`a`d;`a`d;`a;`z)
q)h:`a`b`c`d!(`b`c;`d`c;();())
q)hasCycle[g;`a]
1b
q)hasCycle[h;`a]
0b

Solution

                                
                                ######## solution.q ########

hasCycle:{v:();any {z,:y;raze $[1<sum z=y;1b;0b,.z.s[x;;z] each x y]}[x;y;v]}

Explanation: Perform depth first search and check whether the current vertex is contained in the visited list more than once. If so, return false, otherwise true.

Code:

https://bitbucket.org/alvikabir/dailyq/src/master/Intermediate/graphs-cycles

Tags:

algorithms dictionaries functions

Searchable Tags

algorithms api architecture asynchronous c csv data structures dictionaries disk feedhandler finance functions ingestion ipc iterators machine learning math multithreading optimizations realtime shared library sql statistics streaming strings tables temporal utility websockets

daily q

Graphs - Detecting Cycles

Example

Solution

Tags:

Searchable Tags