1

I am trying to create a directed graph data structure in JavaScript. I want each node in the graph to be doubly-linked, so that I can obtain a list of links that each node points to, as well as the links that point to that node. Each node is an array with 3 elements, like so: [["node that links to node a"], "node a", ["node that node a links to"]]

//The functions linkNodes and unlinkNodes should add and remove nodes links from the directed graph, respectively.
var nodes = new Object();

function linkNodes(a, b){
    //a should be a string, and b should be a string as well
    //create the node a, if it doesn't exist yet
    //create the node b, if it doesn't exist yet
    //link the node a to the node b
}

function unlinkNodes(){
    //unlink the nodes a and b, if a and b exist
    //create the node a, if it doesn't exist yet
}

function getNode(string){
    //get the node that corresponds to the string
    //if the string doesn't exist, then return false
}

jsfiddle: http://jsfiddle.net/NTKZ9/1/​

Is there a more concise way to implement a directed graph in JavaScript, besides the one that I've proposed here?

Anderson Green
  • 30,230
  • 67
  • 195
  • 328
  • This data structure is not meant to represent a visual representation of a directed graph. Instead, it merely represents a group of linked nodes. Each node should be an array with 3 elements: an example of such a node would be `[["node b"], "node a", ["node c"]]`. In this case, node a would "point to" node b, which would "point to" node C. – Anderson Green Dec 31 '12 at 01:20
  • My main motivation for creating such a data structure would be to emulate the MediaWiki category system, but that's only one of many possible use cases. – Anderson Green Dec 31 '12 at 01:21
  • It looks like I'll need to write a function that will remove a string from an array (if the string is in the array), and add an element to an array (if the string isn't in the array). – Anderson Green Dec 31 '12 at 01:26
  • You seem to be making good progress on your own, so what is your question to us? – Frank van Puffelen Dec 31 '12 at 01:30
  • @FrankvanPuffelen I'm trying to find out whether there's a more efficient way to represent a directed graph data structure - the method that I've devised seems a bit clumsy and redundant. – Anderson Green Dec 31 '12 at 01:34
  • Using arrays isn't an elegant solution: I'll need to find a way to mimic sets in JavaScript. http://stackoverflow.com/questions/7958292/mimicking-sets-in-javascript – Anderson Green Dec 31 '12 at 02:01

1 Answers1

1

A concise way would be to store an adjacency matrix in a two-dimensional array.

Bogdan Kulynych
  • 683
  • 1
  • 6
  • 17