Got Questions? Get Answers.
Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
all possible path in a network/graph

Subject: all possible path in a network/graph

From: Syed Galib

Date: 25 Oct, 2011 08:22:29

Message: 1 of 6

Hi all,

I have been struggling with this problem of finding all links which will lead to a destination from a source. For this I was planning to get all possible path from the source to destination and then keep only the unique links of those paths. I tried with MATLabBGL but failed. Can anybody please help me?

Thanks in advance.

Galib

Subject: all possible path in a network/graph

From: Lucio Cetto

Date: 25 Oct, 2011 14:17:46

Message: 2 of 6

Syed:
Be aware that if you want to enumerate "all" paths this could be a big problem, but following your idea about only retaining the nodes (or edges) that are in your solution you can achive this very easily using the Bioinformatics Toolbox graph functions (i.e. graph traversing algorithms), for example, all paths from node 4 to node 1 in the following graph:

DG = sparse([2 2 3 4 5 5 5 6 7 8 8 9],[1 4 1 5 3 6 7 9 8 1 10 10],true,10,10)
g1 = view(biograph(DG))
from4 = graphtraverse(DG,4);
to1 = graphtraverse(DG',1);
h = intersect(from4,to1)
DG2 = DG(h,h);
g2 = view(biograph(DG2,cellstr(num2str(h'))))

HTH
Lucio

Subject: all possible path in a network/graph

From: Syed Galib

Date: 25 Oct, 2011 23:15:40

Message: 3 of 6

Dear Lucio,

Thank you very much for your suggestion. As far I see, your approach works for some of my cases. I hope it'll work for my all other cases. I'm going to use this..

Thank you again.

Syed


"Lucio Cetto" wrote in message <j86gea$88o$1@newscl01ah.mathworks.com>...
> Syed:
> Be aware that if you want to enumerate "all" paths this could be a big problem, but following your idea about only retaining the nodes (or edges) that are in your solution you can achive this very easily using the Bioinformatics Toolbox graph functions (i.e. graph traversing algorithms), for example, all paths from node 4 to node 1 in the following graph:
>
> DG = sparse([2 2 3 4 5 5 5 6 7 8 8 9],[1 4 1 5 3 6 7 9 8 1 10 10],true,10,10)
> g1 = view(biograph(DG))
> from4 = graphtraverse(DG,4);
> to1 = graphtraverse(DG',1);
> h = intersect(from4,to1)
> DG2 = DG(h,h);
> g2 = view(biograph(DG2,cellstr(num2str(h'))))
>
> HTH
> Lucio

Subject: all possible path in a network/graph

From: Berk

Date: 9 Jan, 2013 01:37:10

Message: 4 of 6

Hi,

Would you please tell whether it is possible to enumerate all the paths having at most n edges? i.e. given a directed graph, enumerating all the paths of length 1, 2, ..., n?

Thanks.

"Lucio Cetto" wrote in message <j86gea$88o$1@newscl01ah.mathworks.com>...
> Syed:
> Be aware that if you want to enumerate "all" paths this could be a big problem, but following your idea about only retaining the nodes (or edges) that are in your solution you can achive this very easily using the Bioinformatics Toolbox graph functions (i.e. graph traversing algorithms), for example, all paths from node 4 to node 1 in the following graph:
>
> DG = sparse([2 2 3 4 5 5 5 6 7 8 8 9],[1 4 1 5 3 6 7 9 8 1 10 10],true,10,10)
> g1 = view(biograph(DG))
> from4 = graphtraverse(DG,4);
> to1 = graphtraverse(DG',1);
> h = intersect(from4,to1)
> DG2 = DG(h,h);
> g2 = view(biograph(DG2,cellstr(num2str(h'))))
>
> HTH
> Lucio

Subject: all possible path in a network/graph

From: galib

Date: 9 Jan, 2013 10:56:08

Message: 5 of 6

Hi Berk,

That's where I was stuck. I wanted to get all possible paths. But getting all possible nodes served my purpose. So, I am not sure. You can download a toolbox called "matlab_bgl" from file exchange and see if they provide any function which can give you all possible paths of different length. As far I remember, they have a function for all pairs shortest path only.

Syed


"Berk" wrote in message <kcihk6$3fl$1@newscl01ah.mathworks.com>...
> Hi,
>
> Would you please tell whether it is possible to enumerate all the paths having at most n edges? i.e. given a directed graph, enumerating all the paths of length 1, 2, ..., n?
>
> Thanks.
>
> "Lucio Cetto" wrote in message <j86gea$88o$1@newscl01ah.mathworks.com>...
> > Syed:
> > Be aware that if you want to enumerate "all" paths this could be a big problem, but following your idea about only retaining the nodes (or edges) that are in your solution you can achive this very easily using the Bioinformatics Toolbox graph functions (i.e. graph traversing algorithms), for example, all paths from node 4 to node 1 in the following graph:
> >
> > DG = sparse([2 2 3 4 5 5 5 6 7 8 8 9],[1 4 1 5 3 6 7 9 8 1 10 10],true,10,10)
> > g1 = view(biograph(DG))
> > from4 = graphtraverse(DG,4);
> > to1 = graphtraverse(DG',1);
> > h = intersect(from4,to1)
> > DG2 = DG(h,h);
> > g2 = view(biograph(DG2,cellstr(num2str(h'))))
> >
> > HTH
> > Lucio

Subject: all possible path in a network/graph

From: Berk

Date: 9 Jan, 2013 12:01:09

Message: 6 of 6

Hi Syed,

Thank you very much. I have looked into the toolbox, and as you said, the toolbox seems to focus on shortest paths.

Thanks,
Berk

"galib " <galib.cse@gmail.com> wrote in message <kcjic8$jmc$1@newscl01ah.mathworks.com>...
> Hi Berk,
>
> That's where I was stuck. I wanted to get all possible paths. But getting all possible nodes served my purpose. So, I am not sure. You can download a toolbox called "matlab_bgl" from file exchange and see if they provide any function which can give you all possible paths of different length. As far I remember, they have a function for all pairs shortest path only.
>
> Syed
>
>
> "Berk" wrote in message <kcihk6$3fl$1@newscl01ah.mathworks.com>...
> > Hi,
> >
> > Would you please tell whether it is possible to enumerate all the paths having at most n edges? i.e. given a directed graph, enumerating all the paths of length 1, 2, ..., n?
> >
> > Thanks.
> >
> > "Lucio Cetto" wrote in message <j86gea$88o$1@newscl01ah.mathworks.com>...
> > > Syed:
> > > Be aware that if you want to enumerate "all" paths this could be a big problem, but following your idea about only retaining the nodes (or edges) that are in your solution you can achive this very easily using the Bioinformatics Toolbox graph functions (i.e. graph traversing algorithms), for example, all paths from node 4 to node 1 in the following graph:
> > >
> > > DG = sparse([2 2 3 4 5 5 5 6 7 8 8 9],[1 4 1 5 3 6 7 9 8 1 10 10],true,10,10)
> > > g1 = view(biograph(DG))
> > > from4 = graphtraverse(DG,4);
> > > to1 = graphtraverse(DG',1);
> > > h = intersect(from4,to1)
> > > DG2 = DG(h,h);
> > > g2 = view(biograph(DG2,cellstr(num2str(h'))))
> > >
> > > HTH
> > > Lucio

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us