0

I want to create a nxn symmetric matrix in python. Lets say n=9, then I want something like below: 

array[[0,1,0,0,0,1,1,0,1],[1,0,1,1,1,0,0,0,0],[0,1,0,1,1,0,0,0,0]….].

I know how to do this by first creating a nun zeros matrix in python (np.zeros((9,9)) and then using a loop to populate it 1 and zeros. But I feel that is not a pythonic way. So was looking for an optimised way using loops would slow the code if the matrix is big.

Basically it's the adjacency matrix I am creating for an undirected graph. My follow-up question would be how to plot the graph for which one has an adjacency matrix. Any functions which plot undirected graph from adjacency matrix?

Please advise. I wanted to learn the best optimised/pythonic way of doing something in python rather than using traditional loops.

EDIT:

I used the following to create a edge list for a 30x30 adjacency matrix. But this edge list doesn't have pairs for each node in a cluster. If I start doing that the list would be huge. My graph below consequently doesn't have edges between each node in a cluster. How to automate this edge list so that I don't have to manually type all edge pairs. In the graph I want each node in a cluster to have an edge with other node in that cluster and only node 1 and 2 should have between cluster edge with node 16 and 17 of other cluster. 

N=30
# Creating a matrix of zeros. 
W=np.zeros((N,N))
# Mentioning the edges to start with. Thinking of a pair of 15 node cluster with two cluster connected by two pair of nodes. 
edge=[[1,2],[1,3],[1,4],[1,5],[1,6],[1,7],[1,8],[1,9],[1,10],[1,11],[1,12],[1,13],[1,14],[1,15],
      [16,17],[16,18],[16,19],[16,20],[16,21],[16,22],[16,23],[16,24],[16,25],[16,26],[16,27],[16,28],[16,29],[16,30],
      [1,16],[2,17]]

# Function for creating adjacency matrix ,populating the zeros matrix with 1 and 0-signifying edges on a node. 
def adjacencyMatrix():
    """This function creates an Adjacency Matrix from a edge set. 
    input-> set of edges to be connected 
    output-> Adjacency matrix (n,n)
    """
    for first,second in edge:
        W[first-1,second-1]=W[second-1][first-1]=1

Graph:

enter image description here

Improve this question
1
  • What kind of access do you have to your graph? Obviously, a is_adjacent(source_node, target_node)-type function is necessary, but do you have, for example, a get_neighbors(source_node)-type function that would return a list of target_nodes that were adjacent? That could be used to speed things up. Commented Mar 18, 2015 at 22:13

2 Answers 2

Reset to default
1

If all you care about is having the graph and an adjacency matrix, do you have to build the graph from the matrix? Or are you happy to do it the other way around instead?

You should look at networkx.

Bearing in mind the comment; you have a set of edges - you know these in advance (or at least how you want to create them - and you want to plot the graph. Now, you could create the adjacency matrix separately if you wanted, something like this:

A = [[0 for _ in range(N)] for _ in range(N)]
edges = [[1,2], [3,4], [6,1], ..., etc.]
for start, finish in edges: 
  A[start][finish] = A[finish][start] = 1

And then you could then just do the plotting as below - but why would you want to do this when you would be getting all that functionality from networkx anyway? You create an adjecency matrix by telling it what edges you have - the graph and the adjacency matrix hold exactly the same information, just in different formats, it makes no differences which way you do it (and it could be argued that doing it by adding edges to the graph is more readable too).

From your edit, you want to have two clusters of nodes, and then to have all nodes within each cluster joined to each other, and then a couple of extra edges. You mention that it would be tedious to do this manually, and you're right: so do it programatically.

import networkx as nx
from matplotlib import pyplot

G=nx.Graph()

# Why not group your nodes into clusters, since that's how you plan on using them.
node_clusters = [range(10), range(10,20)]


for node_cluster in node_clusters:
  for node in node_cluster:
    for other_node in node_cluster:
      if node != other_node:
        G.add_edge(node, other_node) # we don't actually need to add nodes, as the `add_edge` will add the nodes for us. 

#Add manual edges
G.add_edge(0,10)
G.add_edge(1, 11)


from networkx.linalg.graphmatrix import adjacency_matrix
A = adjacency_matrix(G)
print A

nx.draw(G)

pyplot.show()

enter image description here

Honestly though, if every node in each cluster is connected to each other, there's not really a huge amount of point drawing all the connections, summarising them instead as on larger node might make a nicer drawing.

Improve this answer
Sign up to request clarification or add additional context in comments.

7 Comments

Well the point is I am creating an adjacency matrix as the first step. Now my adjacency matrix is basically getting created with some graph in mind. But I don't start with a graph. I start with an adjacent matrix . So first ques. was how do you create an adjacency matrix(or basically populate the nxn matrix with 1 and 0's without using loops. Second question is once I have an adjacency matrix how do I create an undirected graph with nodes and edges shown. I guess your answer helps in second part. First part any idea?
This is helpful. Just one more thing. Here one has to mention the edge set. What is the nodes are like very high. Then one can't just keep mentioning the edge set for each nodes. Is there a way to automate this?. So lets say I want to have 30 nodes in such a way that 15 each form a cluster. So two clusters of nodes (15 each). Then I would have one edge between every pair of nodes within a cluster and the clusters are connected by some 2 edges between two different pair of nodes of each cluster. Currently I have to manually add those edge points in a list. Maybe automate the edge list above?
Plus I think the edges need to start with 0. Else it throws an error!
@Manish the nodes in the edges list were just an example - if you're indexing your nodes with 0...N then yes you'll need to do it that way, if you're indexing them with objects then you could use nested dictionaries instead. You can create the edges however you want though, there's no issue doing it programatically.
Hi Will, Pls check the edit. I am looking to kind of create an adjacency matrix which would create edge between each pair of nodes in a cluster and I have two such edges. Currently in the graph above, each cluster points is connected to only one node. I want each node to have edge with each other. The prob is my edge list is only for 1 node with other. But if I start creating a list set for each node with other node then it would be huge pain to write such list. Any idea how to automate this?
|
0

Adjacency matrices are usually sparse (nnz ~ O(N)), thus they are usually stored in sparse format. The simplest one is coo format that is basically three arrays: [row_ids, col_id, value], crs and csc are somewhat more complex to get used to, but have higher performance. The core benefit of using sparse representation is that when you start performing lets say, matvec you would get a huge speed-up usually (asymptotic complexity is lower under assumption nnz ~ O(N)).

Answering your question: you can build matrix with ones in positions pos = [(1, 4), (3, 2)] like this:

M = scipy.sparse.coo_matrix(([1]*len(pos), zip(*pos)))

which is in my view pretty much Pythonic :)

Improve this answer

3 Comments

Why would you say that is pythonic? I'd say it exactly isn't.
@will, generally, agree. But from my point that is pretty much explicit one-liner "put ones on those positions" (removed part about shapes - it was actually wrong)
I'm still on the fence i think, yeah it would be a little wasteful, but i always try to err on the side of maximum readability - and for me one thing that involves is not nesting functions as arguments to others. Might just be me, but i prefer it. And especially think it's more helpful answering questions on here, as asking the question in the first place includes at least some implication of not being completely comfortable with python.

Your Answer

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.