Originally Posted by

**mheins57** Greetings! I'm an old programmer who occasionally has a math question I need help with. I'm currently working with some data structures which form some kind of graph, and I'm trying to figure out exactly what kind of graph it is so that I can look up algorithms that might apply. I'm hoping if I describe the properties of the nodes and edges, someone will recognize it and let me know what official name applies.

The nodes are connected by directed edges; that is, each edge is connected to a left node and a right node. A node may have an arbitrary number of edges to their left and an arbitrary number of edges to their right. An edge may be traversed in either direction, but the value of an associated function of the edge depends on the direction it is traversed. There are no cycles. Each node connects directly to at least one other node. Between any two nodes, there is always exactly one unique path.

I want to say this is a directed acyclic graph but I don't know if it's something more specific than that. Conceptually, my task is to construct a table of every pair of nodes (i, j) and compute the sum of functions of all the edges along the path between i and j, (and also the inverse path from j to i).

If there are N nodes, there are N^2 pairs of nodes (and therefore N^2 paths) to be computed. Each path would have an average of about N/2 edges, so a naive approach would involve considering on the order of (N^3)/2 edges. I am hoping to find an algorithm that will grow more slowly than this as a function of N.