Taking the long route

Question

Challenge

Your goal is to find the furthest point on a graph (from a provided start node). Your code doesn't need to handle cycles in the graph properly, but it might pose a fun challenge. For this question, you can assume the graph is actually a tree.

Input data

Input can be provided in any suitable format for the language. It can be provided either as an adjacency matrix, a list of edges, or an adjacency list. The input data can be directed or undirected as wanted by the program. The program needs to know the starting node - this can be provided in the input data if the program doesn't calculate it.

Output format

The program must output to stdout, in a human readable format, a list of nodes, starting from the root and leading to the furthest node. If you prefer, this order may be reversed. Your program must be consistent wrt to the ordering.

Edge cases

If there are multiple longest paths, only return one. If there is a cycle, or the graph has disconnected components, your code may crash or return a valid or invalid output.

Libraries

All graph related libraries, including built-in language features, are not permitted.

Test case

Input:

{0: (1, 2, 3), 1: (), 2: (4, 5), 3: (6,), 4: (7,), 5: (), 6: (8,), 7: (9,), 8: (), 9: ()}
0

The zero on the second line is the starting node. This could be inferred from the adjacency list, but I've included it in the test data anyway, to be clear.

Output:

[0, 2, 4, 7, 9]

Image:

Scoring

Shortest code wins.

Answer 1

Coconut, 45 bytes

Takes the graph in the format shown in the example test case

f=(g,s)->[s]+max(map(f$g,g[s])::[[]],key=len)

Try it online!

Uses Coconuts lambda syntax, $ for partial application and :: as an operator for itertools.chain. The same would be 56 bytes in Python:

f=lambda g,s:[s]+max([f(g,x)for x in g[s]]+[[]],key=len)

Try it online!

Answer 2

Jelly, 13 12 bytes

;ⱮịṪ¥¥€Ẏ¥ƬẎṪ

Try it online!

A dyadic link taking the start node as the left argument and the list of lists of child nodes as the right argument. The start node is expected to be supplied as [[x]] where x is the number of the node. Uses 1-indexing since that’s the way Jelly is written.

Thanks to @JonathanAllan for saving a byte!

Explanation

        ¥Ƭ    | Starting with the start node index, do the following until there’s a repeated value:
     ¥€       | - For each member of the list:
;Ɱ            |   - Append each of the following:
  ịṪ¥         |     - The last member of the list indexed into the original right argument (actually done as index into then tail)
       Ẏ      | - Flatten lists by one level
          Ẏ   | Finally, join the top level lists together
           Ṫ  | Take the last remaining list (which will be one of the longest paths)

Answer 3

Kotlin 1.4.20, 92 bytes

fun f(e:Map<Int,Set<Int>>,s:Int):List<Int> =(e[s]?.map{f(e,it)}?.maxBy{it.size}?:setOf())+s

Usage

fun main() = println(f(mapOf(0 to setOf(1, 2, 3), 1 to setOf(), 2 to setOf(4, 5), 3 to setOf(6), 4 to setOf(7), 5 to setOf(), 6 to setOf(8), 7 to setOf(9), 8 to setOf(), 9 to setOf()), 0))

Note

This uses a deprecated API that got removed in 1.5, so it requires Kotlin 1.4 or lower.

Answer 4

Charcoal, 23 bytes

⊞υ⟦θ⟧ＦυＦ§η§ι⁰⊞υ⁺⟦κ⟧ιＩ⊟υ

Try it online! Link is to verbose version of code. Takes the root as the first input and an array of lists of adjacencies as the second input and outputs the longest route in reverse order. Explanation:

⊞υ⟦θ⟧

Start a breadth first search with a list of just the root node.

Ｆυ

Process the lists in the order they are found.

Ｆ§η§ι⁰

For each list, loop over the nodes adjacent to the first node in the list...

⊞υ⁺⟦κ⟧ι

... pushing a new list with the adjacent node at the beginning to the search.

Ｉ⊟υ

Output the last, and therefore longest, list.

Answer 5

JavaScript (Node.js), 92 bytes

a=>g=(h,...t)=>v=1/h?a[h].map((n,j)=>g[j]?0:g[j]=n&&t.push(j))[g(...t)[0]]?[h,...v]:v||[h]:0

Try it online!

Input the adjacency matrix of graph and the start node currily.

This one works on graphs with cycles.

---

JavaScript (Node.js), 68 bytes

a=>s=>(g=(h,...t)=>v=h&&g(...t,...a[h[0]].map(j=>[j,...h]))||h)([s])

Try it online!

This one works on directed graph without cycles.

Answer 6

Wolfram Language (Mathematica), 47 bytes

Pick[#,#,#&@@#~Level~{Depth@#-1}]//._[]:>Set@$&

Try it online!

Input an expression - Mathematica's expressions are trees. For example:

Pick almost does the job, but non-leaf nodes with successors still remain. Then we remove all empty nodes.

Also 47 bytes

Select@Not@*FreeQ[#&@@#~Level~{Depth@#-2}]//@#&

Try it online!

Input leaves as e.g. 9[] instead of 9.

Answer 7

PowerShell, 114 109 104 103 96 bytes

param($s,$e)$e|%{$p=($p+,"$_"*!(($a=$_[0])-$s))-replace"\b$a$",$_}
$p|sort{(-split$_).count}-b 1

Try it online!

Stores paths as an array of strings. Each path contains a list of vertices separated by spaces.

---

Less golfed:

param($startVertex,$edges)
$edges|%{
    $fromVertex = $_[0]
    $pathes += ,"$_"*($fromVertex -eq $startVertex) # add $null or an edge
    $pathes = $pathes -replace "\b$fromVertex$",$_
}
$pathes|sort{(-split$_).count} -Bottom 1

The dump of $pathes before sorting for the test case:

"0 1"
"0 2 4 7 9"
"0 3 6 8"

Answer 8

Red, 95 bytes

f: function[x s][m: []foreach i select x s[p: f x i if(length? p)> length? m[m: p]]rejoin[m s]]

Try it online!

Takes input as an adjacency list plus the starting node in the same form as in challenge specification. Returns the longest path in reverse order.

Answer 9

R, 89 bytes

R=function(G,p={})`if`(!is.list(G),p,(A=lapply(G,R,c(p,el(G))))[[which.max(lengths(A))]])

Try it online!

Recursive function taking a tree as input (for the input format see the TIO) and returning the subtree of maximum length.