no way to compare when less than two revisions
Differences
This shows you the differences between two versions of the page.
— | documentation:release:3.5:graph:graph [2019/08/13 10:31] (current) – created - external edit 127.0.0.1 | ||
---|---|---|---|
Line 1: | Line 1: | ||
+ | ====== BigObject Graph< | ||
+ | //from application [[..: | ||
+ | \\ | ||
+ | A graph with optional node and edge attributes. | ||
+ | |||
+ | ? Type Parameters: | ||
+ | :: '' | ||
+ | ? Specializations: | ||
+ | :: '' | ||
+ | :: '' | ||
+ | ? Permutations: | ||
+ | : | ||
+ | ? NodePerm: | ||
+ | :: permutation of nodes | ||
+ | ===== Properties ===== | ||
+ | |||
+ | ==== no category ==== | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: combinatorial description of the Graph in the form of adjacency matrix | ||
+ | ? Type: | ||
+ | :'' | ||
+ | ? 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)-> | ||
+ | {1 2} | ||
+ | {0 2} | ||
+ | {0 1} | ||
+ | </ | ||
+ | |||
+ | |||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: 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: | ||
+ | :: <code perl> > print complete_bipartite(1, | ||
+ | 3/2 | ||
+ | </ | ||
+ | |||
+ | |||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: 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: | ||
+ | :: <code perl> > $g = new Graph< | ||
+ | > print $g-> | ||
+ | {2 3 4} | ||
+ | {0 1 2} | ||
+ | </ | ||
+ | |||
+ | |||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: True if the graph is a bipartite. | ||
+ | ? Type: | ||
+ | :'' | ||
+ | ? Example: | ||
+ | :: The following checks if a square (as a graph) is bipartite: | ||
+ | :: <code perl> > $g = new Graph< | ||
+ | > print $g-> | ||
+ | true | ||
+ | </ | ||
+ | |||
+ | |||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: 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: | ||
+ | :: <code perl> > print complete(3)-> | ||
+ | x^3 -3*x -2 | ||
+ | </ | ||
+ | |||
+ | |||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: 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: | ||
+ | :: <code perl> > $IM = new IncidenceMatrix< | ||
+ | > print new Graph(ADJACENCY=> | ||
+ | true | ||
+ | </ | ||
+ | :: The same procedure yields the opposite outcome after adding an isolated node: | ||
+ | :: <code perl> > $IM = new IncidenceMatrix< | ||
+ | > print new Graph(ADJACENCY=> | ||
+ | false | ||
+ | </ | ||
+ | |||
+ | |||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: The connected components. Every row contains nodes from a single component. | ||
+ | ? Type: | ||
+ | :'' | ||
+ | ? Example: | ||
+ | :: The following prints the connected components of two seperate triangles: | ||
+ | :: <code perl> > $g = new Graph< | ||
+ | > print $g-> | ||
+ | {0 1 2} | ||
+ | {3 4 5} | ||
+ | </ | ||
+ | |||
+ | |||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: 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: | ||
+ | :: <code perl> > print complete_bipartite(2, | ||
+ | 2 | ||
+ | </ | ||
+ | |||
+ | |||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: 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: | ||
+ | :: <code perl> > print complete_bipartite(1, | ||
+ | {(1 3) (3 1)} | ||
+ | </ | ||
+ | |||
+ | |||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: The diameter of the graph. | ||
+ | ? Type: | ||
+ | :'' | ||
+ | ? Example: | ||
+ | :: This prints the diameter of the complete bipartite graph of 1 and 3 nodes: | ||
+ | :: <code perl> > print complete_bipartite(1, | ||
+ | 3 1 1 1 | ||
+ | </ | ||
+ | |||
+ | |||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: 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: | ||
+ | :: <code perl> > print complete(3)-> | ||
+ | 3 -3 0 | ||
+ | </ | ||
+ | |||
+ | |||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: 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: | ||
+ | :: <code perl> > $g = new Graph< | ||
+ | > print $g-> | ||
+ | {{0 1 2} {2 3} {3 4 5}} | ||
+ | </ | ||
+ | |||
+ | |||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: Degrees of nodes in the graph. | ||
+ | ? Type: | ||
+ | :'' | ||
+ | ? Example: | ||
+ | :: This prints the node degrees of the complete bipartite graph of 1 and 3 nodes: | ||
+ | :: <code perl> > print complete_bipartite(1, | ||
+ | 3 1 1 1 | ||
+ | </ | ||
+ | |||
+ | |||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: 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: | ||
+ | :: <code perl> > $g = new Graph< | ||
+ | > print $g-> | ||
+ | 0 1 2 | ||
+ | </ | ||
+ | |||
+ | |||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: 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): | ||
+ | :: <code perl> > print generalized_johnson_graph(4, | ||
+ | {0 1} {0 2} {0 3} {1 2} {1 3} {2 3} | ||
+ | </ | ||
+ | |||
+ | |||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: 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: | ||
+ | :: <code perl> > $g = new Graph< | ||
+ | > print $g-> | ||
+ | 2 1 0 | ||
+ | </ | ||
+ | |||
+ | |||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: Number of '' | ||
+ | ? Type: | ||
+ | :'' | ||
+ | ? Example: | ||
+ | :: The following prints the number of connected components of two seperate | ||
+ | :: <code perl> > $g = new Graph< | ||
+ | > print $g-> | ||
+ | 2 | ||
+ | </ | ||
+ | |||
+ | |||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: Number of '' | ||
+ | ? Type: | ||
+ | :'' | ||
+ | ? Example: | ||
+ | :: This prints the number of edges of the complete graph of 4 nodes (which is 4 choose 2): | ||
+ | :: <code perl> > print complete(4)-> | ||
+ | 6 | ||
+ | </ | ||
+ | |||
+ | |||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: 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): | ||
+ | :: <code perl> > print complete_bipartite(1, | ||
+ | 4 | ||
+ | </ | ||
+ | |||
+ | |||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: Difference of the black and white nodes if the graph is '' | ||
+ | ? Type: | ||
+ | :'' | ||
+ | ? Example: | ||
+ | :: The following prints the signature of the complete bipartite graph with 2 and 7 nodes: | ||
+ | :: <code perl> > print complete_bipartite(2, | ||
+ | 5 | ||
+ | </ | ||
+ | |||
+ | |||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: 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: | ||
+ | :: <code perl> > print cycle_graph(4)-> | ||
+ | 1 0 1 0 | ||
+ | -1 1 0 0 | ||
+ | 0 -1 0 1 | ||
+ | 0 0 -1 -1 | ||
+ | </ | ||
+ | |||
+ | |||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: 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: | ||
+ | :: <code perl> > $g = new Graph< | ||
+ | > print $g-> | ||
+ | false | ||
+ | </ | ||
+ | :: The same procedure yields the opposite result for the graph with the reversed edge added in the middle: | ||
+ | :: <code perl> > $g = new Graph< | ||
+ | > print $g-> | ||
+ | true | ||
+ | </ | ||
+ | |||
+ | |||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: 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: | ||
+ | :: <code perl> > $g = new Graph< | ||
+ | > print $g-> | ||
+ | {2 3} | ||
+ | {0 1} | ||
+ | </ | ||
+ | |||
+ | |||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: Determine whether the graph has triangles or not. | ||
+ | ? Type: | ||
+ | :'' | ||
+ | ? Example: | ||
+ | :: The following checks if the petersen graph contains triangles: | ||
+ | :: <code perl> > print petersen()-> | ||
+ | true | ||
+ | </ | ||
+ | |||
+ | |||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: 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: | ||
+ | :: <code perl> > $g = new Graph< | ||
+ | > print $g-> | ||
+ | true | ||
+ | </ | ||
+ | |||
+ | |||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: 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: | ||
+ | :: <code perl> > $g = new Graph< | ||
+ | > print $g-> | ||
+ | {0 1 2 3} | ||
+ | </ | ||
+ | :: The same procedure yields the opposite outcome using the same graph without the linking edge between the two circles: | ||
+ | :: <code perl> > $g = new Graph< | ||
+ | > print $g-> | ||
+ | {0 1} | ||
+ | {2 3} | ||
+ | </ | ||
+ | |||
+ | |||
+ | ---- | ||
+ | ===== Methods ===== | ||
+ | |||
+ | ==== Combinatorics ==== | ||
+ | These methods capture combinatorial information of the object. | ||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: Explore the graph as a sequence of its edges. | ||
+ | ? Returns: | ||
+ | :'' | ||
+ | |||
+ | |||
+ | ---- | ||
+ | |||
+ | ==== Visualization ==== | ||
+ | These methods are for visualization. | ||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: Visualizes the graph. Decorations may include '' | ||
+ | ? Options: | ||
+ | : | ||
+ | :: '' | ||
+ | : option list '' | ||
+ | ? Returns: | ||
+ | :'' | ||
+ | ? Example: | ||
+ | :: The following visualizes the petersen graph with default settings: | ||
+ | :: <code perl> > petersen()-> | ||
+ | </ | ||
+ | :: The following shows some modified visualization style of the same graph: | ||
+ | :: <code perl> > petersen()-> | ||
+ | </ | ||
+ | |||
+ | |||
+ | ---- | ||