File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
The moose likes Programming Diversions and the fly likes Knots from graphs Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Other » Programming Diversions
Bookmark "Knots from graphs" Watch "Knots from graphs" New topic

Knots from graphs

Ryan McGuire
Ranch Hand

Joined: Feb 18, 2005
Posts: 1044
How about this for a problem to try to solve programmatically.

Given a continuous graph, determine whether it it would form a knot if you pulled the two ends.

Example 1: In its initial position, a string goes from (0,2) to (3,2) to (1,1) to (2,3) to (2,0), alternating over and under at each intersection. If you pull the two ends directly away from each other, the string would form an overhand knot.

Example 2: The string has the same basic initial position as in Example 1, but it goes over-over-under-under-under-over along the path. Pulling on the ends would produce no knots.

I can see a number of hurdles to pass:
  • Define the question more rigorously.
  • List any specific knots we might to identify by name. For instance, I could see the output being one of [no knot, overhand, figure 8, something else]
  • Figure out a good input "language"
  • Develop an algorithm to figure out the answer.

  • Thoughts?
    [ September 14, 2007: Message edited by: Ryan McGuire ]
    Arjun Shastry
    Ranch Hand

    Joined: Mar 13, 2003
    Posts: 1893
    In the second example,string will go 'Over--->Over--->Under'.only three intersections,correct?

    Jim Yingst

    Joined: Jan 30, 2000
    Posts: 18671
    I think it might make sense to simply use three dimensions for all vertices. Then you can input a list of points which describe any possible 3-D knot. Any input for which two lines intersect is invalid - the input must keep the lines far enough apart that they don't appear to intersect. There could be numeric roundoff issues here - for simplicity, let's say input lines can come no closer than a distance of 0.1.

    A simple input language might be:

    Each line represents a single point. A line consists of three numbers in decimal format, separated by commas. A blank line signals the end of a given string (which may or may not be a not. Input may contain multiple strings to solve. Two blank lines signals the end of all strings.

    "I'm not back." - Bill Harding, Twister
    Ryan McGuire
    Ranch Hand

    Joined: Feb 18, 2005
    Posts: 1044
    Originally posted by Arjun Shastry:
    In the second example,string will go 'Over--->Over--->Under'.only three intersections,correct?

    Yes, there are three intersections, but each intersection is "visited" twice. That's why there's [over|under]{6}.

    Of course the over or under for one segment of the string at an intersection determines the other over/under for the other segment. For instance, in both of my examples if the fourth over/under must be the opposite of the first. So the second three convey no additional information.

    Originally posted by Jim Yingst:
    I think it might make sense to simply use three dimensions for all vertices.

    Yes, but...
    It's harder to draw a input case on (2-D) paper and be sure to get the z coordinates correct. It would also be more difficult to modify one input case into a similar one with just the overs and unders changed. Impossible? Of course not -- just harder.

    e.g. My original first example is just five 2-D points plus (as discussed above) three bits.

    Changing that to the second example involved just changing the bit from 1,0,1 to 1,1,0

    I guess I'm of the opinion that programs should be made to make the user's life as easy as possible, even if it involves quite a bit of extra programming.
    I agree. Here's the link:
    subject: Knots from graphs
    It's not a secret anymore!