| 1 | import * as is from '../../is';
|
| 2 | import { defaults } from '../../util';
|
| 3 |
|
| 4 | const hierholzerDefaults = defaults({
|
| 5 | root: undefined,
|
| 6 | directed: false
|
| 7 | });
|
| 8 |
|
| 9 | let elesfn = ({
|
| 10 | hierholzer: function( options ){
|
| 11 | if (!is.plainObject(options)) {
|
| 12 | let args = arguments;
|
| 13 | options = { root: args[0], directed: args[1] };
|
| 14 | }
|
| 15 | let { root, directed } = hierholzerDefaults(options);
|
| 16 | let eles = this;
|
| 17 | let dflag = false;
|
| 18 | let oddIn;
|
| 19 | let oddOut;
|
| 20 | let startVertex;
|
| 21 | if (root) startVertex = is.string(root) ? this.filter(root)[0].id() : root[0].id();
|
| 22 | let nodes = {};
|
| 23 | let edges = {};
|
| 24 |
|
| 25 | if (directed) {
|
| 26 | eles.forEach(function(ele){
|
| 27 | let id = ele.id();
|
| 28 | if(ele.isNode()) {
|
| 29 | let ind = ele.indegree(true);
|
| 30 | let outd = ele.outdegree(true);
|
| 31 | let d1 = ind - outd;
|
| 32 | let d2 = outd - ind;
|
| 33 | if (d1 == 1) {
|
| 34 | if (oddIn) dflag = true;
|
| 35 | else oddIn = id;
|
| 36 | } else if (d2 == 1) {
|
| 37 | if (oddOut) dflag = true;
|
| 38 | else oddOut = id;
|
| 39 | } else if ((d2 > 1) || (d1 > 1)) {
|
| 40 | dflag = true;
|
| 41 | }
|
| 42 | nodes[id] = [];
|
| 43 | ele.outgoers().forEach(e => {
|
| 44 | if (e.isEdge()) nodes[id].push(e.id());
|
| 45 | });
|
| 46 | } else {
|
| 47 | edges[id] = [undefined, ele.target().id()];
|
| 48 | }
|
| 49 | });
|
| 50 | } else {
|
| 51 | eles.forEach(function(ele){
|
| 52 | let id = ele.id();
|
| 53 | if(ele.isNode()) {
|
| 54 | let d = ele.degree(true);
|
| 55 | if (d%2) {
|
| 56 | if (!oddIn) oddIn = id;
|
| 57 | else if (!oddOut) oddOut = id;
|
| 58 | else dflag = true;
|
| 59 | }
|
| 60 | nodes[id] = [];
|
| 61 | ele.connectedEdges().forEach(e => nodes[id].push(e.id()));
|
| 62 | } else {
|
| 63 | edges[id] = [ele.source().id(), ele.target().id()];
|
| 64 | }
|
| 65 | });
|
| 66 | }
|
| 67 |
|
| 68 | let result = {
|
| 69 | found: false,
|
| 70 | trail: undefined
|
| 71 | };
|
| 72 |
|
| 73 | if (dflag) return result;
|
| 74 | else if (oddOut && oddIn) {
|
| 75 | if (directed) {
|
| 76 | if (startVertex && (oddOut != startVertex)) {
|
| 77 | return result;
|
| 78 | }
|
| 79 | startVertex = oddOut;
|
| 80 | } else {
|
| 81 | if (startVertex && (oddOut != startVertex) && (oddIn != startVertex)) {
|
| 82 | return result;
|
| 83 | } else if (!startVertex) {
|
| 84 | startVertex = oddOut;
|
| 85 | }
|
| 86 | }
|
| 87 | } else {
|
| 88 | if (!startVertex) startVertex = eles[0].id();
|
| 89 | }
|
| 90 |
|
| 91 | const walk = (v) => {
|
| 92 | let currentNode = v;
|
| 93 | let subtour = [v];
|
| 94 | let adj, adjTail, adjHead;
|
| 95 | while (nodes[currentNode].length) {
|
| 96 | adj = nodes[currentNode].shift();
|
| 97 | adjTail = edges[adj][0];
|
| 98 | adjHead = edges[adj][1];
|
| 99 | if (currentNode != adjHead) {
|
| 100 | nodes[adjHead] = nodes[adjHead].filter(e => e != adj);
|
| 101 | currentNode = adjHead;
|
| 102 | } else if (!directed && (currentNode != adjTail)) {
|
| 103 | nodes[adjTail] = nodes[adjTail].filter(e => e != adj);
|
| 104 | currentNode = adjTail;
|
| 105 | }
|
| 106 | subtour.unshift(adj);
|
| 107 | subtour.unshift(currentNode);
|
| 108 | }
|
| 109 | return subtour;
|
| 110 | };
|
| 111 |
|
| 112 | let trail = [];
|
| 113 | let subtour = [];
|
| 114 | subtour = walk(startVertex);
|
| 115 | while (subtour.length != 1) {
|
| 116 | if (nodes[subtour[0]].length == 0) {
|
| 117 | trail.unshift(eles.getElementById(subtour.shift()));
|
| 118 | trail.unshift(eles.getElementById(subtour.shift()));
|
| 119 | } else {
|
| 120 | subtour = walk(subtour.shift()).concat(subtour);
|
| 121 | }
|
| 122 | }
|
| 123 | trail.unshift(eles.getElementById(subtour.shift()));
|
| 124 |
|
| 125 | for (let d in nodes) {
|
| 126 | if (nodes[d].length) {
|
| 127 | return result;
|
| 128 | }
|
| 129 | }
|
| 130 | result.found = true;
|
| 131 | result.trail = this.spawn( trail, true );
|
| 132 | return result;
|
| 133 | },
|
| 134 | });
|
| 135 |
|
| 136 | export default elesfn;
|