Adjacency Matrix

[danghotties]

Hi,
I have an input file with string names of vertices to make a graph (adjacency matrix). How can I make it so the string names correspond to numbers to go with the rows and columns of the matrix?

For example, say the file contains:
V1
V2
V3
...

I want it to be like

      V1  V2   V3
V1    0    0    0
V2    0    0    0
V3    0    0    0
...

And then have (V1,V1) mean (1,1) in the matrix.

And if I wanted a weighted edge between the two vertices I'd have something like addEdge(V1, V3, weight), where V1 and V3 correspond ints of (1,3) for (i,j) in the matrix.

[danghotties]

Please help :(

[Duthomhas]

The way you represent things with text only matters when you are either reading or writing it. Manipulating stuff inside the program doesn't need it.

[danghotties]

I'm making a graph using an adjacency matrix. It takes two input files, one of vertices, and one of edges.

If I have an edge like: V192 and V284, how would it know where to edit the matrix to show there's an edge there?

I want to make it so a vertex corresponds to say, for example, 5 and 3 for V192 and V284, respectively. How else would it know to go to (5,3) in the matrix?

[Duthomhas]

Ah, your matrix has a lot of rows and columns? I presume it is fairly sparse?

Use a std::map with a custom 'edge' type.

struct edge
{
  int u, v;
  edge(): u(), v() { }
  edge( int u, int v ): u( u ), v( v ) { }

  bool operator < ( const edge& e ) const 
  {
    return (u < e.u) ? true
         : (u == e.u) ? (v < e.v)
         : false;
  }
};

typedef std::map <edge, bool> adjmatrix;

Now all you have to do is strip the 'V' from the vertex name to get it's index, and use the indices to lookup an edge.

You can iterate through the edges too.

Hope this helps.

[danghotties]

Sorry I should have said the identifiers for vertices can be any string of max length 20.

[Duthomhas]

Well, replace int with std::string.