Databases
StackOverflow2013
Postsdbo
POMinimize Graph keeping Connectivity
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POMinimize Graph keeping Connectivity
    primarykey
    data
    text
    <p>I'm stuck on a graph problem. I'm working with OpenSG and am trying to find paths between two points in a building.</p> <p>I constructed this graph: <img src="https://i.stack.imgur.com/HHZv4.png" alt="graph1"></p> <p>I use it to find the shortest path between two points in a building:</p> <p><img src="https://i.stack.imgur.com/nwgbj.png" alt="path in graph"></p> <p>This is how I find the path:</p> <ul> <li>I add the start/target node in the graph </li> <li>I add edges from start/target node to all nodes that are reachable (this is done with IntersectAction in OSG)</li> <li>I use the A*-algorithm to find the shortest path</li> </ul> <p>I want to minimize the graph now. It doesn't matter if the paths between two points get a little longer i just want to elimate the redundancy that i have now. For example all the light green nodes could be deleted. There is no point in the room that doesnt "see" the door, so there is no need for the nodes. It should look something like this: <img src="https://i.stack.imgur.com/gRH9R.png" alt="minimized graph"></p> <p>So I have an algorithm that does more or less what I want, but I just thought that this must be a well-known problem. It's not a minimal vertex cover, because for example if in the minimal vertex cover a door-node is not included I won't find a way between the two rooms.</p> <p>I compared with various Graph-Problems but I couldnt find a real match...</p> <p>Its very late (6:20am) and I should go to bed and maybe it seems a little bit confusing or maybe its really obvious. Thanks for any kind of input on the problem.</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. This table or related slice is empty.
    1. UStomfroehle
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POMinimize Graph keeping Connectivity
      1. USSrikar Appalaraju
      1. VTFavorite
    2. VO
      singulars
      1. POMinimize Graph keeping Connectivity
      1. USAnil Vaitla
      1. VTFavorite
    3. VO
      singulars
      1. POMinimize Graph keeping Connectivity
      1. This table or related slice is empty.
      1. VTUpMod
    1. This table or related slice is empty.
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload