Introduction to Paths and Traversals

E-Mail Comments to: doc@cyc.com
Last Update: 10/30/1998 16:25:38
Copyright© 1996, 1997, 1998 Cycorp. All rights reserved.

Return to Table of Contents
Search for Constants by Name (In all files, not just this one.)

Detailed Introduction to Paths and Traversals in Cyc

DRAFT ONLY

by Fritz Lehmann, Oct. 1997

The system of paths and traversals in Cyc has to cover two different kinds of applications: first, the real-world paths (roads, sea-lanes, air-lanes, footpaths, blood vessels, wires, etc.) of everyday life, and, second, the abstract paths of links in formal systems such as transition diagrams, graph theory, or symbolic representations of real-world systems. Cyc's path system is designed to use the same basic language, as much as possible, to describe both kinds. This makes the system more complicated than usual models of networks.

Cyc has separate concepts of: paths, directed paths, traversals, and trajectories. Every motion has a #$Trajectory, but a motion may or may not stay on pre-existing paths. If it does follow paths in some path network, it follows a certain #$Traversal of those paths (a traversal follows paths in a certain direction and in a certain order).

A path (#$Path-Generic in Cyc) may be a physical object or place (or series of them) in the world, or it may be a purely abstract thing. Either kind can be associated with a formally specified #$PathSystem, and in the case of abstract paths they are represented only with respect to a specified #$PathSystem. Structurally, every #$Path-Generic is either a #$Path-Simple (with no cycles) or else a #$Path-Cyclic (a cycle).

There are things in the world that are commonly used as paths (roads, footpaths, pipes, wires, etc.). These are usually things or places along which certain things (or fluids or items of information) customarily move. Usually, something ordinarily moves in at one end and moves out at the other end (either in one direction only, or in both directions). These are instances of #$Path-Customary in Cyc. Under this description, an orange is not a #$Path-Customary, even though some ants might very well use an orange as a path in some circumstances.

(Keep in mind that, in Cyc, #$genls siblings are not necessarily disjoint.)

Most kinds of #$Path-Customary are also kinds of #$Path-Spatial, i.e., paths through space.

A path may be a path within a specified path system (a #$PathSystem), but the path system may be left unspecified for customary paths. A #$Path-Customary may or may not be associated with a specified #$PathSystem, whereas any other #$Path-Generic is always associated with a #$PathSystem. In a specified system of ant paths, for example, an orange could indeed be used as a link or path, even though that is not its most customary use. For these systems, the system itself is named in most path-related statements; for a #$Path-Customary, though, an assumed path system may be mentioned or it may be omitted. Even if it is omitted, there is an assumed background #$CustomarySystemOfLinks for every type of #$Path-Customary. See below for a more detailed list of kinds of #$Path-Customary. [Note that there is no collection in Cyc called "PathInSystem"; almost anything could be designated as a path in some particular system -- the predicate (#$pathInSystem PATH SYSTEM) is used in that case.]

A single path cannot cross itself or go back along itself. In a #$Path-Simple, the two end nodes must be distinct, and no point can occur on the path more than once. In a #$Path-Cyclic, the beginning and ending nodes are the same. (A figure-eight is neither a #$Path-Simple nor a #$Path-Cyclic, because it is self-crossing. In Cyc, a figure-eight is not a #$Path-Generic at all, although a #$Traversal or #$Trajectory may follow a figure-eight pattern. The figure-eight is a #$PathSystem containing two #$Path-Cyclics.)

The Basic Elements

The basic elements of Cyc's path representation are non-self-crossing paths and things (called "points") on paths.

Path Systems

As stated above, paths may be described as paths in particular #$PathSystems, but for a #$Path-Customary the surrounding network of paths (of the same general kind) can often be assumed and not mentioned explicitly; it is called a #$CustomarySystemOfLinks.

Unlike the #$CustomarySystemOfLinks, a #$PathSystem must be specified as specific sets of points, nodes, and zero or more links (and possibly loops). A single node with no links or loops qualifies as a (degenerate case of) #$PathSystem. Several Cyc predicates assume that the path is in a specified path system; these predicates' names end with "InSystem". An object itself, whether tangible or abstract, is not inherently a "node" or "link"; it is only a node or link in one or more particular #$PathSystems.

A path system may be specified by some external authority (e.g., the Internet backbone, or the US Interstate Highway System), or you may specify it directly in Cyc as a #$Tuple of sets, or in any other way that clearly determines the elements.

If A Path System Is Specified

If a #$PathSystem is specified, the following elements are given: certain designated points are called "nodes" of the system, there are node-to-node links of the system, there may be other (non-node) "points" along the links of the system, and paths of the system. (In certain discretely formalized path systems, there may also be also "loops" of the system; a loop goes from a node back to itself with no other points along it.)

These are not collections in Cyc; they are indicated by predicates that require specifying a #$PathSystem. These include: #$pointInSystem, #$pathInSystem, #$linkInSystem, #$nodeInSystem, #$loopInSystem, #$deadEndInSystem, #$junctionInSystem and #$cycleInSystem. Reasons: First, anything could be a point on some path or other, depending on how we look at it, and what systems we consider it to be in -- and anything can be deemed a path. Second, whether a point on a path is a node and whether a certain path is a link depend on the specified #$PathSystem. The #$PathSystem determines not only how they are related to other points and paths, but also it determines which intermediate points along a path are designated as nodes of the system.

A link is a path between two nodes, with no intervening nodes. There can be any number of "points" along a link, but no nodes. There could be zero points, one point, two points, any finite number of points, or an infinite numbers of points along the link. Every junction, and every dead-end, and every isolated point of the system must be a node of the system.

A node of a #PathSystem can be a junction (with three or more paths joining at it) of the system, a dead end (with only one link ending there) of the system, or it can be a designated intermediate point along a path (two links join at such a node).

Multiple, distinct links may join the same two nodes. (In graph theory a system with such "parallel" links is sometimes called a "multigraph"; Cyc has #$Multigraph.) In the real world there are often two or more parallel roads connecting the same two nearby towns.

A path may consist of part of a link, a single link, two or more links joined end-to-end, or one or more links along with parts of the end-links. Thus a path could start at a (non-node) "point" part-way along link A, continue through links B and C, and go partway along link D, stopping at a (non-node) point along link D.

In some #$PathSystems, in addition to paths between nodes there are "loops" -- a loop is a path that goes out from a node and returns directly back to that node without passing through any other points. A loop is a special case of a #$Path-Cyclic. (See the Technical Note below.) Loops are useful in some formal path systems like #$Multigraphs.

For a #$Path-Customary that is not defined in terms of any particular #$PathSystem, a so-called "point" may be a large area. Austin can be a "point" on highway I-35 while at the same time Texas is a "point" on I-35. Thus one so-called "point" on such a path can overlap or be entirely within another "point". The relation of this type of "point" to the path is indicated by the predicate #$pointOnPath. The more general #$onPath predicate can also be used, to refer to 'path-on-path' or 'movingObject-on-path' relations, or the like.

In a specified #$PathSystem, on the other hand, distinct "points" are always separate and non-overlapping, whether the paths are customary or not, and the relation to the path is #$pointOnPath.

If No PathSystem Is Specified:

A #$Path-Customary might not have an associated specified #$PathSystem. In that case, there are a number of features that assume that the related items are all paths of the same general type (highways, railroads, veins, bronchial tubes, etc.). The "general type" means the customary type (#$PathType) associated with the main use or function. (For roads, it is usually the most general collection of specializations of #$Path-Customary that allows driving. For pipes, the most specific type that allows passageFor each of these #$PathTypes, any instance may be deemed to occur within a possibly-unspecified #$CustomarySystemOfLinks.

An individual element of the collection #$JunctionOfPaths, in the case of #$BronchialTubes, is a junction of bronchial tubes (#$BronchialTubeSegment) where three or more bronchial tubes (#$BronchialTubeSegments) join together; blood vessels are not involved.

Similarly a railroad track may end at a #$pathTerminus that is a dead end for the railroad line even if there may be a footpath that extends beyond the end.

A #$SimpleSegmentOfPath is any #$Path-Customary that has no branches along it. Such "branches" would have to be branch paths of the same general type, thus a railroad track section is a #$SimpleSegmentOfPath even if several dirt roads "branch off" of it. (Two specializations are: #$SimpleUnloopedSegmentOfPath and #$SimpleLoopedSegmentOfPath).

A branching of a #$Path-Customary can be indicated with one of two predicates, #$branchesInto or #$sideBranches, and the branching junction can be reified as an instance of #$BranchingJunction or #$SideBranchJunction, respectively. In a #$BranchingJunction a main path ends where it #$branchesInto smaller paths, whereas in a #$SideBranchJunction a small side path joins a main path that continues on.

Directed Links and Paths

Links and paths as described so far have no associated directionality. A link simply joins node "a" with node "b" and "b" with "a".

However, an instance of #$Semi-DirectedPathSystem (a specialization of #$PathSystem) may assign "direction" to one or more of its links. In such a #$PathSystem, a directed link may be from "a" to "b", which does not imply that the link is a directed link from "b" to "a". The predicate #$linkFromToInSystem is used for such links. For example, this is used to state the directions of one-way streets in a specified municipal street system.

A link with direction from "a" to "b" can also be given the other direction from "b" to "a", thus it has both directions making it a "bidirected link" or "undirected link". If all links of a #$PathSystem are bidirected/undirected, it is an #$BidirectedPathSystem.

If the #$PathSystem has loops, they are all considered to be bidirected/undirected. (There are reasons for this. See the Technical Note below.)

Within a #$Semi-DirectedPathSystem, directed paths of the system are determined by their directed links. In a directed path, all its links must be directed in the same way along the path. Bidirected links point both ways and are always allowed in a directed path.

The hierarchy of specified-path-system collections includes the following:



Traversals

The notion of traversal is separate from that of path.

A traversal is the trace of a (real or possible) "walk" or movement along some links or sub-paths of a path system. Unlike a path, a traversal can cross itself and/or go back along itself. Every traversal has a corresponding sequence of (not-necessarily-distinct) sub-paths passed through in the traversal. A traversal of a path system must go along (be confined to) its paths.

If a traversal is along directed paths (of a #$Semi-DirectedPathSystem), it must go in the directions of the paths it is on. A traversal generates a sequence of paths passed through, including the links traversed. A traversal may go around a cycle many times before exiting, and it may include traversing loops. (In contrast, a path cannot include cycles or loops part-way along it.)

#$Traversal is a collection. A single traversal is representable as a sequence (represented using #$TheList and #$TraversalFromToFn) of paths traversed. Many different sequences of paths traversed may correspond to the same traversal; it depends how the whole traversal is decomposed into subpaths traversed. A traversal can be a trace within a specified #$PathSystem, or it can be a trace of any end-to-end customary paths (#$Path-Customary).

To represent a traversal with a list of paths, it is necessary also to include the starting point or node; otherwise, in the case of one or more links between a total of two nodes, the list of links would be ambiguous as to which direction they are traversed through.

Trajectories

A #$Trajectory consists of the actual points of space swept through by a moving object, or traced by a particular point in the object. A trajectory is not the same as a #$Traversal of a #$PathSystem. A moving object has a trajectory whether or not it follows any #$PathSystem. If a trajectory moves along paths in a given spatial path system, and stays within the confines of the paths, then it corresponds to a particular #$Traversal in the system. The definitions that determine which trajectories are considered to "follow" or "obey" or "be confined to" the path system (i.e., to go only along paths) depend on the path system or the types of the paths. Even if the trajectories stay within a path system, many different trajectories may have the same traversal; there could be trivial variations in a vehicle's path on a highway, for example, all of which traverse that section of highway.

A trajectory that is also a traversal may trace over a simple path, or a cycle (a single trajectory can go around and around a cycle any number of times), or a complicated network. Descriptions of trajectories are almost always given relative to a particular background space that is considered fixed.

Example: A Car Drive

You drive your car from a location in Austin to a location in San Antonio. Interstate 35 is a #$Path-Customary, as are the streets of Austin and San Antonio. I-35 is also a path-in-system, where the system is the US Interstate Highway system. It is also a path-in-system of many different path systems, such as the Paved Roads In Texas system. Suppose that, in the US Interstate Highway system, only big cities and junctions of interstates are considered "nodes". Then your trip will pass through a few "nodes" and an infinite number of intermediate "points" on the way. Little towns on I-35 between Austin and San Antonio would be "points" in this system. In the Paved Roads of Texas system, however, you may pass through hundreds of nodes, at least one for each highway or street intersection you pass through.

Your trajectory would be the actual space of your motion. Suppose you make a U turn and then make a second U turn and continue on. The U turns would be reflected in your trajectory and possibly in your traversal, but they would not alter the underlying "path". A single path does not cross the same point in space twice (unlike a traversal or trajectory, which may). If you drive erratically veering all over the highway it affects your trajectory but it has no effect on the traversal -- you have traversed a directed link if you enter it at the start end and exit it at the other end, regardless of your trajectory within the link.


The Key Collections, Predicates and Functions

The following are very terse remarks about each concept, relation and function. For more detail, see the actual comment on each item.

Specified Path Systems

#$PathSystem -- a specified system of points, nodes and zero or more links, (and possibly loops) that are indicated by predicates -- it may be an elaborate network.

#$SimplePathSystem -- same, but at most only one direct link between any two nodes, and no loops allowed.

#$Semi-DirectedPathSystem -- every link has one direction or both directions (any loops are bidirectional).

#$DirectedPathSystem -- every link has just one direction (but any loops are bidirectional).

#$BidirectedPathSystem -- (undirected) every link has both directions (any loops are also bidirectional).

#$Multigraph -- discrete path system with no non-node points. May have parallel links between two nodes, and loops.

#$DirectedMultigraph -- same, but with directed links.

#$SimpleGraph-GraphTheoretic -- discrete bidirected path system with no non-node points, no loops, and at most one link between any two nodes. The intersection of Multigraph and SimplePathSystem.

#$ConnectedPathSystem -- single-piece path system with no disconnected pieces.

Collections Not Requiring A Specified Path System

#$Path-Generic -- any kind of non-self-crossing path, either natural, or abstract-in-a-system; simple or cyclic

#$Path-Customary -- something normally used as a path for movement or information transfer. There may or may not be an explicitly given PathSystem. When there is none, then the assumed path system is a not-formally-specified #$CustomarySystemOflinks based on the general #$PathType. (Often it is also a #$Path-Spatial.)

#$PathArtifact -- something deliberately made for use as a path

#$Path-Simple -- two-ended path, no cycles

#$Path-Cyclic -- cycle with start/end point

#$JunctionOfPaths -- junction of paths of same general type

#$ThreeWayJunctionOfPaths

#$FourWayJunctionOfPaths

#$BranchingJunction -- one main path stops and #$branchesInto little ones

#$SideBranchJunction -- a main path has #$sideBranches joining it and it continues on past the junction

#$NonintrusiveJunction -- main path continues past junction where other path doesn't affect main path

#$SimpleSegmentOfPath -- path with no junctions along it

#$SimpleLoopedSegmentOfPath -- same, as loop from point back to itself

#$SimpleUnloopedSegmentOfPath -- same, but not a loop, hence two distinct ends

#$CustomarySystemOfLinks -- a system of #$Path-Customary links

Path Predicates Not Requiring a Specified Path System

#$onPath -- thing a is on path p
#$pointOnPath -- thing a is a stationary thing on path p
#$betweenOnPath -- a is between b and c on path p
#$subPaths -- p is a sub-path of q
#$pathTerminus -- point a is an end of path p with no further paths of the same general type extending beyond it
#$adjacentPathsAtJunction -- paths that join at junction
#$endsOfPathSegment -- relates path to its endpoints
#$branchesInto -- main path branches into little paths
#$sideBranches -- a side path connects along a main path
#$pathBetween -- p is a path with a and b as ends
#$pathConnects -- path p connects a and b (and may go on)
#$linksOfCustomarySystem -- relates a #$Path-Customary or
#$SimpleSegmentOfPath to a #$CustomarySystemOfLinks

Path Predicates Requiring A Specified Path System

The following predicates are always used with a specified PathSystem as the last argument:


#$pointInSystem -- any point in a system, whether it is a node or not.
#$nodeInSystem -- a node -- a point that is a junction, dead-end, designated intermediate point or an isolated point.
#$deadEndInSystem -- a node with only one link joining it.
#$junctionInSystem -- a node at which three or more links join, or at which loops and links join.
#$threeWayJunctionInSystem
#$fourWayJunctionInSystem
#$isolatedNodeInSystem -- an isolated point, not linked to any other, and having no loop.
#$linkInSystem -- a link of a path system.
#$loopInSystem -- a loop of a path system (a path from a node back to itself containing no other points) .
#$pathInSystem -- a path which is within a path system.
#$cycleInSystem -- a cycle: a loop or else a cycle made of two or more links (and the same number of nodes).
#$linkBetweenInSystem -- a link links two specified nodes.
#$pathBetweenInSystem -- a path joins two specified points.
#$connectedInSystem -- there is some path connecting two specified points


#$subPathSystems -- subsystem (a subgraph if the system is discrete and has no non-node points).

#$linkClosedSubSystems -- sub system with all links induced by set of points.
#$pointClosedSubSystems -- sub system preserving all the path-points from the larger system

#$maximalConnectedSubSystems -- maximal connected piece
#$reductionOfPathSystems -- relating a #$PathSystem and its underlying #$Multigraph. #$underlyingGraph -- relates #$PathSystem to the #$Multigraph that is underlying the given #$PathSystem.
#$directionPreservingSubSystems -- subsystem that preserves directions of links.

The following two functions are used to retrieve paths #$JoinPathsFn -- function takes a chain of paths, returns their concatenation.
#$SubPathBetweenFn -- function takes a path and two points on it, returns the unique sub-path.
#$JoinPathsIntoCycleFn -- function takes a chain of paths, returns a cycle that is obtained by concatenating the paths in the chain.

The following functions retrieve sets of elements of a path system:

#$PointsFn -- result is the set of "points" of a path system
#$NodesFn -- result is the set of nodes of a path system
#$LinksFn -- result is the set of links of a path system
#$LoopsFn -- result is the set of loops of a path system
#$SetOfLoopsAtNodeFn -- result is the set of all loops at a given node in a system.
#$SetOfLinksAtNodeFn -- result is the set of all links at a given node in a system.
#$NumberOfLinksAtNodeFn -- result is the cardinality of the set of links at a given node in a system.
#$LinksCut-SubSystemFn -- result is the subsystem of a given #$PathSystem, obtained by cutting off the given set of links.
#$NodesCut-SubSystemFn -- result is the subsystem of a given #$PathSystem, obtained by cutting off the given set of nodes.
#$PathFromFn -- result is the point in the given #$DirectedPathSystem, which is the starting point of the given path in the system.
#$PathToFn -- result is the the point in the given #$DirectedPathSystem, which is the ending point of the given path in the system.
#$SingleSourceFn -- result is the single source node in the given #$BoundedDirectedPathSystem.
#$SingleSinkFn -- result is the single sink node in the given #$BoundedDirectedPathSystem.
#$OutwardLinkSetFn -- result is the set of outward links at a given node in a #$Semi-DirectedPathSystem.
#$InwardLinkSetFn -- result is the set of inward links at a given node in a #$Semi-DirectedPathSystem.

Beyond Paths: Traversals and Trajectories

#$Traversal -- all the paths traversed in a walk through a path system, in order. May be self-crossing. Often represented using (TraversalFn POINT LISTOFPATHS POINT). #$TraversalFn -- A function that returns a #$Traversal.
#$traversalFrom -- relating a #$Traversal and a "starting point" of it.
#$traversalTo -- relating a #$Traversal and an "ending point" of it.
#$pointOnTraversal -- relating a point and a #$Traversal in the sense that the point is somewhere along the #$Traversal.
#$subTraversals -- relating a #$Traversal and its subtraversals.
#$traversalFromToInSystem -- a #$Traversal presented in a #$PathSystem with its definite "starting point" and "ending point" in the system.
#$traversalPassesThrough -- relating a #$Traversal and a point on it in such a way that the #$Traversal does not stop when reached that point.
#$traversalInSystem -- a traversal is within (by homomorphism) a PathSystem, i.e. is a "walk" in the system.
#$traversalInSystem-OrderObserved -- a #$Traversal presented in a #$Semi-DirectedPathSystem whose direction is consistent with the direction of links in the system.
#$SubSystemUnderTraversalFn -- every #$Traversal presented in a #$PathSystem determines a unique subsystem of it that the traversal traversed.

#$Trajectory -- the line of points in space traced by a moving object or by some point in the object. May be self-crossing.

#$Trajectory-SweptSpace -- the points in space swept through by all the points in a moving object during its movement. May be self-crossing.

A Technical Note on Loops

Currently, there can't be a "point" along a loop (other than its one node). See #$loopInSystem. For real-world path systems (including non-discrete ones), though, it may be desirable to allow loops with "points", and hence subpaths, along loops. A road could exit a designated node, wander around, and return to the node without passing through any other nodes. This road could have any arbitrary number of points, hence subpaths, on it. There are few practically useful cases of this (where you could not simply designate one of the points to be a node, thereby converting the loop into an ordinary cycle), but a fully general system might allow this. Unfortunately, this would impose a considerable technical burden on the axiom-writer. Not only must points on loops, and paths including parts of loops, be considered as special conditions of many rules, but the two special cases of loops with no points, and with exactly one point, are degenerate cases for which directionality, etc., is hard to define properly.

[A loop in such a system may have a direction like any other Path-Generic in the system, UNLESS the loop is discrete and it has only one point, or no points, other than the node from which it originates. In the latter special cases, the loop would not have two distinguishable directions, so all such loops might always be considered bidirectional.]


Go to Top