Differences

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

--- retegraphprocessing:elements:prototyping:simple_algorithm [2023/06/12 06:01] – [Simple Algorithm Prototype] 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 ====
-==== 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 Gre ===
-====== 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.