Message Boards Message Boards

Find all paths in a graph when removing one node of the graph at a time

Posted 4 years ago

Hi , I have the following problem which I am trying to solve. Consider a graph, I want to remove one node at a time form the graph (Like VertexDelete) and then retrive all simple paths from every two vertices in the remaining graph (like findpath does). Want to make it automatic so that all nodes of the graph are removed and per each removed node I will have the respective set of paths from every two vertices for the rest of the nodes. It should be smthg like a 4-level nested list. Where the first level will be the set of the paths from node 2 towards all the others, from node 3 to the others and so forth when node 1 is removed. Similarly, when nodes 2 is removed and and so forth.

I am using the following to find the set of paths for every two vertexes in the graph

Network = Graph[..]

Paths[i_, j_] := FindPath[Network, i, j, Infinity, All];

Tpaths = Table[ If [i != j, Paths[i, j]], {i, 1, VertexCount[Network]}, {j, 1, VertexCount[Network]}];

but I am not able to correctly modify it for my case, i.e., when removing each node one at a time.

Any help is welcome,

POSTED BY: Besmir Tola
4 Replies
Posted 4 years ago

I now guess I completely misunderstood your original message and perhaps even your two following messages.

I read "make it automatic so that all nodes of the graph are removed and per each removed node I will have" to mean:

Suppose you have a graph a<->b,b<->c,c<->a. Find all paths in that. Then remove node a leaving graph b<->c. Find all paths in that. Then remove node b leaving graph c. Find all paths in that. Then remove node c leaving the empty graph. Find all paths in that.

Thus I made it it automatic so that all nodes of the graph are removed, removing one more node more each time until none remained.

I tested that by making a small concrete example graph and it seemed to work.

I am now guessing you might mean:

Suppose you have a graph a<->b,b<->c,c<->a. Find all paths in that. Then remove node a leaving graph b<->c. Find all paths in that. Then start over with the original graph and remove node b leaving graph a<->c. Find all paths in that. Then start over with the original graph and remove node c leaving nodes a<->b. Find all paths in that.

Is that perhaps more correct? Or is that still perhaps in error in any way?

I apologize for my misunderstanding.

Today Horvát kindly showed that I incorrectly assumed my test was sufficient.

Again I apologize for not thinking more carefully about my code before posting.

For the error message you get, you know what graph you used which gave that error, but no one else knows what graph you used. Can you show exactly all the code you used that generated the graph you are using and the error you see?

If you use the small icon "<>" in the upper left corner of the Reply window it will let you paste your code into your message and will mostly leave that unchanged as code and not think it needs to reformat that and perhaps damage the code in the process.

It is sometimes difficult, after having worked on a problem for hours or days, to remember that the people who will read your message have not been watching your screen and listening to all the thoughts in your mind for those hours or days. Thinking "suppose the person reading this knows nothing more than what I explain to them in this message" can sometimes help.

Thank you

POSTED BY: Bill Nelson
POSTED BY: Szabolcs Horvát
Posted 4 years ago

Can you adapt this

Network=Graph[{1<->2,2<->3,3<->1}]
Paths[i_,j_]:=FindPath[Network,i,j,Infinity,All]
Join[
  Tpaths=Table[If[i!=j,Paths[i,j]],{i,1,VertexCount[Network]},{j,1,VertexCount[Network]}],
  Table[
    Network=VertexDelete[Network,k];
    Tpaths=Table[If[i!=j,Paths[i,j]],{i,1,VertexCount[Network]},{j,1,VertexCount[Network]}],
    {k,1,3}]
]

That should find your paths for your full graph and then remove the verticies one at a time and find the paths for the resulting graph until you have the empty graph.

POSTED BY: Bill Nelson
Posted 4 years ago

Hi Bill,

thanks for the suggestion. There are two things with your code.

First, I am not sure if you I explained well my intention. The removal of the vertices should be done only for one vertex, i.e., remove the first , calculate all the paths , then remove the second (with the first being part of the graph) and fetch the paths for the remaining, then remove the third (with the first and second being part of the graph) and retrive paths, and so forth. At the end the last graph with be without the last node but not empty graph. I think you previously understood the last part, right?

Second, in your code, when I run the join it gives me errors on the findpath

FindPath::inv: The argument 1 in FindPath[Graph[<2>, <1>], 1, 2, Infinity, All] is not a valid vertex. FindPath::inv: The argument 1 in FindPath[Graph[<2>, <1>], 2, 1, Infinity, All] is not a valid vertex.

Any input ?

Thanks again,

POSTED BY: Besmir Tola
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract