anvaka / ngraph.graph Goto Github PK
View Code? Open in Web Editor NEWGraph data structure in JavaScript
License: BSD 3-Clause "New" or "Revised" License
Graph data structure in JavaScript
License: BSD 3-Clause "New" or "Revised" License
Hello! I am using ngraph.graph
version ^20.0.0
as specified in my package.json
.
I am creating a graph from a file planet-route-data.json
like so:
import createGraph from 'ngraph.graph'
function makeTravelGraph () {
const graph = createGraph()
const travelGraphData = JSON.parse(fs.readFileSync('./src/planet-route-data.json'))
// first, we create nodes
travelGraphData.forEach(sourcePlanet => {
graph.addNode(sourcePlanet.name)
})
// then, we link them
travelGraphData.forEach(sourcePlanet => {
sourcePlanet.destinations.forEach(destination => {
graph.addLink(sourcePlanet.name, destination.name, { fuelCost: destination.cost })
})
})
return graph
}
My planet-route-data.json
file looks like this (please ignore the values themselves, haha):
[
{
"name": "Earth",
"destinations": [
{
"name": "Mars",
"cost": 13
},
{
"name": "Venus",
"cost": 23
}
]
},
{
"name": "Mars",
"destinations": [
{
"name": "Jupiter",
"cost": 22
},
{
"name": "Saturn",
"cost": 25
}
]
},
{
"name": "Saturn",
"destinations": [
{
"name": "Jupiter",
"cost": 30
},
{
"name": "Earth",
"cost": 12
}
]
},
{
"name": "Venus",
"destinations": [
{
"name": "Earth",
"cost": 20
},
{
"name": "Mars",
"cost": 25
},
{
"name": "Mercury",
"cost": 15
}
]
}
]
The nodes in the graph are being created, and links seem to be created successfully -- that is, I can list them as expected with something like:
returnedGraph.forEachLink(link => {
console.log(link)
}
However, the nodes themselves, which contain a property named links
, do not seem to be updated. If I try to print them, their links
property looks like an empty object: {}
. If I do:
returnedGraph.forEachLinkedNode(node => {
console.log(node)
}
nothing is iterated upon, presumably as there are no nodes with links to be found.
Is this, by any chance, by design, or is it not intended behavior?
Is it possible to reassign a different value to Node.data
property after initial assignment?
Add support for printing or generating a visual representation of the graph to the console so you can visually see what the graph looks like and which nodes are linked to which. :D
The code in dist/ngraph.graph.js for v20.0.0 does not seem to match its source.
Comparison of lines 53-57 below (v20.0.0).
dist/ngraph.graph.js:
var nodes = new Map();
var links = [],
// Hash of multi-edges. Used to track ids of edges between same nodes
multiEdges = {},
suspendEvents = 0,
index.js:
var nodes = new Map(); // nodeId => Node
var links = new Map(); // linkId => Link
// Hash of multi-edges. Used to track ids of edges between same nodes
var multiEdges = {};
var suspendEvents = 0;
It looks like the code in the bundle actually matches the index.js of the previous version (v19.1.0).
Does the returning true
to exit only work for .forEachNode
and not forEachLink
and forEachLinkedNode
?
That seems to be what the typescript file suggests, but it seems like a rather odd discrepancy between functions of the same family.
PS: Also, I don't believe this feature is documented in the README
Could you have a look at the pull request I made, please.
Hi, first of all, ngraph is a great project!
Maybe I'm overworked but trying to import ngraph.graph in my TypeScript project I'm not successfull:
import createGraph from 'ngraph.graph'
cause TypeError: createGraph.default is not a function
import { createGraph } from 'ngraph.graph'
cause Module '"ngraph.graph"' has no exported member 'createGraph'.
Am I doing something wrong or I missed something? Couldn't find any solution on the web :(
Is there any way to force the graph and pathfinder to obey link directions? The following example illustrates the problem. The path finder finds a path from "A" to "E" as expected. Unfortunately, it also finds a path from "E" to "A" even though no directed links exists between many of the nodes in this direction. Additionally, where links do exist ("C1" -> "B" and "C2" -> "B"), the given weights are ignored.
const createGraph = require('ngraph.graph');
const pathFinders = require("ngraph.path");
let graph = createGraph();
graph.addLink("A", "B", { weight: 1 });
graph.addLink("B", "C1", { weight: 1 });
graph.addLink("B", "C2", { weight: 5 });
graph.addLink("C1", "B", { weight: 5 });
graph.addLink("C2", "B", { weight: 1 });
graph.addLink("C1", "D", { weight: 1 });
graph.addLink("C2", "D", { weight: 1 });
graph.addLink("D", "E", { weight: 1 });
let finder = pathFinders.aStar(graph, {
distance: (fromNode, toNode, link) => link.data.weight
});
const test1 = finder.find("A", "E").reverse();
const test2 = finder.find("E", "A").reverse();
console.log("TEST 1");
test1.forEach(p => console.log("id:",p.id));
console.log("\nTEST 2");
test2.forEach(p => console.log("id:",p.id));
OUTPUT:
TEST 1
id: A
id: B
id: C1
id: D
id: E
TEST 2
id: E
id: D
id: C1
id: B
id: A
Hi,
Not really an issue rather an enhancement (or probably I'm hopeless and it's already practicable ^^). Is it possible to show the direction of a link with an arrow or a moving particle like vasturiano's 3d-force-graph :
Thanks for your work in any case! :)
Hello,
I'm certainly doing something wrong cause I tried your code and got the following error.
Cannot figure out how to fix it
require.js:7 Uncaught Error: Module name "ngraph.fromjson" has not been loaded yet for context: _. Use require([])
http://requirejs.org/docs/errors.html#notloaded
thank you for you help
Kim
createGraph sets beginUpdate to enterModification,
When calling the 'on' function:
enterModification = enterModificationReal, gets executed, BUT beginUpdate doesn't get updated, the function still holds the original value of enterModification which is noop.
tested on Chrome 41.0.2272.
the following example illustrates the problem:
var c = function() { console.log('c'); };
var b = c;
var a = b;
b = function() { console.log('b'); };
a(); // Prints 'c'
Would like a to print 'b'.
Hello!
Currently it's possible to get a link from the graph through several ways:
getNode
and iterating over the links
propertygetLinks
and getLink
However, there's no way to get a link by its id property, which would be useful if you store these ids externally (when the graph is created or changed) for later use.
The removeLink
method has the following passage in the documentation:
If you pass two arguments, the function assumes they represent from/to node ids
I assume this means something like removeLink(fromID,toID)
? If so, the method's typing doesn't support this signature.
From reading the code, it seems that getLlink(a,b)
just returns the first link it finds between a
and b.
But if you have the multigraph
option set to true, there may be multiple links.
The reason I ask is I am using ngraph.path on a multigraph, and I want to get which particular links are being used.
Sorry if this is outside the scope of the project, but could you advise on ways to find groups of linked nodes in the graph? I needed to count their total.
Many thanks
Type definition for Node.links
seems to suggest that we return an empty array when there's no links.
The actual behaviour is returning Node.links === null
.
when i want to load 500W edges (400W edges are loaded well).
But I got the same error when I used a 196GB memory machine instead of 64GB mem machine.
So could you tell me how setup the memory to let me load more edges?
Thanks.
As the title describes a hasNode
function is missing and it is one of the basic building blocks of a graph data structure.
it would be great to implement one
As the forEachNode loop will stop when returning true
Lines 520 to 524 in b5e768a
The typing of forEachNode should be amended:
/** To stop the iteration return true in the callback */
forEachNode: (callbackPerNode: (node: Node<NodeData>) => void | undefined | null | boolean) => void
This would allow the use of the function as described in the readme:
g.forEachNode(function(node){
console.log(node.id, node.data);
});
Typescript will fail here as the return value is undefined
and not boolean
Hello, lots of thanks for your great work on graph in js.
Here is question I've encountered in using these awesome projects. I am using pm
to visualize some GitHub projects networks and it works fine right now but I need link weight support from the layout generation method.
I am using ngraph.offline.layout
right now and I looked into the projects and I found that actually the physical simulator supports link weight/length in spring force calculation. But as this project is the basic data structure of ngraph
and the type of addLink
method only supports fromId
, toId
and data
for custom data store.
Right now I need to do this as a work around:
(addLink(fromId, toId) as any).length = l;
Should I modify the interface to let users know that link length is supported already?
Thank you for your awesome work again~
Hi.
Thanks for this awesome library! I was able to visualize some pretty big datasets (5-10 millions of nodes and 15 millions of links).
So I tried to increase the number of nodes(somewhere around 50 millions).
I have 32GB of RAM btw.
My current issue is that creating a ngraph.graph instance is a bit difficult. I mean because of such a large dataset my PC memory gets full very fast.
So I was wondering if there is a way to save several ngraph.graph instances into files and then merge them (so the result next can be processed with ngraph.tobinary).
Or maybe there is another approach to this issue?
Thanks!
I have been using and old version since years, but the newer versions are even worse in this aspect (due to map usage and ids).
When 2 nodes have multiple links between them (i.e. multigraph), the current getLink() method always retrieve the same link with no way to know if there are more or which one to choose. In newer versions getLink just retrieves the first one created which happens to match the non unique ID.
While this is irrelevant most times, when using a graph for path calculations, if you want to retrieve a link between 2 nodes, you usually want an specific link (i.e. the shortest one), not the first one. In previous versions you would iterate over the node links, so back to that (instead of relying on the map), you would need to add some kind of function which must be minimized.
function getLink(aNodeId, bNodeId, minimizer) {
// TODO: Use sorted links to speed this up
var node = getNode(aNodeId),
i;
if (!node || !node.links) {
return null;
}
let link = null;
let iLink;
let min = Infinity;
for (i = 0; i < node.links.length; ++i) {
iLink = node.links[i];
if (iLink.fromId === aNodeId && iLink.toId === bNodeId) {
if (minimizer) {
const newMin = minimizer(iLink);
if (newMin < min) {
min = newMin;
link = iLink;
} else if (!link && newMin === min ) {
link = iLink;
}
} else {link = iLink; break;}
}
}
return link;
}
Note iterating over current node links is pretty much as fast as the map, since is just a subset of links. You are not really gaining a lot, since every node should have at least a link in most use cases. So getNode iterates all nodes which should have the same size than the links map (or even smaller in most cases).
Then it's as simple as
mygraph.getLink(nodeA, nodeB, (link) => link.data.weight);
Even if you don't add something like this, the current behavior for multigraphs should be warned at least (or a new method given to retrieve all possible links between A and B).
Then... continuing with this, non oriented graphs! (which to me is equal to multigraphs handling). getLink(a,b) is different to geLink(b,a). Since there is no specific option for oriented/non oriented graphs, a new method should be created to to retrieve any of those links.
function getNonOrientedLink(aNodeId, bNodeId, minimizer) {
// TODO: Use sorted links to speed this up
var node = getNode(aNodeId),
i;
if (!node || !node.links) {
return null;
}
let link = null;
let iLink;
let min = Infinity;
for (i = 0; i < node.links.length; ++i) {
iLink = node.links[i];
if (iLink.fromId === aNodeId && iLink.toId === bNodeId || iLink.fromId === bNodeId && iLink.toId === aNodeId) {
if (minimizer) {
const newMin = minimizer(iLink);
if (newMin < min) {
min = newMin;
link = iLink;
} else if (!link && newMin === min ) {
link = iLink;
}
} else {link = iLink; break;}
}
}
return link;
}
Finally, if maps are to be used. A better way to handle multigraphs could be just creating a map of arrays.
function addLink(fromId, toId, data) {
enterModification();
var fromNode = getNode(fromId) || addNode(fromId);
var toNode = getNode(toId) || addNode(toId);
var link = createLink(fromId, toId, data);
var isUpdate = links.has(link.id);
const idLinks = links.get(link.id);
(if !idLinks || !options.multigraph || !options.oriented) {links.set(link.id, [link]);}
else {idLinks.push(link);}
// TODO: this is not cool. On large graphs potentially would consume more memory.
addLinkToNode(fromNode, link);
if (fromId !== toId) {
// make sure we are not duplicating links for self-loops
addLinkToNode(toNode, link);
}
recordLinkChange(link, isUpdate ? 'update' : 'add');
exitModification();
return link;
}
And then you can have infinite links between nodes that way, no need to differentiate between multigraphs or not (there is also no need for uniqueIds). In single-edge-graphs, getLink would just retrieve the first link of the array. On multi-graphs, either the first one or one according to the minimizer.
Note I added a check for multigraphs in case you explicitly want to force single links.
The good thing about this approach is that you can directly enforce a oriented/non oriented option. For non oriented graphs, you can check whether there is already a link a-b or b-a and treat as a non-multigraph. Oriented graphs would simply be multigraphs with arrays of length <=2.
function makeLinkId(fromId, toId) { // With this there is no need to check both cases for non oriented graphs
return [fromId, toId].sort().join( '๐ ');
}
Checking oriented graphs would be a matter of changing getLink, to match the from and to in the proper order for the array of 2 links.
Not doing a PR since these are breaking changes and don't want to spend time on something may not be implemented at all.
It would be nice to have a utility in the graph to detect if the graph was circular or not. This is useful for determining what kinds of graph layouts are most optimal given the data.
It seems that addNode
will overwrite and replace any existing nodes, addLink
however does not do this.
Perhaps you can consider implementing this for the sake of consistency between the methods.
Gday @anvaka
Im looking at adopting ngraph.graph for my visibility graph algorithm - basically my library reads in polygons and returns a graph showing other visible nodes in the graph, this can be used for path finding by vessels (eg finding me the shortest path but avoid sailing on land!).
My library is functional but I think it would be nice to hook into the ngraph ecosystem you've created which has some neat features like saving graphs etc.
I'm trying to work out the best way to extend ngraph.graph, eg im envisaging something that looks like
var createGraph = require('ngraph.graph');
var g = createGraph();
g.loadPolygons(somepolygons);
// or
var g = require('ngraph.vis-graph').createGraph();
g.loadPolygons(somepolygons);
Any tips as to which of your repos might provide a good example of extending things in this sort of manner? I'm open to any ideas you might have as the best way to do this.
Thanks,
Rowan
I see that when multigraph = true
, we use the createUniqueLink
method. However, there's currently a TODO comment that says createUniqueLink
should be removed.
Does that mean the multigraph
option is deprecated? If so, what is the advised alternative? Thanks.
Line 373 in 75d5679
Hi @anvaka!
Thank you for your huge work on the ngraph
packages family. It is cool, except there is a vital thing not implemented yet - so is a convenient and universal way to iterate through nodes/links. The existing way of iteration via callback provided to internal foreach cycle is not enough, as:
The ngraph.graph
package controls the iteration and one cannot suspend execution somewhere in the middle of the cycle.
It requires an intermediate array to write graph elements to if one wants to pass them anywhere else.
#1 is a pretty similar issue, @ZigGreen probably wanted the same thing - a convenient way to iterate through elements.
I suppose adding methods that will return ECMAScript 6 iterators a cool way to deal with this problem. An iterator is a simple object so it is completely compatible with vanilla JavaScript.
Everyone who is happy to afford using ECMAScript 6 features can then use for..of
and *yield
syntax with the returned iterator. For everybody else we could create a simple ngraph.iteration
package with common functional methods, such as map
/filter
/forEach
, written on vanilla JS.
Another benefit of this approach is that the internal nodes
object won't be able to be changed by user.
The only possible problem may be a concurrency issue... or not?
What do you think about it?
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.