Graph Format

Figure 4: A graph to be entered at the LISP prompt

The format used to describe trees (more generally, graphs) is the adjacency matrix, and the order of the graph. The order is entered on a single line as an integer. The adjacency matrix is entered as a series of 1's and 0's. A 1 at position $(i,j)$ in the adjacency matrix indicates that $i$ and $j$ are adjacent. To begin reading a graph manually, use the function read-graph. For instance, to enter the graph in Figure 4 perform the following:

[2]> (read-graph)
7
0 0 0 0 0 1 0 0
0 0 0 0 0 1 0 0
0 0 0 1 0 0 0 0
0 0 1 0 1 0 1 0
0 0 0 1 0 0 0 0
1 1 0 0 0 0 1 0
0 0 0 1 0 1 0 1
0 0 0 0 0 0 1 0

and the system will respond with

#S(GRAPH
   :ADJACENCY-MATRIX
   ((NIL NIL NIL NIL NIL T NIL NIL) (NIL NIL NIL NIL NIL T NIL NIL)
    (NIL NIL NIL T NIL NIL NIL NIL) (NIL NIL T NIL T NIL T NIL)
    (NIL NIL NIL T NIL NIL NIL NIL) (T T NIL NIL NIL NIL T NIL)
    (NIL NIL NIL T NIL T NIL T) (NIL NIL NIL NIL NIL NIL T NIL))
   :INTERNAL-ORDER NIL :INTERNAL-G6-STRING NIL :INTERNAL-CANONICAL-LABEL NIL
   :INTERNAL-DREADNAUT-STRING NIL :INTERNAL-GRACEFUL-LABELING NIL)

which is the system's internal representation of the graph structure. We needn't concern ourselves with this representation, however.

No checking is done to make sure that the input is correct. For instance, entering a graph in which a vertex is adjacent to itself will not flag an error. Nor is non-directedness flagged as an error. For instance, no error will be signalled if $(0,1)$ is marked 1 but $(1,0)$ is marked 0. Be careful with the input; otherwise later algorithms may not work correctly or as expected.