SimpleGraph.pl - Tools for displaying and manipulating simple graphs from graph theory.
The core of this macro is the GraphTheory::SimpleGraph object which represents simple graphs from graph theory via an adjacency matrix.
The following functions can be used to construct a GraphTheory::SimpleGraph object.
$graph = SimpleGraph($definition, %options);This is an alias for the GraphTheory::SimpleGraph constructor.
The $definition argument is required and can be the number of vertices in the graph, another GraphTheory::SimpleGraph object, a reference to an array of arrays of numbers, a reference to a MathObject Matrix, a reference to an array of arrays containing two strings and possibly a number (an edge set with optional edge weights), a reference to an array of GraphTheory::SimpleGraph::Value::Edge objects, or a reference to a GraphTheory::SimpleGraph::Value::EdgeSet object.
If $definition is the number of vertices in the graph, then the graph that is returned will have that number of vertices and no edges. Note that the number of vertices must be greater than 0.
If $definition is another GraphTheory::SimpleGraph object, then a copy of the graph represented by that object will be returned.
If $definition is a one of the matrix forms (a reference to an array of arrays of numbers or a reference to a MathObject Matrix), then that matrix will be used for the adjacency matrix of the graph. Note that it must be a square symmetric matrix with zero entries along the diagonal and must have size greater than or equal to 1. For example,
[
[ 0, 1, 0],
[ 1, 0, 2],
[ 0, 2, 0]
]represents a graph that has three vertices, an edge between the first and second vertices with weight one, and an edge between the second and third vertices with weight 2.
If $definition is one of the edge set definition forms (a reference to an array of arrays containing two strings and possibly a number, a reference to an array of GraphTheory::SimpleGraph::Value::Edge objects, or a reference to a GraphTheory::SimpleGraph::Value::EdgeSet object), then the labels option is required. For the reference to an array of arrays form each edge in the edge set must be an array containing two strings and possibly a third numeric element. The two strings are the labels for the vertices connected by the edge. The optional third element is the weight of the edge. If the optional third element is not given, then the edge will have a weight of one. Note that all labels provided in the labels option will be used with this definition, and will all be vertices in the graph. For example, if $definition is given as
[
[ 'A', 'B' ],
[ 'A', 'C', 2 ],
[ 'B', 'C', 3 ],
]and the labels option is ['A', 'B', 'C', 'D'], then the return object will represent a graph that has at four vertices labeled 'A', 'B', 'C', and 'D', respectively, an edge between 'A' and 'B' with weight one, an edge between 'A' and 'C' with weight 2, an edge between 'B' and 'C' with weight 3, and no edges connecting to the vertex 'D'. Note that setting weights when a graph is constructed via a reference to an array of GraphTheory::SimpleGraph::Edge objects or a reference to a GraphTheory::SimpleGraph::EdgeSet object is not supported. However, weights can still be set after construction with the "edgeWeight" method or the "setRandomWeights" method.
The arguments that may be passed in %options are as follows. Note that all of these options are undefined by default.
The value of this option must be a reference to an array of strings. These are the labels for the vertices of the graph. The array must contain at least as many strings as there are vertices of the graph. Any extraneous strings will not be used (except in the edge set definition case as mentioned above). If this option is not given, then a random set of consecutive letters from the alphabet will be used for the labels of the vertices. Note that if an edge set version of the $definition argument is used, then this option must be provided.
If this option is given, then it must be a reference to an array containing two numbers, for example, [3, 4]. In this case when the "image" method is called to create the image of the graph, the vertices will be arranged into a grid with the number of rows equal to the first number in the array, and the number of columns equal to the second number in the array. Note that many graphs will not work well in a grid layout. This is primarily intended for graphs created via the "randomSimpleGraph" function where its first argument is used as the value for this option. This option is generally intended for internal use in this macro specifically for that function. However, there may be other graphs that may also work well in a grid layout.
If this option is given, then it must either be 1 or a reference to an array containing two arrays of vertex indices. If this is 1, then a partition of the vertices into two sets in which no two vertices in the same set are connected by an edge will attempt to be obtained internally via the "bipartitePartition" method. If the graph is not bipartite then no such partition will be found and the "image" method will not use the bipartite layout. Instead the image will be displayed in the default circle layout. If this is an array containing two arrays of vertex indices, then the two arrays must be the partition of the vertices of the graph in which no two vertices in the same set are connected by an edge. In this case when the "image" method is called to create the image of the graph, the vertices will be arranged into to rows with the vertices in the first set in the top row, and the vertices in the second set in the bottom row. Note that an exception will be thrown if this option is 1 and the graph is not bipartite.
If this option is given, then it must be an index of one of the vertices in the graph (0, 1, 2, ...), and when the "image" method is called to create the image of the graph, that vertex will be placed in the center of a circle, and the other vertices will be evenly spaced around the perimeter of the circle.
$graph = randomSimpleGraph($size, %options);This function returns a GraphTheory::SimpleGraph object in which the existence of an edge between any two vertices is randomly determined.
The $size argument is required and must either be an integer that is greater than zero, or a reference to an array containing two integers, both of which are greater than zero. If this argument is an integer that is greater than zero, then that will be the number of vertices of the graph. If this argument is a reference to an array containing two integers that are greater than zero, then the number of vertices in the graph will be the product of those two integers. Furthermore, this array reference will be passed as the gridLayout option to the GraphTheory::SimpleGraph constructor, and the image of the graph will have the vertices arranged into rows and columns. Furthermore, in the graph will be generated such that the only possible edges will connect vertices that are adjacent in that grid (including diagonal adjacency).
The arguments that may be passed in %options are as follows.
The value of this option, if given, must be a reference to an array of strings. These are the labels for the vertices of the graph. The array must contain at least as many strings as there are vertices of the graph. Any extraneous strings will not be used (except in the edge set definition case as mentioned above). If this option is not given, then a random set of consecutive letters from the alphabet will be used for the labels of the vertices.
This is the probability that there will be an edge between any two vertices. By default this is 0.5. Note that if $size is a reference to an array of integers, then this only applies to vertices that are adjacent in the grid, and there will never be edges between vertices that are not adjacent in the grid.
If this is given, then it must be a reference to an array of two or three numbers. In this case the weights of the edges will be a random number from the first number to the second number with increments of the optional third number (the increment defaults to 1). In fact the elements of this array are passed directly to the random function (see "Pseudo-random number generator" in PGbasicmacros.pl). Note that the startEdgeWeight option takes precedence over this option, and if it is given and is an integer greater than one, then it will be used instead of this option. Furthermore, if neither this option nor the startEdgeWeight option are given, then all edge weights will be 1.
If this option is given, then it must be an integer that is greater than zero. In this case this will be the first edge weight used in the generated graph, and the other edge weights will be determined by adding increments of the following edgeWeightIncrement option.
If this option is given, then it must be an integer that is greater than zero. Note that this is only used if startEdgeWeight is also given and is greater than zero, and in that case increments of this number will be added to the startEdgeWeight and used for the weights of the edges. If the startEdgeWeight is given, is an integer greater than 0, and this option is undefined, then an edge weight increment of 1 will be used.
The examples below demonstrate the usage of this function and its options in more details.
$graph = randomSimpleGraph(random(3, 5), edgeProbability => 1);will return a complete graph with 3, 4, or 5 vertices and all edge weights equal to 1.
$graph = randomSimpleGraph(random(3, 5), edgeProbability => 0);will return a graph with 3, 4, or 5 vertices that has no edges. Note that $graph = SimpleGraph(random(3, 5)) is equivalent and is slightly more efficient.
$graph = randomSimpleGraph(
5,
edgeProbability => 0.3,
edgeWeightRange => [1, 10]
);will return a graph with 5 vertices with probability 0.3 of an edge between any two vertices, and random edge weights from 1 to 10 (in increments of 1).
$graph = randomSimpleGraph(
5,
startEdgeWeight => 2,
edgeWeightIncrement => 3
);will return a graph with 5 vertices with probability 0.5 of an edge between any two vertices, and the edge weights will be 2, 5, 8, 11, ... (which will be randomly assigned to the edges in the graph).
$graph = randomSimpleGraph([3, 4], edgeProbability => 0.6);will return a graph with 12 vertices and all edge weights equal to 1. When the image of this graph is displayed the vertices will be arranged into a grid with 3 rows and 4 columns. The probability of an edge between vertices that are adjacent in the grid is 0.6. There will be no edges between vertices that are not adjacent in the grid.
$graph = randomGraphWithEulerCircuit($size, %options);This function returns a GraphTheory::SimpleGraph object that represents a random graph with $size vertices that has an Euler circuit. This function also accepts the labels, startEdgeWeight, edgeWeightIncrement, and edgeWeightRange options accepted by the "randomSimpleGraph" function.
$graph = randomGraphWithEulerTrail($size, %options);This function returns a GraphTheory::SimpleGraph object that represents a random graph with $size vertices that has an Euler trail, but does not have an Euler circuit. This function also accepts the labels, startEdgeWeight, edgeWeightIncrement, and edgeWeightRange options accepted by the "randomSimpleGraph" function.
$graph = randomGraphWithoutEulerTrail($size, %options);This function returns a GraphTheory::SimpleGraph object that represents a random graph with $size vertices that does not have an Euler trail (or circuit). This function also accepts the labels, startEdgeWeight, edgeWeightIncrement, and edgeWeightRange options accepted by the "randomSimpleGraph" function.
$graph = randomBipartiteGraph($size, %options);This function returns a GraphTheory::SimpleGraph object that represents a random bipartite graph.
The $size argument can either be a number or a reference to an array of two integers that are greater than zero. If it is a number, then the graph will have $size vertices, and the number of vertices in the two parts of the bipartite partition will be randomly determined. If it is a reference to an array of two integers, then graph will have the number of vertices equal to the sum of those two numbers, and the two sets in the bipartite partition will have those numbers of elements.
This function also accepts the labels, edgeProbability, startEdgeWeight, edgeWeightIncrement, and edgeWeightRange options accepted by the "randomSimpleGraph" function.
$graph = randomTreeGraph($size, %options);This function returns a GraphTheory::SimpleGraph object that represents a random graph with $size vertices that is a tree. This function also accepts the labels, startEdgeWeight, edgeWeightIncrement, and edgeWeightRange options accepted by the "randomSimpleGraph" function.
$graph = randomForestGraph($size, %options);This function returns a GraphTheory::SimpleGraph object that represents a random graph with $size vertices that is a forest, but is not a tree. This function also accepts the labels, startEdgeWeight, edgeWeightIncrement, and edgeWeightRange options accepted by the "randomSimpleGraph" function.
$graph = randomHamiltonianGraph($size, %options);This function returns a GraphTheory::SimpleGraph object that represents a random graph with $size vertices that is Hamiltonian. Note that $size must be 5 or more, or an exception will be thrown. The labels may be passed in %options, and is the same as for the above functions.
$graph = randomNonHamiltonianGraph($size, $type, %options);This function returns a GraphTheory::SimpleGraph object that represents a random graph with $size vertices that is not Hamiltonian.
If $type is even, then the graph will have a vertex of degree one. If $type is odd, then the graph will consist of two cycles joined by a single edge. Note that for the odd $type graph, the $size must be at least 6, or an exception will be thrown.
This function also accepts the labels, startEdgeWeight, edgeWeightIncrement, and edgeWeightRange options accepted by the "randomSimpleGraph" function.
$graph = randomGraphWithDegreeSequence($degrees, %options);This function returns a GraphTheory::SimpleGraph object that represents a random graph that has the given $degree sequence, if such a graph is possible, and undefined otherwise.
The $degrees argument must be a reference to an array containing the desired vertex degrees.
This function also accepts the labels, startEdgeWeight, edgeWeightIncrement, and edgeWeightRange options accepted by the "randomSimpleGraph" function.
$graph = cycleGraph($size, %options);This function returns a GraphTheory::SimpleGraph object that represents a graph with $size vertices that is a cycle. This function also accepts the labels, startEdgeWeight, edgeWeightIncrement, and edgeWeightRange options accepted by the "randomSimpleGraph" function.
$graph = completeGraph($size, %options);This function returns a GraphTheory::SimpleGraph object that represents a graph with $size vertices that is a complete graph. This function also accepts the labels, startEdgeWeight, edgeWeightIncrement, and edgeWeightRange options accepted by the "randomSimpleGraph" function.
$graph = wheelGraph($size, %options);This function returns a GraphTheory::SimpleGraph object that represents a graph with $size vertices that is a wheel. This function also accepts the labels, startEdgeWeight, edgeWeightIncrement, and edgeWeightRange options accepted by the "randomSimpleGraph" function.
Note that the returned graph object will have the wheelLayout graph option set to the vertex at the hub of the wheel, and that vertex will be displayed in the center in the graph image.
$graph = completeBipartiteGraph($m, $n, %options);This function returns a GraphTheory::SimpleGraph object that represents a graph with $m * $n vertices that is a complete bipartite graph with $m vertices in first set in the bipartite partition, and $n vertices in the other set in the bipartite partition. This function also accepts the labels, startEdgeWeight, edgeWeightIncrement, and edgeWeightRange options accepted by the "randomSimpleGraph" function.
Note that the returned graph object will have the bipartiteLayout graph option set so that the graph image is nicely displayed with the vertices in the first set in the bipartite partition in a row on the top, and the vertices in the other set in a row on the bottom.
$edgeSet = EdgeSet($edges);
$edgeSet = EdgeSet($edge1, $edge2, ...);This method is an alias for the GraphTheory::SimpleGraph::Value::EdgeSet MathObject constructor. It can be passed a reference to an array of edges or just a list of edges. An edges can be a reference to an array containing two vertices, or can be a GraphTheory::SimpleGraph::Value::Edge MathObject. As with all MathObject constructors, the first argument can optionally be a context. Note that vertices must be strings in the current context or the context that is passed.
Since this derives from a MathObject List, a list_checker must be used for a custom checker routine.
Usually this would only be used in the EdgeSet context. Otherwise the returned value will not display correctly in the problem and will not work well as an answer. However, the object can still be passed to the SimpleGraph function to create a graph with that edge set.
$edge = Edge($vertex1, $vertex2);
$edge = EdgeSet([ $vertex1, $vertex2 ]);This method is an alias for the GraphTheory::SimpleGraph::Value::Edge MathObject constructor. It can be passed a reference to an array containing two vertices or a list of two vertices. As with all MathObject constructors, the first argument can optionally be a context. Note that vertices must be strings in the current context or the context that is passed.
Since this derives from a MathObject List, a list_checker must be used for a custom checker routine.
Usually this would only be used in the EdgeSet context. Otherwise the returned value will not display correctly in the problem and will not work well as an answer. However, the object can still be passed in an array reference to the SimpleGraph function to create a graph with that edge set.
The GraphTheory::SimpleGraph package is the heart of this macro. All of the functions described above return an object that is an instance of this package class. See the "SimpleGraph" function for the constructor usage. In addition, the following object methods are available.
$matrix = $graph->adjacencyMatrix;This method returns the adjacency matrix that defines the graph. That is a reference to an array of array references each containing numbers. The matrix will be a symmetric square matrix with zero entries along the diagonal. The entry in the i-th row and j-th column will be zero if there is not an edge connecting the i-th and j-th vertex, and will be nonzero if there is such an edge. Furthermore, the entry represents the edge weight in the case that it is not zero.
Note that indexing of vertices is zero based. So the first vertex has index 0, and the last vertex has index one less than the number of vertices in the graph.
$edgeSet = $graph->edgeSet(%options);This method returns the edge set for the graph as a MathObject EdgeSet containing MathObject Edges. For example, if a graph has adjacency matrix
[
[ 0, 1, 0, 0 ],
[ 1, 0, 1, 0 ],
[ 0, 1, 0, 1 ]
[ 0, 0, 1, 0 ]
]and labels 'A', 'B', 'C', and 'D', then this method would return
{{A, B}, {B, C}, {C, D}}where the outer set is a MathObject EdgeSet, the elements of that set are MathObject Edges, and the elements of those sets are MathObject Strings. The returned EdgeSet will be either be in a created EdgeSet context with the vertex labels of the graph defined as strings and marked as being vertices in that context, or in a context provided in the %options as described below.
This return value can be used as an answer to a question, and will display in output as shown above.
Note, that edge weights are not represented in the return value of this method.
The following options that may be passed in %options.
context => undef)The context to use for the returned MathObject EdgeSet object. If this is not provided, then a EdgeSet context will be created, the vertex labels added as strings to the context and marked as being vertices and the returned object will be in the created context.
caseSensitive => 1)Whether vertex labels that are added to the context are case sensitive or not.
$graph->addVerticesToContext($caseSensitive, $context);This adds the vertex labels of the graph to the context and marks them as being vertices (by adding the isVertex flag).
The $caseSensitive and $context arguments are optional.
If $caseSensitive is 1 or the argument is not provided, then the vertices will be case sensitive. So entering "a" will not be accepted as correct for the vertex labeled "A". If $caseSensitive is 0, then vertices will not be case sensitive. So "a" will be accepted as correct for the vertex labeled "A".
If $context is provided, then the strings will be added to that context. Otherwise the strings will be added to the current context.
$n = $graph->numVertices;This method returns the number of vertices in the graph.
$n = $graph->lastVertexIndex;This method returns the index of the last vertex in the graph (i.e., it is one less then the number of vertices).
$n = $graph->numEdges;This method returns the number of edges in the graph.
$labels = $graph->labels;
$graph->labels($labels);Get or set the vertex labels for the graph. In both examples above, $labels is a reference to an array of strings, for example, [ 'M', 'N', 'O', 'P' ].
$labelsString = $graph->labelsString;This returns the vertex labels joined with a comma. This is a convenience method for displaying labels in a problem. For example, the labels string can be inserted into a PGML block with [`[$graph->labelsString]`].
$label = $graph->vertexLabel($index);This method returns the label of the vertex at index $index in the graph.
$index = $graph->vertexIndex($label);This method returns the index of the vertex in the graph that is labeled $label if the given $label exists for a vertex, and -1 otherwise.
$degree = $graph->vertexDegree($index);This method returns the degree of the vertex at index $index in the graph.
@degrees = $graph->degrees;This method returns an array of the degrees of the vertices in the graph.
$c = $graph->numComponents;This method returns the number of connected components in the graph.
@c = $graph->components;This method returns an array containing references to arrays that form a partition of the vertex indices into the connected components of the graph.
$c = $graph->edgeWeight($i, $j);
$graph->edgeWeight($i, $j, $weight);Get or set the weight of the edge between the vertices at indices $i and $i. If the optional third $weight argument is provided, then the weight of the edge between the vertices at indices $i and $j will be set to $weight. In any case, the weight of the edge between the vertices at indices $i and $j will be returned. Note that an edge weight of zero means that there is no edge connecting the vertices.
Setting the edge weight to zero is equivalent to removing the edge if it was nonzero, and setting the edge weight to a nonzero number when it was zero adds an edge. However, if your only intent is to add or remove an edge, then it is recommended to use the addEdge or removeEdge methods instead for clarity in the code.
$graph->addEdge($i, $j, $weight);Add and edge that connects the vertices at indices $i and $j. The $weight argument is optional, and if not provided the weight of the edge will be set to 1.
$graph->removeEdge($i, $j);Remove the edge that connects the vertices at indices $i and $j. This is accomplished by setting the weight of the edge between the two vertices to 0.
$graph->hasEdge($i, $j);This method returns a true value if the graph has an edge that connects the vertices at indices $i and $j, and a false value otherwise.
$graph->setRandomWeights(%options);Set random weights for the edges of the graph. This method does not add or remove any edges, but randomly sets the weights of the existing edges.
The arguments that may be passed in %options are as follows. If neither of the startEdgeWeight or edgeWeightRange options is given, then this method does not change the current edge weights of the graph.
If this option is given, then it must be an integer that is greater than zero. In this case this will be the first edge weight used in the generated graph, and the other edge weights will be determined by adding increments of the following edgeWeightIncrement option.
If this option is given, then it must be an integer that is greater than zero. Note that this is only used if startEdgeWeight is also given and is greater than zero, and in that case increments of this number will be added to the startEdgeWeight and used for the weights of the edges. If the startEdgeWeight is given, is an integer greater than 0, and this option is undefined, then an edge weight increment of 1 will be used.
If this is given, then it must be a reference to an array of two or three numbers. In this case the weights of the edges will be a random number from the first number to the second number with increments of the optional third number (the increment defaults to 1). In fact the elements of this array are passed directly to the random function (see "Pseudo-random number generator" in PGbasicmacros.pl). Note that the startEdgeWeight option takes precedence over this option, and if it is given and is an integer greater than one, then it will be used instead of this option.
The number of edges in the graph for which to set random weights. If this option is not given, then the number of edges in the graph will be computed, and all the weights of all existing edges will be randomized. If the number of edges in the graph is already known, then set this option to that value for efficiency so that this method does not need to compute that number again.
$graph->isEqual($other);This method returns 1 if the graph object represented by $graph and the graph represented by $other are the same. This does not necessarily return 1 for isomorphic graphs. The two graphs must literally have the same adjacency matrix.
$graph->isIsomorphic($other);This method returns 1 if the graph represented by $graph and the graph represented by $other are isomorphic.
WARNING: This method uses a brute force approach and compares the first graph to all possible permutations of the other graph, and so should not be used for graphs with a large number of vertices (probably no more than 8).
$graph->description(%options);Returns a textual description of the graph. The string that is returned is translated and is suitable to be used as the alt text for the graph image returned by one of the following image methods. Note that the description just lists the vertices and edges, and does not describe the layout for the specialized layout image methods.
At this point the only option that can be set via the %options argument is includeWeights. If includeWeights is set to 1, then the edge weights will be included in the description. If this is 0, then edge weights will not be included. Default is 0.
$graph->image(%options);Constructs and returns a Plots::Plot object via the plots.pl macro that provides a pictorial representation of the graph. The returned object may be inserted into the problem via the image method (see "Macros for displaying images" in PGbasicmacros.pl), "insertGraph" in PGcore, or using the PGML image syntax (for example, [!alt text!]{$graph->image}).
Note that the gridLayout, bipartiteLayout, and wheelLayout options that can be set when the GraphTheory::SimpleGraph object is created affect how the graph is displayed. See the "SimpleGraph" function for details on those options. Note that those options can also be set as properties of the object anytime after construction and before this method is called (for example, $self->{bipartiteLayout = 1;). If none of those layout options are used, then the vertices of the graph will be evenly spaced around the perimeter of a circle with the vertex at index 0 on the right.
The following options can be set via the %options argument.
If this is 1, then vertex labels will be shown. If this is 0, then vertex labels will not be shown. Default is 1 (so labels must be explicitly hidden by setting this to 0).
If this is 1, then edge weights will be shown. If this is 0, then edge weights will not be shown. Default is 0.
Note that the display of edge weights often does not work well as it can be unclear which edge a given weight belongs to in the image. Particularly if a graph has a large number of edges. Graphs that are created via the randomSimpleGraph function using the row and column $size argument (and hence are displayed using the grid layout) do work quite well for this.
This is the width of the image. Default is 250 (except in the case that the gridLayout is used, in which case the default is the product of 140 and one less than the number of columns in the grid layout).
Note that the width can also be set via the PGbasicmacros.pl image method, or via the width option for the PGML image syntax.
This is the height of the image. Default is undefined.
Note that the height can also be set via the PGbasicmacros.pl image method, or via the height option for the PGML image syntax.
If this is set and the height option above is not set, then the height of the image will be computed from the width using this aspect_ratio. Default is 1.
Note that aside from the showLabels and showWeights options, all other options (including any not listed above) that are provided are actually just passed to the underlying Plot object.
$graph->gridLayoutImage(%options);This method is not intended to be used externally. It is called by the "image" method if the gridLayout property is set for the graph object. If this method is called directly and the gridLayout property is set, then it will still work. Otherwise an exception will be thrown. It accepts the same options as the "image" method. Note that the default value for the width option is the product of 140 and one less than the number of columns in the grid layout.
$graph->bipartiteLayoutImage(%options);This method is not intended to be used externally. It is called by the "image" method if the bipartiteLayout property is set for the graph object. If this method is called directly and the bipartiteLayout property is set, then it will still work. Otherwise an exception will be thrown. Note that an exception will also be thrown if the bipartiteLayout property is set to 1, and the graph is not bipartite. It accepts the same options as the "image" method.
$graph->wheelLayoutImage(%options);This method is not intended to be used externally. It is called by the "image" method if the wheelLayout property is set for the graph object. If this method is called directly and the wheelLayout property is set, then it will still work. Otherwise an exception will be thrown. It accepts the same options as the "image" method.
$copy = $graph->copy;This method returns a copy of $graph. This is an exact copy with all properties duplicated to the returned object.
$shuffledGraph = $graph->shuffle($permuteLabels);This method returns a randomization of $graph obtained by permuting the vertices. The edges that connected the vertices in the original graph will still connect the permuted vertices in the resulting graph. In other words the returned graph is isomorphic to the original.
If the optional $permuteLabels argument is provided and is true, then the labels will also be permuted with the vertices. Otherwise the labels will remain in the same order that they were in the original graph, but the shuffled graph will still have the same labels.
If the bipartiteLayout property is set to 1 for the original graph, then the shuffled graph will also have also have that property set to 1. However, the array form of the bipartiteLayout property will not be preserved.
The gridLayout property is not preserved in the shuffled graph in any case.
The wheelLayout property is preserved in the shuffled graph, and its value will be permuted so that the vertex it marked as the hub of the wheel is still the hub. This means that the hub of the wheel will still be displayed in the center when the "image" method is used to display the graph. If that is not desired, then delete the wheelLayout property for the result. For example,
$shuffledGraph = $graph->shuffle;
delete $shuffledGraph->{wheelLayout};($path, $weight) = $graph->nearestNeighborPath($vertex);This is an implementation of the nearest neighbor algorithm. It attempts to find the shortest path starting at the vertex indexed by $vertex that visits all vertices in the graph exactly once and returns to the starting vertex. Note that if such a path is not possible, then the algorithm will go as far as it can, but the path that is returned may not visit all vertices and may not be a circuit. This method will always succeed for complete graphs.
The method returns a list whose first entry is a reference to an array containing the path found, and whose second entry is the total weight of that path.
($tree, $treeWeight, $treeWeights, $algorithmSteps) = $graph->kruskalGraph($vertex);This is an implementation of Kruskal's algorithm. It attempts to find a minimum spanning tree or forest for the graph. Note that if the graph is connected, then the result will be a tree, and otherwise it will be a forest consisting of minimal spanning trees for each component.
The method returns a list with four entries. The first entry is a GraphTheory::SimpleGraph object representing the tree or forest found. The second entry is the total weight of that tree or forest. The third entry is a reference to an array containing the weights of the edges in the tree or forest in the order that they are added by the algorithm. The fourth entry is a reference to an array of array references that represent the steps of Kruskal's algorithm.
The returned representation of the steps in the algorithm will be a reference to an array of array references where each array reference is of the form [$i, $j, $weight, $accepted]. This is where $i and $j are the indices of the vertices connected by an edge in the graph, and $weight is the weight of that edge. These arrays will be sorted in ascending order of weight, i.e., the order the edge is considered by Kruskal's algorithm. The last $accepted will be either 0 or 1. It will be 0 if the edge is rejected by the algorithm, and 1 if it is accepted by the algorithm. Note that this list may not contain all edges of the original graph if there are edges that are never considered by the algorithm because the minimal spanning tree is completed before those edges are reached.
$hasEulerCircuit = $graph->hasEulerCircuit;
($hasEulerCircuit, $message) = $graph->hasEulerCircuit;In scalar context this method returns 1 if the graph has an Euler circuit, and 0 otherwise. In list context this method returns 1 if the graph has an Euler circuit, and if the graph does not have an Euler circuit it returns a list whose first entry is 0 and whose second entry is a message stating the reason that the graph does not have an Euler circuit.
$hasEulerTrail = $graph->hasEulerTrail;
($hasEulerTrail, $message) = $graph->hasEulerTrail;In scalar context this method returns 1 if the graph has an Euler trail, and 0 otherwise. In list context this method returns 1 if the graph has an Euler trail, and if the graph does not have an Euler trail it returns a list whose first entry is 0 and whose second entry is a message stating the reason that the graph does not have an Euler trail.
$pathIsEulerTrail = $graph->pathIsEulerTrail(@path);
($pathIsEulerTrail, $message) = $graph->pathIsEulerTrail(@path);The @path argument should contain a list of vertex indices in the graph representing a path in the graph. In scalar context this method returns 1 if the path forms an Euler trail in the graph, and 0 otherwise. In list context this method returns 1 if the path forms an Euler trail in the graph, and if the path does not form an Euler trail in the graph it returns a list whose first entry is 0 and whose second entry is a message stating the reason that the path does not form an Euler trail.
$pathIsEulerCircuit = $graph->pathIsEulerCircuit(@path);
($pathIsEulerCircuit, $message) = $graph->pathIsEulerCircuit(@path);The @path argument should contain a list of vertex indices in the graph representing a path in the graph. In scalar context this method returns 1 if the path forms an Euler circuit in the graph, and 0 otherwise. In list context this method returns 1 if the path forms an Euler circuit in the graph, and if the path does not form an Euler circuit in the graph it returns a list whose first entry is 0 and whose second entry is a message stating the reason that the path does not form an Euler circuit.
$hasCircuit = $graph->hasCircuit;This method returns 1 if the graph has a circuit, and 0 otherwise.
$isTree = $graph->isTree;
($isTree, $message) = $graph->isTree;In scalar context this method returns 1 if the graph is a tree, and 0 otherwise. In list context this method returns 1 if the graph is a tree, and if the graph is not a tree it returns a list whose first entry is 0 and whose second entry is a message stating the reason that the graph is not a tree.
$isForest = $graph->isForest;
($isForest, $message) = $graph->isForest;In scalar context this method returns 1 if the graph is a forest, and 0 otherwise. In list context this method returns 1 if the graph is a forest, and if the graph is not a forest it returns a list whose first entry is 0 and whose second entry is a message stating the reason that the graph is not a forest.
$isBipartite = $graph->isBipartite;This method returns 1 if the graph is bipartite, and 0 otherwise.
($upper, $lower) = $graph->bipartitePartition;If the graph is bipartite, then this method returns a list containing two entries that form a partition of the vertices of the graph into two sets for which no two vertices in the same set have an edge connecting them. If the graph is not bipartite, then this method returns undefined.
($distance, @path) = $graph->dijkstraPath($start, $end);This is an implementation of Dijkstra's algorithm for finding the shortest path between nodes in a weighted graph.
The $start and $end arguments are required and should be indices of two vertices in the graph representing the start vertex and end vertex for which to find the shortest path between.
The return value will be a list whose first entry is the shortest distance from the start vertex to the end vertex, and whose remaining entries are the indices of the vertices that form the shortest path from the start vertex to the end vertex.
($pathWeights, $algorithmSteps, $sortedGraph) = $graph->sortedEdgesPath;This is an implementation of the sorted edges algorithm for finding a low cost Hamiltonian circuit in a graph. That is a path that visits each vertex in the graph exactly once. The return value will be a list with three entries. The first entry is a reference to an array containing the weights of the edges in the path in the order that they are chosen by the algorithm, the second entry is a reference to an array of array references that represent the steps of the sorted edges algorithm, and the third entry is the resulting sorted edges graph.
The returned representation of the steps in the algorithm will be a reference to an array of array references where each array reference is of the form [$i, $j, $weight, $reason]. This is where $i and $j are the indices of the vertices connected by an edge in the graph, and $weight is the weight of that edge. These arrays will be sorted in ascending order of weight, i.e., the order the edge is considered by the sorted edges algorithm. The $reason will be one of 0, 1, or 2. It will be 0 if the edge is chosen by the sorted edges algorithm, 1 if the edge is rejected by the sorted edges algorithm because adding it would have made a vertex in the path have more than two edges connected to it, and 2 if adding the edge would have created a circuit in the path (before the path is completed). Note that this list may not contain all edges of the original graph if there are edges that are never considered by the algorithm because the circuit is completed before those edges are reached.
The returned sorted edges graph will contain a Hamiltonian circuit from the original graph if one exists. In any case the graph will contain all edges chosen in the algorithm.
$graph->chromaticNumber;This method returns the chromatic number of the graph. That is the minimum number of colors required to color the vertices such that no two adjacent vertices share the same color.
$graph->kColoring($k);The argument $k is required and is the desired number of colors for which to find a k-coloring. That is a coloring of the graph consisting of at most k colors such that no two adjacent vertices share the same color. If such a coloring is possible, then this method will return a list with the number of entries equal to the number of vertices in the graph, and whose i-th entry will be an integer from 1 to k where the integers represent a coloring for the vertex with index i in the graph and such that the list forms a k-coloring. If a k-coloring is not possible, then this method returns undefined.
A context for edge sets is provided. To activate the context Call
Context('EdgeSet');Then GraphTheory::SimpleGraph::Value::Edge and GraphTheory::SimpleGraph::Value::EdgeSet objects can be constructed with
$edge = Compute('{B, E}');
$edgeSet = Compute('{{A, B}, {A, E}, {A, F}, {E, F}}');or by using the Edge or EdgeSet methods described before (those methods can also be used outside of this context). Note that the vertices must be added as strings to the context and marked as being vertices with the isVertex flag before constructing the Edge or EdgeSet. For example, by calling
Context()->strings->add(
map { $_ => { isVertex => 1, caseSensitive => 1 } } 'A' .. 'F'
);If it is preferred that the vertices not be case sensitive, then remove caseSensitive => 1 from the above call.
If the vertices in the Edge or EdgeSet belong to a GraphTheory::SimpleGraph object that has already been constructed, then the "addVerticesToContext" method can instead be used to add the vertices to the context.