Layout problem

[Chris Jones]

We have a graph and nodes in the graph are to be placed onto a layout.
The layout has to be partitioned vertically as well as horizontally
several times till it generates one slot per node. Nodes are to be
assigned to vertical and horizontal partitions such that the number of
edges crossing the partition is minimized. Can anybody suggest an
effective procedure to deal with this problem?

As an example if we have a graph with sixteen nodes then layout has to
be partitioned vertically and horizontally till the time it creates
sixteen slots one per node. The idea is to decide which slot would go
to which node by following the above criteria( i.e number of edges
crossing a partition is minimized.

Thanks.

 

[John_H]

Dude,

Since we're not doing the same coursework you are, the verbage is a bit hard
to follow. I know what a graph is and vertical or horizontal partitions
make sense... but how do nodes have edges in this context?
What's a slot, now?

Perhaps there's more appropriate help available through the academic
channels that posed this problem than in comp.arch.fpga where we try to help
each other solve real-world problems.


"Chris Jones" <chjones@dacafe.com> wrote in message
news:8090cd3b.0404130521.61eb9b1f@posting.google.com...

We have a graph and nodes in the graph are to be placed onto a layout.
The layout has to be partitioned vertically as well as horizontally
several times till it generates one slot per node. Nodes are to be
assigned to vertical and horizontal partitions such that the number of
edges crossing the partition is minimized. Can anybody suggest an
effective procedure to deal with this problem?

As an example if we have a graph with sixteen nodes then layout has to
be partitioned vertically and horizontally till the time it creates
sixteen slots one per node. The idea is to decide which slot would go
to which node by following the above criteria( i.e number of edges
crossing a partition is minimized.

Thanks.

 

[Dave Vanden Bout]

"Chris Jones" <chjones@dacafe.com> wrote in message
news:8090cd3b.0404130521.61eb9b1f@posting.google.com...
We have a graph and nodes in the graph are to be placed onto a
layout. The layout has to be partitioned vertically as well as
horizontally several times till it generates one slot per node. Nodes
are to be assigned to vertical and horizontal partitions such that
the number of edges crossing the partition is minimized. Can anybody
suggest an effective procedure to deal with this problem?

As an example if we have a graph with sixteen nodes then layout has
to be partitioned vertically and horizontally till the time it
creates sixteen slots one per node. The idea is to decide which slot
would go to which node by following the above criteria( i.e number of
edges crossing a partition is minimized.

Thanks.

Try doing a search on the terms "graph partitioning optimization". You
should find a lot of algorithms and heuristics. If you don't want to weed
through all the alternatives, then try the Lin-Kernighan technique. It's
fast and usually finds good solutions that are within a few percent of the
optimum.


--
|| Dr. Dave Van den Bout XESS Corp. (919) 363-4695 ||
|| devb@xess.com PO Box 33091 ||
|| http://www.xess.com Raleigh NC 27636 USA FAX919) 367-2946 ||