GraphOptInterface

AbstractGraphOptimizer

Abstract supertype for block-structure-exploiting optimizers.

BipartiteGraph

A simple bipartite graph. Contains two vertex sets to enforce bipartite structure.

BipartiteGraph()

Construct an empty BipartiteGraph with no vertices or edges.

Edge

An edge represents different types of coupling. For instance an Edge{Tuple{Node}} is an edge the couple variables within a single node. An Edge{Tuple{N,Node}} couple variables across one or more nodes.

Edge(graph_index::GraphIndex, edge_index::EdgeIndex, nodes::NTuple{N,Node})

Construct a new Edge connecting the given tuple of nodes. Initializes an empty MOI model and edge index map for storing coupling constraints.

EdgeIndex

A unique identifier for an Edge using an integer value.

EdgeIndexMap

A bidirectional mapping between edge variables and their corresponding node variables. Contains mappings from edge variables to (Node, MOI.VariableIndex) tuples and vice versa.

EdgeIndexMap()

Construct an empty EdgeIndexMap with no variable mappings.

GraphIndex

A unique identifier for an OptiGraph using a Symbol value.

HyperEdge

A hyperedge connecting multiple hypernodes in a hypergraph. Contains a set of vertices (hypernodes) that the edge connects.

HyperEdge(t::HyperNode...)

Construct a HyperEdge from a variable number of hypernode arguments.

HyperEdge(t::Vector{HyperNode})

Construct a HyperEdge from a vector of hypernodes.

HyperGraph

A very simple hypergraph type. Contains attributes for vertices and hyperedges.

HyperGraph()

Construct an empty HyperGraph with no vertices or hyperedges.

HyperMap

A mapping from an OptiGraph to a graph view that supports various graph query functions. Currently supports a HyperGraph as the graph view.

HyperMap(graph::OptiGraph, hypergraph::HyperGraph)

Construct a new HyperMap with empty mappings between the given graph and hypergraph.

HyperNode

Type alias for a hypernode, represented as an Int64.

Node

A node represents a set of variables and associated attributes.

Node(graph_index::GraphIndex, node_index::NodeIndex)

Construct a new Node with the given graph and node indices. Initializes an empty MOI model for storing variables and constraints.

NodeIndex

A unique identifier for a Node using an integer value.

OptiGraph

A hierarchical graph structure for representing optimization problems with block structure. Contains nodes (representing subproblems), edges (representing coupling constraints), and subgraphs (for hierarchical decomposition).

Fields

• index::GraphIndex: Unique identifier for the graph
• parent::Union{Nothing,OptiGraph}: Parent graph (if this is a subgraph)
• nodes::Vector{Node}: Nodes in this graph
• edges::Vector{Edge}: Edges in this graph
• subgraphs::Vector{OptiGraph}: Child subgraphs
• node_by_index::OrderedDict{NodeIndex,Node}: Lookup map for nodes
• edge_by_index::OrderedDict{EdgeIndex,Edge}: Lookup map for edges
• subgraph_by_index::OrderedDict{GraphIndex,OptiGraph}: Lookup map for subgraphs

Base.:(==)(h1::HyperEdge, h2::HyperEdge)

Check if two hyperedges are equal by comparing their vertex sets.

Base.getindex(hypergraph::HyperGraph, edge::HyperEdge)

Get the integer index of a hyperedge in the hypergraph.

Base.getindex(hypergraph::HyperGraph, node::HyperNode)

Get the index of a hypernode (returns the node itself as the index).

Base.getindex(hyper_map::HyperMap, edge::Edge)

Get the HyperEdge that corresponds to the given edge in the hyper map.

Base.getindex(hyper_map::HyperMap, hyperedge::HyperEdge)

Get the Edge that corresponds to the given hyperedge in the hyper map.

Base.getindex(hyper_map::HyperMap, node::Node)

Get the HyperNode that corresponds to the given node in the hyper map.

Base.getindex(hyper_map::HyperMap, vertex::HyperNode)

Get the Node that corresponds to the given vertex in the hyper map.

Base.reverse(e::HyperEdge)

Hyperedges do not support reversal. Throws an error.

Base.setindex!(hyper_map::HyperMap, edge::Edge, hyperedge::HyperEdge)

Set the mapping from edge to hyperedge in the hyper map.

Base.setindex!(hyper_map::HyperMap, hyperedge::HyperEdge, edge::Edge)

Set the mapping from hyperedge to edge in the hyper map.

Base.setindex!(hyper_map::HyperMap, node::Node, vertex::HyperNode)

Set the mapping from node to vertex in the hyper map.

Base.setindex!(hyper_map::HyperMap, vertex::HyperNode, node::Node)

Set the mapping from vertex to node in the hyper map.

add_edge(graph::OptiGraph, nodes::NTuple{N,Node})::Edge where N

Add an edge to graph.

add_node(graph::OptiGraph)::Node

Add a node to graph. The index of the node is determined by the central graph.

add_subgraph(graph::OptiGraph)

Add a new subgraph to graph.

all_edges(graph::OptiGraph)

Return all edges in graph including edges from all subgraphs recursively.

all_incident_edges(hyper_map::HyperMap, nodes::Vector{Node})::Vector{Edge}

Return all of the edges within the optigraph in hyper_map that are incident to the vector of supplied nodes.

all_neighbors(hyper_map::HyperMap, nodes::Vector{Node})::Vector{Node}

Return the neighbor nodes within the optigraph in hyper_map to the vector of supplied optigraph nodes.

all_nodes(graph::OptiGraph)

Return all nodes in graph including nodes from all subgraphs recursively.

all_subgraphs(graph::OptiGraph)

Return all subgraphs contained in graph recursively.

build_hypergraph_map(graph::OptiGraph)

Build a HyperMap that maps the given graph to a HyperGraph representation. Creates hypernodes for each node and hyperedges for each edge in the graph. Returns the complete mapping.

children_incident_edges(hyper_map::HyperMap, graph::OptiGraph)::Vector{Edge}

Return all of the optigraph edges that are incident to the supplied graph that are strictly child connections.

edge_index(edge::Edge)::EdgeIndex

Return the EdgeIndex of the given edge.

expand(g::HyperGraph, nodes::Vector{HyperNode}, distance::Int64)

Expand the given nodes by the specified distance. Returns a tuple of (new_nodes, new_edges) where new_nodes includes all nodes within distance and new_edges are the induced hyperedges on those nodes.

get_edge_variable(edge::Edge, node::Node, variable::MOI.VariableIndex)

Get the edge variable index that corresponds to the given node and variable pair.

get_edges(graph::OptiGraph)

Return the vector of edges directly contained in graph (not including subgraph edges).

get_hyperedge(hypergraph::HyperGraph, edge_index::Int64)

Get the hyperedge corresponding to the given integer index.

get_hyperedge(hypergraph::HyperGraph, hypernodes::Set)

Get the hyperedge connecting the given set of hypernodes.

get_mapped_edges(hyper_map::HyperMap, edges::Vector{Edge})

Get the hypergraph HyperEdge elements that correspond to the supplied optigraph edges.

get_mapped_edges(hyper_map::HyperMap, edges::Vector{HyperEdge})

Get the optigraph Edge elements that correspond to the supplied hypergraph edges.

get_mapped_nodes(hyper_map::HyperMap, nodes::Vector{Node})

Get the hypernode elements that correspond to the supplied optigraph nodes.

get_mapped_nodes(hyper_map::HyperMap, nodes::Vector{HyperNode})

Get the optigraph Node elements that correspond to the supplied hypergraph nodes.

get_node_variable(edge::Edge, variable::MOI.VariableIndex)

Get the (Node, MOI.VariableIndex) tuple that corresponds to the given edge variable.

get_nodes(edge::Edge)

Return a vector of all nodes connected by the given edge.

get_nodes(graph::OptiGraph)

Return the vector of nodes directly contained in graph (not including subgraph nodes).

get_nodes_to_depth(graph::OptiGraph, depth::Int=0)

Return nodes in graph up to the specified depth of subgraphs. A depth of 0 returns only nodes in the current graph, depth of 1 includes immediate subgraph nodes, etc.

get_subgraphs(graph::OptiGraph)

Return the vector of immediate subgraphs contained in graph.

graph_index(graph::OptiGraph)

Return the GraphIndex of the given graph.

identify_edges(hypergraph::HyperGraph,partitions::Vector{Vector{HyperNode}})

Identify both induced partition edges and cut edges given a partition of HyperNode vectors.

identify_nodes(hypergraph::HyperGraph,partitions::Vector{Vector{HyperEdge}})

Identify both induced partition nodes and cut nodes given a partition of HyperEdge vectors.

identify_separators(bgraph::BipartiteGraph, partitions::Vector; cut_selector=Graphs.degree)

Identify separator elements (cut vertices or cut edges) that separate the given partitions. The cut_selector parameter determines how to assign boundary elements to cuts. It can be:

• A function (e.g., Graphs.degree) that compares element degrees
• :vertex to always assign vertices as separators
• :edge to always assign edges as separators

Returns a tuple (partition_elements, cross_elements) where partition_elements are the elements local to each partition and cross_elements are the separator elements.

incident_edges(hypergraph::HyperGraph,hypernode::HyperNode)

Identify the incident hyperedges to a HyperNode.

incident_edges(hypergraph::HyperGraph,hypernodes::Vector{HyperNode})

Identify the incident hyperedges to a vector of HyperNodes.

induced_edges(hypergraph::HyperGraph,hypernodes::Vector{HyperNode})

Identify the induced hyperedges to a vector of HyperNodes.

NOTE: This currently does not support hypergraphs with unconnected nodes

induced_elements(bgraph::BipartiteGraph, partitions::Vector; cut_selector=Graphs.degree)

Get the induced elements for each partition (i.e., elements local to each partition, excluding separators). This is a convenience function that returns only the first element of identify_separators.

Arguments

• bgraph::BipartiteGraph: The bipartite graph
• partitions::Vector: Vector of partitions
• cut_selector=Graphs.degree: Selector for determining cut assignment (function, :vertex, or :edge)

Returns

A vector of vectors, where each inner vector contains the induced elements for that partition.

neighborhood(g::HyperGraph, nodes::Vector{HyperNode}, distance::Int64)

Retrieve the neighborhood within distance of nodes. Returns a vector containing the original vertices and all vertices within the specified distance.

node_index(node::Node)::NodeIndex

Return the NodeIndex of the given node.

node_variables(edge::Edge)::Vector{Tuple{Node,MOI.VariableIndex}}

Return a vector of tuples where each tuple contains the node and variable index associated with each edge variable.

non_parent_incident_edges(hyper_map::HyperMap, subgraph::OptiGraph)::Vector{Edge}

Return all of the optigraph edges that are incident to the supplied subgraph that are strictly not parent connections.

non_parent_neighbors(hyper_map::HyperMap, subgraph::OptiGraph)::Vector{Node}

Return the neighbor nodes in subgraph based on the optigraph in hyper_map that are not in the parent graph of `subgraph.

num_all_nodes(graph::OptiGraph)

Return the total number of nodes in graph including all nodes in subgraphs recursively.

num_all_subgraphs(graph::OptiGraph)

Return the total number of subgraphs in graph recursively.

num_edges(graph::OptiGraph)

Return the number of edges directly contained in graph (not including subgraph edges).

num_nodes(graph::OptiGraph)

Return the number of nodes directly contained in graph (not including subgraph nodes).

num_subgraphs(graph::OptiGraph)

Return the number of immediate subgraphs in graph.

parent_incident_edges(hyper_map::HyperMap, subgraph::OptiGraph)::Vector{Edge}

Return all of the optigraph edges that are incident to the supplied subgraph that are strictly parent connections.

parent_neighbors(hyper_map::HyperMap, subgraph::OptiGraph)::Vector{Node}

Return the neighbor nodes in subgraph based on the optigraph in hyper_map that are only in the parent graph of `subgraph.

raw_index(edge::Edge)

Return the raw integer value of the edge's index.

raw_index(node::Node)

Return the raw integer value of the node's index.

raw_index(graph::OptiGraph)

Return the raw Symbol value of the graph's index.

string(edge::HyperEdge)

Return a string representation of the hyperedge showing its vertices.

string(graph::HyperGraph)

Return a string representation of the hypergraph showing vertex and edge counts.

supports_graph_interface(optimizer::MOI.AbstractOptimizer)

Check if the given optimizer supports the graph interface. Returns false for standard MOI optimizers and true for AbstractGraphOptimizer subtypes.

Graphs.adjacency_matrix(bgraph::BipartiteGraph)

Return the adjacency matrix of the bipartite graph. Rows correspond to vertices in the first set, columns correspond to vertices in the second set.

Graphs.adjacency_matrix(hypergraph::HyperGraph)

Obtain the adjacency matrix from hypergraph. Returns a sparse matrix.

Graphs.incidence_matrix(hypergraph::HyperGraph)

Obtain the incidence matrix representation of hypergraph. Rows correspond to vertices. Columns correspond to hyperedges. Returns a sparse matrix.

Graphs.add_edge!(bgraph::BipartiteGraph, from::Int64, to::Int64)

Add an edge between vertices from and to. Enforces bipartite structure by requiring that the vertices be in different vertex sets.

Graphs.add_edge!(hypergraph::HyperGraph, hypernodes::HyperNode...)

Add a hyperedge connecting the given hypernodes. If the hyperedge already exists, returns the existing hyperedge. Requires at least 2 hypernodes.

Graphs.add_vertex!(bgraph::BipartiteGraph; bipartite=1)

Add a vertex to the bipartite graph. The bipartite keyword argument specifies which vertex set to add the vertex to (1 or 2). Returns the success status.

Graphs.add_vertex!(hypergraph::HyperGraph)

Add a new vertex (hypernode) to the hypergraph. Returns the new hypernode index.

Graphs.all_neighbors(g::HyperGraph, node::HyperNode)

Return all neighbor nodes of the given node in sorted order. Neighbors are nodes that share at least one hyperedge with the given node.

Graphs.degree(g::HyperGraph, v::Int)

Return the degree of vertex v (the number of unique neighbors).

Graphs.edges(bgraph::BipartiteGraph)

Return an iterator over all edges in the bipartite graph.

Graphs.edges(hypergraph::HyperGraph)

Return an iterator over all hyperedges in the hypergraph.

Graphs.edgetype(bgraph::BipartiteGraph)

Return the edge type for a bipartite graph (SimpleEdge{Int64}).

Graphs.edgetype(graph::HyperGraph)

Return the edge type for a hypergraph (HyperEdge).

Graphs.has_edge(bgraph::BipartiteGraph, from::Int64, to::Int64)

Check if the bipartite graph has an edge from from to to.

Graphs.has_edge(graph::HyperGraph, edge::HyperEdge)

Check if the hypergraph contains the given hyperedge.

Graphs.has_edge(graph::HyperGraph, hypernodes::Set{HyperNode})

Check if the hypergraph has a hyperedge connecting the given set of hypernodes.

Graphs.has_vertex(bgraph::BipartiteGraph, v::Integer)

Check if the bipartite graph contains vertex v.

Graphs.has_vertex(graph::HyperGraph, v::Integer)

Check if the hypergraph contains the given vertex.

Graphs.is_directed(bgraph::BipartiteGraph)

Bipartite graphs are undirected. Always returns false.

Graphs.is_directed(graph::HyperGraph)

Hypergraphs are undirected. Always returns false.

Graphs.is_directed(::Type{BipartiteGraph})

Bipartite graphs are undirected. Always returns false.

Graphs.is_directed(::Type{HyperGraph})

Hypergraphs are undirected. Always returns false.

Graphs.ne(bgraph::BipartiteGraph)

Return the number of edges in the bipartite graph.

Graphs.ne(graph::HyperGraph)

Return the number of hyperedges in the hypergraph.

Graphs.nv(bgraph::BipartiteGraph)

Return the number of vertices in the bipartite graph.

Graphs.nv(graph::HyperGraph)

Return the number of vertices (hypernodes) in the hypergraph.

Graphs.vertices(bgraph::BipartiteGraph)

Return a vector of all vertices in the bipartite graph.

Graphs.vertices(hyperedge::HyperEdge)

Return a vector of all vertices connected by the hyperedge.

Graphs.vertices(graph::HyperGraph)

Return a vector of all vertices in the hypergraph.

MOI.add_variable(edge::Edge, node::Node, variable::MOI.VariableIndex)

Add a variable to the edge that maps to the given variable on the specified node. Returns the edge's variable index for use in edge constraints.