# Computing the Atom Graph of a Graph and the Union Join Graph of a Hypergraph
## 4 Computing the Atom Graph
### Algorithm AG-Max-Weight
Thus, algorithm Union-max-weight computes the union of the maximum weight spanning trees of \(G\) by initializing a set \(F\) with the empty set and adding to \(F\), for each weight value \(k\) in decreasing order, the edges \(xy\) of \(G\) of weight \(k\) such that \(x\) and \(y\) are in different connected components of the graph \((V,F)\) in its state just after adding the edges of weight strictly greater than \(k\). In the algorithm Union-max-weight, \(k\) is the current value of weight, the sets \(C_{i}\) are the connected components of the graph \((V,F)\) in its state at the beginning of iteration \(k\) and for each vertex \(x\), and \(numComp(x)\) is the index \(i\) of the component \(C_{i}\) containing \(x\). The algorithm is similar to the \"maximum weight\" variant of [PERSON]'s algorithm, the difference being that [PERSON]'s algorithm considers the connected components of the graph (tree) \((V,F)\) being computed in its current state instead of in its state at the beginning of iteration \(k\), and therefore would update the variables \(C_{i}\) and \(numCom\) just after each addition of an edge to \(F\). It follows that the algorithms and complexity results already published on [PERSON]'s algorithm hold for the computation of the union of the maximum weight spanning trees. In particular, the complexity can be improved by using a sophisticated UNION-FIND data structure. However, the simple algorithm presented here is sufficient to compute the atom graph in \(O(n^{2})\) time. ```
input :The weighted intersection graph \(IG_{w}\) of the atoms of a connected graph \(G\). output :The atom graph of \(G\). return Union-max-weight\((IG_{w})\);
```  
**Algorithm 3**AG-max-weight. ```
input :A weighted-connected graph \(G_{w}=(V,E,w)\), with natural integer weights on the edges output :The union of the maximum weight spanning trees of \(G_{w}\). Compute the maximum weight \(w_{max}\) of an edge of \(G_{w}\) and for each \(k\) in \([0,w_{max}]\) the set \(E_{k}\) of edges of \(G_{w}\) of weight \(k\); \(i\gets 0\); foreach\(x\in V\)do \(i\gets i+1\); \(C_{i}\leftarrow\{x\}\); \(numComp(x)\gets i\);  end foreach\(F\leftarrow\emptyset\); foreach\(k=w_{max}\) downto 0 do foreach\(xy\in E_{k}\)do if\(numComp(x)\
eq numComp(y)\)then Add \(xy\) to \(F\);  end foreach\(xy\in E_{k}\)do if\(numComp(x)\
eq numComp(y)\)then \(i\gets numComp(x);j\gets numComp(y);C_{i}\gets C_{i}\cup C_{j}\); foreach\(z\in C_{j}\)do \(numComp(z)\gets i\);  end foreach end foreach end foreach return\((V,F)\);
```  
**Algorithm 4**Union-max-weight. ```
input :The weighted intersection graph \(IG_{w}\)



**Example 4**. : _Figure 4 shows the weighted intersection graph of the atoms of the graph \(G\) from Figure 1 and an execution of the algorithm AG-max-weight, i.e., the algorithm Union-max-weight, on this weighted graph. It shows the state of the computed graph before and after adding the edges of weight \(1\)._

**Theorem 4**. : _Given a weighted connected graph \(G_{w}=(V,E,w)\) with natural integer weights on the edges, the algorithm Union-max-weight computes the union of the maximum weight spanning trees of \(G_{w}\) in \(O(w_{max}+n^{2})\) time, where \(w_{max}\) is the maximum weight of an edge of \(G_{w}\)._

Proof. : It follows from Lemma 2 that the property \(P\) defined below is an invariant of the main foreach loop, using the notation \(UIM_{k}\) of this lemma,

\(P:UIM_{k}=(V,F)\) and \(\forall x\in V\) (\(C_{numComp(x)}\) is the connected component of \(UIM_{k}\) containing \(x\wedge\forall y\in C_{numComp(x)}\)\(numComp(x)=numComp(y)\)),

which proves the correctness of the algorithm. Let us prove its time complexity. \(w_{max}\) and the sets \(E_{k}\) can be computed and scanned in the internal for each loop in \(O(w_{max}+m)\) time by storing the elements of \(E_{k}\) at index \(k\) of an array. The first internal for each loop runs in \(O(m)\) time globally, and the second one in \(O(n^{2})\) time globally, since merging two connected components is in \(O(n)\) time and is performed \(n-1\) times.