I'm looking for a robust way to add vertices to a graph by modifying its AdjacencyMatrix.

Here's what I have so far:

addNode[matrix_,in_,out_]:=Module[{mod},
mod[[1,2]]=1;
mod[[2,1]]=1;
mod[[Length@mod,-out]]=1;
mod[[-out,Length@mod]]=1;
mod
]


This will add a vertex connected to vertex 1 and another vertex connected to vertex out. Notice that I only add 1x1 0's to my matrix. This is because at the moment I only need to add 2 vertices to my graphs.

Examples:  I've tried implementing a similar function that accepts the in argument, but I couldn't get it to work properly. It seems as if I have to program special cases for it to work.

Is there a better way to do this?

• Do you want an adjacency matrix as the output or a graph as the output? Or does it not matter? – rm -rf Aug 8 '12 at 23:22
• @RM I'd prefer an adjacency matrix, since I'll be able to call the function on itself if I need to add more vertices. But in the end, it's not crucial. – CHM Aug 8 '12 at 23:25

There are functions that allow you to add vertices and edges, namely VertexAdd and EdgeAdd. You can use these to conveniently add vertices and manage connections on the fly. Here's an example that accepts either an AdjacencyMatrix or a Graph object.

Clear@extendGraph
extendGraph[mat_?MatrixQ, vertices_, connect_] :=


You can then extend this further to delete edges/vertices using the EdgeDelete and VertexDelete functions in a similar way.

Here are some example usages:

a = {{0, 1, 0, 1}, {1, 0, 1, 0}, {0, 1, 0, 1}, {1, 0, 1, 0}};
g1 = extendGraph[a, {5, 6}, {1 \[UndirectedEdge] 5, 4 \[UndirectedEdge] 6}] g2 = extendGraph[g1, {7, 8}, {7 \[UndirectedEdge] 2, 8 \[UndirectedEdge] 4}] Use AdjacencyMatrix on the above graphs to get the matrix (although, it is not necessary, since my definition allows you to use it again on the graph itself)

AdjacencyMatrix@g2 // Normal
(* {{0, 1, 0, 1, 1, 0, 0, 0},
{1, 0, 1, 0, 0, 0, 1, 0},
{0, 1, 0, 1, 0, 0, 0, 0},
{1, 0, 1, 0, 0, 1, 0, 1},
{1, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 1, 0, 0, 0, 0},
{0, 1, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 1, 0, 0, 0, 0}} *)

• This works great, thanks! I didn't know about VertexAdd and EdgeAdd. – CHM Aug 8 '12 at 23:50

I answered a similar question before using interactive solution in this example. To construct a basic function you could use EdgeList:

f[m_, v1_, v2_] := AdjacencyMatrix[Graph[EdgeList[AdjacencyGraph[m,
DirectedEdges -> False]]~Join~{v1 \[UndirectedEdge] v2}]]


Here how it works. If you start from a matrix:

m = {{0, 1, 1, 0},
{1, 0, 1, 1},
{1, 1, 0, 1},
{0, 1, 1, 0}};


this is what you will get:

f[m, 4, 5] // Normal // MatrixForm These are the graphs:

AdjacencyGraph /@ {m, %} Now if you want to add a few vertexes at a time you could modify your function like:

g[m_, l_] := AdjacencyMatrix[Graph[EdgeList[AdjacencyGraph[m,
DirectedEdges -> False]]~Join~(UndirectedEdge @@@ l)]]


Don't for get that labels can be pretty arbitrary and new vertexes can be disconnected from original graph - it still will work:

g[m, {{4, 5}, {5, "CAT"}, {"DOG", "BIRD"}}] // Normal // MatrixForm AdjacencyGraph /@ {m, %} 