{ From user Lonnie, Model Connected_components at 13-Jul-2017 5:18:40 PM, encoding="ascii" }
SoftwareVersion 5.0.11


{ System Variables with non-default values: }
Time := 0..10
SampleSize := 1000
TypeChecking := 1
Checking := 1
SaveOptions := 2
SaveValues := 0

NodeInfo FormNode: 1,0,0,1,0,0,0,,0,0,,0,0



Model Connected_components
Description: In this challenge, you are to implement an algorithm to compute connected components.~
~
An adjacency matrix is given (Touching), with a 1 wherever any two items are directly connected. A "connected component" is a subset if items that are directly or indirectly touching. For example, it A directly touches B, and B directly touches C, and there is no other item that touches any of these three, then {A, B, C} form a connected component. Any single item will belong to exactly one connected component. If an item does not touch any other item, then it is the only member of its connected component.~
~
Your solution should figure out how many connected components there are, then using a numbering of 1 to n, it should compute which component each item belongs to. ~
~
Your solution does not have to fit in a single definition -- you can use multiple variables and user-defined functions and you see fit.~
~
Note: This challenge problem is very difficult. If there is a trivial solution to it, I am unaware of it.~
~
To enable to test your algorithm on multiple problem instances, several cases are provided. Select a different case using the Case choice. For your first challenge, implement a solution that works when a single case is selected (but which computes the correct answer for all of the cases provided). For an even more advanced challenge, ensure that your algorithm array-abstracts, so that it works when Case=All is selected.
Author: Lonnie Chrisman~
Lumina Decision Systems
Date: Thu, Jul 13, 2017 2:56 PM
SaveAuthor: Lonnie
SaveDate: Thu, Jul 13, 2017 5:18 PM
DiagState: 2,1,0,721,617,17
WindState: 2,526,241,747,580
FontStyle: Arial,15
FileInfo: 0,Model Connected_components,2,2,0,0,C:\Users\Lonnie\Documents\Analytica\Connected components challenge.ana

Index Item
Title: Item
Description: The items that may or may not be touching each other.
Definition: 1..20
NodeLocation: 128,80,1
NodeSize: 48,24
{!40000|Att_PrevIndexValue: [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20]}

Index Item2
Title: Item2
Description: A copy of the Item index, so that a 2-D square matrix can be represented.
Definition: CopyIndex(Item)
NodeLocation: 128,144,1
NodeSize: 48,24
{!40000|Att_PrevIndexValue: [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20]}

Variable Touching
Title: Touching
Description: A symmetric adjacency matrix. A 1 indicates that two items are adjacent (with every item being adjacent to itself).
Definition: DetermTable(Item,Item2,Case)(~
1,1,1,1,1,1,1,~
0,0,0,0,0,1,0,~
0,0,0,0,1,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,1,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,1,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,1,0,0,0,0,0,~
0,0,0,0,1,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
1,0,0,0,0,1,0,~
0,0,0,1,0,0,0,~
0,1,1,0,0,0,0,~
0,0,0,0,0,1,0,~
1,1,1,1,1,1,1,~
0,0,0,0,1,0,0,~
0,0,0,0,0,0,0,~
0,0,1,0,0,0,0,~
0,1,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,1,0,0,0,1,~
0,1,0,0,0,0,0,~
0,0,0,0,1,1,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
1,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,1,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,1,0,0,~
0,0,0,0,1,0,0,~
1,1,1,1,1,1,1,~
0,0,0,0,0,1,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,1,0,~
0,0,1,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,1,0,0,1,~
0,0,0,0,0,0,0,~
0,0,0,0,1,0,0,~
0,1,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,1,~
1,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,1,0,~
1,1,1,1,1,1,1,~
0,0,0,0,1,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,1,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,1,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,1,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,1,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,1,0,~
1,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,1,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,1,0,0,~
1,1,1,1,1,1,1,~
0,0,0,0,0,0,0,~
0,0,0,0,1,0,0,~
0,0,0,0,0,1,0,~
1,0,0,0,0,0,0,~
0,0,0,0,0,1,0,~
0,1,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,1,0,0,0,~
0,0,0,0,0,0,0,~
0,1,0,0,0,1,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,1,0,1,0,0,0,~
0,0,0,0,1,0,1,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,1,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
1,1,1,1,1,1,1,~
0,0,1,0,0,1,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,1,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,1,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
1,0,0,1,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,1,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,1,0,0,~
0,0,1,0,0,1,0,~
1,1,1,1,1,1,1,~
0,1,0,0,0,0,0,~
1,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,1,0,0,0,0,0,~
0,0,0,0,0,0,1,~
0,0,0,0,0,1,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,1,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,1,0,0,0,0,0,~
0,0,0,0,0,1,0,~
0,0,0,0,0,0,0,~
0,1,0,0,0,0,0,~
1,1,1,1,1,1,1,~
0,0,0,0,0,0,0,~
0,0,0,1,0,0,1,~
0,0,0,0,0,0,0,~
0,0,1,0,0,0,0,~
0,0,0,0,0,0,0,~
1,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,1,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,1,0,0,0,~
0,0,1,0,0,0,1,~
0,0,0,0,0,1,0,~
0,0,0,0,0,0,0,~
1,0,0,0,0,0,0,~
0,0,0,0,0,1,0,~
1,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
1,1,1,1,1,1,1,~
0,0,0,0,0,0,1,~
1,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,1,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,1,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,1,0,0,~
0,0,0,0,0,0,0,~
0,1,0,0,0,0,0,~
0,0,1,0,0,0,0,~
0,0,0,1,0,0,0,~
0,0,0,0,0,1,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,1,0,0,1,~
0,0,0,0,0,0,1,~
1,1,1,1,1,1,1,~
0,0,0,0,0,0,0,~
0,0,0,0,0,1,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,1,0,0,~
1,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,1,~
0,0,0,0,1,1,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,1,0,0,0,0,0,~
0,0,0,0,0,0,1,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
1,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
1,1,1,1,1,1,1,~
1,0,0,0,0,0,0,~
0,0,0,0,0,1,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,1,0,~
0,0,0,0,0,0,0,~
0,0,1,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,1,0,0,1,~
0,0,0,0,0,0,1,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,1,0,0,0,0,0,~
0,0,1,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,1,0,~
1,0,0,0,0,0,0,~
1,1,1,1,1,1,1,~
0,0,0,0,1,0,0,~
0,0,0,1,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,1,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,1,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,1,0,~
0,0,0,0,1,0,0,~
1,1,1,1,1,1,1,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,1,~
0,0,0,0,0,1,0,~
0,0,0,0,0,0,0,~
0,0,0,0,1,0,0,~
1,0,0,0,0,0,0,~
0,1,0,0,0,0,0,~
0,1,0,0,0,0,0,~
1,0,0,0,0,0,0,~
0,0,0,0,1,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,1,0,~
1,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,1,0,0,0,~
0,0,0,0,0,0,0,~
1,1,1,1,1,1,1,~
0,0,1,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,1,0,0,0,0,~
0,0,0,0,0,0,1,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,1,0,0,~
0,0,0,0,0,0,0,~
0,1,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,1,0,0,0,1,0,~
1,0,0,1,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,1,~
0,0,1,0,0,0,0,~
1,1,1,1,1,1,1,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
1,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,1,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,1,0,0,~
0,1,0,0,0,0,0,~
0,0,0,0,1,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,1,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
1,1,1,1,1,1,1,~
0,0,0,1,0,0,0,~
0,0,1,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,1,~
0,1,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,1,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
1,0,0,0,0,0,0,~
0,0,0,0,0,1,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,1,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,1,0,0,0,~
1,1,1,1,1,1,1,~
0,0,0,0,0,0,0,~
1,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
1,0,0,0,0,1,0,~
0,0,0,0,0,0,0,~
1,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,1,0,1,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,1,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,1,0,0,~
0,0,0,0,0,0,1,~
0,0,0,0,0,0,0,~
0,0,1,0,0,0,0,~
0,0,0,0,0,0,0,~
1,1,1,1,1,1,1,~
0,0,0,0,0,0,1,~
1,0,0,0,0,1,0,~
0,0,0,1,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,1,0,~
0,0,0,0,1,0,1,~
0,1,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,1,0,0,0,0,~
0,0,0,0,0,0,0,~
1,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
1,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
1,0,0,0,0,0,0,~
0,0,0,0,0,0,1,~
1,1,1,1,1,1,1,~
0,0,0,0,0,0,1,~
0,1,1,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
1,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,1,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,1,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
0,0,0,0,0,0,0,~
1,0,0,0,0,1,0,~
0,0,0,0,0,0,1,~
1,1,1,1,1,1,1)
NodeLocation: 256,216,1
NodeSize: 48,24
WindState: 2,278,557,720,350
DefnState: 2,216,219,737,416,,DFNM
ValueState: 2,626,12,723,481,,MIDM
ReformVal: [Item2,Item]
{!40000|Att_ResultSliceState: [Case,4,Item,1,Item2,1]}
{!40000|Att_EditSliceState: [Sys_LocalIndex('DomainIndex'),4,Item2,1,Item,1]}
{!50000|Att_ColumnWidths: [,Item2,\([28,28,28,28,28,28,28,28,28,28,28,28,28,28,27,28,28,28,28,28])]}

Decision Case
Title: Case
Description: Several example data are provided, so you can test your implementation on more than one case.
Definition: Choice(Self,1)
NodeLocation: 128,216,1
NodeSize: 48,24
WindState: 2,252,593,720,350
Aliases: FormNode Fo1499988516
Domain: [1,2,3,4,5,6,7]
{!40300|DomainExpr: Discrete(1,2,3,4,5,6,7,type:'number')}
{!40200|Att_ChoiceIndexes: Keyword Self}

FormNode Fo1499988516
Title: Case
Definition: 0
NodeLocation: 96,280,1
NodeSize: 64,16
NodeInfo: 1,,,,,,0,60,,,,,,0
Original: Case

Variable Desired_solution
Title: Desired solution
Description: Your solution for Component_of_item should compute the same result as shown here when you view my result. ~
~
The correct solution is unique up to renaming the components. But a result that is equivalent with respect to renaming the final numbers is also correct. To match the solution show here exactly, the components should be numbered so that the first occurrence of each component appears monotonically along Item (i.e., The first 1 appears before the first 2, etc.).
Definition: DetermTable(Item,Case)(~
1,1,1,1,1,1,1,~
2,2,2,2,1,1,2,~
1,3,3,3,1,2,3,~
1,4,4,4,2,2,3,~
3,3,2,5,2,3,4,~
4,2,5,6,3,2,1,~
3,4,5,7,2,2,5,~
2,4,6,4,4,3,2,~
3,5,2,1,5,2,2,~
4,2,3,4,4,3,2,~
3,3,7,8,1,1,1,~
3,4,6,3,5,3,3,~
4,1,8,5,5,1,5,~
2,1,9,3,1,2,4,~
4,3,9,6,1,3,5,~
5,5,10,9,4,1,2,~
4,4,9,9,2,1,3,~
1,3,10,5,5,1,4,~
4,2,7,1,2,2,4,~
1,1,1,10,5,1,4)
NodeLocation: 256,304,1
NodeSize: 48,24
WindState: 2,280,439,720,350
ValueState: 2,1044,32,424,481,,MIDM

Module Solution
Title: Solution
Description: Contains one possible solution. Try not to peek before you've solved it yourself!
NodeLocation: 600,216,1
NodeSize: 48,24
NodeInfo: 1,0,1,1,1,1,0,,0,,0,,,
DiagState: 2,758,418,579,250,17

Variable Solution___Component
Title: Solution - Component of item
Description: The connected component id for each item.~
~
This iterates to convergence. It starts by placing each item in its own cluster. Then, on each step, each item revises its own assignment to the smallest cluster number among those items that touch it (which includes itself, since Touching encodes that each node touches itself). The number of unique cluster names appearing in c drops with each iteration.~
~
When the iteration finishes, c has a valid assignment, but the cluster numbering is not necessarily consecutive.  The final call to Unique_Nth( ) just renames the clusters to the numbers from 1 to n.~
~
The very first line declares that Touching should be treated as being 2-D, with only the indexes Item and Item2. This ensures that the expression will still work in the event that Touching has other indexes (namely, in this challenge, Case, when Case=All).
Definition: Var Touching[Item,Item2] := Touching;  ~
~
Var c := Item;~
Var next := Min(if Touching then c[Item=Item2] else null, Item2);~
~
while Min(c=next,Item)=0 do (~
	c := next;~
	next := Min(if Touching then c[Item=Item2] else null, Item2);~
);~
Unique_Nth(c,item)~

NodeLocation: 104,48,1
NodeSize: 56,32
WindState: 2,527,16,720,694
ValueState: 2,760,28,585,482,,MIDM
ReformVal: [Item2,Item]

Function Unique_Nth(a : Array[I] ; I : Index )
Title: Unique Nth
Description: Numbers each unique item in Ťať from 1 to n, where n is the number of distinct values, and then returns this unique numer for each value of Ťať.
Definition: Index u := Unique(a,I);~
@[u=a]
NodeLocation: 112,136,1
NodeSize: 48,24
WindState: 2,667,40,720,350

Close Solution

Variable Component_of_item
Title: Component of item
Description: Your challenge is to write this Definition.~
~
The component number that each item belongs to. Two items have the same component number if and only if there is a path between them, with each step in the path being between items that are adjacent according to Variable Touching.~
~
Each cell should have a number between 1 and n, where n is the number of connected components. The variable Desired_solution shows the desired result.
NodeLocation: 408,216,1
NodeSize: 56,24
WindState: 2,375,546,720,350

Text Te1499988790
Description: Write the definition for this node
NodeLocation: 412,200,-1
NodeSize: 84,64
NodeInfo: 1,,,,,1
NodeColor: 65535,65531,39321

Text Te1499988935
Title: Note:
Description: See the model's Description for instructions.
NodeLocation: 416,64,-1
NodeSize: 192,24
NodeInfo: 1,,,,,1
NodeColor: 52427,52429,65535

Close Connected_components