# How to find first relation \*not\* of a type

**URL:** <https://alloytools.discourse.group/t/how-to-find-first-relation-not-of-a-type/430>\
**Category:** Questions\
**Created:** [January 12, 2024, 5:33pm UTC](https://alloytools.discourse.group/t/how-to-find-first-relation-not-of-a-type/430 "2024-01-12T17:33:02Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![hwayne](https://yyz2.discourse-cdn.com/free1/user_avatar/alloytools.discourse.group/hwayne/32/67_2.png) [@hwayne](https://alloytools.discourse.group/u/hwayne)\
**Post date:** [January 12, 2024, 5:33pm UTC](https://alloytools.discourse.group/t/how-to-find-first-relation-not-of-a-type/430/1 "2024-01-12T17:33:02Z")

</div>

Say I have

```alloy
abstract sig Node {
  , next: lone Node
}

fact list {
  some root: Node |
    root.*next = Node
}

sig Red, Blue extends Node {}

```

For each red node, I want to find the next _red_ node. So if the model is `red1 -> blue1 -> blue2 -> red2 -> red3`, the relationship `next_red_node` should be `red1 -> red2 + red2 -> red3`. Ideally I want this to also be fast, since my production model already takes almost a minute to write the CFG.

I’m open to adding an extra field if that’s the fastest way.

---

<div class="post-metadata">

**Author:** ![alcino](https://yyz2.discourse-cdn.com/free1/user_avatar/alloytools.discourse.group/alcino/32/25_2.png) [@alcino](https://alloytools.discourse.group/u/alcino)\
**Post date:** [January 13, 2024, 7:44am UTC](https://alloytools.discourse.group/t/how-to-find-first-relation-not-of-a-type/430/2 "2024-01-13T07:44:49Z")

</div>

Hi,

Your lists currently allow circularity. If that was not the case (that is, if `fact list` included constraint `no x : Node | x in x.^next`) I think you could derive `next_red_node` as follows:

```alloy
fun next_red_node : Node -> Node {
	{ x,y : Red | y in x.^next and no Red & x.^next & ^next.y}
}

```

Best,  
Alcino

---

<div class="post-metadata">

**Author:** ![alcino](https://yyz2.discourse-cdn.com/free1/user_avatar/alloytools.discourse.group/alcino/32/25_2.png) [@alcino](https://alloytools.discourse.group/u/alcino)\
**Post date:** [January 13, 2024, 8:28am UTC](https://alloytools.discourse.group/t/how-to-find-first-relation-not-of-a-type/430/3 "2024-01-13T08:28:38Z")

</div>

With circularity this one seems to work:

```alloy
fun next_red_node : Node -> Node {
	{ x, y : Red | x->y in next or x->y in ^(next :> Blue + Blue <: next) }
}

```

Either the next red node is directly connect or can be reached via a blue path.

Best,  
Alcino

---

<div class="post-metadata">

**Author:** ![hwayne](https://yyz2.discourse-cdn.com/free1/user_avatar/alloytools.discourse.group/hwayne/32/67_2.png) [@hwayne](https://alloytools.discourse.group/u/hwayne)\
**Post date:** [January 13, 2024, 8:58pm UTC](https://alloytools.discourse.group/t/how-to-find-first-relation-not-of-a-type/430/4 "2024-01-13T20:58:16Z")

</div>

Yeah, I meant it to be noncircular. The first works magnificently, thank you!

---

<div class="post-metadata">

**Author:** ![DanielJackson](https://yyz2.discourse-cdn.com/free1/user_avatar/alloytools.discourse.group/danieljackson/32/80_2.png) [@DanielJackson](https://alloytools.discourse.group/u/DanielJackson)\
**Post date:** [January 14, 2024, 5:27pm UTC](https://alloytools.discourse.group/t/how-to-find-first-relation-not-of-a-type/430/5 "2024-01-14T17:27:09Z")

</div>

Another idea: go from red to red, with zero or more steps to a blue and then one step:

```auto
fun next_red_node : Node -> Node {
	Red -> Red & *(next :> Blue).next
}

```

---

<div class="post-metadata">

**Author:** ![hwayne](https://yyz2.discourse-cdn.com/free1/user_avatar/alloytools.discourse.group/hwayne/32/67_2.png) [@hwayne](https://alloytools.discourse.group/u/hwayne)\
**Post date:** [January 15, 2024, 6:42pm UTC](https://alloytools.discourse.group/t/how-to-find-first-relation-not-of-a-type/430/6 "2024-01-15T18:42:13Z")

</div>

This ended up being a LOT faster!