Proper way to add vertices to an adjacency matrix

Question

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=ArrayPad[matrix,1];
    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?

Answer 1

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_] :=    
    AdjacencyGraph[mat, GraphLayout -> "SpringEmbedding", 
       VertexLabels -> "Name", ImagePadding -> 5] ~VertexAdd~ vertices ~EdgeAdd~ connect
extendGraph[graph_?GraphQ, vertices_, connect_] := graph ~VertexAdd~ vertices ~EdgeAdd~ 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}} *)

Answer 2

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, %}