The 3D ACIS® Modeler (ACIS) is Spatial’s prominent 3D solid modeling engine. 3D InterOp is a CAD data translation framework (Interoperability)
Ordering Graphs
From DocR20
Ordering a graph in some manner is one of the more fundamental graph operations that yields a wealth of important relationship information. One way is to order the vertices by the distance, or "hops", that they are from a given vertex. The distance is not the length of the lines drawn for the edges, but the number of vertices encountered when tracing along the edges from one vertex to another specified vertex. The distance between two vertices in a graph is the number of vertices of the shortest path in the graph from one vertex to the other.
The generic_graph::order-from method of ordering a graph works well for trees and linear graphs. The two graphs show in the following figure have been ordered by distance from vertex A. Because ordering uses a single vertex as the starting point, it is possible to have multiple nodes in a graph that are the same distance away, as is shown with F, E, and D, or G and H.
If a graph is cyclic, then it may be ordered by the order_cyclic method. This sets a given vertex's order to zero and the other vertices in a clockwise cyclic order as shown in the following figure.
Both generic_graph::order_cyclic and generic_graph::order-from ordered graphs may be negated, and they negate in different ways. The following figure shows the negations of the graphs from Figure. Ordering Graphs and Figure. Cyclic Ordering. Because ordering uses a single vertex as the starting point, it is possible to have multiple nodes in a negated ordered graph that are 0, as is shown with G and H.
Another way to order a graph G is to order it with respect to an ordered graph H such that G is a subgraph of H. The order_with method imposes the order of H onto G and rescales the ordering on G to remove gaps. The type of ordering (that is cyclic or not) is inherited from the ordered graph H. The following figure shows a linear graph imposing its order on a subgraph.
The following figure shows a cyclic graph imposing its order on a subgraph.
Once a graph has been ordered, the order of a vertex may be found by calling the get_order method and the maximum order in the graph may be found by calling the max_order method.
Given an ordered graph, a subgraph may be formed by calling either of the two subset methods of the generic_graph class. One method takes in two integers and the other takes a law pointer.
The subset method with two integers takes a and b and returns a subgraph in one of two ways.
- If a<b, then the set of all vertices with orders between a and b is returned along with all edges that have both of their adjacent vertices in this set.
- If b<a, then the set of all vertices with orders not between a and b is returned along with all edges that have both of their adjacent vertices in this set.
The subset method with a law returns the set of all vertices such that their order evaluates as true along with the all edges that have both of their adjacent vertices evaluating as true orders.
In the following figure, the graph on the left has been ordered and subsetted from 1 to 3, resulting in the graph on the right.
In the following figure, the graph on the left has been ordered and subsetted from 4 to 1, resulting in the graph on the right. Note that this is a cyclic graph in ascending order. Hence, the result is (E, F, A, B) instead of (E, D, C, B).
In the following figure, the graph on the top has been subsetted with the law even?(x) which returns true if x is even. In addition to even?, the laws odd?, int?, and prime? are available.
Class methods from generic_graph associated with ordering include:
- generic_graph::subset()
- generic_graph::order_from()
- generic_graph::order_cyclic()
- generic_graph::order_with()
- generic_graph::negate()
- generic_graph::get_order()
- generic_graph::max_order()
while Scheme extensions include:
