4

I am writing an application that takes some file specifying an adjacency matrix and uses this to construct a graph (in this case, a directed social network).

What I would like to do is specify the size of the matrix and then have it generate an adjacency matrix with one of these topologies: ring, hierarchical, fully-connected, random and smallworld (every node x degrees of separation from each other). Ideally a text file would be the output.

I can't create these files manually because the size is in the thousands^2... Fully-connected and random aren't 100% required but they would be nice, I can just implement them in code.

I read a dissertation which specified it used an application located at http://ww2.cs.mu.oz.au/~tmill/graphtastic.tgz ...but it does not seem to exist anymore so I am not sure what to do. I thought there would be loads of applications such as this out there, but I can't see any.

So, is there an program out there that could generate an adjacency matrix with a configurable topology into a text file ?

3
  • Is this for homework?
    – psr
    Commented Feb 24, 2012 at 19:56
  • @psr not quite, it's for a dissertation. I would like the user to be able to submit their own adjacency matrix but that is pretty pointless if it's not feasible for them to do. It looks like I will just allow them to specify an enumeration (ring, smallWorld, etc.) and generate the topology in code. (but ultimately some adjacency matrix text file generator gives more possibilities for the empirical phase) Commented Feb 24, 2012 at 20:43
  • I've had this exact problem before. Not joking. I just restricted the cases to about one or two and went from there. Commented Apr 4, 2012 at 19:10

1 Answer 1

2

so you want:

graph => AM representation => textfile

this scriptlet ought to do the trick

(relies on two python libraries, Networkx and NumPy)

>>> import numpy as NP       # import NumPy
>>> import networkx as NX    # import top-level networkx namespace
>>> # mock some data
>>> # create a graph using a built-in graph generator from networkx
>>> G = NX.navigable_small_world_graph(12, 2, 1, 2, 2, seed=542)
>>> type(G)
  <class 'networkx.classes.digraph.DiGraph'>

>>> # express the graph as an Adjacency Matrix:
>>> # (a square matrix symmetric about the main diagonal)
>>> AM = NX.to_numpy_matrix(G)

>>> # use a built-in function from NumPy 
>>> # to save the Adjacency Matrix as a text file
    # import the library

>>> NP.savetxt("am.txt", AM, delimiter=',', newline="\n", fmt='%d')

>>> # to informally verify that it was saved correctly (just first 500 bytes)
>>> # read the text file back out 
>>> with open("am.txt", "r") as f:
f.read(500)

  '0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,
   0,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,
   0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,1,0,0,
   0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,...'

>>> # assertion for a unit test would look something like this:
>>> val AM0 = NP.loadtxt("am.txt", delimiter=",")
>>> NP.assert_allclose(AM, AM0, rtol=1e-5, atol=1e-3)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.