Pendant-Pendant Sums - Compound Sums

---

1. HIERARCHY - Compound Sums (Sums of Sums):

How many compound sums are there in khipus that have pendant pendant sums? Surprisingly, the answer is quite high.

Code

#=======================================================
# INITIALIZE
# Read in the Fieldmark and its associated dataframes
#=======================================================
import plotly
import plotly.express as px
import pandas as pd
import utils_khipu as ukhipu
import utils_loom as uloom
import qollqa_chuspa as qc
from fieldmark_ascher_pendant_pendant_sum import FieldmarkPendantPendantSum

aFieldmark = FieldmarkPendantPendantSum()
matching_khipus = aFieldmark.matching_khipus() 

khipu_df = aFieldmark.dataframes[0].dataframe
sum_cord_df = aFieldmark.dataframes[1].dataframe

(khipu_dict, all_khipus) = qc.fetch_khipus()

# Initialize plotly
plotly.offline.init_notebook_mode(connected = False);

Using the NetworkX graph package, we can build a mathematical graph of nodes and edges where the nodes are cords and the edges are sum relationships between sum and summands. By using a 3rd party package to build the graph we can take advantage of graph analysis tools like cycles, shortest paths, etc.

As a very preliminary analysis of compound sums, let’s simply count how many summand cords for a khipu occur in the sum cord set, indicating the set overlap.

Code

class Pendant_Sum_Edges:
    def __init__(self, khipu, sum_cord_level_name, summand_string):
        self.khipu = khipu
        self.khipu_name = khipu.kfg_name()
        self.sum_name = sum_cord_level_name
        self.summand_string = summand_string
        self.summand_cords = ukhipu.cords_from_sum_string(khipu, summand_string)
        self.summand_names = [cord.cord_name for cord in self.summand_cords]

    def edges(self):
        return [(self.sum_name, summand_name) for summand_name in self.summand_names]
    
    def node_names(self):
        return list(set(self.summand_names).union(set([self.sum_name])))
    
import networkx as nx

class Khipu_Pendant_Sum_Graph:
    def __init__(self, khipu_sum_df, khipu):
        self.khipu_sum_df = khipu_sum_df
        self.khipu = khipu
        
        sum_names = list(self.khipu_sum_df.cord_name.values)
        summand_strings = list(self.khipu_sum_df.summand_string)
        
        self.sum_edges = [Pendant_Sum_Edges(khipu, sum_name, summand_string) for (sum_name, summand_string) in zip(sum_names, summand_strings)]
        
        self.pendant_nodes = {sum_names[index]: Pendant_Sum_Edges(khipu, sum_names[index], summand_strings[index]) \
                                for index in range(len(self.khipu_sum_df))}
        self.sum_names = self.gather_all_sums()
        self.summand_names = self.gather_all_summands()
        
        self.nx_graph = self.make_graph()
        self.longest_path = nx.dag_longest_path(self.nx_graph)
        
    def gather_all_summands(self):
        summand_names = []
        for (level_name, aNode)  in self.pendant_nodes.items(): summand_names += aNode.summand_names
        return sorted(list(set(summand_names)))
        
    def gather_all_sums(self):
        return list(self.pendant_nodes.keys())
    
    def make_graph(self):
        G = nx.MultiDiGraph()
        all_nodes = list(set(self.sum_names).union(self.summand_names))
        G.add_nodes_from(all_nodes)
        
        for cord_name, pendant_edges in self.pendant_nodes.items():
            G.add_edges_from(pendant_edges.edges())

        return G

    def maximum_depth(self):
        return len(self.longest_path)
        
    def ratio_compound_sums(self):
        num_compounds = self.num_compound_sums()
        num_cords = len(set(self.sum_names).union(set(self.summand_names)))
        return float(num_compounds)/float(num_cords)

    def num_compound_sums(self):
        num_compounds = len(list(set(self.sum_names).intersection(set(self.summand_names))))
        return num_compounds        
    
    def cyclic_sums(self):
        return list(nx.simple_cycles(self.nx_graph))
    
    def has_cycles(self):
        return len(self.cyclic_sums()) > 0

    
    @staticmethod
    def build_khipu_graphs(sum_cord_df, khipu_dictionary):
        khipu_graphs = {}
        khipu_names = sorted(list(set(list(sum_cord_df.kfg_name.values))))
        for name in khipu_names:
            khipu_sum_df = sum_cord_df[sum_cord_df.kfg_name == name]
            khipu = khipu_dictionary[name]
            try:
                khipu_graphs[name] = Khipu_Pendant_Sum_Graph(khipu_sum_df, khipu)
            except nx.NetworkXUnfeasible:
                print(f"Can't process {name} - which has cycles...")

        return khipu_graphs

Code

sum_graph = Khipu_Pendant_Sum_Graph.build_khipu_graphs(sum_cord_df, khipu_dict)

# Find out which khipus have compound sums = len(list(set(self.sum_names).intersection(set(self.summand_names))))
compound_khipus = [(khipu_name, sum_graph[khipu_name].num_compound_sums()) for khipu_name in sum_graph.keys() if sum_graph[khipu_name].num_compound_sums()>0]
compound_khipus = sorted(compound_khipus,key = lambda x:x[1], reverse=True)
compound_khipu_names = [x[0] for x in compound_khipus]

pct_compound = f"{100.0*len(compound_khipus)/float(len(set(sum_cord_df.kfg_name.values))):.0f}%"
print(f"{len(compound_khipus)}({pct_compound}) khipus had compound sums, out of {len(set(sum_cord_df.kfg_name.values))} khipus with pendant pendant sum relationships")

260(67%) khipus had compound sums, out of 389 khipus with pendant pendant sum relationships

Code

# What is the maximum depth of sums (ie. the longest path in the graph)
khipu_depths = [(khipu_name, sum_graph[khipu_name].maximum_depth()) for khipu_name in sum_graph.keys()]
khipu_depths = sorted(khipu_depths,key = lambda x:x[1], reverse=True)

depth_df = pd.DataFrame(khipu_depths,columns=["name", "compound_sum_depth"])
depth_df.head(15)
depth_df.describe()

fig = px.histogram(depth_df, x="compound_sum_depth", 
                   labels={"compound_sum_depth":"Compound Sum Depth"},
                   title="Histogram of Compound Sum Depth"
                   )
fig.show()

One khipu, UR196, has 9 cycles…

260(67%) khipus had compound sums, out of 389 khipus with pendant pendant sum relationships, with the biggest compound sum depth going 9 levels, but the average being 3.4 ±1.5

2. Cycles in Compound Sums:

2.1 A Graph with a Cycle:

Are there are any other khipus that have cycles? For example, using the network X graph package let’s construct a cyclic graph - one with nodes from A,B,C,A and A,D,C,A

Code

import networkx as nx
from networkx.drawing.nx_agraph import graphviz_layout
import matplotlib.pyplot as plt
plt.rcParams['figure.figsize'] = [15, 5]

graph_edges = [ 
    ('A','B'),
    ('A','D'), 
    ('B','C'), 
    ('D','C'), 
    ('C','A'),
]

def nodes_from_edges(edge_list):
    nodes = []
    for (from_node, to_node) in edge_list: 
        nodes.append(from_node)
        nodes.append(to_node)
    return sorted(list(set(nodes)))

G = nx.MultiDiGraph()
graph_nodes = nodes_from_edges(graph_edges)
G.add_nodes_from(graph_nodes) 
G.add_edges_from(graph_edges)

_, plot = plt.subplots()
pos = graphviz_layout(G)
nx.draw_networkx(G, pos, node_size=300, font_size=12, style="solid", node_color="#FFE0E0") 

We can ask the graph package “Does this graph contain cycles?” (Answer, yes, two):

Code

nx.find_cycle(G)
list(nx.simple_cycles(G))

[['D', 'C', 'A'], ['B', 'C', 'A']]

By building a graph above, we can ask the same question for the khipus with pendant-pendant-sums:

Code

compound_cycles = [khipu_name for (khipu_name, graph) in compound_khipus if sum_graph[khipu_name].has_cycles()]
print(f"Out of {len(matching_khipus)} khipus with pendant-pendant-sums, " + 
      f"{len(compound_khipus)} have compound sums, and 1 (UR196) has cyclical compound sums.")

Out of 389 khipus with pendant-pendant-sums, 260 have compound sums, and 1 (UR196) has cyclical compound sums.

So only one khipu, (UR196) has a summing error. All the rest have no cyclical compounds. Astounding.

3.2 Sanity Check - No Cycles?

Let’s display the network graph for the simplest compound khipu sums khipu - UR244

Code

name = "UR244"
khipu_sum_df = sum_cord_df[sum_cord_df.kfg_name == name]
khipu = khipu_dict[name]
khipu_graph = Khipu_Pendant_Sum_Graph(khipu_sum_df, khipu)
plt.rcParams['figure.figsize'] = [27, 28]

G = khipu_graph.nx_graph

F = nx.Graph(G)
from networkx.drawing.nx_agraph import graphviz_layout
_, plot = plt.subplots()
pos = graphviz_layout(G)
nx.draw_networkx(G, pos, node_size=200, font_size=7, node_color="#FFE0E0") 

T = nx.dfs_tree(G)
print(f"Tree-span: {T.edges()}")
print(f"Graph-bridge: {list(nx.bridges(F))}")

Tree-span: [('p18', 'p21'), ('p45', 'p47'), ('p45', 'p49'), ('p45', 'p50'), ('p13', 'p20'), ('p13', 'p30'), ('p13', 'p31'), ('p13', 'p32'), ('p10', 'p16'), ('p10', 'p17'), ('p2', 'p14'), ('p2', 'p15'), ('p61', 'p63'), ('p61', 'p64'), ('p61', 'p65'), ('p61', 'p67'), ('p21', 'p22'), ('p21', 'p23'), ('p21', 'p24'), ('p21', 'p25'), ('p21', 'p26'), ('p21', 'p27'), ('p21', 'p28'), ('p21', 'p29')]
Graph-bridge: [('p46', 'p45'), ('p48', 'p45'), ('p62', 'p61'), ('p45', 'p47'), ('p45', 'p49'), ('p45', 'p50'), ('p66', 'p61'), ('p33', 'p13'), ('p68', 'p61'), ('p69', 'p61'), ('p13', 'p30'), ('p13', 'p31'), ('p13', 'p32'), ('p10', 'p16'), ('p10', 'p17'), ('p16', 'p2'), ('p2', 'p14'), ('p2', 'p15'), ('p61', 'p63'), ('p61', 'p64'), ('p61', 'p65'), ('p61', 'p67')]

And for the most complex compound khipu UR231

Code

name = "UR231"
khipu_sum_df = sum_cord_df[sum_cord_df.kfg_name == name]
khipu = khipu_dict[name]
khipu_graph = Khipu_Pendant_Sum_Graph(khipu_sum_df, khipu)
plt.rcParams['figure.figsize'] = [30, 30]

G = khipu_graph.nx_graph
F = nx.Graph(G)
from networkx.drawing.nx_agraph import graphviz_layout
_, plot = plt.subplots()
pos = graphviz_layout(G)
nx.draw_networkx(G, pos, node_size=400, font_size=8, node_color="#FFE0E0") 

Code

#Longest path in graph
nx.dag_longest_path(G)

['p759', 'p785', 'p476', 'p587', 'p305', 'p425']

This khipu has a compound sum ten levels deep starting with p43!

3. Compound Counts and Ratios:

Code

compound_df =  pd.DataFrame(compound_khipus, columns =['KhipuName', 'CompoundSums'])
print(f"Top 10 Compound Khipus: {compound_khipu_names[:10]}")
fig = px.bar(compound_df, x='KhipuName', y='CompoundSums', 
             labels={"KhipuName": "Khipu Name", "CompoundSums": "Number of Compound Sums", }, 
             log_y=True,
             title=f"Number of Compound Sums (log_y) by Khipu ({len(matching_khipus)})",  width=944, height=750).update_layout(showlegend=True).show()

Top 10 Compound Khipus: ['AS069', 'UR231', 'UR004', 'KH0081', 'UR197', 'UR212', 'UR022', 'UR1175', 'UR1140', 'UR010']

4. Conclusions:

Clearly more interesting work can be done here.

We know:

• Out of 427 khipus with pendant-pendant-sums, 292 have compound sums, and 1 (UR196) has cyclical compound sums.
• The biggest compound sum depth was 9 levels, but the average was 3.4 ±1.5
• Only 1 khipu, UR196, has a cyclic sum loop.