MathGroup Archive 2001

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

Search the Archive

Re: Swiftest code to turn list of ordered pairs into Markov matrix

  • To: mathgroup at smc.vnet.net
  • Subject: [mg29701] Re: [mg29683] Swiftest code to turn list of ordered pairs into Markov matrix
  • From: Rob Pratt <rpratt at email.unc.edu>
  • Date: Wed, 4 Jul 2001 03:08:26 -0400 (EDT)
  • Sender: owner-wri-mathgroup at wolfram.com

Perhaps you can modify the FromOrderedPairs command in the
DiscreteMath`Combinatorica` package.  FromOrderedPairs creates a graph,
but you can do Edges[FromOrderedPairs[oplist]] to get the adjacency
matrix.  The Edges[] matrix has entries in {0, 1}, so some modification is
needed if you want to count duplicate edges.

Rob Pratt
Department of Operations Research
The University of North Carolina at Chapel Hill

rpratt at email.unc.edu

http://www.unc.edu/~rpratt/

On Tue, 3 Jul 2001, Seth Chandler wrote:

> Suppose one has a list of ordered pairs oplist such as
> {{1,5},{1,6},{2,3},{2,3} ... }. All the values in the list are positive
> integers. The highest value in oplist is known to be some value z.
> 
> Now one wishes to form a matrix such that the value at element i,j is equal
> to
> Count[oplist,{i,j}]. One terribly slow way to do this is
> 
> Table[Count[oplist,{i,j}],{i,1,z},{j,1,z}]
> 
> A faster way to do this is as follows:
> Fold[ReplacePart[#,Extract[#,#2]+1,{#2}]&,Table[0,{z},{z}],oplist]
> 
> Does anyone have a considerably faster way? A speed up of 100% or more would
> be very helpful.
> 
> For what it's worth Count[oplist,{something_,_}] is the same for all values
> of something.
> 
> P.S. The problem arises in converting a representation of a directed graph
> into a Markov transition matrix.
> 
> Thanks,
> 
> Seth J. Chandler
> Associate Professor of Law
> University of Houston Law Center



  • Prev by Date: newsgroup use
  • Next by Date: Re: Swiftest code to turn list of ordered pairs into Markov matrix
  • Previous by thread: Re: Swiftest code to turn list of ordered pairs into Markov matrix
  • Next by thread: Re: Swiftest code to turn list of ordered pairs into Markov matrix