2

Given: a directed graph dataset Node(node_id,x_position,y_position) Edge(start_node,end_node)

node_id, and edge are certain, only one node set as start node, position of this node is certain, let it be (0,0), others' x and y position will be created randomly.

what I need is to sorting every node by row and Columns(reassign the x and y position) so that the whole graph looks reasonable, I mean, the edges will not cross too much.(since the edges must be straight line, crosses can not be avoid but can be minimize )

I have done the first step to divide the graph to many rows by BFS and the edges can only direct to bottom. Now I need help to sorting the nodes on every row. Or if you have any idea to sorting the whole graph, welcome.

Dominique Fortin
  • 2,212
  • 15
  • 20
Ryu Hitome
  • 29
  • 2
  • How do your rows and columns relate to the graph? are they the `x_position,y_position`? "sorting every node by row and Columns" doesn't make much sense. Are you asking about assigning values to `x_position,y_position` such that crossings are minimised? – Caleth May 11 '18 at 09:19
  • Do your edges have to be single straight lines? – Caleth May 11 '18 at 09:19
  • yes you did understand my need. and the edges must be single and straight line. – Ryu Hitome May 11 '18 at 09:25
  • 1
    see this [Logic to strategically place items in a container with minimum overlapping connections](https://stackoverflow.com/a/18901490/2521214) beauty (make sure to click on the example there to see visually how it works and the layout result). – Spektre May 11 '18 at 09:47

0 Answers0