search

microsoft / automatic-graph-layout

A set of tools for graph layout and viewing
Other
1.35k stars 302 forks source link

Find free space on graph to place new node #294

Closed assopri closed 2 years ago

assopri commented 3 years ago

I have existing graph created by Sugiyama layout. I need to create new node (2), connected to one of existing graph nodes (1) without updating general layout. Any algorithms to find free space enough to place newly created node? Preferably it should be as close as possible to the linking node (1): image

levnach commented 3 years ago

Have a look at https://github.com/microsoft/automatic-graph-layout/tree/master/GraphLayout/Samples/FindEmptySpotSample. There is a naïve algorithm there inserting a rectangle in a graph that might be good enough for you.

assopri commented 3 years ago

Have a look at https://github.com/microsoft/automatic-graph-layout/tree/master/GraphLayout/Samples/FindEmptySpotSample. There is a naïve algorithm there inserting a rectangle in a graph that might be good enough for you.

Thank you for this cool example! I just didn`t clearly get the logic of this cycle: image

  1. numberOfTries - is the number of attempts to randomly find fitting point?
  2. interaction of randomCenter and delta is unclear for me as well
  3. also using hint

I would appreciate, if you drop a line on that!

levnach commented 3 years ago

It tries to find rectangle which doesn't intersect the nodes with the center closest to hint. Think of delta as a half diagonal of the rectangle you want to insert.

Sent from a phone

From: assopri @.> Sent: Friday, August 27, 2021 9:06:06 PM To: microsoft/automatic-graph-layout @.> Cc: Lev Nachmanson @.>; Comment @.> Subject: Re: [microsoft/automatic-graph-layout] Find free space on graph to place new node (#294)

Have a look at https://github.com/microsoft/automatic-graph-layout/tree/master/GraphLayout/Samples/FindEmptySpotSample. There is a naïve algorithm there inserting a rectangle in a graph that might be good enough for you.

Thank you for this cool example! I just didn`t clearly get the logic of this cycle: [image]https://user-images.githubusercontent.com/73235464/131205553-3cca692b-15db-4f38-bcdf-63e842bd186f.png

  1. numberOfTries - is the number of attempts to randomly find fitting point?
  2. interaction of randomCenter and delta is unclear for me as well
  3. also using hint

I would appreciate, if you drop a line on that!

— You are receiving this because you commented. Reply to this email directly, view it on GitHubhttps://github.com/microsoft/automatic-graph-layout/issues/294#issuecomment-907563609, or unsubscribehttps://github.com/notifications/unsubscribe-auth/ABJAYZZRLRFWIMADVFKZ6HLT7BOC5ANCNFSM5CWCNQ5Q.

assopri commented 2 years ago

THank you for explanation!