|
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
order-from method of ordering a graph works well for trees and linear graphs. The two graphs show in Figure 5-10 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.
|
|
|
|
|
Figure 5-10. Ordering Graphs
|
|
|
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 Figure 5-11.
|
|
|
|
|
Figure 5-11. Cyclic Ordering
|
|
|
Both
order_cyclic and
order-from ordered graphs may be negated, and they negate in different ways. Figure 5-12 shows the negations of the graphs from Figure 5-10 and Figure 5-11. 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.
|
|
|
|
|
Figure 5-12. Negation of the Ordering in Graphs
|
|
|
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 (i.e. cyclic or not) is inherited from the ordered graph
H. Figure 5-13 shows a linear graph imposing its order on a subgraph.
|
|
|
|
|
Figure 5-13. Ordering a Graph with another Graph
|
|
|
Figure 5-14 shows a cyclic graph imposing its order on a subgraph.
|
|
|
|
|
Figure 5-14. Ordering Graphs
|
|
|
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 Figure 5-15, the graph on the left has been ordered and subsetted from 1 to 3, resulting in the graph on the right.
|
|
|
|
|
Figure 5-15. Ordered and Subsetted from 1 to 3
|
|
|
In Figure 5-16, 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).
|
|
|
|
|
Figure 5-16. Ordering Graphs
|
|
|
In Figure 5-17, 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.
|
|
|
|
|
Figure 5-17. Ordering a Graph with another Graph
|
|
|
Class methods from
generic_graph associated with ordering include
subset,
order_from,
order_cyclic,
order_with,
negate,
get_order, and
max_order; while Scheme extensions include
graph:get-order,
graph:order-cyclic,
graph:order-with,
graph:order-from,
graph:show-order, and
graph:negate.
|