From 19a8d4e867321a8c7ef1945cb66e4eeda3cadbe3 Mon Sep 17 00:00:00 2001 From: Thomas Walker Lynch Date: Mon, 13 Jan 2025 09:50:18 +0000 Subject: [PATCH] example/IndexTree -> example/IndexTreeGraph now that it is a graph example. --- "developer/document\360\237\226\211/bugs.txt" | 5 + .../diagonal_traversal.txt" | 92 ++++++++++++++++++- .../{IndexTree => IndexTreeGraph}/Graph.java | 0 .../{IndexTree => IndexTreeGraph}/Label.java | 0 .../{IndexTree => IndexTreeGraph}/Node.java | 0 .../SRTM_Child.java | 0 .../SRTM_Diagonal.java | 92 +++---------------- .../SRTM_Diagonal_CLI.java | 0 .../SRTM_Diagonal_transcript.txt | 0 .../four_down_four_across_CLI.java | 0 .../four_down_four_across_transcript.txt | 0 11 files changed, 109 insertions(+), 80 deletions(-) rename developer/example/{IndexTree => IndexTreeGraph}/Graph.java (100%) rename developer/example/{IndexTree => IndexTreeGraph}/Label.java (100%) rename developer/example/{IndexTree => IndexTreeGraph}/Node.java (100%) rename developer/example/{IndexTree => IndexTreeGraph}/SRTM_Child.java (100%) rename developer/example/{IndexTree => IndexTreeGraph}/SRTM_Diagonal.java (53%) rename developer/example/{IndexTree => IndexTreeGraph}/SRTM_Diagonal_CLI.java (100%) rename developer/example/{IndexTree => IndexTreeGraph}/SRTM_Diagonal_transcript.txt (100%) rename developer/example/{IndexTree => IndexTreeGraph}/four_down_four_across_CLI.java (100%) rename developer/example/{IndexTree => IndexTreeGraph}/four_down_four_across_transcript.txt (100%) diff --git "a/developer/document\360\237\226\211/bugs.txt" "b/developer/document\360\237\226\211/bugs.txt" index 54e96f2..2a42aef 100644 --- "a/developer/document\360\237\226\211/bugs.txt" +++ "b/developer/document\360\237\226\211/bugs.txt" @@ -3,3 +3,8 @@ 2024-12-31T01:47:53Z The pencil on file names has been working well .. until yesterday. The jvm doesn't like the `example🖉` directory and refuses to run code in it, so I had to change it to `example`. + + 2024-12-31T01:47:53Z + + The example directory turns out to be mixed content anyway. + diff --git "a/developer/document\360\237\226\211/diagonal_traversal.txt" "b/developer/document\360\237\226\211/diagonal_traversal.txt" index b10710f..fb50b4f 100644 --- "a/developer/document\360\237\226\211/diagonal_traversal.txt" +++ "b/developer/document\360\237\226\211/diagonal_traversal.txt" @@ -1,4 +1,94 @@ -Does there exist a node in the tree, such that if that node were marked before the diagonal generating algorithm is run, that that node will never be reached no matter how long the diagonal generating algorithm runs? Or perhaps you can't tell. +An Index Tree is infinite both in depth and breadth. As a tree is a +graph, and Index Tree is an infinite graph. The label for each node in +an index tree is an array of integers that explain how to traverse the +tree to arrive at the node. `[]` is the root node. `[[0] ,[1] ,[2] +...] is a list of the children to the root node, etc. + + All parts of a node can be computed from its label. Hence + the SRM_Diagonal only manipulates labels. + + Label::inc_down turns a given label into the leftmost + child lavel. + + Label::inc_across turns a child label into its right neighbor + sibling label. + + An infinite child list is represented by an SRM_Child. The + SRM_Child is made from the label for the leftmost child in the + list. From each child label it is possible to generate the label for + the right neighbor child. This is be done by calling `inc_across()`. + +Diagonalization can be used to traverse the infinite Index Tree, while +always enumerating a next layer of nodes nearest the root. This +differs from depth first, which would never return to visit the child +to the right of the leftmost child, and from breadth first, which +would never descend to the grandchildren level of the tree. + +Diagonalization is guaranteed to reach any given node in the tree +in a finite number of steps. Neither depth first, nor breadth first +can do this. This guarantee also applies to a pruned IndexTree. + +/* +How diagonalization works: + + This is an infinite object, with each node having an infinite number + of children, and there being an infinite number of generations, + i.e., levels in the tree. + + Given a label, `inc_across` will turn it into the label for the + right neighbor sibling, while `inc_down` will turn it into the label + for the leftmost child. + + We compute each next diagonal based on the prior diagonal and a list + called 'child_srtm_list'. We do not modify labels in the diagonal + directly because the calling program might still be using it. Instead, + labels on the diagonal are copied before being modified. + + The diagonalization algorithm systematically alternates between + expanding depth (via `inc_down`) and breadth (via `inc_across`), + ensuring that every node in the infinite tree is eventually included + in a diagonal. + + Initially: + + diagonal is the root node, '[]'. + child_srtm_list is empty. + + Each time SRTM_Diagonal is stepped: + + 1. Create a new diagonal_1 and expand the child_srtm_list: + + 1.1 Bind diagonal (current diagonal) to an SRTM. + 1.2 For each label in diagonal: + 1.2.1 Copy the label. + 1.2.2 Apply `inc_down` to the copy to get the leftmost child. + 1.2.3 Append this child label to child_srtm_list as a new SRTM_Child. + + 2. Populate diagonal_1 using child_srtm_list: + + 2.1 Bind child_srtm_list to an SRTM. + 2.2 For each STRM in the list: + 2.2.1 Read the label from the SRTM. + 2.2.2 Append a copy of this label to diagonal_1. + 2.2.3 if can_step the STRM, the step the head to the next sibling. + else remove SRTM from the child_srtm_list. (This removal + will never happen on an infinite topology.) + + 3. Update the state for the next step: + + 3.1 Replace diagonal with diagonal_1. + + This algorithm ensures that any given node in the infinite index + tree is eventually reached in a finite number of step. It traverses + the tree a diagonal manner that alternates between depth and breadth + expansion. + + +-------------------------------------------------------------------------------- +What follows is GP providing an outline of a proof that diagonalization will reach any given node on the tree within a finite number of steps. This follows from the construction of the diagonalization, i.e. this was the design goal. + + Does there exist a node in the tree, such that if that node were marked before the diagonal generating algorithm is run, that that node will never be reached no matter how long the diagonal generating algorithm runs? Or perhaps you can't tell. + ChatGPT said: ChatGPT This is an interesting and profound question that touches on the completeness of the diagonal traversal algorithm in enumerating all nodes in an infinite tree. Let’s analyze it step by step. diff --git a/developer/example/IndexTree/Graph.java b/developer/example/IndexTreeGraph/Graph.java similarity index 100% rename from developer/example/IndexTree/Graph.java rename to developer/example/IndexTreeGraph/Graph.java diff --git a/developer/example/IndexTree/Label.java b/developer/example/IndexTreeGraph/Label.java similarity index 100% rename from developer/example/IndexTree/Label.java rename to developer/example/IndexTreeGraph/Label.java diff --git a/developer/example/IndexTree/Node.java b/developer/example/IndexTreeGraph/Node.java similarity index 100% rename from developer/example/IndexTree/Node.java rename to developer/example/IndexTreeGraph/Node.java diff --git a/developer/example/IndexTree/SRTM_Child.java b/developer/example/IndexTreeGraph/SRTM_Child.java similarity index 100% rename from developer/example/IndexTree/SRTM_Child.java rename to developer/example/IndexTreeGraph/SRTM_Child.java diff --git a/developer/example/IndexTree/SRTM_Diagonal.java b/developer/example/IndexTreeGraph/SRTM_Diagonal.java similarity index 53% rename from developer/example/IndexTree/SRTM_Diagonal.java rename to developer/example/IndexTreeGraph/SRTM_Diagonal.java index a7fea33..f023789 100644 --- a/developer/example/IndexTree/SRTM_Diagonal.java +++ b/developer/example/IndexTreeGraph/SRTM_Diagonal.java @@ -1,84 +1,18 @@ /* -An Index Tree is infinite both in depth and breadth. As a tree is a -graph, and Index Tree is an infinite graph. The label for each node in -an index tree is an array of integers that explain how to traverse the -tree to arrive at the node. `[]` is the root node. `[[0] ,[1] ,[2] -...] is a list of the children to the root node, etc. +Diagonal traversal is guaranteed to reach any given node in the IndexTree +in a finite number of steps. Neither depth first, nor breadth first +can do this. This guarantee also applies to a pruned IndexTree. + +This implementation is nearly ready, to be included in the Ariadne +library for generalized diagonal traversal. I have abstracted out all +references to the IndexTree. It still needs to remove child lists that +have been completely reversed from the child_strm_list. This was not +needed for the IndexTree because it is infinite, so they will never be +completely traversed. Also needed, is to stop when a node does not +have a child list. Again, this is not needed here because the +IndexTree has infinite depth. When the generalized diagonal iterator +is ready, it could be used in place of this one. - All parts of a node can be computed from its label. Hence - the SRM_Diagonal only manipulates labels. - - Label::inc_down turns a given label into the leftmost - child lavel. - - Label::inc_across turns a child label into its right neighbor - sibling label. - - An infinite child list is represented by an SRM_Child. The - SRM_Child is made from the label for the leftmost child in the - list. From each child label it is possible to generate the label for - the right neighbor child. This is be done by calling `inc_across()`. - -Diagonalization can be used to traverse the infinite Index Tree, while -always enumerating a next layer of nodes nearest the root. This -differs from depth first, which would never return to visit the child -to the right of the leftmost child, and from breadth first, which -would never descend to the grandchildren level of the tree. - -/* -How diagonalization works: - - This is an infinite object, with each node having an infinite number - of children, and there being an infinite number of generations, - i.e., levels in the tree. - - Given a label, `inc_across` will turn it into the label for the - right neighbor sibling, while `inc_down` will turn it into the label - for the leftmost child. - - We compute each next diagonal based on the prior diagonal and a list - called 'child_srtm_list'. We do not modify labels in the diagonal - directly because the calling program might still be using it. Instead, - labels on the diagonal are copied before being modified. - - The diagonalization algorithm systematically alternates between - expanding depth (via `inc_down`) and breadth (via `inc_across`), - ensuring that every node in the infinite tree is eventually included - in a diagonal. - - Initially: - - diagonal is the root node, '[]'. - child_srtm_list is empty. - - Each time SRTM_Diagonal is stepped: - - 1. Create a new diagonal_1 and expand the child_srtm_list: - - 1.1 Bind diagonal (current diagonal) to an SRTM. - 1.2 For each label in diagonal: - 1.2.1 Copy the label. - 1.2.2 Apply `inc_down` to the copy to get the leftmost child. - 1.2.3 Append this child label to child_srtm_list as a new SRTM_Child. - - 2. Populate diagonal_1 using child_srtm_list: - - 2.1 Bind child_srtm_list to an SRTM. - 2.2 For each STRM in the list: - 2.2.1 Read the label from the SRTM. - 2.2.2 Append a copy of this label to diagonal_1. - 2.2.3 if can_step the STRM, the step the head to the next sibling. - else remove SRTM from the child_srtm_list. (This removal - will never happen on an infinite topology.) - - 3. Update the state for the next step: - - 3.1 Replace diagonal with diagonal_1. - - This algorithm ensures that any given node in the infinite index - tree is eventually reached in a finite number of step. It traverses - the tree a diagonal manner that alternates between depth and breadth - expansion. */ import java.math.BigInteger; diff --git a/developer/example/IndexTree/SRTM_Diagonal_CLI.java b/developer/example/IndexTreeGraph/SRTM_Diagonal_CLI.java similarity index 100% rename from developer/example/IndexTree/SRTM_Diagonal_CLI.java rename to developer/example/IndexTreeGraph/SRTM_Diagonal_CLI.java diff --git a/developer/example/IndexTree/SRTM_Diagonal_transcript.txt b/developer/example/IndexTreeGraph/SRTM_Diagonal_transcript.txt similarity index 100% rename from developer/example/IndexTree/SRTM_Diagonal_transcript.txt rename to developer/example/IndexTreeGraph/SRTM_Diagonal_transcript.txt diff --git a/developer/example/IndexTree/four_down_four_across_CLI.java b/developer/example/IndexTreeGraph/four_down_four_across_CLI.java similarity index 100% rename from developer/example/IndexTree/four_down_four_across_CLI.java rename to developer/example/IndexTreeGraph/four_down_four_across_CLI.java diff --git a/developer/example/IndexTree/four_down_four_across_transcript.txt b/developer/example/IndexTreeGraph/four_down_four_across_transcript.txt similarity index 100% rename from developer/example/IndexTree/four_down_four_across_transcript.txt rename to developer/example/IndexTreeGraph/four_down_four_across_transcript.txt -- 2.20.1