MathGroup Archive 2006

[Date Index] [Thread Index] [Author Index]

Search the Archive

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



  • Prev by Date: Re: Increment and AddTo
  • Next by Date: Re: Increment and AddTo
  • Previous by thread: Re: Counting the number of paths in a network
  • Next by thread: JLink, Double.NaN, and arrays