> $p=rand_sphere(3,20);
> print $p->GRAPH->N_NODES;
20
Here ''%%GRAPH%%'' is a property of the polytope object ''%%$p%%'' which happens to be of the object type ''%%Graph%%''. The following is a fragment of the file ''%%apps/polytopes/rules/polytope_properties.rules%%''. This is where all the standard properties of polytopes are declared.
property GRAPH : Graph {
# Difference of the vertices for each edge (only defined up to signs).
property EDGE_DIRECTIONS : EdgeMap>;
}
In fact, this ''%%Graph%%'' is the main object class of another application, called ''%%graph%%''. This application ''%%graph%%'' is defined in ''%%apps/graph%%'' and its subdirectories. Although the application ''%%graph%%'' has much fewer features than the application ''%%polytope%%'' the overall mechanism of interaction is the same. In particular, there are properties, rules, clients, and such. Non-trivial features include the algorithm for computing the diameter and the visualization of graphs based on a pseudo-physical model (described in [[https://arxiv.org/abs/0711.2397|this paper]]).
> print $p->DIAMETER;
4
> $p->VISUAL;
declare object Graph {
# combinatorial description of the Graph in the form of adjacency matrix
property ADJACENCY : GraphAdjacency;
...
The key property of a graph object is its ''%%ADJACENCY%%''. For each node all neighbors are listed. Here we want to focus on the type ''%%GraphAdjacency%%'' of this property. This refers to C++ class from the Polymake Template Library named ''%%Graph%%'', and this is where the data structure and most algorithms reside. It is possible to directly manipulate objects of this type, and these are //not// immutable, they can be changed. The following shows how one can create a 5-cycle. Calling the method ''%%edge%%'' creates an edge if it did not exist before. The output is the ordered list of neighbors per node.
> $g=new GraphAdjacency(5);
> for (my $i=0; $i<5; ++$i) { $g->edge($i,($i+1)%5) };
> print $g;
{1 4}
{0 2}
{1 3}
{2 4}
{0 3}
If a graph has many nodes it is convenient to know which line of the output refers to which node. If an array of labels is given this could also be used instead of the numbers which are the default.
> print rows_labeled($g);
0:1 4
1:0 2
2:1 3
3:2 4
4:0 3
There are other ways to change such a graph. Contracting the edge //(x,y)// where //x// is smaller than //y// implies that the node //y// is destroyed.
> $g->delete_edge(0,1);
> $g->contract_edge(2,3);
> $g->squeeze();
However, most of our graph algorithms expect a graph with consecutively numbered nodes. The function ''%%squeeze%%'' takes care of a proper renumbering, but this takes linear time in the number of nodes.
> print rows_labeled($g);
0:3
1:2
2:1 3
3:0 2
How do I iterate over the adjacent nodes to a given node?
foreach (@{$g->adjacent_nodes(0)}) {
print "node number $_ is adjacent to node number 0\n";
}
It is also legal to copy all adjacent nodes to an array as in:
@x = @{$g->adjacent_nodes(0)};
Subsequently, the individial neighbors can be accessed, for instance, as ''%%$x[1]%%''. However, for technical reasons too difficult to explain here, it is //not// legal to write ''%%$g->adjacent_nodes(0)->[1]%%''! Usually it is preferred to avoid copying; so use constructions like ''%%foreach%%'' and ''%%map%%'' if possible.
===== Defining a Graph from Scratch =====
You can also work with graphs independent of their connection to polytopes. We will switch to ''%%application "graph"%%'' for the following commands, but this is not strictly necessary. We want to define a new object of type ''%%Graph%%'' in ''%%polymake%%''.
The key property of a graph is its adjacency matrix, which is stored in the property ''%%ADJACENCY%%''. It lists the neighbors of each node. We use again the above example of a 5-cycle C5 with consecutively numbered nodes. Then one can define C5 by
> application "graph";
> $g=new Graph(ADJACENCY=>[[1,4],[0,2],[1,3],[2,4],[0,3]]);
The list of edges of the graph is induced by the adjacency matrix (please note that in a undirected graph each edge appears twice). You can get an explicit list of the edges with the user function ''%%EDGES%%''.
> print $g->EDGES;
{0 1}
{1 2}
{2 3}
{0 4}
{3 4}
Note however, that this list is not stored in the object, as it is just a different view on the adjacency matrix.
Most often when you define a graph you would not write it down as a list of adjacencies, but as a list of edges. For convenience, ''%%polymake%%'' provides a way to create a graph from a list of edges. The same 5-cycle as above could also be defined via
> $g=graph_from_edges([[0,1],[1,2],[2,3],[0,4],[3,4]]);
The order of the edges, and the order of the nodes for each edge in a undirected case, is not important. We can check the adjacency matrix,
> print $g->ADJACENCY;
{1 4}
{0 2}
{1 3}
{2 4}
{0 3}
and continue to work with the graph by e.g. checking its ''%%DIAMETER%%'', ''%%BIPARTITE%%''-ness or other properties:
> print $g->DIAMETER;
2
> print $g->BIPARTITE;
false
> print $g->MAX_CLIQUES;
{{0 1} {0 4} {1 2} {2 3} {3 4}}
===== Directed Graphs =====
By specifying the template parameter ''%%Directed%%'' a graph is born as a directed graph. Properties which make sense for directed graphs work as expected. A directed graph may have two arcs between any two nodes with opposite orientations.
> $g=new Graph(ADJACENCY=>[[1],[2],[3],[2,4],[0]]);
> print $g->DIAMETER;
4
Some properties of graphs do not make sense for directed graph. Here is an example of an undirected graph property which does not make sense for directed graphs.
> #print $g->MAX_CLIQUES;
polymake: ERROR: Object Graph does not have a property or method MAX_CLIQUES
Graphs with multiple edges/arcs are currently not supported.
===== Visualizing Graphs =====
Like other "big" ''%%polymake%%'' objects the ''%%Graph%%'' class has a member (function) ''%%VISUAL%%'' which returns an abstract visualization object. Depending on the configuration it typically uses ''%%JReality%%'' or ''%%JavaView%%''. Particularly interesting for graph drawing is the visualization via ''%%Graphviz%%''.
> svg($g->VISUAL);
> graphviz($g->VISUAL);
{{ tutorials:release:4.6:apps_graph:output_0.svg }}
Note that the latter starts a postscript viewer with the ''%%Graphviz%%'' output. Make sure that the custom variable ''%%$Postscript::viewer%%'' is set to something reasonable (like, e.g., ''%%/usr/bin/evince%%'').