Hi.

I really want to know the best way to write a reusable graph module in D. Towards this, I'm sponsering:

The Great Pizza D Contest!

To whoever writes the best graph package in D wins three $10 gift certificates at Pizza Hut.  The prize was suggested by Ken Carpenter in an earlier post...

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

I'll decide which version I like best in two weeks, on March 8th, and order the prize for the winner.

Here's the pseudo-code shell of a non-reusable graph module:

class Graph {
LinkedList<Node> nodes; // Define your own container classes
LinkedList<Node> inputNodes, outputNodes;
}

class Node {
LinkedList<Edge> inEdges, outEdges;
bit visited, isInput, isOutput;
int level;
}

class Edge {
Node fromNode, toNode;
}

The only algorithm we'll run for now is visiting all the nodes, depth-first, from inputs to outputs.  On the return, we'll set the level attribute on each node to be the minimum number of nodes we have to go through to reach an output. Output nodes are level 0, and nodes driving output nodes are level 1.

visitNodes(Graph graph)
{
Node node;

foreach(graph.inputNodes, node) {
if(!node.visited) {
visitNode(node);
}
}
}

visitNode(Node node)
{
Node otherNode;
Edge edge;
int minLevel = INT_MAX, level;

node.visited = true;
if(node.isOutput) {
node.level = 0;
return;
}
foreach(node.outEdge, edge) {
otherNode = edge.toNode;
if(!otherNode.visited) {
visitNode(otherNode);
}
level = otherNode.level + 1;
if(level < minLevel) {
minLevel = level;
}
}
node.level = minLevel;
}

To test that the code is in fact reusable, let's reuse it.  Find a way to apply your reusable graph package to a hyper-graph.  Basically, a hyper-graph consists of nets and instances connected by ports.  If both Net and Instance act as Nodes, and Ports act as Edges, we have defined a way to look at a hyper-graph as a graph.  You should be able to call your visitNode function on the hyper-graph and set all the levels on Instances and Nets.  An output instance is level 0.  A net driving it is level 1.  Instances driving level 1 nets are level 2.  To determine if an instance drives a net, look at the output flag on the port connecting the two.  It is true if the instance drives the net, and false if the net drives the instance.  Here's a shell of a hyper-graph:

class Netlist {
DoublyLinkedList<Inst> instances;
DoublyLinkedList<Net> nets;
DoublyLinkedList<Inst> inputs, outputs;
}

class Inst {
LinkedList<Port> ports;
}

class Net {
DoublyLinkedList<Port> ports;
}

class Port {
Inst inst;
Net net;
bit isOutput;
}

Any takers?  If I get a link for beer gift certificates, I'll throw some beer in, too.

Bill Cox

Hi.

It looks like it's too hard to make a graph module that is easily applied to systems that don't have one-to-one matchings with classes and relationships (in any language).

Let's drop the need to apply the reusable graph module to hyper-graphs.  Instead, just show that it could be reused in any system that had classes and relationships corresponding to those in the graph package.

Bill

bill@viasic.com wrote:
> Hi.
> 
> I really want to know the best way to write a reusable graph module in D.
> Towards this, I'm sponsering:
> 
> The Great Pizza D Contest!
> 
> To whoever writes the best graph package in D wins three $10 gift certificates
> at Pizza Hut.  The prize was suggested by Ken Carpenter in an earlier post...
> 
> http://www.giftcertificates.com/merchant/prod.cfm?merchant_id=1963&Siteid=mspizhtlink&origin_id=100036
> 
> I'll decide which version I like best in two weeks, on March 8th, and order the
> prize for the winner.
> 
> Here's the pseudo-code shell of a non-reusable graph module:
> 
> class Graph {
> LinkedList<Node> nodes; // Define your own container classes
> LinkedList<Node> inputNodes, outputNodes;
> }
> 
> class Node {
> LinkedList<Edge> inEdges, outEdges;
> bit visited, isInput, isOutput;
> int level;
> }
> 
> class Edge {
> Node fromNode, toNode;
> }
> 
> The only algorithm we'll run for now is visiting all the nodes, depth-first,
> from inputs to outputs.  On the return, we'll set the level attribute on each
> node to be the minimum number of nodes we have to go through to reach an output.
> Output nodes are level 0, and nodes driving output nodes are level 1.
> 
> visitNodes(Graph graph)
> {
> Node node;
> 
> foreach(graph.inputNodes, node) {
> if(!node.visited) {
> visitNode(node);
> }
> }
> }
> 
> visitNode(Node node)
> {
> Node otherNode;
> Edge edge;
> int minLevel = INT_MAX, level;
> 
> node.visited = true;
> if(node.isOutput) {
> node.level = 0;
> return;
> }
> foreach(node.outEdge, edge) {
> otherNode = edge.toNode;
> if(!otherNode.visited) {
> visitNode(otherNode);
> }
> level = otherNode.level + 1;
> if(level < minLevel) {
> minLevel = level;
> }
> }
> node.level = minLevel;    }
> 
> To test that the code is in fact reusable, let's reuse it.  Find a way to apply
> your reusable graph package to a hyper-graph.  Basically, a hyper-graph consists
> of nets and instances connected by ports.  If both Net and Instance act as
> Nodes, and Ports act as Edges, we have defined a way to look at a hyper-graph as
> a graph.  You should be able to call your visitNode function on the hyper-graph
> and set all the levels on Instances and Nets.  An output instance is level 0.  A
> net driving it is level 1.  Instances driving level 1 nets are level 2.  To
> determine if an instance drives a net, look at the output flag on the port
> connecting the two.  It is true if the instance drives the net, and false if the
> net drives the instance.  Here's a shell of a hyper-graph:
> 
> class Netlist {
> DoublyLinkedList<Inst> instances;
> DoublyLinkedList<Net> nets;
> DoublyLinkedList<Inst> inputs, outputs;
> }
> 
> class Inst {
> LinkedList<Port> ports;
> }
> 
> class Net {
> DoublyLinkedList<Port> ports;
> }
> 
> class Port {
> Inst inst;
> Net net;
> bit isOutput;
> }
> 
> Any takers?  If I get a link for beer gift certificates, I'll throw some beer
> in, too.
> 
> Bill Cox
> 
>