GRAPHS

Graphs are usually used to find the shortest path to something. Ex: AI, Roads, Game Engines...

Generalities

• Graphs can be Directed(oriented) or Not

• Path length ==> length of arcs + weight_of_each(if_present) from one node to another

• Cycle => Origine = Destination and each node has been visited

• Loop => Cycle of length 1, on itself

• Acyclic => Graph with no cycles

• Weighted => Graph that each arc has specific value. Can be anything(ex: bool, int, string...)

Oriented Graphs

• Degree of exit arity => Number of arcs that leaves the Node

• Degree of entrance arity => Number of arcs that comes in the Node

• Source => Node with Entance Arity of 0, i.e. no arc arrives to this Node (Red Node)

• Pit => Node with Exit Arity of 0, i.e. no arc leaves this Node (Blue Node)

• Weakly Connected => If sub-adjacent undirected graph is connected

• Strongly Connected => If there is a path from any Node to another

Non Oriented Graphs

• Arcs have a symmetric relation 1 goes to 5, 5 goes to 1...
• Degree of a Node => Number of arcs touching it
• Connected => Path between any distinct node. An Isolated Node is always Connected.

Connected and Undirected Graphs always have a minimum of (number_of_nodes - 1) arcs

• Not Connected(Unconnected) => Composed of many connected sub-graphs

2 ways of representing graphs programatically. In a matrix of adjacent nodes, or a dynamically linked list of successors.

Trees

• Directed, Acyclic, Weakly Connected
• 1 Source Node(Root) => Entrance Arity Degree of 0
• Multiple Pit Nodes(Leafs) => Entrance Arity Degree of 1
• There is a Path from Root to any Node

Implementation

1. Adjacency matrix => Matrix representing arcs between nodes. 1 or another non null weight is assigned where there is an arc, 0 or a null value is assigned otherwise

• Column Sums => Entrance Arity of a Node
• Row Sums => Exit Arity of a Node
• Valued Matrix => 0 if i = j. Any value if i to j is an direct Arc. Infinity or large number otherwise
• Application A matrix B. Path of length 2(a to b to c) is B^2. Path of length 3(a to b to c to d) is B^3...
• Complexity => Θ(n2)

2. Adjacency List(Successors) => List of nodes. Each node has a list of successors -- Θ(n+m)

• Complexity => Θ(n+m)

3. Utility Cases => Let's suppose: n = number_of_nodes m = number_of_arcs

• Density Directed Graph => m/n^2
• Density Undirected Graph =>  m / (n(n-1)/2)
• Should use successor list only if m << n^2. Graph with low density.