# Differences

This shows you the differences between two versions of the page.

 documentation:latest:graph:graph [2019/08/13 10:31] documentation:latest:graph:graph [2019/11/15 22:01] (current) Line 1: Line 1: + ====== BigObject Graph<​Dir>​ ====== + //from application [[..:​graph|graph]]//​\\ + \\ + A graph with optional node and edge attributes. + + ? Type Parameters: + :: ''​Dir'':​ tag describing the kind of the graph: ''​[[..:​common#​Directed |Directed]]'',​ ''​[[..:​common#​Undirected |Undirected]]'',​ ''​[[..:​common#​DirectedMulti |DirectedMulti]]'',​ or ''​[[..:​common#​UndirectedMulti |UndirectedMulti]]''​. + ? Specializations:​ + :: ''​Graph<​Directed>'':​ Unnamed full specialization of Graph + :: ''​Graph<​Undirected>'':​ Unnamed full specialization of Graph + ? Permutations:​ + : + ? NodePerm: + :: permutation of nodes + ===== Properties ===== + + ==== no category ==== + {{anchor:​adjacency:​}} + ?  **''​ADJACENCY''​** + :: combinatorial description of the Graph in the form of adjacency matrix + ? Type: + :''​[[..:​common#​Graph |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} + ​ + + + ---- + {{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<​Undirected>​(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<​Undirected>​(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<​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 + ​ + + + ---- + {{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 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} + ​ + + + ---- + {{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#​PowerSet |PowerSet]]<​[[..:​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<​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}} + ​ + + + ---- + {{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<​Directed>​(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<​Directed>​(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 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 + ​ + + + ---- + {{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<​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 + ​ + + + ---- + {{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<​Directed>​(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<​Directed>​(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<​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. + ---- + {{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);​ + ​ + + + ----