use hashbrown::{HashMap, HashSet};
use std::{hash::Hash, rc::Rc};
use super::{
MultiplexBase, MultiplexNode,
directive::{MultiplexEdge, MultiplexEdgeType},
layers::Layer,
weak_layers::{WeakDLayer, WeakLayer, WeakULayer},
};
use crate::traits::*;
pub struct MultiplexGraph<N, L> {
pub(crate) base: Rc<MultiplexBase<N>>,
pub(crate) layers: Vec<WeakLayer<L>>,
}
impl<N, L> MultiplexGraph<N, L>
where
N: Clone,
L: Clone,
{
pub fn new() -> Self {
Self {
base: MultiplexBase::new([].into_iter()),
layers: Vec::new(),
}
}
pub fn base(&self) -> &MultiplexBase<N> {
&self.base
}
pub fn layers(&self) -> &[WeakLayer<L>] {
&self.layers
}
pub fn add_node(&mut self, weight: N) -> usize {
let index = self.base.nodes.len();
Rc::make_mut(&mut self.base)
.nodes
.push(MultiplexNode { weight });
index
}
pub fn add_layer<E: MultiplexEdgeType>(&mut self, weight: L, directive: bool) -> usize {
if directive {
let layer = WeakDLayer::new::<E>(weight.clone());
self.layers.push(WeakLayer::Directed(layer));
} else {
let layer = WeakULayer::new::<E>(weight.clone());
self.layers.push(WeakLayer::Undirected(layer));
}
self.layers.len() - 1
}
pub fn decompose(self) -> (Rc<MultiplexBase<N>>, Vec<Layer<N, L>>) {
let base = Rc::clone(&self.base);
let layers = self
.layers
.into_iter()
.map(|layer| layer.strengthen(Rc::clone(&base)))
.collect();
(base, layers)
}
fn get_neighbours<F>(&self, node_index: usize, include_layers: F) -> Option<HashSet<&usize>>
where
F: Fn(usize) -> bool,
{
Some(
self.layers
.iter()
.enumerate()
.filter(|(i, _l)| include_layers(*i))
.filter_map(|(_i, layer)| {
if let WeakLayer::Undirected(layer) = layer {
let edges = &layer.incidence.get(&node_index)?;
let mut out = edges
.iter()
.flat_map(|e| &layer.edges[*e].nodes)
.collect::<HashSet<_>>();
out.remove(&node_index);
Some(out)
} else {
None
}
})
.flatten()
.collect(),
)
}
fn get_in_neighbours<F>(&self, node_index: usize, include_layers: F) -> Option<HashSet<&usize>>
where
F: Fn(usize) -> bool,
{
Some(
self.layers
.iter()
.enumerate()
.filter(|(i, _l)| include_layers(*i))
.filter_map(|(_i, layer)| {
if let WeakLayer::Directed(layer) = layer {
let edges = &layer.incidence.get(&node_index)?;
let mut out = edges
.0
.iter()
.flat_map(|e| &layer.edges[*e].source)
.collect::<HashSet<_>>();
out.remove(&node_index);
Some(out)
} else {
None
}
})
.flatten()
.collect(),
)
}
fn get_out_neighbours<F>(&self, node_index: usize, include_layers: F) -> Option<HashSet<&usize>>
where
F: Fn(usize) -> bool,
{
Some(
self.layers
.iter()
.enumerate()
.filter(|(i, _l)| include_layers(*i))
.filter_map(|(_i, layer)| {
if let WeakLayer::Directed(layer) = layer {
let edges = &layer.incidence.get(&node_index)?;
let mut out = edges
.1
.iter()
.flat_map(|e| &layer.edges[*e].target)
.collect::<HashSet<_>>();
out.remove(&node_index);
Some(out)
} else {
None
}
})
.flatten()
.collect(),
)
}
pub fn induced_shgraph(&self, node_indices: &[usize]) -> Self
where
N: Clone,
{
let mut node_map = vec![None; self.base.len()];
let mut new_nodes = vec![];
for &node_index in node_indices.iter() {
if let Some(node) = self.base.nodes.get(node_index) {
let new_index = new_nodes.len();
new_nodes.push(MultiplexNode {
weight: node.weight.clone(),
});
node_map[node_index] = Some(new_index);
}
}
let out = MultiplexGraph {
layers: self
.layers()
.iter()
.map(|layer| {
match layer {
WeakLayer::Undirected(weak_ulayer) => {
let mut u = node_indices
.iter()
.flat_map(|i| {
weak_ulayer.incidence[i]
.iter()
.map(|x| (*x, &weak_ulayer.edges[*x]))
})
.collect::<Vec<_>>();
u.retain(|(_i, e)| {
!e.nodes.is_empty()
&& e.nodes.iter().all(|&n| node_map[n].is_some())
});
let edge_map = u
.iter()
.enumerate()
.map(|(i, (j, _))| (*j, i))
.collect::<HashMap<_, _>>();
let mut out = WeakULayer::new::<()>(weak_ulayer.weight.clone());
for (i, v) in weak_ulayer.incidence.iter() {
if let Some(new_index) = node_map[*i] {
out.incidence.insert(
new_index,
v.iter()
.filter_map(|&e| edge_map.get(&e).cloned())
.collect(),
);
}
}
for (_, edge) in &u {
let new_source: Vec<usize> =
edge.nodes.iter().filter_map(|&n| node_map[n]).collect();
if !new_source.is_empty() {
out.add_edge((), new_source).unwrap();
}
}
WeakLayer::Undirected(out)
}
WeakLayer::Directed(weak_dlayer) => {
let mut u = node_indices
.iter()
.flat_map(|i| {
weak_dlayer.incidence[i]
.0
.iter()
.chain(weak_dlayer.incidence[i].1.iter())
.map(|x| (*x, &weak_dlayer.edges[*x]))
})
.collect::<Vec<_>>();
u.retain(|(_i, e)| {
!e.source.is_empty()
&& e.source.iter().all(|&n| node_map[n].is_some())
&& !e.target.is_empty()
&& e.target.iter().all(|&n| node_map[n].is_some())
});
let edge_map = u
.iter()
.enumerate()
.map(|(i, (j, _))| (*j, i))
.collect::<HashMap<_, _>>();
let mut out = WeakDLayer::new::<()>(weak_dlayer.weight.clone());
for (i, v) in weak_dlayer.incidence.iter() {
if let Some(new_index) = node_map[*i] {
out.incidence.insert(
new_index,
(
v.0.iter()
.filter_map(|&e| edge_map.get(&e).cloned())
.collect(),
v.1.iter()
.filter_map(|&e| edge_map.get(&e).cloned())
.collect(),
),
);
}
}
for (_, edge) in &u {
let new_source: Vec<usize> =
edge.source.iter().filter_map(|&n| node_map[n]).collect();
let new_target: Vec<usize> =
edge.target.iter().filter_map(|&n| node_map[n]).collect();
if !new_source.is_empty() {
out.add_edge((), new_source, new_target).unwrap();
}
}
WeakLayer::Directed(out)
}
}
})
.collect(),
base: Rc::new(MultiplexBase { nodes: new_nodes }),
};
out
}
}
#[derive(Clone, PartialEq, Eq, Hash, Copy)]
pub struct MultiplexIndex(Option<usize>, usize);
impl From<usize> for MultiplexIndex {
fn from(index: usize) -> Self {
MultiplexIndex(None, index)
}
}
impl Into<usize> for MultiplexIndex {
fn into(self) -> usize {
self.1
}
}
impl MultiplexIndex {
pub fn layer_index(&self) -> Option<usize> {
self.0
}
pub fn component_index(&self) -> usize {
self.1
}
pub fn from_layers(layer_index: usize, component_index: usize) -> Self {
MultiplexIndex(Some(layer_index), component_index)
}
}
impl<'a, N, L> GraphBasics<'a> for MultiplexGraph<N, L>
where
N: Clone + Eq + Hash + 'a,
L: Clone + Eq + Hash + 'a,
{
type NodeRef = &'a MultiplexNode<N>;
type EdgeRef = MultiplexEdge<'a>;
type EdgeIndex = MultiplexIndex;
type NodeIndex = MultiplexIndex;
fn node_count(&'a self) -> usize {
Rc::as_ref(&self.base).nodes.len()
}
fn edge_count(&'a self) -> usize {
self.layers.iter().map(|x| x.edges(0).len()).sum()
}
fn nodes(&'a self) -> impl Iterator<Item = Self::NodeRef> {
self.base.iter()
}
fn edges(&'a self) -> impl Iterator<Item = Self::EdgeRef> {
self.layers
.iter()
.enumerate()
.flat_map(|(i, layer)| layer.edges(i))
}
fn is_directed(&self) -> bool {
self.layers
.iter()
.any(|layer| matches!(layer, WeakLayer::Directed(_)))
}
fn node(&'a self, node_index: MultiplexIndex) -> Option<<Self as GraphBasics<'a>>::NodeRef> {
self.base.nodes.get(node_index.1)
}
fn edge(
&'a self,
edge_index: <Self as GraphBasics<'a>>::EdgeIndex,
) -> Option<<Self as GraphBasics<'a>>::EdgeRef> {
self.layers.get(edge_index.0?).map(|layer| match layer {
WeakLayer::Undirected(layer) => {
MultiplexEdge::Undirected(edge_index.0.unwrap(), &layer.edges[edge_index.1])
}
WeakLayer::Directed(layer) => {
MultiplexEdge::Directed(edge_index.0.unwrap(), &layer.edges[edge_index.1])
}
})
}
fn node_iter(
&'a self,
node_index: impl Iterator<Item = Self::NodeIndex>,
) -> impl Iterator<Item = Option<Self::NodeRef>> {
node_index.map(|index| self.node(index))
}
fn edge_iter(
&'a self,
edge_index: impl Iterator<Item = Self::EdgeIndex>,
) -> impl Iterator<Item = Option<Self::EdgeRef>> {
edge_index.map(|index| self.edge(index))
}
}
impl<'a, N: 'a, L: 'a> GraphProperties<'a> for MultiplexGraph<N, L>
where
N: Clone + Eq + Hash,
L: Clone + Eq + Hash,
{
fn incident_edges(
&self,
node_index: MultiplexIndex,
) -> Option<hashbrown::HashSet<MultiplexIndex>> {
if let Some(layer_index) = node_index.0 {
if let WeakLayer::Undirected(layer) = &self.layers[layer_index] {
Some(
layer.incidence[&node_index.1]
.iter()
.map(|e| MultiplexIndex(Some(layer_index), *e))
.collect::<HashSet<_>>(),
)
} else {
None
}
} else {
Some(
self.layers
.iter()
.enumerate()
.filter_map(|(i, l)| {
if let WeakLayer::Undirected(layer) = l {
Some(
layer.incidence[&node_index.1]
.iter()
.map(|e| MultiplexIndex(Some(i), *e))
.collect::<HashSet<_>>(),
)
} else {
None
}
})
.flatten()
.collect(),
)
}
}
fn contained_nodes(
&self,
edge_index: MultiplexIndex,
) -> Option<hashbrown::HashSet<MultiplexIndex>> {
let MultiplexIndex(layer_index, edge_index) = edge_index;
let layer = self.layers.get(layer_index?)?;
if let WeakLayer::Undirected(layer) = layer {
layer.edges.get(edge_index).map(|edge| {
edge.nodes
.iter()
.map(|&node| MultiplexIndex(layer_index, node))
.collect()
})
} else {
None
}
}
fn neighbours(&self, node_index: MultiplexIndex) -> Option<hashbrown::HashSet<MultiplexIndex>> {
let MultiplexIndex(layer_index, node_index) = node_index;
if let Some(layer_index) = layer_index {
if let WeakLayer::Undirected(layer) = &self.layers[layer_index] {
let edges = &layer.incidence.get(&node_index)?;
let mut out = edges
.iter()
.flat_map(|e| &layer.edges[*e].nodes)
.map(|x| MultiplexIndex(Some(layer_index), *x))
.collect::<HashSet<_>>();
out.remove(&MultiplexIndex(Some(layer_index), node_index));
Some(out)
} else {
None
}
} else {
Some(
self.layers
.iter()
.enumerate()
.filter_map(|(i, layer)| {
if let WeakLayer::Undirected(layer) = layer {
let edges = &layer.incidence.get(&node_index)?;
let mut out = edges
.iter()
.flat_map(|e| &layer.edges[*e].nodes)
.map(|x| MultiplexIndex(Some(i), *x))
.collect::<HashSet<_>>();
out.remove(&MultiplexIndex(Some(i), node_index));
Some(out)
} else {
None
}
})
.flatten()
.collect(),
)
}
}
fn neighbour_count(&self, node_index: usize) -> Option<usize> {
if node_index >= self.base.nodes.len() {
return None;
}
Some(
self.layers
.iter()
.enumerate()
.map(|(_i, l)| {
if let WeakLayer::Undirected(layer) = l {
let edges = layer.incidence.get(&node_index).unwrap();
let mut nmap = edges
.iter()
.flat_map(|x| &layer.edges[*x].nodes)
.collect::<HashSet<_>>();
nmap.remove(&node_index); nmap.len()
} else {
0
}
})
.sum(),
)
}
fn degree(&self, node_index: MultiplexIndex) -> Option<usize> {
if node_index.1 >= self.base.nodes.len() {
return None;
}
Some(
self.layers
.iter()
.map(|l| {
if let WeakLayer::Undirected(layer) = l {
layer
.incidence
.get(&node_index.1)
.map_or(0, |edges| edges.len())
} else {
0
}
})
.sum(),
)
}
fn connected_components(&self) -> Vec<Vec<MultiplexIndex>> {
let mut visited = vec![false; self.base.len()];
let mut components = Vec::new();
for i in 0..self.base.len() {
if !visited[i] {
let mut component = Vec::new();
let mut stack = vec![i];
while let Some(node_index) = stack.pop() {
if !visited[node_index] {
visited[node_index] = true;
component.push(MultiplexIndex(None, node_index));
stack.extend(
self.get_neighbours(node_index, |_| true)
.unwrap()
.iter()
.cloned(),
);
}
}
components.push(component);
}
}
components
}
type Subgraph = Self;
fn component(&self, node_index: usize) -> Option<Vec<usize>> {
let mut visited = vec![false; self.base.len()];
let mut component = Vec::new();
let mut stack = vec![node_index];
while let Some(node_index) = stack.pop() {
if !visited[node_index] {
visited[node_index] = true;
component.push(node_index);
stack.extend(self.get_neighbours(node_index, |_| true)?.iter().cloned());
}
}
Some(component)
}
fn extract_component(&self, node_index: usize) -> Option<Self::Subgraph> {
let component_nodes = self.component(node_index)?;
Some(self.induced_shgraph(&component_nodes))
}
fn degree_by_order(&'a self, node_index: MultiplexIndex, order: usize) -> Option<usize> {
if node_index.1 >= self.base.nodes.len() {
return None;
}
Some(
self.layers
.iter()
.map(|l| {
if let WeakLayer::Undirected(layer) = l {
layer
.incidence
.get(&node_index.1)
.map_or(0, |edges| if edges.len() == order { order } else { 0 })
} else {
0
}
})
.sum(),
)
}
}
impl<'a, N, L> DiGraphProperties<'a> for MultiplexGraph<N, L>
where
N: Clone + Eq + Hash + 'a,
L: Clone + Eq + Hash + 'a,
{
fn in_neighbours(
&self,
node_index: MultiplexIndex,
) -> Option<hashbrown::HashSet<MultiplexIndex>> {
let neighbours = self.get_in_neighbours(
node_index.1,
if let Some(_) = node_index.0 {
Box::new(|i| Some(i) == node_index.0) as Box<dyn Fn(usize) -> bool>
} else {
Box::new(|_| true) as Box<dyn Fn(usize) -> bool>
},
);
neighbours.map(|n| {
n.into_iter()
.map(|&x| MultiplexIndex(node_index.0, x))
.collect()
})
}
fn out_neighbours(
&self,
node_index: MultiplexIndex,
) -> Option<hashbrown::HashSet<MultiplexIndex>> {
let neighbours = self.get_out_neighbours(
node_index.1,
if let Some(_) = node_index.0 {
Box::new(|i| Some(i) == node_index.0) as Box<dyn Fn(usize) -> bool>
} else {
Box::new(|_| true) as Box<dyn Fn(usize) -> bool>
},
);
neighbours.map(|n| {
n.into_iter()
.map(|&x| MultiplexIndex(node_index.0, x))
.collect()
})
}
fn in_edges(
&'a self,
node_index: MultiplexIndex,
) -> Option<hashbrown::HashSet<MultiplexIndex>> {
if let Some(layer_index) = node_index.0 {
if let WeakLayer::Directed(layer) = &self.layers[layer_index] {
Some(
layer
.incidence
.get(&node_index.1)?
.0
.iter()
.map(|&e| MultiplexIndex(Some(layer_index), e))
.collect(),
)
} else {
None
}
} else {
Some(
self.layers
.iter()
.enumerate()
.filter_map(|(i, l)| {
if let WeakLayer::Directed(layer) = l {
layer.incidence.get(&node_index.1).map(|edges| {
edges
.0
.iter()
.map(|&e| MultiplexIndex(Some(i), e))
.collect::<Vec<_>>()
})
} else {
None
}
})
.flatten()
.collect(),
)
}
}
fn in_edge_count(&'a self, node_index: MultiplexIndex) -> Option<usize> {
if let Some(layer_index) = node_index.0 {
if let WeakLayer::Directed(layer) = &self.layers[layer_index] {
Some(layer.incidence.get(&node_index.1)?.0.len())
} else {
None
}
} else {
Some(
self.layers
.iter()
.enumerate()
.filter_map(|(_i, l)| {
if let WeakLayer::Directed(layer) = l {
layer
.incidence
.get(&node_index.1)
.map(|edges| edges.0.len())
} else {
None
}
})
.sum(),
)
}
}
fn out_edges(
&'a self,
node_index: MultiplexIndex,
) -> Option<hashbrown::HashSet<MultiplexIndex>> {
if let Some(layer_index) = node_index.0 {
if let WeakLayer::Directed(layer) = &self.layers[layer_index] {
Some(
layer
.incidence
.get(&node_index.1)?
.1
.iter()
.map(|&e| MultiplexIndex(Some(layer_index), e))
.collect(),
)
} else {
None
}
} else {
Some(
self.layers
.iter()
.enumerate()
.filter_map(|(i, l)| {
if let WeakLayer::Directed(layer) = l {
layer.incidence.get(&node_index.1).map(|edges| {
edges
.1
.iter()
.map(|&e| MultiplexIndex(Some(i), e))
.collect::<Vec<_>>()
})
} else {
None
}
})
.flatten()
.collect(),
)
}
}
fn out_edge_count(&'a self, node_index: MultiplexIndex) -> Option<usize> {
if let Some(layer_index) = node_index.0 {
if let WeakLayer::Directed(layer) = &self.layers[layer_index] {
Some(layer.incidence.get(&node_index.1)?.1.len())
} else {
None
}
} else {
Some(
self.layers
.iter()
.enumerate()
.filter_map(|(_i, l)| {
if let WeakLayer::Directed(layer) = l {
layer
.incidence
.get(&node_index.1)
.map(|edges| edges.1.len())
} else {
None
}
})
.sum(),
)
}
}
fn in_neighbour_count(&'a self, node_index: MultiplexIndex) -> Option<usize> {
let neighbours = self.get_out_neighbours(
node_index.1,
if let Some(_) = node_index.0 {
Box::new(|i| Some(i) == node_index.0) as Box<dyn Fn(usize) -> bool>
} else {
Box::new(|_| true) as Box<dyn Fn(usize) -> bool>
},
)?;
Some(neighbours.len())
}
fn out_neighbour_count(&'a self, node_index: MultiplexIndex) -> Option<usize> {
let neighbours = self.get_out_neighbours(
node_index.1,
if let Some(_) = node_index.0 {
Box::new(|i| Some(i) == node_index.0) as Box<dyn Fn(usize) -> bool>
} else {
Box::new(|_| true) as Box<dyn Fn(usize) -> bool>
},
)?;
Some(neighbours.len())
}
fn strongly_connected_components(&self) -> Vec<Vec<usize>> {
todo!()
}
fn strong_component(&self, node_index: MultiplexIndex) -> Option<Vec<usize>> {
todo!()
}
fn extract_strong_component(&self, node_index: MultiplexIndex) -> Option<Self::Subgraph> {
todo!()
}
fn condense(&self) -> crate::prelude::DiGraph<(), ()> {
todo!()
}
fn weakly_connected_components(&self) -> Vec<Vec<usize>> {
todo!()
}
fn weak_component(&'a self, node_index: MultiplexIndex) -> Option<Vec<usize>> {
todo!()
}
fn extract_weak_component(&'a self, node_index: MultiplexIndex) -> Option<Self::Subgraph> {
todo!()
}
fn in_degree(&'a self, node_index: MultiplexIndex) -> Option<usize> {
todo!()
}
fn out_degree(&'a self, node_index: MultiplexIndex) -> Option<usize> {
todo!()
}
type Subgraph = Self;
fn source(
&'a self,
edge_index: <Self as GraphBasics<'a>>::EdgeIndex,
) -> Option<hashbrown::HashSet<MultiplexIndex>> {
todo!()
}
fn target(
&'a self,
edge_index: <Self as GraphBasics<'a>>::EdgeIndex,
) -> Option<hashbrown::HashSet<MultiplexIndex>> {
todo!()
}
}
impl<'a, N: 'a, L: 'a> HypergraphBasics<'a> for MultiplexGraph<N, L>
where
N: Clone + Eq + Hash,
L: Clone + Eq + Hash,
{
fn uniform(&self) -> bool {
if self.layers.is_empty() {
return true;
}
let o = match self.layers.first().unwrap() {
WeakLayer::Undirected(weak_ulayer) => weak_ulayer.uniform(),
WeakLayer::Directed(weak_dlayer) => weak_dlayer.uniform(),
};
if self.layers.iter().all(|l| match l {
WeakLayer::Undirected(weak_ulayer) => weak_ulayer.uniform() == o,
WeakLayer::Directed(weak_dlayer) => weak_dlayer.uniform() == o,
}) {
o
} else {
false
}
}
type DualType = ();
fn dual(&self) -> Self::DualType {
()
}
}
impl<'a, N: 'a, L: 'a> HypergraphProperties<'a, N, ()> for MultiplexGraph<N, L>
where
N: Clone + Eq + Hash,
L: Clone + Eq + Hash,
{
fn order(&'a self, edge_index: MultiplexIndex) -> Option<usize> {
match self.edge(edge_index)? {
MultiplexEdge::Directed(_, _) => None,
MultiplexEdge::Undirected(_, edge) => Some(edge.nodes.len()),
}
}
fn graph_view(&self) -> crate::prelude::Graph<&N, &()> {
todo!()
}
}
impl<'a, N: 'a, L: 'a> DirectedHypergraphProperties<'a, N, ()> for MultiplexGraph<N, L>
where
N: Clone + Eq + Hash,
L: Clone + Eq + Hash,
{
fn in_order(&self, edge_index: <Self as GraphBasics<'a>>::EdgeIndex) -> Option<usize> {
match self.edge(edge_index)? {
MultiplexEdge::Directed(_, directed_multiplex_edge) => {
Some(directed_multiplex_edge.source.len())
}
MultiplexEdge::Undirected(_, _) => None,
}
}
fn out_order(&self, edge_index: <Self as GraphBasics<'a>>::EdgeIndex) -> Option<usize> {
match self.edge(edge_index)? {
MultiplexEdge::Directed(_, directed_multiplex_edge) => {
Some(directed_multiplex_edge.target.len())
}
MultiplexEdge::Undirected(_, _) => None,
}
}
fn digraph_view(&self) -> crate::prelude::DiGraph<&N, &()> {
todo!()
}
}