FLOAT

FUNDAMENTAL RESEARCH LAB

Laboratory for Computational Revolt

General architecture

In order to organize information we use DAG directed acyclic graph (directed graphs without directed cycle) in which their edges possess weight. Node (or cell) is any information unit: text, image, sound or other kind of data. Two nodes (units) are connected by directed edge. Each DAG can be treated as a POSET (partially ordered set = a set with binary relation which is reflexive, antisymmetric and transitive). Each poset can be draw as Hasse diagram (upward drawing DAG). Every DAG has at least one topological sort (linear extension), and we can use depth-first search to find such an ordering. What we call weights are numbers from range [0,50]. These numbers represent a degree of our believing that one document implicates another, in other words this is a degree of our believing that a document q has 'more information' than p or p is 'less defined' than q. By selecting two nodes and starting Dikstras algorithm the user may find the shortest path which has in the same time strongest connection between nodes. So the user can check a probability that information that is contained in one of them implicates information contained in another. As a result the user can see a drawing of this path and a number from the range [0,50].

architecture.png

The data structure is as simple as you can get : a vector of Nodes, a vector of Edges. The owner of these vectors defines an interface for the rest of the application to access the graph, and there are some very nice algorithms here. In particular, there is a path searching algorithm, to detect potential cycles, as well as conversion from DAG->Hasse, and DAH->LinearExtensions. DAG->LE can be extended to any number of extensions, limited only by the graph, depending how the edges are searched.