Skip to content

feat: variable length pattern matching #685

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
rjurney merged 12 commits into from
Sep 20, 2025
Merged

feat: variable length pattern matching #685

Show file tree
Hide file tree
Changes from 6 commits
Commits
Show all changes
12 commits
Select commit Hold shift + click to select a range
fd5a548
variable length pattern matching
gounnaa Sep 13, 2025
e2980ac
scalafmtAll
gounnaa Sep 13, 2025
0b947f4
fix exhaustive match error
gounnaa Sep 13, 2025
588d8eb
more test cases
gounnaa Sep 14, 2025
8532f9b
to specify the test result type to long
gounnaa Sep 14, 2025
36a1acc
fixed formatting by scalafmtAll to pass Scala CI test
gounnaa Sep 14, 2025
5e7c708
Improve error message
gounnaa Sep 15, 2025
ec12d16
var-length pattern prototype
gounnaa Sep 16, 2025
a121c02
find variable length pattern
gounnaa Sep 17, 2025
8074635
unsupported case handling
gounnaa Sep 18, 2025
2c47bcc
scalafmtAll
gounnaa Sep 18, 2025
5efe0b7
fixed and var length with named edge support
gounnaa Sep 18, 2025
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
23 changes: 22 additions & 1 deletion core/src/main/scala/org/graphframes/pattern/patterns.scala
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -45,8 +45,29 @@ private[graphframes] object PatternParser extends RegexParsers {
"!" ~ edge ^^ { case _ ~ e =>
Negation(e)
}
Comment thread
SemyonSinchenko marked this conversation as resolved.
private val varLengthEdge: Parser[List[Edge]] =
vertex ~ "-" ~ "[" ~ "*" ~ "[0-9]+".r ~ "]" ~ "->" ~ vertex ^^ {
case src ~ "-" ~ "[" ~ "*" ~ num ~ "]" ~ "->" ~ dst => {
val hop = num.toInt
if (hop > 1) {
val midVertices = (1 until hop).map(i => NamedVertex(s"_v$i"))
val vertices = src +: midVertices :+ dst
vertices
.sliding(2)
.map {
case Seq(v1, v2) =>
AnonymousEdge(v1, v2)
case _ => throw new GraphFramesUnreachableException()
}
.toList
} else {
List(AnonymousEdge(src, dst))
}
}
case _ => throw new GraphFramesUnreachableException()
}
private val pattern: Parser[Pattern] = edge | vertex | negatedEdge
val patterns: Parser[List[Pattern]] = repsep(pattern, ";")
val patterns: Parser[List[Pattern]] = varLengthEdge | repsep(pattern, ";")
}

private[graphframes] object Pattern {
Expand Down
27 changes: 27 additions & 0 deletions core/src/test/scala/org/graphframes/PatternMatchSuite.scala
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -547,6 +547,33 @@ class PatternMatchSuite extends SparkFunSuite with GraphFrameTestSparkContext {
compareResultToExpected(res, Set(Row(0L, 1L, 2L), Row(2L, 0L, 1L), Row(1L, 2L, 0L)))
}

Comment thread
rjurney marked this conversation as resolved.
test("a path of length 3") {
val varEdge = g
.find("(u)-[*3]->(v)")
.where("u.id == 0")
.select("u.id", "_v1.id", "_v2.id", "v.id")

val res = varEdge.collect().toSet
val expected = Set(Row(0L, 1L, 2L, 0L), Row(0L, 1L, 2L, 3L), Row(0L, 1L, 0L, 1L))
compareResultToExpected(res, expected)
}

test("a path of length 5") {
val varEdge = g
.find("(u)-[*5]->(v)")
.where("u.id == 0")
.select("u.id", "_v1.id", "_v2.id", "_v3.id", "_v4.id", "v.id")

val res = varEdge.collect().toSet
val expected = Set(
Row(0L, 1L, 2L, 0L, 1L, 0L),
Row(0L, 1L, 0L, 1L, 0L, 1L),
Row(0L, 1L, 2L, 0L, 1L, 2L),
Row(0L, 1L, 0L, 1L, 2L, 0L),
Row(0L, 1L, 0L, 1L, 2L, 3L))
compareResultToExpected(res, expected)
}

test("stateful predicates via UDFs") {
val chain4 = g
.find("(a)-[ab]->(b); (b)-[bc]->(c); (c)-[cd]->(d)")
Expand Down
37 changes: 37 additions & 0 deletions core/src/test/scala/org/graphframes/pattern/PatternSuite.scala
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -51,6 +51,22 @@ class PatternSuite extends SparkFunSuite {
AnonymousEdge(NamedVertex("u"), NamedVertex("v")),
AnonymousEdge(NamedVertex("v"), NamedVertex("w")),
Negation(AnonymousEdge(NamedVertex("u"), NamedVertex("w")))))

assert(
Pattern.parse("(u)-[*3]->(v)") ===
Seq(
AnonymousEdge(NamedVertex("u"), NamedVertex("_v1")),
AnonymousEdge(NamedVertex("_v1"), NamedVertex("_v2")),
AnonymousEdge(NamedVertex("_v2"), NamedVertex("v"))))

assert(
Pattern.parse("(u)-[*5]->(v)") ===
Seq(
AnonymousEdge(NamedVertex("u"), NamedVertex("_v1")),
AnonymousEdge(NamedVertex("_v1"), NamedVertex("_v2")),
AnonymousEdge(NamedVertex("_v2"), NamedVertex("_v3")),
AnonymousEdge(NamedVertex("_v3"), NamedVertex("_v4")),
AnonymousEdge(NamedVertex("_v4"), NamedVertex("v"))))
}

test("bad parses") {
Expand Down Expand Up @@ -121,6 +137,27 @@ class PatternSuite extends SparkFunSuite {
Pattern.parse("(a)-[e]->(b); ()-[e]->()")
}
}
withClue("Failed to catch parse error with unsupported variable length pattern") {
intercept[InvalidParseException] {
Pattern.parse("(u)-[*]->(v)")
}
}
withClue("Failed to catch parse error with unsupported variable length pattern") {
intercept[InvalidParseException] {
Pattern.parse("(u)-[*2..]->(v)")
}

@rjurney rjurney Sep 14, 2025

Copy link
Copy Markdown
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Ahhh thank you for this clarification! After we merge this PR, want to take on variable lengths as well? :)

}
withClue("Failed to catch parse error with unsupported variable length pattern") {
intercept[InvalidParseException] {
Pattern.parse("(u)-[*2..5]->(v)")
}
}
withClue("Failed to catch parse error with chaining long length pattern") {
intercept[InvalidParseException] {
Pattern.parse("(u)-[*2]->(v);(v)-[e]->(w)")
}
}

}

test("empty pattern should be parsable") {
Expand Down