javascript - specify position of some nodes in a graph - Stack Overflow

admin管理员组

文章数量:1431726

Is there way to specify position of a certain subset of nodes of a connected graph, while some algorithm decide the position of other nodes? I am hoping to find an algorithm which treats edges to be like spring so that it won't be away from other nodes too far, e.g. graphopt. I looked at several other algorithms in igraph, e.g., lgl, drl, but none of them doesn't seem to allow specifying nodes' position, i have to let algorithm to have plete control of all nodes' locations.

I am asking this because i have network of data, and some of nodes i can find approximate geographic coordinates. I am hoping to show the entire network on a map. Viewing the network on a map then i can iteratively identify more nodes with some geographic identity, and at end i have georeferenced graph with decent accuracy at least visually.

I got started with igraph on R, but i am open to try other packages/language, or even GIS tool if there is something close to what i am looking for.

Thanks!

[EDIT]

After all, this question is not very good question, but since i started it, let me describe further what I am looking for. Hopefully what I am seeking make sense and somebody have done that before.

G5W's suggestion is moving toward where i want go, but i am hoping to apply the principle of original algorithm after then got pinned to the desired direction.

FR method's paper says that:

We have only two principles for graph drawing:

• Vertices connected by an edge should be drawn near each other.
• Vertices should not be drawn too close to each other.

So i thought that the large loop including path 10-8-4-1-3 should shrink and get closer to the remaining nodes. I imagined that i can find layout like below, if I fix the four points like G5M did.

I thought that algorithm may by chance create such graph, and tried like below, very crude, brute force method. But the algorithm never generated what i was looking for... I guess i need to specify some exemption to the algorithm to treat those edges between pinned nodes.

library(igraph)
set.seed(1)
g = erdos.renyi.game(10, 0.3)
LO = layout_with_fr(g)
plot(g, layout=LO)

n <- nrow(LO)
i <-  0
for (i in 1:100000) {
#  i <- i + 1
  LO <- layout_with_fr(g)
  chk <- c(all(LO[c(5,7),2] >= sort(LO[-c(5,7),2])[n-3]), # 5,7 should e close to top
           all(LO[c(2,9),2] <= sort(LO[-c(2,9),2])[2]),   # 2,9 near bottom 
           all(LO[c(2,7),1] <= sort(LO[-c(2,7),1])[2]),   # 2,7 toward left
           all(LO[c(5,9),1] >= sort(LO[-c(5,9),1])[n-3])  # 5,9 toward right
  ) 
  if (all(chk)>1 ) break      
}

[EDIT2]

Still looking for some way to do this. I found a d3 page Stick Force Layout, which seems what I want. The problem is that I am not sure I can export coordinates once I am happy with the layout. Also I probably want be able to save intermediates. So that means i should be able to node coordiates along with attributes if they got stuck or not. And this data in and out. If this is trivial for people who know JS, please give me a pointer. I try e up with json in/out interface if not.

A graph with no node position specified by user, determined by some kind of force layout algorithm

I pick position of some of nodes so that make the graph tree-like. This is just one example but my point is that i want to be able to rough shape of layout without not have to determine position of every single nodes.

Is there way to specify position of a certain subset of nodes of a connected graph, while some algorithm decide the position of other nodes? I am hoping to find an algorithm which treats edges to be like spring so that it won't be away from other nodes too far, e.g. graphopt. I looked at several other algorithms in igraph, e.g., lgl, drl, but none of them doesn't seem to allow specifying nodes' position, i have to let algorithm to have plete control of all nodes' locations.

I am asking this because i have network of data, and some of nodes i can find approximate geographic coordinates. I am hoping to show the entire network on a map. Viewing the network on a map then i can iteratively identify more nodes with some geographic identity, and at end i have georeferenced graph with decent accuracy at least visually.

I got started with igraph on R, but i am open to try other packages/language, or even GIS tool if there is something close to what i am looking for.

Thanks!

[EDIT]

After all, this question is not very good question, but since i started it, let me describe further what I am looking for. Hopefully what I am seeking make sense and somebody have done that before.

G5W's suggestion is moving toward where i want go, but i am hoping to apply the principle of original algorithm after then got pinned to the desired direction.

FR method's paper says that:

We have only two principles for graph drawing:

• Vertices connected by an edge should be drawn near each other.
• Vertices should not be drawn too close to each other.

So i thought that the large loop including path 10-8-4-1-3 should shrink and get closer to the remaining nodes. I imagined that i can find layout like below, if I fix the four points like G5M did.

I thought that algorithm may by chance create such graph, and tried like below, very crude, brute force method. But the algorithm never generated what i was looking for... I guess i need to specify some exemption to the algorithm to treat those edges between pinned nodes.

library(igraph)
set.seed(1)
g = erdos.renyi.game(10, 0.3)
LO = layout_with_fr(g)
plot(g, layout=LO)

n <- nrow(LO)
i <-  0
for (i in 1:100000) {
#  i <- i + 1
  LO <- layout_with_fr(g)
  chk <- c(all(LO[c(5,7),2] >= sort(LO[-c(5,7),2])[n-3]), # 5,7 should e close to top
           all(LO[c(2,9),2] <= sort(LO[-c(2,9),2])[2]),   # 2,9 near bottom 
           all(LO[c(2,7),1] <= sort(LO[-c(2,7),1])[2]),   # 2,7 toward left
           all(LO[c(5,9),1] >= sort(LO[-c(5,9),1])[n-3])  # 5,9 toward right
  ) 
  if (all(chk)>1 ) break      
}

[EDIT2]

Still looking for some way to do this. I found a d3 page Stick Force Layout, which seems what I want. The problem is that I am not sure I can export coordinates once I am happy with the layout. Also I probably want be able to save intermediates. So that means i should be able to node coordiates along with attributes if they got stuck or not. And this data in and out. If this is trivial for people who know JS, please give me a pointer. I try e up with json in/out interface if not.

A graph with no node position specified by user, determined by some kind of force layout algorithm

I pick position of some of nodes so that make the graph tree-like. This is just one example but my point is that i want to be able to rough shape of layout without not have to determine position of every single nodes.

• javascript
• r
• algorithm
• d3.js
• graph

Share Improve this question Follow edited Jan 16, 2019 at 13:55 yosukesabai asked Jan 13, 2018 at 16:13 yosukesabaiyosukesabai 6,24444 gold badges3434 silver badges4242 bronze badges 7

• users.soe.ucsc.edu/~pang/261/f15/misc/yani.pdf this might be what i am looking for... any experience using this approach...? – yosukesabai Commented Jan 19, 2018 at 18:27
• 1 networkx version of the spring layout allows for fixed node positions in a subset of nodes: networkx.github.io/documentation/networkx-1.11/reference/… – Paul Brodersen Commented Jan 22, 2018 at 18:17
• I looked at the code for layout_fr and at least in principle, the change would be pretty simple. I am not very proficient in C, but as far as I can tell, the main loop putes a displacement for x and y for each node on each iteration, which is then applied to each node position. All that needs to be done is supply an additional argument to the function (e.g. 'fixed' as in networkx) that can be checked to see if the displacement should in fact be applied to the node position. You could probably hack it by repeatedly calling the function, and resetting the fixed node positions each time. – Paul Brodersen Commented Jan 22, 2018 at 18:31
• For the hack, you should probably set the max_iter argument to layout_fr to 1 (assuming the R and python interface are the same), and then iterate a bunch (in python, the default is 500). – Paul Brodersen Commented Jan 22, 2018 at 18:41
• Paul, thank you for input. I try digest what you suggested and test it out. I am not proficient in C either but i will definitely give it a shot. – yosukesabai Commented Jan 22, 2018 at 18:52

 |  Show 2 more ments

1 Answer 1

Sorted by: Reset to default 6 +25

You do not give any example data for the graph or the specific layout that you are trying to achieve, so I will take a random graph and a simple configuration as the target. The idea is that you can let any algorithm lay out all of the points and then adjust the position of the ones that you want to specify.

## basic graph for illustration
library(igraph)
set.seed(1)
g = erdos.renyi.game(10, 0.3)
LO = layout_with_fr(g)
plot(g, layout=LO)

OK, now suppose that we want to take the nodes 2,5,7 and 9 and lay them out in a box without any edges crossing. What I want to do is take a basic box layout and shift it so that these four nodes and their edges are away from the rest of the graph. I will just shift these four nodes so that they are a little above all of the others.

UB = max(LO[,2])
DesiredLO = matrix(c(0,0,0,1,1,0,1,1), nrow=4, ncol=2, byrow=TRUE)
LO[c(2,7,9,5), ]  = DesiredLO + matrix(rep(LO[2,], 4), ncol=2, byrow=TRUE)
LO[c(2,7,9,5), 2] = LO[c(2,7,9,5), 2] + UB - LO[2,2] + 1
plot(g, layout=LO)

Maybe you can adapt this to what you want. If not, please use this example or something like it to specify more clearly what you do want.

本文标签： javascriptspecify position of some nodes in a graphStack Overflow