7 Replies - 6199 Views - Last Post: 06 June 2012 - 03:31 PM

#1 eiarzate  Icon User is offline

  • New D.I.C Head

Reputation: -3
  • View blog
  • Posts: 33
  • Joined: 21-January 10

Adjacency Matrix to Sparse Graph Representation.

Posted 04 June 2012 - 05:13 PM

Can anyone explain how to get from an adjacency matrix to a sparse graph representation.

I have provided a picture of the example I am trying to understand. I have looked everywhere for information about the subject (books, youtube, scholar articles, google).
I understand that a sparse graph representation has non-zero values entities but other than that I have no idea how get from the adjacency matrix to sparse graph.

If anyone can provide a reference or explain it will be greatly appreciated.Attached Image

Sorry but I could not rotate image. You can just download image and rotate it in your image viewer.

This post has been edited by eiarzate: 04 June 2012 - 05:16 PM


Is This A Good Question/Topic? 0
  • +

Replies To: Adjacency Matrix to Sparse Graph Representation.

#2 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10397
  • View blog
  • Posts: 38,465
  • Joined: 27-December 08

Re: Adjacency Matrix to Sparse Graph Representation.

Posted 05 June 2012 - 09:03 PM

So we know that a Graph has Vertices, connected by Edges. An adjacency matrix relates the vertices in a matrix form. Think of it like a Cartesian coordinate system. On each axis, there are the vertices labeled. If the two vertices A and C intersect, it is marked at cells (A, C) and (C, A). A cell without a mark means that two vertices do not intersect.
Was This Post Helpful? 0
  • +
  • -

#3 eiarzate  Icon User is offline

  • New D.I.C Head

Reputation: -3
  • View blog
  • Posts: 33
  • Joined: 21-January 10

Re: Adjacency Matrix to Sparse Graph Representation.

Posted 05 June 2012 - 09:35 PM

That's not the question.

The question is how do you get from an adjacency matrix to a sparse graph?
And for the record a sparse graph is not a linked list representation.
Was This Post Helpful? 0
  • +
  • -

#4 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10397
  • View blog
  • Posts: 38,465
  • Joined: 27-December 08

Re: Adjacency Matrix to Sparse Graph Representation.

Posted 05 June 2012 - 09:45 PM

I don't mean to be rude, but that is the question here. The Graph is sparse regardless of how it is represented- be it an adjacency list or an adjacency matrix.
Was This Post Helpful? 0
  • +
  • -

#5 eiarzate  Icon User is offline

  • New D.I.C Head

Reputation: -3
  • View blog
  • Posts: 33
  • Joined: 21-January 10

Re: Adjacency Matrix to Sparse Graph Representation.

Posted 05 June 2012 - 10:01 PM

In this question Sparse is not a word that describes the graph.
A sparse graph representation is another way a set of nodes and edges (graph) can be represented.
There are three ways a set of edges and nodes (graph) can be represented :
1. Adjacency matrix representation
2. Linked list representation
3. Sparse graph representation
Well those are three ways I am aware of.
Some programming languages come with build in subroutines that handle converting from one representation to another.
MATLAB and Java are two languages that handle this.
But the question is a theory question how to handle the conversion from Adjacency matrix representation(1) to Sparse graph representation(3).
Was This Post Helpful? -1
  • +
  • -

#6 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10397
  • View blog
  • Posts: 38,465
  • Joined: 27-December 08

Re: Adjacency Matrix to Sparse Graph Representation.

Posted 05 June 2012 - 10:11 PM

Figure 3 seems to deal with another graph as far as I can tell from the image, not the adjacency matrix in the image. Also, just FYI, Java has no formal graph theory support built-in (beyond standard Linked Lists and JTrees). Yes, it uses some graph theory in the Collections framework (like with Maps), but not to the extent you are describing. A Sparse Graph is something specific to MATLAB. In formal graph theory, there are four ways of representing graphs: adjacency lists, adjacency matrices, incidence lists, and incidence matrices. Graph density (or sparsity) deals with the ratio of edges to vertices.
Was This Post Helpful? 0
  • +
  • -

#7 eiarzate  Icon User is offline

  • New D.I.C Head

Reputation: -3
  • View blog
  • Posts: 33
  • Joined: 21-January 10

Re: Adjacency Matrix to Sparse Graph Representation.

Posted 05 June 2012 - 10:29 PM

When you convert an array to an arraylist it's how you change between representations in theory...
I have attached a clear image sorry about that blurry one.
Also this is not something I came up with or making up.
The following is a hyperlink where a sparse graph(matrix same thing) is described:
http://www.cs.cmu.ed...cacm/node9.html

Attached Image

This post has been edited by eiarzate: 05 June 2012 - 10:27 PM

Was This Post Helpful? 0
  • +
  • -

#8 mojo666  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 352
  • View blog
  • Posts: 770
  • Joined: 27-June 09

Re: Adjacency Matrix to Sparse Graph Representation.

Posted 06 June 2012 - 03:31 PM

Weird, this book seems to start arrays at position 1.

The indexes of arow correspond to a vertex. The values of arow correspond to a position in acol. The values of acol correspond to a vertex.

acol contains several lists of vertices and each list connects to a particular point. You check which point that is by looking at arow.

arow gives you the range of values that correspond to a vertex. For example, A=1. arow[1] and arow[2] give you the range [1, 3) or the first and third index of acol. These values are 2 and 3 (or B and C). So, A is connected to B and C. If we want to find the edges attached to E, we look at the 5th element of arow. arow[5] and arow[6] give the range [11, 14). acol[11] through acol[14] contain the values 4, 6, and 7 (or D, F, and G).

I hope this explanation helps.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1