www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - path planning implementations?

reply Trass3r <un known.com> writes:
Are there any D path planning implementations?
May 11 2012
next sibling parent reply Gor Gyolchanyan <gor.f.gyolchanyan gmail.com> writes:
Do you mean heuristic graph traversal algorithms?

On Fri, May 11, 2012 at 7:27 PM, Trass3r <un known.com> wrote:
 Are there any D path planning implementations?

-- Bye, Gor Gyolchanyan.
May 11 2012
parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Sat, May 12, 2012 at 11:07:41PM +0200, Philippe Sigaud wrote:
[...]
 Anyway, here is what I would like a graph module to have:
 
 - directed and undirected graphs
 - templated nodes
 - templated edges: I want the possibility to start from a weighted
 graph and to create a graph with no info in edges, for example.

I don't know if this is overly ambitious, but I was thinking along the lines of a completely generic duck-typed graph interface for graph algorithms, so the algorithms will work for any kind of structs/classes that implement the right methods for graph access. For example, say I have a grid of voxels representing some kind of game world, where adjacent voxels within a certain height difference are considered "reachable" and voxels with greater height difference are considered "unreachable". I'd like to be able to invoke graph reachability algorithms on the grid directly, by defining methods that expose a kind of graph-like interface to the grid (e.g., enumerate edges given a particular location, enumerate locations, etc.) without having to explicitly construct a separate graph object to represent reachability. Graph algorithms generally tend to assume a particular kind of representation for the graph; we may classify graphs into different types depending on what kind of operations are expected (analogous to std.range where we have input ranges, output ranges, forward ranges, etc.). T -- Why have vacation when you can work?? -- EC
May 12 2012
prev sibling next sibling parent Trass3r <un known.com> writes:
 Do you mean heuristic graph traversal algorithms?

Yep. There's a generic implementation of Dijkstra and Bellman https://github.com/PhilippeSigaud/dranges But no A*, D* Lite etc.
May 11 2012
prev sibling next sibling parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Sat, May 12, 2012 at 02:53:24PM +0400, Gor Gyolchanyan wrote:
 I've been trying to find a D* lite too, but with no luck.
 Having a fast graph traversal algorithms are useful for a ton of very
 powerful use cases, besides path planning.
 I'm starting to think, that we're gonna have to implement it ourselves.
 Which in turn will require us to implement a graph data structure.
 Right now I need a good graph data structure for my project, so I have
 a direct interest in getting this done.
 How about we chip in and develop an std..graphs module for Phobos with
 different traversal and shortest-path algorithms?

+1. With D's generic programming abilities, we *should* have a generic graph interface. Perhaps something along the lines of the range interface (compile-time duck-typing). It'd be nice to have advanced graph algorithms implemented in a generic way that can be used for a variety of applications. Personally I'd love to have a generic graph-coloring algorithm. T -- "Outlook not so good." That magic 8-ball knows everything! I'll ask about Exchange Server next. -- (Stolen from the net)
May 12 2012
prev sibling next sibling parent Gor Gyolchanyan <gor.f.gyolchanyan gmail.com> writes:
--bcaec554deb20af4d004bfda03f2
Content-Type: text/plain; charset=UTF-8

What do you think about this, The Phobos Crew?

On Sat, May 12, 2012 at 9:06 PM, H. S. Teoh <hsteoh quickfur.ath.cx> wrote:

 On Sat, May 12, 2012 at 02:53:24PM +0400, Gor Gyolchanyan wrote:
 I've been trying to find a D* lite too, but with no luck.
 Having a fast graph traversal algorithms are useful for a ton of very
 powerful use cases, besides path planning.
 I'm starting to think, that we're gonna have to implement it ourselves.
 Which in turn will require us to implement a graph data structure.
 Right now I need a good graph data structure for my project, so I have
 a direct interest in getting this done.
 How about we chip in and develop an std..graphs module for Phobos with
 different traversal and shortest-path algorithms?

+1. With D's generic programming abilities, we *should* have a generic graph interface. Perhaps something along the lines of the range interface (compile-time duck-typing). It'd be nice to have advanced graph algorithms implemented in a generic way that can be used for a variety of applications. Personally I'd love to have a generic graph-coloring algorithm. T -- "Outlook not so good." That magic 8-ball knows everything! I'll ask about Exchange Server next. -- (Stolen from the net)

-- Bye, Gor Gyolchanyan. --bcaec554deb20af4d004bfda03f2 Content-Type: text/html; charset=UTF-8 What do you think about this, The Phobos Crew?<br><br><div class="gmail_quote">On Sat, May 12, 2012 at 9:06 PM, H. S. Teoh <span dir="ltr">&lt;<a href="mailto:hsteoh quickfur.ath.cx" target="_blank">hsteoh quickfur.ath.cx</a>&gt;</span> wrote:<br> <blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="im">On Sat, May 12, 2012 at 02:53:24PM +0400, Gor Gyolchanyan wrote:<br> &gt; I&#39;ve been trying to find a D* lite too, but with no luck.<br> &gt; Having a fast graph traversal algorithms are useful for a ton of very<br> &gt; powerful use cases, besides path planning.<br> &gt; I&#39;m starting to think, that we&#39;re gonna have to implement it ourselves.<br> &gt; Which in turn will require us to implement a graph data structure.<br> &gt; Right now I need a good graph data structure for my project, so I have<br> &gt; a direct interest in getting this done.<br> &gt; How about we chip in and develop an std..graphs module for Phobos with<br> &gt; different traversal and shortest-path algorithms?<br> </div>[...]<br> <br> +1. With D&#39;s generic programming abilities, we *should* have a generic<br> graph interface. Perhaps something along the lines of the range<br> interface (compile-time duck-typing). It&#39;d be nice to have advanced<br> graph algorithms implemented in a generic way that can be used for a<br> variety of applications.<br> <br> Personally I&#39;d love to have a generic graph-coloring algorithm.<br> <span class="HOEnZb"><font color="#888888"><br> <br> T<br> <br> --<br> &quot;Outlook not so good.&quot; That magic 8-ball knows everything! I&#39;ll ask about Exchange Server next. -- (Stolen from the net)<br> </font></span></blockquote></div><br><br clear="all"><div><br></div>-- <br>Bye,<br>Gor Gyolchanyan.<br> --bcaec554deb20af4d004bfda03f2--
May 12 2012
prev sibling next sibling parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Sat, May 12, 2012 at 09:16:21PM +0400, Gor Gyolchanyan wrote:
 What do you think about this, The Phobos Crew?

Doesn't matter, just write the code and submit a pull request. :-)
 On Sat, May 12, 2012 at 9:06 PM, H. S. Teoh <hsteoh quickfur.ath.cx> wrote:
 
 On Sat, May 12, 2012 at 02:53:24PM +0400, Gor Gyolchanyan wrote:
 I've been trying to find a D* lite too, but with no luck.
 Having a fast graph traversal algorithms are useful for a ton of very
 powerful use cases, besides path planning.
 I'm starting to think, that we're gonna have to implement it ourselves.
 Which in turn will require us to implement a graph data structure.
 Right now I need a good graph data structure for my project, so I have
 a direct interest in getting this done.
 How about we chip in and develop an std..graphs module for Phobos with
 different traversal and shortest-path algorithms?

+1. With D's generic programming abilities, we *should* have a generic graph interface. Perhaps something along the lines of the range interface (compile-time duck-typing). It'd be nice to have advanced graph algorithms implemented in a generic way that can be used for a variety of applications. Personally I'd love to have a generic graph-coloring algorithm. T -- "Outlook not so good." That magic 8-ball knows everything! I'll ask about Exchange Server next. -- (Stolen from the net)

-- Bye, Gor Gyolchanyan.

-- What do you get if you drop a piano down a mineshaft? A flat minor.
May 12 2012
prev sibling next sibling parent Gor Gyolchanyan <gor.f.gyolchanyan gmail.com> writes:
--bcaec554deb2712f9404bfdaf902
Content-Type: text/plain; charset=UTF-8

Ok. I gotta implement it anyway - I need it for my project. Might as well
submit it.
Are you gonna work on this too? If so - we should coordinate our efforts.

On Sat, May 12, 2012 at 9:20 PM, H. S. Teoh <hsteoh quickfur.ath.cx> wrote:

 On Sat, May 12, 2012 at 09:16:21PM +0400, Gor Gyolchanyan wrote:
 What do you think about this, The Phobos Crew?

Doesn't matter, just write the code and submit a pull request. :-)
 On Sat, May 12, 2012 at 9:06 PM, H. S. Teoh <hsteoh quickfur.ath.cx>

 On Sat, May 12, 2012 at 02:53:24PM +0400, Gor Gyolchanyan wrote:
 I've been trying to find a D* lite too, but with no luck.
 Having a fast graph traversal algorithms are useful for a ton of very
 powerful use cases, besides path planning.
 I'm starting to think, that we're gonna have to implement it



 Which in turn will require us to implement a graph data structure.
 Right now I need a good graph data structure for my project, so I



 a direct interest in getting this done.
 How about we chip in and develop an std..graphs module for Phobos



 different traversal and shortest-path algorithms?

+1. With D's generic programming abilities, we *should* have a generic graph interface. Perhaps something along the lines of the range interface (compile-time duck-typing). It'd be nice to have advanced graph algorithms implemented in a generic way that can be used for a variety of applications. Personally I'd love to have a generic graph-coloring algorithm. T -- "Outlook not so good." That magic 8-ball knows everything! I'll ask


 Exchange Server next. -- (Stolen from the net)

-- Bye, Gor Gyolchanyan.

-- What do you get if you drop a piano down a mineshaft? A flat minor.

-- Bye, Gor Gyolchanyan. --bcaec554deb2712f9404bfdaf902 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Ok. I gotta implement it anyway - I need it for my project. Might as well s= ubmit it.<div>Are you gonna work on this too? If so - we should coordinate = our efforts.<br><div><br><div class=3D"gmail_quote">On Sat, May 12, 2012 at= 9:20 PM, H. S. Teoh <span dir=3D"ltr">&lt;<a href=3D"mailto:hsteoh quickfu= r.ath.cx" target=3D"_blank">hsteoh quickfur.ath.cx</a>&gt;</span> wrote:<br=

x #ccc solid;padding-left:1ex"><div class=3D"im">On Sat, May 12, 2012 at 09= :16:21PM +0400, Gor Gyolchanyan wrote:<br> &gt; What do you think about this, The Phobos Crew?<br> <br> </div>Doesn&#39;t matter, just write the code and submit a pull request. :-= )<br> <div class=3D"HOEnZb"><div class=3D"h5"><br> <br> &gt; On Sat, May 12, 2012 at 9:06 PM, H. S. Teoh &lt;<a href=3D"mailto:hste= oh quickfur.ath.cx">hsteoh quickfur.ath.cx</a>&gt; wrote:<br> &gt;<br> &gt; &gt; On Sat, May 12, 2012 at 02:53:24PM +0400, Gor Gyolchanyan wrote:<= br> &gt; &gt; &gt; I&#39;ve been trying to find a D* lite too, but with no luck= .<br> &gt; &gt; &gt; Having a fast graph traversal algorithms are useful for a to= n of very<br> &gt; &gt; &gt; powerful use cases, besides path planning.<br> &gt; &gt; &gt; I&#39;m starting to think, that we&#39;re gonna have to impl= ement it ourselves.<br> &gt; &gt; &gt; Which in turn will require us to implement a graph data stru= cture.<br> &gt; &gt; &gt; Right now I need a good graph data structure for my project,= so I have<br> &gt; &gt; &gt; a direct interest in getting this done.<br> &gt; &gt; &gt; How about we chip in and develop an std..graphs module for P= hobos with<br> &gt; &gt; &gt; different traversal and shortest-path algorithms?<br> &gt; &gt; [...]<br> &gt; &gt;<br> &gt; &gt; +1. With D&#39;s generic programming abilities, we *should* have = a generic<br> &gt; &gt; graph interface. Perhaps something along the lines of the range<b= r> &gt; &gt; interface (compile-time duck-typing). It&#39;d be nice to have ad= vanced<br> &gt; &gt; graph algorithms implemented in a generic way that can be used fo= r a<br> &gt; &gt; variety of applications.<br> &gt; &gt;<br> &gt; &gt; Personally I&#39;d love to have a generic graph-coloring algorith= m.<br> &gt; &gt;<br> &gt; &gt;<br> &gt; &gt; T<br> &gt; &gt;<br> &gt; &gt; --<br> &gt; &gt; &quot;Outlook not so good.&quot; That magic 8-ball knows everythi= ng! I&#39;ll ask about<br> &gt; &gt; Exchange Server next. -- (Stolen from the net)<br> &gt; &gt;<br> &gt;<br> &gt;<br> &gt;<br> &gt; --<br> &gt; Bye,<br> &gt; Gor Gyolchanyan.<br> <br> </div></div><span class=3D"HOEnZb"><font color=3D"#888888">--<br> What do you get if you drop a piano down a mineshaft? A flat minor.<br> </font></span></blockquote></div><br><br clear=3D"all"><div><br></div>-- <b= r>Bye,<br>Gor Gyolchanyan.<br> </div></div> --bcaec554deb2712f9404bfdaf902--
May 12 2012
prev sibling next sibling parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Sat, May 12, 2012 at 10:25:15PM +0400, Gor Gyolchanyan wrote:
 Ok. I gotta implement it anyway - I need it for my project. Might as
 well submit it.
 Are you gonna work on this too? If so - we should coordinate our
 efforts.

Well, I'd _like_ to work on it, but I'm supposed to be working on the new AA implementation as well, and time hasn't been on my side. :-( Having said that, though, putting the code up on github should be helpful -- you'll be able to find other volunteers who can help. --T
 On Sat, May 12, 2012 at 9:20 PM, H. S. Teoh <hsteoh quickfur.ath.cx> wrote:
 
 On Sat, May 12, 2012 at 09:16:21PM +0400, Gor Gyolchanyan wrote:
 What do you think about this, The Phobos Crew?

Doesn't matter, just write the code and submit a pull request. :-)
 On Sat, May 12, 2012 at 9:06 PM, H. S. Teoh <hsteoh quickfur.ath.cx>

 On Sat, May 12, 2012 at 02:53:24PM +0400, Gor Gyolchanyan wrote:
 I've been trying to find a D* lite too, but with no luck.
 Having a fast graph traversal algorithms are useful for a ton of very
 powerful use cases, besides path planning.
 I'm starting to think, that we're gonna have to implement it



 Which in turn will require us to implement a graph data structure.
 Right now I need a good graph data structure for my project, so I



 a direct interest in getting this done.
 How about we chip in and develop an std..graphs module for Phobos



 different traversal and shortest-path algorithms?

+1. With D's generic programming abilities, we *should* have a generic graph interface. Perhaps something along the lines of the range interface (compile-time duck-typing). It'd be nice to have advanced graph algorithms implemented in a generic way that can be used for a variety of applications. Personally I'd love to have a generic graph-coloring algorithm. T -- "Outlook not so good." That magic 8-ball knows everything! I'll ask


 Exchange Server next. -- (Stolen from the net)

-- Bye, Gor Gyolchanyan.

-- What do you get if you drop a piano down a mineshaft? A flat minor.

-- Bye, Gor Gyolchanyan.

-- Prosperity breeds contempt, and poverty breeds consent. -- Suck.com
May 12 2012
prev sibling next sibling parent Gor Gyolchanyan <gor.f.gyolchanyan gmail.com> writes:
--f46d04088c75209b0704bfdb2ef5
Content-Type: text/plain; charset=UTF-8

ok, I'll fork from phobos and get down to busyness.

On Sat, May 12, 2012 at 10:39 PM, H. S. Teoh <hsteoh quickfur.ath.cx> wrote:

 On Sat, May 12, 2012 at 10:25:15PM +0400, Gor Gyolchanyan wrote:
 Ok. I gotta implement it anyway - I need it for my project. Might as
 well submit it.
 Are you gonna work on this too? If so - we should coordinate our
 efforts.

Well, I'd _like_ to work on it, but I'm supposed to be working on the new AA implementation as well, and time hasn't been on my side. :-( Having said that, though, putting the code up on github should be helpful -- you'll be able to find other volunteers who can help. --T
 On Sat, May 12, 2012 at 9:20 PM, H. S. Teoh <hsteoh quickfur.ath.cx>

 On Sat, May 12, 2012 at 09:16:21PM +0400, Gor Gyolchanyan wrote:
 What do you think about this, The Phobos Crew?

Doesn't matter, just write the code and submit a pull request. :-)
 On Sat, May 12, 2012 at 9:06 PM, H. S. Teoh <hsteoh quickfur.ath.cx>

 On Sat, May 12, 2012 at 02:53:24PM +0400, Gor Gyolchanyan wrote:
 I've been trying to find a D* lite too, but with no luck.
 Having a fast graph traversal algorithms are useful for a ton of





 powerful use cases, besides path planning.
 I'm starting to think, that we're gonna have to implement it



 Which in turn will require us to implement a graph data





 Right now I need a good graph data structure for my project, so I



 a direct interest in getting this done.
 How about we chip in and develop an std..graphs module for Phobos



 different traversal and shortest-path algorithms?

+1. With D's generic programming abilities, we *should* have a




 graph interface. Perhaps something along the lines of the range
 interface (compile-time duck-typing). It'd be nice to have advanced
 graph algorithms implemented in a generic way that can be used for




 variety of applications.

 Personally I'd love to have a generic graph-coloring algorithm.


 T

 --
 "Outlook not so good." That magic 8-ball knows everything! I'll ask


 Exchange Server next. -- (Stolen from the net)

-- Bye, Gor Gyolchanyan.

-- What do you get if you drop a piano down a mineshaft? A flat minor.

-- Bye, Gor Gyolchanyan.

-- Prosperity breeds contempt, and poverty breeds consent. -- Suck.com

-- Bye, Gor Gyolchanyan. --f46d04088c75209b0704bfdb2ef5 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable ok, I&#39;ll fork from phobos and get down to busyness.<br><br><div class= =3D"gmail_quote">On Sat, May 12, 2012 at 10:39 PM, H. S. Teoh <span dir=3D"= ltr">&lt;<a href=3D"mailto:hsteoh quickfur.ath.cx" target=3D"_blank">hsteoh= quickfur.ath.cx</a>&gt;</span> wrote:<br> <blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1p= x #ccc solid;padding-left:1ex"><div class=3D"im">On Sat, May 12, 2012 at 10= :25:15PM +0400, Gor Gyolchanyan wrote:<br> &gt; Ok. I gotta implement it anyway - I need it for my project. Might as<b= r> &gt; well submit it.<br> &gt; Are you gonna work on this too? If so - we should coordinate our<br> &gt; efforts.<br> <br> </div>Well, I&#39;d _like_ to work on it, but I&#39;m supposed to be workin= g on the<br> new AA implementation as well, and time hasn&#39;t been on my side. :-(<br> <br> Having said that, though, putting the code up on github should be<br> helpful -- you&#39;ll be able to find other volunteers who can help.<br> <br> <br> --T<br> <div class=3D"HOEnZb"><div class=3D"h5"><br> &gt; On Sat, May 12, 2012 at 9:20 PM, H. S. Teoh &lt;<a href=3D"mailto:hste= oh quickfur.ath.cx">hsteoh quickfur.ath.cx</a>&gt; wrote:<br> &gt;<br> &gt; &gt; On Sat, May 12, 2012 at 09:16:21PM +0400, Gor Gyolchanyan wrote:<= br> &gt; &gt; &gt; What do you think about this, The Phobos Crew?<br> &gt; &gt;<br> &gt; &gt; Doesn&#39;t matter, just write the code and submit a pull request= . :-)<br> &gt; &gt;<br> &gt; &gt;<br> &gt; &gt; &gt; On Sat, May 12, 2012 at 9:06 PM, H. S. Teoh &lt;<a href=3D"m= ailto:hsteoh quickfur.ath.cx">hsteoh quickfur.ath.cx</a>&gt;<br> &gt; &gt; wrote:<br> &gt; &gt; &gt;<br> &gt; &gt; &gt; &gt; On Sat, May 12, 2012 at 02:53:24PM +0400, Gor Gyolchany= an wrote:<br> &gt; &gt; &gt; &gt; &gt; I&#39;ve been trying to find a D* lite too, but wi= th no luck.<br> &gt; &gt; &gt; &gt; &gt; Having a fast graph traversal algorithms are usefu= l for a ton of very<br> &gt; &gt; &gt; &gt; &gt; powerful use cases, besides path planning.<br> &gt; &gt; &gt; &gt; &gt; I&#39;m starting to think, that we&#39;re gonna ha= ve to implement it<br> &gt; &gt; ourselves.<br> &gt; &gt; &gt; &gt; &gt; Which in turn will require us to implement a graph= data structure.<br> &gt; &gt; &gt; &gt; &gt; Right now I need a good graph data structure for m= y project, so I<br> &gt; &gt; have<br> &gt; &gt; &gt; &gt; &gt; a direct interest in getting this done.<br> &gt; &gt; &gt; &gt; &gt; How about we chip in and develop an std..graphs mo= dule for Phobos<br> &gt; &gt; with<br> &gt; &gt; &gt; &gt; &gt; different traversal and shortest-path algorithms?<= br> &gt; &gt; &gt; &gt; [...]<br> &gt; &gt; &gt; &gt;<br> &gt; &gt; &gt; &gt; +1. With D&#39;s generic programming abilities, we *sho= uld* have a generic<br> &gt; &gt; &gt; &gt; graph interface. Perhaps something along the lines of t= he range<br> &gt; &gt; &gt; &gt; interface (compile-time duck-typing). It&#39;d be nice = to have advanced<br> &gt; &gt; &gt; &gt; graph algorithms implemented in a generic way that can = be used for a<br> &gt; &gt; &gt; &gt; variety of applications.<br> &gt; &gt; &gt; &gt;<br> &gt; &gt; &gt; &gt; Personally I&#39;d love to have a generic graph-colorin= g algorithm.<br> &gt; &gt; &gt; &gt;<br> &gt; &gt; &gt; &gt;<br> &gt; &gt; &gt; &gt; T<br> &gt; &gt; &gt; &gt;<br> &gt; &gt; &gt; &gt; --<br> &gt; &gt; &gt; &gt; &quot;Outlook not so good.&quot; That magic 8-ball know= s everything! I&#39;ll ask<br> &gt; &gt; about<br> &gt; &gt; &gt; &gt; Exchange Server next. -- (Stolen from the net)<br> &gt; &gt; &gt; &gt;<br> &gt; &gt; &gt;<br> &gt; &gt; &gt;<br> &gt; &gt; &gt;<br> &gt; &gt; &gt; --<br> &gt; &gt; &gt; Bye,<br> &gt; &gt; &gt; Gor Gyolchanyan.<br> &gt; &gt;<br> &gt; &gt; --<br> &gt; &gt; What do you get if you drop a piano down a mineshaft? A flat mino= r.<br> &gt; &gt;<br> &gt;<br> &gt;<br> &gt;<br> &gt; --<br> &gt; Bye,<br> &gt; Gor Gyolchanyan.<br> <br> </div></div><span class=3D"HOEnZb"><font color=3D"#888888">--<br> Prosperity breeds contempt, and poverty breeds consent. -- Suck.com<br> </font></span></blockquote></div><br><br clear=3D"all"><div><br></div>-- <b= r>Bye,<br>Gor Gyolchanyan.<br> --f46d04088c75209b0704bfdb2ef5--
May 12 2012
prev sibling next sibling parent Philippe Sigaud <philippe.sigaud gmail.com> writes:
On Sat, May 12, 2012 at 8:39 PM, Gor Gyolchanyan
<gor.f.gyolchanyan gmail.com> wrote:
 ok, I'll fork from phobos and get down to busyness.

Maybe you should launch another thread on what features such a module should contain. As was linked upstream in this thread, I wrote a small generic Graph (+ algos + ranges) module on this a few years ago, so I'm interested in hearing your take on this. All on all, I had great fun in writing the algos and the factory function.That was my first real dabbling in template constraints. Also, seeing the crowd here, I guess Boost::Graph will be the yardstick with which you'll be measured. Did you have a look at it? Anyway, here is what I would like a graph module to have: - directed and undirected graphs - templated nodes - templated edges: I want the possibility to start from a weighted graph and to create a graph with no info in edges, for example. - a way to get a range on a graph, to as to leverage std.algorithm goodness. - adding, deleting nodes and edges - adding a entire graph to another graph - merging or splitting of edges and nodes - policies! Are multiple edges authorized? Dangling edges? How are the nodes and edges stored (dense graph or sparse graph) - bidirectional graphs (that is, given a node, gives access to all ancestors, probably through a node property) (- branching ranges) - factory functions for standard graphs: linear, circle, grid, etc. - standard graph operations: search and path algorithms of course, transitive closure, metagraph,... But, you know, you could say that a graph is a container (though we are interested not only by what it contains, but also by its the global 'shape'). This opens the same can of worms as for any other containers: memory, element possession, relation to ranges, and so on. We are still waiting for Andrei's design on D allocators. Philippe
May 12 2012
prev sibling next sibling parent Trass3r <un known.com> writes:
Do you think it is possible to conceive an interface that allows a  
rectangular array to be handled as a graph transparently?
(i.e. a regular grid, e.g. for path planning)
May 13 2012
prev sibling parent "jerro" <a a.com> writes:
On Sunday, 13 May 2012 at 19:14:18 UTC, Trass3r wrote:
 Do you think it is possible to conceive an interface that 
 allows a rectangular array to be handled as a graph 
 transparently?
 (i.e. a regular grid, e.g. for path planning)

At least for some stuff it is. For example A* search could work on nodes which would have a property estimate (a lower bound for the shortest path length from this node to goal node) and a property neighbors. Property neighbors would return something iterable (either a range or an instance of a type with opApply defined). Each element of neighbors would have two members: distance from current node to a neighbor node and a neighbor node. The search function would than take a start node, a goal node and an optional predicate. To find a path through a rectangular array of booleans to position (i0, j0) you would write a node type like this: struct Node { RectArray a; int i; int j; int i0; int j0; property auto estimate() { return abs(i0 - i) + abs(j0 - j); } property neighbors() { Tuple!(int, Node)[] r; if(i > 0 && a[i - 1, j]) r ~= tuple(1, Node(a, i - 1, j, i0, j0)); ... take care of the other three possible neighbors here return r; } } I'm not saying we should choose this particular interface for A* search, but an interface that lets you treat rectangular array as a graph is certainly possible at least for A* search, and probably for other searches too.
May 13 2012