From OpenCog
(Redirected from Outgoing set)
Jump to: navigation, search

A Link is a type of Atom that connects (associates together) other Atoms. The outgoing set of a Link is that set of atoms that it has associated together into one. Special cases of a Link include the OrderedLink and the UnorderedLink, which, as the names suggest, maintain either a strict sequential ordering of their contents, or imply an arbitrary order. Another example is the SetLink, which is explicitly meant to resemble the "set" of set theory. Likewise, the AndLink and OrLink are meant to be interpreted as the boolean-logic operators that their names suggest.

The AtomSpace is used to ensure that Links are unique, and are identified only by their type and outgoing set (and by nothing else). That is, once a Link is inserted in an atomspace, it becomes the sole, unique copy. Inserting a second link of the same type and outgoing set just returns the first Link.

The type and outgoing set of the link cannot be changed: OpenCog atoms are immutable objects. This means that if your program or algorithm is holding a reference to a Link, then it is guaranteed to be there, and not to change out from under you.

The "meaning" of a Link

Links can be understood in several different kinds of ways. A Link containing only two atoms A,B can be thought of as an ordered pair (A,B) or an arrow A->B. Ordered pairs are commonly used to represented the (directed) edges of a graph, and thus Links can be thought of as edges. A collection of Links then forms a graph.

However, Links can also contain more than two atoms, and thus it is sometimes said that links are "hyperedges", and that the collection of them form a hypergraph.

A single Link that contains many atoms can be imagined to be a vertex in a (downwardly-directed) tree, and it's outgoing set as the child-vertexes in the tree. Since any atom can appear in multiple Links, this implies that any given branch of a tree might also be shared by other trees; Thus, a collection of Links is then a "forest" or a "multi-tree", and can be envisioned as a dense hedge of intertwined shared branches.

Note that the opencog notion of a hypergraph is actually a "generalized" hypergraph: links are allowed to contain other links, and not just nodes.

As a relational algebra

A Link can be thought of as a relation R between a set of atoms. The outgoing set of relationship R is the list of arguments of that relation. The incoming set of an entity E is the set of relationships that take E as an argument. A collection of links then forms a relational algebra. The pattern matcher is used to implement the query mechanism and the query language of the relational algebra.

Scheme interface

Links can be created, manipulated and destroyed at the scheme shell command prompt. See scheme for details.

Python interface

Links can be created, manipulated and destroyed at the scheme shell command prompt. See python for details.

C++ programming interface

The core structure of the Link is clearly reflected in the C++ interface:

class Link : public Atom
       std::vector<Handle> _outgoing;
       Link(Type, const std::vector<Handle>&);
       const std::vector<Handle>& getOutgoingSet()
            { return _outgoing; }
       size_t getArity() const {return _outgoing.size(); }
       std::string toString() const;
       std::string toShortString() const;

toString() and toShortString() return string representations of the link.

getArity() returns the arity of the Link, i.e. the number of Atoms which participate in the relationship it represents.

getOutgoingSet() returns the outgoing set of the Atom.

Incoming and Outgoing Sets

The outgoing set of a Link is the set of atoms that it encompasses. The incoming set is the converse.

That is, one can visualize a Link as vertex in a directed tree, and its outgoing set being all of the child-vertexes under that vertex. By default, the outgoing set is always an ordered set, unless the link is a type of UnorderedLink.

Since, in OpenCog, an Atom can appear in many different trees (in many different links), the incoming set is the set of all the Links in which an atom might appear. The incoming set is always unordered, and there is no (natural) way to order it.

Below is an example. Consider an AtomSpace formed by four Nodes A, B, C and D and four (ordered) Links:

Link Outgoing set
L1 {A, B}
L2 {A, C}
L3 {D, B}
L4 {L1, A}

The following table shows the incoming and the outgoing sets of each Atom:

Atom Incoming set Outgoing set
A {L1,L2,L4} null
B {L1,L3} null
C {L2} null
D {L3} null
L1 {L4} {A,B}
L2 null {A,C}
L3 null {D,B}
L4 null {L1,A}

The outgoing set is stored in an std::vector of smart pointers to Atoms. The incoming set is stored inside the Atom and represented as a set of weak pointers. They are stored as weak pointers, to avoid the memory management issues that would otherwise ensue from reference counting of circular graphs. That is, Links always form a DAG, with the downward edges being smart pointers, and the upwards edges being weak pointers.