Visualize all short paths in graph using RCreating a weighted undirected graph in “igraph” in C/C++The first 10 shortest paths in a graph - Igraph 0.6 - Python 2.7Finding shortest paths with python-IGraph on DAGs with negative weightsGraph Shortest Paths w/Dynamic Weights (Repeated Dijkstra? Distance Vector Routing Algorithm?) in R / Python / MatlabLines and number of transfers in a transit network using igraphLongest path of weighted DAG using R igraphUpdate a plotted graph with new edges in RComputing many shortest paths in graphShortest path of length l in Rcluster longest paths in a graph using R and igraph
Why we don't have vaccination against all diseases which are caused by microbes?
Vacuum collapse -- why do strong metals implode but glass doesn't?
Were there 486SX revisions without an FPU on the die?
Ask for a paid taxi in order to arrive as early as possible for an interview within the city
Can a character spend multiple hit dice at level 1?
Why is Boris Johnson visiting only Paris & Berlin if every member of the EU needs to agree on a withdrawal deal?
In an emergency, how do I find and share my position?
Create Tmux pane with sudo from sudoed pane?
Why doesn't mathematics collapse even though humans quite often make mistakes in their proofs?
What is the hex versus octal timeline?
The economy of trapping
Get info from plist file
Can my boyfriend, who lives in the UK and has a Polish passport, visit me in the USA?
How to compare two different formulations of a problem?
Brexit and backstop: would changes require unanimous approval by all Euro countries? Does Ireland hold a veto?
If all stars rotate, why was there a theory developed, that requires non-rotating stars?
Why don't we use Cavea-B
What can I do to keep a threaded bolt from falling out of its slot?
LeetCode: Pascal's Triangle C#
Why aren't RCS openings an issue for spacecraft heat shields?
IndexOptimize - Configuration
What is the evidence on the danger of feeding whole blueberries and grapes to infants and toddlers?
Are illustrations in novels frowned upon?
Why does my house heat up, even when it's cool outside?
Visualize all short paths in graph using R
Creating a weighted undirected graph in “igraph” in C/C++The first 10 shortest paths in a graph - Igraph 0.6 - Python 2.7Finding shortest paths with python-IGraph on DAGs with negative weightsGraph Shortest Paths w/Dynamic Weights (Repeated Dijkstra? Distance Vector Routing Algorithm?) in R / Python / MatlabLines and number of transfers in a transit network using igraphLongest path of weighted DAG using R igraphUpdate a plotted graph with new edges in RComputing many shortest paths in graphShortest path of length l in Rcluster longest paths in a graph using R and igraph
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty margin-bottom:0;
The first simple data
m <- read.table(row.names = 1, header = TRUE, text =
" A B C D E F
A 0 1 1 1 1 5
B 1 0 1 1e2 1e2 1
C 1 1 0 1 1 1
D 1 1e2 1 0 1e2 1
E 1 1e2 1 1e2 0 1
F 5 1 1 1 1 0")
m <- as.matrix(m)
Using igraph library
ig <- graph.adjacency(m, mode = "undirected", weighted = TRUE, diag = FALSE)
sp <- shortest.paths(ig, algorithm = "dijkstra")
plot(ig)
spaths <- lapply(V(ig),
function(v)
all_shortest_paths(ig, v,
weight = 1 / E(ig)$weight
)
)
Now let's check paths to all vertices spaths$C$res or spaths$B$res... How can I display only one shortest path from one point to another on the graph? 1.For example From C to A as red line 2.and the longest way from C to A as blue line
r igraph
edited Mar 27 at 16:14
G5W
25.3k9 gold badges24 silver badges46 bronze badges
asked Mar 27 at 15:39
JuliaJulia
1008 bronze badges
add a comment |
The first simple data
m <- read.table(row.names = 1, header = TRUE, text =
" A B C D E F
A 0 1 1 1 1 5
B 1 0 1 1e2 1e2 1
C 1 1 0 1 1 1
D 1 1e2 1 0 1e2 1
E 1 1e2 1 1e2 0 1
F 5 1 1 1 1 0")
m <- as.matrix(m)
Using igraph library
ig <- graph.adjacency(m, mode = "undirected", weighted = TRUE, diag = FALSE)
sp <- shortest.paths(ig, algorithm = "dijkstra")
plot(ig)
spaths <- lapply(V(ig),
function(v)
all_shortest_paths(ig, v,
weight = 1 / E(ig)$weight
)
)
Now let's check paths to all vertices spaths$C$res or spaths$B$res... How can I display only one shortest path from one point to another on the graph? 1.For example From C to A as red line 2.and the longest way from C to A as blue line
r igraph
edited Mar 27 at 16:14
G5W
25.3k9 gold badges24 silver badges46 bronze badges
asked Mar 27 at 15:39
JuliaJulia
1008 bronze badges
2
"longest way from C to A as blue line" - Do you want the longest simple path from C to A? Since your graph has cycles, unless you restrict to simple paths, there are arbitrarily long paths.
– G5W
Mar 27 at 15:53
add a comment |
The first simple data
m <- read.table(row.names = 1, header = TRUE, text =
" A B C D E F
A 0 1 1 1 1 5
B 1 0 1 1e2 1e2 1
C 1 1 0 1 1 1
D 1 1e2 1 0 1e2 1
E 1 1e2 1 1e2 0 1
F 5 1 1 1 1 0")
m <- as.matrix(m)
Using igraph library
ig <- graph.adjacency(m, mode = "undirected", weighted = TRUE, diag = FALSE)
sp <- shortest.paths(ig, algorithm = "dijkstra")
plot(ig)
spaths <- lapply(V(ig),
function(v)
all_shortest_paths(ig, v,
weight = 1 / E(ig)$weight
)
)
Now let's check paths to all vertices spaths$C$res or spaths$B$res... How can I display only one shortest path from one point to another on the graph? 1.For example From C to A as red line 2.and the longest way from C to A as blue line
r igraph
edited Mar 27 at 16:14
G5W
25.3k9 gold badges24 silver badges46 bronze badges
asked Mar 27 at 15:39
JuliaJulia
1008 bronze badges
The first simple data
m <- read.table(row.names = 1, header = TRUE, text =
" A B C D E F
A 0 1 1 1 1 5
B 1 0 1 1e2 1e2 1
C 1 1 0 1 1 1
D 1 1e2 1 0 1e2 1
E 1 1e2 1 1e2 0 1
F 5 1 1 1 1 0")
m <- as.matrix(m)
Using igraph library
ig <- graph.adjacency(m, mode = "undirected", weighted = TRUE, diag = FALSE)
sp <- shortest.paths(ig, algorithm = "dijkstra")
plot(ig)
spaths <- lapply(V(ig),
function(v)
all_shortest_paths(ig, v,
weight = 1 / E(ig)$weight
)
)
Now let's check paths to all vertices spaths$C$res or spaths$B$res... How can I display only one shortest path from one point to another on the graph? 1.For example From C to A as red line 2.and the longest way from C to A as blue line
r igraph
r igraph
edited Mar 27 at 16:14
G5W
25.3k9 gold badges24 silver badges46 bronze badges
asked Mar 27 at 15:39
JuliaJulia
1008 bronze badges
edited Mar 27 at 16:14
G5W
25.3k9 gold badges24 silver badges46 bronze badges
asked Mar 27 at 15:39
JuliaJulia
1008 bronze badges
edited Mar 27 at 16:14
G5W
25.3k9 gold badges24 silver badges46 bronze badges
edited Mar 27 at 16:14
G5W
25.3k9 gold badges24 silver badges46 bronze badges
edited Mar 27 at 16:14
G5W
25.3k9 gold badges24 silver badges46 bronze badges
25.3k9 gold badges24 silver badges46 bronze badges
asked Mar 27 at 15:39
JuliaJulia
1008 bronze badges
asked Mar 27 at 15:39
JuliaJulia
1008 bronze badges
asked Mar 27 at 15:39
JuliaJulia
1008 bronze badges
1008 bronze badges
2
"longest way from C to A as blue line" - Do you want the longest simple path from C to A? Since your graph has cycles, unless you restrict to simple paths, there are arbitrarily long paths.
– G5W
Mar 27 at 15:53
add a comment |
2
"longest way from C to A as blue line" - Do you want the longest simple path from C to A? Since your graph has cycles, unless you restrict to simple paths, there are arbitrarily long paths.
– G5W
Mar 27 at 15:53
2
2
"longest way from C to A as blue line" - Do you want the longest simple path from C to A? Since your graph has cycles, unless you restrict to simple paths, there are arbitrarily long paths.
– G5W
Mar 27 at 15:53
"longest way from C to A as blue line" - Do you want the longest simple path from C to A? Since your graph has cycles, unless you restrict to simple paths, there are arbitrarily long paths.
– G5W
Mar 27 at 15:53
add a comment |
1 Answer
1
active
oldest
votes
I will assume that you want the longest simple path from C to A. Since your graph has cycles, there are paths of arbitrarily large lengths if you revisit nodes. Let me first answer the question, but there is a caveat at the end.
You can get all simple paths from C to A using all_simple_paths. From those, it is easy to select one of the shortest paths and one of the longest paths. Then just color them.
Simple = all_simple_paths(ig, "C", "A")
SP = which.min(sapply(Simple, length))
LP = which.max(sapply(Simple, length))
EL1 = rep(Simple[[LP]], each=2)[-1]
EL1 = EL1[-length(EL1)]
EL2 = rep(Simple[[SP]], each=2)[-1]
EL2 = EL2[-length(EL2)]
ECol = rep("gray", ecount(ig))
ECol[get.edge.ids(ig, EL1)] = "blue"
ECol[get.edge.ids(ig, EL2)] = "red"
plot(ig, edge.color=ECol)
But be warned! If your graph is big and well connected, there may be many paths between two nodes. all_simple_paths may take a long time to run and produce a very large result.
answered Mar 27 at 16:13
G5WG5W
25.3k9 gold badges24 silver badges46 bronze badges
add a comment |
Your Answer
StackExchange.ifUsing("editor", function ()
StackExchange.using("externalEditor", function ()
StackExchange.using("snippets", function ()
StackExchange.snippets.init();
);
);
, "code-snippets");
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "1"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f55381144%2fvisualize-all-short-paths-in-graph-using-r%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
I will assume that you want the longest simple path from C to A. Since your graph has cycles, there are paths of arbitrarily large lengths if you revisit nodes. Let me first answer the question, but there is a caveat at the end.
You can get all simple paths from C to A using all_simple_paths. From those, it is easy to select one of the shortest paths and one of the longest paths. Then just color them.
Simple = all_simple_paths(ig, "C", "A")
SP = which.min(sapply(Simple, length))
LP = which.max(sapply(Simple, length))
EL1 = rep(Simple[[LP]], each=2)[-1]
EL1 = EL1[-length(EL1)]
EL2 = rep(Simple[[SP]], each=2)[-1]
EL2 = EL2[-length(EL2)]
ECol = rep("gray", ecount(ig))
ECol[get.edge.ids(ig, EL1)] = "blue"
ECol[get.edge.ids(ig, EL2)] = "red"
plot(ig, edge.color=ECol)
But be warned! If your graph is big and well connected, there may be many paths between two nodes. all_simple_paths may take a long time to run and produce a very large result.
answered Mar 27 at 16:13
G5WG5W
25.3k9 gold badges24 silver badges46 bronze badges
add a comment |
I will assume that you want the longest simple path from C to A. Since your graph has cycles, there are paths of arbitrarily large lengths if you revisit nodes. Let me first answer the question, but there is a caveat at the end.
You can get all simple paths from C to A using all_simple_paths. From those, it is easy to select one of the shortest paths and one of the longest paths. Then just color them.
Simple = all_simple_paths(ig, "C", "A")
SP = which.min(sapply(Simple, length))
LP = which.max(sapply(Simple, length))
EL1 = rep(Simple[[LP]], each=2)[-1]
EL1 = EL1[-length(EL1)]
EL2 = rep(Simple[[SP]], each=2)[-1]
EL2 = EL2[-length(EL2)]
ECol = rep("gray", ecount(ig))
ECol[get.edge.ids(ig, EL1)] = "blue"
ECol[get.edge.ids(ig, EL2)] = "red"
plot(ig, edge.color=ECol)
But be warned! If your graph is big and well connected, there may be many paths between two nodes. all_simple_paths may take a long time to run and produce a very large result.
answered Mar 27 at 16:13
G5WG5W
25.3k9 gold badges24 silver badges46 bronze badges
add a comment |
I will assume that you want the longest simple path from C to A. Since your graph has cycles, there are paths of arbitrarily large lengths if you revisit nodes. Let me first answer the question, but there is a caveat at the end.
You can get all simple paths from C to A using all_simple_paths. From those, it is easy to select one of the shortest paths and one of the longest paths. Then just color them.
Simple = all_simple_paths(ig, "C", "A")
SP = which.min(sapply(Simple, length))
LP = which.max(sapply(Simple, length))
EL1 = rep(Simple[[LP]], each=2)[-1]
EL1 = EL1[-length(EL1)]
EL2 = rep(Simple[[SP]], each=2)[-1]
EL2 = EL2[-length(EL2)]
ECol = rep("gray", ecount(ig))
ECol[get.edge.ids(ig, EL1)] = "blue"
ECol[get.edge.ids(ig, EL2)] = "red"
plot(ig, edge.color=ECol)
But be warned! If your graph is big and well connected, there may be many paths between two nodes. all_simple_paths may take a long time to run and produce a very large result.
answered Mar 27 at 16:13
G5WG5W
25.3k9 gold badges24 silver badges46 bronze badges
I will assume that you want the longest simple path from C to A. Since your graph has cycles, there are paths of arbitrarily large lengths if you revisit nodes. Let me first answer the question, but there is a caveat at the end.
You can get all simple paths from C to A using all_simple_paths. From those, it is easy to select one of the shortest paths and one of the longest paths. Then just color them.
Simple = all_simple_paths(ig, "C", "A")
SP = which.min(sapply(Simple, length))
LP = which.max(sapply(Simple, length))
EL1 = rep(Simple[[LP]], each=2)[-1]
EL1 = EL1[-length(EL1)]
EL2 = rep(Simple[[SP]], each=2)[-1]
EL2 = EL2[-length(EL2)]
ECol = rep("gray", ecount(ig))
ECol[get.edge.ids(ig, EL1)] = "blue"
ECol[get.edge.ids(ig, EL2)] = "red"
plot(ig, edge.color=ECol)
But be warned! If your graph is big and well connected, there may be many paths between two nodes. all_simple_paths may take a long time to run and produce a very large result.
answered Mar 27 at 16:13
G5WG5W
25.3k9 gold badges24 silver badges46 bronze badges
answered Mar 27 at 16:13
G5WG5W
25.3k9 gold badges24 silver badges46 bronze badges
answered Mar 27 at 16:13
G5WG5W
25.3k9 gold badges24 silver badges46 bronze badges
answered Mar 27 at 16:13
G5WG5W
25.3k9 gold badges24 silver badges46 bronze badges
25.3k9 gold badges24 silver badges46 bronze badges
add a comment |
add a comment |
Got a question that you can’t ask on public Stack Overflow? Learn more about sharing private information with Stack Overflow for Teams.
Got a question that you can’t ask on public Stack Overflow? Learn more about sharing private information with Stack Overflow for Teams.
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f55381144%2fvisualize-all-short-paths-in-graph-using-r%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
2
"longest way from C to A as blue line" - Do you want the longest simple path from C to A? Since your graph has cycles, unless you restrict to simple paths, there are arbitrarily long paths.
– G5W
Mar 27 at 15:53