Packages
graph

0.1.0
1.0.1 1.0.0 0.1.0
Directed and undirected graphs
HexDocs
Current section
Files
Jump to
Readme 3 Versions 1 Dependency Dependants Files Activity
graph src graph.erl
Raw
src/graph.erl

-module(graph).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch]).

-export([new/0, nodes/1, size/1, has_node/2, get_context/2, has_edge/3, insert_node/2, insert_directed_edge/4, insert_undirected_edge/4, remove_directed_edge/3, remove_undirected_edge/3, fold/3, map_contexts/2, map_values/2, map_labels/2, reverse_edges/1, to_directed/1, remove_node/2, match/2]).
-export_type([directed/0, undirected/0, graph/3, node_/1, context/2]).

-type directed() :: any().

-type undirected() :: any().

-opaque graph(FJS, FJT, FJU) :: {graph,
        gleam@dict:dict(integer(), context(FJT, FJU))} |
    {gleam_phantom, FJS}.

-type node_(FJV) :: {node, integer(), FJV}.

-type context(FJW, FJX) :: {context,
        gleam@dict:dict(integer(), FJX),
        node_(FJW),
        gleam@dict:dict(integer(), FJX)}.

-spec new() -> graph(any(), any(), any()).
new() ->
    {graph, gleam@dict:new()}.

-spec nodes(graph(any(), FKF, any())) -> list(node_(FKF)).
nodes(Graph) ->
    {graph, Graph@1} = Graph,
    gleam@dict:fold(
        Graph@1,
        [],
        fun(Acc, _, _use2) ->
            {context, _, Node, _} = _use2,
            [Node | Acc]
        end
    ).

-spec size(graph(any(), any(), any())) -> integer().
size(Graph) ->
    {graph, Graph@1} = Graph,
    maps:size(Graph@1).

-spec has_node(graph(any(), any(), any()), integer()) -> boolean().
has_node(Graph, Node_id) ->
    {graph, Graph@1} = Graph,
    gleam@dict:has_key(Graph@1, Node_id).

-spec get_context(graph(any(), FLF, FLG), integer()) -> {ok, context(FLF, FLG)} |
    {error, nil}.
get_context(Graph, Node) ->
    {graph, Graph@1} = Graph,
    gleam@dict:get(Graph@1, Node).

-spec has_edge(graph(any(), any(), any()), integer(), integer()) -> boolean().
has_edge(Graph, Source, Destination) ->
    case get_context(Graph, Source) of
        {ok, {context, _, _, Outgoing}} ->
            gleam@dict:has_key(Outgoing, Destination);

        {error, _} ->
            false
    end.

-spec insert_node(graph(FMB, FMC, FMD), node_(FMC)) -> graph(FMB, FMC, FMD).
insert_node(Graph, Node) ->
    {graph, Graph@1} = Graph,
    Empty_context = {context, gleam@dict:new(), Node, gleam@dict:new()},
    New_graph = gleam@dict:insert(
        Graph@1,
        erlang:element(2, Node),
        Empty_context
    ),
    {graph, New_graph}.

-spec update_context(
    graph(FNB, FNC, FND),
    integer(),
    fun((context(FNC, FND)) -> context(FNC, FND))
) -> graph(FNB, FNC, FND).
update_context(Graph, Node, Fun) ->
    {graph, Graph@1} = Graph,
    case gleam@dict:get(Graph@1, Node) of
        {ok, Context} ->
            {graph, gleam@dict:insert(Graph@1, Node, Fun(Context))};

        {error, _} ->
            {graph, Graph@1}
    end.

-spec add_outgoing_edge(context(FNO, FNP), integer(), FNP) -> context(FNO, FNP).
add_outgoing_edge(Context, Node, Label) ->
    {context, _, _, Outgoing} = Context,
    erlang:setelement(4, Context, gleam@dict:insert(Outgoing, Node, Label)).

-spec remove_outgoing_edge(context(FNU, FNV), integer()) -> context(FNU, FNV).
remove_outgoing_edge(Context, Node) ->
    {context, _, _, Outgoing} = Context,
    erlang:setelement(4, Context, gleam@dict:delete(Outgoing, Node)).

-spec add_incoming_edge(context(FOA, FOB), integer(), FOB) -> context(FOA, FOB).
add_incoming_edge(Context, Node, Label) ->
    {context, Incoming, _, _} = Context,
    erlang:setelement(2, Context, gleam@dict:insert(Incoming, Node, Label)).

-spec insert_directed_edge(
    graph(directed(), FML, FMM),
    FMM,
    integer(),
    integer()
) -> graph(directed(), FML, FMM).
insert_directed_edge(Graph, Label, Source, Destination) ->
    _pipe = Graph,
    _pipe@1 = update_context(
        _pipe,
        Source,
        fun(_capture) -> add_outgoing_edge(_capture, Destination, Label) end
    ),
    update_context(
        _pipe@1,
        Destination,
        fun(_capture@1) -> add_incoming_edge(_capture@1, Source, Label) end
    ).

-spec insert_undirected_edge(
    graph(undirected(), FMT, FMU),
    FMU,
    integer(),
    integer()
) -> graph(undirected(), FMT, FMU).
insert_undirected_edge(Graph, Label, One, Other) ->
    _pipe = Graph,
    _pipe@2 = update_context(
        _pipe,
        One,
        fun(Context) -> _pipe@1 = add_outgoing_edge(Context, Other, Label),
            add_incoming_edge(_pipe@1, Other, Label) end
    ),
    update_context(
        _pipe@2,
        Other,
        fun(Context@1) -> _pipe@3 = add_outgoing_edge(Context@1, One, Label),
            add_incoming_edge(_pipe@3, One, Label) end
    ).

-spec remove_incoming_edge(context(FOG, FOH), integer()) -> context(FOG, FOH).
remove_incoming_edge(Context, Node) ->
    {context, Incoming, _, _} = Context,
    erlang:setelement(2, Context, gleam@dict:delete(Incoming, Node)).

-spec remove_directed_edge(graph(directed(), FPV, FPW), integer(), integer()) -> graph(directed(), FPV, FPW).
remove_directed_edge(Graph, Source, Destination) ->
    _pipe = Graph,
    _pipe@1 = update_context(
        _pipe,
        Source,
        fun(_capture) -> remove_outgoing_edge(_capture, Destination) end
    ),
    update_context(
        _pipe@1,
        Destination,
        fun(_capture@1) -> remove_incoming_edge(_capture@1, Source) end
    ).

-spec remove_undirected_edge(
    graph(undirected(), FQD, FQE),
    integer(),
    integer()
) -> graph(undirected(), FQD, FQE).
remove_undirected_edge(Graph, One, Other) ->
    _pipe = Graph,
    _pipe@2 = update_context(
        _pipe,
        One,
        fun(Context) -> _pipe@1 = remove_outgoing_edge(Context, Other),
            remove_incoming_edge(_pipe@1, Other) end
    ),
    update_context(
        _pipe@2,
        Other,
        fun(Context@1) -> _pipe@3 = remove_outgoing_edge(Context@1, One),
            remove_incoming_edge(_pipe@3, One) end
    ).

-spec fold(graph(any(), FQM, FQN), FQR, fun((FQR, context(FQM, FQN)) -> FQR)) -> FQR.
fold(Graph, Initial, Fun) ->
    {graph, Graph@1} = Graph,
    gleam@dict:fold(
        Graph@1,
        Initial,
        fun(Acc, _, Context) -> Fun(Acc, Context) end
    ).

-spec insert_context(graph(any(), FRI, FRJ), context(FRI, FRJ)) -> graph(directed(), FRI, FRJ).
insert_context(Graph, Context) ->
    {graph, Graph@1} = Graph,
    New_graph = gleam@dict:insert(
        Graph@1,
        erlang:element(2, erlang:element(3, Context)),
        Context
    ),
    {graph, New_graph}.

-spec map_contexts(
    graph(any(), FQV, FQW),
    fun((context(FQV, FQW)) -> context(FQV, FQW))
) -> graph(directed(), FQV, FQW).
map_contexts(Graph, Fun) ->
    fold(
        Graph,
        new(),
        fun(Acc, Context) -> insert_context(Acc, Fun(Context)) end
    ).

-spec map_values(graph(FRS, FRT, FRU), fun((FRT) -> FRY)) -> graph(FRS, FRY, FRU).
map_values(Graph, Fun) ->
    {graph, Graph@1} = Graph,
    {graph,
        (gleam@dict:map_values(
            Graph@1,
            fun(_, Context) ->
                {context, Incoming, {node, Id, Value}, Outgoing} = Context,
                {context, Incoming, {node, Id, Fun(Value)}, Outgoing}
            end
        ))}.

-spec map_labels(graph(FSC, FSD, FSE), fun((FSE) -> FSI)) -> graph(FSC, FSD, FSI).
map_labels(Graph, Fun) ->
    {graph, Graph@1} = Graph,
    {graph,
        (gleam@dict:map_values(
            Graph@1,
            fun(_, Context) ->
                {context, Incoming, Node, Outgoing} = Context,
                New_incoming = gleam@dict:map_values(
                    Incoming,
                    fun(_, Label) -> Fun(Label) end
                ),
                New_outgoing = gleam@dict:map_values(
                    Outgoing,
                    fun(_, Label@1) -> Fun(Label@1) end
                ),
                {context, New_incoming, Node, New_outgoing}
            end
        ))}.

-spec reverse_edges(graph(directed(), FSM, FSN)) -> graph(directed(), FSM, FSN).
reverse_edges(Graph) ->
    {graph, Graph@1} = Graph,
    {graph,
        (gleam@dict:map_values(
            Graph@1,
            fun(_, Context) ->
                {context, Incoming, Node, Outgoing} = Context,
                {context, Outgoing, Node, Incoming}
            end
        ))}.

-spec to_directed(graph(undirected(), FSU, FSV)) -> graph(directed(), FSU, FSV).
to_directed(Graph) ->
    {graph, Graph@1} = Graph,
    {graph, Graph@1}.

-spec dict_map_shared_keys(
    gleam@dict:dict(FTC, FTD),
    gleam@dict:dict(FTC, FTG),
    fun((FTD, FTG) -> FTD)
) -> gleam@dict:dict(FTC, FTD).
dict_map_shared_keys(One, Other, Fun) ->
    gleam@dict:fold(
        Other,
        One,
        fun(One@1, Key, Other_value) -> case gleam@dict:get(One@1, Key) of
                {ok, One_value} ->
                    gleam@dict:insert(One@1, Key, Fun(One_value, Other_value));

                {error, _} ->
                    One@1
            end end
    ).

-spec remove_incoming_occurrences(
    gleam@dict:dict(integer(), context(FOV, FOW)),
    integer(),
    gleam@dict:dict(integer(), any())
) -> gleam@dict:dict(integer(), context(FOV, FOW)).
remove_incoming_occurrences(Graph, Node, Nodes) ->
    dict_map_shared_keys(
        Graph,
        Nodes,
        fun(Context, _) ->
            {context, Incoming, _, _} = Context,
            erlang:setelement(2, Context, gleam@dict:delete(Incoming, Node))
        end
    ).

-spec remove_outgoing_occurrences(
    gleam@dict:dict(integer(), context(FPI, FPJ)),
    integer(),
    gleam@dict:dict(integer(), any())
) -> gleam@dict:dict(integer(), context(FPI, FPJ)).
remove_outgoing_occurrences(Graph, Node, Nodes) ->
    dict_map_shared_keys(
        Graph,
        Nodes,
        fun(Context, _) ->
            {context, _, _, Outgoing} = Context,
            erlang:setelement(4, Context, gleam@dict:delete(Outgoing, Node))
        end
    ).

-spec remove_node(graph(FOM, FON, FOO), integer()) -> graph(FOM, FON, FOO).
remove_node(Graph, Node_id) ->
    case {Graph, get_context(Graph, Node_id)} of
        {_, {error, _}} ->
            Graph;

        {{graph, Graph@1}, {ok, {context, Incoming, _, Outgoing}}} ->
            _pipe = gleam@dict:delete(Graph@1, Node_id),
            _pipe@1 = remove_incoming_occurrences(_pipe, Node_id, Outgoing),
            _pipe@2 = remove_outgoing_occurrences(_pipe@1, Node_id, Incoming),
            {graph, _pipe@2}
    end.

-spec match(graph(FLO, FLP, FLQ), integer()) -> {ok,
        {context(FLP, FLQ), graph(FLO, FLP, FLQ)}} |
    {error, nil}.
match(Graph, Node_id) ->
    gleam@result:'try'(
        get_context(Graph, Node_id),
        fun(_use0) ->
            {context, Incoming, Node, Outgoing} = _use0,
            Rest = remove_node(Graph, Node_id),
            New_incoming = gleam@dict:delete(Incoming, Node_id),
            New_outgoing = gleam@dict:delete(Outgoing, Node_id),
            {ok, {{context, New_incoming, Node, New_outgoing}, Rest}}
        end
    ).
Operator	Description	Example
name:	Match package name. Supports * wildcards and repo/package form	name:phx* or name:hexpm/phoenix
description:	Full-text search of package descriptions	description:auth
depends:	Packages depending on a given package. Supports repo:package form	depends:ecto or depends:hexpm:ecto
build_tool:	Filter by build tool	build_tool:mix
updated_after:	Packages updated after an ISO8601 datetime	updated_after:2025-01-01T00:00:00Z
extra:	Match custom metadata (key,value). Nested keys are separated by commas	extra:license,MIT