10
$\begingroup$

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:

Mathematica graphics Mathematica graphics

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ Do you want an adjacency matrix as the output or a graph as the output? Or does it not matter? $\endgroup$ Commented Aug 8, 2012 at 23:22
  • $\begingroup$ @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. $\endgroup$ Commented Aug 8, 2012 at 23:25

2 Answers 2

Reset to default
10
$\begingroup$

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}]

enter image description here

g2 = extendGraph[g1, {7, 8}, {7 \[UndirectedEdge] 2, 8 \[UndirectedEdge] 4}]

enter image description here

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}} *)
Improve this answer
$\endgroup$
1
  • $\begingroup$ This works great, thanks! I didn't know about VertexAdd and EdgeAdd. $\endgroup$ Commented Aug 8, 2012 at 23:50
4
$\begingroup$

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

enter image description here

These are the graphs:

AdjacencyGraph /@ {m, %}

enter image description here

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

enter image description here

AdjacencyGraph /@ {m, %}

enter image description here

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.