文件列表:

.travis.yml (1112, 2022-10-23)
LICENSE (1082, 2022-10-23)
Project.toml (830, 2022-10-23)
REQUIRE (77, 2022-10-23)
src (0, 2022-10-23)
src\SimpleGraphAlgorithms.jl (5989, 2022-10-23)
src\chrome_poly.jl (4822, 2022-10-23)
src\connectivity.jl (4802, 2022-10-23)
src\edge-coloring.jl (1891, 2022-10-23)
src\fmatch.jl (875, 2022-10-23)
src\frac_iso.jl (1498, 2022-10-23)
src\hom.jl (1130, 2022-10-23)
src\iso.jl (8842, 2022-10-23)
src\kfactor.jl (803, 2022-10-23)
src\mad.jl (2512, 2022-10-23)
src\vertex-coloring.jl (3398, 2022-10-23)
test (0, 2022-10-23)
test\runtests.jl (1555, 2022-10-23)

# SimpleGraphAlgorithms This module provides additional functions for the `SimpleGraphs` module that rely on integer programming. In addition to requiring the `SimpleGraphs` module, it also requires `JuMP` and `MathProgBase` which, in turn, requires that some solvers be loaded. I've used `Cbc`. ## Functions ### Cliques and independent sets * `max_indep_set(G)` returns a maximum size independent set of an `UndirectedGraph`. * `max_clique(G)` returns a maximum size clique of an `UndirectedGraph`. * `max_matching(G)` returns a maximum size matching of an `UndirectedGraph`. * `fractional_matching(G)` returns a (maximum) fractional matching of the graph `G`. This is presented a dictionary mapping edges of `G` to rational values in `{0, 1/2, 1}`. * `kfactor(G,k)` returns a `k`-factor of `G`. This is a set of edges with the property that every vertex of `G` is incident with exactly `k` edges of the set. An error is thrown if no such set exists. (When `k==1` this returns a perfect matching.) ### Covering and domination * `min_dom_set(G)` returns a smallest dominating set of an `UndirectedGraph`. That is, a smallest set `S` with the property that every vertex of `G` either is in `S` or is adjacent to a vertex of `S`. * `min_vertex_cover(G)` returns a smallest vertex cover of `G`. This is a set of vertices `S` such that every edge of `G` has at least one end point in `S`. * `min_edge_cover(G)` returns a smallest edge cover of `G`. This is a set of edges `F` such that every vertex of `G` is the end point of at least one edge in `F`. **Note**: If `G` has an isolated vertex, then no edge cover is possible and error is generated. ### Isomorphism * `iso(G,H)` finds an isomorphism between graphs `G` and `H`. Specifically, it finds a `Dict` mapping the vertices of `G` to the vertices of `H` that gives the isomorphism. If the graphs are not isomorphic, an error is raised. * `iso2(G,H)` has the same functionality as `iso` but omits various preliminary checks. This may be faster for highly symmetric graphs (e.g., for vertex transitive graphs). * `is_iso(G,H)` checks if the two graphs are isomorphic. * `is_iso(G,H,d)` checks if the dictionary `d` is an isomorphism from `G` to `H`. * `iso_matrix(G,H)` finds an isomorphism between graphs `G` and `H`. Specifically, it finds a permutation matrix `P` such that `A*P==P*B` where `A` and `B` are the adjacency matrices of the graphs `G` and `H`, respectively. If the graphs are not isomorphic, an error is raised. * `frac_iso(G,H)` finds a fractional isomorphism between the graphs. Specifically, if `A` and `B` are the adjacency matrices of the two graphs, then produce a doubly stochastic matrix `S` such that `A*S == S*B`, or throw an error if no such matrix exists. * `is_frac_iso(G,H)` returns `true` if the graphs are fractionally isomorphic and `false` if not. * `hom(G,H)` finds a graph homomorphism from `G` to `H`. This is a mapping `f` (dictionary) with the property that if `{u,v}` is an edge of `G` then `{f[u],f[v]}` is an edge of `H`. If no homomorphism exists an error is raised. * `hom_check(G,H,d)` determines if `d` is a homomorphism from `G` to `H`. * `info_map(G)` creates a mapping from the vertices of `G` to 128-bit integers. If there is an automorphism between a pair of vertices, then they will map to the same value, and the converse is *likely* to be true. * `uhash(G)` creates a hash value for the graph `G` with the property that isomorphic graphs have the same hash value. ### Coloring * `vertex_color(G,k)` returns a `k`-coloring of `G` (or throws an error if no such coloring exists). If `k` is omitted, the number of colors is `χ(G)` (chromatic number). * `vertex_color(G,a,b)` returns an `a:b`-coloring of `G` (or throws an error if no such coloring exists). An `a:b`-coloring is a mapping from the vertices of `G` to `b`-element subsets of `{1,2,...,a}` such that adjacent vertices are assigned disjoint sets. * `chromatic_number(G)` returns the least `k` such that `G` is `k`-colorable. * `chromatic_poly(G)` computes the chromatic polynomial of `G`. (See the `help` message for more information.) * `edge_color(G,k)` returns a `k`-edge-coloring of `G`. * `edge_chromatic_number(G)` returns the edge chromatic number of `G`. ### Connectivity * `min_cut(G)` returns a minimum size (vertex) cut set. `min_cut(G,s,t)` return a smallest set of vertices that separate `s` and `t`. * `connectivity(G)` or `connectivity(G,s,t)` returns the size of such a cut set. * `min_edge_cut(G)` returns a minimum size edge cut set. `min_edge_cut(G,s,t)` returns a minimum set of edges that separate vertices `s` and `t`. * `edge_connectivity(G)` or `edge_connectivity(G,s,t)` returns the size of such an edge cut set. ### Maximum average degree * `ad(G)` returns the average degree of `G`. * `mad(G)` returns the maximum average degree of `G`. * `mad_core(G)` returns a subgraph `H` of `G` for which `ad(H)==mad(G)`. ## Examples ``` julia> using SimpleGraphs; using SimpleGraphAlgorithms; using ChooseOptimizer; using ShowSet julia> set_solver_verbose(false) [ Info: Setting verbose option for Cbc to false julia> G = Paley(17) Paley (n=17, m=68) julia> max_indep_set(G) {1,4,7} julia> max_clique(G) {3,4,5} julia> min_dom_set(G) {3,6,9} julia> max_matching(G) {(1, 16),(2, 4),(3, 12),(5, 9),(6, 15),(7, 8),(10, 11),(13, 14)} julia> vertex_color(G,6) Dict{Int***,Int***} with 17 entries: 2 => 3 16 => 1 11 => 4 0 => 4 7 => 6 9 => 2 10 => 1 8 => 3 6 => 4 4 => 6 3 => 5 5 => 3 13 => 1 14 => 5 15 => 2 12 => 2 1 => 6 ``` Petersen's graph can be described as either the 5,2-Kneser graph or as the complement of the line graph of K(5). ``` julia> G = Kneser(5,2); julia> H = complement(line_graph(Complete(5))); julia> iso(G,H) Dict{Set{Int***},Tuple{Int***,Int***}} with 10 entries: {1,4} => (1, 5) {2,4} => (1, 4) {2,5} => (3, 4) {1,3} => (2, 5) {3,4} => (1, 2) {1,2} => (4, 5) {3,5} => (2, 3) {4,5} => (1, 3) {2,3} => (2, 4) {1,5} => (3, 5) julia> iso_matrix(G,H) 10×10 Array{Int***,2}: 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 ``` ## Setting Solver and its Options By default, the `Cbc` solver is used for integer programming and the optimizer does no output. The function `use_Cbc()` sets the solver to be the `Cbc` solver. Called as `use_Cbc(true)` causes the solver to be verbose in its working. The `Gurobi` solver may used instead. Since this module is not dependent on `Gurobi`, do this: ``` julia> using Gurobi julia> use_Gurobi() ``` Alternatively, `use_Gurobi(true)` for extensive output as the solver does its work. To switch back to the `Cbc` solver, do `use_Cbc()`. These functions rely on my `ChooseOptimizer` module. ## Using `SimpleGraphAlgorithms` with `Graphs` `SimpleGraphAlgorithms` is built to work with `UndirectedGraph` objects as defined in `SimpleGraphs`. To apply these functions to graphs from Julia's `Graphs` module, you can use `SimpleGraphConverter` like this: ``` julia> using Graphs, SimpleGraphAlgorithms, SimpleGraphs, SimpleGraphConverter julia> use_Cbc() [ Info: Solver Cbc verbose is set to false julia> g = circular_ladder_graph(9) {18, 27} undirected simple Int*** graph julia> chromatic_number(UG(g)) Welcome to the CBC MILP Solver Version: 2.10.5 Build Date: Dec 4 2021 command line - Cbc_C_Interface -LogLevel 0 -solve -quit (default strategy 1) Welcome to the CBC MILP Solver Version: 2.10.5 Build Date: Dec 4 2021 command line - Cbc_C_Interface -LogLevel 0 -solve -quit (default strategy 1) Welcome to the CBC MILP Solver Version: 2.10.5 Build Date: Dec 4 2021 command line - Cbc_C_Interface -LogLevel 0 -solve -quit (default strategy 1) 3 ```

近期下载者：

相关文件：

评论：[我要评论] [举报此文件]

收藏者：