[SciPy-User] Graph(?) simplification/optimization problem

classic Classic list List threaded Threaded
1 message Options
Reply | Threaded
Open this post in threaded view

[SciPy-User] Graph(?) simplification/optimization problem

Sebastian Berg
Hi all,

Just in case someone knows simple approaches to this type of problem:

I am wondering about finding a nicer solution for something like a
graph simplification problem.

I have pairs of nodes which are developing/moving over time (pairs if
there are two, but at each time step they form a circle with an even
number, so calling them "n" and "p"):

t=0   -n-------p-
       |   |   |
       |  / \  |
t=1   -n--p-n--p-
       \  / |  |
        \/  |  |
t=2   ------n--p-

Now the algorithm is supposed to "remove" the new p at t=1 which is
there only for a short time and is assumed to be unimportant. Since you
can only remove pairs, one of the "n" needs to be removed as well.
In this case, deciding which "n" to also delete does not matter much
(there are other heuristics to prefer one direction), but in general it
can be non-trivial in my case.

The overall goal would be to (also) maximize lifespans for individual
"nodes", though.
The exact optimization function would probably need some tuning, but I
am wondering if there is a nice approach for this type of problem.

I imagine that I can formulate it as a big integer programming problem,
but it doesn't seem that straight forward on first glance. Currently I
use some greedy strategies, but while it works fine, I am pretty sure
that in some events it gets stuck and does not find the best solution.

Anyway, just in case someone happens to know this type of problem and
has a tip :).


SciPy-User mailing list
[hidden email]

signature.asc (817 bytes) Download Attachment