silk-graph 0.2.4

Merkle-CRDT graph engine for distributed, conflict-free knowledge graphs
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215

"""Silk GraphStore — Python tests for graph queries and engine algorithms."""

import json

import pytest

from silk import GraphStore

ONTOLOGY = json.dumps(
    {
        "node_types": {
            "entity": {"properties": {"status": {"value_type": "string", "required": False}}},
            "signal": {"properties": {}},
            "source": {"properties": {}},
            "processor": {"properties": {}},
            "queue": {"properties": {}},
            "sink": {"properties": {}},
        },
        "edge_types": {
            "DEPENDS_ON": {
                "source_types": ["entity"],
                "target_types": ["entity"],
                "properties": {},
            },
            "FEEDS": {
                "source_types": ["source"],
                "target_types": ["processor"],
                "properties": {},
            },
            "ROUTES": {
                "source_types": ["processor", "queue", "sink"],
                "target_types": ["queue", "sink", "source"],
                "properties": {},
            },
        },
    }
)


class TestGraphQueries:
    """Tests for materialized graph query API."""

    def test_get_node(self):
        store = GraphStore("inst-1", ONTOLOGY)
        store.add_node("s1", "entity", "Server 1", {"status": "alive"})
        node = store.get_node("s1")
        assert node is not None
        assert node["node_id"] == "s1"
        assert node["node_type"] == "entity"
        assert node["label"] == "Server 1"
        assert node["properties"]["status"] == "alive"

    def test_get_node_not_found(self):
        store = GraphStore("inst-1", ONTOLOGY)
        assert store.get_node("nonexistent") is None

    def test_get_edge(self):
        store = GraphStore("inst-1", ONTOLOGY)
        store.add_node("a", "entity", "A")
        store.add_node("b", "entity", "B")
        store.add_edge("e1", "DEPENDS_ON", "a", "b")
        edge = store.get_edge("e1")
        assert edge is not None
        assert edge["edge_type"] == "DEPENDS_ON"
        assert edge["source_id"] == "a"
        assert edge["target_id"] == "b"

    def test_query_by_type(self):
        store = GraphStore("inst-1", ONTOLOGY)
        store.add_node("s1", "entity", "S1")
        store.add_node("s2", "entity", "S2")
        store.add_node("src1", "source", "Source 1")
        entities = store.query_nodes_by_type("entity")
        assert len(entities) == 2
        sources = store.query_nodes_by_type("source")
        assert len(sources) == 1

    def test_query_by_property(self):
        store = GraphStore("inst-1", ONTOLOGY)
        store.add_node("s1", "entity", "S1", {"status": "alive"})
        store.add_node("s2", "entity", "S2", {"status": "dead"})
        alive = store.query_nodes_by_property("status", "alive")
        assert len(alive) == 1
        assert alive[0]["node_id"] == "s1"

    def test_all_nodes_excludes_removed(self):
        store = GraphStore("inst-1", ONTOLOGY)
        store.add_node("s1", "entity", "S1")
        store.add_node("s2", "entity", "S2")
        assert len(store.all_nodes()) == 2
        store.remove_node("s1")
        assert len(store.all_nodes()) == 1

    def test_all_edges_excludes_dangling(self):
        store = GraphStore("inst-1", ONTOLOGY)
        store.add_node("a", "entity", "A")
        store.add_node("b", "entity", "B")
        store.add_edge("e1", "DEPENDS_ON", "a", "b")
        assert len(store.all_edges()) == 1
        store.remove_node("b")
        # Edge still exists in oplog but invisible (dangling target).
        assert len(store.all_edges()) == 0

    def test_neighbors(self):
        store = GraphStore("inst-1", ONTOLOGY)
        store.add_node("a", "entity", "A")
        store.add_node("b", "entity", "B")
        store.add_node("c", "entity", "C")
        store.add_edge("ab", "DEPENDS_ON", "a", "b")
        store.add_edge("ac", "DEPENDS_ON", "a", "c")
        neighbors = store.neighbors("a")
        assert set(neighbors) == {"b", "c"}

    def test_outgoing_incoming_edges(self):
        store = GraphStore("inst-1", ONTOLOGY)
        store.add_node("a", "entity", "A")
        store.add_node("b", "entity", "B")
        store.add_edge("e1", "DEPENDS_ON", "a", "b")
        out = store.outgoing_edges("a")
        assert len(out) == 1
        assert out[0]["target_id"] == "b"
        inc = store.incoming_edges("b")
        assert len(inc) == 1
        assert inc[0]["source_id"] == "a"


class TestEngine:
    """Tests for graph algorithms exposed via Python."""

    def _build_chain(self):
        """A → B → C → D"""
        store = GraphStore("inst-1", ONTOLOGY)
        store.add_node("a", "entity", "A")
        store.add_node("b", "entity", "B")
        store.add_node("c", "entity", "C")
        store.add_node("d", "entity", "D")
        store.add_edge("ab", "DEPENDS_ON", "a", "b")
        store.add_edge("bc", "DEPENDS_ON", "b", "c")
        store.add_edge("cd", "DEPENDS_ON", "c", "d")
        return store

    def test_bfs(self):
        store = self._build_chain()
        visited = store.bfs("a")
        assert visited == ["a", "b", "c", "d"]

    def test_bfs_depth_limit(self):
        store = self._build_chain()
        visited = store.bfs("a", max_depth=2)
        assert visited == ["a", "b", "c"]

    def test_bfs_edge_type_filter(self):
        store = self._build_chain()
        visited = store.bfs("a", edge_type="NONEXISTENT")
        assert visited == ["a"]  # only start node

    def test_shortest_path(self):
        store = self._build_chain()
        path = store.shortest_path("a", "d")
        assert path == ["a", "b", "c", "d"]

    def test_shortest_path_no_path(self):
        store = GraphStore("inst-1", ONTOLOGY)
        store.add_node("a", "entity", "A")
        store.add_node("b", "entity", "B")
        assert store.shortest_path("a", "b") is None

    def test_impact_analysis(self):
        store = self._build_chain()
        impact = store.impact_analysis("d")
        assert set(impact) == {"a", "b", "c", "d"}

    def test_subgraph(self):
        store = self._build_chain()
        result = store.subgraph("b", 1)
        assert "b" in result["nodes"]
        assert "a" in result["nodes"]
        assert "c" in result["nodes"]
        assert "d" not in result["nodes"]

    def test_pattern_match(self):
        store = GraphStore("inst-1", ONTOLOGY)
        store.add_node("src1", "source", "Data Source")
        store.add_node("proc1", "processor", "Processor 1")
        store.add_node("q1", "queue", "Queue 1")
        store.add_node("snk1", "sink", "Sink 1")
        store.add_edge("e1", "FEEDS", "src1", "proc1")
        store.add_edge("e2", "ROUTES", "proc1", "q1")
        store.add_edge("e3", "ROUTES", "q1", "snk1")
        chains = store.pattern_match(["source", "processor", "queue", "sink"])
        assert len(chains) == 1
        assert chains[0] == ["src1", "proc1", "q1", "snk1"]

    def test_topological_sort(self):
        store = self._build_chain()
        order = store.topological_sort()
        assert order is not None
        assert order.index("a") < order.index("b")
        assert order.index("b") < order.index("c")
        assert order.index("c") < order.index("d")

    def test_cycle_detection(self):
        store = GraphStore("inst-1", ONTOLOGY)
        store.add_node("a", "entity", "A")
        store.add_node("b", "entity", "B")
        store.add_node("c", "entity", "C")
        store.add_edge("ab", "DEPENDS_ON", "a", "b")
        store.add_edge("bc", "DEPENDS_ON", "b", "c")
        store.add_edge("ca", "DEPENDS_ON", "c", "a")
        assert store.has_cycle() is True
        assert store.topological_sort() is None

    def test_no_cycle(self):
        store = self._build_chain()
        assert store.has_cycle() is False