Boolean Operations on Graphs
List of: Discussion Topic
Subjects: Graph Theory
Contents: Kernel

The graph theory subsystem provides for four types of Boolean operations: unite, intersect, subtract and lose boundary, and subtract and keep boundary.

Figure 5-4 shows the union of graph 1 and graph 2, shown in Figure 5-3. The result is a graph whose vertices and edges are the union of the vertices and edges of the original graph. As such, there are no duplicate vertices and edges even though they appear in the individual graphs.


Figure 5-3. Graphs 1 and 2 for Boolean Operations


Figure 5-4. Graph 1 Union with Graph 2

Figure 5-5 shows the intersection of the two graphs which keeps only those vertices and edges that are common to both.


Figure 5-5. Graph 1 Intersected with Graph 2

Figure 5-6 and Figure 5-7 show the subtraction operations. The result of subtraction can be ambiguous, because an edge (such as B-E) might be half in a graph. For this reason the subtract method of generic_graph takes a logical option that tells if such edges should be kept or not. Figure 5-6 shows graph 2 subtracted from graph 1 with half edges not kept and Figure 5-7 show the half edges being kept.


Figure 5-6. Graph 2 Subtracted from Graph 1 Not Keeping Boundary


Figure 5-7. Graph 2 Subtracted from Graph 1 Keeping Boundary
PDF/KERN/05GRAPH.PDF
HTM/DATA/KERN/KERN/05GRAPH/0003.HTM