Leucippus

Leucippus is a generic formalism for describing directed graphs. Its primitives include nodes and edges, their typology and the graph properties of the edges. It is used by ArcEnCiel as the main input format for viewpoints.

Leucippus is presented in p115-135 of this thesis, along with a full example.

Leucippus has been developed in order to generalize every graph-based formalisms with the focus of studying the graphs as viewpoints. It is designed as a pivot between several formalisms, and it combines two layers of abstraction:

• Instance-level layer
  • Nodes: the standard graph node, with a name. Nodes are typified.
  • Link: the named entity that binds two nodes. Links are both generic (a single link can be used several times) and typified (as potentially sharing properties with other links).
  • Edges: the actual binding, describing a directed relation between two nodes which translates into a link.
• Concept-level layer
  • Node types: used to differentiate nodes; can be used to translate node types that already exist in a formalism (for instance UML), or to break down a graph structure into node and links only (for instance cardinalities).
  • Link types: express the grouping of several links in a single type sharing properties. For example, both 'is a' and 'may be a' can be links with type 'specialization' (which is asymmetric, transitive and non-reflexive).
  • Link properties: since not every link of the Leucippus graph corresponds to exactly one link in the initial formalism, properties such as symmetry can be specified to give a signature to a link type.

The dtd is pretty straightforward, and can use either an english of a french naming convention.

<!ELEMENT graph (nodes, links, edges, nodetypes, linktypes)>
<!ELEMENT nodes (node*)>
<!ELEMENT node EMPTY>
<!ATTLIST node id ID #REQUIRED>
<!ATTLIST node name CDATA #IMPLIED>
<!ATTLIST node type IDREF #REQUIRED>
<!ELEMENT links (link*)>
<!ELEMENT link EMPTY>
<!ATTLIST link id ID #REQUIRED>
<!ATTLIST link name CDATA #IMPLIED>
<!ATTLIST link type IDREF #REQUIRED>
<!ELEMENT edges (edge*)>
<!ELEMENT edge EMPTY>
<!ATTLIST edge link IDREF #REQUIRED>
<!ATTLIST edge from IDREF #REQUIRED>
<!ATTLIST edge to IDREF #REQUIRED>
<!ELEMENT nodetypes (nodetype*)>
<!ELEMENT nodetype EMPTY>
<!ATTLIST nodetype name ID #REQUIRED>
<!ELEMENT linktypes (linktype*)>
<!ELEMENT linktype (property*)>
<!ATTLIST linktype name ID #REQUIRED>
<!ELEMENT property EMPTY>
<!ATTLIST property name ID #REQUIRED>
<!ATTLIST property value CDATA #REQUIRED>

(property value must be “always”, “never” or “variable”).

<!ELEMENT graphe (noeuds, liens, associations, typesnoeuds, typesliens)>
<!ELEMENT noeuds (noeud*)>
<!ELEMENT noeud EMPTY>
<!ATTLIST noeud id ID #REQUIRED>
<!ATTLIST noeud nom CDATA #IMPLIED>
<!ATTLIST noeud type IDREF #REQUIRED>
<!ELEMENT liens (lien*)>
<!ELEMENT lien EMPTY>
<!ATTLIST lien id ID #REQUIRED>
<!ATTLIST lien nom CDATA #IMPLIED>
<!ATTLIST lien type IDREF #REQUIRED>
<!ELEMENT associations (association*)>
<!ELEMENT association EMPTY>
<!ATTLIST association lien IDREF #REQUIRED>
<!ATTLIST association orig IDREF #REQUIRED>
<!ATTLIST association dest IDREF #REQUIRED>
<!ELEMENT typesnoeuds (typenoeud*)>
<!ELEMENT typenoeud EMPTY>
<!ATTLIST typenoeud nom ID #REQUIRED>
<!ELEMENT typesliens (typelien*)>
<!ELEMENT typelien (propriete*)>
<!ATTLIST typelien nom ID #REQUIRED>
<!ELEMENT propriete EMPTY>
<!ATTLIST propriete nom ID #REQUIRED>
<!ATTLIST propriete val CDATA #REQUIRED>

(PROPERTY value must be “toujours”, “jamais” or “variable”).

<graph>
  <nodes>
    <node id="0" name="Company" type="concept"/>
    <node id="1" name="Employee" type="concept"/>
    <node id="3" name="Client" type="concept"/>
    <node id="4" name="Supplier" type="concept"/>
    <node id="5" name="Resource" type="concept"/>
    <node id="6" name="Product" type="concept"/>
  </nodes>
  <links>
    <link id="0" name="sold to" type="action"/>
    <link id="1" name="pays" type="relation"/>
    <link id="2" name="has" type="relation"/>
    <link id="3" name="uses" type="relation"/>
    <link id="4" name="makes" type="action"/>
    <link id="5" name="sells" type="action"/>
  </links>
  <edges>
    <edge link="0" from="6" to="3"/>
    <edge link="1" from="0" to="1"/>
    <edge link="2" from="0" to="3"/>
    <edge link="4" from="0" to="6"/>
    <edge link="3" from="6" to="5"/>
    <edge link="5" from="4" to="5"/>
  </edges>
  <nodetypes>
    <nodetype name="concept"/>
  </nodetypes>
  <linktypes>
    <linktype name="action">
      <property name="symmetry" value="variable"/>
      <property name="transitivity" value="never"/>
      <property name="reflexivity" value="variable"/>
    </linktype>
    <linktype name="relation">
      <property name="symmetry" value="variable"/>
      <property name="transitivity" value="variable"/>
      <property name="reflexivity" value="variable"/>
    </linktype>
  </linktypes>
</graph>