Path: news.mathworks.com!not-for-mail
From: <HIDDEN>
Newsgroups: comp.soft-sys.matlab
Subject: Re: urgent help in " calcualting number of free independent path"
Date: Wed, 24 Dec 2008 18:44:02 +0000 (UTC)
Organization: The MathWorks, Inc.
Lines: 58
Message-ID: <gitvti$jfu$1@fred.mathworks.com>
References: <gitp09$jh2$1@fred.mathworks.com> <gitpsv$51s$1@fred.mathworks.com> <gituo2$r0k$1@fred.mathworks.com>
Reply-To: <HIDDEN>
NNTP-Posting-Host: webapp-05-blr.mathworks.com
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 8bit
X-Trace: fred.mathworks.com 1230144242 19966 172.30.248.35 (24 Dec 2008 18:44:02 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Wed, 24 Dec 2008 18:44:02 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 791003
Xref: news.mathworks.com comp.soft-sys.matlab:508675


"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!