Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a 2D grid of arbitrary positive integer points, minimum being $0,0$ to a maximum of $n,n$. I can only traverse points by increasing my $x$ and/or $y$ coordinate (no backtracking).

Is this sort of data structure a directed acyclic graph? If so, how can I "convert" it to "linear" sequence form?

share|improve this question
    
Can you clarify, what do you mean by "convert it to linear sequence form"? What are you trying to calculate? –  Calvin Lin Jan 20 '13 at 16:45
    
@CalvinLin So I can convert it to a 1D array representation –  MyNameIsKhan Jan 20 '13 at 16:54
add comment

2 Answers 2

I am not sure if I get your question but here it is. The graph is a directed acyclic graph with $n^2$ vertices.

If you label each cell $(i, j)$ of the grid with $in + j \ \textit{mod} \ n$ then you can create a 1d array to represent the graph where the $k$-th index represents the $k$-th vertex. From position $k$ you can go to position $k + 1$ if $k < n - 1$ and $k + n$ if $k < (n - 1)n$.

But you still need $n^2$ positions so I don't understand what you want to do exactly. If you can be clearer then maybe I can help more.

share|improve this answer
    
I have a grid of size n by n. I have points on this grid (arbitrary number / position of them). I can only go from one point to another, and I can only go to an immediately visible point that is greater than the one I am currently at in either x, y, or both x and y coordinate. –  MyNameIsKhan Jan 20 '13 at 17:42
add comment

First, as has been mentioned, this is a directed acyclic graph. It sounds like your "linear sequence form" is an arrangement of the vertices in a left-to-right sequence $\langle v_1, v_2, \dots , v_n\rangle$ such that any edge goes from left to right in the sequence. If so, you're asking for what's commonly known as a topological sort of the vertices.

For your graphs an easy way to do this is to order the vertices first by weight, where the weight of a vertex $w(i, j)=i+j$ and then within each weight order the vertices by their first coordinate. For example, if $n=2$ we'll have the linear order $$ (0,0), (0, 1), (1, 0), (0, 2), (1, 1), (2, 0), (1, 2), (2, 1), (2, 2) $$ Now look at the edges. From $(i, j)$ we'll have edges to $(i+1, j), (i, j+1), (i+1, j+1)$, as long as $i+1\le n$ and $j+1\le n$. Each of these edges will have weight strictly greater than $i+j$ so each of the edges from $(i, j)$ will end at a vertex of greater weight, hence to the right of $(i, j)$. This also shows that the graph is acyclic.

Notice that there are other ways of arranging the vertices in a line (simply permute the edges of equal weights).

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.