A procedure for generating incidence matrices

Finally, as an advanced example, we show how to compute an incidence matrix from a list of edges in a network. Suppose the nodes of the network are . The directed edges can be given as a list of pairs [i,j] where i is the beginning node of the edge and j is the ending node. Thus, from a list of these pairs, we should be able to generate the incidence matrix. Here's the procedure.

> incidmatrix:=proc(edges:list)
>    local nnodes,nedges,incid,i;
>    nedges:=nops(edges);
>    nnodes:= nops( { op( map(op,edges) ) } );
>    incid:=matrix(nedges,nnodes,0);
>    for i from 1 to nedges do
>          incid[i, op(1,edges[i])]:=-1;
>          incid[i, op(2,edges[i])]:=1
>    od;
>    eval(incid)
> end:

A first example below is a list of edges specified by beginning and ending node.

> v:=[ [1,2],[4,2],[5,3],[3,6],[1,4],[6,5] ];

We compute the incidence matrix with our procedure:

> incidmatrix(v);

Now we go through and explain the steps of our procedure. First, compute the number of edges:

> nedges:=nops(v);

Next use op to generate a list of the operands in all the terms in v.

> w:= map(op,v);

Form the ``set'' of nodes by taking op(w) and enclosing it in braces. Maple eliminates all duplicate entries in a set.

> s:={op(w)};

Compute the number of nodes.

> nnodes:=nops(s);

Now we create an incidence matrix with all entries initialized to 0.

> incid:=matrix(nedges,nnodes,0);

The for loop goes through each edge in v and assigns -1 to the starting node and +1 to the ending node in the corresponding row of incid.

Be prepared for a lot of output here.

>    for i from 1 to nedges do
         incid[i, op(1,v[i])]:=-1;
         incid[i, op(2,v[i])]:=1
   od;

eval displays the final matrix that results.

> eval(incid);

Now as it turns out, Maple has a builtin networks package that can be used to find the incidence matrix. Be sure to read the help page:

> ?networks

First, load the package

> with(networks);

Define a network by the graph procedure.

• Give a set of vertices, e.g. .
• Give a set of directed edges as the second argument. A directed edge is a ``list'' [i,j]. An undirected edge is a ``set'' .

> G:=graph({1,2,3,4},{[1,2],[1,3],[2,3],[2,4],[3,4]}):

Draw the network.

> draw(G);

Compute the incidence matrix: incidence(G) is nodes by edges; take the transpose to get the edge-node incidence matrix:

> A:= transpose( incidence(G)  );