|
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
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
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> 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.
Hmm. If you ensure that all routing is from one row to the adjacent row,
then no, it shouldn't be possible. Good point! (Should also be
impossible for an edge to cross a node.)
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |