[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [ProgSoc] Traversing a Graph



Nathan de Vries wrote:
Howdy folks,

I'm hoping some of you folks with data mining experience can help out.
I've got a data set which consists of a bunch of nodes. Each node also
has one or more "links", which connect that particular node to another
node. In YAML:

--- "0x8085848dbd4cfc3b": - "0x8085848dbce6d0ed"
- "0x8085848d983f8581"
"0x808584ed7a4d17ff": - "0x808584ed7bdc8265"
- "0x808584ed7af291f5"
"0x808584f2f7476807": - "0x808584f2f9f9f0a1"
- "0x808584f2f6e677d5"
"0x80858466b61a63f1": - "0x80858466ca6b248f"
- "0x80858466b6fa2ead"


Does anyone know how to store this data set and mine it for the longest
path (max number of hops, as little repetition of paths as possible)?

In case you're wondering, each "node" represents a frame of video, and
each link represents a potential next frame. At the moment, I've
produced this:

	http://progsoc.org/~ndvries/sv.mp4


Can you assume you can only jump forwards? i.e. is it cyclic or not?

If you can only go forwards, you can keep a hop-count at each node and eliminate (or collapse) nodes behind. I imagine your dataset is quite large for video frames, so you would need to be collapsing as many nodes as possible and just keeping the "front runners".

Even if it was cyclic, you could do two passes - store a list of unresolved links (probably need a efficient structure like binary tree or hash) and anything that hasn't been resolved by the end is known to be cyclic. Then in the second pass, resolve the backward links and readjust the structure generated (e.g. re-insert intermediate nodes that might have been previously cancelled).

From this you would have a collapsed graph from which to do calculations. Depending on how many potential paths, you would need to test each variant (or at least the forward-movement ones, if there is a monotonic path), which could be quite a large set. You could use routing algorithms such as dijkstra's algorithm to calculate the "shortest path" [1,2], using the frame distance counts as weights. Hopefully its not a NP-hard problem like TSP [3].

Cheers,

Nigel

[1] http://en.wikipedia.org/wiki/Shortest_path
[2] http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
[3] http://en.wikipedia.org/wiki/Travelling_salesman_problem

--
UTS CRICOS Provider Code:  00099F
DISCLAIMER: This email message and any accompanying attachments may contain
confidential information.  If you are not the intended recipient, do not
read, use, disseminate, distribute or copy this message or attachments.  If
you have received this message in error, please notify the sender
immediately and delete this message. Any views expressed in this message
are those of the individual sender, except where the sender expressly, and
with authority, states them to be the views the University of Technology,
Sydney. Before opening any attachments, please check them for viruses and
defects.

-
You are subscribed to the progsoc mailing list. To unsubscribe, send a
message containing "unsubscribe" to progsoc-request@xxxxxxxxxxxxxxxxxxx
If you are having trouble, ask owner-progsoc@xxxxxxxxxxxxxxxxxx for help.