Dealing with Graphs [polymake wiki]

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== Dealing with Graphs ======

Graphs are ubiquitous in geometric combinatorics. Hence they occur a lot throughout the ''%%polymake%%'' system, explicitly and implicitly. It is important to understand that the user encounters graphs on two distinct layers in the object hierarchy. It is the purpose of this tutorial to explore the various features. For the sake of simplicity here we restrict our attention to undirected graphs.

===== Graphs of Polytopes =====

Coming from polytopes the first situation in which a graph occurs is the vertex-edge graph of such a polytope.

<code perl>
> $p=rand_sphere(3,20);
> print $p->GRAPH->N_NODES;
20
</code>
Here ''%%GRAPH%%'' is a property of the polytope object ''%%$p%%'' which happens to be of the object type ''%%Graph%%''. The following is a fragment of the file ''%%apps/polytopes/rules/polytope_properties.rules%%''. This is where all the standard properties of polytopes are declared.

<code>
property GRAPH : Graph {

   # Difference of the vertices for each edge (only defined up to signs).
   property EDGE_DIRECTIONS : EdgeMap<Undirected, Vector<Scalar>>;
}
</code>
In fact, this ''%%Graph%%'' is the main object class of another application, called ''%%graph%%''. This application ''%%graph%%'' is defined in ''%%apps/graph%%'' and its subdirectories. Although the application ''%%graph%%'' has much fewer features than the application ''%%polytope%%'' the overall mechanism of interaction is the same. In particular, there are properties, rules, clients, and such. Non-trivial features include the algorithm for computing the diameter and the visualization of graphs based on a pseudo-physical model (described in [[https://arxiv.org/abs/0711.2397|this paper]]).

<code perl>
> print $p->DIAMETER;
3
> $p->VISUAL;
</code>
<HTML>
<!--
polymake for knusper
Wed Mar  2 23:36:20 2022
p
-->


<html>
   <head>
      <meta charset=utf-8>
      <title>p</title>
      <style>
/*
// COMMON_CODE_BLOCK_BEGIN
*/
         html {overflow: scroll;}
         strong{font-size: 18px;}
         canvas { z-index: 8; }
         input[type='radio'] {margin-left:0;}
         input[type='checkbox'] {margin-right:7px; margin-left: 0px; padding-left:0px;}
         .group{padding-bottom: 15px;}
         .settings * {z-index: 11; }
         .settings{z-index: 10; font-family: Arial, Helvetica, sans-serif; margin-left: 30px; visibility: hidden; width: 14em; height: 96%; border: solid 1px silver; padding: 2px; overflow-y: scroll; box-sizing: border-box; background-color: white; position: absolute;}
         .indented{margin-left: 20px; margin-top: 10px; padding-bottom: 0px;} 
         .shownObjectsList{overflow: auto; max-width: 150px; max-height: 150px;}
         .showSettingsButton{visibility: visible; z-index: 12; position: absolute }
         .hideSettingsButton{visibility: hidden; z-index: 12; position: absolute; opacity: 0.5}
         button{margin-left: 0; margin-top: 10px}
         img{cursor: pointer;}
         .suboption{padding-top: 15px;}
         #model24544831490 { width: 100%; height: 100%; }
         .threejs_container { width: 100%; height: 75vh;}
         .settings{max-height: 74vh} 
         input[type=range] {
           -webkit-appearance: none;
           padding:0; 
           width:90%; 
           margin-left: auto;
           margin-right: auto;
           margin-top: 15px;
           margin-bottom: 15px;
           display: block;	
         }
         input[type=range]:focus {
           outline: none;
         }
         input[type=range]::-webkit-slider-runnable-track {
           height: 4px;
           cursor: pointer;
           animate: 0.2s;
           box-shadow: 0px 0px 0px #000000;
           background: #E3E3E3;
           border-radius: 0px;
           border: 0px solid #000000;
         }
         input[type=range]::-webkit-slider-thumb {
           box-shadow: 1px 1px 2px #B8B8B8;
           border: 1px solid #ABABAB;
           height: 13px;
           width: 25px;
           border-radius: 20px;
           background: #E0E0E0;
           cursor: pointer;
           -webkit-appearance: none;
           margin-top: -5px;
         }
         input[type=range]:focus::-webkit-slider-runnable-track {
           background: #E3E3E3;
         }
         input[type=range]::-moz-range-track {
           height: 4px;
           cursor: pointer;
           animate: 0.2s;
           box-shadow: 0px 0px 0px #000000;
           background: #E3E3E3;
           border-radius: 0px;
           border: 0px solid #000000;
         }
         input[type=range]::-moz-range-thumb {
           box-shadow: 1px 1px 2px #B8B8B8;
           border: 1px solid #ABABAB;
           height: 13px;
           width: 25px;
           border-radius: 20px;
           background: #E0E0E0;
           cursor: pointer;
         }
         input[type=range]::-ms-track {
           height: 4px;
           cursor: pointer;
           animate: 0.2s;
           background: transparent;
           border-color: transparent;
           color: transparent;
         }
         input[type=range]::-ms-fill-lower {
           background: #E3E3E3;
           border: 0px solid #000000;
           border-radius: 0px;
           box-shadow: 0px 0px 0px #000000;
         }
         input[type=range]::-ms-fill-upper {
           background: #E3E3E3;
           border: 0px solid #000000;
           border-radius: 0px;
           box-shadow: 0px 0px 0px #000000;
         }
         input[type=range]::-ms-thumb {
           box-shadow: 1px 1px 2px #B8B8B8;
           border: 1px solid #ABABAB;
           height: 13px;
           width: 25px;
           border-radius: 20px;
           background: #E0E0E0;
           cursor: pointer;
         }
         input[type=range]:focus::-ms-fill-lower {
           background: #E3E3E3;
         }
         input[type=range]:focus::-ms-fill-upper {
           background: #E3E3E3;
         }
/*
// COMMON_CODE_BLOCK_END
*/
		</style>
   </head>
<body>
   <div class='threejs_container'>
		<div id='settings_0' class='settings'>
			<div class=group id='transparency_0' class='transparency'>
				<strong>Transparency</strong>
				<input id='transparencyRange_0' type='range' min=0 max=1 step=0.01 value=0>
            <div class=indented><input id='depthWriteCheckbox_0' type='checkbox'>depthWrite</div>
			</div>
			
			<div class=group id='rotation_0'>
				<strong>Rotation</strong>
				<div class=indented>
					<div><input type='checkbox' id='changeRotationX_0'> x-axis</div>
					<div><input type='checkbox' id='changeRotationY_0'> y-axis</div>
					<div><input type='checkbox' id='changeRotationZ_0'> z-axis</div>
					<button id='resetButton_0'>Reset</button>
				</div>

				<div class=suboption>Rotation speed</div>
				<input id='rotationSpeedRange_0' type='range' min=0 max=5 step=0.01 value=2>
			</div>


			<div class=group id='display_0'>
				<strong>Display</strong>
				<div class=indented>
					<div id='shownObjectTypesList_0' class='shownObjectsList'></div>
				</div>
				<div class=suboption>Objects</div>
				<div class=indented>
				   <div id='shownObjectsList_0' class='shownObjectsList'></div>
				</div>
			</div>
         
         <div class=group id='camera_0'>
            <strong>Camera</strong>
            <div class=indented>
               <form>
                  <select id="cameraType_0">
                     <option value='perspective' selected> Perspective<br></option>
                     <option value='orthographic' > Orthographic<br></option>
                  </select>
               </form>
            </div>
         </div>

			<div class=group id='svg_0'>
				<strong>SVG</strong>
				<div class=indented>
					<form>
						<input type="radio" name='screenshotMode' value='download' id='download_0' checked> Download<br>
						<input type="radio" name='screenshotMode' value='tab' id='tab_0' > New tab<br>
					</form>
					<button id='takeScreenshot_0'>Screenshot</button>
				</div>
			</div>

		</div>	<!-- end of settings -->
		<img id='hideSettingsButton_0' class='hideSettingsButton' src='/kernelspecs/r118/polymake/close.svg' width=20px">
		<img id='showSettingsButton_0' class='showSettingsButton' src='/kernelspecs/r118/polymake/menu.svg' width=20px">
<div id="model24544831490"></div>
</div>
   <script>
    requirejs.config({
      paths: {
        three: '/kernelspecs/r118/polymake/three',
        TrackballControls: '/kernelspecs/r118/polymake/TrackballControls',
        OrbitControls: '/kernelspecs/r118/polymake/OrbitControls',
        Projector: '/kernelspecs/r118/polymake/Projector',
        SVGRenderer: '/kernelspecs/r118/polymake/SVGRenderer',
        WEBGL: '/kernelspecs/r118/polymake/WebGL',
      },
      shim: {
        'three': { exports: 'THREE'},
        'SVGRenderer': { deps: [ 'three' ], exports: 'THREE.SVGRenderer' },
        'WEBGL': { deps: [ 'three' ], exports: 'THREE.WEBGL' },
        'Projector': { deps: [ 'three' ], exports: 'THREE.Projector' },
        'TrackballControls': { deps: [ 'three' ], exports: 'THREE.TrackballControls' },
        'OrbitControls': { deps: [ 'three' ], exports: 'THREE.OrbitControls' },
      }
    });
    
    require(['three'],function(THREE){
        window.THREE = THREE;
      require(['TrackballControls', 'OrbitControls', 'Projector', 'SVGRenderer', 'WEBGL'],
               function(TrackballControls, OrbitControls, Projector, SVGRenderer, WEBGL) {
    THREE.TrackballControls = TrackballControls;
    THREE.OrbitControls = OrbitControls;
    THREE.Projector = Projector;
    THREE.SVGRenderer = SVGRenderer;
    THREE.WEBGL = WEBGL;

// COMMON_CODE_BLOCK_BEGIN

const intervalLength = 25; // for automatic animations
const explodableModel = false; 
const modelContains = { points: false, pointlabels: false, lines: false, edgelabels: false, faces: false, arrowheads: false };
const foldables = [];

var three = document.getElementById("model24544831490");
var scene = new THREE.Scene();
var renderer = new THREE.WebGLRenderer( { antialias: true } );
var svgRenderer = new THREE.SVGRenderer( { antialias: true } );
renderer.setPixelRatio( window.devicePixelRatio );
renderer.setClearColor(0xFFFFFF, 1);
svgRenderer.setClearColor(0xFFFFFF, 1);
three.appendChild(renderer.domElement);

var frustumSize = 4;
var cameras = [new THREE.PerspectiveCamera(75, 1, 0.1, 1000), new THREE.OrthographicCamera()];
cameras.forEach(function(cam) {
    cam.position.set(0, 0, 5);
    cam.lookAt(0, 0, 0);  
    cam.up.set(0, 1, 0);         
});
var controls = [new THREE.TrackballControls(cameras[0], three), new THREE.OrbitControls(cameras[1], three)];
var camera, control;

controls[0].zoomSpeed = 0.2;
controls[0].rotateSpeed = 4;


// class to allow move points together with labels and spheres
var PMPoint = function (x,y,z) {
   this.vector = new THREE.Vector3(x,y,z);
   this.sprite = null;
   this.sphere = null;
}
PMPoint.prototype.addLabel = function(labelsprite) {
   this.sprite = labelsprite;
   this.sprite.position.copy(this.vector);
}
PMPoint.prototype.addSphere = function(spheremesh) {
   this.sphere = spheremesh;
   this.sphere.position.copy(this.vector);
}
PMPoint.prototype.set = function(x,y,z) {
   this.vector.set(x,y,z);
   if (this.sprite) {
      this.sprite.position.copy(this.vector);
   }
   if (this.sphere) {
      this.sphere.position.copy(this.vector);
   }
}
PMPoint.prototype.radius = function() {
   if (this.sphere) {
      return this.sphere.geometry.parameters.radius;
   } else {
      return 0;
   }
};
// select the target node
var target = document.querySelector('#model24544831490');

// create an observer instance
var observer = new MutationObserver(function(mutations) {
   mutations.forEach(function(mutation) {
      if (mutation.removedNodes && mutation.removedNodes.length > 0) {
         cancelAnimationFrame(renderId);
         observer.disconnect();
         console.log("cancelled frame "+renderId);
      }
   });
});

// configuration of the observer:
var config = { childList: true, characterData: true }

// pass in the target node, as well as the observer options
while (target) {
   if (target.className=="output") {
      observer.observe(target, config);
      break;
   }
   target = target.parentNode;
}

// COMMON_CODE_BLOCK_END

var obj0 = new THREE.Object3D();
obj0.name = "p";
obj0.userData.explodable = 1;
obj0.userData.points = [];
obj0.userData.points.push(new PMPoint(0.308439, 0.508077, -0.804191));
obj0.userData.points.push(new PMPoint(-0.864646, -0.387754, -0.319429));
obj0.userData.points.push(new PMPoint(0.583479, -0.320746, 0.746106));
obj0.userData.points.push(new PMPoint(0.750463, -0.227647, -0.620469));
obj0.userData.points.push(new PMPoint(-0.539194, -0.227215, 0.810952));
obj0.userData.points.push(new PMPoint(-0.926062, -0.181073, 0.331092));
obj0.userData.points.push(new PMPoint(-0.409276, 0.291109, -0.864725));
obj0.userData.points.push(new PMPoint(-0.657688, 0.291821, 0.694469));
obj0.userData.points.push(new PMPoint(-0.415681, -0.275552, 0.866764));
obj0.userData.points.push(new PMPoint(0.975222, -0.190885, -0.111823));
obj0.userData.points.push(new PMPoint(0.347561, -0.469291, 0.811768));
obj0.userData.points.push(new PMPoint(-0.0834228, 0.769509, -0.633164));
obj0.userData.points.push(new PMPoint(-0.754369, -0.575955, 0.314966));
obj0.userData.points.push(new PMPoint(-0.282649, -0.307642, 0.908551));
obj0.userData.points.push(new PMPoint(0.821865, 0.12358, -0.556116));
obj0.userData.points.push(new PMPoint(0.157641, -0.945535, 0.284804));
obj0.userData.points.push(new PMPoint(-0.489031, 0.871022, -0.0465763));
obj0.userData.points.push(new PMPoint(0.439173, 0.742268, 0.506128));
obj0.userData.points.push(new PMPoint(-0.966099, 0.246305, 0.0773726));
obj0.userData.points.push(new PMPoint(-0.506169, -0.84676, -0.163677));

obj0.userData.pointradii = 0.02;
   <!-- Vertex style -->
obj0.userData.pointmaterial = new THREE.MeshBasicMaterial( { color: 0xFF0000, side: THREE.DoubleSide, transparent: false } );
obj0.userData.pointlabels = ["0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "10", "11", "12", "13", "14", "15", "16", "17", "18", "19"];
obj0.userData.edgeindices = [0, 3, 1, 5, 4, 5, 0, 6, 1, 6, 3, 6, 4, 7, 5, 7, 4, 8, 7, 8, 2, 9, 3, 9, 2, 10, 0, 11, 6, 11, 1, 12, 4, 12, 5, 12, 8, 12, 2, 13, 7, 13, 8, 13, 10, 13, 12, 13, 0, 14, 3, 14, 9, 14, 2, 15, 3, 15, 9, 15, 10, 15, 12, 15, 13, 15, 6, 16, 7, 16, 11, 16, 0, 17, 2, 17, 7, 17, 9, 17, 11, 17, 13, 17, 14, 17, 16, 17, 1, 18, 5, 18, 6, 18, 7, 18, 16, 18, 1, 19, 3, 19, 6, 19, 12, 19, 15, 19];
   <!-- Edge style -->
obj0.userData.edgematerial = new THREE.LineBasicMaterial( { color: 0x000000, linewidth: 1.5, transparent: false } );
obj0.userData.facets = [[0, 14, 3], [17, 14, 0], [2, 17, 13], [2, 13, 10], [15, 2, 10], [15, 10, 13], [12, 15, 13], [19, 15, 12], [13, 7, 8], [12, 13, 8], [8, 7, 4], [12, 8, 4], [1, 19, 12], [18, 5, 7], [1, 12, 5], [18, 1, 5], [5, 12, 4], [5, 4, 7], [16, 18, 7], [6, 19, 1], [6, 1, 18], [16, 6, 18], [11, 6, 16], [0, 6, 11], [11, 16, 17], [0, 11, 17], [13, 17, 7], [17, 16, 7], [3, 15, 19], [6, 3, 19], [0, 3, 6], [15, 9, 2], [3, 9, 15], [9, 17, 2], [9, 14, 17], [3, 14, 9]];
   <!-- Facet style -->
obj0.userData.facetmaterial = new THREE.MeshBasicMaterial( { color: 0x77EC9E, depthFunc: THREE.LessDepth, depthWrite: false, opacity: 1, polygonOffset: true, polygonOffsetFactor: 1, polygonOffsetUnits: 0.5, side: THREE.DoubleSide, transparent: true } );
init_object(obj0);
scene.add(obj0);

// COMMON_CODE_BLOCK_BEGIN
function textSpriteMaterial(message, parameters) {
    if ( parameters === undefined ) parameters = {};
    var fontface = "Helvetica";
    var fontsize = parameters.hasOwnProperty("fontsize") ? parameters["fontsize"] : 15;
    fontsize = fontsize*10;
    var lines = message.split('\\n');
    var size = 512;
    for(var i = 0; i<lines.length; i++){
        var tmp = lines[i].length;
        while(tmp*fontsize > size){
           fontsize--;
        }
    }
    
    var canvas = document.createElement('canvas');
    canvas.width = size;
    canvas.height = size;
    var context = canvas.getContext('2d');
    context.fillStyle = "rgba(255, 255, 255, 0)";
    context.fill();
    context.font = fontsize + "px " + fontface;
    
    // text color
    context.fillStyle = "rgba(0, 0, 0, 1.0)";
     for(var i = 0; i<lines.length; i++){
        context.fillText(lines[i], size/2, size/2+i*fontsize);
     }
    
    // canvas contents will be used for a texture
    var texture = new THREE.Texture(canvas);
    texture.needsUpdate = true;
    
    var spriteMaterial = new THREE.SpriteMaterial({map: texture, depthTest: true, depthWrite: false, polygonOffset: true, polygonOffsetFactor: -1, polygonOffsetUnits: 1 });
    return spriteMaterial;
}


// ---------------------- INITIALIZING OBJECTS--------------------------------------
// ---------------------------------------------------------------------------------

function init_object(obj) {
    if (obj.userData.hasOwnProperty("pointmaterial")) {
        init_points(obj);
        modelContains.points = true;
    }
    if (obj.userData.hasOwnProperty("pointlabels")) {
        init_pointlabels(obj);
        modelContains.pointlabels = true;
    }
    if (obj.userData.hasOwnProperty("edgematerial")) {
        init_lines(obj);
        modelContains.lines = true;
    }
    if (obj.userData.hasOwnProperty("edgelabels")) {
        init_edgelabels(obj);
        modelContains.edgelabels = true;
    }
    if (obj.userData.hasOwnProperty("arrowstyle")) {
        init_arrowheads(obj);
        modelContains.arrowheads = true;
    }
    if (obj.userData.hasOwnProperty("facetmaterial")) {
        init_faces(obj);
        modelContains.faces = true;
    }
}

function init_points(obj) {
    var pointgroup = new THREE.Group();
    pointgroup.name = "points";
    var points = obj.userData.points;
    var radii = obj.userData.pointradii;
    var materials = obj.userData.pointmaterial;
    var geometry,material;
    if (!Array.isArray(radii)) {
        geometry = new THREE.SphereBufferGeometry(radii);  
    }
    if (!Array.isArray(materials)) {
        material = materials;
    }
    for (var i=0; i<points.length; i++) {
        var point = points[i];
        if (Array.isArray(radii)) {
            if (radii[i] == 0) {
                continue;
            }
            geometry = new THREE.SphereBufferGeometry(radii[i]);  
        } 
        if (Array.isArray(materials)) {
            material = materials[i];     
        } 
        var sphere = new THREE.Mesh(geometry, material);
        point.addSphere(sphere);
        pointgroup.add(sphere);
    }
    obj.add(pointgroup);
}

function init_pointlabels(obj) {
    var points = obj.userData.points;
    var labels = obj.userData.pointlabels;
    var pointlabels = new THREE.Group();
    pointlabels.name = "pointlabels";
    if (Array.isArray(labels)) {
        for (var i=0; i<points.length; i++) {
            var point = points[i];
            var spriteMaterial = textSpriteMaterial( labels[i] );
	        var sprite = new THREE.Sprite(spriteMaterial);
            point.addLabel(sprite);
            pointlabels.add(sprite);
        }
    } else {
        var spriteMaterial = textSpriteMaterial( labels );
        for (var i=0; i<points.length; i++) {
            var point = points[i];
	        var sprite = new THREE.Sprite(spriteMaterial);
            point.addLabel(sprite);
            pointlabels.add(sprite);
        }
    }
    obj.add(pointlabels);
}

function init_lines(obj) {
    var edgeindices = obj.userData.edgeindices;
    var points = obj.userData.points;
    var materials = obj.userData.edgematerial;
    var geometry = new THREE.BufferGeometry();
    var bufarr = new Float32Array( obj.userData.edgeindices.length * 3 );
    var bufattr = new THREE.Float32BufferAttribute( bufarr, 3 );
    var geometry = new THREE.BufferGeometry();
    geometry.setAttribute('position', bufattr);
    if (Array.isArray(materials)) {     
        for (var i=0; i<materials.length; i++) {
            geometry.addGroup(2*i,2,i);
        }
    }
    var lines = new THREE.LineSegments(geometry, materials);
    lines.name = "lines";
    obj.add(lines);
    updateEdgesPosition(obj);
}

function init_edgelabels(obj) {
    var points = obj.userData.points;
    var edgeindices = obj.userData.edgeindices;
    var labels = obj.userData.edgelabels;
    var edgelabels = new THREE.Group();
    edgelabels.name = "edgelabels";
    if (Array.isArray(labels)) {
        for (var i=0; i<edgeindices.length/2; i++) {
            var spriteMaterial = textSpriteMaterial( labels[i] );
            var sprite = new THREE.Sprite(spriteMaterial);
            sprite.position.copy(new THREE.Vector3().addVectors(points[edgeindices[2*i]].vector,points[edgeindices[2*i+1]].vector).multiplyScalar(0.5));
            edgelabels.add(sprite);
        }
    } else {
        var spriteMaterial = textSpriteMaterial( labels );
        for (var i=0; i<edgeindices.length/2; i++) {
            var sprite = new THREE.Sprite(spriteMaterial);
            sprite.position.copy(new THREE.Vector3().addVectors(points[edgeindices[2*i]].vector,points[edgeindices[2*i+1]].vector).multiplyScalar(0.5));
            edgelabels.add(sprite);
        }
    }
    obj.add(edgelabels);
}

function init_arrowheads(obj) {
    var arrowheads = new THREE.Group();
    arrowheads.name = "arrowheads";
    var arrowstyle = obj.userData.arrowstyle;
    var edgeindices = obj.userData.edgeindices;
    var edgematerials = obj.userData.edgematerial;
    var points = obj.userData.points;
    var material;
    if (!Array.isArray(edgematerials)) {
        material = new THREE.MeshBasicMaterial( {color: edgematerials.color} );
    }

    for (var i=0; i<edgeindices.length; i=i+2) {
        var start = points[edgeindices[i]];
        var end = points[edgeindices[i+1]];
        var dist = start.vector.distanceTo( end.vector ) - start.radius() - end.radius();
        if (dist <= 0) {
            continue;
        }
        var dir = new THREE.Vector3().subVectors(end.vector,start.vector);
        dir.normalize();
        var axis = new THREE.Vector3().set(dir.z,0,-dir.x);
        axis.normalize();
        var radians = Math.acos( dir.y );
        var radius = dist/25;
        var height = dist/5;
        var geometry = new THREE.ConeBufferGeometry(radius,height);
        var position = new THREE.Vector3().addVectors(start.vector,dir.clone().multiplyScalar(start.radius()+dist-height/2));
        if (Array.isArray(edgematerials)) {
            material = new THREE.MeshBasicMaterial( {color: edgematerials[i].color} );
        }
        var cone = new THREE.Mesh( geometry, material );
        cone.quaternion.setFromAxisAngle(axis,radians);;
        cone.position.copy(position);;
        arrowheads.add(cone);
    }
    obj.add(arrowheads);
}

function init_faces(obj) {
    var points = obj.userData.points;
    var facets = obj.userData.facets;
    obj.userData.triangleindices = [];
    for (var i=0; i<facets.length; i++) {
        facet = facets[i];
        for (var t=0; t<facet.length-2; t++) {
            obj.userData.triangleindices.push(facet[0],facet[t+1],facet[t+2]);  
        }
    }
    var bufarr = new Float32Array( obj.userData.triangleindices.length * 3 );
    var bufattr = new THREE.Float32BufferAttribute(bufarr,3);
    
    var materials = obj.userData.facetmaterial;
    var geometry = new THREE.BufferGeometry();
    var frontmaterials = [];
    var backmaterials = [];
    geometry.setAttribute('position',bufattr);
    if (Array.isArray(materials)) {
        var tricount = 0;
        var facet;
        for (var i=0; i<facets.length; i++) {
            facet = facets[i];
            geometry.addGroup(tricount,(facet.length-2)*3,i);
            tricount += (facet.length-2)*3;
        }
        for (var j=0; j<materials.length; j++) {
            var fmat = materials[j].clone()
            fmat.side = THREE.FrontSide;
            frontmaterials.push(fmat);
            var bmat = materials[j].clone()
            bmat.side = THREE.BackSide;
            backmaterials.push(bmat);
            obj.userData.facetmaterial = frontmaterials.concat(backmaterials);
        }
    } else if (materials instanceof THREE.Material) {
        frontmaterials = materials.clone()
        frontmaterials.side = THREE.FrontSide;
        backmaterials = materials.clone()
        backmaterials.side = THREE.BackSide;
        obj.userData.facetmaterial = [frontmaterials, backmaterials];
    }
    // duplicating the object with front and back should avoid transparency issues
    var backmesh = new THREE.Mesh(geometry, backmaterials);
    // meshname is used to show/hide objects
    backmesh.name = "backfaces";
    obj.add(backmesh);
    var frontmesh = new THREE.Mesh(geometry, frontmaterials);
    frontmesh.name = "frontfaces";
    obj.add(frontmesh);
    updateFacesPosition(obj);
}
// //INITIALIZING


function updateFacesPosition(obj) {
    var points = obj.userData.points;
    var indices = obj.userData.triangleindices;
    var faces = obj.getObjectByName("frontfaces");
    var ba = faces.geometry.getAttribute("position");
    for (var i=0; i<indices.length; i++) {
        ba.setXYZ(i, points[indices[i]].vector.x, points[indices[i]].vector.y ,points[indices[i]].vector.z); 
    }
    faces.geometry.attributes.position.needsUpdate = true;
    
}

function updateEdgesPosition(obj) {
    var points = obj.userData.points;
    var indices = obj.userData.edgeindices;
    var lines = obj.getObjectByName("lines");
    var ba = lines.geometry.getAttribute("position"); 
    for (var i=0; i<indices.length; i++) {
        ba.setXYZ(i, points[indices[i]].vector.x, points[indices[i]].vector.y ,points[indices[i]].vector.z); 
    }
    lines.geometry.attributes.position.needsUpdate = true;
}

function onWindowResize() {
    renderer.setSize( three.clientWidth, three.clientHeight );
    svgRenderer.setSize( three.clientWidth, three.clientHeight );
    updateCamera();
}

function updateCamera() {
    var width = three.clientWidth;
    var height = three.clientHeight;
    var aspect = width / height;
    if (camera.type == "OrthographicCamera") {
        camera.left = frustumSize * aspect / - 2;
        camera.right = frustumSize * aspect / 2;
        camera.top = frustumSize / 2;
        camera.bottom = - frustumSize / 2;
    } else if (camera.type == "PerspectiveCamera") {
        camera.aspect = aspect;
    }
    camera.updateProjectionMatrix();
}

function changeCamera(event) {
    var selindex = event.currentTarget.selectedIndex;
    camera = cameras[selindex];
    control = controls[selindex];
    control.enabled = true; 
    for (var i=0; i<controls.length; i++) {
        if (i!=selindex) {
            controls[i].enabled = false;
        }
    }
    updateCamera();
}

var camtypenode = document.getElementById('cameraType_0');
camtypenode.onchange = changeCamera;
camtypenode.dispatchEvent(new Event('change'));

onWindowResize();
window.addEventListener('resize', onWindowResize);	


var xRotationEnabled = false;
var yRotationEnabled = false;
var zRotationEnabled = false;
var rotationSpeedFactor = 1;
var settingsShown = false;
var labelsShown = true;
var intervals = [];
var timeouts = [];
var explodingSpeed = 0.05;
var explodeScale = 0.000001;
var XMLS = new XMLSerializer();
var svgElement;
var renderId;

var render = function () {

	renderId = requestAnimationFrame(render);

//	comment in for automatic explosion
//	explode(updateFactor());

    var phi = 0.02 * rotationSpeedFactor;

    if (xRotationEnabled) {
        scene.rotation.x += phi;
    }
    if (yRotationEnabled) {
        scene.rotation.y += phi;
    }
    if (zRotationEnabled) {
        scene.rotation.z += phi;
    }

    control.update();
    renderer.render(scene, camera);
};

if ( THREE.WEBGL.isWebGLAvailable() ) {
	render();
} else {
	var warning = WEBGL.getWebGLErrorMessage();
	three.appendChild( warning );
}
    
function changeTransparency() {
    var opacity = 1-Number(event.currentTarget.value);
    for (var i=0; i<scene.children.length; i++) {
        child = scene.children[i];
        if ( child.userData.hasOwnProperty("facetmaterial") ) {
            if (Array.isArray(child.userData.facetmaterial)) {
                for (var j=0; j<child.userData.facetmaterial.length; j++) {
                    child.userData.facetmaterial[j].opacity = opacity;
                }
            } else {
                child.userData.facetmaterial.opacity = opacity;
            }    
        }
    }
}

function toggleDepthWrite(event) {
    depthwrite = event.currentTarget.checked;
    for (var i=0; i<scene.children.length; i++) {
        child = scene.children[i];
        if ( child.userData.hasOwnProperty("facetmaterial") ) {
            if (Array.isArray(child.userData.facetmaterial)) {
                for (var j=0; j<child.userData.facetmaterial.length; j++) {
                    child.userData.facetmaterial[j].depthWrite = depthwrite;
                }
            } else {
                child.userData.facetmaterial.depthWrite = depthWrite;
            }    
        }
    }
}

function changeRotationX(event){
    xRotationEnabled = event.currentTarget.checked;
}	

function changeRotationY(event){
    yRotationEnabled = event.currentTarget.checked;
}	

function changeRotationZ(event){
    zRotationEnabled = event.currentTarget.checked;
}	


function changeRotationSpeedFactor(event){
    rotationSpeedFactor = Number(event.currentTarget.value);
}

function resetScene(){
    scene.rotation.set(0,0,0);
    camera.position.set(0,0,5);
    camera.up.set(0,1,0);
}

function showSettings(event){
    document.getElementById('settings_0').style.visibility = 'visible';
    document.getElementById('showSettingsButton_0').style.visibility = 'hidden';
    document.getElementById('hideSettingsButton_0').style.visibility = 'visible';
    settingsShown = true;
}

function hideSettings(event){
    document.getElementById('settings_0').style.visibility = 'hidden';
    document.getElementById('showSettingsButton_0').style.visibility = 'visible';
    document.getElementById('hideSettingsButton_0').style.visibility = 'hidden';
    settingsShown = false;
}



var pos = 150* Math.PI;

function updateFactor() {
    pos++;
    return Math.sin(.01*pos)+1;
}

// ------------------------ FOLDING ------------------------------------------------
// ---------------------------------------------------------------------------------
// rotate point p around axis defined by points p1 and p2 by given angle
function rotate(p, p1, p2, angle ){   
    angle = -angle;
    var x = p.x, y = p.y, z = p.z, 
    a = p1.x, b = p1.y, c = p1.z, 
    u = p2.x-p1.x, v = p2.y-p1.y, w = p2.z-p1.z;
    var result = [];
    var L = u*u + v*v + w*w;
    var sqrt = Math.sqrt;
    var cos = Math.cos;
    var sin = Math.sin;

    result[0] = ((a*(v*v+w*w)-u*(b*v+c*w-u*x-v*y-w*z))*(1-cos(angle))+L*x*cos(angle)+sqrt(L)*(-c*v+b*w-w*y+v*z)*sin(angle))/L;
    result[1] = ((b*(u*u+w*w)-v*(a*u+c*w-u*x-v*y-w*z))*(1-cos(angle))+L*y*cos(angle)+sqrt(L)*(c*u-a*w+w*x-u*z)*sin(angle))/L;
    result[2] = ((c*(u*u+v*v)-w*(a*u+b*v-u*x-v*y-w*z))*(1-cos(angle))+L*z*cos(angle)+sqrt(L)*(-b*u+a*v-v*x+u*y)*sin(angle))/L;

    return result;
}

var fold = function(event){
    var obj = foldables[Number(event.currentTarget.name)];
    var foldvalue = Number(event.currentTarget.value);
    var scale = foldvalue - obj.userData.oldscale;

    for (var j=0; j<obj.userData.axes.length; j++) {
        rotateVertices(obj, j, scale);
    }
    update(obj);
    obj.userData.oldscale += scale;
    lookAtBarycenter(obj);
}

function lookAtBarycenter(obj){
    control.target = barycenter(obj);
}

function barycenter(obj) {
    var center = new THREE.Vector3(0,0,0);
    var points = obj.userData.points;
    for (var i=0; i<points.length; i++){
        center.add(points[i].vector);
    }
    center.divideScalar(points.length);
    return center;
}

function rotateVertices(obj, edge, scale) {
    var axes = obj.userData.axes;
    var subtrees = obj.userData.subtrees;
    var points = obj.userData.points;
    var angles = obj.userData.angles;
    if (edge < axes.length){
        for (var j=0; j<subtrees[edge].length; j++){
            var rotP = rotate(points[subtrees[edge][j]].vector, points[axes[edge][0]].vector,points[axes[edge][1]].vector, scale * (Math.PI - angles[edge]));
            points[subtrees[edge][j]].set(rotP[0],rotP[1],rotP[2]);
        }
    }
}

function update(obj) {
   updateFacesPosition(obj);
   updateEdgesPosition(obj);
}

if (foldables.length) {
    var settings = document.getElementById('settings_0');
    var foldDiv = document.createElement('div');
    foldDiv.id = 'fold_0';
    var title = document.createElement('strong');
    title.innerHTML = 'Fold';
    foldDiv.appendChild(title);
    foldDiv.className = 'group';
    for (var i=0; i<foldables.length; i++) {
        var range = document.createElement('input');
        range.type = 'range';
        range.min = 0;
        range.max = 1;
        range.value = 0;
        range.step = 0.001;
        range.name = String(i);
        range.oninput = fold;
        foldDiv.appendChild(range);
    }
    lookAtBarycenter(foldables[0]);
    settings.insertBefore(foldDiv,settings.childNodes[0]);
}

    
// ---------------------- EXPLOSION ------------------------------------------------
// ---------------------------------------------------------------------------------

if (explodableModel) {
    for (var i=0; i<scene.children.length; i++) {
        obj = scene.children[i];
        if ( obj.userData.explodable ) {
            computeCentroid(obj);
        }
    }
    document.getElementById('explodeRange_0').oninput = triggerExplode;
    document.getElementById('explodeCheckbox_0').onchange = triggerAutomaticExplode;
    document.getElementById('explodingSpeedRange_0').oninput = setExplodingSpeed;
    explode(0.000001);
}

function computeCentroid(obj) {
    centroid = new THREE.Vector3();
    obj.userData.points.forEach(function(pmpoint) {
        centroid.add(pmpoint.vector);			
    });
    centroid.divideScalar(obj.userData.points.length);
    obj.userData.centroid = centroid;
}

function explode(factor) {
    for (var i=0; i<scene.children.length; i++) {
        var obj = scene.children[i];
        if (obj.userData.hasOwnProperty("centroid")) { 
            var c = obj.userData.centroid;
            obj.position.set(c.x*factor, c.y*factor, c.z*factor);
        }
    }	
}

function triggerExplode(event){
    explodeScale = Number(event.currentTarget.value);
    explode(explodeScale);
}

function setExplodingSpeed(event){
    explodingSpeed = Number(event.currentTarget.value);
}

function triggerAutomaticExplode(event){
    if (event.currentTarget.checked){
        startExploding();
    } else {
        clearIntervals();
    }	
}

function startExploding(){
    intervals.push(setInterval(explodingInterval, 25));
}


function explodingInterval(){
    explodeScale += explodingSpeed;
    if (explodeScale <= 6){ 
        explode(explodeScale);
    }
    else{
        explode(6);
        explodeScale = 6;
        clearIntervals();
        timeouts.push(setTimeout(startUnexploding, 3000));
    }
    document.getElementById('explodeRange_0').value = explodeScale;
}


function startUnexploding(){
    intervals.push(setInterval(unexplodingInterval, 25));
}

function unexplodingInterval(){
    explodeScale -= explodingSpeed;
    if (explodeScale >= 0){	
        explode(explodeScale);
    }
    else {
        explode(0);
        explodeScale = 0;
        clearIntervals();
        timeouts.push(setTimeout(startExploding, 3000));
    }
    document.getElementById('explodeRange_0').value = explodeScale;
}

function clearIntervals(){
    intervals.forEach(function(interval){
        clearInterval(interval);
    });
    intervals = [];
    timeouts.forEach(function(timeout){
        clearTimeout(timeout);
    });
    timeouts = [];
}

// ---------------------- DISPLAY --------------------------------------------------
// ---------------------------------------------------------------------------------

const objectTypeInnerHTMLs = { points: "Points", pointlabels: "Point labels", lines: "Edges", edgelabels: "Edge labels", faces: "Faces", arrowheads: "Arrow heads" };
const objectTypeVisible = {};
Object.assign(objectTypeVisible,modelContains);
const sortedObjectTypeKeys = Object.keys(objectTypeInnerHTMLs).sort();
const shownObjectTypesList = document.getElementById('shownObjectTypesList_0');

function setVisibility(bool,objname) {
    for (var i=0; i<scene.children.length; i++){
        var obj = scene.children[i].getObjectByName(objname);
        if (obj) {
            obj.visible = bool;
        }
    }
}

function toggleObjectTypeVisibility(event){
    var name = event.currentTarget.name;
    var checked = event.currentTarget.checked;
    objectTypeVisible[name] = checked;
    if (name == "faces") {
        setVisibility(checked,"frontfaces");
        setVisibility(checked,"backfaces");
    } else {
        setVisibility(checked,name);
    }
}

for (var i=0; i<sortedObjectTypeKeys.length; i++){
    var key = sortedObjectTypeKeys[i];
    if (modelContains[key]) {
        var objTypeNode = document.createElement('span');
        objTypeNode.innerHTML = objectTypeInnerHTMLs[key] + '<br>';
        var checkbox = document.createElement('input');
        checkbox.type = 'checkbox';
        checkbox.checked = true;
        checkbox.name = key;
        checkbox.onchange = toggleObjectTypeVisibility;
        shownObjectTypesList.appendChild(checkbox);
        shownObjectTypesList.appendChild(objTypeNode);
    }
}

// ------------------------------------------------------

function toggleObjectVisibility(event){
    var nr = Number(event.currentTarget.name);
    scene.children[nr].visible = event.currentTarget.checked;
}

// append checkboxes for displaying or hiding objects
var shownObjectsList = document.getElementById('shownObjectsList_0');
for (var i=0; i<scene.children.length; i++){
    obj = scene.children[i];
    var objNode = document.createElement('span');
    objNode.innerHTML = obj.name + '<br>';
    var checkbox = document.createElement('input');
    checkbox.type = 'checkbox';
    checkbox.checked = true;
    checkbox.name = String(i);
    checkbox.onchange = toggleObjectVisibility;
    shownObjectsList.appendChild(checkbox);
    shownObjectsList.appendChild(objNode);
}

// ---------------------- SVG ------------------------------------------------------
// ---------------------------------------------------------------------------------

function takeSvgScreenshot() {
    if (objectTypeVisible["pointlabels"]) {
        setVisibility(false,"pointlabels");
    }
    if (objectTypeVisible["edgelabels"]) {
        setVisibility(false,"edgelabels");
    }
    svgRenderer.render(scene,camera);
    svgElement = XMLS.serializeToString(svgRenderer.domElement);
    
    if (objectTypeVisible["pointlabels"]) {
        setVisibility(true,"pointlabels");
    }
    if (objectTypeVisible["edgelabels"]) {
        setVisibility(true,"edgelabels");
    }

    if (document.getElementById('tab_0').checked){
        //show in new tab
        var myWindow = window.open("","");
        myWindow.document.body.innerHTML = svgElement;
    } else{
        // download svg file 
        download("screenshot.svg", svgElement);
    }
}

function download(filename, text) {
    var element = document.createElement('a');
    element.setAttribute('href', 'data:text/plain;charset=utf-8,' + encodeURIComponent(text));
    element.setAttribute('download', filename);

    element.style.display = 'none';
    document.body.appendChild(element);

    element.click();

    document.body.removeChild(element);
}


document.getElementById('transparencyRange_0').oninput = changeTransparency;
document.getElementById('depthWriteCheckbox_0').onchange = toggleDepthWrite;
document.getElementById('changeRotationX_0').onchange = changeRotationX;
document.getElementById('changeRotationY_0').onchange = changeRotationY;
document.getElementById('changeRotationZ_0').onchange = changeRotationZ;
document.getElementById('resetButton_0').onclick = resetScene;
document.getElementById('rotationSpeedRange_0').oninput = changeRotationSpeedFactor;
document.getElementById('takeScreenshot_0').onclick = takeSvgScreenshot;
document.getElementById('showSettingsButton_0').onclick = showSettings;
document.getElementById('hideSettingsButton_0').onclick = hideSettings;


// ------------------ SHORTCUTS --------------------------------------------
// -------------------------------------------------------------------------

/**
 * http://www.openjs.com/scripts/events/keyboard_shortcuts/
 * Version : 2.01.B
 * By Binny V A
 * License : BSD
 */
shortcut = {
	'all_shortcuts':{},//All the shortcuts are stored in this array
	'add': function(shortcut_combination,callback,opt) {
		//Provide a set of default options
		var default_options = {
			'type':'keydown',
			'propagate':false,
			'disable_in_input':false,
			'target':document,
			'keycode':false
		}
		if(!opt) opt = default_options;
		else {
			for(var dfo in default_options) {
				if(typeof opt[dfo] == 'undefined') opt[dfo] = default_options[dfo];
			}
		}

		var ele = opt.target;
		if(typeof opt.target == 'string') ele = document.getElementById(opt.target);
		var ths = this;
		shortcut_combination = shortcut_combination.toLowerCase();

		//The function to be called at keypress
		var func = function(e) {
			e = e || window.event;
			
			if(opt['disable_in_input']) { //Don't enable shortcut keys in Input, Textarea fields
				var element;
				if(e.target) element=e.target;
				else if(e.srcElement) element=e.srcElement;
				if(element.nodeType==3) element=element.parentNode;

				if(element.tagName == 'INPUT' || element.tagName == 'TEXTAREA') return;
			}
	
			//Find Which key is pressed
			if (e.keyCode) code = e.keyCode;
			else if (e.which) code = e.which;
			var character = String.fromCharCode(code).toLowerCase();
			
			if(code == 188) character=","; //If the user presses , when the type is onkeydown
			if(code == 190) character="."; //If the user presses , when the type is onkeydown

			var keys = shortcut_combination.split("+");
			//Key Pressed - counts the number of valid keypresses - if it is same as the number of keys, the shortcut function is invoked
			var kp = 0;
			
			//Work around for stupid Shift key bug created by using lowercase - as a result the shift+num combination was broken
			var shift_nums = {
				"`":"~",
				"1":"!",
				"2":"@",
				"3":"#",
				"4":"$",
				"5":"%",
				"6":"^",
				"7":"&",
				"8":"*",
				"9":"(",
				"0":")",
				"-":"_",
				"=":"+",
				";":":",
				"'":"\"",
				",":"<",
				".":">",
				"/":"?",
				"\\":"|"
			}
			//Special Keys - and their codes
			var special_keys = {
				'esc':27,
				'escape':27,
				'tab':9,
				'space':32,
				'return':13,
				'enter':13,
				'backspace':8,
	
				'scrolllock':145,
				'scroll_lock':145,
				'scroll':145,
				'capslock':20,
				'caps_lock':20,
				'caps':20,
				'numlock':144,
				'num_lock':144,
				'num':144,
				
				'pause':19,
				'break':19,
				
				'insert':45,
				'home':36,
				'delete':46,
				'end':35,
				
				'pageup':33,
				'page_up':33,
				'pu':33,
	
				'pagedown':34,
				'page_down':34,
				'pd':34,
	
				'left':37,
				'up':38,
				'right':39,
				'down':40,
	
				'f1':112,
				'f2':113,
				'f3':114,
				'f4':115,
				'f5':116,
				'f6':117,
				'f7':118,
				'f8':119,
				'f9':120,
				'f10':121,
				'f11':122,
				'f12':123
			}
	
			var modifiers = { 
				shift: { wanted:false, pressed:false},
				ctrl : { wanted:false, pressed:false},
				alt  : { wanted:false, pressed:false},
				meta : { wanted:false, pressed:false}	//Meta is Mac specific
			};
                        
			if(e.ctrlKey)	modifiers.ctrl.pressed = true;
			if(e.shiftKey)	modifiers.shift.pressed = true;
			if(e.altKey)	modifiers.alt.pressed = true;
			if(e.metaKey)   modifiers.meta.pressed = true;
                        
			for(var i=0; k=keys[i],i<keys.length; i++) {
				//Modifiers
				if(k == 'ctrl' || k == 'control') {
					kp++;
					modifiers.ctrl.wanted = true;

				} else if(k == 'shift') {
					kp++;
					modifiers.shift.wanted = true;

				} else if(k == 'alt') {
					kp++;
					modifiers.alt.wanted = true;
				} else if(k == 'meta') {
					kp++;
					modifiers.meta.wanted = true;
				} else if(k.length > 1) { //If it is a special key
					if(special_keys[k] == code) kp++;
					
				} else if(opt['keycode']) {
					if(opt['keycode'] == code) kp++;

				} else { //The special keys did not match
					if(character == k) kp++;
					else {
						if(shift_nums[character] && e.shiftKey) { //Stupid Shift key bug created by using lowercase
							character = shift_nums[character]; 
							if(character == k) kp++;
						}
					}
				}
			}
			
			if(kp == keys.length && 
						modifiers.ctrl.pressed == modifiers.ctrl.wanted &&
						modifiers.shift.pressed == modifiers.shift.wanted &&
						modifiers.alt.pressed == modifiers.alt.wanted &&
						modifiers.meta.pressed == modifiers.meta.wanted) {
				callback(e);
	
				if(!opt['propagate']) { //Stop the event
					//e.cancelBubble is supported by IE - this will kill the bubbling process.
					e.cancelBubble = true;
					e.returnValue = false;
	
					//e.stopPropagation works in Firefox.
					if (e.stopPropagation) {
						e.stopPropagation();
						e.preventDefault();
					}
					return false;
				}
			}
		}
		this.all_shortcuts[shortcut_combination] = {
			'callback':func, 
			'target':ele, 
			'event': opt['type']
		};
		//Attach the function with the event
		if(ele.addEventListener) ele.addEventListener(opt['type'], func, false);
		else if(ele.attachEvent) ele.attachEvent('on'+opt['type'], func);
		else ele['on'+opt['type']] = func;
	},

	//Remove the shortcut - just specify the shortcut and I will remove the binding
	'remove':function(shortcut_combination) {
		shortcut_combination = shortcut_combination.toLowerCase();
		var binding = this.all_shortcuts[shortcut_combination];
		delete(this.all_shortcuts[shortcut_combination])
		if(!binding) return;
		var type = binding['event'];
		var ele = binding['target'];
		var callback = binding['callback'];

		if(ele.detachEvent) ele.detachEvent('on'+type, callback);
		else if(ele.removeEventListener) ele.removeEventListener(type, callback, false);
		else ele['on'+type] = false;
	}
}

shortcut.add("Alt+Left",function() {
	var event = new Event('click');
	if (settingsShown){
		document.getElementById('hideSettingsButton_0').dispatchEvent(event);
	} else {
		document.getElementById('showSettingsButton_0').dispatchEvent(event);
	}
});


// COMMON_CODE_BLOCK_END

});});
      </script>
   </body>
</html>
</HTML>
As polytopes and all other objects in ''%%polymake%%'''s object hierarchy the graphs from the application ''%%graph%%'' are immutable objects. It is not possible to add a node or to delete an edge. It is instructive to look at the beginning of the file ''%%apps/graph/graph_properties.rules%%'' which reads like this.

<code>
declare object Graph<Dir=Undirected> {

# combinatorial description of the Graph in the form of adjacency matrix
property ADJACENCY : GraphAdjacency<Dir>;

...
</code>
The key property of a graph object is its ''%%ADJACENCY%%''. For each node all neighbors are listed. Here we want to focus on the type ''%%GraphAdjacency%%'' of this property. This refers to C++ class from the Polymake Template Library named ''%%Graph%%'', and this is where the data structure and most algorithms reside. It is possible to directly manipulate objects of this type, and these are //not// immutable, they can be changed. The following shows how one can create a 5-cycle. Calling the method ''%%edge%%'' creates an edge if it did not exist before. The output is the ordered list of neighbors per node.

<code perl>
> $g=new GraphAdjacency(5);                      
> for (my $i=0; $i<5; ++$i) { $g->edge($i,($i+1)%5) };
> print $g;
{1 4}
{0 2}
{1 3}
{2 4}
{0 3}
</code>
If a graph has many nodes it is convenient to know which line of the output refers to which node. If an array of labels is given this could also be used instead of the numbers which are the default.

<code perl>
> print rows_labeled($g);
0:1 4
1:0 2
2:1 3
3:2 4
4:0 3
</code>
There are other ways to change such a graph. Contracting the edge //(x,y)// where //x// is smaller than //y// implies that the node //y// is destroyed.

<code perl>
> $g->delete_edge(0,1);
> $g->contract_edge(2,3);
> $g->squeeze();
</code>
However, most of our graph algorithms expect a graph with consecutively numbered nodes. The function ''%%squeeze%%'' takes care of a proper renumbering, but this takes linear time in the number of nodes.

<code perl>
> print rows_labeled($g);
0:3
1:2
2:1 3
3:0 2
</code>
How do I iterate over the adjacent nodes to a given node?

<code>
foreach (@{$g->adjacent_nodes(0)}) {
   print "node number $_ is adjacent to node number 0\n";
}
</code>
It is also legal to copy all adjacent nodes to an array as in:

<code>
@x = @{$g->adjacent_nodes(0)};
</code>
Subsequently, the individial neighbors can be accessed, for instance, as ''%%$x[1]%%''. However, for technical reasons too difficult to explain here, it is //not// legal to write ''%%$g->adjacent_nodes(0)->[1]%%''! Usually it is preferred to avoid copying; so use constructions like ''%%foreach%%'' and ''%%map%%'' if possible.

===== Defining a Graph from Scratch =====

You can also work with graphs independent of their connection to polytopes. We will switch to ''%%application "graph"%%'' for the following commands, but this is not strictly necessary. We want to define a new object of type ''%%Graph%%'' in ''%%polymake%%''.

The key property of a graph is its adjacency matrix, which is stored in the property ''%%ADJACENCY%%''. It lists the neighbors of each node. We use again the above example of a 5-cycle C<sub>5</sub> with consecutively numbered nodes. Then one can define C<sub>5</sub> by

<code perl>
> application "graph";
> $g=new Graph(ADJACENCY=>[[1,4],[0,2],[1,3],[2,4],[0,3]]);
</code>
The list of edges of the graph is induced by the adjacency matrix (please note that in a undirected graph each edge appears twice). You can get an explicit list of the edges with the user function ''%%EDGES%%''.

<code perl>
> print $g->EDGES;
{0 1}
{1 2}
{2 3}
{0 4}
{3 4}
</code>
Note however, that this list is not stored in the object, as it is just a different view on the adjacency matrix.

Most often when you define a graph you would not write it down as a list of adjacencies, but as a list of edges. For convenience, ''%%polymake%%'' provides a way to create a graph from a list of edges. The same 5-cycle as above could also be defined via

<code perl>
>  $g=graph_from_edges([[0,1],[1,2],[2,3],[0,4],[3,4]]);
</code>
The order of the edges, and the order of the nodes for each edge in a undirected case, is not important. We can check the adjacency matrix,

<code perl>
> print $g->ADJACENCY;
{1 4}
{0 2}
{1 3}
{2 4}
{0 3}
</code>
and continue to work with the graph by e.g. checking its ''%%DIAMETER%%'', ''%%BIPARTITE%%''-ness or other properties:

<code perl>
> print $g->DIAMETER;
2
> print $g->BIPARTITE;
false
> print $g->MAX_CLIQUES;
{{0 1} {0 4} {1 2} {2 3} {3 4}}
</code>
===== Directed Graphs =====

By specifying the template parameter ''%%Directed%%'' a graph is born as a directed graph. Properties which make sense for directed graphs work as expected. A directed graph may have two arcs between any two nodes with opposite orientations.

<code perl>
> $g=new Graph<Directed>(ADJACENCY=>[[1],[2],[3],[2,4],[0]]);
> print $g->DIAMETER;
4
</code>
Some properties of graphs do not make sense for directed graph. Here is an example of an undirected graph property which does not make sense for directed graphs.

<code perl>
> #print $g->MAX_CLIQUES;
polymake:  ERROR: Object Graph<Directed> does not have a property or method MAX_CLIQUES
</code>
Graphs with multiple edges/arcs are currently not supported.

===== Visualizing Graphs =====

Like other "big" ''%%polymake%%'' objects the ''%%Graph%%'' class has a member (function) ''%%VISUAL%%'' which returns an abstract visualization object. Depending on the configuration it typically uses ''%%JReality%%'' or ''%%JavaView%%''. Particularly interesting for graph drawing is the visualization via ''%%Graphviz%%''.

<code perl>
> svg($g->VISUAL);
> graphviz($g->VISUAL);
</code>
{{ tutorials:master:apps_graph:output_0.svg }}
Note that the latter starts a postscript viewer with the ''%%Graphviz%%'' output. Make sure that the custom variable ''%%$Postscript::viewer%%'' is set to something reasonable (like, e.g., ''%%/usr/bin/evince%%'').