3 Attachment(s)

Sorting a 2-dimensional 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:

Attachment 4748

After:

Attachment 4750

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 pseudo-code 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

Re: Sorting a 2-dimensional 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 so-called "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.

Re: Sorting a 2-dimensional 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.

Re: Sorting a 2-dimensional 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:

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;

}

Note that a pin connection is an attribute of the "Sink" pin, to show where the "Source" was. It's a bit of a linked list structure but in terms of the data flow represented by the model, it points "backwards" only.

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!

Re: Sorting a 2-dimensional network?

Quote:

Originally Posted by

**pbrockway2** 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.

You're correct about that! I will need to add error checking when connections are made to prevent circular paths in the network.

Re: Sorting a 2-dimensional network?

Quote:

Originally Posted by

**pbrockway2** 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.

Very interesting! Seems exactly what I'm after. But I'm going to wing it for now with what I have and maybe in the future when I need to fix something that isn't broken, I'll break it. :D:

Re: Sorting a 2-dimensional 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.

Re: Sorting a 2-dimensional 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).