www.digitalmars.com         C & C++   DMDScript  

D - Directed Graph support

reply Bill Cox <bill viasic.com> writes:
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
Feb 02 2003
parent reply Patrick Down <pat codemoon.com> writes:
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.
Feb 02 2003
parent reply Bill Cox <bill viasic.com> writes:
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.
Feb 02 2003
parent "Ken Carpenter" <kencr shaw.ca> writes:
"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
Feb 12 2003