Differences

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

Link to this comparison view

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:
 +    :: <code perl> > print complete(3)->​ADJACENCY;​
 + {1 2}
 + {0 2}
 + {0 1}
 +</​code>​
 +
 +
 +----
 +{{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:
 +    :: <code perl> > print complete_bipartite(1,​3)->​AVERAGE_DEGREE;​
 + 3/2
 +</​code>​
 +
 +
 +----
 +{{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: 
 +    :: <code perl> > $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}
 +</​code>​
 +
 +
 +----
 +{{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:
 +    :: <code perl> > $g = new Graph<​Undirected>​(ADJACENCY=>​[[1,​3],​[0,​2],​[1,​3],​[0,​2]]);​
 + > print $g->​BIPARTITE;​
 + true
 +</​code>​
 +
 +
 +----
 +{{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:
 +    :: <code perl> > print complete(3)->​CHARACTERISTIC_POLYNOMIAL
 + x^3 -3*x -2
 +</​code>​
 +
 +
 +----
 +{{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:
 +    :: <code perl> > $IM = new IncidenceMatrix<​Symmetric>​([[1],​[0]]);​
 + > print new Graph(ADJACENCY=>​$IM)->​CONNECTED; ​     ​
 + true
 +</​code>​
 +    ::  The same procedure yields the opposite outcome after adding an isolated node:
 +    :: <code perl> > $IM = new IncidenceMatrix<​Symmetric>​([[1],​[0],​[]]);​
 + > print new Graph(ADJACENCY=>​$IM)->​CONNECTED; ​     ​
 + false
 +</​code>​
 +
 +
 +----
 +{{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:
 +    :: <code perl> > $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}
 +</​code>​
 +
 +
 +----
 +{{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:
 +    :: <code perl> > print complete_bipartite(2,​4)->​CONNECTIVITY;​
 + 2
 +</​code>​
 +
 +
 +----
 +{{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:
 +    :: <code perl> > print complete_bipartite(1,​3)->​DEGREE_SEQUENCE;​
 + {(1 3) (3 1)}
 +</​code>​
 +
 +
 +----
 +{{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:
 +    :: <code perl> > print complete_bipartite(1,​3)->​NODE_DEGREES;​
 + 3 1 1 1
 +</​code>​
 +
 +
 +----
 +{{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:
 +    :: <code perl> > print complete(3)->​EIGENVALUES_LAPLACIAN
 + 3 -3 0
 +</​code>​
 +
 +
 +----
 +{{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:
 +    :: <code perl> > $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}}
 +</​code>​
 +
 +
 +----
 +{{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:
 +    :: <code perl> > print complete_bipartite(1,​3)->​NODE_DEGREES;​
 + 3 1 1 1
 +</​code>​
 +
 +
 +----
 +{{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:
 +    :: <code perl> > $g = new Graph<​Directed>​(ADJACENCY=>​[[1,​2],​[2],​[]]);​
 + > print $g->​NODE_IN_DEGREES;​
 + 0 1 2
 +</​code>​
 +
 +
 +----
 +{{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):
 +    :: <code perl> > print generalized_johnson_graph(4,​2,​1)->​NODE_LABELS;​
 + {0 1} {0 2} {0 3} {1 2} {1 3} {2 3}
 +</​code>​
 +
 +
 +----
 +{{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:
 +    :: <code perl> > $g = new Graph<​Directed>​(ADJACENCY=>​[[1,​2],​[2],​[]]);​
 + > print $g->​NODE_OUT_DEGREES;​
 + 2 1 0
 +</​code>​
 +
 +
 +----
 +{{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:
 +    :: <code perl> > $g = new Graph<​Undirected>​(ADJACENCY=>​[[1,​2],​[0,​2],​[0,​1],​[4,​5],​[3,​5],​[3,​4]]);​
 + > print $g->​N_CONNECTED_COMPONENTS;​
 + 2
 +</​code>​
 +
 +
 +----
 +{{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):
 +    :: <code perl> > print complete(4)->​N_EDGES;​
 + 6
 +</​code>​
 +
 +
 +----
 +{{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):
 +    :: <code perl> > print complete_bipartite(1,​3)->​N_NODES;​
 + 4
 +</​code>​
 +
 +
 +----
 +{{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:
 +    :: <code perl> > print complete_bipartite(2,​7)->​SIGNATURE;​
 + 5
 +</​code>​
 +
 +
 +----
 +{{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:
 +    :: <code perl> > print cycle_graph(4)->​SIGNED_INCIDENCE_MATRIX;​
 + 1 0 1 0
 + -1 1 0 0
 + 0 -1 0 1
 + 0 0 -1 -1
 +</​code>​
 +
 +
 +----
 +{{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:
 +    :: <code perl> > $g = new Graph<​Directed>​(ADJACENCY=>​[[1],​[0,​2],​[3],​[2]]);​
 + > print $g->​STRONGLY_CONNECTED;​
 + false
 +</​code>​
 +    ::  The same procedure yields the opposite result for the graph with the reversed edge added in the middle: ​
 +    :: <code perl> > $g = new Graph<​Directed>​(ADJACENCY=>​[[1],​[0,​2],​[1,​3],​[2]]);​
 + > print $g->​STRONGLY_CONNECTED;​
 + true
 +</​code>​
 +
 +
 +----
 +{{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:
 +    :: <code perl> > $g = new Graph<​Directed>​(ADJACENCY=>​[[1],​[0,​2],​[3],​[2]]);​
 + > print $g->​STRONG_COMPONENTS;​
 + {2 3}
 + {0 1}
 +</​code>​
 +
 +
 +----
 +{{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:
 +    :: <code perl> > print petersen()->​TRIANGLE_FREE;​
 + true
 +</​code>​
 +
 +
 +----
 +{{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:
 +    :: <code perl> > $g = new Graph<​Directed>​(ADJACENCY=>​[[1],​[0,​2],​[3],​[2]]);​
 + > print $g->​WEAKLY_CONNECTED;​
 + true
 +</​code>​
 +
 +
 +----
 +{{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:
 +    :: <code perl> > $g = new Graph<​Directed>​(ADJACENCY=>​[[1],​[0,​2],​[3],​[2]]);​
 + > print $g->​WEAKLY_CONNECTED_COMPONENTS;​
 + {0 1 2 3}
 +</​code>​
 +    ::  The same procedure yields the opposite outcome using the same graph without the linking edge between the two circles:
 +    :: <code perl> > $g = new Graph<​Directed>​(ADJACENCY=>​[[1],​[0],​[3],​[2]]);​
 + > print $g->​WEAKLY_CONNECTED_COMPONENTS;​
 + {0 1}
 + {2 3}
 +</​code>​
 +
 +
 +----
 +===== 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:
 +    :: <code perl> > petersen()->​VISUAL;​
 +</​code>​
 +    ::  The following shows some modified visualization style of the same graph:
 +    :: <code perl> > petersen()->​VISUAL(NodeColor=>"​green",​NodeThickness=>​6,​EdgeColor=>"​purple",​EdgeThickness=>​4);​
 +</​code>​
 +
 +
 +----