text:
Q: Select MCQ answer count based on previous question's answer Let's take a PostgreSQL DB with the following structure:

(all the relations from top to down are OneToMany)
Where a Brandlift always has exactly 2 brandlift_question each having 1 brandlift_answer (itself having many brandlift_answer_content) by brandlift_respondent
Goal:
Given a 'brand' (let's call it the "flagship brand")
and a brandlift.campaign_id,
for each brand  of this brandlift,
retrieve by respondent segment,
the count of brand.id = 'answer_content.brand_id' of the second (right) question answers,
where the previous (left) question answer of the same respondent has an answer_content.brand_id equal to the "flagship brand" id
Sample data (dump) :
https://dbfiddle.uk/?rdbms=postgres_12&fiddle=a127374b9a327204db40dc9f4e769fc1
-- -- PostgreSQL database dump -- -- Dumped from database version 12.1 -- Dumped by pg_dump version 12.3 SET statement_timeout = 0; SET lock_timeout = 0; SET idle_in_transaction_session_timeout = 0; SET client_encoding = 'UTF8'; SET standard_conforming_strings = on; SELECT pg_catalog.set_config('search_path', '', false); SET check_function_bodies = false; SET xmloption = content; SET client_min_messages = warning; SET row_security = off; SET default_tablespace = ''; SET default_table_access_method = heap; -- -- Name: brandlift; Type: TABLE; Schema: public; Owner: postgres -- CREATE TABLE public.brandlift ( campaign_id uuid NOT NULL, respondent_goal integer NOT NULL ); ALTER TABLE public.brandlift OWNER TO postgres; -- -- Name: COLUMN brandlift.campaign_id; Type: COMMENT; Schema: public; Owner: postgres -- COMMENT ON COLUMN public.brandlift.campaign_id IS '(DC2Type:uuid)'; -- -- Name: brandlift_answer; Type: TABLE; Schema: public; Owner: postgres -- CREATE TABLE public.brandlift_answer ( id integer NOT NULL, question_id uuid NOT NULL, respondent_id integer NOT NULL ); ALTER TABLE public.brandlift_answer OWNER TO postgres; -- -- Name: COLUMN brandlift_answer.question_id; Type: COMMENT; Schema: public; Owner: postgres -- COMMENT ON COLUMN public.brandlift_answer.question_id IS '(DC2Type:uuid)'; -- -- Name: brandlift_answer_content; Type: TABLE; Schema: public; Owner: postgres -- CREATE TABLE public.brandlift_answer_content ( id integer NOT NULL, answer_id integer NOT NULL, brand_id integer ); ALTER TABLE public.brandlift_answer_content OWNER TO postgres; -- -- Name: brandlift_answer_content_id_seq; Type: SEQUENCE; Schema: public; Owner: postgres -- CREATE SEQUENCE public.brandlift_answer_content_id_seq START WITH 1 INCREMENT BY 1 NO MINVALUE NO MAXVALUE CACHE 1; ALTER TABLE public.brandlift_answer_content_id_seq OWNER TO postgres; -- -- Name: brandlift_answer_id_seq; Type: SEQUENCE; Schema: public; Owner: postgres -- CREATE SEQUENCE public.brandlift_answer_id_seq START WITH 1 INCREMENT BY 1 NO MINVALUE NO MAXVALUE CACHE 1; ALTER TABLE public.brandlift_answer_id_seq OWNER TO postgres; -- -- Name: brandlift_brand; Type: TABLE; Schema: public; Owner: postgres -- CREATE TABLE public.brandlift_brand ( id integer NOT NULL, campaign_id uuid NOT NULL, name character varying(255) NOT NULL ); ALTER TABLE public.brandlift_brand OWNER TO postgres; -- -- Name: COLUMN brandlift_brand.campaign_id; Type: COMMENT; Schema: public; Owner: postgres -- COMMENT ON COLUMN public.brandlift_brand.campaign_id IS '(DC2Type:uuid)'; -- -- Name: brandlift_brand_id_seq; Type: SEQUENCE; Schema: public; Owner: postgres -- CREATE SEQUENCE public.brandlift_brand_id_seq START WITH 1 INCREMENT BY 1 NO MINVALUE NO MAXVALUE CACHE 1; ALTER TABLE public.brandlift_brand_id_seq OWNER TO postgres; -- -- Name: brandlift_question; Type: TABLE; Schema: public; Owner: postgres -- CREATE TABLE public.brandlift_question ( id uuid NOT NULL, campaign_id uuid NOT NULL, title character varying(255) NOT NULL ); ALTER TABLE public.brandlift_question OWNER TO postgres; -- -- Name: COLUMN brandlift_question.id; Type: COMMENT; Schema: public; Owner: postgres -- COMMENT ON COLUMN public.brandlift_question.id IS '(DC2Type:uuid)'; -- -- Name: COLUMN brandlift_question.campaign_id; Type: COMMENT; Schema: public; Owner: postgres -- COMMENT ON COLUMN public.brandlift_question.campaign_id IS '(DC2Type:uuid)'; -- -- Name: brandlift_respondent; Type: TABLE; Schema: public; Owner: postgres -- CREATE TABLE public.brandlift_respondent ( id integer NOT NULL, campaign_id uuid NOT NULL, segment_id integer NOT NULL, aam_uuid character varying(255) DEFAULT NULL::character varying, "timestamp" timestamp(0) without time zone NOT NULL ); ALTER TABLE public.brandlift_respondent OWNER TO postgres; -- -- Name: COLUMN brandlift_respondent.campaign_id; Type: COMMENT; Schema: public; Owner: postgres -- COMMENT ON COLUMN public.brandlift_respondent.campaign_id IS '(DC2Type:uuid)'; -- -- Name: brandlift_respondent_id_seq; Type: SEQUENCE; Schema: public; Owner: postgres -- CREATE SEQUENCE public.brandlift_respondent_id_seq START WITH 1 INCREMENT BY 1 NO MINVALUE NO MAXVALUE CACHE 1; ALTER TABLE public.brandlift_respondent_id_seq OWNER TO postgres; -- -- Name: brandlift_segment; Type: TABLE; Schema: public; Owner: postgres -- CREATE TABLE public.brandlift_segment ( id integer NOT NULL, name character varying(255) NOT NULL ); ALTER TABLE public.brandlift_segment OWNER TO postgres; -- -- Name: brandlift_segment_id_seq; Type: SEQUENCE; Schema: public; Owner: postgres -- CREATE SEQUENCE public.brandlift_segment_id_seq START WITH 1 INCREMENT BY 1 NO MINVALUE NO MAXVALUE CACHE 1; ALTER TABLE public.brandlift_segment_id_seq OWNER TO postgres; -- -- Name: campaign; Type: TABLE; Schema: public; Owner: postgres -- CREATE TABLE public.campaign ( id uuid NOT NULL, format_id integer NOT NULL, advertiser character varying(255) NOT NULL, name character varying(255) NOT NULL, date_start timestamp(0) without time zone NOT NULL, date_end timestamp(0) without time zone NOT NULL ); ALTER TABLE public.campaign OWNER TO postgres; -- -- Name: COLUMN campaign.id; Type: COMMENT; Schema: public; Owner: postgres -- COMMENT ON COLUMN public.campaign.id IS '(DC2Type:uuid)'; -- -- Name: doctrine_migration_versions; Type: TABLE; Schema: public; Owner: postgres -- CREATE TABLE public.doctrine_migration_versions ( version character varying(191) NOT NULL, executed_at timestamp(0) without time zone DEFAULT NULL::timestamp without time zone, execution_time integer ); ALTER TABLE public.doctrine_migration_versions OWNER TO postgres; -- -- Name: format; Type: TABLE; Schema: public; Owner: postgres -- CREATE TABLE public.format ( id integer NOT NULL, name character varying(255) NOT NULL ); ALTER TABLE public.format OWNER TO postgres; -- -- Name: format_id_seq; Type: SEQUENCE; Schema: public; Owner: postgres -- CREATE SEQUENCE public.format_id_seq START WITH 1 INCREMENT BY 1 NO MINVALUE NO MAXVALUE CACHE 1; ALTER TABLE public.format_id_seq OWNER TO postgres; -- -- Data for Name: brandlift; Type: TABLE DATA; Schema: public; Owner: postgres -- COPY public.brandlift (campaign_id, respondent_goal) FROM stdin; 8d8c79ce-188c-4f5e-bd72-edb854faf34c   500 \. -- -- Data for Name: brandlift_answer; Type: TABLE DATA; Schema: public; Owner: postgres -- COPY public.brandlift_answer (id, question_id, respondent_id) FROM stdin; 28 6d6596f4-9418-4f76-9234-c3c943ca56cf    18 29   c84760de-be6f-4f8e-be32-9195846307cf    18 30   6d6596f4-9418-4f76-9234-c3c943ca56cf    19 31   c84760de-be6f-4f8e-be32-9195846307cf    19 32   6d6596f4-9418-4f76-9234-c3c943ca56cf    20 33   c84760de-be6f-4f8e-be32-9195846307cf    20 34   6d6596f4-9418-4f76-9234-c3c943ca56cf    21 35   c84760de-be6f-4f8e-be32-9195846307cf    21 36   6d6596f4-9418-4f76-9234-c3c943ca56cf    22 37   c84760de-be6f-4f8e-be32-9195846307cf    22 \. -- -- Data for Name: brandlift_answer_content; Type: TABLE DATA; Schema: public; Owner: postgres -- COPY public.brandlift_answer_content (id, answer_id, brand_id) FROM stdin; 54 28  5 55    28  7 56    29  5 57    29  8 58    30  5 59    30  7 60    31  7 61    31  5 62    32  5 63    32  7 64    33  6 65    33  7 66    33  8 67    34  7 68    34  5 69    35  6 70    35  7 71    35  8 72    36  7 73    36  5 74    37  6 75    37  7 \. -- -- Data for Name: brandlift_brand; Type: TABLE DATA; Schema: public; Owner: postgres -- COPY public.brandlift_brand (id, campaign_id, name) FROM stdin; 5   8d8c79ce-188c-4f5e-bd72-edb854faf34c    Nike 6  8d8c79ce-188c-4f5e-bd72-edb854faf34c    Adidas 7    8d8c79ce-188c-4f5e-bd72-edb854faf34c    Lacoste 8   8d8c79ce-188c-4f5e-bd72-edb854faf34c    Puma \. -- -- Data for Name: brandlift_question; Type: TABLE DATA; Schema: public; Owner: postgres -- COPY public.brandlift_question (id, campaign_id, title) FROM stdin; 6d6596f4-9418-4f76-9234-c3c943ca56cf  8d8c79ce-188c-4f5e-bd72-edb854faf34c    Parmi les propositions suivantes, pour lesquelles avez-vous vu de la publicité vidéo en ligne au cours du dernier mois ? c84760de-be6f-4f8e-be32-9195846307cf   8d8c79ce-188c-4f5e-bd72-edb854faf34c    Si vous deviez prochainement choisir une marque de streetwear la ou lesquelles choisiriez-vous ? \. -- -- Data for Name: brandlift_respondent; Type: TABLE DATA; Schema: public; Owner: postgres -- COPY public.brandlift_respondent (id, campaign_id, segment_id, aam_uuid, "timestamp") FROM stdin; 10    8d8c79ce-188c-4f5e-bd72-edb854faf34c    3   912407327014    2021-02-01 18:04:43 11  8d8c79ce-188c-4f5e-bd72-edb854faf34c    3   2692416912404   2021-02-01 18:06:01 12  8d8c79ce-188c-4f5e-bd72-edb854faf34c    4   9741094120421   2021-02-01 18:06:56 13  8d8c79ce-188c-4f5e-bd72-edb854faf34c    4   8973093247093   2021-02-01 18:07:59 14  8d8c79ce-188c-4f5e-bd72-edb854faf34c    4   2147124472178421    2021-02-01 18:08:34 15  8d8c79ce-188c-4f5e-bd72-edb854faf34c    4   2147124472178421    2021-02-01 18:09:20 16  8d8c79ce-188c-4f5e-bd72-edb854faf34c    4   23253532532352  2021-02-01 18:09:53 17  8d8c79ce-188c-4f5e-bd72-edb854faf34c    3   357325732577352 2021-02-01 18:20:01 18  8d8c79ce-188c-4f5e-bd72-edb854faf34c    3   357325732577352 2021-02-01 18:21:12 19  8d8c79ce-188c-4f5e-bd72-edb854faf34c    3   4354646464223   2021-02-01 18:22:14 20  8d8c79ce-188c-4f5e-bd72-edb854faf34c    4   6855985895808   2021-02-01 18:25:41 21  8d8c79ce-188c-4f5e-bd72-edb854faf34c    4   6855985895808   2021-02-01 18:26:03 22  8d8c79ce-188c-4f5e-bd72-edb854faf34c    4   6855985895808   2021-02-01 18:26:33 \. -- -- Data for Name: brandlift_segment; Type: TABLE DATA; Schema: public; Owner: postgres -- COPY public.brandlift_segment (id, name) FROM stdin; 3  expo 4  no expo \. -- -- Data for Name: campaign; Type: TABLE DATA; Schema: public; Owner: postgres -- COPY public.campaign (id, format_id, advertiser, name, date_start, date_end) FROM stdin; 8d8c79ce-188c-4f5e-bd72-edb854faf34c    2   Nike    Air Max 270 2021-01-25 00:00:00 2021-02-28 00:00:00 \. -- -- Data for Name: doctrine_migration_versions; Type: TABLE DATA; Schema: public; Owner: postgres -- COPY public.doctrine_migration_versions (version, executed_at, execution_time) FROM stdin; DoctrineMigrations\\Version20210131122327  2021-01-31 13:23:34 199 \. -- -- Data for Name: format; Type: TABLE DATA; Schema: public; Owner: postgres -- COPY public.format (id, name) FROM stdin; 2    Brandlift \. -- -- Name: brandlift_answer_content_id_seq; Type: SEQUENCE SET; Schema: public; Owner: postgres -- SELECT pg_catalog.setval('public.brandlift_answer_content_id_seq', 75, true); -- -- Name: brandlift_answer_id_seq; Type: SEQUENCE SET; Schema: public; Owner: postgres -- SELECT pg_catalog.setval('public.brandlift_answer_id_seq', 37, true); -- -- Name: brandlift_brand_id_seq; Type: SEQUENCE SET; Schema: public; Owner: postgres -- SELECT pg_catalog.setval('public.brandlift_brand_id_seq', 8, true); -- -- Name: brandlift_respondent_id_seq; Type: SEQUENCE SET; Schema: public; Owner: postgres -- SELECT pg_catalog.setval('public.brandlift_respondent_id_seq', 22, true); -- -- Name: brandlift_segment_id_seq; Type: SEQUENCE SET; Schema: public; Owner: postgres -- SELECT pg_catalog.setval('public.brandlift_segment_id_seq', 4, true); -- -- Name: format_id_seq; Type: SEQUENCE SET; Schema: public; Owner: postgres -- SELECT pg_catalog.setval('public.format_id_seq', 2, true); -- -- Name: brandlift_answer_content brandlift_answer_content_pkey; Type: CONSTRAINT; Schema: public; Owner: postgres -- ALTER TABLE ONLY public.brandlift_answer_content ADD CONSTRAINT brandlift_answer_content_pkey PRIMARY KEY (id); -- -- Name: brandlift_answer brandlift_answer_pkey; Type: CONSTRAINT; Schema: public; Owner: postgres -- ALTER TABLE ONLY public.brandlift_answer ADD CONSTRAINT brandlift_answer_pkey PRIMARY KEY (id); -- -- Name: brandlift_brand brandlift_brand_pkey; Type: CONSTRAINT; Schema: public; Owner: postgres -- ALTER TABLE ONLY public.brandlift_brand ADD CONSTRAINT brandlift_brand_pkey PRIMARY KEY (id); -- -- Name: brandlift brandlift_pkey; Type: CONSTRAINT; Schema: public; Owner: postgres -- ALTER TABLE ONLY public.brandlift ADD CONSTRAINT brandlift_pkey PRIMARY KEY (campaign_id); -- -- Name: brandlift_question brandlift_question_pkey; Type: CONSTRAINT; Schema: public; Owner: postgres -- ALTER TABLE ONLY public.brandlift_question ADD CONSTRAINT brandlift_question_pkey PRIMARY KEY (id); -- -- Name: brandlift_respondent brandlift_respondent_pkey; Type: CONSTRAINT; Schema: public; Owner: postgres -- ALTER TABLE ONLY public.brandlift_respondent ADD CONSTRAINT brandlift_respondent_pkey PRIMARY KEY (id); -- -- Name: brandlift_segment brandlift_segment_pkey; Type: CONSTRAINT; Schema: public; Owner: postgres -- ALTER TABLE ONLY public.brandlift_segment ADD CONSTRAINT brandlift_segment_pkey PRIMARY KEY (id); -- -- Name: campaign campaign_pkey; Type: CONSTRAINT; Schema: public; Owner: postgres -- ALTER TABLE ONLY public.campaign ADD CONSTRAINT campaign_pkey PRIMARY KEY (id); -- -- Name: doctrine_migration_versions doctrine_migration_versions_pkey; Type: CONSTRAINT; Schema: public; Owner: postgres -- ALTER TABLE ONLY public.doctrine_migration_versions ADD CONSTRAINT doctrine_migration_versions_pkey PRIMARY KEY (version); -- -- Name: format format_pkey; Type: CONSTRAINT; Schema: public; Owner: postgres -- ALTER TABLE ONLY public.format ADD CONSTRAINT format_pkey PRIMARY KEY (id); -- -- Name: answer_content_unique; Type: INDEX; Schema: public; Owner: postgres -- CREATE UNIQUE INDEX answer_content_unique ON public.brandlift_answer_content USING btree (answer_id, brand_id); -- -- Name: answer_unique; Type: INDEX; Schema: public; Owner: postgres -- CREATE UNIQUE INDEX answer_unique ON public.brandlift_answer USING btree (question_id, respondent_id); -- -- Name: idx_1f1512ddd629f605; Type: INDEX; Schema: public; Owner: postgres -- CREATE INDEX idx_1f1512ddd629f605 ON public.campaign USING btree (format_id); -- -- Name: idx_3be90c3a44f5d008; Type: INDEX; Schema: public; Owner: postgres -- CREATE INDEX idx_3be90c3a44f5d008 ON public.brandlift_answer_content USING btree (brand_id); -- -- Name: idx_3be90c3aaa334807; Type: INDEX; Schema: public; Owner: postgres -- CREATE INDEX idx_3be90c3aaa334807 ON public.brandlift_answer_content USING btree (answer_id); -- -- Name: idx_80d627bdf639f774; Type: INDEX; Schema: public; Owner: postgres -- CREATE INDEX idx_80d627bdf639f774 ON public.brandlift_question USING btree (campaign_id); -- -- Name: idx_d5009950db296aad; Type: INDEX; Schema: public; Owner: postgres -- CREATE INDEX idx_d5009950db296aad ON public.brandlift_respondent USING btree (segment_id); -- -- Name: idx_d5009950f639f774; Type: INDEX; Schema: public; Owner: postgres -- CREATE INDEX idx_d5009950f639f774 ON public.brandlift_respondent USING btree (campaign_id); -- -- Name: idx_d671e368f639f774; Type: INDEX; Schema: public; Owner: postgres -- CREATE INDEX idx_d671e368f639f774 ON public.brandlift_brand USING btree (campaign_id); -- -- Name: idx_fcce59931e27f6bf; Type: INDEX; Schema: public; Owner: postgres -- CREATE INDEX idx_fcce59931e27f6bf ON public.brandlift_answer USING btree (question_id); -- -- Name: idx_fcce5993ce80cd19; Type: INDEX; Schema: public; Owner: postgres -- CREATE INDEX idx_fcce5993ce80cd19 ON public.brandlift_answer USING btree (respondent_id); -- -- Name: campaign fk_1f1512ddd629f605; Type: FK CONSTRAINT; Schema: public; Owner: postgres -- ALTER TABLE ONLY public.campaign ADD CONSTRAINT fk_1f1512ddd629f605 FOREIGN KEY (format_id) REFERENCES public.format(id); -- -- Name: brandlift_answer_content fk_3be90c3a44f5d008; Type: FK CONSTRAINT; Schema: public; Owner: postgres -- ALTER TABLE ONLY public.brandlift_answer_content ADD CONSTRAINT fk_3be90c3a44f5d008 FOREIGN KEY (brand_id) REFERENCES public.brandlift_brand(id); -- -- Name: brandlift_answer_content fk_3be90c3aaa334807; Type: FK CONSTRAINT; Schema: public; Owner: postgres -- ALTER TABLE ONLY public.brandlift_answer_content ADD CONSTRAINT fk_3be90c3aaa334807 FOREIGN KEY (answer_id) REFERENCES public.brandlift_answer(id); -- -- Name: brandlift fk_5b5d1287f639f774; Type: FK CONSTRAINT; Schema: public; Owner: postgres -- ALTER TABLE ONLY public.brandlift ADD CONSTRAINT fk_5b5d1287f639f774 FOREIGN KEY (campaign_id) REFERENCES public.campaign(id); -- -- Name: brandlift_question fk_80d627bdf639f774; Type: FK CONSTRAINT; Schema: public; Owner: postgres -- ALTER TABLE ONLY public.brandlift_question ADD CONSTRAINT fk_80d627bdf639f774 FOREIGN KEY (campaign_id) REFERENCES public.brandlift(campaign_id); -- -- Name: brandlift_respondent fk_d5009950db296aad; Type: FK CONSTRAINT; Schema: public; Owner: postgres -- ALTER TABLE ONLY public.brandlift_respondent ADD CONSTRAINT fk_d5009950db296aad FOREIGN KEY (segment_id) REFERENCES public.brandlift_segment(id); -- -- Name: brandlift_respondent fk_d5009950f639f774; Type: FK CONSTRAINT; Schema: public; Owner: postgres -- ALTER TABLE ONLY public.brandlift_respondent ADD CONSTRAINT fk_d5009950f639f774 FOREIGN KEY (campaign_id) REFERENCES public.brandlift(campaign_id); -- -- Name: brandlift_brand fk_d671e368f639f774; Type: FK CONSTRAINT; Schema: public; Owner: postgres -- ALTER TABLE ONLY public.brandlift_brand ADD CONSTRAINT fk_d671e368f639f774 FOREIGN KEY (campaign_id) REFERENCES public.brandlift(campaign_id); -- -- Name: brandlift_answer fk_fcce59931e27f6bf; Type: FK CONSTRAINT; Schema: public; Owner: postgres -- ALTER TABLE ONLY public.brandlift_answer ADD CONSTRAINT fk_fcce59931e27f6bf FOREIGN KEY (question_id) REFERENCES public.brandlift_question(id); -- -- Name: brandlift_answer fk_fcce5993ce80cd19; Type: FK CONSTRAINT; Schema: public; Owner: postgres -- ALTER TABLE ONLY public.brandlift_answer ADD CONSTRAINT fk_fcce5993ce80cd19 FOREIGN KEY (respondent_id) REFERENCES public.brandlift_respondent(id); -- -- PostgreSQL database dump complete --

Desired output with :
campaign_id => 8d8c79ce-188c-4f5e-bd72-edb854faf34c
"flagship brand" => Nike (id=5)

brand_name
segment_name
count

Adidas
expo
0

Adidas
no expo
3

Lacoste
expo
1

Lacoste
no expo
3

Nike
expo
2

Nike
no expo
0

Puma
expo
1

Puma
no expo
2

UPDATE :
Ended up adding an 'ordinal' column to brandlift_question table, so that later if I ever have to add more questions in a Brandlift, I can compare answers based on other questions indexes and not just between first & second

SELECT
    bb.name AS brand_name,
    s.name AS segment_name,
    COUNT(q2ac.brand_id)
FROM
    brandlift b
    LEFT JOIN brandlift_brand bb ON b.campaign_id = bb.campaign_id
    LEFT JOIN brandlift_respondent r ON b.campaign_id = r.campaign_id
    LEFT JOIN brandlift_segment s ON s.id = r.segment_id

    LEFT JOIN brandlift_question q1 ON b.campaign_id = q1.campaign_id AND q1.ordinal = 1
    LEFT JOIN brandlift_answer q1a ON r.id = q1a.respondent_id AND q1.id = q1a.question_id
    INNER JOIN brandlift_answer_content q1ac ON  q1a.id = q1ac.answer_id AND q1ac.brand_id = 5 -- the "flagship brand" id

    LEFT JOIN brandlift_question q2 ON q1.campaign_id = q2.campaign_id AND q2.ordinal = 2
    INNER JOIN brandlift_answer q2a ON q1a.respondent_id = q2a.respondent_id AND q2.id = q2a.question_id
    LEFT JOIN brandlift_answer_content q2ac ON q2a.id = q2ac.answer_id AND bb.id = q2ac.brand_id
WHERE
    b.campaign_id = '8d8c79ce-188c-4f5e-bd72-edb854faf34c'
GROUP BY
    bb.name,
    s.name

But there is still a point, if there is no respondent on a segment, the result output of this query will not contain rows with that segment values filled with 0. Need them too if possible
I'm keen for any advice

A: If you don't want to do mod, then you need to select questionID instead.
and I used cross join to get some other segment where not in respond. and in select statement, you case statement to count segmentName to 0.
SELECT
    bb.name,
    s.name,
    CASE WHEN s.id IN(
        SELECT
            r.segment_id FROM brandlift_respondent r) THEN
        COUNT(q2ac.brand_id)
    ELSE
        0
    END AS CountNumber
FROM
    brandlift b
    LEFT JOIN brandlift_brand bb ON b.campaign_id = bb.campaign_id
    LEFT JOIN brandlift_respondent r ON b.campaign_id = r.campaign_id

    CROSS JOIN brandlift_segment s

    LEFT JOIN brandlift_question q1 ON b.campaign_id = q1.campaign_id AND q1.ordinal = 1
    LEFT JOIN brandlift_answer q1a ON r.id = q1a.respondent_id AND q1.id = q1a.question_id
    INNER JOIN brandlift_answer_content q1ac ON q1a.id = q1ac.answer_id AND q1ac.brand_id = 1 -- the "flagship brand" id

    LEFT JOIN brandlift_question q2 ON q1.campaign_id = q2.campaign_id AND q2.ordinal = 2
    LEFT JOIN brandlift_answer q2a ON q1a.respondent_id = q2a.respondent_id AND q2.id = q2a.question_id
    LEFT JOIN brandlift_answer_content q2ac ON q2a.id = q2ac.answer_id AND bb.id = q2ac.brand_id
WHERE
    b.campaign_id = :campaign_id -- parameter
    AND R.segment_id = s.id OR s.id NOT IN(SELECT r.segment_id FROM brandlift_respondent r)
GROUP BY
    bb.name,
    s.name,
    s.id

the result shows like that

redpajama_set_name: RedPajamaStackExchange


text:
Home Latest News Playing With Prisoners' Lives
Playing With Prisoners' Lives
by Newsweek Pakistan December 14, 2020
File Photo. Asif Hassan—AFP
New report warns that Pakistan's failure to reduce overcrowding in prisons has left tens of thousands at risk of COVID-19
Pakistan's failure to reduce overcrowding in its prisons—even as a second wave of COVID-19 shows few signs of abating—is endangering the lives of tens of thousands, according to a new report compiled by Amnesty International and Justice Project Pakistan.
Prisoners of the Pandemic—The Right to Health and COVID-19 in Pakistan's Detention Facilities was released on Monday and examines the country's response between March and July to the challenges posed by the pandemic. Noting that by August 2020, at least 2,313 prisoners had tested positive for COVID-19, it slams the authorities for failing to reduce the country's prison population despite promising to do so to curb the spread of the virus.
"With infections and fatalities rising daily, overcrowding in Pakistan's prisons is a ticking time bomb. The authorities must learn the lessons of the first wave and urgently ensure a significant reduction in the country's prison population," said Rimmel Mohydin, South Asia Campaigner at Amnesty International. "It's no secret that Pakistan's prisons were dangerously overcrowded even before COVID-19 struck. The authorities recognized that special protective measures were needed for prisons—above all, a big reduction in prisoner numbers. A series of failures in the early stages of the pandemic meant that this goal was spectacularly missed, leaving people in detention dangerously exposed as the country approaches a second spike," she added.
This report, comprising research carried out between Aug. 1, 2020 and Sept. 20, 2020, involved on-site investigations in six prisons and includes 22 interviews with prison authorities, medical personnel, prisoners and newly-released prisoners. It noted that the Islamabad High Court had, in March, ordered that no unnecessary arrests should be made to curb the spread of COVID-19. However, says the report, there was a continued intake of prisoners with minimal precautions to prevent transmissions within prisons and no official steps were taken to limit prisoner intake or reduce the pace of arrests for petty crimes.
"Indeed, during the outbreak, the police arrested and detained several individuals simply for exercising their rights to freedom of expression and peaceful assembly," reads the report, adding that this included health workers protesting lack of resources and personal protection equipment; students protesting a lack of internet access to attend virtual classes; and a transgender rights activist detained in a prison with a known COVID-19 outbreak.
According to the Federal Ombudsman, the national overcrowding rate in Pakistan's prisons is 134 percent, with significantly higher percentages depending on the prison. Amnesty and JPP say the overuse of arrests and detention, including for minor offenses, as well as a massive backlog of cases in Pakistan's courts and long delays between hearings contribute to the prison populations.
Judicial interventions
Noting that in March, when COVID-19 first started spreading through Pakistan, media reports had suggested at least 20,000 prisoners across Punjab were set for release, the report said Islamabad High Court had also issued directives to release pre-trial prisoners detained for non-prohibitory offenses, and those whose bail was refused previously. The Sindh High Court also authorized the release of 519 prisoners on bail.
However, says the report, the Supreme Court intervened on March 30 and suspended all bail orders specifically granted on account of COVID-19. This, it notes, halted the campaign to reduce prison populations and led to the re-arrest of prisoners who had already been released. It says that an apex court decision for prison authorities to prepare lists of at-risk prisoners eligible for release was ignored by prison authorities, stalling all attempts to reduce prison populations through early releases.
"A justice system that caused the problem of overcrowding in the first place also stood in the way of resolving it. The response in the early stages of the pandemic ensured that prisons remained a teeming hotbed for COVID-19 transmission. The Pakistani authorities must not commit the same mistakes as a second wave looms over the country," said Mohydin.
"In April this year, the Supreme Court of Pakistan outlined specific categories of prisoners who would be eligible for bail on account of their age and sentences, but those prisoners were never released. The prime minister, too, had reaffirmed the release of women prisoners nearly 3 months ago and yet over a thousand women continue to languish in jails, many with their children," said Sarah Belal, Justice Project Pakistan's executive director, warning of a looming health disaster.
Overcrowding
According to JPP and Amnesty, some prisons house between six and 15 prisoners in jail cells built to hold a maximum of three individuals. Some prisoners interviewed for the report described having to sleep in shifts because there was not enough floor space for all of them to lie down at the same time, it said.
The report also slams the lack of visitation during the outbreak, noting that for a period of four months between March and July no one was allowed to meet any prisoners. "On July 7, after almost four months, families were allowed to meet prisoners once every 15 days. Lawyers, however, were still not permitted to visit their clients," it said, noting this hampered effective communication.
The lack of a clean and consistent supply of water was also found to be an alarming concern for prisoners, with many reporting that they did not have adequate water to drink or wash with. "The appalling state of Pakistan's prisons is a longstanding problem that has been ignored by all levels of government for years. The COVID-19 outbreak has exposed just how precarious the conditions in prisons are, and the threats these pose to the lives and health of prisoners, prison staff and the community at large," said Mohydin. "The Pakistani authorities must tackle these systemic issues, ease the strain on the prison infrastructure and address the multiple human rights violations that take place behind prison walls every day," she added.
Amnesty and JPP have urged Pakistani authorities to urgently submit lists of prisoners at risk who can be eligible for early, temporary or conditional release; to immediately and unconditionally release all prisoners detained solely for exercising their human rights; and to follow through on any orders to implement early releases of women and children in prisons.
Imran Khan Slams Political Influence in Punjab Police
Naeem Bokhari Removed as PTV Chairman
Pakistan Records 2,432 COVID-19 Cases in 24 Hours
Pakistan Has Yet to Finalize Any COVID-19 Vaccine...
Copyright © 2020 AG Publications (Private) Limited.

redpajama_set_name: RedPajamaCommonCrawl


text:
\section{Introduction}
\label{introduction}

\emph{Routing of a single connection in an optical network} is one of
the most important tasks of operating an optical network, and one of
many research problems of the optical network design, planning, and
operation.  In the wavelength-division multiplexed (WDM) network, the
problem is called the routing and wavelength assignment (RWA) problem,
and in the elastic optical network it is called the routing and
spectrum assignment (RSA) problem, or the routing, modulation, and
spectrum assignment (RMSA), if we take into account the constraints of
the signal modulation.  Related problems exist in other optical
networks: in the optical transport network (OTN) for the virtual and
contiguous concatenation, or in the space division multiplexing (SDM)
network for the fiber-core assignment.

In EONs, the optical spectrum (the erbium window) is divided into fine
\emph{frequency slot units} (of, e.g., 6.25 GHz width), or just
\emph{units}, as opposed to coarse fixed-grid channels (of, e.g., 25
GHz width) of WDM networks.  In EONs, \emph{contiguous units} are
concatenated to form a \emph{slot}.  Slots are tailored for a specific
demand, unlike WDM channels, thus making EONs more spectrum efficient
than WDM networks.

Future optical networks should deal with dynamic traffic, where
connections are frequently established, and are of short duration as
opposed to the quasi-static WDM connections that are characteristic of
traditional networks.  Furthermore, given the increasing deployment of
optical networks, the network densification, the softwarization of the
network control, the ever-increasing need for bandwidth and agility,
further increased by the content-oriented services, network and
service orchestration, and the next generation wireless network
requirements, a shortest optical path should be found \emph{fast}.
The proposed algorithm enables real-time control of future optical
networks.

The RWA, RSA and RMSA problems come in many versions, most notably
static (a.k.a.~offline) and dynamic (a.k.a.~online).  The objective of
the static version is to route a number of demands along shortest
paths in an unloaded network using the least spectrum.  The objective
of the dynamic version is to route a single demand along a shortest
path in a loaded network using the available spectrum.  The static
version is nondeterministic polynomial time complete (NP-complete),
but the dynamic version is not, because it can be solved tractably
(though inefficiently) by finding a shortest path in a number of
filtered graphs.

Our novel contribution is the algorithm which efficiently solves the
dynamic RWA, RSA and RMSA problems.  The algorithm is the
generalization of the Dijkstra shortest-path algorithm.  With
simulations, we demonstrate its efficiency in comparison to three
other optimal algorithms frequently used in research.  The
implementation of the algorithm using the Boost Graph Library is
available at \cite{gdwebsite}.  We published the first implementation
of the algorithm in 2013 \cite{sdiwebsite}.

The shortest path Dijkstra algorithm is a premier graph algorithm,
amenable to various adaptations due to its simple and clever design.
Dijkstra is optimal (i.e., it finds a shortest path) and efficient (no
better algorithm has been proposed yet after half a century since it
was proposed), and follows the \emph{label-setting} paradigm, as
opposed to the label-correcting paradigm \cite{networkflows}.  At
first look, our generalization seems to discard the label-setting
paradigm in favor of the label-correcting paradigm, because we allow
for revisiting vertices, which Dijkstra does not do, and which is a
hallmark of the label-correcting algorithms.  But this is not so; the
proposed algorithm is still a label-setting algorithm, only with a
generalized notion of a label and reformulated edge relaxation.

The paper is organized as follows.  In Section \ref{related} we review
related works, in Section \ref{statement} we define the research
problem, in Section \ref{algorithm} we describe the proposed
algorithm, and in Section \ref{simulations} we report on the
simulation results.  Finally, Section \ref{conclusion} concludes the
paper.

\section{Related works}
\label{related}

We extended our conference paper \cite{10.1109/ONDM.2016.7494087} in a
number of significant ways.  First, we refined the algorithm
description by defining better the relation between labels.  Second,
we took into account the signal modulation constraints.  Third, since
the proposed algorithm is not heuristic, we evaluated its performance
in comparison with three other optimal algorithms, and not with
heuristic algorithms as before.

The proposed algorithm was inspired by the \emph{generic programming}
paradigm which is based on mathematical abstraction: generic data
structures and algorithms can operate on any algebraic structure,
provided it has the required properties, such as operations or
ordering relations \cite{generic}.  We call the proposed algorithm the
\emph{generic Dijkstra} algorithm as a tribute to generic programming.

The dynamic RWA, RSA, and RMSA problems are defined in the literature
in two different ways.  First, they can be defined to optimize the
overall network performance expressed in, e.g., the bandwidth blocking
probability for a set of demands, bearing similarity to the static
version, thus this problem is considered hard \cite{Zang00areview}.
Second, these problems can be defined to optimize a single connection
(i.e., to find a shortest path or a path of minimal cost), since in
an operational network requests usually arrive sequentially
\cite{10.1016/j.osn.2014.02.003}.  We concentrate on the second
definition of the dynamic RWA, RSA, and RMSA problems, i.e., we
optimize a single connection.

The static RWA was proven to be NP-complete nearly three decades ago,
and then the static RSA was proven NP-complete too
\cite{10.1109/INFCOM.2011.5934939}.  The status of the
single-connection dynamic RWA, RSA, and RMSA problems was unclear: no
proof of NP-completeness was proposed, but heuristic algorithms and
linear-programming formulations were proposed and reviewed
\cite{10.1109/COMST.2015.2431731, 10.1016/j.osn.2016.08.003,
10.1007/s11107-017-0700-5}.

The dynamic RWA, RSA, and RMSA problems can be solved inefficiently by
finding shortest paths in filtered graphs.  A filtered graph retains
only those edges which can support a given slot.  For a given demand
and available modulations, we compute set $S$ of slots for which we
filter the input graph, and search for a shortest path.  From among
the shortest paths found, the shortest one is selected.  This
algorithm, termed \emph{filtered-graphs algorithm}, is of
$O(|S| \times |V| \log |V|)$ complexity, where $V$ is the set of
vertices of a (sparse, we assume) graph.  This computational
complexity is the upper bound, and a proof that these problems are
tractable.

We argue that the filtered-graphs algorithm is inefficient and we show
through simulations on realistic networks that the proposed algorithm
is considerably faster than the filtered-graphs algorithm.  To the
best of our knowledge, we are the first to propose an optimal and
efficient algorithm for the dynamic routing problem, as simulated in
realistic optical networks.

In \cite{10.1007/s11107-012-0378-7} the authors report that by
computing in advance the set of slots that can be assigned to a
demand, the complexity added by the contiguity constraint is removed.
We, in contrast, show that the time performance of the filtered-graphs
algorithm is worse than the time performance of the proposed
algorithm, because we process not a slot, but contiguous units, which
can include many slots.

In \cite{10.1364/JOCN.6.001115} the authors proposed an algorithm for
solving the dynamic RSA problem with the brute-force search strategy
of enumerating the paths capable of supporting a demand.  The
algorithm does not use the edge relaxation to limit the search space.
The algorithm stores the complete paths in a priority queue, and does
not use the dynamic-programming principle of reusing intermediate
results, like Dijkstra does with node labels.  For these reasons, we
refer to this algorithm as the \emph{brute-force algorithm}.

In \cite{10.1364/JOCN.4.000603} the authors proposed an algorithm,
which checks whether the consecutive paths provided by the Yen
$K$-shortest path (KSP) algorithm can support a demand.  When $K$ is
limited to some value (e.g., $K = 10$), we call this algorithm the
\emph{limited Yen KSP}, and if there is no limit on $K$, we call the
algorithm the \emph{unlimited Yen KSP}.  The limited Yen KSP algorithm
is heuristic, while the unlimited Yen KSP is optimal.  If there is a
path capable of supporting the demand, the unlimited Yen KSP algorithm
will eventually find this path, but its $K$ could be very large,
possibly a million, even for small graphs.

In \cite{10.1109/TNET.2011.2138717}, the authors proposed a dynamic
RWA algorithm, which is based on the algorithm in
\cite{10.1016/j.comnet.2008.06.016}, and in turn based on the
Dijkstra-based algorithm proposed in \cite{gutierrez}.  In
\cite{gutierrez}, the authors introduced the transitive path
domination relation to solve the max-min problem, where the network
resources are continuous.  This relation was adapted in
\cite{10.1016/j.comnet.2008.06.016} for discrete network resources and
then used \cite{10.1109/TNET.2011.2138717} to model the availability
of wavelengths.  That adaptation, however, leads to a less efficient
search, since it was defined with the $\ge$ relation for the
wavelength availability vector, which models the $\supseteq$ set
relation.  We, in contrast, define the relation of the incomparability
of solution labels using the $\supsetneq$ relation for a set of
contiguous units, and show that this relation is intransitive.

The authors in \cite{10.1109/TNET.2011.2138717}, and
\cite{10.1016/j.comnet.2008.06.016} report on the complexity of their
algorithms, which may be exponential.  This complexity is the result
of the way the path cost vectors are defined, compared, and produced
when an edge is traversed.  In \cite{10.1109/TNET.2011.2138717} the
path cost vector stores the availability information of all
wavelengths of a path.  The edge traversal produces paths which are
non-dominant, but which can have overlapping wavelengths, thus
possibly leading to the explosion of the search space (the set of
non-dominant paths).  We, in contrast, store in a solution label a
single sequence of contiguous units (represented by two integer
numbers), which is faster to process.  During the edge relaxation, we
produce a set of incomparable labels (without overlapping units),
which limits the search space (the set of incomparable labels).

The algorithm in \cite{10.1109/TNET.2011.2138717} finds an optimal
solution in two phases: in the first phase, the complete set of
non-dominated solutions is obtained, and in the second phase an
optimal solution is selected.  In contrast, our algorithm can make
optimization decisions for intermediate solutions by sorting the
priority queue elements, taking into account, e.g., the spectrum
allocation policy.  Thus, our algorithm has a single phase, and
produces a single result, which is more efficient.

In \cite{10.1364/JOCN.4.000603}, the authors also proposed a heuristic
algorithm, termed a modified Dijkstra algorithm, which is the Dijkstra
algorithm with the constrained edge relaxation, where a candidate path
is rejected if it cannot support a demand.

In \cite{10.1109/JLT.2014.2315041}, the authors proposed a heuristic
algorithm, which is a constrained Yen $K$-shortest path algorithm that
drops the path deviations incapable of supporting a demand.  The Yen
algorithm delegates the shortest path search to the Dijkstra
algorithm.

The limited Yen, the modified Dijkstra, and the constrained Yen
algorithms, which find a candidate path with the Dijkstra algorithm,
fail to find a shortest path meeting the spectrum and modulation
constraints, when there is a shorter path unable to meet the spectrum
and modulation constraints, because that shorter path diverts the
algorithms into a dead end.

\section{Problem statement}
\label{statement}

\noindent{}Given:

\begin{itemize}

\item directed multigraph $G = (V, E)$, where $V = \{v_i\}$ is a set
  of vertices, and $E = \{e_i\}$ is a set of edges,

\item cost function $\cost(e_i)$, which gives non-negative cost
  (length) of edge $e_i$,

\item available units function $\AU(e_i)$, which gives the set of
  available units of edge $e_i$, which do not have to be contiguous,

\item $s$ and $t$ are the source and target vertices of the demand,

\item a \emph{decision function of monotonically increasing
  requirements}, which returns true if a candidate solution (the given
  contiguous units at the given cost) can support the demand,
  otherwise false,

\item the set of all units $\Omega$ on every edge.

\end{itemize}

\noindent{}Find:

\begin{itemize}

\item a shortest path (a sequence of edges),

\item continuous and contiguous units.

\end{itemize}

We refer to a set of contiguous units as a CU.  We denote a CU with
the units starting at $a$ and ending at $b$ inclusive as $\CUO{a}{b}$.
For instance, $\CUO{0}{2}$ denotes units 0, 1 and 2.  A set of units
can be treated as a set of CUs.  For instance, $\{0, 1, 3, 4, 5\}$ and
$\{\CUO{0}{1}, \CUO{3}{5}\}$ are the same.

Two CUs are \emph{incomparable}, when one is not included in the
other.  For instance, $\CUO{0}{2}$ is incomparable with $\CUO{2}{3}$.
We denote the incomparability of CUs with the $\parallel$ relation.
For instance, $\CUO{0}{2} \parallel \CUO{2}{3}$.

We intentionally stated the problem generically by introducing the
decision function to consider the RWA, RSA, and RMSA problems at once.
The decision function is responsible for accepting or rejecting a
candidate solution, and gives a user leeway to define what an
acceptable candidate solution is.  For RWA, the function should check
whether a CU has at least one unit (wavelength), for RSA, whether a CU
has at least the number of contiguous units required by the demand,
and for RMSA, whether a CU has at least the number of contiguous units
required by the demand at a given cost (distance).  The decision
function could also check other parameters such as the signal quality.

The requirements of the decision function should be monotonically
increasing as the cost increases, i.e., a candidate solution rejected
at a given cost could not be accepted at a higher cost.  It is a valid
assumption, since as the distance grows, the number of required
contiguous units can only grow.  This assumption allows us to reject a
candidate solution due to its insufficient number of the available
contiguous units, because as distance grows, that rejected solution
would fail to provide the same or greater number of required
contiguous units anyway.

The demand bitrate is not a given of the stated problem, because that
would narrow the problem statement.  If need be, the demand bitrate
should be considered by the decision function.  In Section
\ref{simulations} we use the proposed algorithm to solve the RMSA
problem, and there, in Algorithm \ref{a:decide}, we define a decision
function which takes into account the demand bitrate.

\section{Proposed algorithm}
\label{algorithm}

We generalize and constrain the shortest path Dijkstra algorithm to
find a shortest path in EONs for a given demand.  The generalization
is novel, and the constriction is trivial.  The generalization
resolves the unit continuity and contiguity constraints, while the
constriction takes into account the signal modulation constraints.

In label-setting algorithms, a label is associated with a vertex, and
gives information on what cost and how to reach that vertex from the
source.  In Dijkstra, the label is defined as a pair of a cost and a
preceding vertex.  Each vertex has at most one label, which we call
the \emph{vertex label}.  For a given vertex, the vertex label is
initially \emph{tentative}, because it can be updated by the edge
relaxation, and then becomes \emph{permanent} when the vertex is
visited.

The Dijkstra algorithm is label setting in that once a vertex is
visited, its label is set for good (the status of the vertex label
changes from \emph{tentative} to \emph{permanent}), but before that
happens, the vertex label converges to its optimum by \emph{edge
relaxation}.

In Dijkstra, when relaxing edge $e$, a tentative vertex label is
updated with a better candidate label.  The tentative vertex label, if
it exists (i.e., it has been found by some earlier relaxation), is the
tentative vertex label of the target vertex of edge $e$.  The
candidate label is the label produced for edge $e$, and tells the cost
of reaching the target vertex of edge $e$.  The candidate label is
better than the tentative vertex label if it has a lower cost.

\begin{figure}
  \centering
  \begin{tikzpicture}[node distance = 3 cm]
    \node [node] (s) {$s$};
    \node [node, right of = s] (i) {$i$};
    \node [node, right of = i] (t) {$t$};

    \path (s) edge [bend left = 35]
    node [circle, fill = white] {$e_1$}
    node [above] {$\eattrs{1}{\CUO{1}{2}}$} (i);

    \path (s) edge [bend right = 35]
    node [circle, fill = white] {$e_2$}
    node [below] {$\eattrs{2}{\CUO{1}{3}}$} (i);

    \path (i) edge
    node [circle, fill = white] {$e_3$}
    node [above] {$\eattrs{10}{\CUO{2}{3}}$} (t);

  \end{tikzpicture}
  \caption{Example for vertex revisiting and looping.}
  \label{f:example1}
\end{figure}

\subsection{Observations on the stated problem}
\label{observations}

The following three observations shaped the generalization.

\subsubsection{Revisit vertices}

In Dijkstra, a vertex is visited only once for a single label.  We,
however, want to \emph{revisit} a vertex even for a label of a higher
cost than the vertex label, because it may eventually yield a shortest
path capable of supporting a given demand.

To demonstrate vertex revisiting, we show an example in
Fig.~\ref{f:example1}, where an edge is annotated with the length and
the available units, e.g., $\eattrs{1}{\CUO{1}{2}}$ says the edge is
of length 1 with units 1 and 2 available.  We are searching for a
shortest path with two units from vertex $s$ to vertex $t$.

In the first iteration of Dijkstra, vertex $s$ is visited, vertex $i$
is discovered along edge $e_1$, and the discovery along edge $e_2$ is
discarded because of a higher cost.  In the second iteration, vertex
$i$ is visited, and now we know that we can get to vertex $i$ along
edge $e_1$ at cost 1, and with $\CUO{1}{2}$.  The problem is that
vertex $t$ cannot be discovered, because the spectrum continuity
constraint would be violated: the demand requires two units, vertex
$i$ is visited with $\CUO{1}{2}$, but $\AU(e_3) = \CUO{2}{3}$.  We
reach a dead end; the search stops with no solution.

Continuing with the example, and allowing for vertex revisiting, now
vertex $i$ is discovered along both parallel edges $e_1$ and $e_2$,
and none of the discoveries is discarded.  Now there are two tentative
labels for vertex $i$.  Then vertex $i$ is visited along edge $e_1$ at
cost 1 with $\CUO{1}{2}$, and then revisited along edge $e_2$ at cost
2 with $\CUO{1}{3}$, thus allowing vertex $t$ to be discovered, end
eventually visited at cost 12 with $\CUO{2}{3}$.

\begin{figure}
  \centering
  \begin{tikzpicture}[node distance = 3 cm]
    \node [node] (s) {$s$};
    \node [node, right of = s] (i) {$i$};
    \node [node, right of = i] (t) {$t$};

    \path (s) edge [bend left = 35]
    node [circle, fill = white] {$e_1$}
    node [above] {$\eattrs{1}{\CUO{1}{2}}$} (i);

    \path (s) edge [bend right = 35]
    node [circle, fill = white] {$e_3$}
    node [below] {$\eattrs{1}{\CUO{1}{3}}$} (i);

    \path (s) edge [bend left = 7.5]
    node [bend left = 20, circle, fill = white] {$e_2$}
    node [below] {$\eattrs{2}{\CUO{2}{3}}$} (i);

    \path (i) edge
    node [circle, fill = white] {$e_4$}
    node [above] {$\eattrs{1}{\CUO{1}{3}}$} (t);

  \end{tikzpicture}
  \caption{Example for discarding worse labels.}
  \label{f:example2}
\end{figure}

\subsubsection{Avoid loops}

In Dijkstra, loops are avoided, because an edge is relaxed only if it
yields a candidate label of a lower cost.  Since edge costs are
non-negative, loops cannot decrease cost, and so they will not be
allowed by edge relaxation.

The problem is we will find loops if we revisit vertices at higher
costs.  For instance, considering the same example in
Fig.~\ref{f:example1}: when we visit vertex $i$, we rediscover vertex
$s$ and later revisit it, thus finding the loop with edges $e_1$ and
$e_2$.

To avoid loops, we refine when we can revisit a vertex. We still allow
a revisit at a higher cost, \emph{but only for a CU not included in
the CUs of previous visits.}  Therefore, a vertex is visited and
possibly revisited always at the lowest cost for a CU not included in
the CUs of previous visits.

For example, in Fig.~\ref{f:example1}, we start the search by visiting
vertex $s$ at cost 0, and with the CU of $\Omega$.  While visiting
vertex $i$ at cost 1, and with $\CUO{1}{2}$, we rediscover vertex $s$
along edge $e_2$, but the edge will not be relaxed, because vertex $s$
was already visited with $\Omega$, which includes $\CUO{1}{2}$.  This
example would hold even if the loop did not increase the cost.

\subsubsection{Discard labels}

In Dijkstra, when a tentative vertex label is updated by the edge
relaxation, the previous value of the tentative label is discarded.
In generic Dijkstra, when we relax an edge, we can discard a number of
tentative labels.

For instance, in Fig.~\ref{f:example2}, while visiting vertex $s$,
three edges are relaxed: first edge $e_1$ is relaxed at cost 1, and
with $\CUO{1}{2}$, next edge $e_2$ is relaxed at cost 2, and with
$\CUO{2}{3}$, and, finally, edge $e_3$ is relaxed at cost 1, and with
$\CUO{1}{3}$.  The results for edges $e_1$, and $e_2$ are discarded,
because the result for edge $e_3$ is better: at cost 1 it offers
$\CUO{1}{3}$, which includes both $\CUO{1}{2}$, and $\CUO{2}{3}$.
Thus, vertex $i$ is visited at cost 1, and with $\CUO{1}{3}$.

\subsection{Changes to the Dijkstra algorithm}
\label{changes}

Based on the observations, we motivate the changes to the Dijkstra
algorithm that make it generic, and applicable to the stated problem.

\subsubsection{Labels}

\begin{table*}
  \caption{Relations between labels $l_i$ and $l_j$ depending on their
    costs and CUs.}
  \label{t:relations}
  \centering
  \begin{tabular}{c|c|c|c|c|}
    \cline{2-5}
    & $\CU(l_i) \supsetneq \CU(l_j)$
    & $\CU(l_i) = \CU(l_j)$
    & $\CU(l_i) \subsetneq \CU(l_j)$
    & $\CU(l_i) \parallel \CU(l_j)$\\
    \hline
    \multicolumn{1}{|c|}{$\cost(l_i) < \cost(l_j)$}
    & $l_i < l_j$
    & $l_i < l_j$
    & $l_i \parallel l_j$
    & $l_i \parallel l_j$\\
    \hline
    \multicolumn{1}{|c|}{$\cost(l_i) = \cost(l_j)$}
    & $l_i < l_j$
    & $l_i = l_j$
    & $l_i > l_j$
    & $l_i \parallel l_j$\\
    \hline
    \multicolumn{1}{|c|}{$\cost(l_i) > \cost(l_j)$}
    & $l_i \parallel l_j$
    & $l_i > l_j$
    & $l_i > l_j$
    & $l_i \parallel l_j$\\
    \hline
  \end{tabular}
\end{table*}

We define a label as \emph{a tuple of cost, a CU, and a preceding
edge}, to keep track of the CU used.  For instance, label
$\lbl{1}{\CUO{1}{2}}{e_1}$ says that a vertex is reached at cost 1 and
with the CU of $\CUO{1}{2}$ along edge $e_1$.  To allow for
multigraphs, we keep a preceding edge, not a preceding vertex, in the
label.  The cost of label $l_i$ we denote as $\cost(l_i)$, and the
contiguous units as $\CU(l_i)$.  This label can be a candidate label,
a tentative vertex label, or a permanent vertex label.

Label $l_i$ is better than label $l_j$ (or label $l_j$ is worse than
label $l_i$), denoted by $l_i < l_j$, if either:

\begin{enumerate}

  \item label $l_i$ offers a CU which includes the CU of label $l_j$
    at a lower cost than the cost of label $l_j$, i.e., $\cost(l_i) <
    \cost(l_j)$ and $\CU(l_i) \supset \CU(l_j)$, or

  \item label $l_i$ offers a CU which properly includes the CU of
    label $l_j$ at a cost that is lower than or equal to the cost of
    label $l_j$, i.e., $\cost(l_i) \le \cost(l_j)$ and $\CU(l_i)
    \supsetneq \CU(l_j)$.

\end{enumerate}

Our $<$ label relation is a \emph{strict partial order}, since it is
irreflexive and transitive \cite{elements}.  Furthermore, in a strict
partial order some pairs can be incomparable.  We say that labels
$l_i$ and $l_j$ are incomparable, denoted by $l_i \parallel l_j$, when
neither $l_i < l_j$ nor $l_j < l_i$ holds.  Indeed, our labels can be
incomparable.

However, our $<$ order is not a \emph{strict weak order}, because the
incomparability of labels is not transitive.  For example, while
$\eattrs{0}{\CUO{1}{1}} \parallel \eattrs{2}{\CUO{1}{2}}$ and
$\eattrs{2}{\CUO{1}{2}} \parallel \eattrs{1}{\CUO{1}{1}}$ hold,
$\eattrs{0}{\CUO{1}{1}} \parallel \eattrs{1}{\CUO{1}{1}}$ does not,
because $\eattrs{0}{\CUO{1}{1}} < \eattrs{1}{\CUO{1}{1}}$ holds.

Table \ref{t:relations} shows the label relations depending on their
costs and CUs, where relation $l_i > l_j$ means $l_j < l_i$.

When we rediscover or revisit a vertex, we grow \emph{a set of
incomparable labels}, i.e., for any labels $l_i$ and $l_j$ that are
different, $l_i \parallel l_j$ is true, or equivalently $l_i < l_j$ is
false.  The incomparability of labels insures that in the set we do
not store a label that is worse than some other label.

\subsubsection{Iteration}

In an iteration, Dijkstra processes a tentative vertex $v$ (i.e., a
vertex with a tentative label) of the lowest cost, while generic
Dijkstra processes a tentative label of the lowest cost, where the
edge of the tentative label has the target vertex $v$.  The labels we
iterate over are provided by the edge relaxation.

An iteration corresponds to visiting (or revisiting) vertex $v$.  In
Dijkstra, only the status of the label of vertex $v$ changes from
tentative to permanent.  In generic Dijkstra, we insert the tentative
label into the set of permanent (optimal) incomparable labels of
vertex $v$.

\subsubsection{Relaxation}

We reformulate the edge relaxation.  In Dijkstra, an edge is relaxed
when a candidate label is \emph{better} than the vertex label.  In
generic Dijkstra, we relax an edge when there is \emph{no better}
vertex label than the candidate label.  A small tweak.

This tweak makes no difference when the relation between labels is a
strict total order, as in Dijkstra.  However, for our label order, the
tweak entails we relax an edge not only for better labels, but also
for incomparable labels.  A big difference.

In Dijkstra, a vertex has a single label, which is either tentative or
permanent.  In generic Dijkstra, a vertex has a set of tentative
labels, and a set of permanent labels.  Labels in these sets are
incomparable: no label in the two sets is better than some other
label, i.e., for any two different labels (tentative or permanent)
$l_i$ and $l_j$ of the given vertex, $l_i < l_j$ is false.  Our edge
relaxation maintains the labels in the two sets incomparable.

As part of the relaxation we discard those tentative labels (of vertex
$v'$), which are worse than the candidate label.  The permanent labels
are left alone, because they are optimal.

\subsection{Constriction}

Typically, a constriction can be introduced in the edge relaxation,
where we drop a candidate label if it does not meet some conditions.
For instance, to limit the length of a shortest path, we drop a
candidate label if its cost is greater than a given value.  We use the
decision function introduced in the problem statement for the
constriction.

\subsection{Algorithm}

Algorithm \ref{a:algorithm} presents the complete algorithm with the
typical Dijkstra algorithm structure, where the main loop processes
the labels of the priority queue $Q$ sorted in the ascending order of
the label cost.

\begin{algorithm}[t]
  \caption{Generic Dijkstra\\
    In: graph $G$, source vertex $s$, target vertex $t$\\
    Out: a pair of a shortest path, and a CU\\
    \emph{Here we concentrate on permanent labels $l$.}}
  \label{a:algorithm}
    \begin{algorithmic}
      \STATE $Q_s = \{\lbl{0}{\Omega}{e_\emptyset}\}$
      \WHILE{$Q$ is not empty}
      \STATE $l = \text{pop}(Q)$
      \STATE $e = \edge(l)$
      \STATE $v = \target(e)$
      \STATE // Add $l$ to the set of permanent labels of vertex $v$.
      \STATE $L_v = L_v \cup \{l\}$
      \IF{$v == t$}
      \STATE break the main loop
      \ENDIF
      \FORALL{out edge $e'$ of $v$ in $G$}
      \STATE $\myrelax(e', l)$
      \ENDFOR
      \ENDWHILE
      \RETURN $\text{trace}(L, t)$
    \end{algorithmic}
\end{algorithm}

The priority queue $Q$ is a set of $Q_v$, i.e., $Q = \{Q_v\}$, where
$Q_v$ is the set of tentative incomparable labels of vertex $v$.  The
solution of the search is maintained in $L = \{L_v\}$, where $L_v$ is
the set of permanent (optimal) incomparable labels of vertex $v$.

To boot the search, we initialize $Q_s =
\{\lbl{0}{\Omega}{e_\emptyset}\}$ to make all units available at vertex
$s$ at cost 0.  The null edge $e_\emptyset$, which is not present in
graph $G$, marks the beginning of a shortest path.

In every iteration of the main loop, we process label $l$ of the
lowest cost popped from queue $Q$, and along edge $e$ we visit vertex
$v$.  Function $\target(e)$ gives the target vertex of edge $e$ with
the special case of $\target(e_{\emptyset}) == s$, i.e., the source
vertex.  If $v == t$, then we found a solution and break the main
loop.  Otherwise, we try to relax each edge $e'$ leaving vertex $v$.

Algorithm \ref{a:relax} shows the relaxation of edge $e'$ reached with
label $l$.  We relax the edge for a set of incomparable candidate
labels $l'$, which we produce for each CU $C'$ in the set obtained by
intersecting the CU of label $l$ and the available units of edge $e'$.
The candidate labels $l'$ have the same cost $c'$ and edge $e'$, and
differ in the CU $C'$ only.  We examine label $l'$ if the decision
function $\decide(l')$ permits.

Next, if there is no permanent or tentative label of vertex $v'$
better than $l'$, we relax the edge by first discarding any tentative
label of vertex $v'$ which is worse than $l'$, and then adding $l'$ to
$Q_{v'}$.  Edge relaxation replenishes the queue with tentative
labels, and the algorithm keeps iterating until destination vertex $t$
is reached, or the queue is empty.

\begin{algorithm}[t]
  \caption{$\myrelax$\\
    In: edge $e'$, label $l$\\
    \emph{Here we concentrate on tentative labels $l'$.}}
  \label{a:relax}
    \begin{algorithmic}
      \STATE $c = \cost(l)$
      \STATE $c' = c + \text{cost}(e')$
      \STATE $C = \CU(l)$
      \STATE $v' = \text{target}(e')$
      \FORALL{CU $C'$ in $C \cap \AU(e')$}
      \STATE $l' = (c', C', e')$
      \IF{$\decide(l')$}
      \IF{$\nexists l_{v'} \in L_{v'} : l_{v'} < l'$}
      \IF{$\nexists q_{v'} \in Q_{v'} : q_{v'} < l'$}
      \STATE // Discard tentative labels $q_{v'}$ such that $l' < q_{v'}$.
      \STATE $Q_{v'} = Q_{v'} \setminus \{q_{v'} \in Q_{v'}: l' < q_{v'}\}$
      \STATE // Add $l'$ to the set of tentative labels of vertex $v'$.
      \STATE $Q_{v'} = Q_{v'} \cup \{l'\}$
      \ENDIF
      \ENDIF
      \ENDIF
      \ENDFOR
    \end{algorithmic}
\end{algorithm}

The required spectrum allocation policy (e.g., first-fit, best-fit)
can be taken into account by the priority queue while popping a label.
From among the labels of the lowest (equal) cost, the priority queue
should pop the label with the CU preferred by the given spectrum
allocation policy.  For instance, for the best-fit spectrum allocation
policy, the queue should pop the label not only of the lowest cost,
but also of the CU with the lowest number of units.

Finally, once we leave the main loop, function $\trace(L, t)$ traces
back from node $t$ a shortest path found, if any, based on the vertex
labels $L$, and returns a pair of a path and a CU.  The function
selects, according to the spectrum allocation policy used, the CU with
the required number of units from the CU of the vertex label of node
$t$, which may have more units than required.  We do not present the
function, since it is the typical Dijkstra path back-tracing.

To be general, we stated and solved the problem for a directed
multigraph, but the algorithm can be used for undirected multigraphs
too.  In our simulations we modeled an EON with an undirected graph,
and were able to use our algorithm.

\section{Simulations}
\label{simulations}

We compared the memory and time performance of the proposed algorithm
applied to the dynamic RMSA problem with three other optimal
algorithms: the filtered-graphs algorithm, the brute-force algorithm,
and the unlimited Yen KSP algorithm.

Early in our simulation studies, we realized that the unlimited Yen
KSP is very time inefficient, which prohibited using it in our
large-scale simulations.  In one case, Yen produced over three hundred
thousand shortest paths in 24 hours which had not met the spectrum
continuity and contiguity constraints.  For this reason, we were
unable to include the unlimited Yen KSP algorithm in the comparison.

We report the simulation results only for the \emph{first-fit}
spectrum allocation policy, since the \emph{best-fit} and
\emph{random-fit} policies performed worse for all algorithms
compared.

To make the comparison unbiased, we implemented all algorithms with a
great attention to detail, and an emphasis on time and memory
performance.  We especially carefully treated the filtered-graphs
algorithm, and implemented it using our generic Dijkstra
implementation, which is ultra efficient, employing the latest C++17
functionality, such as the extraction of the associative-array
elements with the move semantics.

We made sure that the proposed algorithm and implementation were
correct with unit tests, assertions, and extra code that validated the
optimality and integrity of the results found.  We validated, with the
filtered-graphs algorithm, not only the final results found, but also
the intermediate results.  In the production runs, we disabled the
assertions and the extra code, so that the time measurements were not
disturbed.

In the simulations, we concentrated on the long-haul networks with 75
nodes, since they model the current and future optical transport
networks well.  However, we also carried out simulations for legacy
long-haul networks with 25 nodes, and found that the brute-force
algorithm, and the proposed algorithm performed comparably in terms of
memory usage (using tens of kB), and execution time (taking
milliseconds), while the filtered-graph algorithm was about a hundred
times slower, but used only hundreds of bytes.

We also carried out fragmentary simulations for large, ultra-dense
random networks with 100 nodes and 1000 edges.  We found that the
brute-force algorithm needed very large amounts of memory (more than
96 GB), which we did not have.  The proposed algorithm on average was
using a few hundred kB, and taking milliseconds.  The filtered-graph
algorithm was on average a thousand times slower, and used only a few
kB.

\subsection{Simulation setting}
\label{setting}

The simulation setting had three major parts: the network model, the
traffic model, and the signal modulation model.

\subsubsection{Network model}

We generated a set of random long-haul graphs with random traffic to
obtain reliable statistical results for various populations of
interest.  Specifically, we used Gabriel graphs, because they have
been shown to model the properties of the long-haul transport networks
very well \cite{10.1109/ICUMT.2013.6798402}.

A network model is defined by a network graph, and the number
$|\Omega|$ of edge units.  We randomly generated 100 Gabriel graphs.
Each graph had 75 vertices, which were uniformly distributed over a
square area with the typical density of one vertex per $10^4$
$\text{km}^2$.  In generating Gabriel graphs, the number of edges
cannot be directly controlled, as it depends on the location of
vertices, and on the candidate edges meeting the conditions of the
Gabriel graph.  The statistics of the generated graphs are given in
Table \ref{t:netstats}.

For $|\Omega|$, we used the three values of 160, 320, and 640.  For
the conventional band (C-band), 160 units would require the spacing of
25 GHz, 320 units the spacing of 12.5 GHz, and 640 units the spacing
of 6.25 GHz.

\begin{table}
  \caption{Statistics of the generated Gabriel networks.}
  \label{t:netstats}
  \centering
  \begin{tabular}{|l|r|r|r|r|}
    \hline
    \textbf{Measured quantity} & \textbf{Min} & \textbf{Average} & \textbf{Max} & \textbf{Variance}\\
    \hline
    number of edges & 119 & 131.53 & 145 & 33.84\\
    edge length & 1 & 97.12 & 499 & 2712.19\\
    vertex degree & 1 & 3.51 & 8 & 1.21\\
    shortest-path hops & 1 & 5.96 & 20 & 8.62\\
    shortest-path length & 1 & 510.45 & 1369 & 59518.11\\
    \hline
  \end{tabular}
\end{table}

\subsubsection{Traffic model}

Demands arrive according to the exponential distribution with the rate
of $\lambda$ demands per day.  The probability distribution of the
demand holding time is also exponential with the mean of $\delta$
days.  The end nodes of a demand are different and chosen at random.
The number of units a demand requests follows the distribution of
$(\Poisson(\gamma - 1) + 1)$ with the mean of $\gamma$, i.e., the
Poisson distribution shifted by one to the right, to ensure that the
number of units is greater than zero.

We describe a demand with a requested number of units, and not with a
bitrate, to keep the discussion simple, and because the algorithms
operate on units, and not on bitrate.  If needed, a demand can be
described with bitrate, and the required number of units can be
obtained using function $n_1(b)$, which should take into account the
technical details of the specific modulation and optical hardware
used.

To investigate the difference in algorithm performance as $\gamma$
increases, we used two values of 1 and 10 for $\gamma$.  Using
$\gamma = 1$ approximates the algorithm performance for a traditional
WDM network.

We argue that the choice of a traffic model is irrelevant to our study
as the traffic only produces the input data (i.e., the state of the
graph) for the routing algorithms, and we chose the exponential and
Poisson distributions to keep the discussion simple.  The question is
how the algorithms perform under the given utilization, regardless of
how the utilization was obtained, which could have been equally well
produced randomly.

We express the mean demand arrival rate $\lambda$ as a function of the
offered load $\mu$ as estimated by (\ref{e:lambda}), where $\alpha$ is
the mean number of edges of all shortest-paths in a network being
simulated.  We define the offered load $\mu$ as the ratio of the
number of units demanded to the number of units in the network.  The
average number of demanded units is $\lambda\delta\alpha\gamma$, since
there are $\lambda\delta$ active connections (assuming every demand
has a connection established), and since in an unloaded network a
connection takes on average $\alpha\gamma$ units.  The number of units
in the network is $|E||\Omega|$, and so the offered load $\mu =
\lambda\delta\alpha\gamma/(|E||\Omega|)$, from which (\ref{e:lambda})
follows.

\begin{equation}
  \lambda (\mu) = \frac{\mu|E||\Omega|}{\delta\alpha\gamma}
  \label{e:lambda}
\end{equation}

We define the \emph{network utilization} as the ratio of the number of
units in use to the total number of units on all edges.  We cannot
directly control the network utilization, but only measure it in
response to the offered load $\mu$.

\subsubsection{Signal modulation model}

In EONs, signal modulation can be adapted to the quality of the
optical path, which depends on the length of the path and the optical
components traversed.  If we assume that the quality of the optical
path depends mostly on its length, then a modulation can be
characterized by the reach, i.e., the maximum length of a path above
which the modulation cannot be used, because the signal would suffer
unacceptable bit error rate.  The reach increases as the spectral
efficiency of the modulation decreases.

In \cite{10.1109/MCOM.2010.5534599}, the authors experimentally
demonstrated that if, for a demand requesting bitrate $b$ in b/s, the
most spectrally-efficient modulation available of reach $r_M$ requires
$n_M(b)$ units, then a less spectrally-efficient modulation of reach
$r_m$ requires $(M + 1 - m)n_M(b)$ units, where $m = M, (M - 1), ...,
1$ is integer and is called the modulation level, and $M$ is the
modulation level of the most spectrally-efficient modulation
considered.  Reach $r_m$ doubles for the next less
spectrally-efficient modulation (i.e., $m$ decreases), as given by
(\ref{e:r_m}).  Therefore, for a path of length $r_M < d \le r_1$, we
need to use modulation level $m$ given by (\ref{e:m}), derived from
(\ref{e:r_m}) with the assumption that $m$ is integer.  For $d \le
r_M$ we use $m = M$, and for $r_1 < d$ we have no modulation
available.

\begin{equation}
  r_m = r_M2^{M - m}
  \label{e:r_m}
\end{equation}

\begin{equation}
  m(d) = M + 1 - \ceil{log_2(2d / r_M)}
  \label{e:m}
\end{equation}

However, the assumption that the number of required units is an
integer multiple of $n_M(b)$, because $m$ is integer, is too strict.
The bit error rate, which is increasing with the increasing path
length $d$, can be lowered by using more units for the overhead of the
error correction codes.  In the most general case, the number of
required units should increase by one.  For this reason, we allow the
number of required units to be any integer from $n_M(b)$ to $Mn_M(b)$
depending on distance $0 \le d \le r_1$, as given by (\ref{e:n}).

\begin{equation}
  n(b, d) =
  \begin{cases}
    n_M(b) & \text{if}\ d \le r_M \\
    \infty & \text{if}\ r_1 < d \\
    \ceil{n_M(b)log_2(2d / r_M)} & \text{otherwise}%
  \end{cases}
  \label{e:n}
\end{equation}

\begin{algorithm}[t]
  \caption{$\decide$\\
    In: label $l'$\\
    Out: boolean}
  \label{a:decide}
  \begin{algorithmic}
    \STATE // Make sure that $l'$ has the required number of units.
    \RETURN $n(b, \cost(l')) \le |\CU(l')|$
    \end{algorithmic}
\end{algorithm}

The decision function in Algorithm \ref{a:decide} uses (\ref{e:n}) to
check whether candidate label $l'$ is able to support the demand of
bitrate $b$, i.e., whether $l'$ has at least the number of contiguous
units required for bitrate $b$ at the cost (distance) of $l'$.

In our simulations we assumed $r_1$ equals the length of the longest
of all shortest paths multiplied by 1.5, which allows us to consider
paths which were far longer than an average shortest path.  Using
(\ref{e:r_m}), we calculated $r_M$ for (\ref{e:n}).  We tried to
increase the multiple from 1.5 to 2.0, but the brute-force algorithm
would cause the simulations to run out of memory.  We assumed $M = 4$.

\subsection{Runs and populations}

\emph{A simulation run} simulated 100 days of a network in operation.
The parameters of a simulation run were: the network graph, the number
of units $|\Omega|$, the mean number of demanded units $\gamma$, the
offered load $\mu$, and the mean connection holding time $\delta$.  A
simulation run reported the mean network utilization, and, for each of
the algorithms evaluated, the mean and maximum memory used, and the
mean and maximum times taken by a shortest-path search.

When a demand arrived, we searched for an optical path using all
evaluated algorithms.  We made sure that either all algorithms found
no result, or that all results found were of the same cost and the
same number of contiguous units.  The result of the proposed algorithm
was used to establish a connection.

During a shortest-path search we measured the maximum number of 32 bit
words required by the largest data structures of the algorithm
evaluated: the sets of tentative and permanent labels of the proposed
algorithm, the vertex labels and the priority queue of the
filtered-graphs algorithm, and the priority queue of the brute-force
algorithm.  We tracked separately the words required to store the
costs, edges, and units.  We stored a cost in one word, an edge in two
words, a single unit in one word, and a CU in two words.  Using the
obtained memory measurements of a shortest-path search, we calculated
the mean and maximum memory used by each algorithm throughout a
simulation run.  With careful implementation and testing, we made sure
that the memory measurement had negligible effect on the time
measurement.

Time measurement required special attention, because we ran
simulations using a supercomputing infrastructure.  While we were able
to select one specific hardware type for all our simulations, we had
little control over how much the hardware was loaded with the
processes of other users, which could have severely degraded the
performance of our simulations.  For this reason we repeated a
simulation run after a few hours, and for every time measurement, we
took the minimum of the two values obtained, based on which we
calculated the mean and maximum time taken by each of the algorithms
throughout a simulation run.

We are interested in the results for a statistical population of
simulation runs, rather than in the results for a single simulation
run only, because a simulation run could have been an outlier with
unusual results due to its randomly-generated network and traffic.  To
estimate a mean result for a population, we carried out the simulation
runs which were the population samples, and calculated a \emph{sample
mean} of all the mean results reported by the simulation runs.  We
estimated the pessimistic algorithm performance of a population by a
\emph{sample maximum}, which is the maximum of the maximum results
reported by the simulation runs.

In a given population there were 100 simulation runs whose parameters
differed only with the network model.  Hence, we had 100 Gabriel
graphs generated, and used for every population.  We had 102
populations, because we varied 3 values of the number of units
$|\Omega|$ (160, 320, 640), 17 values of the offered load $\mu$ (0.05,
0.075, 0.1, 0.125, 0.15, 0.175, 0.2, 0.3, 0.45, 0.55, 0.65, 0.75, 1,
1.25, 1.5, 1.75, and 2), and two values of the mean number of demanded
units $\gamma$ (1, 10).  For all populations, the mean connection
holding time $\delta = 10$ days was constant.  In total we carried out
10200 simulation runs (102 populations $\times$ 100 samples), which
then we repeated.  For the proposed algorithm and the filtered-graphs
algorithms, the sample means credibly estimate the mean results of
populations, since their relative standard error is usually around
1\%.  For the brute-force algorithm, the sample means frequently have
the relative standard error of around 20\%.

\subsection{Simulation results}
\label{results}

Figure \ref{f:plots} shows the sample means and the sample maxima of
the time taken and memory used by a shortest path search, regardless
of whether the search was successful or not.  The results are shown on
a logarithmic scale as a function of network utilization.  The curves
are plotted solid for the proposed algorithm, dashed for the
filtered-graphs algorithm, and dotted for the brute-force algorithm.
The sample means are plotted thin, and the sample maxima thick.  Each
curve is drawn using 17 data points for different values of $\mu$.
The error bars of the 95\% confidence interval, appear only for the
sample means of the brute-force algorithm, since their relative
standard error was high, frequently around 20\%, while for the other
sample means the error bars were too small to plot.

Figure \ref{f:plots} has 12 subfigures in four rows and three columns.
The first and the second rows show the time results for $\gamma = 1$,
and $\gamma = 10$, respectively, and the third and fourth rows show
the memory results for $\gamma = 1$, and $\gamma = 10$, respectively.
The first column shows the results for $|\Omega| = 160$, the second
for $|\Omega| = 320$, and the third for $|\Omega| = 640$.  We use the
same scales in the various plots to allow for easy comparison.

The sample mean time results for $\gamma = 1$ show that the proposed
algorithm was usually about 10 times faster and at most 20 times
faster than two other algorithms, except at very heavy utilization,
where most searches ended up with no solution, and where the
brute-force algorithm was able to determine this more quickly.  As the
utilization increased, the mean time of every algorithm decreased, as
the solution was less likely to exist.  As the number of units
increased from 160 to 320, and from 320 to 640 the mean time results
increased about twice for the proposed algorithm and the
filtered-graphs algorithm, and stayed about the same for the
brute-force algorithm.

The sample mean time results for $\gamma = 10$ show that the proposed
algorithm \emph{was hundreds of times} faster than two other
algorithms, and for the case of 640 units and light utilization, the
proposed algorithm was about 500 times faster than the filtered-graphs
algorithm.

As to the pessimistic time performance, i.e., the sample maximum time
taken, our algorithm and the filtered-graphs algorithm usually took a
few seconds, while the brute-force algorithm usually took hundreds of
seconds, which makes a gap of \emph{two orders of magnitude}.

The memory results are clear-cut: the filtered-graphs algorithm
performed the best (since it used the Dijkstra algorithm), our
algorithm performed very well, and the brute-force algorithm performed
the worst.  While the sample mean memory results of the brute-force
algorithm are acceptable (even better than those of the proposed
algorithm for heavy utilization), the sample maximum memory results
reveal the unacceptable memory performance of the brute-force
algorithm: the brute-force algorithm required about \emph{six orders
of magnitude} more memory than the proposed and the filtered-graphs
algorithms.

As the number of units increased from 160 to 320, and from 320 to 640
the mean memory results increased almost twice for our algorithm, for
the filtered-graphs algorithm the results expectedly stayed the same,
and for the brute-force algorithm increased about 10\%.  The memory
used by our algorithm and the brute-force algorithm were smaller for
$\gamma = 10$ in comparison with $\gamma = 1$, because the spectrum
was fragmented less.

\begin{figure*}
  \subfloat[time taken for $\gamma = 1$, and 160 units]{%
    \label{f:time_1_160}%
    \input{time_1_160.tikz}}\hfill%
  \subfloat[time taken for $\gamma = 1$, and 320 units]{%
    \label{f:time_1_320}%
    \input{time_1_320.tikz}}\hfill%
  \subfloat[time taken for $\gamma = 1$, and 640 units]{%
    \label{f:time_1_640}%
    \input{time_1_640.tikz}}\\[3pt]
  \subfloat[time taken for $\gamma = 10$, and 160 units]{%
    \label{f:time_10_160}%
    \input{time_10_160.tikz}}\hfill%
  \subfloat[time taken for $\gamma = 10$, and 320 units]{%
    \label{f:time_10_320}%
    \input{time_10_320.tikz}}\hfill%
  \subfloat[time taken for $\gamma = 10$, and 640 units]{%
    \label{f:time_10_640}%
    \input{time_10_640.tikz}}\\[3pt]
  \subfloat[memory used for $\gamma = 1$, and 160 units]{%
    \label{f:memory_1_160}%
    \input{memory_1_160.tikz}}\hfill%
  \subfloat[memory used for $\gamma = 1$, and 320 units]{%
    \label{f:memory_1_320}%
    \input{memory_1_320.tikz}}\hfill%
  \subfloat[memory used for $\gamma = 1$, and 640 units]{%
    \label{f:memory_1_640}%
    \input{memory_1_640.tikz}}\\[3pt]
  \subfloat[memory used for $\gamma = 10$, and 160 units]{%
    \label{f:memory_10_160}%
    \input{memory_10_160.tikz}}\hfill%
  \subfloat[memory used for $\gamma = 10$, and 320 units]{%
    \label{f:memory_10_320}%
    \input{memory_10_320.tikz}}\hfill%
  \subfloat[memory used for $\gamma = 10$, and 640 units]{%
    \label{f:memory_10_640}%
    \input{memory_10_640.tikz}}\\[10pt]
  \centering\ref{regular}%
  \caption{Simulation results: the sample means and maxima of the time taken and memory used by the evaluated algorithms.}
  \label{f:plots}
\end{figure*}

Figure \ref{f:stack} shows the stacked plots of the maximum number of
required memory words by our algorithm (Fig.~\ref{f:stack_dijkstra}),
the filtered-graphs algorithm (Fig.~\ref{f:stack_parallel}), and the
brute-force algorithm (Fig.~\ref{f:stack_brtforce}).  In each of the
plots there are 17 $\times$ 3 data points, because for the 17 values
of the offered load $\mu$ we report the maximum number of required
costs, edges, and units.  The results are at the order of $10^4$ for
our algorithm, $10^2$ for the filtered-graphs algorithm, and $10^9$
for the brute-force algorithm.  Clearly, the filtered-graphs algorithm
performs best (requiring at most 1.2 kB), followed by our algorithm
(requiring at most 160 kB), and then followed by the brute-force
algorithm (requiring at most 10 GB).  For our algorithm, the memory
was used in 20\% for costs, in 40\% for edges, and 40\% for units,
since a label has one cost (one word), one edge (two words), and one
CU (two words).  For the filtered-graphs algorithm, the memory was
used mainly to store edges, and costs, since a label has one cost and
one edge.  The brute-force algorithm used most of its memory to store
the units of the paths in the priority queue.

\begin{figure*}
  \subfloat[Proposed algorithm.]{%
    \label{f:stack_dijkstra}%
    \input{stack_dijkstra.tikz}}\hfill%
  \subfloat[Filtered-graphs algorithm.]{%
    \label{f:stack_parallel}%
    \input{stack_parallel.tikz}}\hfill%
  \subfloat[Brute-force algorithm.]{%
    \label{f:stack_brtforce}%
    \input{stack_brtforce.tikz}}\\[10pt]
  \centering\ref{stack}%
  \caption{Simulation results: the maximum number of required words by
    the evaluated algorithms.}
  \label{f:stack}
\end{figure*}

Table \ref{t:summary} summarizes the algorithm comparison.

\begin{table}
  \caption{Summary of algorithm comparison.}
  \label{t:summary}
  \centering
  \begin{tabular}{|p{0.21\columnwidth}|p{0.325\columnwidth}|p{0.325\columnwidth}|}
    \hline
    \textbf{Algorithm} & \textbf{Pros} & \textbf{Cons}\\
    \hline
    generic Dijkstra & fastest & complex\\
    \hline
    filtered-graphs & ultra-low memory usage & slow\\
    \hline
    brute-force & good for small networks & fails for large networks\\
    \hline
  \end{tabular}
\end{table}

\section{Conclusion}
\label{conclusion}

We proposed a novel generalization of the Dijkstra shortest path
algorithm for finding a shortest path in the wavelength-division
multiplexed networks and the elastic optical networks.

Our extensive simulation studies show that the proposed algorithm has
a small memory footprint and is considerably (even hundreds of times)
faster than other routing algorithms that are frequently utilized.

We provide no proof of correctness or complexity analysis.  However,
with robust simulations, we corroborated the correctness and
efficiency of the proposed algorithm.

We presented the algorithm in the setting of optical networks, but we
believe that the novel ideas we introduced can be applied in the
routing in the multilayer and wireless networks to make their control
quicker.  For instance, the algorithm could be used to solve
efficiently the contiguous frequency and time resource allocation in
the wireless orthogonal frequency-multiplexed wireless networks.

There are a number of directions for future work.  First, the
algorithm could be adapted for parallel execution, making it even
faster.  Second, the algorithm could be turned into a distributed
algorithm, very much like a distance-vector algorithm.  Next, the
algorithm could be extended further to be applicable to multilayer
networks or space-division multiplexed networks.  Finally, the
algorithm could be extended to take into account signal regeneration,
spectrum conversion, or inverse multiplexing.

\section*{Acknowledgments}

I, Irek Szcześniak, dedicate this work to my mom and dad, Halina and
Jerzy Szcześniak, for their never-ending love and support.

We thank the anonymous reviewers for their constructive criticism,
which helped us improve our work.

redpajama_set_name: RedPajamaArXiv


text:
India, All India
London court to hear Vijay Mallya extradition case, review Mumbai jail cell
Published : Sep 12, 2018, 1:32 pm IST
Updated : Sep 12, 2018, 1:32 pm IST
Mallya's defence team had demanded inspection of jail cell to ensure it meets UK's human rights obligations related to extradition.
The 62-year-old former Kingfisher Airline boss, who has been on bail on an extradition warrant since his arrest in April 2017, is fighting extradition to India on charges of fraud and money laundering amounting to around Rs 9,000 crores. (Photo: File)
Mumbai/London: Vijay Mallya will appear before a London court on Wednesday for a hearing in his extradition case, during which the judge is expected to review a video of the Mumbai jail cell prepared by the Indian authorities for the embattled liquor tycoon.
The 62-year-old former Kingfisher Airline boss, who has been on bail on an extradition warrant since his arrest in April 2017, is fighting extradition to India on charges of fraud and money laundering amounting to around Rs 9,000 crores.
At the previous hearing in July in the Westminster Magistrates' Court in, Judge Emma Arbuthnot had asked the Indian authorities to submit a "step by step video" of the Barrack 12 of Arthur Road Jail for "the avoidance of doubt" over the availability of natural light in the cell where the businessman is expected to be detained pre-trial, during trial and in the event he is convicted by the Indian courts.
Also Read: UK court asks India for video of prison where Vijay Mallya will be kept
The Crown Prosecution Service (CPS), arguing on behalf of the Indian government, had agreed to the request and the video has since been submitted to the court. Mallya's defence team had demanded an inspection of the jail cell to ensure it meets the UK's human rights obligations related to extradition proceedings.
The CPS stressed that the Indian government had provided "adequate material" which rendered the need for an inspection unnecessary, leading to the demand for a video recording to be reviewed by the court. The judge is also expected to hear the final closing arguments in the case, after which a timeline for her ruling is likely to become clearer.
The extradition trial, which opened at the London court on December 4, 2017, is aimed at laying out a prima facie case of fraud against Mallya. It also seeks to prove there are no "bars to extradition" and that the tycoon is assured a fair trial in India over his now-defunct Kingfisher Airlines' alleged default of over Rs 9,000 crores in loans from a consortium of Indian banks.
The CPS has argued that the evidence they have presented establishes "dishonesty" on the part of the businessman and that there are no bars to him being extradited from the UK to face Indian courts.
Tags: vijay mallya, vijay mallya extradition case
Location: India, Maharashtra, Mumbai (Bombay)
Latest From India
Jaishankar urges Pak to free Jadhav immediately
Supreme Court hearings on Ayodhya begin August 2
Karnataka gov to HD Kumaraswamy: Prove majority by 1.30 pm today
Direct Tax Code report by July 31
ALSO FROMLife
Belarus: Heaven for nature lovers
Running of the Bulls at the San Fermin Festival
Countless cats beckon visitors at a temple in a quiet Tokyo neighbourhood
New-born lion cub photos that will melt your heart
Europe celebrates LGBTQ Pride with colourful parades
Breathtaking firework display on the Fourth of July


text:
Биликтуй () — село в составе Железнодорожного муниципального образования Усольского района Иркутской области.

Происхождение названия
Название Биликтуй связано с  — «мудрость», «ум», «знание», «способность», «дарование», бэлигтэ(й) — «разумный», «мудрый», «одарённый», «даровитый», «талантливый». Предполагается, что это могло быть имя жившего здесь бурята.

География
Расположено примерно в 20 километрах от райцентра на реках Картагон и Биликтуйка.

Внутреннее деление
Село состоит из 13 улиц:
 8 Марта
 Зеленый Мыс
 Интернациональная
 Коммунистическая
 Набережная
 Новая
 Октябрьских Событий
 Полевая
 Советский (переулок)
 Совхозная
 Советская
 Школьный (переулок)
 Чапаева
Кроме того, в состав села входят садовые товарищества Монтажник и Черёмушки.

История

Предположительно, населённый пункт был основан в 1720 году семьями ямщиков.

После подавления крестьянского восстания под предводительством Емельяна Пугачёва в Биликтуй были сосланы 17 его участников.

Население села на 1807 год составляло 663 человека.

В 1860-е годы в Биликтуе была открыта мельница.

В 1872 году в селе было открыто училище на три класса, где учились около 60 человек.

Большинство местных жителей работали на проходившем рядом Московском тракте, занимались растениеводством, а также охотой и рыболовством. Продукты хозяйства продавались на базарах в населённом пункте Тельма. Некоторые из биликтуйцев совершали грабежи проходивших по тракту обозов. В 1892 году в газете «Сибирь» писалось: «Обозные ямщики сообщили, что между Биликтуем и Мальтою учреждены казачьи разъезды в видах ограждения обозов от грабежей. Но, тем не менее, сельские власти, по той же причине не позволяли обозам ночью проходить через Усолье, Тельму, Биликтуй»

В 1898 году через Биликтуй прошла Транссибирская магистраль, что положительно сказалось на экономическом положении населённого пункта.

На 1901 год население Биликтуя составляло 1262 жителя, кроме того там проживали 124 ссыльных.

В 1904 году в населённом пункте открыли Фельдшерский пункт.

Религия
В 1876-1815 годах в Биликтуе (Биликтуйской слободе) была построена каменная церковь. Это была каменная церковь, вероятно, довольно крупная, так как имела три престола. Главный из них, в холодном храме был освящен во имя Рождества Христова; боковые теплые приделы были посвящены - Святителю и Чудотворцу Николаю (правый) и Александру Невскому (левый). Храм имел в завершении восьмерик, над папертью возвышалась колокольня. Все здание венчало пять позолоченных крестов. При обозрении церквей в 1828 году иркутский архиепископ Михаил отметил, что церковь прочная и "очень хорошая".

На 1910 год в приходе церкви насчитывался 1851 прихожанин.

15 апреля 1935 года по Биликтуйский сельсовет принял постановление о закрытии церкви. В настоящий момент от неё ничего не осталось.

Также в Биликтуе была мечеть (о чем свидетельствуют архивы).

Население

Примечания

Населённые пункты Усольского района (Иркутская область)

redpajama_set_name: RedPajamaWikipedia


Vegetable and fruit prices have highly increased in HCMC because heavy rain triggered flooding has submerged thousands of hectares of crops in the Central Highlands and the central region for the last couple of days.
The unfavorable weather condition has reduced supply and hiked prices since October, reported deputy chairwoman of the HCMC Department of Industry and Trade Nguyen Huynh Trang at a meeting, chaired deputy chairman of the city People's Committee Tran Vinh Tuyen yesterday.
However the supply shortage and price surge is forecast to not extend long as production will be resumed in flooding affected provinces and broadened in other areas of the country to meet high demand in the lead of the Tet holidays, she added.
The supply sources of pork, poultry, sugar, egg and rice have been abundant so there will no price fluctuation from now until the end of the year.
In October, the consumer price index soared 0.62 percent against the previous month with eight out of 11 groups of commodities seeing price up and three down.
According to Ms. Trang, the index increase was due to the hike of 2.27 percent in traffic group because of up petrol price. Education saw an increase of 2.05 percent after tuition levels started rising for nursery and vocational schools in the month.


text:
package org.cagrid.gaards.websso.test.system.steps;

import java.io.File;
import java.util.List;

import org.cagrid.gaards.websso.test.system.WebSSOSystemTest;
import org.jdom.Document;
import org.jdom.Element;
import org.jdom.Namespace;

import gov.nih.nci.cagrid.common.Utils;
import gov.nih.nci.cagrid.common.XMLUtilities;
import gov.nih.nci.cagrid.testing.system.deployment.ContainerException;
import gov.nih.nci.cagrid.testing.system.haste.Step;

/**
 * Add certificates and key file as Filter param values in web.xml.
 * @author garmillas
 *
 */
public class WebSSOClientCertificatesStep extends Step {

	private File tempWebSSOClientService;
	private String hostCertificate;
	private String hostCertificateKey;

	public WebSSOClientCertificatesStep(File tempWebSSOClientService,
			String hostCertificate, String hostCertificateKey) {
		this.tempWebSSOClientService = tempWebSSOClientService;
		this.hostCertificate=hostCertificate;
		this.hostCertificateKey=hostCertificateKey;
	}

	@Override
	public void runStep() throws Throwable {
		modifyCASJasigWebXML();
		modifyCASAcegiApplicationContextXML();
	}

	private void modifyCASAcegiApplicationContextXML() {
	}

	@SuppressWarnings("unchecked")
	private void modifyCASJasigWebXML() throws Exception {
		File webssopropertiesfile = new File(tempWebSSOClientService
				.getCanonicalPath(), "ext" + File.separator
				+ "dependencies-xml-resources" + File.separator + "xmls"
				+ File.separator + "web-template-jasig-"+WebSSOSystemTest.getProjectVersion()+".xml");

	    Document confDocument = null;
	    try {
	        confDocument = XMLUtilities.fileNameToDocument(webssopropertiesfile.getCanonicalPath());
	    } catch (Exception ex) {
	        throw new ContainerException("Error loading websso server properties document for editing: " + ex.getMessage(), ex);
	    }
	    // locate the param name  certificate-file-path and key-file-path
	    Element webXMLElement= confDocument.getRootElement();
	    Namespace namespace=Namespace.getNamespace("", "http://java.sun.com/xml/ns/j2ee");
	    List<Element> filters=(List<Element>)webXMLElement.getChildren("filter",namespace);
		for (Element filter : filters) {
			Element filterName=filter.getChild("filter-name",namespace);
			if (filterName.getValue().equals("caGRID WebSSO Delegation Lookup Filter")) {
				List<Element> initParams = (List<Element>) filter.getChildren("init-param",namespace);
				for (Element initParam : initParams) {
					Element paramName = initParam.getChild("param-name",namespace);
					if (paramName.getValue().equals("certificate-file-path")) {
						Element paramValue = initParam.getChild("param-value",namespace);
						paramValue.removeContent();
						paramValue.addContent(hostCertificate);
					}
					if (paramName.getValue().equals("key-file-path")) {
						Element paramValue = initParam.getChild("param-value",namespace);
						paramValue.removeContent();
						paramValue.addContent(hostCertificateKey);
					}
				}
			}
		}
	    // write the webssoproperties.xml back to disk
	    String confXml = XMLUtilities.documentToString(confDocument);
	    try {
	    	System.out.println(webssopropertiesfile.getCanonicalPath());
	        Utils.stringBufferToFile(new StringBuffer(confXml), webssopropertiesfile.getCanonicalPath());
	    } catch (Exception ex) {
	        throw new ContainerException("Error writing server configuration file back to disk: " + ex.getMessage(), ex);
	    }
	}

	public static void main(String[] args) throws Throwable {
		File tempWebSSOService = new File("C:/devroot/caGrid/cagrid-1-0/tests/projects/websso/tmp/websso-client-example");
		WebSSOClientCertificatesStep step = new WebSSOClientCertificatesStep(tempWebSSOService,"xxxxxxxx","yyyyyyyy");
		step.runStep();
	}
}

redpajama_set_name: RedPajamaGithub


text:
Музей этнографии в Могилёве является филиалом Могилёвского областного историко-краеведческого музея. Располагается по адресу ул. Первомайская № 8. Открыт в 1981 году.

Площадь экспозиции 760 м², 4,5 тыс. предметов основного фонда (2000). Материалы музея знакомят с состоянием материальной и духовной культуры крестьян Могилевского Поднепровья городского быта могилевчан конца XIX — начала XX веков. Среди экспонатов — орудия труда, предметы быта, национальная одежда могилевских и краснопольских костюмов, коллекция подлинных могилёвских полотенец, иконы, изразцы и деревянная скульптура XVII — XIX веков, церковные книги, журналы XIX — начала XX веков.

Здание музея стоит на фундаменте Могилёвского иезуитского коллегиума. Внутренняя стена, которая выходит во двор музея, является аутентичной стеной XVIII века, бывшей частью коллегиума.

Литература
 Музей этнаграфіі // Беларуская энцыклапедыя: У 18 тамах / Беларуская энцыклапедыя; Рэдкалегія: Г. П. Пашкоў (галоўны рэдактар) [і інш.]. Том 11: Мугір — паліклініка. — : Беларуская энцыклапедыя, 2000. — С. 13.

Ссылки

Этнографические музеи
Музеи Могилёва
Википедия:Ссылка на Викисклад непосредственно в статье


We Heart YA: "Hit Me Over the Head" or "Hide and Seek" - how obvious do you like your literary themes?
No, I don't like to be hit over the head, but I also consider it a problem if I can't make any sense of why a character is behaving the way s/he is. In other words, like many, I like to be given the clues to figure things out for myself but I don't want it to be too hard LOL.
I started Thirteen Reasons but I was a bit put off. The suicide theme is a tough one, and all the spy-game stuff seemed a little crazy.
The Things A Brother Knows was spectacular. Beautiful. I loved the mystery aspect so much, and the way that she portrayed families. You can live so close to someone and only catch glimpses of who they are sometimes.
To be fair, I like both. Not everyone can do both, so they choose either or and that's okay with me. If you can be creative and subtle but still in a way where I can interpret what's going on - perfect. If you can be forthright and realistic - also okay!
I just need to be able to believe it.
The happy medium. We like that area of the spectrum too.
"You can live so close to someone and only catch glimpses of who they are sometimes."
YES. Exactly. So poignant. So real.
You have a very good attitude about it!