# K-Graph-Kit🌐
This project aims to provide a comprehensive library for manipulating and analyzing graphs in Python. It includes various methods for working with both weighted and unweighted graphs, as well as algorithms for finding shortest paths, Krustal algorithm, identifying Eulerian and Hamiltonian cycles, and much more.
## Features 🛠️
* Implementation of the `Graph` class for representing simple graphs, multigraphs, directed, and undirected graphs.
* Methods for calculating vertex degrees.
* Dijkstra's algorithm for finding the shortest paths.
* Support for identifying and working with Eulerian graphs and Hamiltonian cycles.
* Methods for verifying graph connectivity and much more...
## Formalism 📐
This is a model of reprentation of a graph, with some relative methods
Ex: * Case of graphs with weights
G = Graph({'A', 'B', 'C'}, {fs({'A', 'B'}): [1, 1], ('A', 'C'): [3.5], fs({'C'}): [4]})
- {'A', 'B', 'C'} : is the set of vertices of G
- {fs({'A', 'B'}): [1, 1], ('A', 'C'): [3.5], fs({'C'}): [4]} : is the set of edges of G
- 'fs({'A', 'B'}): [1, 1]' : means that we have 2 non oriented edges between the edges 'A' et 'B' of weight 1 and 1
- '('A', 'C'): [3.5]' : means that we have one oriented edge (arc) from 'A' to 'C' of weight 3.5
- fs({'C'}): [4] : means that we have one edge (loops) of weight 4 which connects 'C' to itself
NB: - Edges weights are strict positive real numbers
- Vertices are strings or int
* Case of graphs without weight
G = Graph({'A', 'B', 'C'}, {fs({'A', 'B'}): 2, ('A', 'C'): 1, fs({'C'}): 2})
- {'A', 'B', 'C'} : is the set of vertices of G
- {fs({'A', 'B'}): 2, ('A', 'C'): 1, fs({'C'}): 2} : is the set of edges of G
- 'fs({'A', 'B'}): 2' : means that we have 2 non oriented edges between the edges 'A' et 'B'
- '('A', 'C'): 1' : means that we have one oriented edge (arc) from 'A' to 'C'
- fs({'C'}): 2 : means that we have 2 edges (loops) which connects 'C' to itself
NB: - Edges numbers are strict positive integers
- Vertices are strings or int
## Terminology 📚
NB: this class uses a little different terminology comparing to the conventionnal one, in terms of the graph theory
- Arc : oriented edge
- Chain : an alternative succession of vertices and edges, starting and ending with a vertex, and where each edge is between its starting and ending vertices. Ex: A-(A,B)-B-{B, C}-C
NB: - In a simple graph, due to the fact that 2 vertices are connected with maximum 1 edge, it is not necessary to mention the edges.
- Even in multi graph, in general we don't care about the edges, but only about the succession of vertices
Thus, in most cases, a chain will be just a succession of edges. Ex: [1, 3, 2]
- Circuit : it is a chain where the starting and the ending vertices are the same
- Connected graph : graph which has a not oriented version (version where all arcs are replaced by non oriented edges), related.
- Cycle : it is the equivalent of a circuit in a non oriented graph
- Edge : link between 2 vertices (in a mixed graph)
- Loop : edge that connects a vertex to itself
NB: In convention, a loop is not oriented, due to the fact than an eventual orientation is useless
- Mixed graph : graph that have can both arcs and not oriented edges
- Multigraph : graph where we can have loops and even more than 1 edge between 2 vertices
- Not oriented graph : graph where all edges are not oriented
- Oriented graph : graph where all edges are arcs
- Path : it is the equivalent of a chain in a non oriented graph
- Related graph: a non oriented graph, where it is possible, starting from a given vertex, to reach the others
Rk: If this condition is possible for a given vertex, it is possible for the others, due to the fact that the graph is not oriented
- Simple graph : graph without loop, and where there is maximum 1 edge between 2 vertices.
Rk: a such graph can be oriented or not
There are some examples of graphs definitions :
- G = Graph({'A', 'B', 'C', 'D', 'E', 'F', 1, 2, 3, 4}, {fs(('C', 'A')): [1], fs({'B', 'D'}): [3], fs({'B', 'F'}): [2, 4], fs({'C', 'D'}): [2], fs({'C', 'E'}): [50], fs({'D', 'E'}): [100], fs({'E'}): [8], fs({'E', 'F'}): [10], (1, 2): [5], fs({1, 3}): [2], (4, 2): [3], (3, 4): [1]})
- G2 = Graph({1, 2, 3, 7, 5, 6}, {fs((1, 2)): [3], fs({1, 7}): [0.5], fs({1, 6}): [1], fs((3, 1)): [4], fs((1, 5)): [1], (3, 2): [3], fs({3, 7}): [1], (5, 6): [3]}, "G2")
- G3 = Graph({1, 2, 3, 4}, {fs((1, 2)): 2, fs((3, 1)): 1, fs((4, 1)): 3, fs((3, 2)): 1, fs((2, 4)): 1, fs((3, 4)): 1}, "G3")
## Usage Examples 📖
### Creating and Manipulating Weighted Graphs
```python
from graph.graph_class import Graph
# Creating a weighted graph with multiple edges and loops
G = Graph({'A', 'B', 'C', 'D', 'E', 'F', 1, 2, 3, 4}, {fs(('C', 'A')): [1], fs({'B', 'D'}): [3], fs({'B', 'F'}): [2, 4], fs({'C', 'D'}): [2], fs({'C', 'E'}): [50], fs({'D', 'E'}): [100], fs({'E'}): [8], fs({'E', 'F'}): [10], (1, 2): [5], fs({1, 3}): [2], (4, 2): [3], (3, 4): [1]})
# Displaying the vertices and edges of the graph
print(G.Vertices) # Outputs {1, 2, 3, 4, 'A', 'B', 'C', 'D', 'E', 'F'}
print(G.Edges) # Outputs {frozenset({'A', 'C'}): [1],
frozenset({'B', 'D'}): [3],
frozenset({'B', 'F'}): [2, 4],
frozenset({'C', 'D'}): [2],
frozenset({'C', 'E'}): [50],
frozenset({'D', 'E'}): [100],
frozenset({'E'}): [8],
frozenset({'E', 'F'}): [10],
(1, 2): [5],
frozenset({1, 3}): [2],
(4, 2): [3],
(3, 4): [1]}
# Finding the shortest path from 'A' to 'F' using Dijkstra's algorithm
print(G.Djikstra('A', 'F')) # Outputs the path and cost : (['A', 'C', 'D', 'B', 'F'], 8)
```
### Analyzing Caracteristics
```python
print(G.isConnected()) # Returns False
print(G.isSimple()) # Returns False
```
### ...
### Author ✍️
This project was created by KpihX. You can contact me at kapoivha@gmail.com for any questions or suggestions.
## License 📄
This project is under the MIT license - see the LICENSE file for details.
🔗: https://github.com/KpihX/PyGraphKit
Raw data
{
"_id": null,
"home_page": "",
"name": "k-graph-kit",
"maintainer": "",
"docs_url": null,
"requires_python": ">=3.8",
"maintainer_email": "KpihX <kapoivha@gmail.com>",
"keywords": "Djikstrat,Euler,Hamilton,chain,cycle,degree,graph,tree",
"author": "",
"author_email": "KpihX <kapoivha@gmail.com>",
"download_url": "",
"platform": null,
"description": "# K-Graph-Kit\ud83c\udf10\n\nThis project aims to provide a comprehensive library for manipulating and analyzing graphs in Python. It includes various methods for working with both weighted and unweighted graphs, as well as algorithms for finding shortest paths, Krustal algorithm, identifying Eulerian and Hamiltonian cycles, and much more.\n\n## Features \ud83d\udee0\ufe0f\n\n* Implementation of the `Graph` class for representing simple graphs, multigraphs, directed, and undirected graphs.\n* Methods for calculating vertex degrees.\n* Dijkstra's algorithm for finding the shortest paths.\n* Support for identifying and working with Eulerian graphs and Hamiltonian cycles.\n* Methods for verifying graph connectivity and much more...\n\n## Formalism \ud83d\udcd0\n\nThis is a model of reprentation of a graph, with some relative methods\n\n Ex: * Case of graphs with weights\n\n G = Graph({'A', 'B', 'C'}, {fs({'A', 'B'}): [1, 1], ('A', 'C'): [3.5], fs({'C'}): [4]})\n\n - {'A', 'B', 'C'} : is the set of vertices of G\n\n - {fs({'A', 'B'}): [1, 1], ('A', 'C'): [3.5], fs({'C'}): [4]} : is the set of edges of G\n\n - 'fs({'A', 'B'}): [1, 1]' : means that we have 2 non oriented edges between the edges 'A' et 'B' of weight 1 and 1\n\n - '('A', 'C'): [3.5]' : means that we have one oriented edge (arc) from 'A' to 'C' of weight 3.5\n\n - fs({'C'}): [4] : means that we have one edge (loops) of weight 4 which connects 'C' to itself\n\n NB: - Edges weights are strict positive real numbers\n\n - Vertices are strings or int\n\n * Case of graphs without weight\n\n G = Graph({'A', 'B', 'C'}, {fs({'A', 'B'}): 2, ('A', 'C'): 1, fs({'C'}): 2})\n\n - {'A', 'B', 'C'} : is the set of vertices of G\n\n - {fs({'A', 'B'}): 2, ('A', 'C'): 1, fs({'C'}): 2} : is the set of edges of G\n\n - 'fs({'A', 'B'}): 2' : means that we have 2 non oriented edges between the edges 'A' et 'B'\n\n - '('A', 'C'): 1' : means that we have one oriented edge (arc) from 'A' to 'C'\n\n - fs({'C'}): 2 : means that we have 2 edges (loops) which connects 'C' to itself\n\n NB: - Edges numbers are strict positive integers\n\n - Vertices are strings or int\n\n## Terminology \ud83d\udcda\n\n NB: this class uses a little different terminology comparing to the conventionnal one, in terms of the graph theory\n\n - Arc : oriented edge\n\n - Chain : an alternative succession of vertices and edges, starting and ending with a vertex, and where each edge is between its starting and ending vertices. Ex: A-(A,B)-B-{B, C}-C\n\n NB: - In a simple graph, due to the fact that 2 vertices are connected with maximum 1 edge, it is not necessary to mention the edges.\n\n - Even in multi graph, in general we don't care about the edges, but only about the succession of vertices\n\n Thus, in most cases, a chain will be just a succession of edges. Ex: [1, 3, 2]\n\n - Circuit : it is a chain where the starting and the ending vertices are the same\n\n - Connected graph : graph which has a not oriented version (version where all arcs are replaced by non oriented edges), related.\n\n - Cycle : it is the equivalent of a circuit in a non oriented graph\n\n - Edge : link between 2 vertices (in a mixed graph)\n\n - Loop : edge that connects a vertex to itself\n\n NB: In convention, a loop is not oriented, due to the fact than an eventual orientation is useless\n\n - Mixed graph : graph that have can both arcs and not oriented edges\n\n - Multigraph : graph where we can have loops and even more than 1 edge between 2 vertices\n\n - Not oriented graph : graph where all edges are not oriented\n\n - Oriented graph : graph where all edges are arcs\n\n - Path : it is the equivalent of a chain in a non oriented graph\n\n - Related graph: a non oriented graph, where it is possible, starting from a given vertex, to reach the others\n\n Rk: If this condition is possible for a given vertex, it is possible for the others, due to the fact that the graph is not oriented\n\n - Simple graph : graph without loop, and where there is maximum 1 edge between 2 vertices.\n\n Rk: a such graph can be oriented or not\n\n There are some examples of graphs definitions :\n\n- G = Graph({'A', 'B', 'C', 'D', 'E', 'F', 1, 2, 3, 4}, {fs(('C', 'A')): [1], fs({'B', 'D'}): [3], fs({'B', 'F'}): [2, 4], fs({'C', 'D'}): [2], fs({'C', 'E'}): [50], fs({'D', 'E'}): [100], fs({'E'}): [8], fs({'E', 'F'}): [10], (1, 2): [5], fs({1, 3}): [2], (4, 2): [3], (3, 4): [1]})\n- G2 = Graph({1, 2, 3, 7, 5, 6}, {fs((1, 2)): [3], fs({1, 7}): [0.5], fs({1, 6}): [1], fs((3, 1)): [4], fs((1, 5)): [1], (3, 2): [3], fs({3, 7}): [1], (5, 6): [3]}, \"G2\")\n- G3 = Graph({1, 2, 3, 4}, {fs((1, 2)): 2, fs((3, 1)): 1, fs((4, 1)): 3, fs((3, 2)): 1, fs((2, 4)): 1, fs((3, 4)): 1}, \"G3\")\n\n## Usage Examples \ud83d\udcd6\n\n### Creating and Manipulating Weighted Graphs\n\n```python\nfrom graph.graph_class import Graph\n\n# Creating a weighted graph with multiple edges and loops\nG = Graph({'A', 'B', 'C', 'D', 'E', 'F', 1, 2, 3, 4}, {fs(('C', 'A')): [1], fs({'B', 'D'}): [3], fs({'B', 'F'}): [2, 4], fs({'C', 'D'}): [2], fs({'C', 'E'}): [50], fs({'D', 'E'}): [100], fs({'E'}): [8], fs({'E', 'F'}): [10], (1, 2): [5], fs({1, 3}): [2], (4, 2): [3], (3, 4): [1]})\n\n# Displaying the vertices and edges of the graph\nprint(G.Vertices) # Outputs {1, 2, 3, 4, 'A', 'B', 'C', 'D', 'E', 'F'}\nprint(G.Edges) # Outputs {frozenset({'A', 'C'}): [1],\n frozenset({'B', 'D'}): [3],\n frozenset({'B', 'F'}): [2, 4],\n frozenset({'C', 'D'}): [2],\n frozenset({'C', 'E'}): [50],\n frozenset({'D', 'E'}): [100],\n frozenset({'E'}): [8],\n frozenset({'E', 'F'}): [10],\n (1, 2): [5],\n frozenset({1, 3}): [2],\n (4, 2): [3],\n (3, 4): [1]}\n\n# Finding the shortest path from 'A' to 'F' using Dijkstra's algorithm\nprint(G.Djikstra('A', 'F')) # Outputs the path and cost : (['A', 'C', 'D', 'B', 'F'], 8)\n```\n\n### Analyzing Caracteristics\n\n```python\nprint(G.isConnected()) # Returns False\n\nprint(G.isSimple()) # Returns False\n\n```\n\n### ...\n\n### Author \u270d\ufe0f\n\nThis project was created by KpihX. You can contact me at kapoivha@gmail.com for any questions or suggestions.\n\n## License \ud83d\udcc4\n\nThis project is under the MIT license - see the LICENSE file for details.\n\n\ud83d\udd17: https://github.com/KpihX/PyGraphKit\n",
"bugtrack_url": null,
"license": "MIT License",
"summary": "A package to easily deal with graph and their universe!",
"version": "0.0.1",
"project_urls": {
"Homepage": "https://pypi.org/project/k_graph_kit/",
"Issues": "https://github.com/KpihX/k_graph_kit/issues",
"Repository": "https://github.com/KpihX/k_graph_kit.git"
},
"split_keywords": [
"djikstrat",
"euler",
"hamilton",
"chain",
"cycle",
"degree",
"graph",
"tree"
],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "38f4013249f2dbf040ef697918240296e9ebf101a06deb673d7470403b986077",
"md5": "99d6adb4bd3d624a0bbd5a027ec75d01",
"sha256": "55f4500603f382ce5b80f04633e1b82e8ce86451db605d96520fe7dca83b4f01"
},
"downloads": -1,
"filename": "k_graph_kit-0.0.1-py3-none-any.whl",
"has_sig": false,
"md5_digest": "99d6adb4bd3d624a0bbd5a027ec75d01",
"packagetype": "bdist_wheel",
"python_version": "py3",
"requires_python": ">=3.8",
"size": 11118,
"upload_time": "2024-02-15T22:56:08",
"upload_time_iso_8601": "2024-02-15T22:56:08.119643Z",
"url": "https://files.pythonhosted.org/packages/38/f4/013249f2dbf040ef697918240296e9ebf101a06deb673d7470403b986077/k_graph_kit-0.0.1-py3-none-any.whl",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2024-02-15 22:56:08",
"github": true,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"github_user": "KpihX",
"github_project": "k_graph_kit",
"travis_ci": false,
"coveralls": false,
"github_actions": false,
"lcname": "k-graph-kit"
}
JSON
