An************@gmail.com wrote:
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.
A) The value of the property of the node object can be a reference to an
Array object. Each element of the array can be an object with the
target node object reference and different weights as property value:
var targetNodes = [
{name: 'www.abc.com', targets: [...]},
{name: 'www.def.com', targets: [...]},
{name: 'www.ghi.com', targets: [...]}
];
var sourceNode = {
name: 'www.google.com',
targets: [
{target: targetNodes[0], w1: 2, w2: 45, w3: 34},
{target: targetNodes[1], w1: 6, w2: 1, w3: 234},
{target: targetNodes[2], w1: 7, w2: 6, w3: 1}
]
};
B) The node object can have several enumerable properties, where the
value of each property is a reference to an object that has the
target node and the weights as its properties:
var sourceNode = {
target1: {targetNodes[0], w1: 2, w2: 45, w3: 34},
target2: {targetNodes[1], w1: 6, w2: 1, w3: 234},
target3: {targetNodes[2], w1: 7, w2: 6, w3: 1}
};
C) (recommended) Each node can be represented by name, as name of the
property of a graph object referencing a node object with the
aforementioned properties:
var graph = {
'www.google.com': {
targets: {
'www.abc.com': {w1: 2, w2: 45, w3: 34},
'www.def.com': {w1: 6, w2: 1, w3: 234},
'www.ghi.com': {w1: 7, w2: 6, w3: 1}
}
},
'www.abc.com': {
...
},
'www.def.com': {
...
},
'www.ghi.com': {
...
}
};
The object the `targets' property references can also be a collection[1],
so that the target node names and associated weights can be referred to
by numeric index too:
graph['http://www.google.com'].targets[0].name === 'www.abc.com'
graph[graph['http://www.google.com'].targets[0].name]
=== graph['www.abc.com']
graph['http://www.google.com'].targets['www.abc.com'].w1
=== graph['http://www.google.com'].targets[0].w1
=== 2
(etc.)
I recommend approach C because it does not require the resolution of
circular references (as the first two approaches), nevertheless displays
objects of graph theory directly in data structure and program logic, and
allows for full exploitation of the Object literal syntax, which makes it
easy to maintain.
Regards,
PointedEars
___________
[1] <URL:http://pointedears.de/scripts/collection.js>
