Реализация графов на php

Saved searches

Use saved searches to filter your results more quickly

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session.

GraPHP is the mathematical graph/network library written in PHP.

License

graphp/graph

This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?

Sign In Required

Please sign in to use Codespaces.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching Xcode

If nothing happens, download Xcode and try again.

Launching Visual Studio Code

Your codespace will open once ready.

There was a problem preparing your codespace, please try again.

Latest commit

Git stats

Files

Failed to load latest commit information.

README.md

GraPHP is the mathematical graph/network library written in PHP.

Development version: This branch contains the code for the upcoming 1.0 release. For the code of the current stable 0.9 release, check out the 0.9.x branch.

The upcoming 1.0 release will be the way forward for this package. However, we will still actively support 0.9.x for those not yet on the latest version. See also installation instructions for more details.

Table of contents

Once installed, let’s initialize a sample graph:

 require __DIR__ . '/vendor/autoload.php'; $graph = new Graphp\Graph\Graph(); // create some cities $rome = $graph->createVertex(array('name' => 'Rome')); $madrid = $graph->createVertex(array('name' => 'Madrid')); $cologne = $graph->createVertex(array('name' => 'Cologne')); // build some roads $graph->createEdgeDirected($cologne, $madrid); $graph->createEdgeDirected($madrid, $rome); // create loop $graph->createEdgeDirected($rome, $rome);

Let’s see which city (Vertex) has a road (i.e. an edge pointing) to Rome:

foreach ($rome->getVerticesEdgeFrom() as $vertex) < echo $vertex->getAttribute('name') . ' leads to Rome' . PHP_EOL; // result: Madrid and Rome itself lead to Rome >

This library is built around the concept of mathematical graph theory (i.e. it is not a charting library for drawing a graph of a function). In essence, a graph is a set of nodes with any number of connections in between. In graph theory, vertices (plural of vertex) are an abstract representation of these nodes, while connections are represented as edges. Edges may be either undirected («two-way») or directed («one-way», aka di-edges, arcs).

Depending on how the edges are constructed, the whole graph can either be undirected, can be a directed graph (aka digraph) or be a mixed graph. Edges are also allowed to form loops (i.e. an edge from vertex A pointing to vertex A again). Also, multiple edges from vertex A to vertex B are supported as well (aka parallel edges), effectively forming a multigraph (aka pseudograph). And of course, any combination thereof is supported as well. While many authors try to differentiate between these core concepts, this library tries hard to not impose any artificial limitations or assumptions on your graphs.

This library provides the core data structures for working with graphs, its vertices, edges and attributes.

There are several official components built on top of these structures to provide commonly needed functionality. This architecture allows these components to be used independently and on demand only.

Following is a list of some highlighted components. A list of all official components can be found in the graphp project.

This library is built to support visualizing graph images, including them into webpages, opening up images from within CLI applications and exporting them as PNG, JPEG or SVG file formats (among many others). Because graph drawing is a complex area on its own, the actual layouting of the graph is left up to the excellent GraphViz «Graph Visualization Software» and we merely provide some convenient APIs to interface with GraphViz.

Besides graph drawing, one of the most common things to do with graphs is running algorithms to solve common graph problems. Therefore this library is being used as the basis for implementations for a number of commonly used graph algorithms:

• Search
  • Deep first (DFS)
  • Breadth first search (BFS)
  • Dijkstra
  • Moore-Bellman-Ford (MBF)
  • Counting number of hops (simple BFS)
  • Kruskal
  • Prim
  • Bruteforce algorithm
  • Minimum spanning tree heuristic (TSP MST heuristic)
  • Nearest neighbor heuristic (NN heuristic)
  • Edmonds-Karp
  • Cycle canceling
  • Successive shortest path
  • Flow algorithm

  The recommended way to install this library is through Composer. New to Composer?

  Once released, this project will follow SemVer. At the moment, this will install the latest development version:

  composer require graphp/graph:^1@dev

  See also the CHANGELOG for details about version upgrades.

  This project aims to run on any platform and thus does not require any PHP extensions and supports running on legacy PHP 5.3 through current PHP 8+. It’s highly recommended to use the latest supported PHP version for this project.

  You may also want to install some of the additional components. A list of all official components can be found in the graphp project.

  This library uses PHPUnit for its extensive test suite. To run the test suite, you first need to clone this repo and then install all dependencies through Composer:

  To run the test suite, go to the project root and run:

  This library comes with an extensive test suite and is regularly tested and used in the real world. Despite this, this library is still considered beta software and its API is subject to change. The changelog lists all relevant information for updates between releases.

  If you encounter any issues, please don’t hesitate to drop us a line, file a bug report or even best provide us with a patch / pull request and/or unit test to reproduce your problem.

  Besides directly working with the code, any additional documentation, additions to our readme or even fixing simple typos are appreciated just as well.

  Any feedback and/or contribution is welcome!

  Check out #graphp on irc.freenode.net.

  This project is released under the permissive MIT license.

  Did you know that I offer custom development services and issuing invoices for sponsorships of releases and for contributions? Contact me (@clue) for details.

  About

  GraPHP is the mathematical graph/network library written in PHP.

  Источник

  Реализация алгоритма обхода графа в глубину на PHP

  http://shujkova.ru/sites/default/files/lec7.pdf — оригинальный документ, в котором подробно описан алгоритм на C++.

  // представление графа в виде списка смежности $graph = [ 0 => [1, 2, 3], 1 => [0, 4, 8], 2 => [0, 5], 3 => [0, 6, 7], 4 => [1], 5 => [2], 6 => [3], 7 => [3, 9], 8 => [1], 9 => [7], ]; $used = []; $time_in = []; $time_out = []; $time = 0; // функция обхода графа глубину (depth-first search) function dfs($v, &$used, &$time_in, &$time_out, &$time, $graph) < print "v = $v"; $used[$v] = 1; $time_in[$v] = $time; $time++; foreach ($graph[$v] as $el)< if (empty($used[$el]))< dfs($el, $used, $time_in, $time_out, $time, $graph); >> $time_out[$v] = $time; $time++; > dfs(0, $used, $time_in, $time_out, $time, $graph); $result = []; for ($i = 0; $i < 10; $i++)< $result[$i]['time_in'] = $time_in[$i]; $result[$i]['time_out'] = $time_out[$i]; >print $result;

  Результат будет следующий:

  v = 0 v = 1 v = 4 v = 8 v = 2 v = 5 v = 3 v = 6 v = 7 v = 9

  То есть в таком порядке алгоритм обходил вершины: 0, 1, 4, 8, 2, 5, 3, 6, 7, 9.

  Массив $result содержит номер шага входа в каждую вершину и выхода из неё. Результат будет следующий:

  Array ( [0] => Array ( [time_in] => 0 [time_out] => 19 ) [1] => Array ( [time_in] => 1 [time_out] => 6 ) [2] => Array ( [time_in] => 7 [time_out] => 10 ) [3] => Array ( [time_in] => 11 [time_out] => 18 ) [4] => Array ( [time_in] => 2 [time_out] => 3 ) [5] => Array ( [time_in] => 8 [time_out] => 9 ) [6] => Array ( [time_in] => 12 [time_out] => 13 ) [7] => Array ( [time_in] => 14 [time_out] => 17 ) [8] => Array ( [time_in] => 4 [time_out] => 5 ) [9] => Array ( [time_in] => 15 [time_out] => 16 ) )

  Тэги:

  

  zanyatie7_grafy.pdf

  Источник

  Обход графа или как проехать из . в . на Php

  Здравствуйте, уважаемый разработчики. Пишу эту заметку после длительной паузы: как всегда нехватка времени или попросту неумение им распоряжаться. Но главное я опять с вами и сегодня я расскажу вам немного о графах, а точнее о поиске кратчайшего маршрута. Будем разбирать на примере поиска маршрута между станциями метро Московского метрополитена. И в конце заметки вас будет ждать маленький пример, наглядно демонстрирующий решение.

  Итак, поехали. У нас имеется неориентированный граф (в метро можно проехать как от станции-источник до станции-назначение, так и наоборот). Описывать мы его будем совсем просто и очень понятно: массив, ключи которого – это станции-источник, а значения для этого ключа – станции, в которые из источника мы можем попасть. К примеру,

  php $graph = array(  'Севастопольская' => array('Чертановская', 'Нахимовский проспект', 'Каховская') ); ?> 

  Из станции Севастопольская мы можем попасть в Чертановскую, Нахимовский проспект и в Каховскую. Единственный недостаток подобного метода описания неориентированного графа – это избыточность, но она с лихвой нивелируется простотой и наглядностью записи.

  Давайте я для нетерпеливых приведу пример кода, а потом прокомментирую некоторые моменты.

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 

  

  Строки 9-31, содержащие функцию, самые интересные и в них заключается всю изюминка алгоритма по поиску в глубину. Алгоритмы можно вкратце описать так: для вершины, которую мы еще не посетили, нужно отыскать все еще не посещенные смежные вершины и повторить поиск для них. Данная реализация взята из документации к Python, который я понемногу изучаю, и немного изменена.

  Строки 33-53 описывают граф, в котором мы и будем искать кратчайший путь (я не стал описывать все станции метро, коих больше двухсот – для наглядного примера подобного участка должно хватить).

  Строки 58-72 проверяют были ли переданы данные через форму, проверяют их корректность (значения, полученные из формы, должны содержаться в нашем графе) и выводят результат в виде ненумерованного списка с подсвеченными первой и последней вершинами.

  В довершении мы выводим форму, состоящую из двух select-ов, содержащих станции метро и кнопки “Поехали!”, после нажатии на которую и происходит поиск по графу.

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

  Поменьше багов вам в коде и удачи 🙂

  Источник

  Читайте также:  Иконка на button html