Graph algorithms

all_maximal_cliques(::Type{U}, g::SimpleGraph{T}; kwargs...
    ) where {T,U} -> (Vector{U}, Symbol)

Calculate maximal cliques.

Reference

1. Tomita, E., Tanaka, A., & Takahashi, H. (2006). The worst-case time complexity for generating all maximal cliques and computational experiments. Theoretical Computer Science, 363(1), 28–42. https://doi.org/10.1016/J.TCS.2006.06.015
2. Cazals, F., & Karande, C. (2008). A note on the problem of reporting maximal cliques. Theoretical Computer Science, 407(1–3), 564–568. https://doi.org/10.1016/j.tcs.2008.05.010

all_maximal_conn_cliques(::Type{U}, g::SimpleGraph{T}, eattrs::Dict;
    kwargs...) where {T,U} -> (Vector{U}, Symbol)

Calculate maximal connected cliques.

Reference

1. Cazals, F., & Karande, C. (2005). An algorithm for reporting maximal c-cliques. Theoretical Computer Science, 349(3), 484–490. https://doi.org/10.1016/j.tcs.2005.09.038

approx_maximum_clique(g) -> Vector{Int}

Return approximate maximal cliques.

Reference:

• Boppana, R., & Halldórsson, M. M. (1992).
• https://networkx.org/documentation/stable/modules/networkx/algorithms/approximation/clique.html#maxclique

maximum_clique(::Type{U}, g::SimpleGraph{T}; kwargs...) where {T,U} -> (U, Symbol)

Calculate maximum clique.

maximum_conn_clique(::Type{U}, g::SimpleGraph{T}, eattrs::Dict;
    kwargs...) where {T,U} -> (U, Symbol)

Calculate maximal connected cliques.

mincyclebasis(graph::UndirectedGraph) -> Vector{Vector{Int}}

Returns minimum cycle basis represented as an array of edge sequence that make up a cycle.

Reference

1. de Pina, J.C. Applications of shortest path methods. PhD thesis, University of Amsterdam, Nether-lands (1995)
2. Kavitha, T., Mehlhorn, K., Michail, D. & Paluch, K. E. An $\tilde{O}(m^{2}n)$ Algorithm for Minimum Cycle Basis of Graphs. Algorithmica 52, 333–349 (2008).

maximum_common_subgraph(g::ConstraintArrayMCIS, h::ConstraintArrayMCIS;
    connected=false, kwargs...) -> (Dict, Symbol)

Compute maximum common node-induced subgraph (MCIS) between the two MCS constraints.

maximum_common_subgraph(g::ConstraintArrayMCES, h::ConstraintArrayMCES;
    connected=false, kwargs...) -> (Dict, Symbol)

Compute maximum common edge-induced subgraph (MCES) between the two MCS constraints.

modular_product(g::ConstraintArrayMCS, h::ConstraintArrayMCS;
    tolerance=0, kwargs...) -> SimpleGraph

Compute modular product of the two MCS constrait arrays.

edgesubgraph_is_isomorphic(g::SimpleGraph, h::SimpleGraph; kwargs...) -> Bool

Return whether an edge-induced subgraph of G is isomorphic to H.

edgesubgraph_isomorphisms(
    g::SimpleGraph, h::SimpleGraph;
    vmatch=(g,h)->true, ematch=(g,h)->true,
    kwargs...) -> Iterator

Return an iterator that generate isomorphic mappings between H and edge-induced subgraphs of G. The returned iterator has ig => ih pairs that correspond to the indices of matching edges in G and H, respectively.

vmatch and ematch control the features needed to be counted as a match.

See Graphs.induced_subgraph to construct the subgraphs that result from the match.

is_isomorphic(g::SimpleGraph, h::SimpleGraph; kwargs...) -> Bool

Return whether G and H are isomorphic.

isomorphisms(g::SimpleGraph, h::SimpleGraph; kwargs...) -> Iterator

Return an iterator that generate isomorphic mappings between G and H. The returned iterator has ig => ih pairs that correspond to the indices of matching nodes in G and H, respectively.

nodesubgraph_is_isomorphic(g::SimpleGraph, h::SimpleGraph; kwargs...) -> Bool

Return whether a node-induced subgraph of G is isomorphic to H.

nodesubgraph_isomorphisms(g::SimpleGraph, h::SimpleGraph; kwargs...) -> Iterator

Return an iterator that generate isomorphic mappings between H and node-induced subgraphs of G. The returned iterator has ig => ih pairs that correspond to the indices of matching nodes in G and H, respectively.

subgraph_is_monomorphic(g::SimpleGraph, h::SimpleGraph; kwargs...) -> Bool

Return whether a subgraph of G is monomorphic to H.

subgraph_monomorphisms(g::SimpleGraph, h::SimpleGraph; kwargs...) -> Iterator

Generate monomorphism mappings between H and subgraphs of G. The returned iterator has ig => ih pairs that correspond to the indices of matching nodes in G and H, respectively.

VF2Matcher{T,U,G<:SimpleGraph{T},H<:SimpleGraph{U}}

Lazy iterator that generate all isomorphism mappings between G and H.

matchtype should be one of the followings

• :isomorphic: G is isomorphic to H
• :subgraph_isomorphic: a node-induced subgraph of G is isomorphic to H
• :monomorphic: a subgraph of G is monomorphic to H

Options

• vmatch::Function: a function for semantic node attribute matching (default: (a, b) -> true)
• ematch::Function: a function for semantic edge attribute matching (default: (a, b) -> true)
• mandatory::Dict{Int,Int}: mandatory node mapping (if matchtype=:edgeinduced, edge mapping)
• forbidden::Dict{Int,Int}: forbidden node mapping (if matchtype=:edgeinduced, edge mapping)
• timeout::Union{Int,Nothing}: if specified, abort vf2 calculation when the time reached and return empty iterator (default: 10 seconds)

is_perfect_matching(G::SimpleGraph) -> Bool
is_perfect_matching(G::SimpleGraph, matching::Set{Int}) -> Bool

Return if the given graph has a perfect matching.

max_matching(G::SimpleGraph; method=:Blossom) -> Set{Int}

Compute maximum cardinality matching by Edmonds' blossom algorithm and return the set of matched edges.

induced_subgraph_edges(g, node_list)

Return the node-induced subgraph edges.

line_graph(G::SimpleGraph) -> SimpleGraph, Dict, Dict

Generate line graph, reverse mapping lg(v) -> g(e) and shared nodes mapping lg(e) -> g(v)

modularproduct(g::SimpleGraph{T}, h::SimpleGraph{T};
    vmatch=(g1,h1)->true,
    edgefilter=(g1,g2,h1,h2)->has_edge(g,g1,g2)==has_edge(g,h1,h2)) where T

Return the modular product m of graphs g and h, and a mapping whether the edge is connected or not. mapping g,h nodes to m nods is f(i, j) = (i - 1) * nv(h) + j and the reverse mapping is f(i) = (div(i - 1, nv(h)) + 1, mod(i - 1, nv(h))) + 1, where i in g and j in h.

isouterplanar(graph::SimpleGraph) -> Bool

Return whether the graph is outerplanar. The outerplanarity test is based on a planarity test (see isplanar).

isplanar(graph::SimpleGraph) -> Bool

Return whether the graph is planar.

Reference

1. de Fraysseix, H., & Ossona de Mendez, P. (2012). Trémaux trees and planarity. European Journal of Combinatorics, 33(3), 279–293. https://doi.org/10.1016/j.ejc.2011.09.012
2. Trémaux trees and planarity. https://arxiv.org/abs/math/0610935