OpenMath Content Dictionary: graph1

Canonical URL:

http://www.dse.nl/~postma/graph1.ocd

CD Base:

http://www.openmath.org/cd

CD File:

graph1.ocd

CD as XML Encoded OpenMath:

graph1.omcd

Defines:

arrowset, digraph, edgeset, graph, source, target, vertexset

Date:

2004-06-01

Version:

0 (Revision 13)

Review Date:

2006-06-01

Status:

experimental

This CD defines symbols for handling directed and undirected graphs. Authored by Hans Cuypers and Erik Postma. This version is edited by amc; bugfix JHD after Robbins.

graph

Description:

This symbol represents an undirected graph. It takes two arguments: the vertex set of the graph and the edge set. The vertices can be arbitrary OpenMath objects. Each edge should be a set consisting of two vertices.

Example:

A path of length 2.

OpenMath XML (source)

<OMOBJ xmlns="http://www.openmath.org/OpenMath" version="2.0">
      <OMA>
        <OMS cd="graph1" name="graph"/>
        <OMA>
          <OMS cd="set1" name="set"/>
          <OMI> 1 </OMI>
          <OMI> 2 </OMI>
          <OMI> 3 </OMI>
        </OMA>
        <OMA>
          <OMS cd="set1" name="set"/>
          <OMA>
    	<OMS cd="set1" name="set"/>
    	<OMI> 1 </OMI>
    	<OMI> 2 </OMI>
          </OMA>
          <OMA>
    	<OMS cd="set1" name="set"/>
    	<OMI> 2 </OMI>
    	<OMI> 3 </OMI>
          </OMA>
        </OMA>
      </OMA>
    </OMOBJ>

Strict Content MathML

<math xmlns="http://www.w3.org/1998/Math/MathML">
 <apply><csymbol cd="graph1">graph</csymbol>
  <apply><csymbol cd="set1">set</csymbol><cn>1</cn><cn>2</cn><cn>3</cn></apply>
  <apply><csymbol cd="set1">set</csymbol>
   <apply><csymbol cd="set1">set</csymbol><cn>1</cn><cn>2</cn></apply>
   <apply><csymbol cd="set1">set</csymbol><cn>2</cn><cn>3</cn></apply>
  </apply>
 </apply>
</math>

Prefix

graph (set ( 1 , 2 , 3 ) , set (set ( 1 , 2 ) , set ( 2 , 3 ) ) )

Popcorn

graph1.graph({1 , 2 , 3}, {{1 , 2} , {2 , 3}})

Rendered Presentation MathML

$$\mathrm{graph}(\{1,2,3\},\{\{1,2\},\{2,3\}\})$$

Signatures:

sts

vertexset

Description:

This symbol represents the vertex set of a (directed or undirected) graph. It takes one argument, the graph.

Example:

If Gamma is a graph, the following function tests whether its argument v is a vertex of Gamma.

OpenMath XML (source)

<OMOBJ xmlns="http://www.openmath.org/OpenMath" version="2.0">
        <OMBIND>
	<OMS cd="fns1" name="lambda"/>
	<OMBVAR>
	  <OMV name="v"/>
	</OMBVAR>
	<OMA>
	  <OMS cd="set1" name="in"/>
	  <OMV name="v"/>
	  <OMA>
	    <OMS cd="graph1" name="vertexset"/>
	    <OMV name="Gamma"/>
	  </OMA>
	</OMA>
	</OMBIND>
      </OMOBJ>

Strict Content MathML

<math xmlns="http://www.w3.org/1998/Math/MathML">
 <bind><csymbol cd="fns1">lambda</csymbol>
  <bvar><ci>v</ci></bvar>
  <apply><csymbol cd="set1">in</csymbol>
   <ci>v</ci>
   <apply><csymbol cd="graph1">vertexset</csymbol><ci>Gamma</ci></apply>
  </apply>
 </bind>
</math>

Prefix

lambda [ v ] . (in ( v, vertexset ( Gamma) ) )

Popcorn

fns1.lambda[$v -> set1.in($v, graph1.vertexset($Gamma))]

Rendered Presentation MathML

$$\lambda \hspace{0.17em}v.v\in \mathrm{vertexset}\left(\Gamma \right)$$

Signatures:

sts

edgeset

Description:

This symbol represents the set of edges of an undirected graph. It takes one argument, the undirected graph.

Example:

Given a graph Gamma and two of its vertices v and w, this predicate asserts that they are adjacent.

OpenMath XML (source)

<OMOBJ xmlns="http://www.openmath.org/OpenMath" version="2.0">
	<OMA>
	  <OMS cd="set1" name="in"/>
	  <OMA>
	    <OMS cd="set1" name="set"/>
	    <OMV name="v"/>
	    <OMV name="w"/>
	  </OMA>
	  <OMA>
	    <OMS cd="graph1" name="edgeset"/>
	    <OMV name="Gamma"/>
	  </OMA>
	</OMA>
      </OMOBJ>

Strict Content MathML

<math xmlns="http://www.w3.org/1998/Math/MathML">
 <apply><csymbol cd="set1">in</csymbol>
  <apply><csymbol cd="set1">set</csymbol><ci>v</ci><ci>w</ci></apply>
  <apply><csymbol cd="graph1">edgeset</csymbol><ci>Gamma</ci></apply>
 </apply>
</math>

Prefix

in (set ( v, w) , edgeset ( Gamma) )

Popcorn

set1.in({$v , $w}, graph1.edgeset($Gamma))

Rendered Presentation MathML

$$\{v,w\}\in \mathrm{edgeset}\left(\Gamma \right)$$

Commented Mathematical property (CMP):

Every edge in an undirected graph Gamma is a subset of the vertex set of size two.

Formal Mathematical property (FMP):

OpenMath XML (source)

      <OMOBJ xmlns="http://www.openmath.org/OpenMath" version="2.0">
        <OMBIND>
	  <OMS cd="quant1" name="forall"/>
	  <OMBVAR>
	    <OMV name="e"/>
	    <OMV name="Gamma"/>
	  </OMBVAR>
	  <OMA>
	    <OMS cd="logic1" name="implies"/>
	    <OMA>
	      <OMS cd="set1" name="in"/>
	      <OMV name="e"/>
	      <OMA>
	        <OMS cd="graph1" name="vertexset"/>
		<OMV name="Gamma"/>
	      </OMA>
	    </OMA>
	    <OMA>
	      <OMS cd="logic1" name="and"/>
	      <OMA>
	        <OMS cd="set1" name="subset"/>
		<OMV name="e"/>
		<OMA>
		  <OMS cd="graph1" name="vertexset"/>
		  <OMV name="Gamma"/>
		</OMA>
	      </OMA>
	      <OMA>
	        <OMS cd="relation1" name="eq"/>
		<OMA>
		  <OMS cd="set1" name="size"/>
		  <OMV name="e"/>
		</OMA>
		<OMI> 2 </OMI>
	      </OMA>
	    </OMA>    
	  </OMA>
	</OMBIND>
      </OMOBJ>

Strict Content MathML

<math xmlns="http://www.w3.org/1998/Math/MathML">
 <bind><csymbol cd="quant1">forall</csymbol>
  <bvar><ci>e</ci></bvar>
  <bvar><ci>Gamma</ci></bvar>
  <apply><csymbol cd="logic1">implies</csymbol>
   <apply><csymbol cd="set1">in</csymbol>
    <ci>e</ci>
    <apply><csymbol cd="graph1">vertexset</csymbol><ci>Gamma</ci></apply>
   </apply>
   <apply><csymbol cd="logic1">and</csymbol>
    <apply><csymbol cd="set1">subset</csymbol>
     <ci>e</ci>
     <apply><csymbol cd="graph1">vertexset</csymbol><ci>Gamma</ci></apply>
    </apply>
    <apply><csymbol cd="relation1">eq</csymbol>
     <apply><csymbol cd="set1">size</csymbol><ci>e</ci></apply>
     <cn>2</cn>
    </apply>
   </apply>
  </apply>
 </bind>
</math>

Prefix

forall [ e Gamma ] . (implies (in ( e, vertexset ( Gamma) ) , and (subset ( e, vertexset ( Gamma) ) , eq (size ( e) , 2 ) ) ) )

Popcorn

quant1.forall[$e, $Gamma -> set1.in($e, graph1.vertexset($Gamma)) ==> set1.subset($e, graph1.vertexset($Gamma)) and set1.size($e) = 2]

Rendered Presentation MathML

$$\forall \hspace{0.17em}e,\Gamma .e\in \mathrm{vertexset}\left(\Gamma \right)\Rightarrow e\subset \mathrm{vertexset}\left(\Gamma \right)\wedge \mathrm{size}\left(e\right)=2$$

Signatures:

sts

digraph

Description:

This symbol refers to a digraph. It has two arguments. The first is the set of vertices, the second is the set of arrows. Arrows are represented by lists of length two, where a list represents the arrow from the first element to the second.

Example:

The two-sided infinite directed path.

OpenMath XML (source)

<OMOBJ xmlns="http://www.openmath.org/OpenMath" version="2.0">
        <OMA>
          <OMS cd="graph1" name="digraph"/>
          <OMS cd="setname1" name="Z"/>
  	  <OMA>
  	    <OMS cd="set1" name="map"/>
            <OMBIND>
  	      <OMS cd="fns1" name="lambda"/>
  	      <OMBVAR>
  	        <OMV name="x"/>
  	      </OMBVAR>
  	      <OMA>
  	        <OMS cd="list1" name="list"/>
  	        <OMV name="x"/>
  	        <OMA>
  	          <OMS cd="arith1" name="plus"/>
  		  <OMV name="x"/>
  		  <OMI> 1 </OMI>
  	        </OMA>
  	      </OMA>
  	    </OMBIND>
            <OMS cd="setname1" name="Z"/>
  	  </OMA>
        </OMA>
      </OMOBJ>

Strict Content MathML

<math xmlns="http://www.w3.org/1998/Math/MathML">
 <apply><csymbol cd="graph1">digraph</csymbol>
  <csymbol cd="setname1">Z</csymbol>
  <apply><csymbol cd="set1">map</csymbol>
   <bind><csymbol cd="fns1">lambda</csymbol>
    <bvar><ci>x</ci></bvar>
    <apply><csymbol cd="list1">list</csymbol>
     <ci>x</ci>
     <apply><csymbol cd="arith1">plus</csymbol><ci>x</ci><cn>1</cn></apply>
    </apply>
   </bind>
   <csymbol cd="setname1">Z</csymbol>
  </apply>
 </apply>
</math>

Prefix

digraph (Z, map (lambda [ x ] . (list ( x, plus ( x, 1 ) ) ) , Z) )

Popcorn

graph1.digraph(setname1.Z, set1.map(fns1.lambda[$x -> [$x , $x + 1]], setname1.Z))

Rendered Presentation MathML

$$\mathrm{digraph}(\mathbb{Z},\left\{(x,x+1)\right|x\in \mathbb{Z}\})$$

Signatures:

sts

arrowset

Description:

This symbol represents the set of arrows of a directed graph. It takes one argument, the directed graph.

Example:

The arrow set of the loop consists of one loop.

OpenMath XML (source)

<OMOBJ xmlns="http://www.openmath.org/OpenMath" version="2.0">
        <OMA>
	  <OMS cd="relation1" name="eq"/>
	  <OMA>
	    <OMS cd="graph1" name="arrowset"/>
	    <OMA>
	      <OMS cd="graph1" name="digraph"/>
	      <OMA>
	        <OMS cd="set1" name="set"/>
		<OMI> 1 </OMI>
	      </OMA>
	      <OMA>
    	        <OMS cd="set1" name="set"/>
      	        <OMA>
      	          <OMS cd="list1" name="list"/>
      	          <OMI> 1 </OMI>
      	          <OMI> 1 </OMI>
      	        </OMA>
	      </OMA>
	    </OMA>
	  </OMA>
	  <OMA>
	    <OMS cd="set1" name="set"/>
	    <OMA>
	      <OMS cd="list1" name="list"/>
	      <OMI> 1 </OMI>
	      <OMI> 1 </OMI>
	    </OMA>
	  </OMA>
	</OMA>
      </OMOBJ>

Strict Content MathML

<math xmlns="http://www.w3.org/1998/Math/MathML">
 <apply><csymbol cd="relation1">eq</csymbol>
  <apply><csymbol cd="graph1">arrowset</csymbol>
   <apply><csymbol cd="graph1">digraph</csymbol>
    <apply><csymbol cd="set1">set</csymbol><cn>1</cn></apply>
    <apply><csymbol cd="set1">set</csymbol>
     <apply><csymbol cd="list1">list</csymbol><cn>1</cn><cn>1</cn></apply>
    </apply>
   </apply>
  </apply>
  <apply><csymbol cd="set1">set</csymbol>
   <apply><csymbol cd="list1">list</csymbol><cn>1</cn><cn>1</cn></apply>
  </apply>
 </apply>
</math>

Prefix

eq (arrowset (digraph (set ( 1 ) , set (list ( 1 , 1 ) ) ) ) , set (list ( 1 , 1 ) ) )

Popcorn

graph1.arrowset(graph1.digraph({1}, {[1 , 1]})) = {[1 , 1]}

Rendered Presentation MathML

$$\mathrm{arrowset}\left(\mathrm{digraph}(\left\{1\right\},\left\{(1,1)\right\})\right)=\left\{(1,1)\right\}$$

Signatures:

sts

source

Description:

Given an arrow, this symbol refers to the vertex where the arrow starts. It takes one argument, the arrow.

Example:

The arrow [a, b] starts at a.

OpenMath XML (source)

<OMOBJ xmlns="http://www.openmath.org/OpenMath" version="2.0">
        <OMA>
	  <OMS cd="relation1" name="eq"/>
	  <OMA>
	    <OMS cd="graph1" name="source"/>
	    <OMA>
	      <OMS cd="list1" name="list"/>
	      <OMV name="a"/>
	      <OMV name="b"/>
	    </OMA>
	  </OMA>
	  <OMV name="a"/>
	</OMA>
      </OMOBJ>

Strict Content MathML

<math xmlns="http://www.w3.org/1998/Math/MathML">
 <apply><csymbol cd="relation1">eq</csymbol>
  <apply><csymbol cd="graph1">source</csymbol>
   <apply><csymbol cd="list1">list</csymbol><ci>a</ci><ci>b</ci></apply>
  </apply>
  <ci>a</ci>
 </apply>
</math>

Prefix

eq (source (list ( a, b) ) , a)

Popcorn

graph1.source([$a , $b]) = $a

Rendered Presentation MathML

$$\mathrm{source}\left((a,b)\right)=a$$

Signatures:

sts

target

Description:

Given an arrow, this symbol refers to the vertex the arrow points to. It takes one argument, the arrow.

Example:

The arrow [a, b] points to b.

OpenMath XML (source)

<OMOBJ xmlns="http://www.openmath.org/OpenMath" version="2.0">
        <OMA>
	  <OMS cd="relation1" name="eq"/>
	  <OMA>
	    <OMS cd="graph1" name="target"/>
	    <OMA>
	      <OMS cd="list1" name="list"/>
	      <OMV name="a"/>
	      <OMV name="b"/>
	    </OMA>
	  </OMA>
	  <OMV name="b"/>
	</OMA>
      </OMOBJ>

Strict Content MathML

<math xmlns="http://www.w3.org/1998/Math/MathML">
 <apply><csymbol cd="relation1">eq</csymbol>
  <apply><csymbol cd="graph1">target</csymbol>
   <apply><csymbol cd="list1">list</csymbol><ci>a</ci><ci>b</ci></apply>
  </apply>
  <ci>b</ci>
 </apply>
</math>

Prefix

eq (target (list ( a, b) ) , b)

Popcorn

graph1.target([$a , $b]) = $b

Rendered Presentation MathML

$$\mathrm{target}\left((a,b)\right)=b$$

Signatures:

sts