SED navigation bar go to SED home page go to Dataplot home page go to NIST home page SED Home Page SED Staff SED Projects SED Products and Publications Search SED Pages
Dataplot Vol 2 Vol 1

ADJACENCY MATRIX

Name:
    ADJACENCY MATRIX (LET)
Type:
    Let Subcommand
Purpose:
    Create an adjacency matrix from a list of edges.
Description:
    In graph theory, given n vertices an nxn adjacency matrix defines the connections between the edges. If there is an edge between vertex i and vertex j, then Aij = 1. Otherwise, Aij = 0.

    We make a distinction between undirected and directed adjacency matrices. For the undirected case, the order of the edges does not matter. So an edge between vertex i and vertex j means that both Aij and Aji will be set to 1. In the directed case, the order is relevant. So if Aij = 1, this does not imply that Aji = 1.

    Adjaency matrices are most useful when dealing with dense graphs with a relatively modest number of vertices.

Syntax 1:
    LET <mat> = ADJACENCY MATRIX <edge1> <edge2> <nvert>
    where <edge1> is a variable that identifies the first vertex in the edge;
                <edge2> is a variable that identifies the second vertex in the edge;
    and <mat> is a matrix where the adjacency matrix is saved.

    This syntax is used for the undirected case.

Syntax 2:
    LET <mat> = DIRECTED ADJACENCY MATRIX <edge1> <edge2> <nvert>
    where <edge1> is a variable that identifies the first vertex in the edge;
                <edge2> is a variable that identifies the second vertex in the edge;
    and <mat> is a matrix where the adjacency matrix is saved.

    This syntax is used for the directed case.

Examples:
    LET M = ADJACENCY MATRIX E1 E2 NVERT
Note:
    The maximum size matrix that DATAPLOT can handle is set when DATAPLOT is built on a particular site. Enter HELP DIMENSION and HELP MATRIX DIMENSION for details.
Default:
    None
Synonyms:
    EDGES TO ADJACENCY MATRIX is a synonym for ADJACENCY MATRIX.
Related Commands: References:
    Skiena (1998), "The Algorithm Design Manual", Telos.
Applications:
    Graph Theory
Implementation Date:
    2009/1
Program:
     
    dimension 100 columns
    read edge1 edge2
    2 3
    4 7
    1 9
    7 11
    5 8
    2 5
    6 10
    2 8
    3 8
    4 11
    end of data
    .
    let nvert = 14
    let adj = adjacency matrix edge1 edge2 nvert
    .
    set write format 14F5.0
    print adj
        

Date created: 9/8/2010
Last updated: 9/8/2010
Please email comments on this WWW page to alan.heckert@nist.gov.