phreak--- via plug on 3 Jan 2022 07:42:28 -0800


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: [PLUG] Topics for PLUG in January


On 1/3/2022 10:29 AM, Walt Mankowski via plug wrote:
...

Step 1 in solving it is realizing you can think of the grid as a graph
where each number is a node, and the edges are each cells
neighbors. Once you've done that, there are a number of different
shortest path algorithms you can use. One of the most popular is
called Dijkstra's Algorithm, and some friends mentioned that they had
to look it up and see how to implement it. All I did was load all the
edges into networkx (another Python graph module) and then call
nx.dijkstra_path_length().

1. https://adventofcode.com/2021/day/15
A couple years ago, I experimented with GraphViz and some tools of the like that allow generating graphical representations of graphs, using a PHP library for it.
At the time, I was interested in analyzing properties of graphs and the different relationships that existed (degrees of separation, density, min/max in/out degrees, different average properties) in real world models.

The cumulative result was a site I set up which allows the public to easily model graphs: https://graph.interlinked.us/

Anyone can create a graph model by adding nodes and relationships using the web tool, and it'll use common graph algorithms to generate all the different statistics, which is mainly what I was interested in at the time - network properties. For instance, I see this for a graph where I modeled some social relationships:
Vertices (N)26
Edges (M)67
Connected Components1
% in Largest Connected Component100%
CompleteNo
# of Groups1
Density (Undirected)0.20615384615385
Density (Directed)0.10307692307692
Min Degree1
Max Degree25
Min In-Degree kin1
Max In-Degree kin12
Min Out-Degree kout1
Max Out-Degree kout13
Avg In-Degree kin2.5769230769231
Avg Out-Degree kout2.5769230769231










The graph on the home page is generated by GraphViz, but it's not a real model, just an example of what it could look like.
Not sure if this is helpful or of interest, but maybe an easy way to play around.

Albert
___________________________________________________________________________
Philadelphia Linux Users Group         --        http://www.phillylinux.org
Announcements - http://lists.phillylinux.org/mailman/listinfo/plug-announce
General Discussion  --   http://lists.phillylinux.org/mailman/listinfo/plug