JSAV Graph API design

1 reply [Last post]
ville
ville's picture
Offline
White BeltYellow BeltGreen BeltRed BeltBlack Belt
Joined: 2009-05-28
Posts:
Points: 559
It’s been a while since anyone posted here on the forums… So here’s a draft design for the JSAV Graph API which will been implemented soon to.

Graph

  • jsavinstance.ds.graph([options]) - initializes a graph, additional options
    • weighted: true/false, default to false
    • directed: true/false, default to true
  • .newNode(value) - returns a new graph node
  • .addEdge(fromNode, toNode) - adds an edge from fromNode to toNode
  • .removeEdge(fromNode, toNode) - removes an edge from fromNode to toNode
  • .hasEdge(fromNode, toNode) - returns true/false whether an edge from fromNode to toNode exists
  • .removeNode(node) - removes node
  • .nodes() - returns an array of nodes in the graph
  • .edges() - returns an array of edges in the graph
  • .css(propertyName) - like .css function for tree/list structures, following similarly
  • .css(propertyName, value)
  • .css(map)
  • .id([newId])
  • .layout()
  • .hide([options])
  • .show([options])
  • .clear()
  • event addition functions
  • class handling functions

GraphNode

  • .edgeTo(node) - adds an edge from this node to given node
  • .edgeFrom(node) - adds an edge from given node to this node
  • .successors() - returns an array of successor nodes for this node
  • .value([newValue]) - returns or sets the value of this node
  • .css… - all the methods available for tree/list nodes
I tried to include the functionality of the JHAVÉ and Matrix APIs and change them to better match the rest of JSAV API. Any thoughts/ideas/missing functionality? Data generation will not be part of the graph, but probably in the JSAV.utils.random library or somewhere.

I think I can use an existing JS graph layout so it should be possible to calculate somewhat sensible layouts. But we’ll see.

Ville Karavirta, Aalto University, http://villekaravirta.com/

shaffer
shaffer's picture
Offline
White BeltYellow BeltGreen BeltRed BeltBlack Belt
Joined: 2009-05-28
Posts:
Points: 2009
Re: JSAV Graph API design

Thanks, Ville! This seems like a good start. But I have a number of issues to raise.

I see that you are making nodes as objects, and passing in object references in the API methods such as .addEdge(). An alternative is to have the graph store a node array, and have such parameters be integer indices to that array. Actually, you could support both approaches, allowing the parameter to be either a node object or an integer (assumed to be the index for the node in the node array).

You have a node object, but not an edge object. I am used to doing this the other way around — especially if there is a node array.

I might have missed it, but I don’t see how to get the weight for an edge. Nor how to set it, which might naturally be through an optional parameter to addEdge().

How are you planning to implement the graph? Using an adjacency matrix, or an adjacency list? You probably need to support both types, since the performance of any given algorithm might depend on which is used.

What is the .successors() method? Is this what I think of as the neighbors for the node? Meaning, all nodes that are reachable by an edge going out of the current node. I am used to thinking of the neighbors as a list. That is, I am used to having a way to get at the "first" neighbor, the "next" neighbor, and knowing when I am at the end of the list. Of course, the user can implement these from the successor array. But it would be nice to have the convenience methods.

It would be nice to have methods to indicate the current number of nodes and edges in the graph.

What does .clear() do? Delete all of the nodes and edges currently in the graph?

Perhaps some of these questions seem alien to you. That is probably because I am used to a different API, which you can see on P377 of http://people.cs.vt.edu/~shaffer/Book/JAVA3e20121119.pdf . I am not pushing to use that API, actually I am not all that fond of it. But I do want to make sure that I can do what I need when implementing the various graph algorithms. And I would like for the code examples that I use in the modules (in, for example, Processing or Python), to match the API that we use internally in JSAV.