• bill viasic.com (86/86) Feb 21 2003 Hi.
• Bill Cox (9/118) Feb 23 2003 Hi.

bill viasic.com writes:

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

Bill Cox <bill viasic.com> writes:

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