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:

GraphAdjacency<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);

---