from application graph
A graph with optional node and edge attributes.
Dir: tag describing the kind of the graph: Directed, Undirected, DirectedMulti, or UndirectedMulti.
Graph<Directed>: Unnamed full specialization of Graph
Graph<Undirected>: Unnamed full specialization of Graph
permutation of nodes
ADJACENCYcombinatorial description of the Graph in the form of adjacency matrix
GraphAdjacency<Dir>
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_DEGREEThe average degree of a node
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_COMPONENTSBiconnected components. Every row contains nodes from a single component. Articulation nodes may occur in several rows.
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}
BIPARTITETrue if the graph is a bipartite.
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_POLYNOMIALCharacteristic polynomial of the adjacency matrix; its roots are the eigenvalues
The following prints the characteristic polynomial of a complete graph with three nodes:
> print complete(3)->CHARACTERISTIC_POLYNOMIAL x^3 -3*x -2
CONNECTEDTrue if the graph is a connected graph.
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_COMPONENTSThe connected components. Every row contains nodes from a single component.
The following prints the connected components of two separate 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}
CONNECTIVITYNode connectivity of the graph, that is, the minimal number of nodes to be removed from the graph such that the result is disconnected.
The following prints the connectivity of the complete bipartite graph of 2 and 4 nodes:
> print complete_bipartite(2,4)->CONNECTIVITY; 2
DEGREE_SEQUENCEHow many times a node of a given degree occurs
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)}
DIAMETERThe diameter of the graph.
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_LAPLACIANeigenvalues of the discrete laplacian operator of a graph
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_CLIQUESThe maximal cliques of the graph, encoded as node sets.
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}}
MAX_INDEPENDENT_SETSThe maximal independent sets of the graph, encoded as node sets.
NODE_DEGREESDegrees of nodes in the graph.
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_DEGREESThe number of incoming edges of the graph nodes.
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_LABELSLabels of the nodes of the graph.
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_DEGREESThe number of outgoing edges of the graph nodes.
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.
The following prints the number of connected components of two separate 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.
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_NODESNumber of nodes of the graph.
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.
The following prints the signature of the complete bipartite graph with 2 and 7 nodes:
> print complete_bipartite(2,7)->SIGNATURE; 5
SIGNED_INCIDENCE_MATRIXSigned vertex-edge incidence matrix; for undirected graphs, the orientation comes from the lexicographic order of the nodes.
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_CONNECTEDTrue if the graph is strongly connected
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_COMPONENTSStrong components. Every row contains nodes from a single component
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_FREEDetermine whether the graph has triangles or not.
The following checks if the petersen graph contains triangles:
> print petersen()->TRIANGLE_FREE; true
WEAKLY_CONNECTEDTrue if the graph is weakly connected
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_COMPONENTSWeakly connected components. Every row contains nodes from a single component
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.
These methods are for visualization.
VISUAL()
Visualizes the graph. Decorations may include Coord, disabling the default spring embedder.
Int seed: random seed value for the spring embedder
Visual::Graph::decorations
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);