brianbruggeman/pathing.py

## pathing.py
#!/usr/bin/env python3
import json
import os
from uuid import uuid4 as uuid


D3_HTML = """
<!DOCTYPE html>
<meta charset="utf-8">
<style>

.links line {
  stroke: #999;
  stroke-opacity: 0.6;
}

.nodes circle {
  stroke: #fff;
  stroke-width: 1.5px;
}

</style>
<svg width="960" height="600"></svg>
<script src="https://d3js.org/d3.v4.min.js"></script>
<script>

var svg = d3.select("svg"),
    width = +svg.attr("width"),
    height = +svg.attr("height");

var color = d3.scaleOrdinal(d3.schemeCategory20);

var simulation = d3.forceSimulation()
    .force("link", d3.forceLink().id(function(d) { return d.id; }))
    .force("charge", d3.forceManyBody())
    .force("center", d3.forceCenter(width / 2, height / 2));

  graph = %(graph)s;

  var link = svg.append("g")
      .attr("class", "links")
    .selectAll("line")
    .data(graph.links)
    .enter().append("line")
      .attr("stroke-width", function(d) { return Math.sqrt(d.value); });

  var node = svg.append("g")
      .attr("class", "nodes")
    .selectAll("circle")
    .data(graph.nodes)
    .enter().append("circle")
      .attr("r", 5)
      .attr("fill", function(d) { return color(d.group); })
      .call(d3.drag()
          .on("start", dragstarted)
          .on("drag", dragged)
          .on("end", dragended));

  node.append("title")
      .text(function(d) { return d.id; });

  simulation
      .nodes(graph.nodes)
      .on("tick", ticked);

  simulation.force("link")
      .links(graph.links);

  function ticked() {
    link
        .attr("x1", function(d) { return d.source.x; })
        .attr("y1", function(d) { return d.source.y; })
        .attr("x2", function(d) { return d.target.x; })
        .attr("y2", function(d) { return d.target.y; });

    node
        .attr("cx", function(d) { return d.x; })
        .attr("cy", function(d) { return d.y; });
  }

function dragstarted(d) {
  if (!d3.event.active) simulation.alphaTarget(0.3).restart();
  d.fx = d.x;
  d.fy = d.y;
}

function dragged(d) {
  d.fx = d3.event.x;
  d.fy = d3.event.y;
}

function dragended(d) {
  if (!d3.event.active) simulation.alphaTarget(0);
  d.fx = null;
  d.fy = null;
}

</script>"""


class Base(object):
    """Shared by Node and Edge

    Args:
        name (str, optional): the name of the node or edge
        attributes (dict, optional): attributes attached to the node or edge
    """

    @property
    def id(self):
        if not hasattr(self, '_id'):
            self._id = uuid().hex
        return self._id

    @id.setter
    def id(self, value):
        if value is not None:
            self._id = value

    def __init__(self, name=None, **attributes):
        self.id = name
        self.edges = {}
        self.attributes = attributes

    def __repr__(self):
        attrs = ' '.join(f'{k}:{v}' for k, v in self.attributes.items())
        if attrs:
            attrs = f' {attrs}'
        return f'<{type(self).__name__}:{self.id}{attrs}>'


class Edge(Base):
    """A Basic Edge

    Args:
        start (Node): the starting node
        end (Node): the ending node
        name (str, optional): the name of the node or edge
        attributes (dict, optional): attributes attached to the edge
    """

    def __init__(self, start, end, name=None, **attributes):
        self.source = start
        self.target = end
        name = name or f'{start.id}-{end.id}'
        super().__init__(name=name, **attributes)

    def __iter__(self):
        yield self.source
        if self.source != self.target:
            yield self.target

    def __contains__(self, other):
        return other in [self.source, self.target]


class Node(Base):
    """A Basic Node

    Args:
        name (str, optional): the name of the node or edge
        attributes (dict, optional): attributes attached to the node
    """

    @property
    def neighbors(self):
        found_nodes = [self]
        edges = self.edges.values()
        for edge in edges:
            for node in edge:
                if node not in found_nodes:
                    found_nodes.append(node)
                    yield node

    def add(self, edge):
        """Adds an edge to a Node.

        Args:
            edge (Edge): an edge to add to the node
        """
        self.edges[edge.id] = edge

    def remove(self, edge):
        """Removes an edge from a Node.

        Args:
            edge (Edge): an edge to remove from the node
        """
        self.edges.pop(edge.id)


class Graph(dict):
    """A basic network which holds nodes"""

    def __repr__(self):
        count = len(self)
        return f'<{type(self).__name__} node_count={count}>'

    @property
    def nodes(self):
        nodes = []
        for node_id, node in self.items():
            if node not in nodes:
                nodes.append(node)
                yield node

    @property
    def edges(self):
        edges = []
        nodes = []
        for node_id, node in self.items():
            if node in nodes:
                continue
            nodes.append(node)
            for edge in node.edges.values():
                if edge not in edges:
                    edges.append(edge)
                    yield edge


class Path(object):

    def __init__(self, graph):
        self.graph = graph

    def __iter__(self):
        for x in range(len(self.graph)):
            for y in range(len(self.graph)):
                for path in find_paths(self.graph, x, y):
                    yield x, y, path


def find_paths(graph, start, end, path=[]):
    path = path + [start]
    if start == end:
        found = False
        start_node = graph[start]
        for edge in start_node.edges.values():
            if edge.source == edge.target:
                found = True
                break
        if found is True:
            return [path]
        elif path != [start]:
            return [path]
        else:
            return []
    elif start not in graph:
        return []
    else:
        paths = []
        node = graph[start]
        for neighbor in node.neighbors:
            if neighbor.id not in path:
                new_paths = find_paths(graph, neighbor.id, end, path)
                for new_path in new_paths:
                    paths.append(new_path)
    return paths


def generate_graph(size=4, edge_count=4):
    map_size = size ** 2
    # print(f'Generating nodes ({size}x{size})')
    nodes = [
        Node(index) for index in range(map_size)
    ]
    # print(f'Generating edges')
    for index in range(map_size):
        start = nodes[index]
        for edge_index in range(random.choice(range(max_edge_count))):
            end_index = random.choice(range(map_size))
            end = nodes[end_index]
            start.add(Edge(start, end))
            end.add(Edge(end, start))

    graph = Graph({node.id: node for node in nodes})
    return graph


def visualize(graph, group_size=10):
    """Visualizes graph"""
    # dump to out.json
    data = {
        'nodes': [{'id': f"{node.id}", 'group': index % group_size} for index, node in enumerate(graph.nodes)],
        'links': [{'source': f"{edge.source.id}", 'target': f"{edge.target.id}", 'value': 1} for edge in graph.edges]
    }
    d3_string = json.dumps(data, sort_keys=True, indent=4)

    html = D3_HTML % {'graph': d3_string}
    # dump to out.html
    with open('out.html', 'w') as fd:
        fd.write(html)

    # open out.html in browser
    os.system('open out.html --args -allow-file-access-from-files')


if __name__ == '__main__':
    import random

    size = 6
    edge_count = range(size // 2, size)
    # edge_count = range(size * 2)
    max_edge_count = min(random.choice(edge_count) or 1, 4)
    # print(f'Graph Connectivity: {max_edge_count}')
    graph = generate_graph(size=size, edge_count=max_edge_count)
    visualize(graph)
	#!/usr/bin/env python3
	import json
	import os
	from uuid import uuid4 as uuid


	D3_HTML = """
	<!DOCTYPE html>
	<meta charset="utf-8">
	<style>

	.links line {
	stroke: #999;
	stroke-opacity: 0.6;
	}

	.nodes circle {
	stroke: #fff;
	stroke-width: 1.5px;
	}

	</style>
	<svg width="960" height="600"></svg>
	<script src="https://d3js.org/d3.v4.min.js"></script>
	<script>

	var svg = d3.select("svg"),
	width = +svg.attr("width"),
	height = +svg.attr("height");

	var color = d3.scaleOrdinal(d3.schemeCategory20);

	var simulation = d3.forceSimulation()
	.force("link", d3.forceLink().id(function(d) { return d.id; }))
	.force("charge", d3.forceManyBody())
	.force("center", d3.forceCenter(width / 2, height / 2));

	graph = %(graph)s;

	var link = svg.append("g")
	.attr("class", "links")
	.selectAll("line")
	.data(graph.links)
	.enter().append("line")
	.attr("stroke-width", function(d) { return Math.sqrt(d.value); });

	var node = svg.append("g")
	.attr("class", "nodes")
	.selectAll("circle")
	.data(graph.nodes)
	.enter().append("circle")
	.attr("r", 5)
	.attr("fill", function(d) { return color(d.group); })
	.call(d3.drag()
	.on("start", dragstarted)
	.on("drag", dragged)
	.on("end", dragended));

	node.append("title")
	.text(function(d) { return d.id; });

	simulation
	.nodes(graph.nodes)
	.on("tick", ticked);

	simulation.force("link")
	.links(graph.links);

	function ticked() {
	link
	.attr("x1", function(d) { return d.source.x; })
	.attr("y1", function(d) { return d.source.y; })
	.attr("x2", function(d) { return d.target.x; })
	.attr("y2", function(d) { return d.target.y; });

	node
	.attr("cx", function(d) { return d.x; })
	.attr("cy", function(d) { return d.y; });
	}

	function dragstarted(d) {
	if (!d3.event.active) simulation.alphaTarget(0.3).restart();
	d.fx = d.x;
	d.fy = d.y;
	}

	function dragged(d) {
	d.fx = d3.event.x;
	d.fy = d3.event.y;
	}

	function dragended(d) {
	if (!d3.event.active) simulation.alphaTarget(0);
	d.fx = null;
	d.fy = null;
	}

	</script>"""


	class Base(object):
	"""Shared by Node and Edge

	Args:
	name (str, optional): the name of the node or edge
	attributes (dict, optional): attributes attached to the node or edge
	"""

	@property
	def id(self):
	if not hasattr(self, '_id'):
	self._id = uuid().hex
	return self._id

	@id.setter
	def id(self, value):
	if value is not None:
	self._id = value

	def __init__(self, name=None, **attributes):
	self.id = name
	self.edges = {}
	self.attributes = attributes

	def __repr__(self):
	attrs = ' '.join(f'{k}:{v}' for k, v in self.attributes.items())
	if attrs:
	attrs = f' {attrs}'
	return f'<{type(self).__name__}:{self.id}{attrs}>'


	class Edge(Base):
	"""A Basic Edge

	Args:
	start (Node): the starting node
	end (Node): the ending node
	name (str, optional): the name of the node or edge
	attributes (dict, optional): attributes attached to the edge
	"""

	def __init__(self, start, end, name=None, **attributes):
	self.source = start
	self.target = end
	name = name or f'{start.id}-{end.id}'
	super().__init__(name=name, **attributes)

	def __iter__(self):
	yield self.source
	if self.source != self.target:
	yield self.target

	def __contains__(self, other):
	return other in [self.source, self.target]


	class Node(Base):
	"""A Basic Node

	Args:
	name (str, optional): the name of the node or edge
	attributes (dict, optional): attributes attached to the node
	"""

	@property
	def neighbors(self):
	found_nodes = [self]
	edges = self.edges.values()
	for edge in edges:
	for node in edge:
	if node not in found_nodes:
	found_nodes.append(node)
	yield node

	def add(self, edge):
	"""Adds an edge to a Node.

	Args:
	edge (Edge): an edge to add to the node
	"""
	self.edges[edge.id] = edge

	def remove(self, edge):
	"""Removes an edge from a Node.

	Args:
	edge (Edge): an edge to remove from the node
	"""
	self.edges.pop(edge.id)


	class Graph(dict):
	"""A basic network which holds nodes"""

	def __repr__(self):
	count = len(self)
	return f'<{type(self).__name__} node_count={count}>'

	@property
	def nodes(self):
	nodes = []
	for node_id, node in self.items():
	if node not in nodes:
	nodes.append(node)
	yield node

	@property
	def edges(self):
	edges = []
	nodes = []
	for node_id, node in self.items():
	if node in nodes:
	continue
	nodes.append(node)
	for edge in node.edges.values():
	if edge not in edges:
	edges.append(edge)
	yield edge


	class Path(object):

	def __init__(self, graph):
	self.graph = graph

	def __iter__(self):
	for x in range(len(self.graph)):
	for y in range(len(self.graph)):
	for path in find_paths(self.graph, x, y):
	yield x, y, path


	def find_paths(graph, start, end, path=[]):
	path = path + [start]
	if start == end:
	found = False
	start_node = graph[start]
	for edge in start_node.edges.values():
	if edge.source == edge.target:
	found = True
	break
	if found is True:
	return [path]
	elif path != [start]:
	return [path]
	else:
	return []
	elif start not in graph:
	return []
	else:
	paths = []
	node = graph[start]
	for neighbor in node.neighbors:
	if neighbor.id not in path:
	new_paths = find_paths(graph, neighbor.id, end, path)
	for new_path in new_paths:
	paths.append(new_path)
	return paths


	def generate_graph(size=4, edge_count=4):
	map_size = size ** 2
	# print(f'Generating nodes ({size}x{size})')
	nodes = [
	Node(index) for index in range(map_size)
	]
	# print(f'Generating edges')
	for index in range(map_size):
	start = nodes[index]
	for edge_index in range(random.choice(range(max_edge_count))):
	end_index = random.choice(range(map_size))
	end = nodes[end_index]
	start.add(Edge(start, end))
	end.add(Edge(end, start))

	graph = Graph({node.id: node for node in nodes})
	return graph


	def visualize(graph, group_size=10):
	"""Visualizes graph"""
	# dump to out.json
	data = {
	'nodes': [{'id': f"{node.id}", 'group': index % group_size} for index, node in enumerate(graph.nodes)],
	'links': [{'source': f"{edge.source.id}", 'target': f"{edge.target.id}", 'value': 1} for edge in graph.edges]
	}
	d3_string = json.dumps(data, sort_keys=True, indent=4)

	html = D3_HTML % {'graph': d3_string}
	# dump to out.html
	with open('out.html', 'w') as fd:
	fd.write(html)

	# open out.html in browser
	os.system('open out.html --args -allow-file-access-from-files')


	if __name__ == '__main__':
	import random

	size = 6
	edge_count = range(size // 2, size)
	# edge_count = range(size * 2)
	max_edge_count = min(random.choice(edge_count) or 1, 4)
	# print(f'Graph Connectivity: {max_edge_count}')
	graph = generate_graph(size=size, edge_count=max_edge_count)
	visualize(graph)