Re: [Algorithms] Trimming network connectivity
Brought to you by:
vexxed72
From: Jason H. <jas...@di...> - 2008-05-16 04:38:15
|
I'm still not sure I understand your problem or requirements, but I'll hazard a guess at them aloud. You've got a fully connected spatial mesh that is represented in a graph-like form... maybe a pathfinding representation? You want to A) minimize the size of the graph without B) losing connectivity, and C) there is no constraint requiring connections to nearest neighbors. Odd set of requirements. Anyway, spanning tree algorithms either work by glomming together individual nodes into full trees, or by growing a single tree by its best link one by one. If you treat this as a MST problem, you can consider the domain to be the edges that you are given in your initial graph, but you start from scratch. Once you've built an MST, you've satisfied criteria A and B. Then, you get to be creative and write your own algorithm to add additional edges to a minimal graph so that there is "enough" connectivity to satisfy your additional criteria, preferably with some cutoff metric that says you have enough edges and adding more will not significantly improve your graph. For what it's worth, 'nearness' and 'angle' are pretty meaningless on a global scale when building a graph. If you are looking to reduce the angles or distance between adjacent nodes, you'll get a complete spiderweb with no rhyme or reason to it. You're probably trying to solve a legitimate problem with these criteria... such as minimize the query distance for collisions, or minimize the depth of an A* search space, or minimize the full trip distance between the farthest points on the graph. Whatever it is, that should be your metric, or some representation of it. Angle and nearness are very localized and will not act as a proxy for larger-scale properties. Edges should be added that improve the cases you're actually optimizing for. Hope that helps, JH mark meijer wrote: > > Thanks Willem and George, > > > To clarify, > The network needs to be walkable between "near" nodes. > So, links can cross each other. > ie. I'm not looking for a minimal spanning tree > > But there can be too many links to a node as well. > > I'm currently checking the angle between links, if it's small > I throw away the link to the node further away. > This works ok for nodes that aren't close. > When they are close, the angles are larger and I can't trim them. > > > Thanks for your ideas! > > Mark > > > > On Thu, May 15, 2008 at 1:03 PM, George van Venrooij > <ge...@or... <mailto:ge...@or...>> wrote: > > Perhaps you mean something like this: http://vast.sourceforge.net (the > algorithm behind it, not the library itself). > > Regards, > > George > > > > Hi all, > > > > > > I have a network of nodes that are connected. > > So far they are connected based just on distance, which is too > much. > > > > How can I best filter out the extra connections? > > > > I thought of keeping the closest links in the most diverse > directions by > > - group them based on angle, up to eight groups > > - keep only the closest in each group > > > > How can I group them? Creating the intervals sounds a bit like a > > skip list. > > > > Wish I had my old Tanenbaum book here, this must have been handled > > in networking before. > > > > > > cheers, > > > > Mark > > > > > > > > > > > > > ------------------------------------------------------------------------------ > > > > > > > ------------------------------------------------------------------------- > > This SF.net email is sponsored by: Microsoft > > Defy all challenges. Microsoft(R) Visual Studio 2008. > > http://clk.atdmt.com/MRT/go/vse0120000070mrt/direct/01/ > > > > > > > ------------------------------------------------------------------------------ > > > > > > _______________________________________________ > > GDAlgorithms-list mailing list > > GDA...@li... > <mailto:GDA...@li...> > > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > > Archives: > > > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list > > > > > ------------------------------------------------------------------------- > This SF.net email is sponsored by: Microsoft > Defy all challenges. Microsoft(R) Visual Studio 2008. > http://clk.atdmt.com/MRT/go/vse0120000070mrt/direct/01/ > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > <mailto:GDA...@li...> > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list > > > ------------------------------------------------------------------------ > > ------------------------------------------------------------------------- > This SF.net email is sponsored by: Microsoft > Defy all challenges. Microsoft(R) Visual Studio 2008. > http://clk.atdmt.com/MRT/go/vse0120000070mrt/direct/01/ > ------------------------------------------------------------------------ > > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list |