Differences

This shows you the differences between two versions of the page.

--- retegraphprocessing:elements:prototyping:simple_algorithm [2023/06/20 10:40] – [Simple Cycle Detection within the Web Graph library] gedbadmin
+++ retegraphprocessing:elements:prototyping:simple_algorithm [2024/01/19 17:41] (current) – removed gedbadmin
@@ Line 1: / Line 1: @@
-====== Simple Algorithm Prototype ======
-===== Simple Cycle Detection =====
-==== Defining a Simple Cycle ====
-The goal of this prototype is to implement a simple algorithm for detecting simple cycles within a graph.
-Let //G = (V,E)// be a directed graph (//G//) consists of a finite set of vertices (//V//) and a finite set of edges (//E//).  Each edge describes a relationship v<sub>1</sub> -> v<sub>2</sub> where v<sub>1</sub> and v<sub>2</sub>  are distinct members of V.
-Within G a cycle of length //l// is a sequence of vertices [v<sub>0</sub>,v<sub>1</sub>,...,v<sub>//l//</sub>] where v<sub>//i//]-1</sub> -> <sub>//i//]</sub> for i = 1, 2, ...., //l//-1 and v<sub>//l//</sub> -> v<sub>1</sub>.
-The cycle is simple when each vertex in [v<sub>0</sub>,v<sub>1</sub>,...,v<sub>//l//</sub>] are distinct, so that v<sub>//i//</sub> ≠ v<sub>//j//</sub> for //i// ≠ //j//.
-==== Simple Cycle Detection using standard algorithms ====
-==== Simple Cycle Detection within the Web Graph library ====
-The Web Graph library does not include an algorithm for Cycle Detection.  However, within the scratch package for the Java source code there is a  DynamicDAG (Directed Acrylic Graph) implementation that uses topological ordering based on an algorithm for Incremental Cycle Detection.((https://github.com/vigna/webgraph/blob/master/src/it/unimi/dsi/webgraph/scratch/DynamicDAG.java#L9)) ((Haeupler, Bernhard, et al. (2012) "Incremental cycle detection, topological ordering, and strong component maintenance." //ACM Transactions on Algorithms//)).  This appears to be a prototype.
-==== Simple Cycle Detection using a Graph Database  ====
-=== Cycle Detection within Neo4J ===
-The Neo4J library provides two methods for detecting cycles: cyphter queries and the APOC library.
-Cypther is a declarative query language supported by neo4j.  ((https://neo4j.com/docs/cypher-manual/current/introduction/)).
-The following code was provided on Stack Overflow  ((https://stackoverflow.com/questions/39196706/find-all-simple-cycles-through-a-given-node-in-neo4j)) as an example where //l//=15:
-<code>
-MATCH p=(n)-[*1..15]->(n) RETURN nodes(p)
-</code>
-However, as noted in the stack overflow discussion, this simple example has many limitations:
-  - The query is expensive for larger graphs, with the cost growing exponentially as the graph size and //l// are increased.
-  - It will return cycles consisting of a single vertex.  To avoid this a minimum depth of 2 is required.
-  - It detects cycles that include duplicate vertices.  A more complex query is necessary to eliminate duplicates for the detection of simple graphs.
-For detecting cycles in a more convenient and better performing way the APOC library provides the ''apoc.nodes.cycles'' procedure for detecting all path cycles from a node list.  ((https://neo4j.com/labs/apoc/4.3/overview/apoc.nodes/apoc.nodes.cycles/))
-The signature for the procedure is as follows:
-<code>
-apoc.nodes.cycles(nodes :: LIST? OF NODE?, config = {} :: MAP?) :: (path :: PATH?)
-</code>
-The documentation provides the following example:
-<code>
-CREATE (m1:Start {bar: 'alpha'}) with m1 CREATE (m1)-[:DEPENDS_ON {id: 0}]->(m2:Module {bar: 'one'})-[:DEPENDS_ON {id: 1}]->(m3:Module {bar: 'two'})-[:DEPENDS_ON {id: 2}]->(m1)  WITH m1, m2, m3 CREATE (m1)-[:DEPENDS_ON {id: 3}]->(m2), (m2)-[:ANOTHER {id: 4}]->(m3), (m2)-[:DEPENDS_ON {id: 5}]->(m3) CREATE (m1)-[:DEPENDS_ON {id: 6}]->(:Module {bar: 'seven'})-[:DEPENDS_ON {id: 7}]->(:Module {bar: 'eight'})-[:DEPENDS_ON {id: 8}]->(m1);
-CREATE (m1:Start {bar: 'beta'}) with m1 CREATE (m1)-[:MY_REL {id: 9}]->(m2:Module {bar: 'three'})-[:MY_REL  {id: 10}]->(m3:Module {bar: 'four'})-[:MY_REL {id: 11}]->(m1);
-CREATE (m1:Start {bar: 'gamma'}) with m1 CREATE (m1)-[:DEPENDS_ON {id: 12}]->(m2:Module {bar: 'five'})-[:DEPENDS_ON {id: 13}]->(m3:Module {bar: 'six'});
-CREATE (m1:Start {bar: 'delta'}) with m1 CREATE (m1)-[:DEPENDS_ON {id: 20}]->(m1);
-CREATE (m1:Start {bar: 'epsilon'}) with m1 CREATE (m1)-[:DEPTH_ONE {id: 30}]->(:Module {bar: 'seven'})-[:DEPTH_ONE {id: 31}]->(m1);
-MATCH (m1:Start) WITH collect(m1) as nodes CALL apoc.nodes.cycles(nodes) YIELD path RETURN path
-</code>
-=== Cycle Detection within Tinkerpop ===
-The Apache Tinkerpop documentation provides a recipe for Cycle Detection ((https://tinkerpop.apache.org/docs/current/recipes/#cycle-detection)).
-The following code detects cycles of arbitrary length.
-<code>
-g.V().as('a').repeat(both().simplePath()).emit(loops().is(gt(1))).
-  both().where(eq('a')).path().
-  dedup().by(unfold().order().by(id).dedup().fold())
-</code>
-This code takes advantage of the the following Gremlin steps:
-  * simplePath() step to ensure that no vertex is repeated within the cycle ((https://tinkerpop.apache.org/docs/3.6.4/reference/#simplepath-step)).
-  * loops() step to count the number of times a loop is repeated ((https://tinkerpop.apache.org/docs/3.6.4/reference/#loops-step)).
-  * dedup() step to remove repeated objects ((https://tinkerpop.apache.org/docs/3.6.4/reference/#dedup-step)).
-These loops() ad dedup() steps indicate inefficiencies in the recipe.  The query tests for loops greater than 1.  This means that a cycle is detected once it has been repeated twice, rather than when the first repeated node is detected.  The use of deduplication means that redundant cycles are discovered and then eliminated.
-====== References ======
-* Golumbic, M. C. (2004). Algorithmic Graph Theory and Perfect Graphs (2nd ed., Chapter 1 - Graph Theoretic Foundations). North Holland Publishing Company, a Subsidiary of Eslevier.