Kevin Wampler wrote:

> In practice, you should interpret a problem being NP-complete to mean 
> that any known algorithm will have an exponential worst-case running 
> time.  This does not necessarily mean that you can't efficiently solve 
> the problem instances you encounter in practice, or that it's impossible 
> to quickly solve for an approximate solution.  What sorts of efficiency 
> gains are possible over the worse-case behavior of an exact algorithm 
> will depend on the particulars of the problem and the domain to which 
> you're applying it.

The paper I'm looking at has several places where the program has to 
guess a solution that is "good enough" because finding the perfect 
solution is "NP-complete". Makes it sound like solving such a problem is 
somehow "impossible" - but as you say, all it really means is that it's 
slow. (Or at least, *potentially* slow.)

Post a reply to this message

Invisible wrote:
> The paper I'm looking at has several places where the program has to 
> guess a solution that is "good enough" because finding the perfect 
> solution is "NP-complete". Makes it sound like solving such a problem is 
> somehow "impossible" - but as you say, all it really means is that it's 
> slow. (Or at least, *potentially* slow.)

Yeah, that's basically correct.  It's a pretty well justified approach 
though since often NP-complete problems will take too long to solve 
practically in the average case as well as the worst case.

If you haven't done so before, it can be enlightening to write a program 
to solve some NP-complete problem by brute force, and then get a feel 
for how quickly its running time explodes on larger problems.  It's easy 
to rationally know what `exponential' means, but I've known many people 
to still be surprised when they see for themselves what that entails in 
real life.

What's the paper for out of curiosity?

Post a reply to this message

Kevin Wampler wrote:
> Invisible wrote:
>> The paper I'm looking at has several places where the program has to 
>> guess a solution that is "good enough" because finding the perfect 
>> solution is "NP-complete". Makes it sound like solving such a problem 
>> is somehow "impossible" - but as you say, all it really means is that 
>> it's slow. (Or at least, *potentially* slow.)
> 
> Yeah, that's basically correct.  It's a pretty well justified approach 
> though since often NP-complete problems will take too long to solve 
> practically in the average case as well as the worst case.
> 
> If you haven't done so before, it can be enlightening to write a program 
> to solve some NP-complete problem by brute force, and then get a feel 
> for how quickly its running time explodes on larger problems.  It's easy 
> to rationally know what `exponential' means, but I've known many people 
> to still be surprised when they see for themselves what that entails in 
> real life.
> 
> What's the paper for out of curiosity?

GraphViz paper on graph layout.

For example, finding a global arrangement of all graph nodes that 
minimises the number of edges that cross each other is meant to be 
NP-complete.

In this instance, the point is that finding *the* minimum number of 
crossings isn't hugely important, so long as the number can be kept 
reasonably small. But it's just the implication that this is impossibly 
difficult that bothered me. How long can it possibly take to try all 
possible permutations of 10 nodes?

Post a reply to this message

Invisible wrote:
> But it's just the implication that this is impossibly 
> difficult that bothered me. How long can it possibly take to try all 
> possible permutations of 10 nodes?

Really, try implementing a brute force algorithm and see for yourself 
how it scales.  Ten nodes may work, but what about twenty?  This is an 
important point since if you only have ten nodes you often don't really 
need a graph drawing program to visualize it.  It's when the graph 
becomes larger that it becomes really useful to automatically draw a 
nice picture of it.

If I remember correctly you wanted to draw trees though?  Edge crossings 
certainly wouldn't be a problem there.

Post a reply to this message

>> But it's just the implication that this is impossibly difficult that 
>> bothered me. How long can it possibly take to try all possible 
>> permutations of 10 nodes?
> 
> Really, try implementing a brute force algorithm and see for yourself 
> how it scales.  Ten nodes may work, but what about twenty?

Ah, I see. So you mean the problem is that *other people* might try to 
draw big graphs with it?

> If I remember correctly you wanted to draw trees though?  Edge crossings 
> certainly wouldn't be a problem there.

Trees that occasionally have nodes pointing back to their ancesters, 
yes. ;-)

Weirdly, GraphViz manages to come up with some *really* strange layouts 
- and refuses to obey my hints to lay the graph out the way I actually 
want it...

Post a reply to this message

Invisible wrote:
>>> But it's just the implication that this is impossibly difficult that 
>>> bothered me. How long can it possibly take to try all possible 
>>> permutations of 10 nodes?
>>
>> Really, try implementing a brute force algorithm and see for yourself 
>> how it scales.  Ten nodes may work, but what about twenty?
> 
> Ah, I see. So you mean the problem is that *other people* might try to 
> draw big graphs with it?

Heh, yeah I suppose that's the idea.  I think that "works with graphs of 
up to 12 nodes!" is maybe not the best feature for a piece of software 
to have.


>> If I remember correctly you wanted to draw trees though?  Edge 
>> crossings certainly wouldn't be a problem there.
> 
> Trees that occasionally have nodes pointing back to their ancesters, 
> yes. ;-)

Ahh, that makes sense.  If I remember you didn't want to order of the 
nodes to be able to change, in which case you really don't have as much 
choice


> Weirdly, GraphViz manages to come up with some *really* strange layouts 
> - and refuses to obey my hints to lay the graph out the way I actually 
> want it...

I haven't actually used the program, so I unfortunately can't be of much 
help here.  Since you have a small graph and pretty specific formatting 
requirements, what happened with the app you were writing yourself to do 
the layout?  You could also just draw it in inkscape of course if you 
want a really exact layout.

Post a reply to this message

>>>> But it's just the implication that this is impossibly difficult that 
>>>> bothered me. How long can it possibly take to try all possible 
>>>> permutations of 10 nodes?
>>>
>>> Really, try implementing a brute force algorithm and see for yourself 
>>> how it scales.  Ten nodes may work, but what about twenty?
>>
>> Ah, I see. So you mean the problem is that *other people* might try to 
>> draw big graphs with it?
> 
> Heh, yeah I suppose that's the idea.  I think that "works with graphs of 
> up to 12 nodes!" is maybe not the best feature for a piece of software 
> to have.

I wonder how big the graphs they use it for are? I mean, you can only 
fit a small number of nodes in a single drawing anyway...

>> Trees that occasionally have nodes pointing back to their ancesters, 
>> yes. ;-)
> 
> Ahh, that makes sense.  If I remember you didn't want to order of the 
> nodes to be able to change, in which case you really don't have as much 
> choice

Yeah, I basically already know the relative XY positions of the nodes, I 
just need to put in appropriate spacing and draw the edges nicely. (I 
haven't figured out how to control font selection with Cairo yet!)

>> Weirdly, GraphViz manages to come up with some *really* strange 
>> layouts - and refuses to obey my hints to lay the graph out the way I 
>> actually want it...
> 
> I haven't actually used the program, so I unfortunately can't be of much 
> help here.  Since you have a small graph and pretty specific formatting 
> requirements, what happened with the app you were writing yourself to do 
> the layout?

I think I'm going to reimplement it in light of what I've learned from 
GraphViz. (E.g., it uses invisible nodes that don't show up on the 
drawing, but *do* help it to route edges so they don't collide. I can 
copy that easily enough.)

Post a reply to this message

Invisible wrote:
> I wonder how big the graphs they use it for are? I mean, you can only 
> fit a small number of nodes in a single drawing anyway...

I'd guess that a few tens to a few hundred nodes is not too uncommon.  I 
have seen some graph drawings with millions of nodes, but generally 
these aren't DAGs and are thus drawn with a different technique.


> I think I'm going to reimplement it in light of what I've learned from 
> GraphViz. (E.g., it uses invisible nodes that don't show up on the 
> drawing, but *do* help it to route edges so they don't collide. I can 
> copy that easily enough.)

I'll be interested to see how it looks.  I assume you'll also be 
dropping the bounding box for collision avoidance? :)

Post a reply to this message

>> I wonder how big the graphs they use it for are? I mean, you can only 
>> fit a small number of nodes in a single drawing anyway...
> 
> I'd guess that a few tens to a few hundred nodes is not too uncommon.

...Jesus Christ! o_O

OK, sure, you definitely don't want to use an NP-complete algorithm. :-}

>> I think I'm going to reimplement it in light of what I've learned from 
>> GraphViz. (E.g., it uses invisible nodes that don't show up on the 
>> drawing, but *do* help it to route edges so they don't collide. I can 
>> copy that easily enough.)
> 
> I'll be interested to see how it looks.  I assume you'll also be 
> dropping the bounding box for collision avoidance? :)

Yeah, I'm not overly worried about a few lines crossing. I may or may 
not need to do something about avoiding one path being partially on top 
of another for any great length though...

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

Orchid XP v8 wrote:
> I may or may 
> not need to do something about avoiding one path being partially on top 
> of another for any great length though...

Assuming you're using invisible nodes to route long edges I don't think 
it's possible to have coincident edges, so unless I'm mistaken this 
shouldn't be an issue.

Post a reply to this message