index.html - master - Ladlen/graph

index.html
264 строки10 KB
Dolgov Dmitriy
случайные вершины и рёбра
03 мар 2017, 16:27
03 мар 2017, 16:274220049
<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>Случайный граф.</title>

    <script type="text/javascript" src="https://code.jquery.com/jquery-3.1.1.min.js"></script>
    <script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/vis/4.18.1/vis.min.js"></script>

    <link type="text/css" rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/vis/4.18.1/vis.min.css">

    <style type="text/css">
        #container {
            width: 80%;
            margin: 10px auto;
        }

        #mynetwork, #mynetwork_text {
            width: 49%;
            height: 600px;
            border: 1px solid lightgray;
            /*margin: 10px 0;*/
            display: inline-block;
        }

        #mynetwork_text {
            overflow: auto;
            background-color: #EEE;
            padding: 10px;
            -webkit-box-sizing: border-box; /* Safari/Chrome, other WebKit */
            -moz-box-sizing: border-box; /* Firefox, other Gecko */
            box-sizing: border-box; /* Opera/IE 8+ */
        }

        table td {
            vertical-align: top;
        }

        #mynetwork_text table {
            border-spacing: 0;
            border-collapse: collapse;
        }

        #mynetwork_text table td, #mynetwork_text table th {
            border: 1px steelblue dashed;
            text-align: center;
            vertical-align: middle;
            padding: 5px;
        }

        .right {
            color: green;
        }

        .wrong {
            color: red;
        }

    </style>

</head>
<body>

<div id="container">
    <table style="width: 100%">
        <tr>
            <td>
                <table>
                    <tr>
                        <td>
                            <label for="nodes">Максимум вершин:</label>
                        </td>
                        <td>
                            <!--<input type="text" maxlength="3" id="nodes" value="5">-->
                            <input type="text" maxlength="3" id="nodes" value="10">
                        </td>
                    </tr>
                    <tr>
                        <td>
                            <label for="edges">Максимум рёбер:</label>
                        </td>
                        <td>
                            <!--<input type="text" maxlength="3" id="edges" value="5">-->
                            <input type="text" maxlength="3" id="edges" value="30">
                        </td>
                    </tr>
                </table>
            </td>
            <td>
                <!--<label for="simple">Простой граф: <input type="checkbox" id="simple" checked="checked"></label><br>-->
                <!--<label for="connected">Cвязный граф: <input type="checkbox" id="connected" checked="checked"></label>-->
            </td>
            <td>
                <button id="generate">Сгенерировать случайный граф</button>
            </td>
        </tr>
    </table>
    <div id="mynetwork"></div>
    <div id="mynetwork_text"></div>

</div>

<script type="text/javascript">
    $(function () {
        function Graph() {
            /**
             * Returns a random integer between min (inclusive) and max (inclusive)
             * Using Math.round() will give you a non-uniform distribution!
             */
            function getRandomInt(min, max) {
                return Math.floor(Math.random() * (max - min + 1)) + min;
            }

            function getEdgesNodes() {
                /*return {
                    'nodes': $("#nodes").val(),
                    'edges': $("#edges").val()
                };*/
                return {
                    'nodes': getRandomInt(1, $("#nodes").val()),
                    'edges': getRandomInt(1, $("#edges").val())
                }
            }

            function mkNodeValues(edgesNodes) {
                var nodeValues = [];
                for (var i = 0; i < edgesNodes.nodes; ++i) {
                    nodeValues.push({id: i, label: 'Узел ' + i});
                }
                return nodeValues;
            }

            function mkEdgeValues(edgesNodes) {
                var edgeValues = [];
                for (i = 0; i < edgesNodes.edges; ++i) {
                    var from = getRandomInt(0, edgesNodes.nodes - 1);
                    var to = getRandomInt(0, edgesNodes.nodes - 1);
                    edgeValues.push({id: i, from: from, to: to, label: i, font: {align: 'middle'}});
                }
                return edgeValues;
            }

            function mkNodeEdgesInfo(edgeValues) {
                var nodeEdgesInfo = [];
                for (var id in edgeValues) {
                    if (!nodeEdgesInfo[edgeValues[id].from]) {
                        nodeEdgesInfo[edgeValues[id].from] = [];
                    }
                    if (!nodeEdgesInfo[edgeValues[id].to]) {
                        nodeEdgesInfo[edgeValues[id].to] = [];
                    }
                    nodeEdgesInfo[edgeValues[id].from].push(edgeValues[id].id);
                    nodeEdgesInfo[edgeValues[id].to].push(edgeValues[id].id);
                }
                return nodeEdgesInfo;
            }

            function ifConnected(nodeValues, edgeValues, nodeEdgesInfo) {
                var nodeMap = Array.apply(null, Array(nodeValues.length)).map(Number.prototype.valueOf, 1);
                nodeMap[0] = 2;

                for (; ;) {
                    var secMark = nodeMap.indexOf(2);
                    if (secMark == -1 || !nodeEdgesInfo[secMark]) {
                        break;
                    }
                    nodeMap[secMark] = 3;
                    for (var id in nodeEdgesInfo[secMark]) {
                        if (nodeMap[edgeValues[nodeEdgesInfo[secMark][id]].from] == 1) {
                            nodeMap[edgeValues[nodeEdgesInfo[secMark][id]].from] = 2;
                        }
                        if (nodeMap[edgeValues[nodeEdgesInfo[secMark][id]].to] == 1) {
                            nodeMap[edgeValues[nodeEdgesInfo[secMark][id]].to] = 2;
                        }
                    }
                }

                return nodeMap.indexOf(1) == -1 ? true : false;
            }

            function hasOddDegree(nodeValues, nodeEdgesInfo) {
                var hasOddDegree = false;
                for (var id in nodeValues) {
                    var nId = nodeValues[id].id;
                    var degree = nodeEdgesInfo[nId] ? nodeEdgesInfo[nId].length : 0;
                    if (degree % 2 == 1) {
                        hasOddDegree = true;
                        break;
                    }
                }
                return hasOddDegree;
            }

            function mkResultString(right, rightString, wrongString) {
                return "<span class='" + (right ? "right" : "wrong") + "'>" + (right ? rightString : wrongString) + "</span>";
            }

            function showTextData(edgesNodes, nodes, edges, nodeEdgesInfo, connected, oddDegree) {
                var id;
                var s = "Вершин: " + edgesNodes.nodes + "; Рёбер: " + edgesNodes.edges + ".<br><br>"
                        + mkResultString(connected, "Граф связный", "Граф НЕ связный") + "<br>"
                        + mkResultString(!oddDegree, "Граф НЕ содержит вершины нечётной степени", "Граф содержит вершины нечётной степени") + "<br>"
                        + mkResultString(connected && !oddDegree, "Эйлеров цикл", "НЕ эйлеров цикл") + "<br>"
                        + "<br>Вершины:<br>"
                        + "<table><tr><th>ID</th><th>Степень</th><th>Рёбра</th></tr>";
                for (id in nodes) {
                    var nId = nodes[id].id;
                    var edgesList = nodeEdgesInfo[nId] ? nodeEdgesInfo[nId].join() : "&lt;-нет-&gt;";
                    var edgesListLength = nodeEdgesInfo[nId] ? nodeEdgesInfo[nId].length : 0;
                    s += "<tr><td>" + nId + "</td><td>" + edgesListLength + "</td><td>" + edgesList + "</td></tr>";
                }
                s += "</table><br>Рёбра:<br>"
                        + "<table><tr><th>ID</th><th>Вершины</th></tr>";

                for (id in edges) {
                    s += "<tr><td>" + edges[id].id + "</td><td>" + edges[id].from + " - " + edges[id].to + "</td></tr>";
                }

                s += "</table><br>&nbsp;<br>";

                $("#mynetwork_text").html(s);
            }

            return {
                generateRandom: function () {
                    var edgesNodes = getEdgesNodes();

                    var nodeValues = mkNodeValues(edgesNodes);
                    var edgeValues = mkEdgeValues(edgesNodes);

                    var nodeEdgesInfo = mkNodeEdgesInfo(edgeValues);

                    var connected = ifConnected(nodeValues, edgeValues, nodeEdgesInfo);
                    var oddDegree = hasOddDegree(nodeValues, nodeEdgesInfo);

                    var nodes = new vis.DataSet(nodeValues);
                    var edges = new vis.DataSet(edgeValues);

                    showTextData(edgesNodes, nodeValues, edgeValues, nodeEdgesInfo, connected, oddDegree);

                    // create a network
                    var container = document.getElementById('mynetwork');
                    var data = {
                        nodes: nodes,
                        edges: edges
                    };
                    var options = {};
                    var network = new vis.Network(container, data, options);
                }
            }
        }

        var gr = new Graph;
        gr.generateRandom();

        $("#generate").click(function () {
            gr.generateRandom();
        });
    });

</script>

</body>
</html>