graph.theory.txt

                                  ┏━━━━━━━━━━━┓
                                  ┃   GRAPH   ┃
                                  ┗━━━━━━━━━━━┛

COMPARISON ==>                    #If the focus|importance is on:
                                  #  - nodes and adjacency: node list, adjacency list, adjacency matrix
                                  #  - edges and incidency: edge list, incidence list, incidence matrix
                                  #Complexity:
                                  #  - time:
                                  #     - adjacency|incidency list > adjacency|incidency matrix > node|edge list
                                  #  - space:
                                  #     - node|edge list > adjacency|incidency list > adjacency|incidency matrix
                                  #     - adjacency matrix is better than incidency matrix if dense (size > order),
                                  #       worst otherwise
                                  #Specific cases:
                                  #  - nodes or edges have values: no adjacency|incidence matrix
                                  #  - some isolated nodes: no edge list
                                  #  - graph structure is known: use node list

SENTINEL NODE ==>                 #Like sentinel value but for graphs
                                  #I.e. node used to indicate end of walk

                                  ┌─────────────────────┐
                                  │   DATA STRUCTURES   │
                                  └─────────────────────┘

NODE LIST ==>                     #Representing a graph as a multiset of nodes, i.e. [EDGE..., NODE_VALUE]
                                  #Variants:
                                  #  - if graph structure is known (e.g. line graph or balanced binary tree),
                                  #    can be multiset of NODE_VALUE instead
                                  #     - more space|time efficient

EDGE LIST ==>                     #Representing a graph as a multiset of edges, i.e. [NODE, NODE2, EDGE_VALUE]

ADJACENCY LIST ==>                #Representing a graph as a associative array with:
                                  #  - KEY: current node
                                  #  - VAL: [ADJACENT_NODE..., NODE_VALUE]
                                  #Variants:
                                  #  - if nodes have no values, can represent them as indices instead, i.e. use a list of
                                  #    lists (neighbors)
                                  #     - more space efficient

INCIDENCE LIST ==>                #Similar to adjacency list, but using [ADJACENT_EDGE..., NODE_VALUE] as VAL

ADJACENCY MATRIX ==>              #Representing a graph as a square matrix:
                                  #  - columns represent child node, rows parent node
                                  #     - i.e. for undirected graphs, matrix is symmetric
                                  #  - cells are incremented if nodes are adjacent
                                  #     - for simple graphs: it is either 0 (no edge) or 1 (an edge)
                                  #     - for non-simple graphs:
                                  #        - it can be anything
                                  #        - loops increment by 2
                                  #"(a,b,c) adjacency matrix":
                                  #  - instead of incrementing cells, use b if there is no edge, a if there is an edge,
                                  #    c if there is a loop
                                  #  - i.e. normal adjacency matrix is a (1,0,2) adjacency matrix (for graphs with single edges)
                                  #  - "seidel [adjacency] matrix" is (-1,1,0) adjacency matrix

INCIDENCE MATRIX ==>              #Representing a graph as a square matrix:
                                  #  - columns represent node, row edge
                                  #  - cells is 1 if node and edge are incident, 0 otherwise
                                  #     - for directed graph, -1 if parent, 1 if child (or 1 for parent, 2 for child)
                                  #Comparison with adjacency matrix:
                                  #  - more space efficient if size < order, less otherwise.

                                  ┌──────────┐
                                  │   TREE   │
                                  └──────────┘

REPRESENTATIONS ==>               #Often using a node list:
                                  #  - NODE_VALUE ("sequential representation"/"ahnentafel's list"):
                                  #     - when max outdegree is static
                                  #     - waste space if tree is not complete
                                  #     - often following BFS order
                                  #     - using a random access array
                                  #  - [NODE_VALUE, ...CHILDREN_POINTER|INDEX] ("linked representation")
                                  #     - using either linked lists of random access arrays
                                  #Rarely used:
                                  #  - adjacency matrix: density is often low
                                  #  - adjacency|incidence list: often operations start at root, so associative array not needed
                                  #  - edge list, incidence list|matrix: often nodes are more important than edges