Conversation

Notices

1. Embed this notice
   alcinnz (alcinnz@floss.social)'s status on Sunday, 08-Dec-2024 06:03:49 JST alcinnz

   In describing computer algorithms I've been finding myself using graph-analysis jargon in order to keep my descriptions brief. So what do I mean by these terms?

   A "graph" is a bunch of "nodes" connected by "edges", what these nodes & edges represent depends on the concrete problem we're trying to solve.

   Edges may have numeric "weights" and/or textual "labels" to consider. It might matter which node is the incoming one vs teh outgoing one (a "weighted graph") or not.

   1/3?

   • Embed this notice
     alcinnz (alcinnz@floss.social)'s status on Sunday, 08-Dec-2024 06:13:43 JST alcinnz

     in reply to

     A key concept in analyzing graphs are "traversals" over all the edges in a graph. The datastructure you use to store-nodes to traverse determines the order. A Depth-1st-Search finds the longest unvisited "path" before backtracking. A Breadth-1st-Search traverses all siblings before their connections.

     You can process a node before traversing its edges ("pre-order"), after ("post-order"), or during ("in-order").

     These same concepts also apply to "trees", arranges their nodes in a hierarchy.

     2/3

   • Embed this notice
     alcinnz (alcinnz@floss.social)'s status on Sunday, 08-Dec-2024 06:26:42 JST alcinnz

     in reply to

     Paths refer a sequences of edges, each pair connected by a shared node, through the graph. If the start & end at the same node that's a "cycle".

     Yesterday I mentioned Tries which treats keys-to-lookup as a path through a labelled tree. Doing the same for a general graph is called a Deterministic Finite Automaton (DFA), or Non-deterministic Finite Automaton (NFA) if there's redundant edges, & is how regular expressions work!

     There's more graphconcepts, but I think those are the major ones!

     3/4

   • Embed this notice
     alcinnz (alcinnz@floss.social)'s status on Sunday, 08-Dec-2024 06:33:26 JST alcinnz

     in reply to

     Many of these concepts are more readily explained visually, so hree's Reducible: https://inv.nadeko.net/channel/UCK8XIGR5kRidIw2fWqwyHRA

     I will add that there was a time when analysing implicit graphs (graphs following rigorous-enough rules they can be lazily computed; e.g. Chess moves) was considered "Artificial Intelligence". We've heard all the same talking points about them as we're hearing now!
     Explicit graphs don't seem as magical meanwhile...

     4/4!