documentation:latest:graph:graph

Differences

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


documentation:latest:graph:graph [2023/11/06 10:57] (current) – created - external edit 127.0.0.1
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#GraphAdjacency |GraphAdjacency]]<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 separate 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#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:
 +    :: <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: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:
 +    :: <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 separate  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>
 +
 +
 +----
  
  • documentation/latest/graph/graph.txt
  • Last modified: 2023/11/06 10:57
  • by 127.0.0.1