50.1 Introduction to graphs

The graphs package provides graph and digraph data structure for Maxima. Graphs and digraphs are simple (have no multiple edges nor loops), although digraphs can have a directed edge from u to v and a directed edge from v to u.

Internally graphs are represented by adjacency lists and implemented as a lisp structures. Vertices are identified by their ids (an id is an integer). Edges/arcs are represented by lists of length 2. Labels can be assigned to vertices of graphs/digraphs and weights can be assigned to edges/arcs of graphs/digraphs.

There is a draw_graph function for drawing graphs. Graphs are drawn using a force based vertex positioning algorithm. draw_graph can also use graphviz programs available from http://www.graphviz.org. draw_graph is based on the maxima draw package.

To use the graphs package, first load it with load("graphs").