MathGroup Archive 2002

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

Search the Archive

Re: creating adjacency matrices

  • To: mathgroup at smc.vnet.net
  • Subject: [mg36593] Re: [mg36561] creating adjacency matrices
  • From: Andrzej Kozlowski <andrzej at tuins.ac.jp>
  • Date: Fri, 13 Sep 2002 01:14:16 -0400 (EDT)
  • Sender: owner-wri-mathgroup at wolfram.com

One can make my original code (below) much faster by adding an  
auxiliary function and using "dynamic programming":

In[1]:=
ss=ReadList["adj.txt",{Number,Word}]

Out[1]=
{{1,A},{1,B},{2,B},{3,C},{4,B},{5,D},{5,E},{6,F},{7,A}}

In[2]:=
l=Length[Union[First[Transpose[ss]]]]

Out[2]=
7

a[i_] := a[i] = Cases[ss, {i, x_} -> x, {1}]

In[4]:=
Table[If[Intersection[a[i],a[j]]=!={},1,0](1- 
KroneckerDelta[i,j]),{i,l},{j,
       l}]//MatrixForm

Out[4]//MatrixForm=
0   1   0   1   0   0   1

1   0   0   1   0   0   0

0   0   0   0   0   0   0

1   1   0   0   0   0   0

0   0   0   0   0   0   0

0   0   0   0   0   0   0

1   0   0   0   0   0   0

For large lists you will see a large difference in speed.

Andrzej Kozlowski
Toyama International University
JAPAN





On Friday, September 13, 2002, at 01:48  am, Andrzej Kozlowski wrote:

> First of all, Import is not really meant for this sort of situation;  
> it is better to use ReadList. Suppose your file is:
>
> 1 A
> 1 B
> 2 B
> 3 C
> 4 B
> 5 D
> 5 E
> 6 F
> 7 A
>
> and its name is "adj.txt". Here is one way you can deal with this  
> case. First, read in the file:
>
>
> In[1]:=
> ss=ReadList["adj.txt",{Number,Word}]
>
> Out[1]=
> {{1,A},{1,B},{2,B},{3,C},{4,B},{5,D},{5,E},{6,F},{7,A}}
>
> Next, find how many "actors" there are:
>
> In[2]:=
> l=Length[Union[First[Transpose[ss]]]]
>
> Out[2]=
> 7
>
> Construct the adjacency matrix:
>
> In[3]:=
> Table[If[Intersection[Cases[ss,{i,x_}->x,{1}],
>              
> Cases[ss,{j,x_}->x,{1}]]=!={},1,0](1-KroneckerDelta[i,j]),{i,
>       l},{j,l}]//MatrixForm
>
> Out[3]//MatrixForm=
> 0   1   0   1   0   0   1
>
> 1   0   0   1   0   0   0
>
> 0   0   0   0   0   0   0
>
> 1   1   0   0   0   0   0
>
> 0   0   0   0   0   0   0
>
> 0   0   0   0   0   0   0
>
> 1   0   0   0   0   0   0
>
> The function ToAdjacencyMatrix form the Combinatorica package  
> constructs the adjacency matrix from a graph, so it has no direct  
> application to your problem.
>
> Andrzej Kozlowski
> Toyama International University
> JAPAN
>
>
>
>
> On Thursday, September 12, 2002, at 02:27  am, Moliterno, Thomas wrote:
>
>> I need to create an adjacency matrix from my data, which is currently  
>> in
>> the form of a .txt file and is basically a two column incidence list.
>> For example:
>>
>> 1 A
>> 1 B
>> 2 B
>> 3 C
>> . .
>> . .
>> . .
>> m n
>>
>> Where 1 to m represent actors and A to n represent events. My goal is  
>> to
>> have an (m x m) matrix where cell i,j equals 1 if two actors are
>> incident to the same event (in the sample above, 1 and 2 are both
>> incident to B) and 0 otherwise (w/ zeros on the diagonal).
>>
>> I'm new to Mathmatica, and so I'm on the steep part of the learning
>> curve ... All I've been able to figure out so far is how to get my
>> incidence list into the program using Import["filename.txt"]. But then
>> what? How do I convert to the adjacency matrix? I've found the
>> ToAdjacencyMatrix[] command in DiscreteMath`Combinatorica`, but I  
>> can't
>> seem to get it to work ...
>>
>> Thanks to any and all in advance.
>>
>> Tom
>>
>> **********************************************
>> Thomas P. Moliterno
>> Graduate School of Management
>> University of California, Irvine
>> tmoliter at uci.edu
>> **********************************************
>>
>>
>>
>
>



  • Prev by Date: RE: Empirical CDF and InterpolatingFunction
  • Next by Date: RE: Re: : huge number, ciphers after decimal point?
  • Previous by thread: RE: creating adjacency matrices
  • Next by thread: Re: creating adjacency matrices