Thread: What kind of graph do I have?

1. What kind of graph do I have?

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.

2. Re: What kind of graph do I have?

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.
Based on your description, the graph is connected (as there is always a path between every two nodes, and the path is unique). It sounds to me like you have a tree.

3. Re: What kind of graph do I have?

Thanks, you must be right about it being a tree. It has no distinguished root though. Here's an example:

I guess I could just pick a node at random and call it the root (Is there a better way?). I'll need to calculate a sort of distance function between every pair of nodes, so I should be able to sweep through the tree once and store distances from each node to the root, and calculate the distance from A to B as a distance from A to root plus distance from root to B minus 2 * distance from the lowest common ancestor to the root. Any advice on a quick way to locate the lowest common ancestor of A and B?