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: Wed, 24 Dec 2008 18:24:02 +0000 (UTC)
Organization: Awco
Lines: 55
Message-ID: <gituo2$r0k$1@fred.mathworks.com>
References: <gitp09$jh2$1@fred.mathworks.com> <gitpsv$51s$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 1230143042 27668 172.30.248.37 (24 Dec 2008 18:24:02 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Wed, 24 Dec 2008 18:24:02 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 1650284
Xref: news.mathworks.com comp.soft-sys.matlab:508673


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.