Representing a tree as glued half-edges

Question

I have a tree, given e.g. as a networkx object. In order to inpput it into a black-box algorithm I was given, I need to save it in the following strange format:

Traverse the tree in a clockwise order. As I pass through one side of an edge, I label it incrementally. Then I want to save for each edge the labels of its two sides.

For example, a star will become a list [(0,1),(2,3),(4,5),...] and a path with 3 vertices will be [(0,3),(1,2)].

I am stumped with implementing this. How can this be done? I can use any library.

Answer 1

I'll answer this without reference to any library.

You would need to perform a depth-first traversal, and log the (global) incremental number before you visit a subtree, and also after you visited it. Those two numbers make up the tuple that you have to prepend to the result you get from the subtree traversal.

Here is an implementation that needs the graph to be represented as an adjacency list. The main function needs to get the root node and the adjacency list

def iter_naturals(): # helper function to produce sequential numbers
    n = 0
    while True:
        yield n
        n += 1

def half_edges(root, adj):
    visited = set()
    sequence = iter_naturals()

    def dfs(node):
        result = []
        visited.add(node)
        for child in adj[node]:
            if child not in visited:
                forward = next(sequence)
                path = dfs(child)
                backward = next(sequence)
                result.extend([(forward, backward)] + path)
        return result

    return dfs(root)

Here is how you can run it for the two examples you mentioned. I have just implemented those graphs as adjacency lists, where nodes are identified by their index in that list:

Example 1: a "star":

The root is the parent of all other nodes

adj = [
    [1,2,3], # 1,2,3 are children of 0
    [], 
    [],
    []
]
print(half_edges(0, adj))  # [(0, 1), (2, 3), (4, 5)]

Example 2: a single path with 3 nodes

adj = [
    [1], # 1 is a child of 0
    [2], # 2 is a child of 1
    []
]
print(half_edges(0, adj))  # [(0, 3), (1, 2)]