MATLAB Central Newsreader - urgent help in " calcualting number of free independent path"

urgent help in " calcualting number of free independent path"

ayman ayad — Wed, 24 Dec 2008 16:46:01 -0500

i have a network "water pipe netwrok "
and i have the "connectivity matrix " bwteen points
and i know the id of source points

does anyone know a file m-file or a way where i can claculate
free independent path , or number of possible paths between source points and any point in the network
so i can have at the end a digit equall to that number of paths ??

i really need that help so so so much in my Msc

so if anyone can help me with that i will be so greatful
also u can send me in my e-mail sea_dreamer82@yahoo.com

Re: urgent help in " calcualting number of free independent path"

David — Wed, 24 Dec 2008 17:01:20 -0500

"ayman ayad" <sea_dreamer82@yahoo.com> wrote in message <gitp09$jh2$1@fred.mathworks.com>...
> i have a network "water pipe netwrok "
> and i have the "connectivity matrix " bwteen points
> and i know the id of source points
>
> does anyone know a file m-file or a way where i can claculate
> free independent path , or number of possible paths between source points and any point in the network
> so i can have at the end a digit equall to that number of paths ??
>
> i really need that help so so so much in my Msc
>
> so if anyone can help me with that i will be so greatful
> also u can send me in my e-mail sea_dreamer82@yahoo.com

this sounds more like a question for a math or topology theory group to first determine the algorithm you need.

Re: urgent help in " calcualting number of free independent path"

ayman ayad — Wed, 24 Dec 2008 18:24:02 -0500

i found some tips searching in wikipedia

under following links

http://en.wikipedia.org/wiki/Connectivity_(graph_theory)
http://en.wikipedia.org/wiki/Menger%27s_theorem

i just want to calculate the number of possible routes (path) from source points to other points in a given network .. having the connectivity (adjecency ) network
which is in form of

point id 1 2 3 4 5
line id 1 1 0 0 0 -1
line id 2 0 1 -1 0 0

and so on

The problem of determining whether two vertices in a graph are connected can be solved efficiently using a search algorithm, such as breadth-first search. More generally, it is easy to determine computationally whether a graph is connected (for example, by using a disjoint-set data structure), or to count the number of connected components. A simple algorithm might be written in pseudo-code as follows:

Begin at any arbitrary node of the graph, G
Proceed from that node using either depth-first or breadth-first search, counting all nodes reached.
Once the graph has been entirely traversed, if the number of nodes counted is equal to the number of nodes of G, the graph is connected; otherwise it is disconnected.
By Menger's theorem, for any two vertices u and v in a connected graph G, the numbers κ(u,v) and λ(u,v) can be determined efficiently using the max-flow min-cut algorithm. The connectivity and edge-connectivity of G can then be computed as the minimum values of κ(u,v) and λ(u,v), respectively.
In computational complexity theory, SL is the class of problems log-space reducible to the problem of determining whether two vertices in a graph are connected, which was proved to be equal to L by Omer Reingold in 2004. Hence, undirected graph connectivity may be solved in O(logn) space.

The problem of computing the probability that a Bernoulli random graph is connected is called Network reliability and the problem of computing whether two given vertices are connected the ST-reliability problem. Both of these are #P-hard.

i

Menger's theorem
diected graph

"David" <dave@bigcompany.com> wrote in message <gitpsv$51s$1@fred.mathworks.com>...
> "ayman ayad" <sea_dreamer82@yahoo.com> wrote in message <gitp09$jh2$1@fred.mathworks.com>...
> > i have a network "water pipe netwrok "
> > and i have the "connectivity matrix " bwteen points
> > and i know the id of source points
> >
> > does anyone know a file m-file or a way where i can claculate
> > free independent path , or number of possible paths between source points and any point in the network
> > so i can have at the end a digit equall to that number of paths ??
> >
> > i really need that help so so so much in my Msc
> >
> > so if anyone can help me with that i will be so greatful
> > also u can send me in my e-mail sea_dreamer82@yahoo.com
>
> this sounds more like a question for a math or topology theory group to first determine the algorithm you need.

Re: urgent help in " calcualting number of free independent path"

David — Wed, 24 Dec 2008 18:44:02 -0500

"ayman ayad" <sea_dreamer82@yahoo.com> wrote in message <gituo2$r0k$1@fred.mathworks.com>...
> i found some tips searching in wikipedia
>
> under following links
>
> http://en.wikipedia.org/wiki/Connectivity_(graph_theory)
> http://en.wikipedia.org/wiki/Menger%27s_theorem
>
> i just want to calculate the number of possible routes (path) from source points to other points in a given network .. having the connectivity (adjecency ) network
> which is in form of
>
> point id 1 2 3 4 5
> line id 1 1 0 0 0 -1
> line id 2 0 1 -1 0 0
>
> and so on
>
>
>
>
>
>
>
> The problem of determining whether two vertices in a graph are connected can be solved efficiently using a search algorithm, such as breadth-first search. More generally, it is easy to determine computationally whether a graph is connected (for example, by using a disjoint-set data structure), or to count the number of connected components. A simple algorithm might be written in pseudo-code as follows:
>
> Begin at any arbitrary node of the graph, G
> Proceed from that node using either depth-first or breadth-first search, counting all nodes reached.
> Once the graph has been entirely traversed, if the number of nodes counted is equal to the number of nodes of G, the graph is connected; otherwise it is disconnected.
> By Menger's theorem, for any two vertices u and v in a connected graph G, the numbers κ(u,v) and λ(u,v) can be determined efficiently using the max-flow min-cut algorithm. The connectivity and edge-connectivity of G can then be computed as the minimum values of κ(u,v) and λ(u,v), respectively.
> In computational complexity theory, SL is the class of problems log-space reducible to the problem of determining whether two vertices in a graph are connected, which was proved to be equal to L by Omer Reingold in 2004. Hence, undirected graph connectivity may be solved in O(logn) space.
>
> The problem of computing the probability that a Bernoulli random graph is connected is called Network reliability and the problem of computing whether two given vertices are connected the ST-reliability problem. Both of these are #P-hard.
>
> i
>
> Menger's theorem
> diected graph
>
>
>
> "David" <dave@bigcompany.com> wrote in message <gitpsv$51s$1@fred.mathworks.com>...
> > "ayman ayad" <sea_dreamer82@yahoo.com> wrote in message <gitp09$jh2$1@fred.mathworks.com>...
> > > i have a network "water pipe netwrok "
> > > and i have the "connectivity matrix " bwteen points
> > > and i know the id of source points
> > >
> > > does anyone know a file m-file or a way where i can claculate
> > > free independent path , or number of possible paths between source points and any point in the network
> > > so i can have at the end a digit equall to that number of paths ??
> > >
> > > i really need that help so so so much in my Msc
> > >
> > > so if anyone can help me with that i will be so greatful
> > > also u can send me in my e-mail sea_dreamer82@yahoo.com
> >
> > this sounds more like a question for a math or topology theory group to first determine the algorithm you need.

great! now you have a place to start. now just convert that theorem into a practical algorithm to work on the data that you have and you'll be done!

Re: urgent help in " calcualting number of free independent path"

ayman ayad — Thu, 25 Dec 2008 19:16:02 -0500

the problem is that iam acivil engineer with like zero knowledge in such mathmatics algorithms
i was hoping to find someone who have such algorithm or .m file already written

or any .m file that calculate the reliability of a network or number of possible routes from a single point to all other points in a network

hope to find an answer , thanks

"David" <dave@bigcompany.com> wrote in message <gitvti$jfu$1@fred.mathworks.com>...
> "ayman ayad" <sea_dreamer82@yahoo.com> wrote in message <gituo2$r0k$1@fred.mathworks.com>...
> > i found some tips searching in wikipedia
> >
> > under following links
> >
> > http://en.wikipedia.org/wiki/Connectivity_(graph_theory)
> > http://en.wikipedia.org/wiki/Menger%27s_theorem
> >
> > i just want to calculate the number of possible routes (path) from source points to other points in a given network .. having the connectivity (adjecency ) network
> > which is in form of
> >
> > point id 1 2 3 4 5
> > line id 1 1 0 0 0 -1
> > line id 2 0 1 -1 0 0
> >
> > and so on
> >
> >
> >
> >
> >
> >
> >
> > The problem of determining whether two vertices in a graph are connected can be solved efficiently using a search algorithm, such as breadth-first search. More generally, it is easy to determine computationally whether a graph is connected (for example, by using a disjoint-set data structure), or to count the number of connected components. A simple algorithm might be written in pseudo-code as follows:
> >
> > Begin at any arbitrary node of the graph, G
> > Proceed from that node using either depth-first or breadth-first search, counting all nodes reached.
> > Once the graph has been entirely traversed, if the number of nodes counted is equal to the number of nodes of G, the graph is connected; otherwise it is disconnected.
> > By Menger's theorem, for any two vertices u and v in a connected graph G, the numbers κ(u,v) and λ(u,v) can be determined efficiently using the max-flow min-cut algorithm. The connectivity and edge-connectivity of G can then be computed as the minimum values of κ(u,v) and λ(u,v), respectively.
> > In computational complexity theory, SL is the class of problems log-space reducible to the problem of determining whether two vertices in a graph are connected, which was proved to be equal to L by Omer Reingold in 2004. Hence, undirected graph connectivity may be solved in O(logn) space.
> >
> > The problem of computing the probability that a Bernoulli random graph is connected is called Network reliability and the problem of computing whether two given vertices are connected the ST-reliability problem. Both of these are #P-hard.
> >
> > i
> >
> > Menger's theorem
> > diected graph
> >
> >
> >
> > "David" <dave@bigcompany.com> wrote in message <gitpsv$51s$1@fred.mathworks.com>...
> > > "ayman ayad" <sea_dreamer82@yahoo.com> wrote in message <gitp09$jh2$1@fred.mathworks.com>...
> > > > i have a network "water pipe netwrok "
> > > > and i have the "connectivity matrix " bwteen points
> > > > and i know the id of source points
> > > >
> > > > does anyone know a file m-file or a way where i can claculate
> > > > free independent path , or number of possible paths between source points and any point in the network
> > > > so i can have at the end a digit equall to that number of paths ??
> > > >
> > > > i really need that help so so so much in my Msc
> > > >
> > > > so if anyone can help me with that i will be so greatful
> > > > also u can send me in my e-mail sea_dreamer82@yahoo.com
> > >
> > > this sounds more like a question for a math or topology theory group to first determine the algorithm you need.
>
> great! now you have a place to start. now just convert that theorem into a practical algorithm to work on the data that you have and you'll be done!

Re: urgent help in " calcualting number of free independent path"

ayman ayad — Wed, 07 Jan 2009 14:33:02 -0500

hi all
I wish you all first a wonderful day and hope everything is going great
Let me introduce myself
Aim ayman Ramadan from Egypt
I prepare my master in "optimal design of pipe network"
And I was seeking a help in the matter of
"Transferring the arc-node adjacency matrix into node- arc connectivity matrix"

For example
A closed rectangle loop of 4 nodes A, B.C.D
The arc-node adjacency matrix = [ 1 0 -1 0 ; 0 1 -1 0 ; 0 0 1 -1 ; -1 0 0 1]
I have such matrix and I want to convert it into
[0 1 0 1; 1 0 1 0; 0 1 0 1 ; 1 0 1 0]
Can you help me with that?
I really hope that I didn’t annoy you

Wish you again best
Yours
Ayman Ayad
Sea_dreamer82@yahoo.com

Re: urgent help in " calcualting number of free independent path"

Ray — Mon, 20 Jul 2009 12:09:01 -0400

Ayman,

The number of paths from one node to another can be obtained through linear graph theory. Multiply the adjacency matrix times itself (A^2) and you will see the number of paths of length 2 between each pair of nodes ij. Multiply the adjacency matrix by itself n times (A^n) to find the number of paths of length n between each pair of nodes ij.

Ref: http://oneweb.utc.edu/~Christopher-Mawata/petersen/lesson7.htm

Ray
_________________
"ayman ayad" <sea_dreamer82@yahoo.com> wrote in message <gitp09$jh2$1@fred.mathworks.com>...
> i have a network "water pipe netwrok "
> and i have the "connectivity matrix " bwteen points
> and i know the id of source points
>
> does anyone know a file m-file or a way where i can claculate
> free independent path , or number of possible paths between source points and any point in the network
> so i can have at the end a digit equall to that number of paths ??
>
> i really need that help so so so much in my Msc
>
> so if anyone can help me with that i will be so greatful
> also u can send me in my e-mail sea_dreamer82@yahoo.com

Re: urgent help in " calcualting number of free independent path"

Andy Eisenberg — Mon, 20 Jul 2009 13:11:01 -0400

I'm not sure what the difference is between an arc-node adjacency matrix and a node-arc connectivity matrix, and I'm at work right now so I can't spend time looking this up. But since your arc-node adjacency matrix (which seems to be your input) has -1 in it, it is not just the standard adjacency matrix of a directed graph. So Ray's solution of raising the matrix to a power will not work.

"Ray " <removethis_ray@aarden.us> wrote in message <h41mot$gkq$1@fred.mathworks.com>...
> Ayman,
>
> The number of paths from one node to another can be obtained through linear graph theory. Multiply the adjacency matrix times itself (A^2) and you will see the number of paths of length 2 between each pair of nodes ij. Multiply the adjacency matrix by itself n times (A^n) to find the number of paths of length n between each pair of nodes ij.
>
> Ref: http://oneweb.utc.edu/~Christopher-Mawata/petersen/lesson7.htm
>
> Ray
> _________________
> "ayman ayad" <sea_dreamer82@yahoo.com> wrote in message <gitp09$jh2$1@fred.mathworks.com>...
> > i have a network "water pipe netwrok "
> > and i have the "connectivity matrix " bwteen points
> > and i know the id of source points
> >
> > does anyone know a file m-file or a way where i can claculate
> > free independent path , or number of possible paths between source points and any point in the network
> > so i can have at the end a digit equall to that number of paths ??
> >
> > i really need that help so so so much in my Msc
> >
> > so if anyone can help me with that i will be so greatful
> > also u can send me in my e-mail sea_dreamer82@yahoo.com