Hi.

I need a generic directed graph module written in D.  The basic structure would look something like:

class Graph {
    NodeCollection nodes;

// Graph applications
    Color(int numColors) {...}
    FindMinCut() {...}
...
}

class Node {
    Graph owner;
    EdgeCollection inEdges, outEdges;
}

class Edge {
    Node from, to;
}

If I write such a package, and then try to inherit from it, I run into lots of problems.  For example, itterators return Edge objects instead of MyEdge objects.  Also, the user really needs to be able to fill in the definition for Collection in the various places.  You can't assume any single collection class will fill the user's needs.

Can the various problems be solved efficiently (run-time wise) and cleanly with templates?  How about interfaces?

I'd like to benchmark D to C on graph intensive algorithms, so efficiency is key.  I need a no-holds-barred kick-ass fast graph module.  The C version won't be re-usable, so it will be fast and easy to write.

Anyone up for trying to write the outline of this thing?  I'll finish it if the aproach can be defined.

Thanks
Bill

Bill Cox <bill@viasic.com> wrote in news:3E3CEC57.7090403@viasic.com:

> Hi.
> 
> I need a generic directed graph module written in D.  The basic structure would look something like:
> 
> class Graph {
>      NodeCollection nodes;
> 
> // Graph applications
>      Color(int numColors) {...}
>      FindMinCut() {...}
> ...
> }
> 
> class Node {
>      Graph owner;
>      EdgeCollection inEdges, outEdges;
> }
> 
> class Edge {
>      Node from, to;
> }
> 
> If I write such a package, and then try to inherit from it, I run into lots of problems.  For example, itterators return Edge objects instead of MyEdge objects.  Also, the user really needs to be able to fill in the definition for Collection in the various places.  You can't assume any single collection class will fill the user's needs.

I'm just thinking out load.  I haven't tried this code to see if it
really
works but a first pass might look like this.

template (GraphImpl, NodeImpl, EdgeImpl) GraphLib
{
 class Graph : GraphImpl
 {
      NodeCollection nodes;

 // Graph applications
      Color(int numColors) {...}
      FindMinCut() {...}
 ...
 }

 class Node : NodeImpl
 {
      Graph owner;
      EdgeCollection inEdges, outEdges;
 }

 class Edge : EdgeImpl
 {
      Node from, to;

      EdgeImpl GetFromNode() { return from; }
      EdgeImpl GetToNode() { return from; }
 }
}

// Your implementation of Graph, Node and Edge
// plus abstract function to link it with the
// template. (see Edge,EdgeData)

class GraphData {} // class NodeData {}

class EdgeData
{
  abstract EdgeData GetFromNode();
  abstract EdgeData GetToNode();
}

instance GraphLib(GraphData,NodeData,EdgeData) My;

My.Graph myGraph; // etc...

Declaring all the abstract functions in GraphData, NodeData, and EdgeData is a pain but I'm not sure how to get around it.

Hi, Patrick.

I was thinking along the same lines.  Inheriting from template parameters is something I would generally shoot a programmer for doing, but I think it might actually work.

Any chance I could bribe you into doing a first cut?  I generally offer free pizza and beer for such things, but I'm not sure how that works on the internet.

Thanks,
Bill

Patrick Down wrote:
> Bill Cox <bill@viasic.com> wrote in news:3E3CEC57.7090403@viasic.com:
> 
> 
>>Hi.
>>
>>I need a generic directed graph module written in D.  The basic structure would look something like:
>>
>>class Graph {
>>     NodeCollection nodes;
>>
>>// Graph applications
>>     Color(int numColors) {...}
>>     FindMinCut() {...}
>>...
>>}
>>
>>class Node {
>>     Graph owner;
>>     EdgeCollection inEdges, outEdges;
>>}
>>
>>class Edge {
>>     Node from, to;
>>}
>>
>>If I write such a package, and then try to inherit from it, I run into lots of problems.  For example, itterators return Edge objects instead of MyEdge objects.  Also, the user really needs to be able to fill in the definition for Collection in the various places.  You can't assume any single collection class will fill the user's needs.
> 
> 
> I'm just thinking out load.  I haven't tried this code to see if it really
> works but a first pass might look like this.  
> 
> template (GraphImpl, NodeImpl, EdgeImpl) GraphLib
> {
>  class Graph : GraphImpl
>  {
>       NodeCollection nodes;
>   // Graph applications
>       Color(int numColors) {...}
>       FindMinCut() {...}
>  ...
>  }
>   class Node : NodeImpl
>  {
>       Graph owner;
>       EdgeCollection inEdges, outEdges;
>  }
>   class Edge : EdgeImpl
>  {
>       Node from, to;
>             EdgeImpl GetFromNode() { return from; }
>       EdgeImpl GetToNode() { return from; }
>  }
> }
> 
> // Your implementation of Graph, Node and Edge
> // plus abstract function to link it with the
> // template. (see Edge,EdgeData)
> 
> class GraphData {} // class NodeData {}
> 
> class EdgeData {
>   abstract EdgeData GetFromNode();
>   abstract EdgeData GetToNode();
> }
> 
> instance GraphLib(GraphData,NodeData,EdgeData) My;
> 
> My.Graph myGraph; // etc...
> 
> Declaring all the abstract functions in GraphData, NodeData,
> and EdgeData is a pain but I'm not sure how to get around it.

"Bill Cox" <bill@viasic.com> wrote in message news:3E3D9197.60307@viasic.com...
> Hi, Patrick.
>
> I was thinking along the same lines.  Inheriting from template parameters is something I would generally shoot a programmer for doing, but I think it might actually work.
>
> Any chance I could bribe you into doing a first cut?  I generally offer free pizza and beer for such things, but I'm not sure how that works on the internet.

How about this?  ;-)


http://www.giftcertificates.com/merchant/prod.cfm?merchant_id=1963&Siteid=ms pizhtlink&origin_id=100036


Ken Carpenter