Help me traverse a network of data.

February 12, 2009 4:11 AM

Data/Python/Other programming filter: How do I construct and traverse a simple network of data?

I have a large list of numbered nodes, with corresponding values between them. I would like to be able to find out the total value between any two nodes. For example:

n1 to n2 = 5
n2 to n3 = 2
n2 to n4 = 6

So the total of n1 to n4 = 5 + 6, and the total of n1 to n3 = 5 + 2.

I am struggling to figure out exactly what this problem would be called to google it. I have been having a play in python but can't quite figure out how to approach the problem.

Does anyone have any experience doing something like this, and know of a resource/have any tips for me?

posted by latentflip to computers & internet (7 comments total)

I assume that you're looking for Dijkstra's algorithm, though your description of the graphs isn't quite sufficient to figure out whether they a) satisfy the requirements and b) require the full mechanism.
posted by themel at 4:29 AM on February 12

I believe graph is the search term you are looking for. I would suggest implementing it in lisp for shits and giggles.
posted by ghost of a past number at 4:29 AM on February 12

If I read you correctly, you've got a cost tree, usually refered to as "minimum cost tree", and used for routing of different kinds.
posted by Harald74 at 4:29 AM on February 12

You can start digging on All-Pairs Shortest Path.
posted by fleacircus at 4:48 AM on February 12

It's actually just a huge list of resistors. There should only be one path between any two nodes, it will just be made up of lots of individual sections.

I will have a look into Dijkstra's algorithm tho, as it should presumably work with just one path.
posted by latentflip at 4:53 AM on February 12

It's probably not a "network", but a "graph". A "network" tends to refer to an interconnected group of thingies that do stuff and then pass the results on to another thingie; a "graph" tends to refer to a datastructure with nodes and connections, where you're analyzing attributes of the nodes and connections.

And, as themel mentioned, Dijkstra's algorithm is the (provably) best algorithm for finding minimum paths through a graph. That wikipedia link even has sample Python code.

However, I don't know if your data structure is actually a graph, nor if what you're talking about is actually the shortest path. Generally a graph is defined as a set of nodes, and a set of edges. The nodes are just {n1, n2, n3, n4, n5, ...}, while the edges are {e1=(n1, n2), e2=(n1, n3), e3=(n2, n3), e4=(n2, n4), e5=(n4, n5)}. Since you talk about costs between them, you would then have a set of weights {(e1, 2), (e2, 2), (e3, 242), (e4, 12), (e5, 2)}. If we drew this, using crappy ascii graphics, we'd have something like this:

     [2]   [12]   [2]
n1-----n2-----n4----n5
  \        |
2] \      | [242]
      \    |
         n3

Dijkstra is then capable of saying that the shortest path between n1 and n5 is (n1, n2, n4, n5) with a cost of 16. This is obvious to a human, but without an algorithm, the computer has no idea that (n1, n3, n2, n4, n5) isn't equally cheap. Dijkstra does better than simply testing all the routes and keeping the best.
posted by Netzapper at 4:58 AM on February 12

Since you mentioned Python, you might find some the available graph libraries useful. Check out NetworkX or python-graph.
posted by ijoshua at 11:11 AM on February 12 [1 favorite has favorites]