{
"cells": [
{
"cell_type": "markdown",
"id": "2ef97eb3-0f34-4d18-8b2c-429e84db9991",
"metadata": {},
"source": [
"# heterograph: graph operations"
]
},
{
"cell_type": "markdown",
"id": "0301c00d-b615-4677-92a1-d5d4db617a15",
"metadata": {},
"source": [
"## neighbour ordering\n",
"\n",
"When capturing programming models, it is often crucial to preserve the order of incoming or outgoing edges. For example, maintaining the order is essential for parameter lists or statement lists. When using `add_edge`, the insertion order determines the neighbor ordering.\n",
"\n",
"### implicit ordering"
]
},
{
"cell_type": "code",
"execution_count": 1,
"id": "6b7bb227-6f08-488f-bdce-5dce671fed8a",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[3, 1, 2]"
]
},
"execution_count": 1,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"from heterograph import *\n",
"g = HGraph()\n",
"g.add_vx(4)\n",
"g.add_edge(0, [3, 1, 2])\n",
"g.out_vx(0)"
]
},
{
"cell_type": "markdown",
"id": "d941ccd7-7147-4a3f-bb4f-2b135ab48b1e",
"metadata": {},
"source": [
"### custom ordering\n",
"\n",
"The methods `in_vx(vx)` and `out_vx(vx)` include three optional parameters to configure the ordering:\n",
"\n",
"- `order` (list of int): A list of vertex IDs specifying the desired order. This list can be a subset of the neighbors.\n",
"- `anchor` (int, default: None): A vertex ID indicating where to insert the subset provided in `order`. If the anchor is `None`, the subset is inserted at the end of the list.\n",
"- `after` (bool, default: True): Determines whether to insert the sublist before or after the anchor."
]
},
{
"cell_type": "code",
"execution_count": 2,
"id": "61badbe0-3fef-4219-af35-b17b21d3f6a7",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[1, 2, 3, 4]"
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"g=HGraph()\n",
"g.add_vx(5)\n",
"g.add_edge(0, [1, 2, 3, 4])\n",
"g.out_vx(0)"
]
},
{
"cell_type": "code",
"execution_count": 3,
"id": "6378781f-6620-4c16-8f4b-05920734a5b8",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[2, 1, 3, 4]"
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# specify the order [2, 1, 3, 4]\n",
"g.out_vx(0, order=[2, 1, 3, 4])"
]
},
{
"cell_type": "code",
"execution_count": 4,
"id": "65607fd1-be85-44d9-a064-fa93f7f851fc",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[1, 4, 3, 2]"
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# specify subset [3, 2] (by default after the last element)\n",
"g.out_vx(0, order=[3,2])"
]
},
{
"cell_type": "code",
"execution_count": 5,
"id": "ccc6d7ef-7af8-449c-b490-5f0e9ff46155",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[1, 3, 2, 4]"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# specify subset before [3, 2] before 4\n",
"g.out_vx(0, order=[3,2], after=False, anchor=4)"
]
},
{
"cell_type": "markdown",
"id": "37f18663-0fe5-4c67-b905-23aa9f5ea038",
"metadata": {},
"source": [
"## cloning a graph\n",
"\n",
"To clone a graph, we use the `copy(vs=None, g=None, induced=True, ret_map=False)` method, which offers the following optional parameters:\n",
"\n",
"- `vs`: A list of IDs specifying which vertices should be included in the copy. If not provided, all vertices will be copied.\n",
"- `g`: If supplied, vertices will be copied and added to the specified graph `g`. Otherwise, a new graph is created.\n",
"- `induced`: If set to True, any edge between two copied vertices will also be copied, allowing for the cloning of a subgraph.\n",
"- `ret_map`: If True, the method returns a tuple `(cg, map)`, where `cg` is the graph where vertices were copied, and `map` provides a mapping from old to new vertices in the form of a dictionary `{old vertex: new vertex}`.\n"
]
},
{
"cell_type": "code",
"execution_count": 6,
"id": "90f02a15-f702-4bd0-997a-f8909dc782f7",
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"g=HGraph()\n",
"g.add_vx(5)\n",
"g.add_edge(0, [1, 2, 3])\n",
"g.add_edge([1,2,3], 4)\n",
"g.view()"
]
},
{
"cell_type": "code",
"execution_count": 7,
"id": "1f51ba86-394a-49a6-8bc2-dd864ffa4ff1",
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"# clone the whole graph\n",
"h = g.copy()\n",
"h.view()"
]
},
{
"cell_type": "code",
"execution_count": 8,
"id": "f04fcf8e-3d7c-4637-8c06-21f066e6edfd",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"{0: 0, 2: 1, 4: 2}\n"
]
},
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"# clone only vertices\n",
"(h, rmap) = g.copy(vs=[0, 2, 4], induced=False, ret_map=True)\n",
"print(rmap)\n",
"h.view()"
]
},
{
"cell_type": "code",
"execution_count": 9,
"id": "f27b7fb6-ed60-47cf-a1cd-ef2a5c91e8db",
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"# clone subgraph (induced)\n",
"h = g.copy(vs=[0, 2, 4])\n",
"h.view()"
]
},
{
"cell_type": "code",
"execution_count": 10,
"id": "c2bc775b-e581-4070-a038-4ed8275d32b4",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"{0: 5, 2: 6, 4: 7}\n"
]
},
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"# clone full graph\n",
"h1 = g.copy()\n",
"# clone subgraph into graph h1\n",
"(h2, rmap) = g.copy(vs=[0, 2, 4], g=h1, ret_map=True)\n",
"print(rmap)\n",
"# connect first copy with second copy\n",
"h2.add_edge(4, 5)\n",
"h2.view()"
]
},
{
"cell_type": "markdown",
"id": "44e0fdd2",
"metadata": {},
"source": [
"## depth-first search (DFS) \n",
"\n",
"DFS, or Depth-First Search, is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible along each branch before backtracking. \n",
"\n",
"Let us look at the following example:"
]
},
{
"cell_type": "code",
"execution_count": 11,
"id": "a00bec0c",
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"from heterograph import *\n",
"g = HGraph()\n",
"g.add_vx(5)\n",
"g.add_edge(0, [1, 2])\n",
"g.add_edge([1,2], 3)\n",
"g.add_edge(3, 4)\n",
"g.view()"
]
},
{
"cell_type": "markdown",
"id": "06e4af69",
"metadata": {},
"source": [
"### collecting all paths\n",
"To gather all paths, we utilize the function `get_paths(g, vs=None)`:\n",
"* if vs is not provided (default), then all source vertices in the graph (vertices without inputs) are taken into account."
]
},
{
"cell_type": "code",
"execution_count": 12,
"id": "ad9c108a",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[[0, 1, 3, 4], [0, 2, 3, 4]]"
]
},
"execution_count": 12,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"from heterograph.algorithm.dfs import get_paths\n",
"get_paths(g) # root is 0 (graph source)"
]
},
{
"cell_type": "code",
"execution_count": 13,
"id": "707e5aac",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[[1, 3, 4], [2, 3, 4]]"
]
},
"execution_count": 13,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"get_paths(g, vs=[1, 2]) # root: 1 and 2"
]
},
{
"cell_type": "markdown",
"id": "a6086bbd",
"metadata": {},
"source": [
"### visiting nodes\n",
"To visit all nodes of a graph using depth-first search, you can use `dfs_visitor(g, vs=None, pre=None, post=None, data=None)` function: \n",
"* `g` (HGraph): The graph to perform the depth-first search on.\n",
"* `vs` (list, optional): The starting vertices for the search. If not provided, the source vertices of the graph will be used.\n",
"* `pre` (function, optional): A function to be called before visiting each vertex. It takes four arguments: the graph, the current vertex, the current path, and the additional data.\n",
"* `post` (function, optional): A function to be called after visiting each vertex. It takes four arguments: the graph, the current vertex, the current path, and the additional data.\n",
"* `data` (any, optional): Additional data to be passed to the pre and post functions. \n",
"\n",
"Note: functions `pre` or `post` can gracefully stop search at any time by raising `StopSearch`."
]
},
{
"cell_type": "code",
"execution_count": 14,
"id": "1139ea78",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Hello vertex 0: 0\n",
"Hello vertex 1: 1\n",
"Hello vertex 3: 2\n",
"Hello vertex 4: 3\n",
"Bye vertex 4\n",
"Bye vertex 3\n",
"Bye vertex 1\n",
"Hello vertex 2: 4\n",
"Hello vertex 3: 5\n",
"Hello vertex 4: 6\n",
"Bye vertex 4\n",
"Bye vertex 3\n",
"Bye vertex 2\n",
"Bye vertex 0\n",
"===\n",
"Hello again vertex 0\n",
"Hello again vertex 1\n",
"Hello again vertex 3\n"
]
}
],
"source": [
"from heterograph.algorithm.dfs import dfs_visitor, StopSearch\n",
"def pre(g, vx, path, data):\n",
" counter = data['n']\n",
" print(f\"Hello vertex {vx}: {counter}\")\n",
" data['n'] = counter + 1\n",
"\n",
"def post(g, vx, path, data):\n",
" print(f\"Bye vertex {vx}\")\n",
"\n",
"def pre_stops_at_3(g, vx, path, data):\n",
" print(f\"Hello again vertex {vx}\")\n",
" if vx == 3:\n",
" raise StopSearch()\n",
"\n",
"counter = { 'n': 0 }\n",
"# pass data as reference instead of value in order to change it\n",
"dfs_visitor(g, [0], pre=pre, post=post, data=counter)\n",
"print(\"===\")\n",
"dfs_visitor(g, [0], pre=pre_stops_at_3)\n"
]
},
{
"cell_type": "markdown",
"id": "13f8b262",
"metadata": {},
"source": [
"### graph traversal\n",
"\n",
"The `dfs_traversal(g, vx, pre=None, post=None, inh=None)` function provides an advanced mechanism for depth-first search (DFS) traversal:\n",
"\n",
"* It is more efficient than `dfs_visitor`, making it ideal for large graphs.\n",
"* The `inh` parameter allows you to pass initial data that can be inherited by the child nodes during traversal.\n",
"* If supplied, the `pre(g, vx, inh)` function is invoked prior to the visitation of `vx`. The `inh` parameter is optional and represents the value inherited from the parent node.\n",
"* If supplied, the `post(g, vx, synth)` function is invoked following the visitation of `vx`. The `synth` parameter is optional and represents a list of values, each of which is returned by a child node.\n",
"\n",
"In the example below, we use the inheritance feature to assign a depth to each vertex and the synthesis feature to count the number of vertices visited."
]
},
{
"cell_type": "code",
"execution_count": 15,
"id": "47b462d7",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Pre-visit: 0, inherited: 0\n",
"Pre-visit: 1, inherited: 1\n",
"Pre-visit: 3, inherited: 2\n",
"Pre-visit: 4, inherited: 3\n",
"Post-visit: 4, synthesized: []\n",
"Post-visit: 3, synthesized: [1]\n",
"Post-visit: 1, synthesized: [2]\n",
"Pre-visit: 2, inherited: 1\n",
"Post-visit: 2, synthesized: [2]\n",
"Post-visit: 0, synthesized: [3, 3]\n"
]
},
{
"data": {
"text/plain": [
"7"
]
},
"execution_count": 15,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"from heterograph.algorithm.dfs import dfs_traversal\n",
"\n",
"def pre_visit(g, vx, inh):\n",
" print(f\"Pre-visit: {vx}, inherited: {inh}\")\n",
" return inh + 1\n",
"\n",
"def post_visit(g, vx, synth):\n",
" print(f\"Post-visit: {vx}, synthesized: {synth}\")\n",
" return sum(synth) + 1\n",
"\n",
"dfs_traversal(g, 0, pre=pre_visit, post=post_visit, inh=0)"
]
},
{
"cell_type": "markdown",
"id": "8ea13d45-be4f-4737-9815-0fe12e9eb389",
"metadata": {},
"source": [
"## erasing a graph\n",
"\n",
"To remove parts of the graph, we use the `remove_subgraph(vx)` method, where `vx` is the root vertex of the subgraph. All graph elements connected directly and indirectly to `vx` are removed. \n"
]
},
{
"cell_type": "code",
"execution_count": 16,
"id": "7a306561-5391-471a-b4ea-c04f95c1cdbb",
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"# from the graph above\n",
"g.remove_subgraph(2)\n",
"g.view()"
]
},
{
"cell_type": "markdown",
"id": "108cb709-a2c8-4db4-ae4a-df21d384863d",
"metadata": {},
"source": [
"To remove all graph elements and reset the graph, we can use the method `erase()`."
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3 (ipykernel)",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.11.9"
}
},
"nbformat": 4,
"nbformat_minor": 5
}