Available versions of this document: latest release, release 4.13, 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
, orUndirectedMulti
.- Specializations:
Graph<Directed>
: Unnamed full specialization of GraphGraph<Undirected>
: Unnamed full specialization of Graph- Permutations:
- NodePerm:
permutation of nodes
Properties
no category
-
ADJACENCY
combinatorial description of the Graph in the form of adjacency matrix
-
AVERAGE_DEGREE
The average degree of a node
- Type:
- 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:
- 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:
- 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:
- 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:
- 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:
- 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:
- 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:
- 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:
- 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:
- 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:
- 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:
- 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:
- 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:
- 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:
- 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:
- 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:
- 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:
- 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:
- 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:
- 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:
- 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:
- 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:
- 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:
- 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:
- 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}
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.
-
EDGES()
Explore the graph as a sequence of its edges.
- Returns:
Visualization
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:
- 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);