You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@arrow.apache.org by Bechir Ben Daadouch <be...@gmail.com> on 2023/06/30 01:21:43 UTC
Apache Arrow | Graph Algorithms & Data Structures
Dear Apache Arrow Dev Community,
My name is Bechir, I am currently working on a project that involves
implementing graph algorithms in Apache Arrow.
The initial plan was to construct a node structure and a subsequent graph
that would encompass all the nodes. However, I quickly realized that due to
Apache Arrow's columnar format, this approach was not feasible.
I tried a couple of things, including the implementation of the
shortest-path algorithm. However, I rapidly discovered that manipulating
arrow objects, particularly when applying graph algorithms, proved more
complex than anticipated and it became very clear that I would need to
resort to some data structures outside of what arrow offers (i.e.: Heapq
wouldn't be possible using arrow).
I also gave a shot at doing it similar to a certain SQL method (see:
https://ibb.co/0rPGB42 ), but ran into some roadblocks there too and I
ended up having to resort to using Pandas for some transformations.
My next course of action is to experiment with compressed sparse rows,
hoping to execute Matrix Multiplication using this method. But honestly,
with what I know right now, I remain skeptical about the feasibility
of it. However,
before committing to this approach, I would greatly appreciate your opinion
based on your experience with Apache Arrow.
Thank you very much for your time.
Looking forward to potentially discussing this further.
Many thanks,
Bechir
Re: Apache Arrow | Graph Algorithms & Data Structures
Posted by Weston Pace <we...@gmail.com>.
Is your use case to operate on a batch of graphs? For example, do you have
hundreds or thousands of graphs that you need to run these algorithms on at
once?
Or is your use case to operate on a single large graph? If it's the
single-graph case then how many nodes do you have?
If it's one graph and the graph itself is pretty small and fits into cache,
then I'm not sure the in-memory representation will matter much (though
maybe the search space is large enough to justify a different
representation)
On Thu, Jun 29, 2023 at 6:22 PM Bechir Ben Daadouch <be...@gmail.com>
wrote:
> Dear Apache Arrow Dev Community,
>
> My name is Bechir, I am currently working on a project that involves
> implementing graph algorithms in Apache Arrow.
>
> The initial plan was to construct a node structure and a subsequent graph
> that would encompass all the nodes. However, I quickly realized that due to
> Apache Arrow's columnar format, this approach was not feasible.
>
> I tried a couple of things, including the implementation of the
> shortest-path algorithm. However, I rapidly discovered that manipulating
> arrow objects, particularly when applying graph algorithms, proved more
> complex than anticipated and it became very clear that I would need to
> resort to some data structures outside of what arrow offers (i.e.: Heapq
> wouldn't be possible using arrow).
>
> I also gave a shot at doing it similar to a certain SQL method (see:
> https://ibb.co/0rPGB42 ), but ran into some roadblocks there too and I
> ended up having to resort to using Pandas for some transformations.
>
> My next course of action is to experiment with compressed sparse rows,
> hoping to execute Matrix Multiplication using this method. But honestly,
> with what I know right now, I remain skeptical about the feasibility
> of it. However,
> before committing to this approach, I would greatly appreciate your opinion
> based on your experience with Apache Arrow.
>
> Thank you very much for your time.
>
> Looking forward to potentially discussing this further.
>
> Many thanks,
> Bechir
>
Re: Apache Arrow | Graph Algorithms & Data Structures
Posted by Bechir Ben Daadouch <be...@gmail.com>.
Hi,
@Adam, thank you :)
@Aldrin:
First, I tried to implement the basic data structures needed for graph
algorithms, namely a queue and a heapq (for breadth first search
and dijkstra (weighted shortest path)). That's when I had some problems
since Apache Arrow objects are immutable.
This is how I implemented the queue:
https://replit.com/@BechirBen2/ArrowQueue#arrow_array_queue.py
I used the concat_arrays method in the enqueue method, basically creating a
new array every time I add an object to the queue.
This is how I implemented breadth first search:
https://replit.com/@BechirBen2/Graph-Apache-Arrow#arrow_breadh_first_search.py
As you can see I had to resort to converting the objects to python objects
and using python Set.
for the Heapq, I haven't tried since I'll probably be doing some back and
forth between Arrow objects and Python types, I'd be better off using the
Heapq module from Python directly.
Since I can't do operations elementwise, I saw no use in using adjacency
lists. Here is a screenshot on how I represented the data:
https://ibb.co/pxyFpb6
I basically saved the nodes as Int64 and the neighboring nodes in a List.
For the sql approach I did something similar to this:
https://imgbb.com/0rPGB42
I basically use the pyarrow.compute module:
1- Filter the neighbors of the start Node: https://ibb.co/2gMDHnX
2- use pc.list_flatten and then check if the target node is in the
neighboring nodes using pc.is_in(flat_neighbors, target_node)
3- If not, I convert the pyarrow table to pandas, then I explode the
neighboring_nodes, and save the start_node in a new column called
source_path: https://ibb.co/60Vj0RX
and I continue like this until we reach the target or we reach the last
node(s) without neighbors
@Gavin: Thank you for taking the time to give a code example. I already did
^^
On Fri, Jun 30, 2023 at 8:55 PM Gavin Ray <ra...@gmail.com> wrote:
> This isn't particularly efficient, but could you do something like this?
>
> https://replit.com/@GavinRay97/EnlightenedRichAdministration#main.py
>
> On Fri, Jun 30, 2023 at 1:10 PM Aldrin <oc...@pm.me.invalid> wrote:
>
> > > But I found out very quickly that I won't be able to... using only
> > Apache Arrow without resorting to other libraries.
> >
> > > I am aiming to assess the viability of Apache Arrow for graph
> algorithms
> > and data structures...
> >
> > > I also gave a shot at doing it similar to a certain SQL method...
> >
> > I'm curious about these portions of what you've said.
> >
> > Could you share what you have tried and what roadblocks you're hitting?
> > Are you struggling with mutability? How are you representing your data?
> You
> > mention heapq, but it's not clear if you're using an adjacency matrix or
> > adjacency lists or if you're using a more normalized relational format.
> >
> > Thanks!
> >
> >
> > # ------------------------------
> >
> > # Aldrin
> >
> >
> > https://github.com/drin/
> >
> > https://gitlab.com/octalene
> >
> > https://keybase.io/octalene
>
Re: Apache Arrow | Graph Algorithms & Data Structures
Posted by Bechir Ben Daadouch <be...@gmail.com>.
Hi,
Adam, thank you :)
Aldrin:
First, I tried to implement the basic data structures needed for graph
algorithms, namely a queue and a heapq (for breadth first search
and dijkstra (weighted shortest path)). That's when I had some problems
since Apache Arrow objects are immutable.
This is how I implemented the queue:
https://replit.com/@BechirBen2/ArrowQueue#arrow_array_queue.py
I used the concat_arrays method in the enqueue method, basically creating a
new array every time I add an object to the queue.
This is how I implemented breadth first search:
https://replit.com/@BechirBen2/Graph-Apache-Arrow#arrow_breadh_first_search.py
As you can see I had to resort to converting the objects to python objects
and using python Set.
for the Heapq, I haven't tried since I'll probably be doing some back and
forth between Arrow objects and Python types, I'd be better off using the
Heapq module from Python directly.
Since I can't do operations elementwise, I saw no use in using adjacency
lists. Here is a screenshot on how I represented the data:
https://ibb.co/pxyFpb6
I basically saved the nodes as Int64 and the neighboring nodes in a List.
For the sql approach I did something similar to this:
https://imgbb.com/0rPGB42
I basically use the pyarrow.compute module:
1- Filter the neighbors of the start Node: https://ibb.co/2gMDHnX
2- use pc.list_flatten and then check if the target node is in the
neighboring nodes using pc.is_in(flat_neighbors, target_node)
3- If not, I convert the pyarrow table to pandas, then I explode the
neighboring_nodes, and save the start_node in a new column called
source_path: https://ibb.co/60Vj0RX
and I continue like this until we reach the target or we reach the last
node(s) without neighbors
Gavin: Thank you for taking the time to give a code example. I already did
^^
On Fri, Jun 30, 2023 at 8:55 PM Gavin Ray <ra...@gmail.com> wrote:
> This isn't particularly efficient, but could you do something like this?
>
> https://replit.com/@GavinRay97/EnlightenedRichAdministration#main.py
>
> On Fri, Jun 30, 2023 at 1:10 PM Aldrin <oc...@pm.me.invalid> wrote:
>
> > > But I found out very quickly that I won't be able to... using only
> > Apache Arrow without resorting to other libraries.
> >
> > > I am aiming to assess the viability of Apache Arrow for graph
> algorithms
> > and data structures...
> >
> > > I also gave a shot at doing it similar to a certain SQL method...
> >
> > I'm curious about these portions of what you've said.
> >
> > Could you share what you have tried and what roadblocks you're hitting?
> > Are you struggling with mutability? How are you representing your data?
> You
> > mention heapq, but it's not clear if you're using an adjacency matrix or
> > adjacency lists or if you're using a more normalized relational format.
> >
> > Thanks!
> >
> >
> > # ------------------------------
> >
> > # Aldrin
> >
> >
> > https://github.com/drin/
> >
> > https://gitlab.com/octalene
> >
> > https://keybase.io/octalene
>
Re: Apache Arrow | Graph Algorithms & Data Structures
Posted by Gavin Ray <ra...@gmail.com>.
This isn't particularly efficient, but could you do something like this?
https://replit.com/@GavinRay97/EnlightenedRichAdministration#main.py
On Fri, Jun 30, 2023 at 1:10 PM Aldrin <oc...@pm.me.invalid> wrote:
> > But I found out very quickly that I won't be able to... using only
> Apache Arrow without resorting to other libraries.
>
> > I am aiming to assess the viability of Apache Arrow for graph algorithms
> and data structures...
>
> > I also gave a shot at doing it similar to a certain SQL method...
>
> I'm curious about these portions of what you've said.
>
> Could you share what you have tried and what roadblocks you're hitting?
> Are you struggling with mutability? How are you representing your data? You
> mention heapq, but it's not clear if you're using an adjacency matrix or
> adjacency lists or if you're using a more normalized relational format.
>
> Thanks!
>
>
> # ------------------------------
>
> # Aldrin
>
>
> https://github.com/drin/
>
> https://gitlab.com/octalene
>
> https://keybase.io/octalene
Re: Apache Arrow | Graph Algorithms & Data Structures
Posted by Aldrin <oc...@pm.me.INVALID>.
> But I found out very quickly that I won't be able to... using only Apache Arrow without resorting to other libraries.
> I am aiming to assess the viability of Apache Arrow for graph algorithms and data structures...
> I also gave a shot at doing it similar to a certain SQL method...
I'm curious about these portions of what you've said.
Could you share what you have tried and what roadblocks you're hitting? Are you struggling with mutability? How are you representing your data? You mention heapq, but it's not clear if you're using an adjacency matrix or adjacency lists or if you're using a more normalized relational format.
Thanks!
# ------------------------------
# Aldrin
https://github.com/drin/
https://gitlab.com/octalene
https://keybase.io/octalene
Re: Apache Arrow | Graph Algorithms & Data Structures
Posted by Adam Lippai <ad...@rigo.sk>.
Hi Bechir,
GraphBlas is mainly an interface, a list of functions.
This is similar to how BLAS is implemented by OpenBlas and MKL.
Gabor Szárnyas has a great collection on how they are implanted and how
they perform:
https://github.com/GraphBLAS/GraphBLAS-Pointers
Best regards,
Adam Lippai
On Fri, Jun 30, 2023 at 08:04 Bechir Ben Daadouch <be...@gmail.com>
wrote:
> Hey Adam,
>
> Thank you very much for taking the time to respond and for the suggestions
> :)
>
> I am aiming to assess the viability of Apache Arrow for graph algorithms
> and data structures, rather than addressing a particular issue. I am
> interested to determine the extent to which I can utilize Apache Arrow for
> this purpose and what potential challenges may arise.
>
> and since I have already encountered some roadblocks early on in my
> evaluation of Apache Arrow for graph algorithms and data structures, I am
> very interested in hearing your point of view on this topic.
>
> Thanks,
> Bechir
>
> On Fri, Jun 30, 2023, 13:38 Adam Lippai <ad...@rigo.sk> wrote:
>
> > Hi,
> >
> > I’d recommend integrating with GraphBlas/suitesparse which are sparse
> > matrix multiplication based algorithms for common graph problems. There
> > might be an overlap in the data structures used, eg creating and a new
> > arrow type like the recent tensor type addition, or simply creating zero
> > copy or memcopy based efficient converters would be something worth
> > exploring.
> >
> > Best regards,
> > Adam alippai
> >
> > On Fri, Jun 30, 2023 at 06:57 Bechir Ben Daadouch <
> bechirchepti@gmail.com>
> > wrote:
> >
> > > Thank you for taking the time to answer :)
> > >
> > > I don't have a fix Use-Case, but I am trying yo build a POC and
> evaluate
> > > whether Apache Arrow could be adequate in the context of graphs. But I
> > > found out very quickly that I won't be able to do all the necessary
> > > algorithm steps using only Apache Arrow without resorting to other
> > > libraries.
> > >
> > > On Fri, Jun 30, 2023, 07:36 Benson Muite <be...@emailplus.org>
> > > wrote:
> > >
> > > > On 6/30/23 04:21, Bechir Ben Daadouch wrote:
> > > > > Dear Apache Arrow Dev Community,
> > > > >
> > > > > My name is Bechir, I am currently working on a project that
> involves
> > > > > implementing graph algorithms in Apache Arrow.
> > > > >
> > > > > The initial plan was to construct a node structure and a subsequent
> > > graph
> > > > > that would encompass all the nodes. However, I quickly realized
> that
> > > due
> > > > to
> > > > > Apache Arrow's columnar format, this approach was not feasible.
> > > > >
> > > > > I tried a couple of things, including the implementation of the
> > > > > shortest-path algorithm. However, I rapidly discovered that
> > > manipulating
> > > > > arrow objects, particularly when applying graph algorithms, proved
> > more
> > > > > complex than anticipated and it became very clear that I would need
> > to
> > > > > resort to some data structures outside of what arrow offers (i.e.:
> > > Heapq
> > > > > wouldn't be possible using arrow).
> > > > >
> > > > > I also gave a shot at doing it similar to a certain SQL method
> (see:
> > > > > https://ibb.co/0rPGB42 ), but ran into some roadblocks there too
> > and I
> > > > > ended up having to resort to using Pandas for some transformations.
> > > > >
> > > > > My next course of action is to experiment with compressed sparse
> > rows,
> > > > > hoping to execute Matrix Multiplication using this method. But
> > > honestly,
> > > > > with what I know right now, I remain skeptical about the
> feasibility
> > > > > of it. However,
> > > > > before committing to this approach, I would greatly appreciate your
> > > > opinion
> > > > > based on your experience with Apache Arrow.
> > > > >
> > > > > Thank you very much for your time.
> > > > >
> > > > > Looking forward to potentially discussing this further.
> > > > >
> > > > > Many thanks,
> > > > > Bechir
> > > > >
> > > > Arrow may not be the best choice for most graph algorithms as they
> > > > typically require random memory accesses that will be difficult to
> > > > coalesce into forms that allow for vectorization. If your data will
> fit
> > > > in memory of a single node, you might consider:
> > > > https://github.com/DrTimothyAldenDavis/GraphBLAS
> > > > https://pypi.org/project/python-graphblas/
> > > > https://github.com/JuliaSparse/SuiteSparseGraphBLAS.jl
> > > >
> > >
> >
>
Re: Apache Arrow | Graph Algorithms & Data Structures
Posted by Bechir Ben Daadouch <be...@gmail.com>.
Hey Adam,
Thank you very much for taking the time to respond and for the suggestions
:)
I am aiming to assess the viability of Apache Arrow for graph algorithms
and data structures, rather than addressing a particular issue. I am
interested to determine the extent to which I can utilize Apache Arrow for
this purpose and what potential challenges may arise.
and since I have already encountered some roadblocks early on in my
evaluation of Apache Arrow for graph algorithms and data structures, I am
very interested in hearing your point of view on this topic.
Thanks,
Bechir
On Fri, Jun 30, 2023, 13:38 Adam Lippai <ad...@rigo.sk> wrote:
> Hi,
>
> I’d recommend integrating with GraphBlas/suitesparse which are sparse
> matrix multiplication based algorithms for common graph problems. There
> might be an overlap in the data structures used, eg creating and a new
> arrow type like the recent tensor type addition, or simply creating zero
> copy or memcopy based efficient converters would be something worth
> exploring.
>
> Best regards,
> Adam alippai
>
> On Fri, Jun 30, 2023 at 06:57 Bechir Ben Daadouch <be...@gmail.com>
> wrote:
>
> > Thank you for taking the time to answer :)
> >
> > I don't have a fix Use-Case, but I am trying yo build a POC and evaluate
> > whether Apache Arrow could be adequate in the context of graphs. But I
> > found out very quickly that I won't be able to do all the necessary
> > algorithm steps using only Apache Arrow without resorting to other
> > libraries.
> >
> > On Fri, Jun 30, 2023, 07:36 Benson Muite <be...@emailplus.org>
> > wrote:
> >
> > > On 6/30/23 04:21, Bechir Ben Daadouch wrote:
> > > > Dear Apache Arrow Dev Community,
> > > >
> > > > My name is Bechir, I am currently working on a project that involves
> > > > implementing graph algorithms in Apache Arrow.
> > > >
> > > > The initial plan was to construct a node structure and a subsequent
> > graph
> > > > that would encompass all the nodes. However, I quickly realized that
> > due
> > > to
> > > > Apache Arrow's columnar format, this approach was not feasible.
> > > >
> > > > I tried a couple of things, including the implementation of the
> > > > shortest-path algorithm. However, I rapidly discovered that
> > manipulating
> > > > arrow objects, particularly when applying graph algorithms, proved
> more
> > > > complex than anticipated and it became very clear that I would need
> to
> > > > resort to some data structures outside of what arrow offers (i.e.:
> > Heapq
> > > > wouldn't be possible using arrow).
> > > >
> > > > I also gave a shot at doing it similar to a certain SQL method (see:
> > > > https://ibb.co/0rPGB42 ), but ran into some roadblocks there too
> and I
> > > > ended up having to resort to using Pandas for some transformations.
> > > >
> > > > My next course of action is to experiment with compressed sparse
> rows,
> > > > hoping to execute Matrix Multiplication using this method. But
> > honestly,
> > > > with what I know right now, I remain skeptical about the feasibility
> > > > of it. However,
> > > > before committing to this approach, I would greatly appreciate your
> > > opinion
> > > > based on your experience with Apache Arrow.
> > > >
> > > > Thank you very much for your time.
> > > >
> > > > Looking forward to potentially discussing this further.
> > > >
> > > > Many thanks,
> > > > Bechir
> > > >
> > > Arrow may not be the best choice for most graph algorithms as they
> > > typically require random memory accesses that will be difficult to
> > > coalesce into forms that allow for vectorization. If your data will fit
> > > in memory of a single node, you might consider:
> > > https://github.com/DrTimothyAldenDavis/GraphBLAS
> > > https://pypi.org/project/python-graphblas/
> > > https://github.com/JuliaSparse/SuiteSparseGraphBLAS.jl
> > >
> >
>
Re: Apache Arrow | Graph Algorithms & Data Structures
Posted by Adam Lippai <ad...@rigo.sk>.
Hi,
I’d recommend integrating with GraphBlas/suitesparse which are sparse
matrix multiplication based algorithms for common graph problems. There
might be an overlap in the data structures used, eg creating and a new
arrow type like the recent tensor type addition, or simply creating zero
copy or memcopy based efficient converters would be something worth
exploring.
Best regards,
Adam alippai
On Fri, Jun 30, 2023 at 06:57 Bechir Ben Daadouch <be...@gmail.com>
wrote:
> Thank you for taking the time to answer :)
>
> I don't have a fix Use-Case, but I am trying yo build a POC and evaluate
> whether Apache Arrow could be adequate in the context of graphs. But I
> found out very quickly that I won't be able to do all the necessary
> algorithm steps using only Apache Arrow without resorting to other
> libraries.
>
> On Fri, Jun 30, 2023, 07:36 Benson Muite <be...@emailplus.org>
> wrote:
>
> > On 6/30/23 04:21, Bechir Ben Daadouch wrote:
> > > Dear Apache Arrow Dev Community,
> > >
> > > My name is Bechir, I am currently working on a project that involves
> > > implementing graph algorithms in Apache Arrow.
> > >
> > > The initial plan was to construct a node structure and a subsequent
> graph
> > > that would encompass all the nodes. However, I quickly realized that
> due
> > to
> > > Apache Arrow's columnar format, this approach was not feasible.
> > >
> > > I tried a couple of things, including the implementation of the
> > > shortest-path algorithm. However, I rapidly discovered that
> manipulating
> > > arrow objects, particularly when applying graph algorithms, proved more
> > > complex than anticipated and it became very clear that I would need to
> > > resort to some data structures outside of what arrow offers (i.e.:
> Heapq
> > > wouldn't be possible using arrow).
> > >
> > > I also gave a shot at doing it similar to a certain SQL method (see:
> > > https://ibb.co/0rPGB42 ), but ran into some roadblocks there too and I
> > > ended up having to resort to using Pandas for some transformations.
> > >
> > > My next course of action is to experiment with compressed sparse rows,
> > > hoping to execute Matrix Multiplication using this method. But
> honestly,
> > > with what I know right now, I remain skeptical about the feasibility
> > > of it. However,
> > > before committing to this approach, I would greatly appreciate your
> > opinion
> > > based on your experience with Apache Arrow.
> > >
> > > Thank you very much for your time.
> > >
> > > Looking forward to potentially discussing this further.
> > >
> > > Many thanks,
> > > Bechir
> > >
> > Arrow may not be the best choice for most graph algorithms as they
> > typically require random memory accesses that will be difficult to
> > coalesce into forms that allow for vectorization. If your data will fit
> > in memory of a single node, you might consider:
> > https://github.com/DrTimothyAldenDavis/GraphBLAS
> > https://pypi.org/project/python-graphblas/
> > https://github.com/JuliaSparse/SuiteSparseGraphBLAS.jl
> >
>
Re: Apache Arrow | Graph Algorithms & Data Structures
Posted by Bechir Ben Daadouch <be...@gmail.com>.
Thank you for taking the time to answer :)
I don't have a fix Use-Case, but I am trying yo build a POC and evaluate
whether Apache Arrow could be adequate in the context of graphs. But I
found out very quickly that I won't be able to do all the necessary
algorithm steps using only Apache Arrow without resorting to other
libraries.
On Fri, Jun 30, 2023, 07:36 Benson Muite <be...@emailplus.org> wrote:
> On 6/30/23 04:21, Bechir Ben Daadouch wrote:
> > Dear Apache Arrow Dev Community,
> >
> > My name is Bechir, I am currently working on a project that involves
> > implementing graph algorithms in Apache Arrow.
> >
> > The initial plan was to construct a node structure and a subsequent graph
> > that would encompass all the nodes. However, I quickly realized that due
> to
> > Apache Arrow's columnar format, this approach was not feasible.
> >
> > I tried a couple of things, including the implementation of the
> > shortest-path algorithm. However, I rapidly discovered that manipulating
> > arrow objects, particularly when applying graph algorithms, proved more
> > complex than anticipated and it became very clear that I would need to
> > resort to some data structures outside of what arrow offers (i.e.: Heapq
> > wouldn't be possible using arrow).
> >
> > I also gave a shot at doing it similar to a certain SQL method (see:
> > https://ibb.co/0rPGB42 ), but ran into some roadblocks there too and I
> > ended up having to resort to using Pandas for some transformations.
> >
> > My next course of action is to experiment with compressed sparse rows,
> > hoping to execute Matrix Multiplication using this method. But honestly,
> > with what I know right now, I remain skeptical about the feasibility
> > of it. However,
> > before committing to this approach, I would greatly appreciate your
> opinion
> > based on your experience with Apache Arrow.
> >
> > Thank you very much for your time.
> >
> > Looking forward to potentially discussing this further.
> >
> > Many thanks,
> > Bechir
> >
> Arrow may not be the best choice for most graph algorithms as they
> typically require random memory accesses that will be difficult to
> coalesce into forms that allow for vectorization. If your data will fit
> in memory of a single node, you might consider:
> https://github.com/DrTimothyAldenDavis/GraphBLAS
> https://pypi.org/project/python-graphblas/
> https://github.com/JuliaSparse/SuiteSparseGraphBLAS.jl
>
Re: Apache Arrow | Graph Algorithms & Data Structures
Posted by Benson Muite <be...@emailplus.org>.
On 6/30/23 04:21, Bechir Ben Daadouch wrote:
> Dear Apache Arrow Dev Community,
>
> My name is Bechir, I am currently working on a project that involves
> implementing graph algorithms in Apache Arrow.
>
> The initial plan was to construct a node structure and a subsequent graph
> that would encompass all the nodes. However, I quickly realized that due to
> Apache Arrow's columnar format, this approach was not feasible.
>
> I tried a couple of things, including the implementation of the
> shortest-path algorithm. However, I rapidly discovered that manipulating
> arrow objects, particularly when applying graph algorithms, proved more
> complex than anticipated and it became very clear that I would need to
> resort to some data structures outside of what arrow offers (i.e.: Heapq
> wouldn't be possible using arrow).
>
> I also gave a shot at doing it similar to a certain SQL method (see:
> https://ibb.co/0rPGB42 ), but ran into some roadblocks there too and I
> ended up having to resort to using Pandas for some transformations.
>
> My next course of action is to experiment with compressed sparse rows,
> hoping to execute Matrix Multiplication using this method. But honestly,
> with what I know right now, I remain skeptical about the feasibility
> of it. However,
> before committing to this approach, I would greatly appreciate your opinion
> based on your experience with Apache Arrow.
>
> Thank you very much for your time.
>
> Looking forward to potentially discussing this further.
>
> Many thanks,
> Bechir
>
Arrow may not be the best choice for most graph algorithms as they
typically require random memory accesses that will be difficult to
coalesce into forms that allow for vectorization. If your data will fit
in memory of a single node, you might consider:
https://github.com/DrTimothyAldenDavis/GraphBLAS
https://pypi.org/project/python-graphblas/
https://github.com/JuliaSparse/SuiteSparseGraphBLAS.jl