<p>This is simple. You have basically a <a href="http://en.wikipedia.org/wiki/Hasse_diagram" rel="noreferrer">Hasse diagram</a> on which you need to perform a <a href="http://en.wikipedia.org/wiki/Topological_sorting" rel="noreferrer">topological sort</a> to determine the order in which to complete a set of tasks, some of which depend on others. Each subset of the tasks for which order is not significant can be executed in parallel. You can divide these into your "cells" (threads?) however you please.</p>

<p>So, for example, based on the graph you gave, you ought to get a list of sets:</p>

<p>{C, A, B}, {I, E, F, G}, {K, L, H, J}, {D}</p>

<p>Each set contains all tasks that must be completed to fulfill the prerequisites of the tasks in the next set, and all tasks in a set can be executed simultaneously.</p>

CC BY-SA 2.5
2011-01-17T23:38:59.657Z
Judging from the example in the question, I do not think that this is what is being asked.  However, I have no idea what is being asked.
Tsuyoshi Ito
CC BY-SA 2.5
2011-01-18T03:58:18.257Z
@Tsuyoshi Ito: My reasoning about it comes from how he divided the tasks into cells. If you read first from Cell 1, then 2, then 3, then back to 1 and so on, you get (C, A, B, I, E, F, K, H, G, D, L, J), which is a valid topological sort of the graph. And the cells can easily represent threads, because each set of three tasks in that sort can be carried out in parallel. It doesn't work quite so neatly for all graphs, but still, that seems to be the fundamental problem at work here.
Jon Purdy
CC BY-SA 2.5
2011-01-18T06:44:58.320Z
@Jon.Thank you.Please could you explain how can I sort those tasks to the cells so it will answer my conditions(for ex. 4 neighbors )
YAKOVM
CC BY-SA 2.5
2011-01-18T06:59:50.317Z
@Yakov: I'm afraid I still don't understand what you mean by "4-neighbours". Do you have a grid, some of whose cells are connected to form a graph, that puts some constraint on the order of the output?
Jon Purdy
CC BY-SA 2.5
2011-01-18T07:13:01.247Z
http://books.google.com/books?id=fGX8yC-4vXUC&lpg=PA24&dq=%2C4%20adjacency%2C&pg=PA23#v=onepage&q=%2C4%20adjacency%2C&f=false- Here is an explanation.Only adjacent cells can use information from each other.So for example to do "I" task the cell that exucuted C and D should be adjacent.
YAKOVM
CC BY-SA 2.5
2011-01-18T10:10:49.310Z
@Yakov: I think I understand, but I don't know how to solve it.
Jon Purdy
CC BY-SA 2.5
2011-01-18T10:28:55.460Z
@Jon:Maybe you could help me to rephrase the question better so people will remove their negative marks and unterstand the question.
YAKOVM
CC BY-SA 2.5
2011-01-17T22:00:26.497Z
2011-01-17T22:09:54.297Z
2011-01-17T22:09:54.297Z
Jon Purdy
<p>Given a DAG (which represents DDG – each node is a operation the in-edge/s show the operands from which inputs are taken) I want to obtain its compact representation of the graph, in such a way that:</p>

<ol>
<li>Each node is mapped to the cell.(To
the some cell several nodes can be
mapped) The communication is exists
between cells in 4-neighbors(adjacency).</li>
<li>In the example below node I get
“results” (as operands) from nodes C
and E and we can see that they were
mapped in the proper way
(4-neighbors(adjacency)).</li>
<li>The result from each operation is
transformed in 4-neighbors(adjacency). It means
(in the below example) that after
cell 1 has calculated C the
operation result maybe used by cell 2 (And ofcourse it maybe used by cell
1 also).</li>
<li>The motivation is to execute the
operations in parallel in minimum
time and in minimum cells.Each Cell
can execute one node at a time</li>
</ol>

<p>(The graph drawing I get using bary-center algorithm for cross-edges minimization, I think this information can help while the mapping is performed…)</p>

<p>4-neighbors(adjacency)-Only adjacent cells can use information from each other.So for example to do "I" task the cell that executed C and D should be adjacent. More at <a href="http://books.google.com/books?id=fGX8yC-4vXUC&amp;lpg=PA24&amp;dq=%2C4%20adjacency%2C&amp;pg=PA23#v=onepage&amp;q=%2C4%20adjacency%2C&amp;f=false-" rel="nofollow noreferrer">http://books.google.com/books?id=fGX8yC-4vXUC&amp;lpg=PA24&amp;dq=%2C4%20adjacency%2C&amp;pg=PA23#v=onepage&amp;q=%2C4%20adjacency%2C&amp;f=false-</a></p>

<p>Can you give some advice for such mapping algorithm?</p>

<p>Thank you in advance
<img src="https://i.sstatic.net/IKW8k.png" alt="alt text"></p>

CC BY-SA 2.5
2011-01-17T18:35:00.647Z
Your question is bordering on incoherent, I'm sorry to say. What do you mean by a compact representation ? and how does the table you drew satisfy the requirements. While examples are helpful, they cannot replace a FORMAL description of the problem, and you don't have that. Please don't add more description - try to make your question PRECISE
Suresh Venkat
CC BY-SA 2.5
2011-01-17T18:39:55.933Z
But I have explained what do I mean by "compact" and table representation in 1,2,3.Could you explain what is not clear?.You may remove word "compact" it will not change the question
YAKOVM
CC BY-SA 2.5
2011-01-17T18:56:17.743Z
What is 4-adjacency ? are adjacencies between cells meaningful ? do you want a "drawing" of the cells ? Why do I care about "results" from nodes ? What is a DDG ? Why is the graph drawing important for thinking about this problem ?
Suresh Venkat
CC BY-SA 2.5
2011-01-17T19:09:00.993Z
ddg-data dependence graph.I will answer other questions shortly
YAKOVM
CC BY-SA 2.5
2011-01-17T19:26:07.517Z
4-adjacency- it also called 4 neighbors http://books.google.com/books?id=fGX8yC-4vXUC&lpg=PA24&dq=%2C4%20adjacency%2C&pg=PA23#v=onepage&q=%2C4%20adjacency%2C&f=false-
YAKOVM
CC BY-SA 2.5
2011-01-17T19:33:41.220Z
"Why is the graph drawing important for thinking about this problem ?" Because I think it will be easier to solve the problem intuitively I understand how to do it but there should be some algorithm
YAKOVM
CC BY-SA 2.5
2011-01-17T19:40:37.317Z
As stated, your problem can be solved by mapping every node in your DAG to a single cell.
Jeffε
CC BY-SA 2.5
2011-01-17T19:44:51.213Z
@Jeffe: But if I map C,A,B to the same cell I cannot execute it simultaneously
YAKOVM
CC BY-SA 2.5
2011-01-17T19:46:01.367Z
But that's @JeffE's point: your problem as stated doesn't capture what your intuition appears to desire.
Suresh Venkat
CC BY-SA 2.5
2011-01-17T19:47:36.887Z
The word "execute" does not appear in your problem statement, so it's not relevant to the problem *as stated*.
Jeffε
CC BY-SA 2.5
2011-01-17T19:53:02.813Z
I have edited the question
YAKOVM
CC BY-SA 2.5
2011-01-17T20:50:52.527Z
I'm recommending closing this question. It's not our job to divine user intent from am incoherent question, and there are numerous examples on the site of actual good questions.
Suresh Venkat
CC BY-SA 2.5
2011-01-17T22:02:55.447Z
@Suresh Venkat: It's actually quite a simple question, unless I'm thoroughly misunderstanding it. We on StackExchange sites should be more forgiving of questions that are asked with good intent and honest effort, regardless of their actual quality, especially when a calm and careful reading is all that's needed to understand them.
Jon Purdy
CC BY-SA 2.5
2011-01-17T22:38:28.427Z
@Jon you're probably right. from my perspective, I spend a lot of time trying to nudge posters to make things clear in their questions. I only do this because I don't want the site to be cluttered by less than clear questions. so it's a little frustrating sometimes.
Suresh Venkat
CC BY-SA 2.5
2011-01-17T23:51:27.297Z
I might have agreed with Jon if a calm and careful reading were really all that’s needed to understand this question.
Tsuyoshi Ito
CC BY-SA 2.5
2011-01-18T10:29:36.193Z
@All: I have edited the question once more.Maybe you could remove your negative marks
YAKOVM
CC BY-SA 2.5
2011-01-18T22:57:34.770Z
Nope.  Still incoherent.  In particular, the word "execute" still does not appear in the question, so my previous objection still stands.  I honestly have no idea what "the operation result has transformed to the cell 2" is supposed to mean.  @Jon: If a simple question really is hiding here, perhaps you could help @Yakov clarify it?
Jeffε
CC BY-SA 2.5
2011-01-19T05:05:22.527Z
@Jeffe Please Reread point 4.I have clarified also the "transform".Its just means that the data can be used only by adjacent cells
YAKOVM
CC BY-SA 2.5
2011-01-19T10:24:58.410Z
Visually speaking, you want to cut the tree (forest) in as few as possible, as similar in size as possible pieces in a "planar" (non-crossing lines from top to bottom) way. Correct? (Of course, you need to have a proper visualisation of the graph, first, for this intuition)
Raphael
<graph-theory><ds.data-structures><graph-algorithms><directed-acyclic-graph>
Compact representation of DAG,
YAKOVM
# Compact representation of DAG,

(Asked by: username_0 on 2011-01-17)

Given a DAG (which represents DDG – each node is a operation the in-edge/s show the operands from which inputs are taken) I want to obtain its compact representation of the graph, in such a way that:

1. Each node is mapped to the cell.(To
   the some cell several nodes can be
   mapped) The communication is exists
   between cells in 4-neighbors(adjacency).
2. In the example below node I get
   “results” (as operands) from nodes C
   and E and we can see that they were
   mapped in the proper way
   (4-neighbors(adjacency)).
3. The result from each operation is
   transformed in 4-neighbors(adjacency). It means
   (in the below example) that after
   cell 1 has calculated C the
   operation result maybe used by cell 2 (And ofcourse it maybe used by cell
   1 also).
4. The motivation is to execute the
   operations in parallel in minimum
   time and in minimum cells.Each Cell
   can execute one node at a time

(The graph drawing I get using bary-center algorithm for cross-edges minimization, I think this information can help while the mapping is performed…)

4-neighbors(adjacency)-Only adjacent cells can use information from each other.So for example to do "I" task the cell that executed C and D should be adjacent. More at <http://books.google.com/books?id=fGX8yC-4vXUC&lpg=PA24&dq=%2C4%20adjacency%2C&pg=PA23#v=onepage&q=%2C4%20adjacency%2C&f=false->

Can you give some advice for such mapping algorithm?

Thank you in advance
![alt text](https://i.sstatic.net/IKW8k.png)

**Tags:** graph-theory, ds.data-structures, graph-algorithms, directed-acyclic-graph

> **Comments:**
> **username_1**: Your question is bordering on incoherent, I'm sorry to say. What do you mean by a compact representation ? and how does the table you drew satisfy the requirements. While examples are helpful, they cannot replace a FORMAL description of the problem, and you don't have that. Please don't add more description - try to make your question PRECISE  
> **username_0**: But I have explained what do I mean by "compact" and table representation in 1,2,3.Could you explain what is not clear?.You may remove word "compact" it will not change the question  
> **username_1**: What is 4-adjacency ? are adjacencies between cells meaningful ? do you want a "drawing" of the cells ? Why do I care about "results" from nodes ? What is a DDG ? Why is the graph drawing important for thinking about this problem ?  
> **username_0**: ddg-data dependence graph.I will answer other questions shortly  
> **username_0**: 4-adjacency- it also called 4 neighbors http://books.google.com/books?id=fGX8yC-4vXUC&lpg=PA24&dq=%2C4%20adjacency%2C&pg=PA23#v=onepage&q=%2C4%20adjacency%2C&f=false-  
> **username_0**: "Why is the graph drawing important for thinking about this problem ?" Because I think it will be easier to solve the problem intuitively I understand how to do it but there should be some algorithm  
> **username_2**: As stated, your problem can be solved by mapping every node in your DAG to a single cell.  
> **username_0**: @Jeffe: But if I map C,A,B to the same cell I cannot execute it simultaneously  
> **username_1**: But that's @JeffE's point: your problem as stated doesn't capture what your intuition appears to desire.  
> **username_2**: The word "execute" does not appear in your problem statement, so it's not relevant to the problem *as stated*.  
> **username_0**: I have edited the question  
> **username_1**: I'm recommending closing this question. It's not our job to divine user intent from am incoherent question, and there are numerous examples on the site of actual good questions.  
> **username_3**: @username_1: It's actually quite a simple question, unless I'm thoroughly misunderstanding it. We on StackExchange sites should be more forgiving of questions that are asked with good intent and honest effort, regardless of their actual quality, especially when a calm and careful reading is all that's needed to understand them.  
> **username_1**: @Jon you're probably right. from my perspective, I spend a lot of time trying to nudge posters to make things clear in their questions. I only do this because I don't want the site to be cluttered by less than clear questions. so it's a little frustrating sometimes.  
> **username_4**: I might have agreed with Jon if a calm and careful reading were really all that’s needed to understand this question.  
> **username_0**: @All: I have edited the question once more.Maybe you could remove your negative marks  
> **username_2**: Nope.  Still incoherent.  In particular, the word "execute" still does not appear in the question, so my previous objection still stands.  I honestly have no idea what "the operation result has transformed to the cell 2" is supposed to mean.  @Jon: If a simple question really is hiding here, perhaps you could help @Yakov clarify it?  
> **username_0**: @Jeffe Please Reread point 4.I have clarified also the "transform".Its just means that the data can be used only by adjacent cells  
> **username_5**: Visually speaking, you want to cut the tree (forest) in as few as possible, as similar in size as possible pieces in a "planar" (non-crossing lines from top to bottom) way. Correct? (Of course, you need to have a proper visualisation of the graph, first, for this intuition)  

---

## 1 answers

### Answer by username_3 on 2011-01-17. Score: 5 | Accepted answer

This is simple. You have basically a [Hasse diagram](http://en.wikipedia.org/wiki/Hasse_diagram) on which you need to perform a [topological sort](http://en.wikipedia.org/wiki/Topological_sorting) to determine the order in which to complete a set of tasks, some of which depend on others. Each subset of the tasks for which order is not significant can be executed in parallel. You can divide these into your "cells" (threads?) however you please.

So, for example, based on the graph you gave, you ought to get a list of sets:

{C, A, B}, {I, E, F, G}, {K, L, H, J}, {D}

Each set contains all tasks that must be completed to fulfill the prerequisites of the tasks in the next set, and all tasks in a set can be executed simultaneously.

> **Comments:**
> **username_4**: Judging from the example in the question, I do not think that this is what is being asked.  However, I have no idea what is being asked.  
> **username_3**: @username_4: My reasoning about it comes from how he divided the tasks into cells. If you read first from Cell 1, then 2, then 3, then back to 1 and so on, you get (C, A, B, I, E, F, K, H, G, D, L, J), which is a valid topological sort of the graph. And the cells can easily represent threads, because each set of three tasks in that sort can be carried out in parallel. It doesn't work quite so neatly for all graphs, but still, that seems to be the fundamental problem at work here.  
> **username_0**: @Jon.Thank you.Please could you explain how can I sort those tasks to the cells so it will answer my conditions(for ex. 4 neighbors )  
> **username_3**: @Yakov: I'm afraid I still don't understand what you mean by "4-neighbours". Do you have a grid, some of whose cells are connected to form a graph, that puts some constraint on the order of the output?  
> **username_0**: http://books.google.com/books?id=fGX8yC-4vXUC&lpg=PA24&dq=%2C4%20adjacency%2C&pg=PA23#v=onepage&q=%2C4%20adjacency%2C&f=false- Here is an explanation.Only adjacent cells can use information from each other.So for example to do "I" task the cell that exucuted C and D should be adjacent.  
> **username_3**: @Yakov: I think I understand, but I don't know how to solve it.  
> **username_0**: @Jon:Maybe you could help me to rephrase the question better so people will remove their negative marks and unterstand the question.  

---

