# Computing the Atom Graph of a Graph and the Union Join Graph of a Hypergraph
## 4 Computing the Atom Graph
### Algorithm Forest Join  
Our first algorithm, Forest Join (Algorithm 1), is based on Characterization 9. Given an atom tree \(T\), a minimal separator S is represented by one or several edges of \(T\). If we remove these edges, we obtain a forest. Let us now further shrink this forest by removing the nodes that do not contain \(S\). Any edge between two nodes of different trees of the resulting forest will correspond to an edge of the atom graph, which also represents S, and all the \(S\) representatives are thus encountered. To implement this remarkable property, our algorithm processes the edges of the atom tree one by one and computes the relevent nodes and edges with the help of relation _sub_. **Characterization 9**. : _Let \(G\) be a connected graph, let \(T\) be an atom tree of \(G\), and let \(S\) be a minimal separator of \(G\). Then, the edges of \(AG(G)\) associated with \(S\) are the pairs of nodes of \(T\) whose endpoints are in different connected components of \(T(\mathcal{A}_{S})-E_{S}\), where \(\mathcal{A}_{S}\) is the set of nodes of \(T\) containing \(S\), and \(E_{S}\) is the set of edges of \(T\) associated with \(S\)._  
Proof. : Let \(\{X,Y\}\) be a pair of nodes of \(T\). Let us show that \(XY\) is an edge of \(AG(G)\) associated with \(S\) if and only if \(X\) and \(Y\) are in different connected components of \(T(\mathcal{A}_{S})-E_{S}\), i.e., by Characterization 8, and the fact that \(T(\mathcal{A}_{S})\) is connected, that there is an edge \(X^{\prime}Y^{\prime}\) of \(P_{T}(X,Y)\), such that \(S=X\cap Y=X^{\prime}\cap Y^{\prime}\) if and only if \(P_{T}(X,Y)\) is a path in \(T(\mathcal{A}_{S})\) having an edge \(X^{\prime}Y^{\prime}\) in \(E_{S}\). \(\Rightarrow\): as \(S=X\cap Y\)\(P_{T}(X,Y)\) is a path in \(T(\mathcal{A}_{S})\), and as \(S=X^{\prime}\cap Y^{\prime}\), \(X^{\prime}Y^{\prime}\) is in \(E_{S}\). \(\Leftarrow\): as \(X\) and \(Y\) are in \(\mathcal{A}_{S}\), \(S\subseteq X\cap Y\subseteq X^{\prime}\cap Y^{\prime}=S\), and therefore \(S=X\cap Y=X^{\prime}\cap Y^{\prime}\). The algorithm Forest Join computes the edges of the atom graph of \(G\) according to Characterization 9. Given an atom tree \(T\) of \(G\) and its subset relation _sub_, it scans the edges of \(T\), and for each edge \(AB\), it computes the set of edges of the atom graph associated with the minimal separator \(S\) associated with \(AB\) if it has not been computed yet, _i.e._, if \(AB\) does not belong to the set of edges computed so far. It calls the algorithm Components (Algorithm 2), which computes the connected components of the forest \(T(\mathcal{A}_{S})-E_{S}\) defined in Characterization 9. The relation \(sub\) enables us to compute these components at no extra cost than a simple tree search: \(T(\mathcal{A}_{S})\) is the subtree of \(T\) whose edges \(XY\) are associated with supersets of \(S\), i.e., satisfy \(sub(AB,XY)\), and \(E_{S}\) is the set of edges \(XY\) of \(T\) associated with \(S\), i.e., such that \(sub(AB,XY)\) and \(sub(XY,AB)\). In the algorithm Components, \(k\) is the current number of connected components, \(C_{1},\ldots,C_{k}\) are the current components, \(Queue\) contains the nodes of \(T\) that are reached but not processed yet, and for each reached node \(X\), \(numComp(X)\) is the index \(i\) of the component \(C_{i}\) containing \(X\), and \(pred(X)\) is the node of \(T\) from which it has been reached (and which should not be processed again). ```
input :An atom tree \(T=(\mathcal{A},E_{T})\) of a connected graph \(G\) and its subset relation \(sub\). output :The atom graph of \(G\). \(E^{\prime}\leftarrow\emptyset\); foreach\(AB\in E_{T}\)do if\(AB\
otin E^{\prime}\)then // the edges associated with \(A\cap B\) are not in \(E^{\prime}\) yet \(CompSet\leftarrow\text{\bf Components}(T,AB,sub)\); foreach\(\{C,C^{\prime}\}\subseteq CompSet\)do foreach\(X\in C\)do foreach\(Y\in C^{\prime}\)do Add \(XY\) to \(E^{\prime}\);  end foreach  end foreach  end foreach return \((\mathcal{A},E^{\prime})\);
```  
**Algorithm 1**Forest Join. **Example 3**.