Ways to paint a backbone on a tree

Question

Say I have some unlabelled tree graph:

I'll define a "backbone" as a path on a graph that can't be extended - both its ends are at terminal vertices. There are three ways to overlay a backbone on the above graph:

However, you might notice that the first two are the same up to rearrangement (or a more strict definition: the graphs are isomorphic when only distinguishing nodes by color). Because of that, we'll consider them to be the same, and say that there are two distinct ways to draw a backbone on this graph.

Now, a more complex example:

This can have a backbone overlaid on it in six ways. However, the top two and bottom two of these are identical up to rearrangement, so there are 4 ways to paint a backbone on this graph.

Your challenge is to, given an unlabelled tree graph with at least two vertices, count the number of distinct-up-to-rearrangement ways a backbone can be overlaid on that graph. Graphs can be taken as:

• an adjacency matrix
• an adjacency list
• an incidence matrix (whether each edge touches each vertex)
• a list of pairs of adjacent vertices

Note that for all of these, input is given as a labelled graph, but your solution should behave the same regardless of how the graph is labelled.

This is code-golf, shortest wins!

Testcases

Image	Vertex pairs	Output
	[[1,2],[2,3],[3,4],[3,5]]	2
	[[1,2],[2,3],[3,4],[5,6],[6,7],[3,7],[7,8]]	4
	[[1,2],[2,3],[3,4],[3,5],[3,6],[3,7]]	2
	[[1,2],[2,3],[3,4],[3,5],[5,6],[6,7],[6,8],[6,9]]	4
	[[1,2],[2,3],[3,4],[4,5],[4,6],[7,8],[8,9],[6,9],[9,10]]	6
	[[1,2],[2,3],[3,4],[4,5],[4,6],[6,7],[4,8],[8,9],[9,10],[9,11],[11,12]]	10
	[[1, 2], [2, 3], [2, 4], [4, 5], [4, 6], [6, 7], [7, 8], [7, 9]]	5
	[[1,2],[1,3],[2,4],[2,5],[3,6],[3,7],[4,8],[4,9],[5,10],[5,11],[6,12],[6,13],[7,14],[7,15]]	3

Answer 1

Python, 238 bytes

-7 bytes thanks to @Neil
-8 bytes thanks to @emanresu A
-5 bytes thanks to @xnor
+72 bytes due to a very serious bug (pointed out by @Jonathan Allan); bugged version

h=lambda g,p,n:(*sorted(h(g,n,c)for c in g[n]if p^c),)
def f(g):
 s=[]
 for*i,p,n in(q:=[[h(g,n,n),n,n]for n,c in enumerate(g)if len(c)<2]):
  q+=[[h(g,c,c),*i,n,c]for c in g[n]if p^c];s+=[(*min(i,i[::-1]),)]*(g[n]==[p])
 return len({*s})

Attempt This Online!

Takes input as an adjacency list, test runner contains code to convert edge list to adjacency list.

Answer 2

Charcoal, 149 135 bytes

≔Ｅθ⊞Ｏ⌕ＡＳ1κθ≔ＥθＥθυηＦθＦＥθλＦ§θκ«≔Ｅ⁻§θκ⟦κλ⟧§§ημκζ≔⟦⟧εＷ⁻ζεＦ№ζ⌊μ⊞ε⌊μ§≔§ηκλε»≔ΦＥθ⟦κι⟧⁼²Ｌ⊟ιζＦζ«≔⁻§θ§ι⁰ιε¿εＦε⊞ζ⁺⟦κ⟧ι⊞υＥ駧ηκκ»ＵＭυ⌊⟦ι⮌ι⟧ＩＬΦυ⁼κ⌕υι

Try it online! Link is to verbose version of code. Takes input as an adjacency matrix. Explanation: Port of an earlier version of @Mukundan314's Python answer.

≔Ｅθ⊞Ｏ⌕ＡＳ1κθ

Convert the adjacency matrix into a modified adjacency list where each node is considered to be adjacent to itself.

≔ＥθＥθυη

Start constructing the list representations (Charcoal doesn't really have tuples) of trees rooted at each node.

Ｆθ

Repeat enough times to complete all of the representations.

ＦＥθλＦ§θκ«

Loop through each adjacency pair.

≔Ｅ⁻§θκ⟦κλ⟧§§ημκζ

Get a list of all of the nodes that are next steps from the current node as seen from the current node, except for the current adjacent node.

≔⟦⟧εＷ⁻ζεＦ№ζ⌊μ⊞ε⌊μ

Sort this list.

§≔§ηκλε

Save it as the current node as seen from the adjacent node.

»≔ΦＥθ⟦κι⟧⁼²Ｌ⊟ιζＦζ«

Start a breadth-first search for backbones with a list of all the leaves as the first element of a backbone.

≔⁻§θ§ι⁰ιε

Get a list of next nodes for the current node, excluding the previous nodes.

¿εＦε⊞ζ⁺⟦κ⟧ι

If there are any then for each next node add it to the backbone so far and add the new backbone to the search.

⊞υＥ駧ηκκ

Otherwise this is a leaf so save the list representation of this backbone.

»ＵＭυ⌊⟦ι⮌ι⟧

Take the minimum of each backbone and its reverse so that they can be deduplicated.

ＩＬΦυ⁼κ⌕υι

Deduplicate and count the backbones.

Answer 3

Python, 161 150 bytes

-11 bytes thanks to @xnor's idea in the comments

lambda G:len({min((H:=lambda a,b,p=G:(1,*sorted(H(n,b,a)for n in G[a]if n!=p))*([]==G[b][a!=b:]))(j,k),H(k,j))for j in sum(G,[])for k in sum(G,[])})-1

Attempt This Online!

Unnamed function which takes an adjacency list as input and outputs the number of backbones.

While I came up with the algorithm I used here independently, I did use some stuff from Mukundan314's answer, so be sure to go upvote that as well. Specifically, the idea of using an adjacency list instead of edge pairs saved at least a dozen bytes, and I'm using their code that runs the test cases as well.

Explanation

The idea started out pretty simple: Look at each pair of leaves on the graph, take a representation of the graph with them "marked" in some way, add that to a set. Then our answer will be the size of the set at the end. First we have to think about how to represent the graph; in python, nested tuples are a pretty natural choice for a tree where nodes are not distinguishable. This is also just about the only choice since to get our free deduplication from the set, we need the representation to be hashable. But how to mark the two leaves? Well we get one for free, since we have to pick a root when converting the graph to nested tuples. The other one is a little trickier. We put an integer at the beginning of every tuple except the second leaf, which we leave as an empty tuple. To keep the representations consistent for isomorphic graphs, as they are recursively generated, the tuples are sorted at every step. This means that two isomorphic graphs will have the same representation. The last bit to consider is ordering. We pick ordered pairs, but backbones are not directional. To solve this problem, we simply look at both directions, compare them, and take the "first" one. In this way we can generate a set of all backbones and we have our answer.

As for the actual code, let's start by looking at the helper function H. This is the function which generates the tuple representation of the graph given two nodes a and b. This is defined inline so it has access to the graph G, p is the previous node which is avoided to prevent backtracking.

H:=lambda a,b,p=G:          # define lambda H inline
  (1,                       # integer for first element of tuple
    *sorted(                # sort and splat elements in to tuple
      H(n,b,a)              # make a recursive call to H
      for n in G[a]if n!=p  # for each node connected to 'a' that isn't the previous node
    )                       # 
  )                         # 
  *([]==G[b][a!=b:])        # if len(G[b]) > 1 or if a==b, we return an empty tuple

That last bit there does a lot of heavy lifting. If b is not a leaf or a and b are equal at the start, we immediately return an empty tuple, meaning that this always returns an empty tuple for invalid node pairs. It also does the job of distinguishing the second leaf, since it will be the only empty tuple.

For the main function then all we need to do is iterate over all node pairs, call H on both orderings, add the "lesser" one to the set, and take the length. We subtract one from this length since all invalid node pairs will be added to the set as an empty tuple, which we can discount.

lambda G:                                   # define our main funciton
  len(                                      # take the length of
    {                                       # the set of
      min(                                  # the lesser of
        H(j,k),H(k,j)                       # H called on (j,k) in both orders
      )                                     # 
      for j in sum(G,[])for k in sum(G,[])  # iterate j and k over all nodes
    }                                       # 
  )                                         # 
  -1                                        # subtract 1 to account for invalid pairs

Answer 4

Python3, 643 bytes

F=lambda x:{J for K in x for J in K}
W=tuple
def B(g):
 D={}
 for a,b in g:D[a]={*D.get(a,[]),b};D[b]={*D.get(b,[]),a} 
 q,S=[(i,[i],[len(D[i])])for i in D if len(D[i])==1],{}
 for a,p,d in q:
  F=1
  for A in D[a]-{*p}:q+=[(A,p+[A],d+[len(D[A])])];F=0
  if F:
   if(t:=W(d))in S:
    if p not in S[t]and p[::-1]not in S[t]:S[t]=S[t]+[p]
   elif(T:=W(d[::-1]))in S:
    if p not in S[T]and p[::-1]not in S[T]:S[T]=S[T]+[p]
   else:S[t]=[p]
 return S
def f(g):
 d=B(g)
 C=0
 for i in d:
  V=[]
  for j in d[i]:
   r=[b for b in g if all(I not in b for I in j)]
   V+=[W(sorted([*B(r+[[u,u]for u in F(g)-F(r)-{*j}])]))]
  C+=len({*V})
 return C 

Try it online!

Answer 5

Scala 3, 1987 bytes

A port of @Ajax1234's Python code in Scala.

1987 bytes, it can be golfed much more.

---

Golfed version. Attempt This Online!

def e(edges: List[(Int, Int)]): Set[Int] = {
    edges.flatMap { case (a, b) => List(a, b) }.toSet
  }
def t[A](seq: Seq[A]): List[A] = {
    seq.toList
  }
def b(edges: List[(Int, Int)]): Map[Int, Set[Int]] = {
    edges.foldLeft(Map[Int, Set[Int]]()) { (A, edge) =>
      val (a, b) = edge
      A.updated(a, A.getOrElse(a, Set()) + b)
        .updated(b, A.getOrElse(b, Set()) + a)
    }
  }
def f(A: Map[Int, Set[Int]]): Map[List[Int], List[List[Int]]] = {
    var queue = A.filter(_._2.size == 1).keys.map(node => (node, List(node), List(A(node).size))).toList
    var paths = Map[List[Int], List[List[Int]]]()
    while (queue.nonEmpty) {
      val (currentNode, path, degrees) = queue.head
      queue = queue.tail
      var isLeaf = true
      for (neighbor <- A(currentNode) -- path.toSet) {
        queue = queue :+ (neighbor, path :+ neighbor, degrees :+ A(neighbor).size)
        isLeaf = false
      }
      if (isLeaf) {
        val d= t(degrees)
        val r= t(degrees.reverse)
        if (paths.contains(d)) {
          if (!paths(d).contains(path) && !paths(d).contains(path.reverse)) {
            paths = paths.updated(d, paths(d) :+ path)
          }
        } else if (paths.contains(r)) {
          if (!paths(r).contains(path) && !paths(r).contains(path.reverse)) {
            paths = paths.updated(r, paths(r) :+ path)
          }
        } else {
          paths = paths.updated(d, List(path))
        }
      }
    }
    paths
  }
def c(edges: List[(Int, Int)]): Int = {
    val paths = f(b(edges))
    var u= 0
    for ((degrees, pathList) <- paths) {
      var subgraphs = List[List[List[Int]]]()
      for (path<-pathList) {
        val E=edges.filter { case (a, b) => !path.contains(a) && !path.contains(b) }
        val N= e(edges).diff(e(E)).diff(path.toSet)
        val newSubgraph = f(b(E ++ N.map(node => (node, node)))).keys.toList
        subgraphs = subgraphs :+ newSubgraph.map(_.sorted)
      }
      u+= subgraphs.distinct.size
    }
    u
  }

Ungolfed version. Attempt This Online!

import scala.math.Ordering.Implicits.seqOrdering

object Main {

  def extractNodesFromEdges(edges: List[(Int, Int)]): Set[Int] = {
    edges.flatMap { case (a, b) => List(a, b) }.toSet
  }

  def toTuple[A](seq: Seq[A]): List[A] = {
    seq.toList
  }

  def buildAdjacencyList(edges: List[(Int, Int)]): Map[Int, Set[Int]] = {
    edges.foldLeft(Map[Int, Set[Int]]()) { (adjacencyList, edge) =>
      val (a, b) = edge
      adjacencyList.updated(a, adjacencyList.getOrElse(a, Set()) + b)
        .updated(b, adjacencyList.getOrElse(b, Set()) + a)
    }
  }

  def findAllPaths(adjacencyList: Map[Int, Set[Int]]): Map[List[Int], List[List[Int]]] = {
    var queue = adjacencyList.filter(_._2.size == 1).keys.map(node => (node, List(node), List(adjacencyList(node).size))).toList
    var paths = Map[List[Int], List[List[Int]]]()

    while (queue.nonEmpty) {
      val (currentNode, path, degrees) = queue.head
      queue = queue.tail

      var isLeaf = true

      for (neighbor <- adjacencyList(currentNode) -- path.toSet) {
        queue = queue :+ (neighbor, path :+ neighbor, degrees :+ adjacencyList(neighbor).size)
        isLeaf = false
      }

      if (isLeaf) {
        val degreesTuple = toTuple(degrees)
        val reversedDegreesTuple = toTuple(degrees.reverse)

        if (paths.contains(degreesTuple)) {
          if (!paths(degreesTuple).contains(path) && !paths(degreesTuple).contains(path.reverse)) {
            paths = paths.updated(degreesTuple, paths(degreesTuple) :+ path)
          }
        } else if (paths.contains(reversedDegreesTuple)) {
          if (!paths(reversedDegreesTuple).contains(path) && !paths(reversedDegreesTuple).contains(path.reverse)) {
            paths = paths.updated(reversedDegreesTuple, paths(reversedDegreesTuple) :+ path)
          }
        } else {
          paths = paths.updated(degreesTuple, List(path))
        }
      }
    }

    paths
  }

  def countUniqueSubgraphs(edges: List[(Int, Int)]): Int = {
    val paths = findAllPaths(buildAdjacencyList(edges))
    var uniqueCount = 0

    for ((degrees, pathList) <- paths) {
      var subgraphs = List[List[List[Int]]]()

      for (path <- pathList) {
        val remainingEdges = edges.filter { case (a, b) => !path.contains(a) && !path.contains(b) }
        val remainingNodes = extractNodesFromEdges(edges).diff(extractNodesFromEdges(remainingEdges)).diff(path.toSet)
        val newSubgraph = findAllPaths(buildAdjacencyList(remainingEdges ++ remainingNodes.map(node => (node, node)))).keys.toList
        subgraphs = subgraphs :+ newSubgraph.map(_.sorted)
      }
      uniqueCount += subgraphs.distinct.size
    }

    uniqueCount
  }

  def main(args: Array[String]): Unit = {
    println(countUniqueSubgraphs(List((1, 2), (2, 3), (3, 4), (3, 5))))
    println(countUniqueSubgraphs(List((1, 2), (2, 3), (3, 4), (5, 6), (6, 7), (3, 7), (7, 8))))
    println(countUniqueSubgraphs(List((1, 2), (2, 3), (3, 4), (3, 5), (3, 6), (3, 7))))
    println(countUniqueSubgraphs(List((1, 2), (2, 3), (3, 4), (3, 5), (5, 6), (6, 7), (6, 8), (6, 9))))
    println(countUniqueSubgraphs(List((1, 2), (2, 3), (3, 4), (4, 5), (4, 6), (7, 8), (8, 9), (6, 9), (9, 10))))
    println(countUniqueSubgraphs(List((1, 2), (2, 3), (3, 4), (4, 5), (4, 6), (6, 7), (4, 8), (8, 9), (9, 10), (9, 11), (11, 12))))
    println(countUniqueSubgraphs(List((1, 2), (2, 3), (2, 4), (4, 5), (4, 6), (6, 7), (7, 8), (7, 9))))
  }
}