dagrejs / graphlib Goto Github PK

Node IDs seem to be stored internally as strings and any integer ID inputs are automatically converted to strings:

g=new graphlib.Graph();
g.setNode(1);
g.setNode('2');
g.hasNode('1');  // true
g.hasNode(2);    // true

This is useful, since you can store node values in a standard array data-structure, but use the array indices as graph node IDs. This gives the code a lot of flexibility and allows you to operate on your node values indepedently of when you build the graph.

However, there is a bug where certain integer IDs don't get properly converted to strings:

g=new graphlib.Graph({ directed: false});
g.setNode(2);
g.setNode(9);
g.setNode(10);
g.setEdge(2,9);
g.setEdge(9,10);
g.setEdge(10,2);

g.hasEdge('2','9') // true
g.hasEdge('9','10') // true
g.hasEdge('10','2') // true

g.hasEdge(2,9) // true
g.hasEdge(9,10) // false, unexpected behavior
g.hasEdge(10,2) // false, unexpected behavior

Another example:

// Works: [1,10]
a=graphlib.json.read(JSON.parse('{"options":{"directed":false},"nodes":[{"v":"1"},{"v":"10"}],"edges":[{"v":"10","w":"1"}]}'));
a.hasEdge('1','10') // true
a.hasEdge(1,10) // true, expected behavior

// Fails: [9,88]
a=graphlib.json.read(JSON.parse('{"options":{"directed":false},"nodes":[{"v":"9"},{"v":"88"}],"edges":[{"v":"88","w":"9"}]}'));
a.hasEdge('9','88') // true
a.hasEdge(9,88) // false, unexpected behavior

I haven't had time to look through the graphlib source. It's very odd behavior that doesn't seem to depend on the order of edge IDs, or any particular value of ID.

Hi,

I am currently working on a JavaScript library using graphlib. I use Typescript to enhance the development.

What about add a typescript support ?

You can support Typescript by defining a "definition file" which expose the external library API. It mainly exists for compile time check.

Hello,

Previous versions of the graphlib provided a Graph.filterNodes method. It seems there is not such method anymore. Is it on purpose? Is there an easy way to achieve this?

Thanks for your work.

Add a cluster graph. It should have the following basic functions:

• cluster(clusterId, [value]) - get / set value for the cluster.
• addCluster(clusterId) - create a cluster with the given id.
• delCluster(clusterId) - remove a cluster with the given id. Nodes owned by the cluster get promoted to the immediate parent cluster.
• joinCluster(clusterId, nodeId | clusterId) - add a node or cluster as a child of the specified cluster. Remove the object from the current owning cluster.
• leaveCluster(clusterId, nodeId | clusterId) - remove node from the current cluster, adding it back to the root of the graph.

Hello :)

Would it be possible to merge two graphs by combining the internal representations of them? What I have in mind is using Object.assign for _nodes, _parent, etc. effectively merging two graphs in O(1). Or is there any other way to do it?

Thank you for your work on Graphlib, Dagre and Dagre-D3. :)

I get a "Uncaught TypeError: _.constant is not a function" error when I try to use it in my project. I use the supposedly working graphlib.min.js but it seems that it tries to pull in a dependency (lodash) which is not present. Even if I load lodash (using the compatibility version of lodash.min.js) using a <script> tag I can see on the developer console that _ is present but graphlib still does not work.

Lets suppose i've created a mutligraph and created two edges between same nodes:

var g = new Graph({ multigraph: true });
g.setEdge("a", "b", "edge1-label", "edge1");
g.setEdge("a", "b", "edge2-label", "edge2");

now i want to retrieve all edges between these two nodes, for example:

g.edge({ v: "a", w: "b" }) 

i would expect this method to return something like:

{"edge1": "edge1-label", "edge2": "edge2-label"}

But it only returns the first edge value.

Hi!

I'm quite new to graphs, so this may not be a bug at all. Anyway, I noticed while i'm working on my network viewer(http://high5.io/network/), that the distance between nodes is quite randomly set to Infinity, instead of 1 or 2. When i type graphlib.alg.dijkstra(h5.network.graph, h5.id) in the console, I should see distance 0, 1 or anything but not Infinity I think. When I change the graph to directed and copy the edges, this problem seems to be gone. Any idea? Thanks by the way for creating this library!

0.8.0v has listed files for bower main which do not exist.

I'm setting the directed property to false in order to make my graph undirected. However, a problem occurs when I run the dijkstra algorithm.

If I set the property to true (that is the default) it returns as expected the distances of nodes taking into account the direction of the edges.

If I set the property to false it returns the distances of nodes taking into account only the reverse direction of the original edges, instead of ignoring the direction altogether.

It seems that phantomjs has a bug in strict mode. Consider you have following code:

"use strict";
function f(x) {
  x = 1;
  return arguments[0]; // in phantomjs this returns 1, regardless of the given parameter
}
console.log(f({ attr: "foo" }));

Graph.setEdge() currently relies on strict mode working correctly. Suggested implementation would be something along these lines:

Graph.prototype.setEdge = function(v, w, value, name) {
  var valueSpecified = arguments.length > 2;

  if (_.isPlainObject(v)) {
    name = v.name;
    if (arguments.length === 2) {
      value = w;
      valueSpecified = true;
    }
    w = v.w;
    v = v.v;
  } else {
    if (!_.isUndefined(name)) {
      name = String(name);
    }
  }
  v = String(v);
  w = String(w);
  // ... rest is working correctly

Hi:

Suppose I add a new graph algorithm, I think I should also update the corresponding API document. Am I correct?

Thanks

In the demo at http://cpettitt.github.io/project/dagre-d3/latest/demo/interactive-demo.html
The nodes are rendered with respect to the order the node/links are defined. Eg: if A -> D is defined before A -> B, then D will be to the left of B, and vise versa. So the order is stored in the graph(?)

However, graph.successors() does not seem to return the original order?

On the reference wiki page
all api methods has described their complexity like O(|V|)
but alg.components method does not have such description.

It is unclear how to use graphlib.js in a browser. It would be great to update the wiki with instructions on how to use it within a browser.

• Attempting to call require reasonably throws an undefined error.
• Attempting to load the js and instantiate Graph throws an undefined error.
• Attempting to instantiate Graph in body onLoad handler throws an undefined error.

Steps to reproduce:

Download graphlib.js locally:

wget "https://cpettitt.github.io/project/graphlib/latest/graphlib.js"

Create index.html:

<!DOCTYPE html>
<html>
<head>
  <title>graphlib test</title>
  <script src="graphlib.js"></script>
</head>

<body>
    graphlib
  <script>
    var g = new Graph();
    console.log(g);
  </script>

</body>

</html>

Observe error:

Uncaught ReferenceError: Graph is not defined

Hi,

Is there any plan for Grpahli to move to the next update of JavaScript such as ES6 ?

Thanks.

Since there is so many dataset (edge lists) available online but stored with txt or csv format, I think it will be useful if there is a API support this function.

would be nice to have this not be dependent on lodash's old _.filter method. _.filter no longer accepts a this argument as it's third parameter. In projects requiring lodash 4.x, this breaks graphlib.

I've forked and run the unit tests with => fat arrow functions as the iterator for the _.filter calls, where I removed the this arguments, and it works swimmingly, but we would need to introduce babel/es6 and the associated tooling required to support that.

thoughts?

what about having Graph be an EventEmitter so we can fire events such as when a node is added?

For example:

• core-bundle
• core-bundle + algs
• core-bundle + algs + dot

the default behavior of pre/postorder is to accumulate the nodes in an array, but that is just one possible behavior that we could take when visiting each node. This could be a default iterator function that is passed into dfs if none other is provided. But, what if we allow the user to provide their own iterator function that is called when each node is visited?

i saw you note over in immutable-js/immutable-js#35 that you're working on a persistent graph lib. i've need of such a thing :) is that work here, or supposed to be here eventually?

The current approach of generating docs from source code is not working well. Critiques:

• Not easy to tell how the modules are imported
• ToC is weak
• Some code is split across files making it harder to see the relationship between prototypes and their functions.

Can you refactor the source code so that I can use it as plain-javascript library?

Perhaps consider using an ES6 Map as the underlying storage for nodes so they can be other datatypes other than Strings.

e.g.

var user = {
  name: 'Bob'
}
graph.addNode(user)

Hi, thanks for awesome graphlib.

Correct me if I'm wrong. findCycles algorithm does not support undirected graphs. Any plans to add this?

Your sample code has an example of subgraph usage, but the libs don't seem to include any mention of it?

Hi
I cant find working example .. Can u please make a tutorial folder for noobs

graphlib.core.min.js does not have a @license header. This makes it difficult to comply with your MIT license that requires the copyright notice be shipped with the code.

If you put the following at the tops of your files, then your minifier tools should be smart enough to know what to do:

/**
 * @license
 * Graphlib
 * Copyright (c) 2012-2014 Chris Pettitt
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 * THE SOFTWARE.
 */

Can you please exclude .min.js from the main parameter inside bower.json? I think is just duplicate to use both versions there.

"main": [
    "dist/graphlib.core.js",
    "dist/graphlib.core.min.js"
  ]

Am I correct in saying that graphlib 1.0.1 does not support loading via requirejs, but dagre does?

Remaining algorithms to port:

• components
• floydWarshall
• prim

API documentation claims that a sink is a "...node that has no in-edges"

A sink is a node with no out edges.

The example is correct, only the description needs fixing

This fix for lodash was merged a while back but sadly has not yet been released to npm: #59

@cpettitt think you could publish a new version? ❤️

Related #58

I hacked up recursive versions of successors and predecessors, with isAcylic checks. In the hack, I'm using a third-party library (underscore's) to flatten at each level:

function ancestors(graph, node) {
    var up = graph.predecessors(node);
    return _.flatten(
        up.concat(up.map(function(u) { return ancestors(graph, u); })));
}

and similar-like for descendants. I'd expect something a bit more solid from a library, but is recursion the right approach to these two functions, and if so, should I submit a pull request (minus the underscore requirement of course)?

You/graphlib/dagre/dagre-d3 rock.

Maybe a wiki like https://github.com/node-task/spec/wiki

Hi,

I would like to retrieve specific nodes by the label they have. In the API I don't directly see how to do this. I am looking for something like graph.getNode(label).
In the end I would like to use graphlib to parse a dot file and to visualize it with cola.js. By retrieving specific nodes I aim to make groups in order to visualize the graph like this: http://marvl.infotech.monash.edu/webcola/examples/smallgroups.html