Results 1 to 8 of 8
Thread: Sorting a 2dimensional network?
 03302013, 06:30 AM #1Member
 Join Date
 Mar 2013
 Posts
 87
 Rep Power
 0
Sorting a 2dimensional network?
Hi,
I'm developing a CAD system whereby I can drop any number of blocks. Each block can have a few inputs and outputs, although some just have inputs and some just have outputs.
I call the connectors "Pins" whether they are input or output. Each Pin has a name which includes the word "Input" or "Output" so it is possible at run time to determine which is which.
An input can be connected to only one output, but an output can go to any number of inputs (practically speaking the max would be about 3). Each pin has a place holder for the block and pin of a predecessor (output of a previous block).
I am looking for a way to sort all block ordering (the "order" is simply an int, per block, that is set sequentially when the block is added to the list). Blocks can be added and deleted in any order, so I would expect to have holes in the sequence.
There is a special block called the "Output" block (#5 in the original, #12 after sorting). The "Output" block needs to be the last one (with the largest "order"). Starting from the output block and working backwards from its inputs to driving outputs of previous blocks, I need to walk the entire network and set the ordering correctly. I am not actually swapping the blocks but merely putting the "order" field so that the number of a preceding block is always lower than the following block.
Supposing there was a block that did not have a path to the output block, that block is not included in the rendering step (though it could still be part of the drawing).
Here are a couple images showing what I mean.
Before:
After:
Notice that there are several possible correct answers. For example, in the final sorted network, 6 and 7 could be swapped, as could 10 and 11. I started trying to write down a pseudocode approach and it seems recursive. I figured this problem must have been solved before so I thought I'd ask you brilliant folks how to go about it.
Thanks!
DL
 03302013, 07:49 AM #2Moderator
 Join Date
 Feb 2009
 Location
 New Zealand
 Posts
 4,717
 Rep Power
 16
Re: Sorting a 2dimensional network?
One initial observation is that you need to make an explicit condition on your network that there can not be a cycle: that is a path from any block back to itself. Such a cycle would defeat any attempt to number each block with a number strictly greater than all of the blocks connected to it.

If I understand your question correctly what you have is a certain type of directed acyclic graph. In it's (much studied) generalised form no special assumption is made about the pins and the fact that an output pin can go multiple places while an input must come from only one. Basically a DAG "is formed by a collection of vertices and directed edges, each edge connecting one vertex to another, such that there is no way to start at some vertex v and follow a sequence of edges that eventually loops back to v again." according to Wikipedia.
A well known (to anyone whose read that page!) fact about DAGs is that they posses a socalled "topological ordering", ie "an ordering of the vertices such that the starting endpoint of every edge occurs earlier in the ordering than the ending endpoint of the edge". And that appears to be exactly what you're looking for.
Hopefully the jargon (DAG, topological ordering) will help in googling.Last edited by pbrockway2; 03302013 at 08:03 AM.
 03302013, 08:24 AM #3Moderator
 Join Date
 Feb 2009
 Location
 New Zealand
 Posts
 4,717
 Rep Power
 16
Re: Sorting a 2dimensional network?
According to http://homes.cs.washington.edu/~jrl/421slides/lec5.pdf where they give a proof, remove some node that has no lines entering it and just keep doing that. When you remove a node some other node may well end up with no lines entering it and thereby become a candidate for removal. It is an important fact about DAGs that there will always be a node you can remove.
The nodes in the order you removed them gives the topological ordering.
 03312013, 05:59 PM #4Member
 Join Date
 Mar 2013
 Posts
 87
 Rep Power
 0
Re: Sorting a 2dimensional network?
Hi everyone, thanks for the responses. As it turns out, the first thing I tried seems to work, however it requires a few iterations. As the models are generally very small, this is not a problem. The number of required passes through the model to get it completely sorted seems to vary depending both on the unsortedness of the original list as well as a topological dependency which I haven't actually figured out.
Here's my code for the sorting method:
Java Code:public int modelSort() { Iterator<SpinCADBlock> itr = blockList.iterator(); System.out.printf("Model sort...\n", name); SpinCADBlock block; int b = 1; int nSwaps = 0; while(itr.hasNext()) { block = itr.next(); Iterator<SpinCADPin> itrPin = block.pinList.iterator(); SpinCADPin currentPin; while(itrPin.hasNext()) { currentPin = itrPin.next(); SpinCADBlock cB = currentPin.getBlockConnection(); SpinCADPin cP = currentPin.getPinConnection(); if(cB != null && cP != null) { b = block.getBlockNum(); if (b < cB.getBlockNum()) { int c = cB.getBlockNum(); block.setBlockNum(c); cB.setBlockNum(b); nSwaps++; } } } } return nSwaps; }
I had thought I would need to explicitly identify the output block and repeatedly start from there. However, the output block is unique in that it only has inputs, no outputs, and it seems that the algorithm itself automatically sorts the output block to the end of the list as a result of this.
What I'm doing for testing is to create an arrangement of blocks and connections, then run the sort algorithm. I see how many swaps were done and if it's > 0 then I sort again. For all of the models I've tried so far, it has taken no more than 5 passes to get it completely sorted. Since it works I'm not too worried about it. I will put the sorting inside an iterator that will run once for each block in the list. When the number of swaps gets to zero, I'll know it's completely sorted and will bail.
In the back of my mind I still wonder if there's a general purpose "closed" form that doesn't require me to keep track of the number of swaps and of course, it would be nifty if the thing could completely sort in one pass through. Since what I have works, those queries are simply "creeping elegance" and a desire to learn more about algorithms for scanning and manipulating network topologies.
Thanks!
 03312013, 06:01 PM #5Member
 Join Date
 Mar 2013
 Posts
 87
 Rep Power
 0
 03312013, 06:07 PM #6Member
 Join Date
 Mar 2013
 Posts
 87
 Rep Power
 0
 04062013, 07:15 AM #7Member
 Join Date
 Mar 2012
 Location
 Novosibirsk, Russia
 Posts
 15
 Rep Power
 0
Re: Sorting a 2dimensional network?
You did not told what is sorting for. I suspect your graph is a computational graph, where pins are variables and blocks are functions. You need to calculate the order to call the functions. If so, consider using more general Data flow diagram  Wikipedia, the free encyclopedia (graph can have cycles, blocks can execute multiple times). An example of library which support that model and compute correct execution ordering at run time is https://github.com/rfqu/df4j.
 04062013, 04:41 PM #8Member
 Join Date
 Mar 2013
 Posts
 87
 Rep Power
 0
Re: Sorting a 2dimensional network?
Yes, the purpose of the graph is to generate DSP code based on an arrangement of functional blocks. I am pleased to say that it works with my original algorithm although it takes several passes to get it completely sorted. There is so much more to do in other areas that I'm not spending the time to see if this can be optimized.
There are probably some limitations of this approach, but the DSP target itself does not support subroutines and very limited branching (skips) under certain conditions. Note that my data structures only uses backward links (blocks only know about connecting blocks which feed into them, but know nothing about downstream blocks).Last edited by Digital Larry; 04062013 at 05:07 PM.
Similar Threads

Need a java code to read 2dimensional excel file and write as 1dimensional file
By idhayanila in forum New To JavaReplies: 2Last Post: 03122013, 11:17 AM 
Sorting a 2dimensional array
By Krauger in forum New To JavaReplies: 1Last Post: 02272012, 04:29 PM 
Sorting Two Dimensional arrays
By anfielder in forum New To JavaReplies: 5Last Post: 12142010, 08:12 AM 
Server is in a network using an IP, but router in network carries the external IP(www
By lse123 in forum NetworkingReplies: 7Last Post: 05022010, 11:35 PM 
Help with java sorting two dimensional array
By Joycey in forum New To JavaReplies: 2Last Post: 03272010, 03:36 AM
Bookmarks