Анализ процессов, Графы

«Непитоновский» граф

Время прочтения: 7 мин.

Графы так или иначе связаны с анализом данных. Они либо визуализируют результат этого анализа, либо являются средством для его проведения.

Само же словосочетание «анализ данных» практически всегда равно python. Но эта статья будет посвящена веб-приложению графовой аналитики, написанному на C# + JavaScript.

Для простоты восприятия структурированной информации можно использовать различные инструменты: таблицы, схемы и тд. Но нагляднее отобразить её в виде связанного, а иногда и направленного графа.

В процессе работы мы столкнулись с проблемой отрисовки графов по различным входным данным, в требованиях было желание универсальности разрабатываемого решения.

Великий Интернет, конечно же знает всё и очень настойчиво советовал использовать python с библиотеками NetworkX, Plolty и подобные. Однако у нас было ограничение в серверном ПО. При чём тут сервер? Просто наше универсальное средство должно было быть доступно каждому сотруднику. Так вот, сервер… Он имеет возможность публикации решений на C# или на python2 с большим ограничением по доступным библиотекам. Выбор был очевиден: C# – простота и адекватность решения.

Сервер, доступность решения, web-версия, frontend… Ощущаете это? О, да… Именно JavaScript идеально вписался в наше «представление о прекрасном». На нём есть отличная библиотека Cytoscape.js для изображения различных вариаций на тему графов.

Перейдём к любимой части повествования: код и с чем его едят.

Для реализации простого интерактивного графа, состоящего из 2 вершин и ребра между ними, нам потребуется 3 файла: index.html – файлик запуска красоты; code.js – рабочая лошадка и style.css – стиль и расположения.

Index.html
<!DOCTYPE html>
<html>
<head>
<link href="style.css" rel="stylesheet" />
<meta name="viewport" charset=utf-8 content="user-scalable=no, initial-scale=1.0, minimum-scale=1.0, maximum-scale=1.0, minimal-ui">
<title>First Example</title>
<script src="cytoscape.min.js"></script>
</head>
<body>
<div id="cy"></div>
<script src="code.js"></script>
</body>
</html>

Index.html довольно шаблонный. Основные моменты, на которые стоит обратить внимание, это указание ссылки на файл стилей (<link href="style.css" rel="stylesheet" />), подключение файла со скриптом (<script src="code.js"></script>) и подключение библиотеки (<script src="cytoscape.min.js"></script>).

style.css
body { 
  font: 14px helvetica neue, helvetica, arial, sans-serif;
}

#cy {
  height: 100%;
  width: 100%;
  position: absolute;
  left: 0;
  top: 0;
}

В файле со стилями задаются параметры шрифтов, размера и координат поля для размещения построенного графа. В Index-файле можно расположить много дополнительных элементов, стили которых лучше прописать в style.css.

code.js
var cy = window.cy = cytoscape({
  container: document.getElementById('cy'),
  boxSelectionEnabled: false,
  layout: {
    name: 'preset',
    padding: 5,
  },
  
  style: [
    {
      selector: 'node',
      css: {
        'content': 'data(id)',
        'text-valign': 'center',
        'text-halign': 'center'
      }
    },
    {
      selector: 'edge',
      css: {
        'curve-style': 'bezier',
        'target-arrow-shape': 'triangle'
      }
    }
  ],

  elements: {
    nodes: [
      { data: { id: 'a' }, position: { x: 10, y: 15 } },
      { data: { id: 'b' }, position: { x: 100, y: 65 } }
    ],
    edges: [
      { data: { id: 'ab', source: 'a', target: 'b' } }
    ]
  },
});

Самым интересным, на мой взгляд, является исполняемый код в js файле. Именно в нём можно задать различные формы стрелок для рёбер ('target-arrow-shape': 'triangle'), параметры вершин, например, цвет и размер ("height": n_height, "width": n_ width, "color": n_color).

В зависимости от указанного значения в поле Layout name может быть задана различная форма графа. Например, мы создавали две окружности, одна из которых вложена в другую.

В результате открытия файла Index.html в браузере будет отображено следующее:

Рисунок 1 – Результат выполнения тестовой программы

К чему был упомянут C#, если всё работает на 3 файлах? Он обеспечивает возможность публикации приложения на сервере. Если создать новый проект по архитектурному паттерну MVC (Model-View-Controller) и перенести код из Index.html в представление, а остальные файлы добавить в скрипты, то изменив пути их подключения, получим самостоятельное приложение с возможностью размещения на сервере.

Как можно заметить, прописывать каждый узел и ребро между ними явно затруднительно и ни о какой универсальности речи быть не может. Тогда добавим в code.js чтение данных из txt файлов и их визуализацию на странице.

code.js
document.getElementById('file-input').addEventListener('change', function (evt) {
    elements = [];
    let reader = new FileReader();
    reader.readAsText(evt.target.files[0], "utf-8");
    reader.onerror = function (event) { alert("Фйл не может быть прочитан!"); }
    reader.onload = function (event) {
        createElement(event.target.result);
        window.cy = createGraph(); 
    }    
});

function createElement(arr) {
    let rows = arr.split("\n");
    for (i = 0; i < rows.length; i++) {
        if (rows[i] == "") break;
        let columns = rows[i].split(";");
        let lineName = "line" + i;
        elements.push({
            "data": {
                "id": columns[0],
                "degr": "6",
                "height": "20",
                "width": "20",
                "color": "#FFFF00",
                "shape": "round",
            },
            "group": "nodes"
        });
        elements.push({
            "data": {
                "id": columns[1],
                "degr": "2",
                "height": "40",
                "width": "40",
                "color": "#00CC00",
                "shape": "rectangle",
            },
            "group": "nodes"
        });
        elements.push({
            "data": {
                "id": lineName,
                "source": (columns[2] >= 0) ? columns[0] : columns[1],
                "target": (columns[2] >= 0) ? columns[1] : columns[0],
                "width": "5",
                "color": "#708090",
                "style": "Solid",
                "arrow": "triangle",
                "opacity": "0.65"
            },
            "group": "edges"
        });
    }
}

function createGraph() {
    var cy = window.cy = cytoscape({
        container: document.getElementById('cy'),
        layout: {
            name: 'concentric',
            concentric: function (node) { return node.data('degr'); },
            levelWidth: function () { return 2; }
        },
        style: [{
            selector: 'node',
            style: {
                'content': 'data(id)',
                'background-color': 'data(color)',
                'width': 'data(width)',
                'height': 'data(height)',
                'shape': 'data(shape)'
            }
        }, {
            selector: 'edge',
            style: {
                'curve-style': 'straight',
                'width': 'data(width)',
                'opacity': 'data(opacity)',
                'target-arrow-shape': 'data(arrow)',
                'line-color': 'data(color)',
                'target-arrow-color': 'data(color)'
            }
        }],
        elements: elements,
        wheelSensitivity: 0.5,
    });
    return cy;
}

И, соответственно на страницу Index.html или представления необходимо добавить кнопку для выбора файла.

Index.html
<!DOCTYPE html>
<html>
<head>
<link href="style.css" rel="stylesheet" />
<meta name="viewport" charset=utf-8 content="user-scalable=no, initial-scale=1.0, minimum-scale=1.0, maximum-scale=1.0, minimal-ui">
<title>First Example</title>
<script src="cytoscape.min.js"></script>
</head>
<body>
<h1>Инструмент для работы с графами</h1><br>
<div class="line">
<button id="graphml" onclick="document.getElementById('file-input').click();"><b>Выбрать файл</b></button>
<input id="file-input" type="file" name="name" style="display: none;" />
</div>
<div id="cy"></div>
<script src="code.js"></script>
</body>
</html>

Добавим дополнительные стили и посмотрим на приведённый ниже рисунок, который является результатом наших модификаций.

style.css
body { 
  font: 14px helvetica neue, helvetica, arial, sans-serif;
}

#cy {
  height: 100%;
  width: 100%;
  position: absolute;
  left: 0;
  top: 0;
} 

#graphml {
  background-color: #2bc528;
  color: white;
  border: none;
  opacity: 0.8;
  padding: 7px 10px;
}

.line{
  position:absolute;
  margin-top: 10px;
  margin-bottom: 10px;
  z-index: 900;
}

Входной файл для примера:

Pers1; Comp1; 10
Pers1; Comp2; 15
Pers1; Comp3; 5
Pers1; Comp4; 5
Pers2; Comp1; 3
Pers2; Comp5; 5
Pers2; Comp2; 80
Pers2; Comp4; 1
Pers3; Comp5; 25
Pers3; Comp1; 45
Pers3; Comp6; 17
Pers3; Comp3; 17
Pers4; Comp6; 18
Pers4; Comp1; 71
Pers4; Comp5; 71
Pers4; Comp2; 83
Рисунок 2 – Результат работы после прочтения входного файла

Если во входном файле поставить отрицательное значение в третьем столбце, то направление стрелки изменится на противоположное.

Полученный инструмент уже можно использовать как приложение для визуализации графов, готовое к публикации на сервере. Однако, изменяя различные параметры можно получить довольно интересный и полезный инструмент для анализа больших данных.

В контексте поставленной перед нами задачей, приведённый код был модернизирован и результат его работы представлен на следующих рисунках.

На рисунке 3 размер и цвет вершин зависит от суммы взаимодействия вершин друг с другом, а на рисунке 4 с помощью рассматриваемой библиотеки получилось построить граф с областями. Главное условие для него – разные имена вершин во всех квадратах, поэтому были использованы дополнительные индексы от 1 до 3.

Рисунок 3 – Граф взаимосвязей людей и компаний
Рисунок 3 – Граф взаимосвязей между семейной парой

Замечательную библиотеку можно скачать с официального сайта http://cytoscape.org, а подробные и интерактивные примеры можно посмотреть по ссылке: http://js.cytoscape.org.

А как вы относитесь к анализу данных не на python?

Советуем почитать