documentation:release:3.5:graph:graph

Available versions of this document: latest release, release 4.12, release 4.11, release 4.10, release 4.9, release 4.8, release 4.7, release 4.6, release 4.5, release 4.4, release 4.3, release 4.2, release 4.1, release 4.0, release 3.6, release 3.5, nightly master

Reference documentation for older polymake versions: release 3.4, release 3.3, release 3.2

# BigObject Graph<Dir>

from application graph

A graph with optional node and edge attributes.

Type Parameters:

Dir: tag describing the kind of the graph: Directed, Undirected, DirectedMulti, or UndirectedMulti.

Specializations:

Graph<Directed>: Unnamed full specialization of Graph

Graph<Undirected>: Unnamed full specialization of Graph

Permutations:
NodePerm:

permutation of nodes

ADJACENCY

combinatorial description of the Graph in the form of adjacency matrix

Type:
Graph<Dir>
Example:

This prints the adjacency matrix of the complete graph of three nodes, whereby the i-th node is connected to the nodes shown in the i-th row:

 > print complete(3)->ADJACENCY;
{1 2}
{0 2}
{0 1}

AVERAGE_DEGREE

The average degree of a node

Type:
Rational
Example:

The following prints the average degree of a node for the complete bipartite graph with 1 and 3 nodes:

 > print complete_bipartite(1,3)->AVERAGE_DEGREE;
3/2

BICONNECTED_COMPONENTS

Biconnected components. Every row contains nodes from a single component. Articulation nodes may occur in several rows.

Type:
IncidenceMatrix<NonSymmetric>
Example:

The following prints the biconnected components of two triangles having a single common node:

 > $g = new Graph<Undirected>(ADJACENCY=>[[1,2],[0,2],[0,1,3,4],[2,4],[2,3]]); > print$g->BICONNECTED_COMPONENTS;
{2 3 4}
{0 1 2}

BIPARTITE

True if the graph is a bipartite.

Type:
Bool
Example:

The following checks if a square (as a graph) is bipartite:

 > $g = new Graph<Undirected>(ADJACENCY=>[[1,3],[0,2],[1,3],[0,2]]); > print$g->BIPARTITE;
true

CHARACTERISTIC_POLYNOMIAL

Characteristic polynomial of the adjacency matrix; its roots are the eigenvalues

Type:
UniPolynomial<Rational,Int>
Example:

The following prints the characteristic polynomial of a complete graph with three nodes:

 > print complete(3)->CHARACTERISTIC_POLYNOMIAL
x^3 -3*x -2

CONNECTED

True if the graph is a connected graph.

Type:
Bool
Example:

The following checks whether a graph is connected or not. A single edge with its endpoints is obviously connected. We construct the adjacency matrix beforehand:

 > $IM = new IncidenceMatrix<Symmetric>([[1],[0]]); > print new Graph(ADJACENCY=>$IM)->CONNECTED;
true

The same procedure yields the opposite outcome after adding an isolated node:

 > $IM = new IncidenceMatrix<Symmetric>([[1],[0],[]]); > print new Graph(ADJACENCY=>$IM)->CONNECTED;
false

CONNECTED_COMPONENTS

The connected components. Every row contains nodes from a single component.

Type:
IncidenceMatrix<NonSymmetric>
Example:

The following prints the connected components of two seperate triangles:

 > $g = new Graph<Undirected>(ADJACENCY=>[[1,2],[0,2],[0,1],[4,5],[3,5],[3,4]]); > print$g->CONNECTED_COMPONENTS;
{0 1 2}
{3 4 5}

CONNECTIVITY

Node connectivity of the graph, that is, the minimal number of nodes to be removed from the graph such that the result is disconnected.

Type:
Int
Example:

The following prints the connectivity of the complete bipartite graph of 2 and 4 nodes:

 > print complete_bipartite(2,4)->CONNECTIVITY;
2

DEGREE_SEQUENCE

How many times a node of a given degree occurs

Type:
Map<Int,Int>
Example:

The following prints how often each degree of a node in the complete bipartite graph with 1 and 3 nodes occurs, whereby the first entry of a tuple represents the degree:

 > print complete_bipartite(1,3)->DEGREE_SEQUENCE;
{(1 3) (3 1)}

DIAMETER

The diameter of the graph.

Type:
Int
Example:

This prints the diameter of the complete bipartite graph of 1 and 3 nodes:

 > print complete_bipartite(1,3)->NODE_DEGREES;
3 1 1 1

EIGENVALUES_LAPLACIAN

eigenvalues of the discrete laplacian operator of a graph

Type:
Vector<Float>
Example:

The following prints the eigenvalues of the discrete laplacian operator of the complete graph with 3 nodes:

 > print complete(3)->EIGENVALUES_LAPLACIAN
3 -3 0

MAX_CLIQUES

The maximal cliques of the graph, encoded as node sets.

Type:
PowerSet<Int>
Example:

The following prints the maximal cliques of two complete graphs with 3 nodes being connected by a single edge:

 > $g = new Graph<Undirected>(ADJACENCY=>[[1,2],[0,2],[0,1,3],[2,4,5],[3,5],[3,4]]); > print$g->MAX_CLIQUES;
{{0 1 2} {2 3} {3 4 5}}

NODE_DEGREES

Degrees of nodes in the graph.

Type:
Array<Int>
Example:

This prints the node degrees of the complete bipartite graph of 1 and 3 nodes:

 > print complete_bipartite(1,3)->NODE_DEGREES;
3 1 1 1

NODE_IN_DEGREES

The number of incoming edges of the graph nodes.

Type:
Array<Int>
Example:

To print the number of incoming edges of a directed version of the complete graph with 3 nodes, type this:

 > $g = new Graph<Directed>(ADJACENCY=>[[1,2],[2],[]]); > print$g->NODE_IN_DEGREES;
0 1 2

NODE_LABELS

Labels of the nodes of the graph.

Type:
Array<String>
Example:

The following prints the node labels of the generalized_johnson_graph with parameters (4,2,1):

 > print generalized_johnson_graph(4,2,1)->NODE_LABELS;
{0 1} {0 2} {0 3} {1 2} {1 3} {2 3}

NODE_OUT_DEGREES

The number of outgoing edges of the graph nodes.

Type:
Array<Int>
Example:

To print the number of incoming edges of a directed version of the complete graph with 3 nodes, type this:

 > $g = new Graph<Directed>(ADJACENCY=>[[1,2],[2],[]]); > print$g->NODE_OUT_DEGREES;
2 1 0

N_CONNECTED_COMPONENTS

Number of CONNECTED_COMPONENTS of the graph.

Type:
Int
Example:

The following prints the number of connected components of two seperate triangles:

 > $g = new Graph<Undirected>(ADJACENCY=>[[1,2],[0,2],[0,1],[4,5],[3,5],[3,4]]); > print$g->N_CONNECTED_COMPONENTS;
2

N_EDGES

Number of EDGES of the graph.

Type:
Int
Example:

This prints the number of edges of the complete graph of 4 nodes (which is 4 choose 2):

 > print complete(4)->N_EDGES;
6

N_NODES

Number of nodes of the graph.

Type:
Int
Example:

This prints the number of nodes of the complete bipartite graph of 1 and 3 nodes (which is the sum of the nodes in each partition):

 > print complete_bipartite(1,3)->N_NODES;
4

SIGNATURE

Difference of the black and white nodes if the graph is BIPARTITE. Otherwise -1.

Type:
Int
Example:

The following prints the signature of the complete bipartite graph with 2 and 7 nodes:

 > print complete_bipartite(2,7)->SIGNATURE;
5

SIGNED_INCIDENCE_MATRIX

Signed vertex-edge incidence matrix; for undirected graphs, the orientation comes from the lexicographic order of the nodes.

Type:
SparseMatrix<Int,NonSymmetric>
Example:

The following prints the signed incidence matrix of the cylcic graph with 4 nodes:

 > print cycle_graph(4)->SIGNED_INCIDENCE_MATRIX;
1 0 1 0
-1 1 0 0
0 -1 0 1
0 0 -1 -1

STRONGLY_CONNECTED

True if the graph is strongly connected

Type:
Bool
Example:

The following checks a graph for strong connectivity. First we construct a graph with 4 nodes consisting of two directed circles, which are connected by a single directed edge. We then and check the property:

 > $g = new Graph<Directed>(ADJACENCY=>[[1],[0,2],[3],[2]]); > print$g->STRONGLY_CONNECTED;
false

The same procedure yields the opposite result for the graph with the reversed edge added in the middle:

 > $g = new Graph<Directed>(ADJACENCY=>[[1],[0,2],[1,3],[2]]); > print$g->STRONGLY_CONNECTED;
true

STRONG_COMPONENTS

Strong components. Every row contains nodes from a single component

Type:
IncidenceMatrix<NonSymmetric>
Example:

To print the strong connected components of a graph with 4 nodes consisting of two directed circles and which are connected by a single directed edge, type this:

 > $g = new Graph<Directed>(ADJACENCY=>[[1],[0,2],[3],[2]]); > print$g->STRONG_COMPONENTS;
{2 3}
{0 1}

TRIANGLE_FREE

Determine whether the graph has triangles or not.

Type:
Bool
Example:

The following checks if the petersen graph contains triangles:

 > print petersen()->TRIANGLE_FREE;
true

WEAKLY_CONNECTED

True if the graph is weakly connected

Type:
Bool
Example:

The following checks a graph for weak connectivity. First we construct a graph with 4 nodes consisting of two directed circles, which are connected by a single directed edge. We then check the property:

 > $g = new Graph<Directed>(ADJACENCY=>[[1],[0,2],[3],[2]]); > print$g->WEAKLY_CONNECTED;
true

WEAKLY_CONNECTED_COMPONENTS

Weakly connected components. Every row contains nodes from a single component

Type:
IncidenceMatrix<NonSymmetric>
Example:

To print the weakly connected components of a graph with 4 nodes consisting of two directed circles, which are connected by a single directed edge, type this:

 > $g = new Graph<Directed>(ADJACENCY=>[[1],[0,2],[3],[2]]); > print$g->WEAKLY_CONNECTED_COMPONENTS;
{0 1 2 3}

The same procedure yields the opposite outcome using the same graph without the linking edge between the two circles:

 > $g = new Graph<Directed>(ADJACENCY=>[[1],[0],[3],[2]]); > print$g->WEAKLY_CONNECTED_COMPONENTS;
{0 1}
{2 3}

These methods capture combinatorial information of the object. Combinatorial properties only depend on combinatorial data of the object like, e.g., the face lattice.

EDGES()

Explore the graph as a sequence of its edges.

Returns:
Array<Set<Int>>

These methods are for visualization.

VISUAL()

Visualizes the graph. Decorations may include Coord, disabling the default spring embedder.

Options:

Int seed: random seed value for the spring embedder

option list Visual::Graph::decorations
Returns:
Visual::Graph
Example:

The following visualizes the petersen graph with default settings:

 > petersen()->VISUAL;

The following shows some modified visualization style of the same graph:

 > petersen()->VISUAL(NodeColor=>"green",NodeThickness=>6,EdgeColor=>"purple",EdgeThickness=>4);

• documentation/release/3.5/graph/graph.txt