Show Bid Request
Graph layout algorithm
Bid Request Id: 41482
A C#/VB.Net class to layout a database diagram in an appropriate manner. Similar to the the auto-layout feature found in the database diagram system in SQL Server Enterprise manager.
The produced software need render nothing to the screen, it only has to calculate an appropriate layout.
An array of elements giving width (in pixels), height, and a unique identifier.
An array of edges (connectors) specifying a start element and an end element, and (optionally) a direction.
An x,y location for each element.
A series of coordinates describing the best way to render the connectors.
The resulting diagram may have only horizontal and vertical connectors and a minimum of bends or connector overlaps.
1) Working source code in C# plus a very simple project to demonstrate functionality.
2) Basic documentation describing the algorithm used in general terms
3) Complete ownership and distribution copyrights to all work purchased.
Would perhaps accept another language if someone has an appropriate class already prepared. In this case full documentation would be required to assist conversion to C#.
Must be 100% finished and received by buyer on:
Jan 14, 2003 EDT
Deadline legal notes: All times are expressed in the time zone of the site EDT (UT - 5). If the buyer omitted a time, then the deadline is 11:59:59 PM EDT on the indicated date.
Remember that contacting the other party outside of the site (by email, phone, etc.) on all business projects < $500 (before the buyer's money is escrowed) is a violation of both the software buyer and seller agreements.
We monitor all site activity for such violations and can instantly expel transgressers on the spot, so we thank you in advance for your cooperation.
If you notice a violation please help out the site and report it. Thanks for your help.
|All monetary amounts on the site are in United States dollars.
Rent a Coder is a closed auction, so coders can only see their own bids and comments. Buyers can view every posting made on their bid requests.
See all rejected bids (and all comments)
This bid was accepted by the buyer!
|Dec 31, 2002
7:51:37 AM EDT
|Dear Darren Johnstone,
We take a look at graph layout algorithm used in SQL Server Enterprise manager, they are used some variant of hierarchical layout for directed graphs.
We plan to adopt Sugiyama algorithm that is most frequently used to directed graph layout for solving your task. Generally, Sugiyama algorithm includes three steps.
- In stage I, the graph is transformed into a 'proper' hierarchy, if necessary. A 'proper' hierarchical graph has no cycles, and only has edges between adjacent levels. For this purpose cycles are broken by edge reversal. Edges that span more than one level are replaced with placeholder vertices and edges that connect two levels.
- In stage II, the vertices at each level are ordered to reduce the number of edge crossings.
An iterated barycentric method is used to reduce the number of edge crossings.
The barycentre of a graph is a vertex with the minimum distance between itself and every
other vertex in the graph. A graph may have more than one barycentre. Conceptually,
these vertices are those closest to the middle of the graph. The barycentric
method minimizes the distance between a vertex and its neighbours and as a result
reduces the number of edge crossings in the drawing.
- In stage III, the horizontal position of each vertex is manipulated to reduce the length of the edges.
The adaptation is needed to provide that resulting diagram may have only horizontal and vertical connectors and a minimum of bends. It will be the forth step in the algorithm.
Our company already have experience in the development and adaptation of graph layout algorithms. For example we have developed several graph layout algorithms for drawing metabolic pathways and gene network diagrams. We plan to use this experience, as well as some parts of code (these algorithms were implemented on Java, but due to similarity between C# and Java these parts of code can be converted quite easily) for your task.
Your source of innovative solutions