graph ADT

[Andreas.Burman]

Hi

What is the best way to implement a undirected weighted graph ADT in
javascript?

[Evertjan.]

An************@ gmail.com wrote on 06 apr 2006 in comp.lang.javas cript:

What is the best way to implement a undirected weighted graph ADT in
javascript?

Telling us what you are talking about?

--
Evertjan.
The Netherlands.
(Please change the x'es to dots in my emailaddress)

[Andreas.Burman]

Sorry

I'm writing an extension to firefox where I want to grade all links on
the pages the user visits and then store this information in a weighted
graph (grade as edges, uri as nodes), to make it possible to find the
"best" link on the page or calculate the median grade of the path
between to pages the user has visited, etc.

What I want to know is how to implement the graph datastructure in
javascript in the most efficient way (performance wise and to some
extent also memory wise). I was thinking on using an adjacency matrix
but it would probably be to sparse since most urls on the web are not
connected to each other, and I wonder if someone had an better idea.

[Evertjan.]

An************@ gmail.com wrote on 06 apr 2006 in comp.lang.javas cript:

Sorry
Please quote what you are replying to. If you want to post a followup via
groups.google.c om, don't use the "Reply" link at the bottom of the article.
Click on "show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers.
<http://www.safalra.com/special/googlegroupsrep ly/>

I'm writing an extension to firefox where I want to grade all links on
the pages the user visits and then store this information in a weighted
graph (grade as edges, uri as nodes), to make it possible to find the
"best" link on the page or calculate the median grade of the path
between to pages the user has visited, etc.
Clientside drawing of graphs is possible,
but should be carfully cross-browser designed.

An IE example of mine from 2003:

<http://devrijehuisarts .org/test/jsgraph.asp>

What I want to know is how to implement the graph datastructure in
javascript in the most efficient way (performance wise and to some
extent also memory wise). I was thinking on using an adjacency matrix
but it would probably be to sparse since most urls on the web are not
connected to each other, and I wonder if someone had an better idea.

'Graph datastructures' and 'adjacency matrices', do you need such beasts?

--
Evertjan.
The Netherlands.
(Please change the x'es to dots in my emailaddress)

[Andreas.Burman]

Evertjan. skrev:

An************@ gmail.com wrote on 06 apr 2006 in comp.lang.javas cript:

I'm writing an extension to firefox where I want to grade all links on
the pages the user visits and then store this information in a weighted
graph (grade as edges, uri as nodes), to make it possible to find the
"best" link on the page or calculate the median grade of the path
between to pages the user has visited, etc.

Clientside drawing of graphs is possible,
but should be carfully cross-browser designed.

An IE example of mine from 2003:

<http://devrijehuisarts .org/test/jsgraph.asp>

I dont want to draw graphs just store data in them i.e the
datastructure graph and then be able to traverse it depending on the
values of the edges.

What I want to know is how to implement the graph datastructure in
javascript in the most efficient way (performance wise and to some
extent also memory wise). I was thinking on using an adjacency matrix
but it would probably be to sparse since most urls on the web are not
connected to each other, and I wonder if someone had an better idea.

'Graph datastructures' and 'adjacency matrices', do you need such beasts?

Not sure there may be some better way to implement it. It's just that a
graph seemed like the natural choice since the internet already is a
graph.
--
Evertjan.
The Netherlands.
(Please change the x'es to dots in my emailaddress)

[Thomas 'PointedEars' Lahn]

An************@ gmail.com wrote:

What I want to know is how to implement the graph datastructure in
javascript in the most efficient way (performance wise and to some
extent also memory wise). I was thinking on using an adjacency matrix
but it would probably be to sparse since most urls on the web are not
connected to each other, and I wonder if someone had an better idea.

var node1 = {target: null};
var node2 = {target: node1, weight: 1};

Got the idea?
PointedEars

[Thomas 'PointedEars' Lahn]

Thomas 'PointedEars' Lahn wrote:

An************@ gmail.com wrote:

What I want to know is how to implement the graph datastructure in
javascript in the most efficient way (performance wise and to some
extent also memory wise). I was thinking on using an adjacency matrix
but it would probably be to sparse since most urls on the web are not
connected to each other, and I wonder if someone had an better idea.

var node1 = {target: null};
var node2 = {target: node1, weight: 1};

Got the idea?

Sorry, I overlooked "undirected ".
PointedEars

[Andreas.Burman]

Thomas 'PointedEars' Lahn skrev:

Thomas 'PointedEars' Lahn wrote:

An************@ gmail.com wrote:

What I want to know is how to implement the graph datastructure in
javascript in the most efficient way (performance wise and to some
extent also memory wise). I was thinking on using an adjacency matrix
but it would probably be to sparse since most urls on the web are not
connected to each other, and I wonder if someone had an better idea.
var node1 = {target: null};
var node2 = {target: node1, weight: 1};

Got the idea?

Not quite, I understand how that work if each node only is connected to
one node but how does it work in the following example:

<ascii graphic warning>

w1:2, w2:45, w3:34
|------------------> www.abc.com ->...
| w1:6, w2:1, w3:234
http://www.google.com -|------------------> www.def.com ->...
| w1:7, w2:6, w3:1
|------------------> www.ghi.com ->...
</acsii graphic warning>

As you can see I alsa need more then one weight value on each edge.
Sorry, I overlooked "undirected ".
No my fault I meant directed.
PointedEars

[Evertjan.]

An************@ gmail.com wrote on 06 apr 2006 in comp.lang.javas cript:

It's just that a
graph seemed like the natural choice since the internet already is a
graph.

Are you sure?

I did not know I was sending my email on a graph,
reading usenet on a graph,
and more recently browse the www on a graph!

--
Evertjan.
The Netherlands.
(Please change the x'es to dots in my emailaddress)

[Andreas.Burman]

Evertjan. skrev:

An************@ gmail.com wrote on 06 apr 2006 in comp.lang.javas cript:

It's just that a
graph seemed like the natural choice since the internet already is a
graph.

Are you sure?

I did not know I was sending my email on a graph,
reading usenet on a graph,
and more recently browse the www on a graph!

I'm not sure if we are thinking of the same kind of graph... I mean
that the www is a directed graph with the urls as nodes and the links
as edges of the graph

i.e this kind of graph: http://en.wikipedia.org/wiki/Graph_theory