====== BigObject Graph
> print complete(3)->ADJACENCY;
{1 2}
{0 2}
{0 1}
----
{{anchor:average_degree:}}
? **''AVERAGE_DEGREE''**
:: The average degree of a node
? Type:
:''[[..:common#Rational |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
----
{{anchor:biconnected_components:}}
? **''BICONNECTED_COMPONENTS''**
:: Biconnected components. Every row contains nodes from a single component. Articulation nodes may occur in several rows.
? Type:
:''[[..:common#IncidenceMatrix |IncidenceMatrix]]<[[..:common#NonSymmetric |NonSymmetric]]>''
? Example:
:: The following prints the biconnected components of two triangles having a single common node:
:: > $g = new Graph(ADJACENCY=>[[1,2],[0,2],[0,1,3,4],[2,4],[2,3]]);
> print $g->BICONNECTED_COMPONENTS;
{2 3 4}
{0 1 2}
----
{{anchor:bipartite:}}
? **''BIPARTITE''**
:: True if the graph is a bipartite.
? Type:
:''[[..:common#Bool |Bool]]''
? Example:
:: The following checks if a square (as a graph) is bipartite:
:: > $g = new Graph(ADJACENCY=>[[1,3],[0,2],[1,3],[0,2]]);
> print $g->BIPARTITE;
true
----
{{anchor:characteristic_polynomial:}}
? **''CHARACTERISTIC_POLYNOMIAL''**
:: Characteristic polynomial of the adjacency matrix; its roots are the eigenvalues
? Type:
:''[[..:common#UniPolynomial |UniPolynomial]]<[[..:common#Rational |Rational]],[[..:common#Int |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
----
{{anchor:connected:}}
? **''CONNECTED''**
:: True if the graph is a connected graph.
? Type:
:''[[..:common#Bool |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([[1],[0]]);
> print new Graph(ADJACENCY=>$IM)->CONNECTED;
true
:: The same procedure yields the opposite outcome after adding an isolated node:
:: > $IM = new IncidenceMatrix([[1],[0],[]]);
> print new Graph(ADJACENCY=>$IM)->CONNECTED;
false
----
{{anchor:connected_components:}}
? **''CONNECTED_COMPONENTS''**
:: The connected components. Every row contains nodes from a single component.
? Type:
:''[[..:common#IncidenceMatrix |IncidenceMatrix]]<[[..:common#NonSymmetric |NonSymmetric]]>''
? Example:
:: The following prints the connected components of two separate triangles:
:: > $g = new Graph(ADJACENCY=>[[1,2],[0,2],[0,1],[4,5],[3,5],[3,4]]);
> print $g->CONNECTED_COMPONENTS;
{0 1 2}
{3 4 5}
----
{{anchor:connectivity:}}
? **''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:
:''[[..:common#Int |Int]]''
? Example:
:: The following prints the connectivity of the complete bipartite graph of 2 and 4 nodes:
:: > print complete_bipartite(2,4)->CONNECTIVITY;
2
----
{{anchor:degree_sequence:}}
? **''DEGREE_SEQUENCE''**
:: How many times a node of a given degree occurs
? Type:
:''[[..:common#Map |Map]]<[[..:common#Int |Int]],[[..:common#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)}
----
{{anchor:diameter:}}
? **''DIAMETER''**
:: The diameter of the graph.
? Type:
:''[[..:common#Int |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
----
{{anchor:eigenvalues_laplacian:}}
? **''EIGENVALUES_LAPLACIAN''**
:: eigenvalues of the discrete laplacian operator of a graph
? Type:
:''[[..:common#Vector |Vector]]<[[..:common#Float |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
----
{{anchor:max_cliques:}}
? **''MAX_CLIQUES''**
:: The maximal cliques of the graph, encoded as node sets.
? Type:
:''[[..:common#Set |Set]]<[[..:common#Set |Set]]<[[..:common#Int |Int]]%%>>%%''
? Example:
:: The following prints the maximal cliques of two complete graphs with 3 nodes being connected by a single edge:
:: > $g = new Graph(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}}
----
{{anchor:max_independent_sets:}}
? **''MAX_INDEPENDENT_SETS''**
:: The maximal independent sets of the graph, encoded as node sets.
? Type:
:''[[..:common#Set |Set]]<[[..:common#Set |Set]]<[[..:common#Int |Int]]%%>>%%''
----
{{anchor:node_degrees:}}
? **''NODE_DEGREES''**
:: Degrees of nodes in the graph.
? Type:
:''[[..:common#Array |Array]]<[[..:common#Int |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
----
{{anchor:node_in_degrees:}}
? **''NODE_IN_DEGREES''**
:: The number of incoming edges of the graph nodes.
? Type:
:''[[..:common#Array |Array]]<[[..:common#Int |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(ADJACENCY=>[[1,2],[2],[]]);
> print $g->NODE_IN_DEGREES;
0 1 2
----
{{anchor:node_labels:}}
? **''NODE_LABELS''**
:: Labels of the nodes of the graph.
? Type:
:''[[..:common#Array |Array]]<[[..:common#String |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}
----
{{anchor:node_out_degrees:}}
? **''NODE_OUT_DEGREES''**
:: The number of outgoing edges of the graph nodes.
? Type:
:''[[..:common#Array |Array]]<[[..:common#Int |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(ADJACENCY=>[[1,2],[2],[]]);
> print $g->NODE_OUT_DEGREES;
2 1 0
----
{{anchor:n_connected_components:}}
? **''N_CONNECTED_COMPONENTS''**
:: Number of ''[[..:graph:Graph#CONNECTED_COMPONENTS |CONNECTED_COMPONENTS]]'' of the graph.
? Type:
:''[[..:common#Int |Int]]''
? Example:
:: The following prints the number of connected components of two separate triangles:
:: > $g = new Graph(ADJACENCY=>[[1,2],[0,2],[0,1],[4,5],[3,5],[3,4]]);
> print $g->N_CONNECTED_COMPONENTS;
2
----
{{anchor:n_edges:}}
? **''N_EDGES''**
:: Number of ''[[..:graph:Graph#EDGES |EDGES]]'' of the graph.
? Type:
:''[[..:common#Int |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
----
{{anchor:n_nodes:}}
? **''N_NODES''**
:: Number of nodes of the graph.
? Type:
:''[[..:common#Int |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
----
{{anchor:signature:}}
? **''SIGNATURE''**
:: Difference of the black and white nodes if the graph is ''[[..:graph:Graph#BIPARTITE |BIPARTITE]]''. Otherwise -1.
? Type:
:''[[..:common#Int |Int]]''
? Example:
:: The following prints the signature of the complete bipartite graph with 2 and 7 nodes:
:: > print complete_bipartite(2,7)->SIGNATURE;
5
----
{{anchor:signed_incidence_matrix:}}
? **''SIGNED_INCIDENCE_MATRIX''**
:: Signed vertex-edge incidence matrix; for undirected graphs, the orientation comes from the lexicographic order of the nodes.
? Type:
:''[[..:common#SparseMatrix |SparseMatrix]]<[[..:common#Int |Int]],[[..:common#NonSymmetric |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
----
{{anchor:strongly_connected:}}
? **''STRONGLY_CONNECTED''**
:: True if the graph is strongly connected
? Type:
:''[[..:common#Bool |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(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(ADJACENCY=>[[1],[0,2],[1,3],[2]]);
> print $g->STRONGLY_CONNECTED;
true
----
{{anchor:strong_components:}}
? **''STRONG_COMPONENTS''**
:: Strong components. Every row contains nodes from a single component
? Type:
:''[[..:common#IncidenceMatrix |IncidenceMatrix]]<[[..:common#NonSymmetric |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(ADJACENCY=>[[1],[0,2],[3],[2]]);
> print $g->STRONG_COMPONENTS;
{2 3}
{0 1}
----
{{anchor:triangle_free:}}
? **''TRIANGLE_FREE''**
:: Determine whether the graph has triangles or not.
? Type:
:''[[..:common#Bool |Bool]]''
? Example:
:: The following checks if the petersen graph contains triangles:
:: > print petersen()->TRIANGLE_FREE;
true
----
{{anchor:weakly_connected:}}
? **''WEAKLY_CONNECTED''**
:: True if the graph is weakly connected
? Type:
:''[[..:common#Bool |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(ADJACENCY=>[[1],[0,2],[3],[2]]);
> print $g->WEAKLY_CONNECTED;
true
----
{{anchor:weakly_connected_components:}}
? **''WEAKLY_CONNECTED_COMPONENTS''**
:: Weakly connected components. Every row contains nodes from a single component
? Type:
:''[[..:common#IncidenceMatrix |IncidenceMatrix]]<[[..:common#NonSymmetric |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(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(ADJACENCY=>[[1],[0],[3],[2]]);
> print $g->WEAKLY_CONNECTED_COMPONENTS;
{0 1}
{2 3}
----
===== Methods =====
==== Combinatorics ====
These methods capture combinatorial information of the object. Combinatorial properties only depend on combinatorial data of the object like, e.g., the face lattice.
----
{{anchor:edges:}}
? **''EDGES()''**
:: Explore the graph as a sequence of its edges.
? Returns:
:''[[..:common#Array |Array]]<[[..:common#Set |Set]]<[[..:common#Int |Int]]%%>>%%''
----
==== Visualization ====
These methods are for visualization.
----
{{anchor:visual:}}
? **''VISUAL()''**
:: Visualizes the graph. Decorations may include ''Coord'', disabling the default spring embedder.
? Options:
:
:: ''[[..:common#Int |Int]]'' ''seed'': random seed value for the spring embedder
: option list ''[[..:graph#Visual_Graph_decorations |Visual::Graph::decorations]]''
? Returns:
:''[[..:graph:Visual_Graph |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);
----