Re: Counting the number of paths in a network
- To: mathgroup at smc.vnet.net
- Subject: [mg64596] Re: Counting the number of paths in a network
- From: "Steve Luttrell" <steve_usenet at _removemefirst_luttrell.org.uk>
- Date: Thu, 23 Feb 2006 00:35:17 -0500 (EST)
- References: <dthhhr$nek$1@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
You need to use HamiltonianCycle. Here is an example of how this solves your
problem:
<<DiscreteMath`Combinatorica`
g=RandomGraph[10,0.5];
h=HamiltonianCycle[g];
ShowGraph[g];
ShowGraph[Highlight[g,{Partition[h,2,1]}]];
hall=HamiltonianCycle[g,All];
Length[hall]
The total number of Hamiltonian cycles is Length[hall], which is equal to
the number of loops that start from and eventually return to any starting
node, having visited every other node exactly once.
Steve Luttrell
"John Dickmann" <jqd at MIT.EDU> wrote in message
news:dthhhr$nek$1 at smc.vnet.net...
>I am interested in counting the number of paths from a node in a
> network back to that node, counting loops (cycles) only once. Is
> there any readily available code that does this?
>
> I found some code posted here a few years ago that counts the number
> of paths between two nodes, but am having trouble modifying it to
> complete the loop (it also enumerates each path, but I'm not really
> interested in that).
>
> More academically, is there perhaps a better measurement for the
> fundamental feature --namely the number of options available to
> someone to get information around a system?
>
> thanks for any help,
>
> John
>
>
> John Q. Dickmann
> Research Assistant
> Lean Aerospace Initiative
> Massachusetts Institute of Technology
> Bldg 41-205
> 77 Massachusetts Ave.
> Cambridge, MA 02139
>
> jqd at mit.edu
> 401-225-3511
>
>