Path: news.mathworks.com!not-for-mail
From: "ayman ayad" <sea_dreamer82@yahoo.com>
Newsgroups: comp.soft-sys.matlab
Subject: Re: urgent help in " calcualting number of free independent path"
Date: Thu, 25 Dec 2008 19:16:02 +0000 (UTC)
Organization: Awco
Lines: 67
Message-ID: <gj0m5i$p52$1@fred.mathworks.com>
References: <gitp09$jh2$1@fred.mathworks.com> <gitpsv$51s$1@fred.mathworks.com> <gituo2$r0k$1@fred.mathworks.com> <gitvti$jfu$1@fred.mathworks.com>
Reply-To: "ayman ayad" <sea_dreamer82@yahoo.com>
NNTP-Posting-Host: webapp-02-blr.mathworks.com
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 8bit
X-Trace: fred.mathworks.com 1230232562 25762 172.30.248.37 (25 Dec 2008 19:16:02 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Thu, 25 Dec 2008 19:16:02 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 1650284
Xref: news.mathworks.com comp.soft-sys.matlab:508762


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 &#954;(u,v) and &#955;(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 &#954;(u,v) and &#955;(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!