Graph datastructure using skill

[tattvamasi@gmail.com]

All,
I am looking for the best data structure to implement graph algorithms
in skill.
What is your recommendation?
Does someone have an implementation that they would be kind enough to
share?
I am expecting to do graph operations on the resulting datastructure
including graph traversal, finding Eulerier trails etc.

Should this probably be done in C++ and called in through skill?
Thoughts?
On a general note how do we tackle graph theory problems using skill?

Thankyou,
Partha

 

[tattvamasi@gmail.com]

I am thinking that if I follow traditional approaches of representing
Graphs - Adj. List & Adj. Matrix in skill(lists and arrays
respectively), I will be forced to worry about the implementation
details on the graph data structure and thus lose the intent of solving
the problem at hand.

Thus, hoping to find out if any other implementation approaches are
available..

DAG in skill is an application for implementing Browsers, and might not
relate to this?

Partha

 

[Sylvio Triebel]

If you have less than millions of nodes, use the table (makeTable).
It is fast and easy to use...
For huge graphs you should probably prefere a C++ implementation
Regards,
Sylvio

e.g.
graph = makeTable("" nil)
graph[0] = list(1 3) ;node 0 has edges to node 1 and node 3
graph[1] = list(2) ;node 1 has one edge to node 2
graph[2] = list(0)

....
node = 0
foreach( neigbor graph[node]
do something...
)


tattvamasi@gmail.com wrote:

All,
I am looking for the best data structure to implement graph algorithms
in skill.
What is your recommendation?
Does someone have an implementation that they would be kind enough to
share?
I am expecting to do graph operations on the resulting datastructure
including graph traversal, finding Eulerier trails etc.

Should this probably be done in C++ and called in through skill?
Thoughts?
On a general note how do we tackle graph theory problems using skill?

Thankyou,
Partha

 

[tattvamasi@gmail.com]

Thanks much Sylvio, I am sure the problem size is less than a million
nodes

Andrew your thoughts?

Partha

 

[Andrew Beckett]

On 8 May 2006 11:22:52 -0700, "tattvamasi@gmail.com" <tattvamasi@gmail.com>
wrote:

Thanks much Sylvio, I am sure the problem size is less than a million
nodes

Andrew your thoughts?

Partha

I don't really have any (recent) experience of using graph algorithms, so I
can't make any recommendations as to how you'd do it. I'm sure it's quite
feasible in SKILL using either tables or structures (or quite probably classes
using SKILL++).

Andrew.
Andrew Beckett
Principal European Technology Leader
Cadence Design Systems, UK.

 

[DReynolds]

Patha, can you elaborate on what kind of graph problems you are working
on? Are you working on factor graphs? How were you planning on
displaying your outputs in the cadence environment? Why are you
choosing skill as your implementation language... obviously it is list
oriented so it can do what you need (within the size limits)



David