7.3 Graphs from adjacency matrices

To construct the graph Gamma with $ n \times n$ adjacency matrix $ A$ , you want a graph $ X$ so that the vertex-set of Gamma is $ \{1,..., n\}$ , and $ [i,j]$ is an edge of Gamma if and only if $ A[i][j] = 1$ .

Here is an example of the syntax in Sage (copied from Robert Miller's SageDays 3 talk):

sage: M = Matrix ([ [0, 1, 1], 
...   [1, 0, 1], 
...   [1, 1, 0] ]) 
...   # (the order is the number of edges) 
sage: G = Graph(M); G.order() 
3

Here is an example of the syntax in GRAPE:

sage: print gap.eval("A := [[0,1,0],[1,0,0],[0,0,1]]")
[ [ 0, 1, 0 ], [ 1, 0, 0 ], [ 0, 0, 1 ] ]
sage: print gap.eval("G := Group( (1,2) )")
Group([ (1,2) ])
sage: print gap.eval("Gamma := Graph( G, [1..3], OnPoints, function(x,y) return A[x][y] = 1; end,true )")  # optional gap package
rec( isGraph := true, order := 3, group := Group([ (1,2) ]),
  schreierVector := [ -1, 1, -2 ], adjacencies := [ [ 2 ], [ 3 ] ],
  representatives := [ 1, 3 ], names := [ 1, 2, 3 ] )
sage: print gap.eval("Adjacency(Gamma,1)")           # optional gap package
[ 2 ]
sage: print gap.eval("Adjacency(Gamma,2)")           # optional gap package
[ 1 ]
sage: print gap.eval("Adjacency(Gamma,3)")           # optional gap package
[ 3 ]
sage: print gap.eval("IsEdge( Gamma, [ 1, 2 ] )")    # optional gap package
true
sage: print gap.eval("Vertices( Gamma )")            # optional gap package
[ 1 .. 3 ]

Define the distance $ d(x,y)$ from $ x$ to $ y$ to be the minimum length of a (directed) path in Gamma joining a vertex $ x$ to a vertex $ y$ if such a path exists, and $ -1$ otherwise.

sage: print gap.eval("Distance( Gamma, 1, 3 )")      # optional gap package
-1

A diameter of $ -1$ is returned if Gamma is not (strongly) connected. Otherwise, the diameter of Gamma is equal to the maximum (directed) distance $ d(x,y)$ in gamma (as $ x$ and $ y$ range over all the vertices of Gamma).

sage: print gap.eval("Distance( Gamma, 1, 2 )")      # optional gap package
1

See About this document... for information on suggesting changes.